XGBoosttype
status
date
slug
summary
tags
category
icon
password
Property
原理
从GBDT到XGBoost
作为GBDT的高效实现，XGBoost是一个上限特别高的算法，因此在算法竞赛中比较受欢迎。简单来说，对比原算法GBDT，XGBoost主要从下面三个方面做了优化：
- 一是算法本身的优化：在算法的弱学习器模型选择上，对比GBDT只支持决策树，还可以直接很多其他的弱学习器。在算法的损失函数上，除了本身的损失，还加上了正则化部分。在算法的优化方式上，GBDT的损失函数只对误差部分做负梯度（一阶泰勒）展开，而XGBoost损失函数对误差部分做二阶泰勒展开，更加准确。算法本身的优化是重点也是难点
- 二是算法运行效率的优化：对每个弱学习器，比如决策树建立的过程做并行选择，找到合适的子树分裂特征和特征值。在并行选择之前，先对所有的特征的值进行排序分组，方便前面说的并行选择。对分组的特征，选择合适的分组大小，使用CPU缓存进行读取加速。将各个分组保存到多个硬盘以提高IO速度
- 三是算法健壮性的优化：对于缺失值的特征，通过枚举所有缺失值在当前节点是进入左子树还是右子树来决定缺失值的处理方式。算法本身加入了L1和L2正则化项，可以防止过拟合，泛化能力更强
XGBoost损失函数
在看XGBoost本身的优化内容前，先回顾下GBDT的回归算法迭代的流程，对于GBDT的第颗决策树，主要是走下面4步：
- 对样本 ，计算负梯度
- 利用 , 拟合一颗CART回归树，得到第颗回归树，其对应的叶子节点区域为 。其中为回归树的叶子节点的个数
- 对叶子区域 ，计算最佳拟合值
- 更新强学习器
上面第一步是得到负梯度，或者是泰勒展开式的一阶导数。第二步是第一个优化求解，即基于残差拟合一颗CART回归树，得到个叶子节点区域。第三步是第二个优化求解，在第二步优化求解的结果上，对每个节点区域再做一次线性搜索，得到每个叶子节点区域的最优取值。最终得到当前轮的强学习器。
从上面可以看出，要求解这个问题，需要求解当前决策树最优的所有个叶子节点区域和每个叶子节点区域的最优解。
GBDT采样的方法是分两步走，先求出最优的所有个叶子节点区域，再求出每个叶子节点区域的最优解。
对于XGBoost，它期望把第2步和第3步合并在一起做，即一次求解出决策树最优的所有 个叶子节点区域和每个叶子节点区域的最优解。在讨论如何求解前，我们先看看XGBoost的损失函数的形式。
在GBDT损失函数 的基础上加入正则化项如下：
这里的 是叶子节点的个数，而 是第 个叶子节点的最优值。这里的 和我们GBDT里使用的 是一个意思，只是XGBoost的论文里用的是 表示叶子区域的值，因此这里和论文保持一致。
最终XGBoost的损失函数可以表达为：
最终我们要极小化上面这个损失函数，得到第 个决策树最优的所有个叶子节点区域和每个叶子节点区域的最优解 。XGBoost没有和GBDT一样去拟合泰勒展开式的一阶导数，而是期望直接基于损失函数的二阶泰勒展开式来求解。现在我们来看看这个损失函数的二阶泰勒展开式：
为了方便，我们把第 个样本在第 个弱学习器的一阶和二阶导数分别记为
则我们的损失函数现在可以表达为：
损失函数里面 是常数，对最小化无影响，可以去掉，同时由于每个决策树的第j个叶子节点的取值最终会是同一个值 ,因此我们的损失函数可以继续化简：
我们把每个叶子节点区域样本的一阶和二阶导数的和单独表示如下：
最终损失函数的形式可以表示为：
现在我们得到了最终的损失函数，那么回到前面讲到的问题，我们如何一次求解出决策树最优的所有J个叶子节点区域和每个叶子节点区域的最优解 呢？
XGBoost损失函数的优化求解
关于如何一次求解出决策树最优的所有J个叶子节点区域和每个叶子节点区域的最优解 ，我们可以把它拆分成2个问题：
1) 如果我们已经求出了第t个决策树的 个最优的叶子节点区域，如何求出每个叶子节点区域的最优解 ？
2) 对当前决策树做子树分裂决策时，应该如何选择哪个特征和特征值进行分裂，使最终我们的损失函数 最小？
对于第一个问题，其实是比较简单的，我们直接基于损失函数对 求导并令导数为0即可。这样我们得到叶子节点区域的最优解 表达式为：
这个叶子节点的表达式不是XGBoost首创，实际上在GBDT的分类算法里，已经在使用了。大家在梯度提升树(GBDT)中叶子节点区域值的近似解表达式为：
它其实就是使用了上式来计算最终的 。注意到二元分类的损失函数是：
其每个样本的一阶导数为：
其每个样本的二阶导数为：
由于没有正则化项，则 ，即可得到GBDT二分类叶子节点区域的近似值。
现在我们回到XGBoost，我们已经解决了第一个问题。现在来看XGBoost优化拆分出的第二个问题：如何选择哪个特征和特征值进行分裂，使最终我们的损失函数 最小？
在GBDT里面，我们是直接拟合的CART回归树，所以树节点分裂使用的是均方误差。XGBoost这里不使用均方误差，而是使用贪心法，即每次分裂都期望最小化我们的损失函数的误差。
注意到在我们 取最优解的时候，原损失函数对应的表达式为 ：
如果我们每次做左右子树分裂时，可以最大程度的减少损失函数的损失就最好了。也就是说，假设当前节点左右子树的一阶二阶导数和为 , 则我们期望最大化下式：
整理下上式后，我们期望最大化的是：
也就是说，我们的决策树分裂标准不再使用CART回归树的均方误差，而是上式了。
具体如何分裂呢？举个简单的年龄特征的例子如下，假设我们选择年龄这个 特征的值a作为决策树的分裂标准，则可以得到左子树2个人，右子树三个人，这样可以分别计算出左右子树的一阶和二阶导数和，进而求出最终的上式的值。
然后我们使用其他的不是值a的划分标准，可以得到其他组合的一阶和二阶导数和，进而求出上式的值。最终我们找出可以使上式最大的组合，以它对应的特征值来分裂子树。
至此，我们解决了XGBoost的2个优化子问题的求解方法。
XGBoost算法主流程
这里我们总结下XGBoost的算法主流程，基于决策树弱分类器。不涉及运行效率的优化和健壮性优化的内容。
输入是训练集样本 ， 最大迭代次数，损失函数， 正则化系数
输出是强学习器
对迭代轮数 有：
1）计算第个样本在当前轮损失函数L基于的一阶导数，二阶导数，计算所有样本的一阶导数和， 二阶导数和
2）基于当前节点尝试分裂决策树，默认分数score=0，G和H为当前需要分裂的节点的一阶二阶导数之和。
对特征序号 :
a)
b.1) 将样本按特征 从小到大排列，依次取出第 个样本，依次计算当前样本放入左子树后，左右子树一阶和二阶导数和：
b.2) 尝试更新最大的分数：
3）基于最大score对应的划分特征和特征值分裂子树。
4）如果最大score为0，则当前决策树建立完毕，计算所有叶子区域的 , 得到弱学习器 ，更新强学习器 ，进入下一轮弱学习器迭代.如果最大score不是0，则转到第2)步继续尝试分裂决策树。
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)步要更新为：
XGBoost小结
不考虑深度学习，则XGBoost是算法竞赛中最热门的算法，它将GBDT的优化走向了一个极致。当然，后续微软又出了LightGBM，在内存占用和运行速度上又做了不少优化，但是从算法本身来说，优化点则并没有XGBoost多。
何时使用XGBoost，何时使用LightGBM呢？建议是优先选择XGBoost，毕竟调优经验比较多一些，可以参考的资料也多一些。如果使用XGBoost遇到的内存占用或者运行速度问题，那么尝试LightGBM是个不错的选择。
代码
XGBoost的类库参数主要包括boosting框架参数，弱学习器参数以及其他参数。
XGBoost有2种Python接口风格。一种是XGBoost自带的原生Python API接口，另一种是sklearn风格的API接口，两者的实现是基本一样的，仅仅有细微的API使用的不同，主要体现在参数命名上，以及数据集的初始化上面
XGBoost框架参数
对于XGBoost的框架参数，最重要的是3个参数: booster，n_estimators和objectve
- booster决定了XGBoost使用的弱学习器类型，可以是默认的gbtree, 也就是CART决策树，还可以是线性弱学习器gblinear以及DART。一般来说，使用gbtree就可以了，不需要调参。
- n_estimators是非常重要的要调的参数，关系到XGBoost模型的复杂度，因为它代表了我们决策树弱学习器的个数。这个参数对应sklearn GBDT的n_estimators。n_estimators太小，容易欠拟合，n_estimators太大，模型会过于复杂，一般需要调参选择一个适中的数值。
- objective代表了要解决的问题是分类还是回归，或其他问题，以及对应的损失函数。具体可以取的值很多，一般只关心在分类和回归的时候使用的参数。在回归问题objective一般使用reg:squarederror ，即MSE均方误差。二分类问题一般使用binary:logistic，多分类问题一般使用multi:softmax。
XGBoost 弱学习器参数
这里只讨论使用gbtree默认弱学习器的参数，要调参的参数主要是决策树的相关参数如下：
- max_depth：控制树结构的深度，数据少或者特征少的时候可以不管这个值。如果模型样本量多，特征也多的情况下，需要限制这个最大深度，具体的取值一般要网格搜索调参。这个参数对应sklearn GBDT的max_depth。
- min_child_weight：最小的子节点权重阈值，如果某个树节点的权重小于这个阈值，则不会再分裂子树，即这个树节点就是叶子节点。这里树节点的权重使用的是该节点所有样本的二阶导数的和，即
:
这个值需要网格搜索寻找最优值，在sklearn GBDT里面，没有完全对应的参数，不过min_samples_split从另一个角度起到了阈值限制。
- gamma：XGBoost的决策树分裂所带来的损失减小阈值。也就是在尝试树结构分裂时，会尝试最大数：
这个最大化后的值需要大于我们的gamma，才能继续分裂子树。这个值也需要网格搜索寻找最优值。
- subsample：子采样参数，这个也是不放回抽样，和sklearn GBDT的subsample作用一样。选择小于1的比例可以减少方差，即防止过拟合，但是会增加样本拟合的偏差，因此取值不能太低。初期可以取值1，如果发现过拟合后可以网格搜索调参找一个相对小一些的值。
- colsample_bytree/colsample_bylevel/colsample_bynode：这三个参数都是用于特征采样的，默认都是不做采样，即使用所有的特征建立决策树。colsample_bytree控制整棵树的特征采样比例，colsample_bylevel控制某一层的特征采样比例，而colsample_bynode控制某一个树节点的特征采样比例。比如一共64个特征，则假设colsample_bytree，colsample_bylevel和colsample_bynode都是0.5，则某一个树节点分裂时会随机采样8个特征来尝试分裂子树。
- reg_alpha/reg_lambda: 这2个是XGBoost的正则化参数。reg_alpha是L1正则化系数，reg_lambda是L2正则化系数，XGBoost的正则化损失项部分：
上面这些参数都是需要调参的，不过一般先调max_depth，min_child_weight和gamma。如果发现有过拟合的情况下，再尝试调后面几个参数。
XGBoost 其他参数
XGBoost还有一些其他的参数需要注意，主要是learning_rate。
learning_rate控制每个弱学习器的权重缩减系数，和sklearn GBDT的learning_rate类似，较小的learning_rate意味着需要更多的弱学习器的迭代次数。通常用步长和迭代最大次数一起来决定算法的拟合效果。所以这两个参数n_estimators和learning_rate要一起调参才有效果。当然也可以先固定一个learning_rate ，然后调完n_estimators，再调完其他所有参数后，最后再来调learning_rate和n_estimators。
此外，n_jobs控制算法的并发线程数；scale_pos_weight用于类别不平衡的时候，负例和正例的比例，类似于sklearn中的class_weight；importance_type则可以查询各个特征的重要性程度，可以选择“gain”, “weight”, “cover”, “total_gain” 或者 “total_cover”；最后可以通过调用booster的get_score方法获取对应的特征权重。“weight”通过特征被选中作为分裂特征的计数来计算重要性，“gain”和“total_gain”则通过分别计算特征被选中做分裂特征时带来的平均增益和总增益来计算重要性。“cover”和 “total_cover”通过计算特征被选中做分裂时的平均样本覆盖度和总体样本覆盖度来来计算重要性。
使用原生Python API接口
原生XGBoost需要先把数据集按输入特征部分，输出部分分开，然后放到一个DMatrix数据结构里面，这个DMatrix不需要关心里面的细节，使用训练集X和y初始化即可。
使用sklearn风格接口
对于sklearn风格的接口，主要有2个类可以使用，一个是分类用的XGBClassifier，另一个是回归用的XGBRegressor。在使用这2个类的使用，对于算法的参数输入也有2种方式，第一种就是仍然使用和原始API一样的参数命名集合，另一种是使用sklearn风格的参数命名。
这里先看看如何使用和原始API一样的参数命名集合
其实就是使用XGBClassifier/XGBRegressor的**kwargs参数，把上面原生参数的params集合放进去：
使用sklearn风格的接口，并使用sklearn风格的参数，是推荐的方式，主要是这样做和GBDT之类的sklearn库使用起来没有什么两样了，也可以使用sklearn的网格搜索