决策树(下)-Xgboost

参考资料(要是对于本文的理解不够透彻，必须将以下博客认知阅读，方可更加了解Xgboost)：

1.对xgboost的理解(参考资料1和4是我认为对Xgboost理解总结最透彻的两篇文章，其根据作者paper总结!)

2.手动还原XGBoost实例过程(提供了一个实例，方便读者更加了解算法过程)

3.手写xgboost(利用python手写实现xgb)

4.XGBoost超详细推导(参考资料1和4是我认为对Xgboost理解总结最透彻的两篇文章)

什么是XGBoost？

XGBoost是Exterme Gradient Boosting（极限梯度提升）的缩写，它是基于决策树的集成机器学习算法，它以梯度提升（Gradient Boost）为框架。XGBoost是由由GBDT发展而来，同样是利用加法模型与前向分步算法实现学习的优化过程，但与GBDT是有区别的。主要区别包括以下几点：

• 目标函数：XGBoost的损失函数添加了正则化项，使用正则用以控制模型的复杂度，正则项里包含了树的叶子节点个数、每个叶子节点权重（叶结点的socre值）的平方和。
• 优化方法：GBDT在优化时只使用了一阶导数信息，XGBoost在优化时使用了一、二介导数信息。
• 缺失值处理：XBGoost对缺失值进行了处理，通过学习模型自动选择最优的缺失值默认切分方向。
• 防止过拟合: XGBoost除了增加了正则项来防止过拟合,还支持行列采样的方式来防止过拟合。
• 结果：它可以在最短时间内用更少的计算资源得到更好的结果。

XGBoost的基学习器

XGBoost的可以使用Regression Tree（CART）作为基学习器，也可以使用线性分类器作为基学习器。以CART作为基学习器时，其决策规则和决策树是一样的，但CART的每一个叶节点具有一个权重，也就是叶节点的得分或者说是叶节点的预测值。CART的示例如下图：

图中为两颗回归树（左右两个），其中树下方的输出值即为叶节点的权重（得分），当输出一个样本进行预测时，根据每个内部节点的决策条件进行划分节点，最终被划分到的叶节点的权重即为该样本的预测输出值。

XGBoost的模型

XGBoost模型的定义为：给定一个包含n个样本m个特征的数据集，  ，集成模型的预测输出表示为：

 （1）

其中，  表示回归树， 为回归树的数量。整个式（1）表示给定一个输入  ，输出值为  颗回归树得预测值（即按照相应回归树的决策规则，所划分到的叶节点的权重）相加。那么我们如何去学习这个模型？

模型的学习

通常情况下，怎样去学习一个模型？

1. 定义目标函数，即损失函数以及正则项。
2. 优化目标函数。

第一步：定义XGBoost的目标函数

 (2)

其中 

公式（2）右边第一部分是度量预测值与真实值之间的损失函数，第二部分表示对模型复杂度的惩罚项（正则项），

•   、  表示惩罚系数(超参数，提前设定)，
•   表示给定一颗树的叶节点数，
•   表示每颗树叶节点上的输出分数的平方(相当于L2正则)。

从目标函数的定义可以看出XGBoost对模型复杂度(树的复杂度)考虑了每颗树的叶节点个数，以及每颗树叶节点输出得分值得平方和。

第二步：优化目标函数。

在通常的模型中针对这类目标函数可以使用梯度下降的方式进行优化，但注意到  表示的是一颗树，而非一个数值型的向量，所以不能使用梯度下降的方式去优化该目标函数。那么怎么优化这个目标函数呢？前向分步算法！！！

使用前向分步算法优化目标函数。设  是第i个样本在第t次迭代（第t颗树）的预测值。则

 (3)

公式（3）表示样本i在t次迭代后的预测值 = 样本i在前 t - 1 次迭代后的预测值 + 当前第 t 颗树预测值。则目标函数可以表示为：

式（4）表示贪心地添加使得模型提升最大的  其中constant表示常数项,这个常数项是指前 t - 1 次迭代的惩罚项为一个常数，即公式中  部分，在第 t 次迭代时，前 t - 1 次迭产生的 t - 1 颗树已经完全确定，则 t - 1 颗树的叶节点以及权重都已经确定，所以变成了常数。.在式（4）中如果考虑平方损失函数，则式（4）可以表示为：

式5中  表示残差，即经过前 t - 1 颗树的预测之后与真实值之间的差距，也就是在GBDT中所使用的残差概念。在XGBoost中提出使用二阶泰勒展开式近似表示式5.泰勒展开式的二阶形式为：

 (式6)

定义  则根据式6可以将式4表示为：

 (式7)

注意式7中  部分表示前 t - 1 次迭代的损失函数，在当前第 t 次迭代来说已经是一个确定的常数，省略常数项则得到下面的式子：

 （式8）

