一.前言

XGB的推导过程见：https://blog.csdn.net/weixin_44467105/article/details/111810895

基于上述推导，可以得到cart回归树的分裂标准。但是在回归树分裂的过程中，如何利用分裂标准找到最优切分点实际上在论文中有两个方法：

1. 贪心算法
2. 近似算法

二.贪心算法

这里的贪心算法实际就是在之前决策树中利用到分裂方法。基于某种标准（GINI系数/均方误差/信息增益比等），每次依次遍历所有特征和所有特征的取值，通过线性扫描来找到最优分割点。

其流程如下：
1.从根节点开始，枚举每个叶子节点的可用特征。
2.将每个特征的取值排序，然后线性扫描来找到该特征的最佳分裂点及其对应的增益。
3.选择增益最大的特征及其分裂点来分裂叶子节点。
4.重复1~3直到达到预设的停止条件。

三.近似算法

贪婪算法一般来说能得到较优解，但是需要将所有数据同时读入内存，如果数据量过大时，这就不适用了。所以针对该问题提出了近似算法。

贪婪算法需要线性扫描特征的每个分裂点，但是近似算法只考察分位点，这样可以有效的减少计算量。

近似算法会将连续的特征映射到对应的桶中，然后遍历桶之间的间隙来找最佳的分裂分位点。而在划分桶的时候会有两种方法：

1. Global：在每棵树分裂前就找好候选的特征分位点，每次分裂时就在这群候选的分位点里找。
2. Local：每次分裂前重新找候选的分位点。

Local策略需要更多的计算步骤，因为再每次分裂前都要重新找分位点。而Global则需要更多的候选分位点。

从上图不难看出，在Global策略划分的候选分位点较多时（eps较小），其效果和loca候选分位点较少时(eps较大)差不多。

对于划分方法，Xgboost论文里提出了近似分位数法。

分位点：
输入：4，5，1，2
排序：1，2，4，5
排名：1，2，3，4
0.5分位点的计算：0.5*4=2，所以对应排名为2的值，也就是value=2。

加权分位点:
前面计算分位点时是假设每个值的权值都为1，但在XGB里面权值是不同的（以样本点的二阶导作为权值，具体推导可以参考XGB原文）。
输入：4，5，1，2
排序：1，2，4，5
权重 0.1 0.8 0.7 0.5
排名：0.1 0.9 1.6 2.1
所以这里0.5分位点为：0.5*2.1=1.05为order=1.05(0.9),value=2.

在XGB中，权重就是样本点的二阶导。然后求出分位点来做分箱。以减少计算量，和内存消耗。

四.稀疏感知

在XGB里面，考虑到数据缺失的问题（在论文中表述为数据稀疏），提出了稀疏感知算法来解决。这也使得XGB的基模型对缺失值处理的方法和传统决策树并不相同。XGBoost在构建树的节点过程中只考虑非缺失值的数据遍历，而为每个节点增加了一个缺省方向，当样本相应的特征值缺失时，可以被归类到缺省方向上，最优的缺省方向可以从数据中学到。至于如何学到缺省值的分支，其实很简单，分别枚举特征缺省的样本归为左右分支后的增益，选择增益最大的枚举项即为最优缺省方向。

算法的流程如下，对每个特征，依次遍历缺失值至左右子树，计算最大的收益值。

五.XGB的并行化

XGB的并行是在特征的粒度上并行的

决策树学习最耗时的部分是对特征值的排序（因为要确定最佳分割点）

（1）XGB在训练之前，对所有数据根据特征值【列】进行排序，然后保存为block结构，后面迭代中重复使用这个结构，大大减小了计算量，这个block使并行成为了可能

（2）在进行节点分裂时，需要计算每个特征的增益，最终选增益大的去分裂，各个特征增益的计算就可以开多线程进行。

参考
https://blog.csdn.net/datawhale/article/details/103725122
https://zhuanlan.zhihu.com/p/73678009

六.XGB的评价

优点
精度更高： GBDT 只用到一阶泰勒展开，而 XGBoost 对损失函数进行了二阶泰勒展开。XGBoost 引入二阶导一方面是为了增加精度，另一方面也是为了能够自定义损失函数，二阶泰勒展开可以近似大量损失函数；

灵活性更强： GBDT 以 CART 作为基分类器，XGBoost 不仅支持 CART 还支持线性分类器，使用线性分类器的 XGBoost 相当于带 和 正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。此外，XGBoost 工具支持自定义损失函数，只需函数支持一阶和二阶求导；

正则化： XGBoost 在目标函数中加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、叶子节点权重的 范式。正则项降低了模型的方差，使学习出来的模型更加简单，有助于防止过拟合，这也是XGBoost优于传统GBDT的一个特性。

Shrinkage（缩减）： 相当于学习速率。XGBoost 在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。传统GBDT的实现也有学习速率；

列抽样： XGBoost 借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算。这也是XGBoost异于传统GBDT的一个特性；

缺失值处理： 对于特征的值有缺失的样本，XGBoost 采用的稀疏感知算法可以自动学习出它的分裂方向；

XGBoost工具支持并行： boosting不是一种串行的结构吗?怎么并行的？注意XGBoost的并行不是tree粒度的并行，XGBoost也是一次迭代完才能进行下一次迭代的（第 次迭代的代价函数里包含了前面 次迭代的预测值）。XGBoost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），XGBoost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。

可并行的近似算法： 树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以XGBoost还提出了一种可并行的近似算法，用于高效地生成候选的分割点。

缺点
虽然利用预排序和近似算法可以降低寻找最佳分裂点的计算量，但在节点分裂过程中仍需要遍历数据集；

预排序过程的空间复杂度过高，不仅需要存储特征值，还需要存储特征对应样本的梯度统计值的索引，相当于消耗了两倍的内存。

cs