xgboost分类_算法笔记：XGBoost: A Scalable Tree Boosting Sysem

最近看了陈天奇老师的论文XGBoost: A Scalable Tree Boosting Sysem，写个笔记整理一下思路。本文主要叙述算法idea以及自己的理解，不严谨的地方敬请谅解。如有错误欢迎指出，非常感谢！！（大三狗，并且本人对于工程方面不是很了解，主要记录算法上面的内容，不会提及论文后半部分对于数据存储系统的改进）

论文内容介绍

XGBoost可算是打比赛的一个网红算法，如果去看Kaggle的Top排行榜，基本都是被XGBoost占领。它是目前最快最好的开源算法，比常见的工具包快10倍以上，并且很少有别的集成算法学习效果能比得过调好参数的XGBoost（不过因为参数过多，XGBoost对调参要求也很高orz）。在数据量日益增大的情况下，XGBoost既能快速处理大数据量，并且由于其为端到端的系统（基本不用数据预处理），使其一跃成为竞赛宠儿。

论文主要贡献大致分为四个方面：

1. 设计并建立可扩展的，端到端的提升树系统。
2. 提供有效且可理论证明的weighted quantile sketch来计算候选集。
3. 介绍新颖的sparsity-aware algorithm来处理稀疏数据。
4. 提出高效的cache-aware block structure用于外存树学习。（涉及工程部分，暂不提及）

论文整体顺序也是基于这四个方面依次展开。

算法总结

基本思路：通过残差逼近思想拟合模型。

创新点：

• 通过泰勒二次展开，提高对目标函数的拟合精度。
• 定义正则化项，防止过拟合。
• 提供可理论验证的‘分箱’方法，减轻决策树分枝过程中遍历所有特征数值的负担。
• 工程优化（考虑硬件问题），①通过特征提前排序，实现并行化计算，同时避免重复计算；②block compression，尽可能把数据保存在内存中（内存读取更快）；③block sharing，将block放到多个磁盘，增大磁盘带宽，使读取更快。

或许可以提升的point：

• 对缺失值的处理增加一些随机性。
• 迭代过程使用自适应步长。

提出问题

机器学习的问题一般可分为：回归、分类、探索数据结构等。XGBoost是GBDT的改进版本，其每个基分类器是CART回归树，也就是解决

回归

问题的。当然，通过对回归问题的处理，也可以扩展到分类问题。

由于是解决回归问题，XGBoost的输入和输出都是一系列数值，并且由于其可对稀疏数据进行学习，我们唯一需要做的预处理就是对类别型变量进行转换。（独热编码等处理）

正如它的名称，XGBoost属于提升算法家族（boosting），是一个迭代过程，用来自适应地改变训练样本的分布。但是它的思想和家族另一成员Adaboost不同，Adaboost是在每一次提升结束时更新训练样本的权值，通过提高被错误分类样本的权重，降低被正确分类样本的权重，来使后面的分类器更关注那些被错误分类的样本。而XGBoost的思想属于提升树，下一个分类器是对于上个分类器的残差进行分类，即通过计算上个分类器的结果和正确答案的差值，将这个差值代入下个分类器进行计算。

个人认为boosting作为集成算法，就是召集一个团队一起解决一个问题。而这两种boosting的不同在于，Adaboost这个团队中每个人做的事情都差不多，只不过下一个人是基于他‘前辈’的经验来做决策，前辈把他没分出来的样本告诉下一个人，这样下一个人就能重点处理这些‘问题儿童’；而Gradient boosting团队里每个人都有自己擅长的一个方面，对于同一个问题，第一个人先处理一部分，得到一定成果（数值），但一个人力量不够大，这个数值离最终目标还有一定距离，而这个‘距离’（残差）就由后面的人来补上，最后团队做出来的结果就是所有人成果的总和。

目标函数

任何模型的学习都依赖于目标函数。

上文我们有提到，梯度提升最终的结果是所有基分类器的总和，这就意味着XGBoost是采用

分步前向加性模型

，我们的预测值

是所有基分类树结果的总和。

假设我们样本集D里有n个样本，m个特征，我们将这m个特征分别表示为

，则可以将样本集写为：

。

由于决策树的效果是空间分块，无法像线性回归那样，用固定参数表示目标函数，我们先用

来表示整个算法的效果，则我们的目标函数可以表示为：

这里的f可以理解为对于一个输入样本，单个基CART回归树的输出结果，即该样本所处叶子节点权重。

（题外话：最开始看的时候纠结了很久这里为什么叫‘权重’，后来想了一下，回归的本质就是自变量加权求和，应用到决策树中也是相似，而决策树能做到非线性边界，只是因为其在决策的时候将空间分了很多‘块’，在每一块内分别进行回归加权，所以叶子节点的输出相当于权重。另外还想到一种理解，在下文，进行泰勒展开后w就相当于对目标函数的一次导和二次导的加权。）

