• 集成学习之Xgboost(21)

3) 基于最大score对应的划分特征和特征值分裂子树。

4) 如果最大score为0，则当前决策树建立完毕，计算所有叶子区域的wtj$w_{tj}$, 得到弱学习器ht(x)$h_t(x)$，更新强学习器ft(x)$f_t(x)$,进入下一轮弱学习器迭代.如果最大score不是0，则转到第2)步继续尝试分裂决策树。

XGBoost算法运行效率的优化

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

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

具体的过程如下图所示：

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

XGBoosting涉及的算法工程优化策略：

1. 对内存的优化（列分块）；

2. 对CPU Cache的优化：a) 提前取数(Prefetching)，b) 合理设置分块大小；

3. 对IO的优化：a) Block压缩优化，b) Block 分片优化。

XGBoost算法健壮性的优化

XGBoost在算法健壮性的优化方面，除了上面讲到的正则化项提高算法的泛化能力外，XGBoost还对特征的缺失值做了处理。XGBoost没有假设缺失值一定进入左子树还是右子树，则是尝试通过枚举所有缺失值在当前节点是进入左子树，还是进入右子树更优来决定一个处理缺失值默认的方向，这样处理起来更加的灵活和合理。

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

如果是所有的缺失值走右子树，使用上面a),b)和c)即可。如果是所有的样本走左子树，则上面

a)步要变成：

GR=0,HR=0$G_R=0,H_R=0$

b)步要更新为：

GR=GR+gti,GL=G−GR$G_R=G_R+g_{ti},G_L=G-G_R$

HR=HR+hti,HL=H−HR$H_R=H_R+h_{ti},H_L=H-H_R$

XGBoosting的优缺点总结

在分析XGBooting优缺点的时候，通过比较该算法与GBDT的差异，即可有较清楚的描述，具体表现在如下方面。

1）基分类器的差异

• GBDT算法只能利用CART树作为基学习器，满足分类应用；
• XGBoost算法除了以CART树中的回归树作为基分类器之外还支持线性的基学习器，因此其一方面可以解决带L1与L2正则化项的逻辑回归分类问题，也可以解决线性回问题。

2）节点分类方法的差异

• GBDT算法主要是利用Gini impurity针对特征进行节点划分；
• XGBoost经过公式推导，提出的weighted quantile sketch划分方法，依据影响Loss的程度来确定连续特征的切分值。

3）模型损失函数的差异

• 传统GBDT在优化时只用到一阶导数信息；
• xgboost则对代价函数进行了二阶泰勒展开，二阶导数有利于梯度下降的更快更准。

4）模型防止过拟合的差异

• GBDT算法无正则项，可能出现过拟合；
• Xgboost在代价函数里加入了正则项，用于控制模型的复杂度，降低了过拟合的可能性。

5）模型实现上的差异

决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点）。xgboost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。其能够实现在特征粒度的并行。