集成学习

集成学习概述

集成学习通过将多个学习器进行结合,常可以获得比单一学习器更加优越显著的泛化能力, 在个体学习器是弱学习器(泛化能力略优于随机猜测的学习器,如在二分类问题上精度略高于 $50%$ 的学习器)的情况下尤为明显。

Bagging和随机森林

Bagging

$Bagging$ 通过随机采样确定分类器,从而保证分类器的差异,各个弱学习器之间没有依赖关系,可以并行生成:

$Bagging$ 的个体学习器的训练集是通过有放回的随机采样得到的。通过 $T$ 次的随机采样,就可以得到 $T$ 个采样集,对于这 $T$ 个采样集,分别独立地训练出 $T$ 个学习器,再对这 $T$ 个学习器通过结合策略来得到最终的强学习器。

算法过程

$Bagging$ 的集合策略也比较简单,对于分类问题,通常使用简单投票法,得到最多票数的类别或者类别之一为最终的模型输出。对于回归问题,通常使用简单平均法,对 $T$ 个弱学习器得到的回归结果进行算术平均得到最终的模型输出。

Random Forest

随机森林是 $Bagging$ 的一个特化进阶版,特化是因为随机森林的弱学习器都是决策树。所谓的进阶是随机森林在 $Bagging$ 的样本随机采样基础上,又加上了特征随机选择,其基本思想没有脱离 $Bagging$ 的范畴。

随机森林使用 $CART$ 决策树作为弱学习器,但它在 $Bagging$ 的基础上进行了改进,改进点在于决策树的建立上:

普通的决策树会在节点上所有的 $n$ 个样本特征中选择一个最优的特征来做决策树的左右子树划分,但是随机森林随机选择了节点上的一部分样本特征,这个数字小于 $n$,假设为 $n_{sub}$,然后在这些随机选择的 $n_{sub}$ 个样本特征中,选择一个最优的特征来做决策树的左右子树划分。这样进一步增强了模型的泛化能力。

如果 $n_{sub}=n$,则此时随机森林的 $CART$ 决策树和普通的 $CART$ 决策树没有区别。$n_{sub}$ 越小,则模型越健壮,泛化能力越强,当然此时对于训练集的拟合程度会变差。也就是说 $n_{sub}$ 越小, 模型的方差会减小,但是偏差会增大。在实际案例中,一般会通过交叉验证调参获取一个合适的 $n_{sub}$ 的值,通常来讲,$n_{sub}$ 一般取 $\sqrt n$ 或者 $\log n$。

除此之外,随机森林算法和普通的 $Bagging$ 没有区别。

算法过程

优缺点分析

优点

  • 训练时树与树之间相互独立,训练可以高度并行化
  • 由于可以随机选择决策树节点划分特征,能高效的训练高维特征
  • 由于采用了随机采样,训练出的模型的方差小,泛化能力强
  • 相对于 $Boosting$ 系列的 $Adaboost$ 和$GBDT$,随机森林实现比较简单
  • 对部分特征缺失不敏感

缺点

  • 随机森林已经被证明在某些噪音较大的分类或回归问题上会过拟合
  • 取值划分比较多的特征容易对随机森林的决策产生更大的影响,从而影响拟合的模型的效果

Boosting和提升树

Boosting

从图中可以看出,$Boosting$ 算法的工作机制是首先从训练集用初始权重训练出一个弱学习器 $1$,根据弱学习器的学习误差率来更新训练样本的权重,使弱学习器 $1$ 学习误差率高的训练样本点的权重变高,使得这些误差率高的点在后面的弱学习器 $2$ 中得到更多的重视。然后基本调整权重后的训练集来训练弱学习器,如此重复进行,直到弱学习器数达到事先指定的数目 $T$,最后将这 $T$ 个弱学习器通过结合策略进行整合,得到最终的强学习器。

$Boosting$ 其实是一个算法框架,没有规定具体的函数实现方式,框架内的算法,都要解决如下四个问题:

  • 如何计算学习误差率 $e$
  • 如何得到弱学习器权重系数 $\alpha$
  • 如何更新样本权重 $w$
  • 使用何种结合策略

Adaptive Boosting

$AdaBoost$ 是英文“自适应增强”的缩写,其本质是一个加性模型。$AdaBoost$ 方法的自适应在于:前一个分类器分错的样本会被用来训练下一个分类器。$AdaBoost$ 既可以用于分类,又可以用于回归。

