决策树相关算法——XGBoost原理分析及实例实现(二)

我们知道决策树中的ID3算法和C4.5或者是CART分类回归树的构造过程中都是有一个切分评价标准，ID3进行特征选择的是信息增益，C4.5是信息增益率。而CART分类树构造的切分点是根据选择的特征和特征值的Gini系数进行对比。CART回归树是根据切分点后的平方误差进行评价的。我们的XGBoost的决策树构建过程中切分点的选择是根据代价函数(代价函数可以是任意的一般函数)的化简值——如下图所示。具体化简过程参照上篇博客。

原因:完全贪心算法，贪婪的遍历所有的切分点，当所有的数据点不能全部加载到内存时，算法就会变的低效。同时在XGBoost分布式学习时也会遇到这样的问题。所以此时需要一些近似算法来获取切分点列表。

XGBoost中的近似方法框架

算法讲解：前面一个 for 循环做的工作是，对特征 K 根据该特征分布的分位数找到切割点的候选集合 Sk={sk1,sk2,...,skl} ,这样做的目的是提取出部分的切分点不用遍历所有的切分点。其中获取某个特征K的候选切割点的方式叫 proposal .主要有两种 proposal 方式: global proposal 和 local proposal .

第二个 for 循环的工作是，将每个特征的取值映射到由这些该特征对应的候选点集划分的分桶(buckets)区间 {skv≥xjk>skv−1} 中，对每个桶(区间)内的样本统计值G、H进行累加统计，最后在这些累计的统计量上寻找最佳分裂点。这样做的主要目的是获取每个特征的候选分割点的G和H量。

存在的疑惑——后面会讲解：

举例子说明，一般来说对于一个数据列表有：

ϕ−quantile表示rank=⌊ϕ−quantile×N⌋ 的元素

我们需要取出 0.25-quantile (0.25分位点的数),即取出rank为0.25*N的数。

举例子说明，一般来说对于一个数据列表有，取元素的方法为，指定rank(大于0小于1)即可，0.5分位点的元素为3：

此部分便是讲述疑惑中的问题1：如何根据特征分布的分位数挑选出候选点集？？？

通常，一个特征的百分位数可以被用来让候选在数据上进行均匀地分布。我们用一个multi-set: D _k =(x _1k ,h ₁ ),(x _2k ,h ₂ ),…(x _nk ,h _n )，来表示每个训练实例的第k个特征值以及它的二阶梯度值统计。其中h _i 表示i个实例的第k个特征值对应的二阶梯度值统计，可看作i个实例的第k个特征值的权重。至于为什么可以看作是权重作为 疑惑问题3 后面会提到。

如下示例有：

一般来说对于加权分位数缩略图的取值是根据Rank的值进行的，Rank计算公式为：

该 Rank 函数，输入为某个特征值 z ,计算的是该特征所有可取值中小于z的特征值的总权重占总的所有可取值的总权重和的比例，输出为一个比例值。于是我们就能用下面这个不等式来寻找候选分离点{s _k1 ,s _k2 ,s _k3 ,⋅,⋅,s _kl }

其中s _k1 是特征k的取值中最小的值x _ik ，其中s _kl 是特征k的取值中最大的值x _ik ，这是分位数缩略图的要求需要保留原序列中的最小值和最大值。ϵ是一个近似比例，或者说是扫描步幅。可以理解为在特征K的取值范围上，按照步幅ϵ挑选出特征K的取值候选点，组成候选点集。起初是从s _k1 起，每次增加ϵ∗(s _kl −s _k1 )作为候选点，加入到候选集中。如此计算的话，这意味着大约是 1/ϵ 个候选点。

此时特征k的取值中最小的值x _ik 和特征k的取值中最大的值x _ik 来自的数据集D _k ，对于D _k 的数据集有两种定义，一种是一开始选好，然后每次树切分都不变，也就是说是在总体样本里选最大值s _kl 和最小值s _k1 ，这就是我们之前定义的 global proposal 。另外一种是树每次确定好切分点的分割后样本也需要进行分割，最大值s _kl 和最小值s _k1 来自子树的样本集D _k ，这就是 local proposal 。

疑惑问题3，对于特征K的取值为什么权权可以表示为h _i 为二阶梯度的值?

首先，将代价函数公式进行转换：

最后的代价函数就是一个加权平方误差，权值为h _i ,labels为-g _i /h _i .所以可以将特征K的取值的权重看成对应的h _i 。

分布式加权分位数缩略图：对于需要并行的获取候选集切割点，需要使用分布式加权分位数缩略图，必须包含两个操作m合并erge和修剪prune。分布式加权分位数缩略图具体如何操作需要查看论文XGBoost: A Scalable Tree Boosting System附录1.

数据集稀疏的原因：1.样本中的部分数据缺失。2.统计中过多的 zero entries。3.特征工程中的one-hot encoding。

于是XGBoost中提出了稀疏感知的划分查找算法，如下：

如下为带缺省方向的树结构。当在split时相应的feature值缺失时，一个样本可以被归类到缺省方向上。

大体思想流程是：在每个树节点上增加一个缺省的方向（default direction），如上图所示，当稀疏矩阵x中的某个特征值缺失时，该样本实例被归类到缺省方向上。默认的缺省方向有两种，一个是左分支和右分支。XGBoost指定的默认缺省方向是从数据中学习到的，并不是随机指定的。

稀疏感知的划分查找算法的理解：至于缺省值的实例分到哪个分支方向，如何学习的问题，稀疏感知的划分查找算法计算切分后的评判标准(公式六)时只关注没有缺失的条目I _k .然后再通过将实例以枚举的方式，枚举项为默认分到左分支和默认分到右分支，计算切分前后相差最大的Score，然后将缺失值的实例分到该分支上。