则我们的目标函数变成了公式8.可以看出目标函数只依赖于数据点的一阶和二阶导数。其中 

重新定义一颗树

包括两个部分：

• 叶子结点的权重向量 ω ；
• 实例 -> 叶子结点的映射关系q（本质是树的分支结构）；

一棵树的表达形式定义如下：

定义树的复杂度

我们定义一颗树的复杂度 Ω，它由两部分组成：

• 叶子结点的数量；
• 叶子结点权重向量的L2范数；

定义完树以及树的复杂度之后，接下来针对公式8进行细分。首先定义集合 为树的第j个叶节点上的所有样本点的集合，即给定一颗树，所有按照决策规则被划分到第j个叶节点的样本集合。则根据式2中对模型复杂度惩罚项的定义，将其带入式8有：

• 式9就是最终的损失函数的形式了。不知道面试直接写这个行不行。T表示叶子结点个数，
• 解释一下式9，以叶子节点为基础进行求和，每一个叶子节点中所有样本的的一阶梯度与叶节点的输出值的乘积 加上 0.5的这个叶子节点所有样本的二阶梯度与lambada正则化系数之和与叶子节点的输出值的平方的乘积，这一系列式子求和之后再加上gamma与这棵树的所有叶子节点的个数的和的成绩，就得到了最终的损失函数的形式了。

对式9进行求导：

插入一个小知识点：

这里我们和传统的gbdt做对比，传统的gbdt的叶节点值是这样的：

传统的gbdt的基树是cart tree，叶节点值的预测输出是这个叶节点值的所有样本的标签的平均值，单纯从单个cart tree的角度（不涉及gbm框架）来说，如果是回归问题，某个叶子节点的预测输出就是这个叶子节点所有样本的标签值的平均，比如说回归问题中某个叶子节点所有的样本的标签是[0.5,0.4,0.0]，则预测输出就是三者的平均0.3，传统的gbdt也是一样的，只不过每一轮要拟合的标签值是前面所有所有tree预测结果与真实标签值计算出来的负梯度而已，比如第t轮，某个叶子节点的值为[0.3,0.4,0.2]（这里的值是上一轮拟合得到的损失函数的负梯度），则预测输出就是简单的求平均0.3。也就是上面的这个式子：

而xgboost通过复杂的推导最后得出结论，叶子节点值不应该是简单的上一轮负梯度的均值，应该加入二阶负梯度和树的正则化系数，于是就得到了：

将（式10）带入（式9）中得到（式11）：

 (式11)

令  则，（式11）可以简化为（式12）

 （式12）

到目前我们得到了（式12）[损失函数的最终形式]，xgb通过二阶泰勒展开并且引入了树的正则化的概念将原始的简单的损失函数的形式转化为了上面的这个新的损失函数的形式。而传统的gbdt的损失函数只有上面的Gj一项而已。这个损失函数(式12)是可以做为得分值评价一颗树的好坏，那么评价一颗树的好坏有什么用呢？

• 可以用于对的剪枝操作(防止过拟合),和决策树中的剪枝是一样的,给定一个损失函数,判断剪枝后,根据损失函数是否减小来决定是否执行剪枝,只是XGBoost是运用式12来作为损失函数判断的标准。注意到评价一颗树的还好的前提是我们能得到一颗树，上式也是基于给定一个树的前提下推导而来的，那么这颗树怎么来得到呢？

XGB模型的学习用一句话总结：xgb引入了树的正则化的概念，在原始的损失函数的基础上加入了正则项（类似与逻辑回归的损失函数加入了正则项）并且通过将带正则项的损失函数进行二阶泰勒展开推导出了叶子节点的新的计算方式。但每一轮要拟合的值还是负梯度。

树的生成

在决策树的生成中，我们用ID3、C4.5、Gini指数等指标去选择最优分裂特征、切分点(CART时)，XGBoost同样定义了特征选择和切分点选择的指标：

 （式13）

XGBoost中使用过（式13）判断切分增益，Gain值越大，说明分裂后能使目标函数减少越多，就越好。其中  表示在某个节点按条件切分后左节点的得分，  表示在某个节点按条件切分后右节点的得分，  表示切分前的得分，  表示切分后模型复杂度的增加量。现在有了判断增益的方法，就需要使用该方法去查找最优特征以及最优切分点。

分裂查找算法

关于最优特征以及最优切分点的选取XGBoost提供了两个算法。

1. Basic Exact Greedy Algorithm （精确贪心算法）
2. Approximate Algorithm（近似算法）

精确贪心算法类似于CART中最优特征与切分点的查找，通过遍历每个特征下的每个可能的切分点取值，计算切分后的增益，选择增益最大的特征及切分点。具体算法流程如下