分类问题

算法描述

对二元分类问题,数据标签 $y_i$ 和分类器输出 $g(x_i)$ 取值范围均为 ${+1,-1}$,训练样本为:
$$ T= {(x_1,y_1),(x_2,y_2),\dots,(x_m,y_m)}$$

训练集数据对应第 $k$ 个弱分类器的权重为:
$$D(k) = (w_{k1},w_{k1},\dots, w_{k1}) \\
w_{1i} = \frac 1 m ; \; i = 1,2,\dots, m $$

  1. 误差率计算
    第 $k$ 个弱分类器 $g_k(x)$ 在训练集上的加权误差率为:
    $$ e_k = \sum_{i=1}^m w_{ki}I(g_k(x_i)\neq y_i) $$

  2. 弱学习器权重计算
    第 $k$ 个弱分类器 $g_k(x)$ 的权重系数为:
    $$ \alpha_k = \frac 1 2 \ln \frac {1-e_k} {e_k}$$
    从上式可以看出,如果分类误差率 $e_k$ 越大,则对应的弱分类器权重系数越小,$e_k$ 误差率越小的弱分类器权重系数越大,也就是说误差率大的弱学习器对最后的强学习器影响小。

  3. 样本权重更新
    已知第 $k$ 个弱分类器的训练集样本权重 $w_{ki}$ 和分类器权重 $\alpha_k$,则第 $k+1$ 个弱分类器对应的训练集样本权重为:
    $$ w_{k+1,i} = \frac {w_{ki}} {Z_k} exp (-\alpha_k y_i g_k(x_i)) $$
    其中,规范化因子:
    $$ Z_k =\sum_{i=1}^m w_{ki} exp (-\alpha_k y_i g_k(x_i)) $$
    从权重更新公式可以看出,如果第 $i$ 个样本被分错,$y_i g_k(x_i)\lt 0$,该样本的权重在第 $k+1$ 个分类器中就会增大,如果分类正确,该样本的权重在第 $k+1$ 个分类器中就会减小。

  4. 结合策略
    $Adaboost$ 分类采用的是加权平均法,最终的强分类器为:
    $$f(x) = sign(\sum_{k=1}^K\alpha_k g_k(x)) $$

公式推导

公式的推导利用的是前向分步加法算法,模型是由基本分类器组成的加法模型,损失函数是指数函数。

第 $k-1$ 轮的强学习器为:
$$ f_{k-1}(x) =\sum_{i=1}^{k-1}\alpha_i g_i(x) \tag{a-1}$$

而第 $k$ 轮的强学习器为:
$$ f_k(x) = \sum_{i=1}^k\alpha_i g_i(x) \tag{a-2}$$

于是有:
$$ f_k(x) = f_{k-1}(x) + \alpha_kg_k(x) \tag{a-3}$$

$Adaboost$ 的损失函数为指数函数,定义损失函数为:

$$ L = \sum_{i=1}^m exp(-y_if_k(x_i))=\sum_{i=1}^m exp(-y_i(f_{k-1}(x_i)+\alpha_k g_k(x_i))) \tag{a-4}$$

其中 $f_{k-1}(x)$ 是前 $k-1$ 个弱学习器组成的强学习器,所以损失函数只与 $\alpha_k$ 和 $g_k(x)$ 有关,即:
$$ \arg\min_{\alpha_k,g_k(x)} \sum_{i=1}^m exp(-y_i(f_{k-1}(x_i)+\alpha_k g_k(x_i))) \tag{a-5}$$

令 $\widetilde{r}_{k,i} = exp(-y_if_{k-1}(x_i))$,它的值不依赖于 $\alpha_k$ 和 $g_k(x)$,因此在迭代过程中和最小化无关,于是 $a-5$ 式可以写作:
$$ \arg\min_{\alpha_k,g_k(x)} \sum_{i=1}^m \widetilde{r}_{k,i} exp(-y_i\alpha_k g_k(x_i)) \tag{a-6}$$

当 $y_i=g_k(x_i)$ 时,$y_i g_k(x_i) = 1$,否则$y_i g_k(x_i) = -1 $,于是 $a-6$ 式又可以改写为:

$$ \arg\min_{\alpha_k,g_k(x)} e^{-\alpha_k} \sum_{y_i = g_k(x_i)} \widetilde{r}_{k,i} + e^{\alpha_k} \sum_{y_i \neq g_k(x_i)} \widetilde{r}_{k,i} \tag{a-7}$$$$ \arg\min_{\alpha_k,g_k(x)} (e^{\alpha_k}-e^{-\alpha_k}) \sum_{i=1}^m \widetilde{r}_{k,i}I(y_i \neq g_k(x_i)) + e^{-\alpha_k} \sum_{i=1}^m \widetilde{r}_{k,i} \tag{a-8}$$

对 $\alpha_k$ 求偏导:
$$ \frac {\partial L} {\partial \alpha_k} = (e^{\alpha_k}+e^{-\alpha_k}) \sum_{i=1}^m \widetilde{r}_{k,i}I(y_i \neq g_k(x_i)) - e^{-\alpha_k} \sum_{i=1}^m \widetilde{r}_{k,i}\tag{a-9} $$

令导数等于 $0$ ,于是有:
$$ (e^{2\alpha_k}+ 1) \sum_{i=1}^m \widetilde{r}_{k,i}I(y_i \neq g_k(x_i)) = \sum_{i=1}^m \widetilde{r}_{k,i}\tag{a-10} $$$$ e^{2\alpha_k} = \frac {\sum_{i=1}^m \widetilde{r}_{k,i}} {\sum_{i=1}^m \widetilde{r}_{k,i}I(y_i \neq g_k(x_i))} -1 \tag{a-11} $$$$ \alpha_k = \frac 1 2\ln \left(\frac {\sum_{i=1}^m \widetilde{r}_{k,i}} {\sum_{i=1}^m \widetilde{r}_{k,i}I(y_i \neq g_k(x_i))} -1 \right) \tag{a-12} $$