我们可以基于这个目标函数，

自己定义损失函数

，XGBoost的可延展性的一个体现就在于此。只要保证定义的损失函数是

二次可导

即可，这是由于在后面求导过程中需要用到泰勒二次展开。（其实也可以多项展开的，但是考虑到运行速度以及系统优化，作者在此进行了权衡。）

损失函数

XGBoost的其中一个改进点在于其在损失函数中添加正则项，可有效防止过拟合。基于上文定义的目标函数

，我们可以用

来表示对于每个CART树的损失函数，则算法的损失函数可表示为：

式中第二项即为正则项，T是该基回归树叶节点的数量，

就是每棵树叶子节点的输出权重的范数。正则项从基模型大小和其输出结果两个方面对整个模型进行惩罚。

（题外话：看到这里我总是想到AIC和BIC，特别是BIC，同时通过模型复杂度和样本数量两个方面对模型进行衡量；这里是通过模型复杂度（叶子节点数量）结合所有样本点预测

进行惩罚。莫名有点既视感www）

这里如果把正则项去掉，就是最原始的gradient tree boosting。

有了损失函数，我们就可以算梯度了。

这里体现了XGBoost基于梯度树的第二个改进点，

使用泰勒二次展开

，使得预测函数f更快速、精确的逼近真实值。（梯度树相当于一次展开）

由于提升树是将所有输出结果相加，并且我们之前提到了，这个团队里是‘每个人擅长的领域都不同’，也就是说每个人处理的问题其实是不一样的，可以某种程度上抽象为每棵树‘独立’。（下一棵树的输入是上一棵树的残差，也就是说下一棵树预测的结果是要等于这个差值，而不是真实标签值）

我们在看第t棵树的时候（第t次迭代），前（t-1）棵树的结果都是已定的，并且和本次建模‘无关’。所以我们只需要使得加上这次结果后，损失函数能最有效的降低即可。第t次迭代可写成：

可以发现就是前（t-1）次迭代结果

加上本次迭代结果

。

回顾一下泰勒二阶展开：

这里说一个我自己的理解：可以想象一下，整个boosting算法里面是有很多棵树的，并且由于我们加的正则之类的惩罚，每棵树的影响力可以算是比较小的，而我们的预测值

是关于f的函数，那么我们每次加入的f可以看做泰勒展开中的

。则

可展开为：

将展开结果写进损失函数，可以得到：

具体关于为什么目标函数关于当前模型的负梯度是残差的近似，请参考这位大大：

梯度提升树中为什么说目标函数关于当前模型的负梯度是残差的近似值？​www.zhihu.com

由于前（t-1）次迭代都已经有结果了，损失函数第一项是个定值，对于我们最小化损失函数没有影响，可以去掉以简化计算，得到：

还记得正则项里有

吗？

把正则项拆开，将

和方括号内的

合并可得：

令

，求得最优权重为：

得到最优解了！！？？慢着

定睛一看怎么有个下标

？？

作者这里定义的

是本次迭代中生成的基分类树在叶子节点j处样本的集合，也就是说我们要知道本轮迭代生成的

树的结构

，才能知道此最优解。

列举出所有可能生成的结构是不太可能的（这是个NP问题），我们需要用贪心算法找到尽可能好的分枝策略。根据预剪枝的原理，我们可以根据损失函数来衡量，分枝前后的效果，选择效果最好的特征进行分枝。即每次尝试分裂一个叶节点，根据分裂后的信息增益（在这里就是损失函数值）进行判断。

套用一个图：（查资料的时候顺手存的，忘记出处了orz）

由于推导的时候使用了以上打分公式，并且引入了正则项，XGBoost就不需要剪枝操作了。（普通决策树在生成的时候并不考虑树的复杂度，所以才需要进行剪枝操作）

再发散一下思维，还有没有其他方法进一步防止过拟合？（集成算法因为其自适应的改变训练样本的分布，天生容易引起过拟合，能避免就尽量避免）

XGBoost还提供两种方式防止过拟合

• Shrinkage （相当于增加learning rate，进一步减小每棵树的影响力）
• Column Subsampling （灵感来自随机森林的列采样，每次都随机抽取部分特征考虑分枝，提高特征信息利用率，还能加快选择速度）

关于shrinkage我联想到的一个可能改进的点在于自适应步长。（最近学微分方程用到的orz）