因为精确贪心算法需要遍历所有特征和取值，当数据量非常大的时候，无法将所有数据同时加载进内存时，精确贪心算法会非常耗时，XGBoost的作者引进了近似算法。近似算法对特征值进行了近似处理，即根据每个特征k的特征值分布，确定出候选切分点  ，即按特征分布将连续的特征值划分到  个候选点对应的桶（buckets）中，并且对每个桶中每个样本的  进行累加。候选切分点的划分以及  的累加过程如下：

划分好候选切分点之后，按照精确贪心算法描述的算法步骤进行选择最优切分特征与最优切分点，不同的是切分点被上述候选切分点所代替，但原理和操作过程是一样的。

在近似算法的伪代码图中，作者提到可以按照global的方式提出候选切分点，也可以按照local的方式提出候选切分点。

什么是global方式？什么是local方式？简单的说就是什么时候提取候选切分点，即在哪一个步骤进行候选切分点的提取。global表示在生成树之前进行候选切分点的提取，即开始之前为整颗树做一次提取即可，在每次的节点划分时都使用已经提取好的候选切分点。而local则是在每次节点划分时才进行候选切分点的提取。那么区别是什么呢？

• global方式进行候选切分点提取的次数少。因为只是在初始化的阶段进行一次即可，以后的节点切分均使用同一个，而local方式是在每次节点切分时才进行，需要很多次的提取。
• global方式需要更多的候选点，即对候选点提取数量比local更多，因为没有像local方式一样每次节点划分时，对当前节点的样本进行细化，local方式更适合树深度较大的情况。

上图是作者在Higgs boson 数据集上对两种方式的测试，可以看出local需要更少的候选切分点，当global方式有足够多的候选点时正确率与local相当。

下面对近似算法举个栗子做为说明。

图示中特征值被切分成三个候选切分点，位于0~  处的样本被划分到第一个桶中， 位于 之间的样本分别被划分到第二个和第三个桶中。那么在计算最优切分点时，就有两种划分方式，第一种方式，即第一个桶的样本被切分到左节点中，第二、三个桶的样本被切分到右节点中。其增益gain为max函数中第二项。第二种划分方式为，第一、二个桶中的样本切分到左节点中，第三个桶中的样本切分到右节点中，其增益为max函数中第三项。那么max函数第一项表示什么呢？第一项表示的是其他特征切分点确认后的最大增益，与当前特征的两种切分方式比较，选择最优的特征及其切分点。

注意到栗子在对样本进行划分时，考虑的是样本的个数，即每个桶中样本个数相同为出发点来划分的，如果样本有权重呢？直观上的想法是，那就考虑权重而不是个数呗。那么每个样本应该赋予什么样的权重?又怎样去处理这个权重？

加权分位数略图（Weighted Quantile Sketch）

为了处理带权重的候选切分点的选取，作者提出了Weighted Quantile Sketch算法。加权分位数略图算法提出一种数据结构,这种数据结构支持merge和prune操作。作者在论文中给出了该算法的详细描述和证明链接(ps:已经失效),这里不做详细介绍。可以参考链接加权分位数略图定义及证明说明。简单介绍加权分位数略图侯选点的选取方式。

设数据集  表示每个样本的第k个特征值(  )和二阶导数(  )的集合。定义排名函数  ：

 （式14）

（式14）表示数据集中第k个特征值小于z的样本所在比例（公式看起来貌似有点奇怪，简单来说就是特征值小于z的样本的权重和，占所有样本权重总和的百分比）。我们的目标是找到一个候选切分点（也就是说怎么去划分候选点的问题），可以根据下式进行侯选点的选取  （式15）

简单的说（式15）表示落在两个相邻的候选切分点之间样本占比小于某个值  （很小的常数），那么我们就有  个候选切分点。

由（式14）看的样本是以二阶导数作为加权考虑占比的，那么问题来了，为什么使用二阶导数作为加权呢？

对目标函数（式8）进行改写，过程如下：

（式16）可以看成权重 为 的label为  （ps：这个值比作者论文中多出一个负号，有文章说作者论文里面少写了负号。个人觉得这个正负号不是关注重点，它不是一种定量的计算，而是表示一种以二阶导数作为加权的合理性说明。）的平方损失函数，其权重  则为二阶导数。由此表明将二阶导数作为样本权重的考虑是合理的。

其他优化方法

• 稀疏值处理（Sparsity-aware Split Finding）。实际工程中一般会出现输入值稀疏的情况。比如数据的缺失、one-hot编码都会造成输入数据稀疏。论文中作者提出了关于稀疏值的处理，思路是：对于缺失数据让模型自动学习默认的划分方向。算法具体的方法如下：