根据 $\widetilde{r}_{k,i} = exp(-y_i(f_{k-1}(x_i))$ 可得:

$$\begin{align} \widetilde{r}_{k+1,i}
&= exp(-y_i f_k(x_i)) \nonumber \\
&= exp(-y_i(f_{k-1}(x_i) + \alpha_k g_k(x_i))) \nonumber \\
&= exp(-y_if_{k-1}(x_i)) \times exp(-y_i\alpha_k g_k(x_i)) \nonumber \\
&= \widetilde{r}_{k,i} exp(-y_i\alpha_k g_k(x_i)) \tag{a-13}
\end{align}$$

比较 $\widetilde{r}_{k,i}$ 与 $w_{k,i}$ 的递推公式,发现 $\widetilde{r}_{k,i}$ 与未除以规范化常数的 $w_{k,i}$ 相同,所以有:

$$ e_k = \frac {\sum_{i=1}^m \widetilde{r}_{k,i}I(y_i \neq g_k(x_i))} {\sum_{i=1}^m \widetilde{r}_{k,i}} \tag{a-14} $$

把式 $a-14$ 代入到式 $a-12$ 中,可以得到:
$$ \alpha_k = \frac 1 2 \ln(\frac 1 {e_k} -1) = \frac 1 2 \ln \frac {1-e_k} {e_k} \tag{a-15}$$

关于算法在训练集上错误率的推导,见另外一篇博客:从决策树到Adaboost算法

算法实例

回归问题

$Adaboost$ 的回归问题有很多变种,这里以 $Adaboost\;R2$ 算法为例,依旧套用 $Boosting$ 的四步框架:

  1. 误差率计算
    第 $k$ 个弱分类器 $g_k(x)$ 在训练集上的最大误差为:
    $$ E_k = max |y_i - g_k(x_i)| \; i=1,2,\dots,m$$
    然后计算每个样本的相对误差:
    $$ e_{ki} = \frac {|y_i - g_k(x_i)|}{E_k} $$
    若是选用平方误差,则有 $e_{ki} = \frac {(y_i - g_k(x_i))^2}{E_k}$,若是选用指数误差,则有 $e_{ki} = 1- exp (\frac {- y_i + g_k(x_i)}{E_k}) $。
    最终得到第 $k$ 个弱分类器的误差率:
    $$ e_k = \sum_{i=1}^m w_{ki}e_{ki} $$

  2. 弱学习器权重计算
    第 $k$ 个弱分类器 $g_k(x)$ 的权重系数为:
    $$ \alpha_k = \frac {e_k} {1-e_k}$$

  3. 样本权重更新
    第 $k+1$ 个弱分类器对应的训练集样本权重为:
    $$ w_{k+1,i} = \frac {w_{ki}} {Z_k} \alpha_k^{1-e_{ki}} $$
    其中,规范化因子:
    $$ Z_k =\sum_{i=1}^m w_{ki} \alpha_k^{1-e_{ki}} $$

  4. 结合策略
    和分类问题一样,回归同样采用的是加权平均法,最终的强分类器为:
    $$f(x) = \sum_{k=1}^K (\ln \frac 1 {\alpha_k}) g_k(x) $$

优缺点分析

理论上任何学习器都可以用于 $Adaboost$,但一般来说,使用最广泛的$Adaboost$ 弱学习器是决策树和神经网络,对于决策树,$Adaboost$ 分类使用的是 $CART$ 分类树。

优点

  • $Adaboost$ 作为分类器时,分类精度很高
  • 在 $Adaboost$ 的框架下,可以使用各种回归分类模型来构建弱学习器,非常灵活
  • 作为简单的二元分类器时,构造简单,结果易理解
  • 不容易发生过拟合

缺点

  • 对异常样本敏感,异常样本在迭代中可能会获得较高的权重,影响最终的强学习器的预测准确性

Gradient Boosting Decision Tree

$GBDT$ 是一种迭代的决策树算法,该算法由多棵决策树组成,所有树的结论累加起来做最终答案。它在被提出之初就和 $SVM$ 一起被认为是泛化能力较强的算法。$GBDT$ 中的树是回归树(不是分类树),$GBDT$ 用来做回归预测,调整后也可以用于分类。

回归树

回归树总体流程类似于分类树,区别在于,回归树的每一个节点都会得一个预测值,以年龄为例,该预测值等于属于这个节点的所有人年龄的平均值。分枝时穷举每一个特征的每个阈值找最好的分割点,但衡量最好的标准不再是最大熵,而是最小化平方误差。通过最小化平方误差能够找到最可靠的分支依据。分支直到每个叶子节点上人的年龄都唯一或者达到预设的终止条件(如叶子个数上限),若最终叶子节点上人的年龄不唯一,则以该节点上所有人的平均年龄做为该叶子节点的预测年龄。

提升树

提升树是迭代多棵回归树来共同决策,当采用平方误差损失函数时,每一棵回归树学习的是之前所有树的结论和残差,拟合得到一个当前的残差回归树。提升树即是整个迭代过程生成的回归树的累加。

算法描述

算法实例
已知 $4$ 个人,$A,B,C,D$ 年龄分别是 $14,16,24,26$。又已知购物金额、上网时长、经常到百度知道提问等特征。提升树的过程如下:

GBDT 回归算法

上述的提升树算法,是对残差进行拟合,即以 $|y_i - f_{k-1}(x_i)|_{i=1}^m$ 作为第 $k$ 次拟合的训练样本,而 $GBDT$ 名为梯度提升树,使用损失函数的负梯度来拟合本轮损失的近似值。

按照加法模型,有:
$$ L(y, f_k(x)) = L(y, f_{k-1}(x) +g_k (x)) \tag{g-1}$$

泰勒公式:设是 $n$ 一个正整数,如果定义在一个包含 $a$ 的区间上的函数 $f$ 在点 $a$ 处 $n+1$ 次可导,那么对于这个区间上的任意 $x$ 都有:$\displaystyle f(x)=\sum_{n=0}^{N}\frac{f^{(n)}(a)}{n!}(x-a)^ n+R_ n(x)$,其中的多项式称为函数在 $a$ 处的泰勒展开式,$R_n(x)$ 是泰勒公式的余项且是 $(x-a)^n$ 的高阶无穷小。

根据泰勒公式把 $f(x+\Delta x)$ 在 $x$ 处进行一阶展开,可以得到:
$$ f(x+\Delta x) \approx f(x) + f’(x)\Delta x \tag{g-2}$$

由式 $g-1$ 可知,损失函数是关于变量 $f_{k-1}(x) +g_k (x)$ 的函数,若把变量 $f_{k-1}(x)$ 看成是式 $g-2$ 中的 $x$,把变量 $g_k (x)$ 看成是式 $g-2$ 中的 $\Delta x$,则式 $g-1$ 可转化为:
$$ L(y, f_k(x)) = L(y, f_{k-1}(x)) + L’(y, f_{k-1}(x))g_k (x) \tag{g-3}$$

上式可以改写为:
$$ L(y, f_k(x)) = L(y, f_{k-1}(x)) + \sum_{i=1}^m L’(y_i, f_{k-1}(x_i))g_k(x_i) \tag{g-4}$$

若对 $g_k(x_i)$,使其取值为 $-L’(y_i, f_{k-1}(x_i))$,于是有:
$$ L(y, f_k(x)) = L(y, f_{k-1}(x)) - \sum_{i=1}^m L’(y_i, f_{k-1}(x_i))^2 \tag{g-5}$$

显然,$L(y, f_k(x)) \lt L(y, f_{k-1}(x))$ 必然成立,这样就实现了损失函数的减小,此时 $g_k(x_i) = -L’(y_i, f_{k-1}(x_i))$ 为第 $k$ 次迭代时第 $i$ 个样本的损失函数的负梯度,记作 $r_{ki}$,即:
$$r_{ki} = \frac {\partial L(y_i, f_{k-1}(x_i))} {\partial f_{k-1}(x_i)} \tag{g-6}$$

算法过程

步骤 $2.b$ 中对训练集中的每个数据 $x_i$,计算 $r_{mi}$,得到新的数据集 ${(x_i,r_{mi})}_{i=1}^J$。使用新数据集训练得到的即为第 $m$ 棵回归树。
步骤 $2.c$ 中设第 $m$ 棵回归树共有 $J$ 个叶子节点,每个叶子节点被表示为 $R_{mj}$,对每个叶子节点,求出对叶子节点拟合效果最好的的输出值 $c_{mj}$,此时模型的输出值应该为 $f_{m -1}(x_i)+c$。

GBDT 二元分类算法

$GBDT$ 的分类算法从思想上和 $GBDT$ 的回归算法没有区别,使用的弱学习器也都是 $CART$ 回归树,但是由于样本输出不是连续的值,而是离散的类别,导致无法直接从输出类别去拟合类别 为了解决这个问题,主要有两个方法,一个是用指数损失函数,此时 $GBDT$ 退化为 $Adaboost$ 算法。另一种方法是用类似于逻辑回归的对数似然损失函数的方法。也就是说,用类别的预测概率值和真实概率值的差来拟合损失。对于二元 $GBDT$ ,如果用对数似然损失函数,则损失函数为:
$$ L(y, f(x)) = log(1+ exp(-yf(x)))$$

其中 $y \in {+1, -1}$,此时负梯度误差为:
$$ r_{ki} = -\frac{\partial L(y_i, f_{k-1}(x_i))}{\partial f_{k-1}(x_i)} = \frac {y_i} {1+exp(y_if(x_i))}$$

对于生成的决策树,各个叶子节点的最佳残差拟合值为:
$$ c_{kj} = \arg\min_c\sum_{x_i \in R_{kj}} log(1+exp(-y_i(f_{k-1}(x_i) +c)))$$

由于上式比较难优化,一般使用近似值代替:
$$ c_{kj} = \frac {\sum_{x_i \in R_{kj}}r_{ki}} {\sum_{x_i \in R_{kj}}|r_{ki}|(1-|r_{ki}|)} $$

除了负梯度计算和叶子节点的最佳残差拟合的线性搜索,二元 $GBDT$ 分类和 $GBDT$ 回归算法过程相同。

GBDT 正则化

和 $Adaboost$ 一样,$GBDT$ 也需要正则化,防止过拟合。$GBDT$ 的正则化主要有三种方式:

第一种是增加正则化项,类似 $Adaboost$ 中的弱分类器权重,定义为 $v$,对于前面的弱学习器的迭代 $f_k(x) = f_{k-1}(x) +h_k(x)$,如果加上了正则化项,则有
$f_k(x) = f_{k-1}(x) +vh_k(x)$,$v$ 的取值范围为 $(0,1]$。对于同样的训练集,较小的 $v$ 意味着需要更多的弱学习器的迭代次数。通常用步长和迭代最大次数一起来决定算法的拟合效果。
第二种正则化的方式是通过子采样比例,采用比例取值为 $(0,1]$。注意这里的子采样和随机森林不一样,随机森林使用的是放回抽样,而这里是不放回抽样。如果取值为 $1$,则全部样本都使用,等于没有使用子采样。如果取值小于$1$,则只有一部分样本会去做 $GBDT$ 的决策树拟合。选择小于 $1$ 的比例可以减少方差,即防止过拟合,但是会增加样本拟合的偏差,因此取值不能太低,推荐在 $[0.5, 0.8]$ 之间。由于使用了子采样,程序可以并行学习。
第三种是对于弱学习器即 $CART$ 回归树进行正则化剪枝

GBDT 常用损失函数

对于分类算法,常用损失函数有如下两种:

  • 指数损失
    $$ L(y, f(x)) = exp(-yf(x))$$
  • 对数损失(二元分类)
    $$ L(y, f(x)) = \log(1+ exp(-yf(x)))$$
  • 对数损失(多元分类)
    $$ L(y, f(x)) = - \sum_{k=1}^K y_k \log p_k(x)$$

对于回归算法,常用损失函数有如下三种:

  • 均方差损失
    $$ L(y, f(x)) =(y-f(x))^2 $$
  • 绝对值损失
    $$ L(y, f(x)) =|y-f(x)|$$
  • $Huber$损失
    $$ L(y, f(x))= \begin{cases} \frac{1}{2}(y-f(x))^2& {|y-f(x)| \le \delta}\\ \delta(|y-f(x)| - \frac{\delta}{2})& {|y-f(x)| > \delta} \end{cases} $$
    $Huber$损失可以看做为均方差和绝对损失的折中产物,对于远离中心的异常点,采用绝对损失,而中心附近的点采用均方差,这个界限一般用分位数点度量
    (分位数,亦称分位点,是指将一个随机变量的概率分布范围分为几个等份的数值点,常用的有中位数即二分位数、四分位数、百分位数等)。

优缺点分析

优点

  • 可以灵活处理各种类型的数据,包括连续值和离散值。
  • 在相对少的调参时间情况下,预测的准确率比较高
  • 使用一些健壮的损失函数,对异常值的鲁棒性非常强。比如 $Huber$ 损失函数。

缺点

  • 由于弱学习器之间存在依赖关系,难以并行训练数据。不过可以通过子采样来达到部分并行。

XGBoost

$XGBoost$ 实际上是对 $GBDT$ 的一个改进,现在已经成为了最为流行的提升树算法,这里只将其与 $GDBT$ 做一个简单的比较。

首先:$XGBoost$ 在目标函数中显示的加上了正则化项,基学习为 $CART$ 时,正则化项与树的叶子节点的数量 $T$ 和叶子节点的值有关。
$$ L(\phi) = \sum_i l(y_i, f_k(x_i)) + \sum_k \Omega(f_k)$$
其中,$\Omega(f)=\gamma T + \frac12 \lambda \sum_{j=1}^T w_j^2$,$T$ 表示决策树的叶子节点数,$w$ 表示该决策树叶子节点对应的值向量。

其次,$GBDT$ 中使用的是损失函数的一阶泰勒展开来拟合残差,$XGBoost$ 使用的是二阶泰勒展开来拟合残差。
$$ L(y, f_k(x)) = L(y, f_{k-1}(x)) + L’(y, f_{k-1}(x))g_k (x) + \frac 1 2L’’(y, f_{k-1}(x))g^2_k(x) + \Omega(g_k) $$

除此之外,还有:

  • $XGBoost$ 在进行完一次迭代时,会将叶子节点的权值乘上一个系数 $\eta$,主要是为了削弱每棵树的影响,让后面有更大的学习空间
  • $XGBoost$ 借鉴了随机森林的做法,支持列抽样,不仅防止过拟合,还能减少计算
  • $XGBoost$ 还可以自动学习有缺失值的样本的出的分裂方向
  • $XGBoost$ 工具支持并行。$XGBoost$ 的并行不是 $Tree$ 粒度的并行,$XGBoost$ 也是一次迭代完才能进行下一次迭代的,这里的并行是在特征粒度上的。我们知道,决策树的学习最耗时的一个步骤就是对特征的值进行排序(因为要确定最佳分割点),$XGBoost$ 在训练之前,预先对数据进行了排序,然后保存为块结构,后面的迭代中重复地使用这个结构,大大减小计算量。这个块结构也使得并行成为了可能,在进行节点的分裂时,需要计算每个特征的增益,最终选增益最大的那个特征去做分裂,那么各个特征的增益计算就可以开多线程进行

参考文献:
[1] 周晓飞,《统计机器学习》,中国科学院大学2017年秋季研究生课程
[2] 李航,《统计学习方法》,清华大学出版社
[3] 周志华,《机器学习》,清华大学出版社