XGBoost（eXtreme Gradient Boosting）是一种高效、灵活且广泛应用的机器学习算法，属于梯度提升决策树（Gradient Boosting Decision Tree, GBDT） 的优化实现。它在分类、回归、排序等结构化/表格数据的预测任务中表现尤为出色。

XGBoost Documentation：https://xgboost.readthedocs.io/en/release_3.0.0/

首先要明确一点，xgboost 是基于提升树的。

什么是提升树，简单说，就是一个模型表现不好，我继续按照原来模型表现不好的那部分训练第二个模型，依次类推。

来几个形象的比喻就是：

做题的时候，第一个人做一遍得到一个分数，第二个人去做第一个人做错的题目，第三个人去做第二个人做错的题目，以此类推，不停的去拟合从而可以使整张试卷分数可以得到100分（极端情况）。

把这个比喻替换到模型来说，就是真实值为100，第一个模型预测为90，差10分，第二个模型以10为目标值去训练并预测，预测值为7，差三分，第三个模型以3为目标值去训练并预测，以此类推。

一、从GBDT到XGBoost

作为GBDT的高效实现，XGBoost是一个上限特别高的算法，因此在算法竞赛中比较受欢迎。简单来说，对比原算法GBDT，XGBoost主要从下面三个方面做了优化：

• 一是算法本身的优化：在算法的弱学习器模型选择上，对比GBDT只支持决策树，还可以直接很多其他的弱学习器。在算法的损失函数上，除了本身的损失，还加上了正则化部分。在算法的优化方式上，GBDT的损失函数只对误差部分做负梯度（一阶泰勒）展开，而XGBoost损失函数对误差部分做二阶泰勒展开，更加准确。算法本身的优化是我们后面讨论的重点。

• 二是算法运行效率的优化：对每个弱学习器，比如决策树建立的过程做并行选择，找到合适的子树分裂特征和特征值。在并行选择之前，先对所有的特征的值进行排序分组，方便前面说的并行选择。对分组的特征，选择合适的分组大小，使用CPU缓存进行读取加速。将各个分组保存到多个硬盘以提高IO速度。

• 三是算法健壮性的优化：对于缺失值的特征，通过枚举所有缺失值在当前节点是进入左子树还是右子树来决定缺失值的处理方式。算法本身加入了L1和L2正则化项，可以防止过拟合，泛化能力更强。

在上面三方面的优化中，第一部分算法本身的优化是重点也是难点。现在我们就来看看算法本身的优化内容。

二、XGBoost原理

2.1 XGBoost损失函数

2.1.1 GBDT损失函数

我们先回顾下GBDT的回归算法迭代的流程，对于GBDT的第t颗决策树，主要是走下面4步：

上面第一步是得到负梯度，或者是泰勒展开式的一阶导数。第二步是第一个优化求解，即基于残差拟合一颗CART回归树，得到J个叶子节点区域。第三步是第二个优化求解，在第二步优化求解的结果上，对每个节点区域再做一次线性搜索，得到每个叶子节点区域的最优取值。最终得到当前轮的强学习器。

从上面可以看出，我们要求解这个问题，需要求解当前决策树最优的所有J个叶子节点区域和每个叶子节点区域的最优解Ctj。GBDT采样的方法是分两步走，先求出最优的所有J个叶子节点区域，再求出每个叶子节点区域的最优解。

对于XGBoost，它期望把第2步和第3步合并在一起做，即一次求解出决策树最优的所有J个叶子节点区域和每个叶子节点区域的最优解Ctj。在讨论如何求解前，我们先看看XGBoost的损失函数的形式。

2.1.2 GBDT损失函数

最终我们要极小化上面这个损失函数，得到第t个决策树最优的所有J个叶子节点区域和每个叶子节点区域的最优解Wtj .

2.1.3 GBDT损失函数二阶泰勒展开式

XGBoost没有和GBDT一样去拟合泰勒展开式的一阶导数，而是期望直接基于损失函数的二阶泰勒展开式来求解。现在我们来看看这个损失函数的二阶泰勒展开式：