Adaboost对于每棵树输出值是有进行加权的，因为后面的树更注重分错的值，所以给它们加了更大的权重。XGBoost后面的树是根据前面的树的残差建立，如果可以给前面的树稍大一些的权值，后面的树稍小一些的权值，能进一步提高精度。（不过本来自适应步长在微分方程那里就很鸡助...这里如果用了说不定会进一步拖慢算法速度，所以应该只是理论上可行吧www）

寻找分裂点

有了目标函数、损失函数、衡量分枝的Gain函数，要知道回归树的结构，我们还需要知道具体是根据哪个特征的哪个值进行分裂。（这也是树算法中最关键以及最耗时耗力的一个步骤）

作者在文中提供了三种寻找分裂点的方式：

1. 贪心遍历所有可分裂节点
2. 等距找到一些候选分裂节点
3. 通过二次导h，定义rank函数，通过对节点rank值排序，找出备选点

前两个都是已经提出的做法，第三个是作者论文的主要贡献之一。

贪心建树策略就是遍历所有特征以及所有分裂点，每次去选最好的那个。分裂算法会对特征的所有值枚举，但是对于数值型变量，可能取值的数量极其多，可以想象如果真的通过枚举速度会非常慢。

一个自然的想法是通过离散化进行分箱，对分箱后产生的分位点进行判断即可。但是对于如何分桶，以往的分位法通过排序或启发式算法，没有理论保证，但是由于XGBoost通过二次展开进行改进，使得分箱方法有了理论支撑。——

使用

（二阶梯度）加权进行分箱

样本点具体的特征值对于我们分箱是没有用的（在哪分裂主要是看分完后的节点纯不纯），那怎么去衡量每个样本对于损失函数减少的影响呢？

作者提出使用二阶梯度衡量样本点对损失函数减小的贡献程度，并且不是使用等频/等宽分箱，而是采用‘

等贡献度分箱

’。（没有这个名词，是我为了描述瞎编的...）

分箱思想里的等频/等宽分箱是出现在数据预处理中，希望的是每个桶的样本个数相同，或值分布相同。但是这里不是真的要做分箱呀！是为了更有效地分枝，也就是希望分完之后左右子树能以大致相同的程度一起降低loss。

为什么使用二阶导作为权重？

我们将损失函数进行变形：

关于具体怎么分箱，作者提出了rank function

：

寻找分裂点

就可以通过以下过程进行描述：

这里相当于找到

个备选点，使得备选点与备选点之间的

值之间的差距小于

。这样处理之后，分枝的依据就可转化为选择

值最大的那个节点。

（题外话：只使用一阶导的时候相当于只是根据残差方向进行学习，引入二阶导之后相当于通过‘残差变化方向’对样本点进行加权。让变化快的人有机会跑的更远，变化慢的人就留下来不要拖累团队。）

分完箱，我们已经做到了‘weighted quantile’，但问题是作者提出来的算法是‘

Weighted Quantile Sketch

’呀！sketch去哪了？

通过分箱离散后的数据，可以用

直方图

来观察其分布。我们可以‘sketch’出该特征的直方图，不需要导入全部数据即可完成近似。（这部分还没有仔细研究，目前的宏观image大概如下图）

直方图近似算法在遍历完所有特征之后，最后汇总所有特征的直方图来寻找分裂点。这个算法有两种实现，一种是

globa variant

，在建立这棵树之前先提出所有候选分裂，所以只建立一次直方图；另一种是

local variant

，在分完枝之后都会重新绘制一次直方图。

全局方法虽然只画一次图比较方便，但是因为在每次分裂之后并没有改善，需要较多的候选点才能保证和局部方法一样准确。

处理稀疏数据

关于XGBoost端到端系统的一个重要体现，是它自带对稀疏数据的学习。作者提出缺省方向（default direction），让算法学习当出现缺失数据的时候应该如何进行决策，省去我们提前对缺失数据进行处理。

算法实现过程很简单：

• 让该特征所有缺失值都到左子树，对结果进行打分
• 让该特征所有缺失值都到右子树，对结果进行打分

哪个最终得分高，就让缺失数据自己去哪边~复杂度仅依赖于缺失数据量，还是很划算的。

在这里想到的一个改进点在于对缺省方向加一些随机，让其适当‘分错’几个缺失值，毕竟本来就没有具体数值，这里只是模拟一个大分类方向。但是这样改进只有在缺失值较多才会有效果，缺失值少的时候只是徒增复杂度而已orz

使用（持续更新）

推荐一个下载方法

简单到一步安装 xgboost (Windows环境)​blog.csdn.net

具体使用参考官方文档

https://xgboost.readthedocs.io/en/latest/index.html#​xgboost.readthedocs.io

--------------------------TBC--------------------------

• 第 1 次编辑（2020.5.27）
• 第 2 次编辑（2020.5.31）