从决策树到XGBOOST

1.引子

XGBoost在机器学习领域可谓风光无限，作为从学术界来的模范生，帮助工业界解决了许多实际问题，真可谓：

模型锋从学界出，算法香自公式来。

限于篇幅，本文就不展开赞美XGBoost了。笔者使用XGBoost解决了一些实际问题，但对其本质一直有点模棱两可，或者说对XGBoost从原理到工程实现没有一个清晰认识。作为一名技术男，有必要刨根问底下。本身对机器学习模型有一定了解的应该清楚，XGBoost本质上属于树形算法（不严谨，XGBoost也支持线性集成算法，但是本文着重从树算法的维度剖析XGBoost），可以说决策树是XGBoost的基础。进一步的，随机森林作为集成学习之光基于决策树实现，一定程度上解决了决策树容易过拟合的问题。在此基础之上，GBDT类算法横空出世，尝试基于boosting将集成学习发扬光大，XGBoost就是GBDT类算法中的佼佼者。基于这个进化背景，本文按照决策树->随机森林->GBDT->xgboost这个路径来阐述XGBoost。为了方便描述，本文中的分类均指二分类。

2.什么是决策树

决策树（Decision Tree，DT）是一种简单的机器学习方法，其本质是一堆决策结构以树形组合起来，叶子节点代表最终的预测值或类别。决策树本质上是在做若干个决策，以判定输入的数据对应的类别（分类）或数值（回归）。每一次决策其实是一次划分，划分的方法成为了关键，不同的决策树对应不同的划分方法。常见的DT有三种：ID3、C4.5和CART，这三种方法分别提出于1986年、1993年和1984年，可见决策树是一种持久经典的机器学习方法，下面分别介绍这三种树。

2.1 ID3

决策的本质是划分，划分的本质是将分析目标分成两个集合，如果两个集合均指包含一个类别，那么这次划分就是最好的划分。ID3采用信息增益来度量划分的质量，在介绍信息增益之前，介绍下信息熵的概念。

假设当前样本集合D中包含两类样本，所占的比例为p1和p2，那么D的信息熵是：

Ent(D) = -(p1logp1+p2logp2)

信息熵越小，D的纯度越高，具体这个信息熵的具体含义推荐去看这个：什么是信息熵？。怎么找到最佳信息熵的划分呢？使用计算机最擅长的方法：轮询，即按照样本中出现的所有属性值（假设为N个）做N次划分，分别计算N次划分的信息熵，选出最小的那个划分。

假定在离散属性a上有V个可能的取值，若使用a对样本集D做划分，则产生V个分支，记Dv为a值为v的集合，信息增益的定义如下：

一般而言，信息增益越大，代表着使用属性a进行划分获得的”纯度提升越大“，也就是使用信息增益最大的属性进行划分。

2.2 C4.5

信息增益方法存在一个缺点：倾向于选择取值多的属性，因为取值越多，每个子集合的纯度就越好，这就导致信息增益越大。为了改善这个问题，C4.5算法采用”增益率“择优划分，其公式如下：

其中IV(a)称为a的固有值，a的取值数目越多，IV(a)越大。可以看出，这个操作就是为了将具有多取值的属性的信息增益降下去，有”枪打出头鸟“的意思。但是C4.5并不是直接选择增益率最大的属性进行划分，因为这样的话就是偏向于取值较小的属性了，即所谓的矫枉过正。C4.5的做法是：先找出信息增益高于平均水平的属性，再从这些属性中选增益率最高的那个进行划分。也是辛苦的C4.5的发明者，像在走钢丝，左也不行右也不行。

2.3 CART

CART——Classification And Regression Tree，分类与回归树，所以说这其实是两棵树，一颗是CART分类树、一颗是CART回归树，下面分别介绍着两棵树

CART分类树与ID3/C4.5使用信息增益不同，CART分类树使用基尼指数选择划分属性，公式如下：

物理意义上来说，Gini(D)反应了数据集D中随机抽取两个样本，其类别标记不一致的概率，因此Gini越小，数据集纯度越高。

类似上面的计算方式，属性a的基尼指数是：E|Dv|/|D|Gini(Dv)。

CART分类树的划分就是找到一个划分后Gini最小的属性进行划分。

CART回归树

CART回归树也利用二分划分数据。与分类树不同的是，回归树将特征值大于切分点值的数据划分为左子树，将特征值小于等于切分点值的数据划分为右子树。 回归树用平方误差选择切分点，即选择最小的平方误差来进行划分。若数据集按特征取值是否大于切分点值划分为两部分，平方误差的公式为：

[公式]

其中M是左子树样本数量，N是右子树样本数量。

3.什么是随机森林

决策树的优点是简单，逻辑清晰，具备可解释性，但是也有一个很大的缺点：非常容易过拟合，解决过拟合的方法主要是有剪枝、随机森林，这里就不放开讲剪枝了，因为本文目标主要是说清楚XGBoost，下面说下随机森林。