从算法中可以看出，作者采用的是在每次的切分中，让缺失值分别被切分到左节点以及右节点，通过计算得分值比较两种切分方法哪一个更优，则会对每个特征的缺失值都会学习到一个最优的默认切分方向。乍一看这个算法会多出相当于一倍的计算量，但其实不是的。因为在算法的迭代中只考虑了非缺失值数据的遍历，缺失值数据直接被分配到左右节点，所需要遍历的样本量大大减小。

作者通过在Allstate-10K数据集上进行了实验，从结果可以看到稀疏算法比普通算法在处理数据上快了超过50倍。

• 分块并行（Column Block for Parallel Learning）。在树生成过程中，需要花费大量的时间在特征选择与切分点选择上，并且这部分时间中大部分又花费在了对特征值得排序上。那么怎么样减小这个排序时间开销呢？作者提出通过按特征进行分块并排序，在块里面保存排序后的特征值及对应样本的引用，以便于获取样本的一阶、二阶导数值。具体方式如图：

通过顺序访问排序后的块遍历样本特征的特征值，方便进行切分点的查找。此外分块存储后多个特征之间互不干涉，可以使用多线程同时对不同的特征进行切分点查找，即特征的并行化处理。

• XGBoost的并行，指的是特征维度的并行：在训练之前，每个特征按特征值对样本进行预排序，并存储为Block结构，在后面查找特征分割点时可以重复使用，而且特征已经被存储为一个个block结构，那么在寻找每个特征的最佳分割点时，可以利用多线程对每个block并行计算。

注意到，在顺序访问特征值时，访问的是一块连续的内存空间，但通过特征值持有的索引（样本索引）访问样本获取一阶、二阶导数时，这个访问操作访问的内存空间并不连续，这样可能造成cpu缓存命中率低，影响算法效率。那么怎么解决这个问题呢？缓存访问 Cache-aware Access 。

• 缓存访问（Cache-aware Access）。为了减小非连续内存的访问带来缓存命中率低问题，作者提出了缓存访问优化机制。解决思路是：既然是非连续内存访问带来问题，那么去掉非连续内存访问就可以解决。那么怎么能去掉非连续内存空间的访问呢？转非连续为连续----缓存预取。即提起将要访问的非连续内存空间中的梯度统计信息（一阶、二阶导数），放置到连续的内存空间中。具体的操作上就是为每个线程在内存空间中分配一个连续的buffer缓存区，将需要的梯度统计信息存放在缓冲区中。这种方式对数据量大的时候很有用，因为大数据量时，不能把所有样本都加入到内存中，因此可以动态的将相关信息加入到内存中。

上图给出了在Higgs数据集上使用缓存访问和不使用缓存访问的式样对比。可以发现在数据量大的时候，基于精确的贪心算法使用缓存预取得处理速度几乎是普通情况下的两倍。那么对于block块应该选择多大才合理呢？作者通过实验证明选择每个块存放  个样本时效率最高。

• "核外"块计算（Blocks for Out-of-core Computation）。当数据量非常大的是时候我们不能把所有数据都加载内存中，因为装不下。那么就必须的将一部分需要加载进内存的数据先存放在硬盘中，当需要时在加载进内存。这样操作具有很明显的瓶颈，即硬盘的IO操作速度远远低于内存的处理速度，那么肯定会存在大量等待硬盘IO操作的情况。针对这个问题作者提出了“核外”计算的优化方法。具体操作为，将数据集分成多个块存放在硬盘中，使用一个独立的线程专门从硬盘读取数据，加载到内存中，这样算法在内存中处理数据就可以和从硬盘读取数据同时进行。为了加载这个操作过程，作者提出了两种方法。
• 块压缩（Block Compression）。论文使用的是按列进行压缩，读取的时候用另外的线程解压。对于行索引，只保存第一个索引值，然后用16位的整数保存与该block第一个索引的差值。作者通过测试在block设置为  个样本大小时，压缩比率几乎达到26%  29%（貌似没说使用的是什么压缩方法.......）。
• 块分区（Block Sharding ）。块分区是将特征block分区存放在不同的硬盘上，以此来增加硬盘IO的吞吐量。
• 防止过拟合。从XGBoost的模型上可以看到，为了防止过拟合加入了两项惩罚项  、  ，除此之外XGBoost还有另外两个防止过拟合的方法。1.学习率。和GBDT一样XGBoost也采用了学习率（步长）来防止过拟合，表现为：  ，其中  就是学习率，通常取0.1。2.行、列采样。和随机森林一样XGBoost支持对样本以及特征进行采样，取采样后的样本和特征作为训练数据，进一步防止过拟合。

决策树(下)-Xgboost

原文：https://www.cnblogs.com/XDU-Lakers/p/11912265.html