为了方便，我们把第i个样本在第t个弱学习器的一阶和二阶导数分别记为:

则我们的损失函数现在可以表达为：

　损失函数里面L(yi,ft−1(xi))是常数，对最小化无影响，可以去掉，同时由于每个决策树的第j个叶子节点的取值最终会是同一个值Wtj ,因此我们的损失函数可以继续化简。

我们把每个叶子节点区域样本的一阶和二阶导数的和单独表示如下：

最终损失函数的形式可以表示为：

2.2 XGBoost损失函数的优化求解

关于如何一次求解出决策树最优的所有J个叶子节点区域和每个叶子节点区域的最优解Wtj，我们可以把它拆分成2个问题：

• 1. 如果我们已经求出了第t个决策树的J个最优的叶子节点区域，如何求出每个叶子节点区域的最优解Wtj。
• 2. 对当前决策树做子树分裂决策时，应该如何选择哪个特征和特征值进行分裂，使最终我们的损失函数Lt最小。

整理下上式后，我们期望最大化的是：

也就是说，我们的决策树分裂标准不再使用CART回归树的均方误差，而是上式了。

具体如何分裂呢？举个简单的年龄特征的例子如下，假设我们选择年龄这个 特征的值a作为决策树的分裂标准，则可以得到左子树2个人，右子树三个人，这样可以分别计算出左右子树的一阶和二阶导数和，进而求出最终的上式的值。

然后我们使用其他的不是值a的划分标准，可以得到其他组合的一阶和二阶导数和，进而求出上式的值。最终我们找出可以使上式最大的组合，以它对应的特征值来分裂子树。

至此，我们解决了XGBoost的2个优化子问题的求解方法。

三、 XGBoost算法主流程

这里我们总结下XGBoost的算法主流程，基于决策树弱分类器。不涉及运行效率的优化和健壮性优化的内容。

四、 XGBoost算法运行效率的优化

上边我们重点讨论了XGBoost算法本身的优化，在这里我们再来看看XGBoost算法运行效率的优化。

大家知道,Boosting算法的弱学习器是没法并行迭代的，但是单个弱学习器里面最耗时的是决策树的分裂过程，XGBoost针对这个分裂做了比较大的并行优化。对于不同的特征的特征划分点，XGBoost分别在不同的线程中并行选择分裂的最大增益。

同时，对训练的每个特征排序并且以块的的结构存储在内存中，方便后面迭代重复使用，减少计算量。计算量的减少参见上面第4节的算法流程，首先默认所有的样本都在右子树，然后从小到大迭代，依次放入左子树，并寻找最优的分裂点。这样做可以减少很多不必要的比较。

具体的过程如下图所示：

此外，通过设置合理的分块的大小，充分利用了CPU缓存进行读取加速（cache-aware access）。使得数据读取的速度更快。另外，通过将分块进行压缩（block compressoin）并存储到硬盘上，并且通过将分块分区到多个硬盘上实现了更大的IO。

五、 XGBoost算法健壮性的优化

最后我们再来看看XGBoost在算法健壮性的优化，除了上面讲到的正则化项提高算法的泛化能力外，XGBoost还对特征的缺失值做了处理。

XGBoost没有假设缺失值一定进入左子树还是右子树，则是尝试通过枚举所有缺失值在当前节点是进入左子树，还是进入右子树更优来决定一个处理缺失值默认的方向，这样处理起来更加的灵活和合理。

也就是说，上面第三节的算法的步骤a),b.1)和b.2)会执行2次，第一次假设特征k所有有缺失值的样本都走左子树，第二次假设特征k所有缺失值的样本都走右子树。然后每次都是针对没有缺失值的特征k的样本走上述流程，而不是所有的的样本。

如果是所有的缺失值走右子树，使用上面第三节的a),b.1)和b.2)即可。如果是所有的样本走左子树，则上面第三节的a)步要变成：
　　　　
　　b.1)步要更新为：