从随机森林的名字上就能猜出，这种方法无非是信奉”树多力量大“这句话把诸多决策树集成在一起，进而形成一个更强大的树树树模型。随机森林是一个Bagging方法，Bagging是一种有放回抽样方法：取出一个样本加入训练集，然后再把该样本放回原始样本空间，以使下次取样本依然能取到该样本。使用这种方式，可以取样出T个包含m个样本的训练集，并且每个训练集都不一样。随机森林在Bagging的基础上，进一步在决策树的训练过程中引入了一些随机性：在决定划分属性的时候，先随机选择一个包含k个属性的子集，然后再从子集中选择一个最优属性进行划分，这也是随机的内涵。

随机森林简单、容易实现、计算开销小，而且在实际任务中表现良好，可谓集成学习之光。可以看出随机森性的好表现一是来源于Bagging在采样阶段的随机性，二是源于在构建树阶段引入的属性随机。这两个随机增强了模型整体的泛化能力，也就是针对性的解决了决策树的易过拟合的问题。

虽然说随机森林相对于决策树提升了很多，但是有心的小伙伴应该能看出来：随机森林内决策树之间其实是独立的，也就是说每棵决策树都是一颗孤立的树，没有对周围的树产生正面影响，这也是GBDT改进的地方。

4.什么是GBDT

大名鼎鼎的GBDT——Gradient Boosting Decision Tree，又称Multiple Additive Regression Tree，后面这种叫法不常看到，但是Regression Tree却揭示了GBDT的本质——GBDT中的树都是回归树，这点非常重要。我们先不看后面这个陌生的名字，只看GBDT——梯度提升决策树，分两部分理解他，一是提升决策树，二是梯度提升。

先来说下提升，在介绍随机森林的时候，我们可以知道随机森林内各个树之间是没有关联的，提升树其实就是针对这一点做的提升：每棵树都是以前一棵树的残差为学习目标去拟合，模型最终的输出是将所有树的结果相加。这也是说为什么GBDT的树全都是回归树的原因——因为分类树的结果不能使用加法模型，也就是无法提升。这其实就是BDT的本质了：森林中的每棵树是有序的，第二颗树学习的目标是上一课树的残差，整个算法的输出是每棵树结果的和。举个例子，我们要预测一个人的年龄，假如训练数据中A的年龄是30，我们第一棵树学习的结果将A分在了年龄27的叶子节点，那么A的残差就是30-27=3。我们第二颗树的目标就是拟合上一课树的残差，也就是针对A拟合3这个结果。第三棵树第四棵树的建树逻辑也类似于第二颗树，直到算法到达终止状态，这个终止状态一般是超参：树的个数。

再来说下梯度，前面介绍提升决策树时，我们默认每棵树的提升是以上一棵树的残差为拟合目标，为什么呢？因为我们默认损失函数是平方损失函数，也就是（y-f(x)）^2，此时我们的提升方向就是残差。但是当算法的损失函数不是平方损失函数时，我们怎么确认提升的方向呢？答案就是按照损失函数反梯度去优化，这是一个很直接、简单的思维，但是要理解梯度的概念，建议看这篇文章：什么是梯度？简单来说梯度是一个向量，既有方向又有大小，其方向是最大方向导数的方向，其大小是最大方向导数的大小 。梯度解决的问题是：函数在变量空间的某一点处，沿着哪一个方向有最大的变化率？需要指出的是，梯度在数学本质上是一阶导数，GBDT使用梯度这个指标指导优化的方向。可以这么说，提升决策树中的拟合残差是拟合负梯度的一种特例；或者说，梯度提升是将这种方法扩展到更其他复杂损失函数的一种通用化途径。

总结来说，GBDT算法基树采用CART回归树，树节点的划分指标是平方损失函数，叶子节点的值是落在该叶子节点所有样本的目标均值。树与树之间的Boosting逻辑是：新树拟合的目标是上一课树的损失函数的负梯度的值。GBDT最终的输出结果是将样本在所有树上的叶子值相加。

可以看出，GBDT最核心的两部分，Boosting提升说明每棵树之间是有关系有序的、Gradient梯度指明了提升的方向与大小。

最后说下GBDT的正则化，主要有以下措施：

1，Early Stopping，本质是在某项指标达标后就停止训练，也就是设定了训练的轮数；

2，Shrinkage，其实就是学习率，具体做法是将没课树的效果进行缩减，比如说将每棵树的结果乘以0.1，也就是降低单棵树的决策权重，相信集体决策；

3，Subsampling，无放回抽样，具体含义是每轮训练随机使用部分训练样本，其实这里是借鉴了随机森林的思想；

4，Dropout，这个方法是论文里的方法，没有在SKLearn中看到实现，做法是每棵树拟合的不是之前全部树ensemble后的残差，而是随机挑选一些树的残差，这个效果如何有待商榷。

5.什么是XGBoost

介绍到这里，XGBoost的出现就更倾向于一种顺其自然的进化，也就是说xgboost并不是孤立的，是从决策树、随机森林、GBDT一步步打怪升级而来。

Anyway，XGBoost仍然是Gradient Boosting算法，那么以下两个主线问题是必须要回答的

1，XGBoost基树和基树之间是怎么进行boosting的？

