• python入门教程之集成学习之Xgboost(19)

 

其中G2LHL+λ$\frac{G_L^2}{H_L+\lambda }$表示左子树分数，G2RHR+λ$\frac{G_R^2}{H_R+\lambda }$表示右子树分数，(GL+GR)2HL+HR+λ$\frac{(G_L+G_R{)}^2}{H_L+H_R+\lambda }$表示不可分割我们可以拿到的分数，γ$\gamma$表示加入新叶子节点引入的复杂度代价。

也就是说，Xgboost里的决策树分裂标准不再使用CART回归树的均方误差，而是上式了。这样就可以在建树的过程中动态的选择是否要添加一个结点。  联想决策树中信息增益，这里的原理类似。这一步实质上是为了寻找分裂结点的候选集。每次做左右子树分裂时，可以最大程度的减少损失函数的损失就最好了。

2) 寻找分裂结点标准

对于每次扩展，我们要枚举所有的分割方案，如何高效地枚举所有的分割呢？比如设置一个值a，然后枚举所有x < a，a  < x这样的条件，对于某个特定的分割a我们要计算a左边和右边的导数和。

具体如何分裂呢？举个简单的年龄特征的例子，假设我们选择年龄这个特征的值a作为决策树的分裂标准，x代表某个特征比如年龄age，把age从小到大排序：假定从左至右依次增大，则比a小的放在左边，比a大的放在右边，计算a左边和右边的导数和。

比如总共五个人，按年龄排好序后，一开始我们总共有如下4种划分方法：

• 把第一个人和后面四个人划分开
• 把前两个人和后面三个人划分开
• 把前三个人和后面两个人划分开
• 把前面四个人和后面一个人划分开

接下来，把上面4种划分方法全都各自计算一下Gain，看哪种划分方法得到的Gain值最大则选取哪种划分方法，经过计算，发现把第2种划分方法“前面两个人和后面三个人划分开”得到的Gain值最大，这样可以分别计算出左右子树的一阶和二阶导数和，进而求出最终的上式的值。

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

可以发现对于所有的a，我们只要做一遍从左到右的扫描就可以枚举出所有分割的梯度和GL$G_L$和 GR$G_R$。然后用上面的公式计算每个分割方案的分数就可以了。

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

10. 寻找分裂结点

确定好损失函数以及最优解之后，接下来需要确定树的结构，即如何选出最优分裂节点。可以参考决策树算法：ID3选择信息增益为切分准则，C4.5选择信息增益率为切分准则。Xgboost基本思想和决策树一致，贪心法枚举所有节点，计算各个节点分裂前后的信息增益，选出信息增益最大的。

很显然，一棵树的生成是由一个节点一分为二，然后不断分裂最终形成为整棵树。那么树怎么分裂的就成为了接下来我们要探讨的关键。对于一个叶子节点如何进行分裂，根据Xgboost的Gain公式，Xgboost作者在其原始论文中给出了两种分裂节点的方法（切分算法）。

1) 枚举所有不同树结构的贪心法（精确贪心算法）：

在所有特征上暴力枚举所有可能的切分点。

贪心法，从树深度0开始，每一节点都遍历所有的特征，比如年龄、性别等等，然后对于某个特征，先按照该特征里的值进行排序，然后线性扫描该特征进而确定最好的分割点，最后对所有特征进行分割后，我们选择所谓的增益Gain最高的那个特征。

2) 近似算法：

主要针对数据太大，不能直接进行计算。基本思想是通过特征的统计分布（分位数），按照百分比确定一组候选分裂点，（对于连续属性特征，根据候选切分点进行离散化）然后通过遍历所有的候选分裂点来找到最佳分裂点。近似算法有两种版本：global variant和local variant。global variant在树初始化时就确定了候选切分点；local variant是在每次节点分裂后重新选出候选点。

两种策略：全局策略和局部策略。在全局策略中，对每一个特征确定一个全局的候选分裂点集合，就不再改变；而在局部策略中，每一次分裂 都要重选一次分裂点。前者需要较大的分裂集合，后者可以小一点。对比补充候选集策略与分裂点数目对模型的影响。 全局策略需要更细的分裂点才能和局部策略差不多。

 

XGBoosting算法流程总结

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

输入是训练集样本I={(x,y1),(x2,y2),...(xm,ym)}$I=\{(x_{,}{y}_1),(x_2,y_2),...(x_m,y_m)\}$， 最大迭代次数T$T$, 损失函数L$L$， 正则化系数λ,γ$\lambda ,\gamma$；

输出是强学习器：f(x)$f(x)$。

对迭代轮数t=