前文《集成学习：基于梯度的Boosting算法——GBDT》介绍了GBDT，本文将介绍一种GBDT的改进算法——XGBoost算法。XGBoost最初是由华盛顿大学计算机系博士生陈天奇开发，后来成为了Kaggle竞赛传奇——在2015年的時候29个Kaggle冠军队伍中有17队在他们的解决方案中使用了XGboost。

XGBoost算法

X代表的就是eXtreme（极致），XGBoost能够更快的、更高效率的训练模型。与GBDT方法一样，XGBoost的提升模型也是采用残差，不同的是GBDT的损失函数是最小平方误差，XGBoost的损失函数根据树模型的复杂度加入了一项正则化项：

XGBoost损失函数

XGBoost损失函数由最小平方误差和正则化项之和组成，上式中后面的加和项就是正则化项。正则化项的作用来控制树的复杂度，从而避免模型过拟合。式子中的T为叶子节点数。

那么正则化项是如何定义树的复杂度呢？

首先把树拆分成结构部分q(x)和叶子节点输出值w。树的结构q(x)实际上是确定输入值最终会落到哪个叶子节点上，而w将会给出相应的输出值。

树的结构和叶子输出值

在上图中，输入样本是一个人，经过树结构会映射到某一个叶子节点上，叶子1，叶子2或者叶子3。q(x)就是把输入映射到有限的集合（叶子）上的函数，集合的元素数量就是叶子数T。

对应每一个映射结果（叶子），都有一个输出：叶子1的输出是w1，叶子2的输出是w2, ...。基于以上概念，我们得到了树的复杂度定义：

树的复杂度

根据这个定义，叶子数量越多越复杂，另外叶子输出分数的L2范式越大越复杂。每次训练一个新的树分类器，都要综合评估残差（最小平方误差）和树的复杂度。这样就避免追求最小误差导致树模型过拟合。

有了树的复杂度定义，接下来再回到XGBoost的损失函数上来。在GBDT中我们通过求损失函数的负梯度（一阶导数），利用负梯度替代残差来拟合树模型。在XGBoost中直接用泰勒展开式将损失函数展开成二项式函数，得到了一种新形式的目标函数。

去掉常量后，目标优化函数可以转换成：

我们要训练出来新的树，主要是得到叶节点的输出分数。为得到目标函数的极小值，对求导并令导数为0，可得：

目标函数极小值及对应的叶子输出值

以上目标函数Obj可以认为是一个类似基尼指数的对树结构进行打分的函数。

对于求得Obj分数最小的树结构，我们可以枚举所有的可能性，然后对比分数来获得最优的树结构。然而这种方法计算消耗太大，更常用的是贪心法：从最开始的根节点，每次尝试对已经存在的叶节点进行分割，然后获得分割后的增益。

叶节点分割增益

如果分割增益Gain小于0，则此叶节点不做分割。先将所有样本按照增益从小到大排序，然后进行遍历，查看每个节点是否需要分割，具体示例如下：

现在想按照年龄将单节点树进行分叉，我们需要知道：

　　1）按照年龄分是否有效，也就是是否减少了obj的值

　　2）如果可分，那么以哪个年龄值来分。

　　此时我们就是先将年龄特征从小到大排好序，然后再从左到右遍历分割。这样的分割方式，我们就只要对样本扫描一遍，就可以分割出来。

XGBoost和GBDT的区别

这里总结下XGBoost相比GBDT的主要改进点：

　 1）XGBoost将树模型的复杂度加入到正则项中，来避免过拟合，因此泛化性能会优于GBDT。

　 2）XGBoost的损失函数是用泰勒展开式展开的，同时用到了一阶导和二阶导，而GBDT只用了一阶导数。理论上来说XGBoost可以加快优化速度。

　3）GBDT只支持CART作为基分类器，XGBoost还支持线性分类器，在使用线性分类器的时候可以使用L1，L2正则化。

　4）寻找最佳分割点时，XGBoost实现了一种近似贪心算法，用来加速和减小内存消耗。

　5）XGBoost支持并行处理，XGBoost的并行不是在模型上的并行，而是在特征上的并行，将特征列排序后以block的形式存储在内存中，也使得并行化成为了可能。在进行节点分裂时，计算每个特征的增益，各个特征的增益计算可以开多线程进行。

总结来说，XGBoost能利用CPU的多线程，并且加了剪枝，控制了模型复杂度。