2，XGBoost是怎么创建基树的？

我们来剖析主线问题，上面已经说到GBDT类的方法所采用的树都是回归树，XGBoost当然不例外。那么XGBoost是怎么在树和树之间做提升的呢？也就是要回答如下问题：

有了第t-1棵树，怎么得到第t棵树？

首先，我们列出XGBoost的目标函数：

[公式]

第一项是损失函数，衡量预测值与真实值的差距；

第二项欧米伽是正则项，表示树的复杂度，用来避免过拟合，具体公式如下：

[公式]

需要指出的是，在目标函数中增加正则项是XGBoost的一项比较重要的改进，因为GBDT中的正则化主要依靠一些工程措施，局限性与可操作性较差。XGBoost则直接将正则项加入到目标函数中，这样一来，每一轮的迭代均在数学层面进行了正则化，效果与可操作性大大提升。

针对第t轮的迭代，其目标函数如下：

[公式]

注意，上式中第t-1轮的预测是已知的，也就是已经有了t-1棵树。

然后使用二阶泰勒展开得到（具体为什么能使用泰勒公式二次展开看这里）：

[公式]

其中：

[公式]

,

[公式]

由于t-1轮的结果是已知的，可以去掉，去掉后公式如下 ：

[公式]

可以看出公式仅依赖于g和h，也就是一阶导和二阶导，这也是为什么XGBoost支持的自定义损失函数必须二阶可导的原因。

进一步将正则化项展开并合并，得：

[公式]

—————（公式1）

可以看出，对上式求最小值可以得到 ωj的最优值，如下：

[公式]

————（公式2）

公式2其最小值如下：

[公式]

————（公式3）

公式3可以用来衡量一个树的结构质量，可以将公式3理解为对决策树不纯度的衡量，也就是说可以使用公式3作为树节点分裂的依据，即衡量节点在分裂前后公式3对应数值的大小来判断是否需要分裂，如分列前公式3值为100，按照特征1分裂后两节点公式3的值相加为90，按照特征2分裂后两节点公式3的值相加为80，那么树就将按照特征2分裂。分裂增益公式如下：

[公式]

———（公式4）

从公式4上可以看出 γ 的存在可以在一定程度上控制分裂的程度。

公式4特别重要，他是XGBoost基树分裂的依据。

公式2同样重要，他是计算叶子节点值的公式。

结合公式2与4，就可以从第t-1棵树创建第t棵树。

综上所述，XGBoost的建树过程、boosting过程均是以目标函数为基础进行的，一切操作的衡量标准均是最小化目标函数，其采用的算法策略依然是贪心策略。由于引入了泰勒二阶展开，建树与boosting的过程仅依赖于损失函数的一阶导数与二阶导数，公式比较清晰易懂。整个推导使用二阶泰勒展开的一个最大好处是：支持自定义损失函数，仅要求损失函数二阶可导。另外XGBoost将正则项加入到了目标函数中，保证了每次的迭代均对模型的复杂度进行了对冲，有效降低了过拟合发生的可能性。

XGBoost的主线就是上面所介绍的部分，除此之外，XGBoost还有很多工程上的优化，如下：

1，对缺失值的处理，XGBoost可以自动学习出它的分裂方向；

2，支持并行，注意XGBoost的并行不是tree粒度的并行，XGBoost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。XGBoost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），XGBoost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行（摘录自此）；

3，近似算法（Approximate Algorithm），树节点在分裂时，需要枚举每个可能的分割点。当数据没法一次性载入内存时，这种方法会很慢。xgboost提出了一种近似的方法去高效的生成候选分割点；

除此之外，XGBoost基学习器不仅支持决策树，也支持线性分类器。也就是说，xgboost不仅是一种集成的树模型，也是一种集成的线性模型，也就是带L1和L2的逻辑斯底回归或逻辑回归。所以严格来说xgboost已经不仅仅是GBDT，而是GBM（Gradient Boosting Machine），所以说xgboost这个名字起的非常严谨。

除去目标函数自带的正则化项，XGBoost也支持Shrinkage和Subsampling。

6.总结

从决策树、随机森林、GBDT最终到XGBoost，每个热门算法都不是孤立存在的，而是基于一系列算法的改进与优化。决策树算法简单易懂可解释性强，但是过拟合风险很大，应用场景有限；随机森林采用Bagging采样+随机属性选择+模型集成的方法解决决策树易过拟合的风险，但是牺牲了可解释性；GBDT在随机森林的基础上融合boosting的思想建立树与树之间的联系，使森林不再是互相独立的树存在，进而成为一种有序集体决策体系；XGBoost在GBDT的基础上更进一步，将每轮迭代的目标函数中加入正则项，进一步降低过拟合的风险。相对于GBDT启发式的迭代原则，XGBoost的优化准则完全基于目标函数的最小化推导，并采用了二阶泰勒展开，使自定义损失函数成为可能。除此之外，XGBoost同样继承了随机采样、随机属性选择、学习率等算法实用技巧，与此同时实现了属性计算级别的并行化。可以说，XGBoost是一种集大成的机器学习算法。