tree learning的其中一个关键问题是,找到等式(7)的最好划分(best split)。为了达到这个目标,split finding
算
法
会
在所有特征(features)上,枚举所有可能的划分(splits)。我们称它为“
完
全
贪
婪
算
法
(exact greedy
algorithm)”。许多单机版tree-boosting实现中,包括scikit-learn,R’s gbm以及单机版的XGBoost,都支持完全贪
婪算法(exact greedy algorithm)。该算法如算法1所示。它会对连续型特征(continuous features)枚举所有可能
的split。为了更高效,该算法必须首先根据特征值对数据进行排序,以有序的方式访问数据来枚举等式(7)中的结构得
分(structure score)的梯度统计(gradient statistics)。
[算法1]
(1) for j in sorted(I, by ):表示对第m个特征,对叶子节点j,依据特征k进行对该节点内的所有实例进行从小到大
的排序,依据下面Score公式计算该split下的Score。
(2) 算法总结:对每个叶子节点j,对叶子节点的每个特征k,依据k对实例进行排序,然后计算该特征下的Score,对
该叶子节点,遍历所有特征后,得到该节点下对应的score及split进行输出(即最佳割特征下对应的最佳分割点)。
(3) However, it is impossible to efficiently do so when the data does not fit entirely into memory.
3.2 Approximate Algorithm
前面提到过,XGBoost每一步选能使分裂后增益最大的分裂点进行分裂。而分裂点的选取之前是枚举所有分割点,这
称为精确的贪心法(Exact Greedy Algorithm).
当
数
据
量
十
分
庞
大
,
以
致
于不
能
全
部
放
入内
存
时
,
Exact Greedy
算
法
就
会
很
慢
。
因此XGBoost引入了近似的算
法。
我们总结了一个近似框架(approximate framework),重组了在文献[17,2,22]中提出的思想,如算法2所示。为了
进行总结(summarize),
该
算
法
会
首
先
根
据
特
征
分
布
的百
分
位
数
(percentiles of feature distribution)
,
提
出
候
选
划分
点
(candidate splitting points)
。
接
着
,
该
算
法
将
连
续
型
特
征
映
射
到
由
这
些
候
选
点
划分
的
分
桶
(buckets)
中
,
聚
合
统
计
信
息
,
基
于
该
聚
合
统
计
找
到
在
建
议
(
proposal
)
间
的
最
优
解
。
简单的说,就是根据特征 的分布来确定 个候选切分点 ,然后根据这些候选切分点把相
应的样本放入对应的
桶
中,对每个桶的G,H进行累加。最后在候选切分点集合上贪心查找,和Exact Greedy
Algorithm类似。该算法描述如下: