Max Blog

树模型第二节，从集成学习到随机森林、GBDT等

本篇为树模型第二篇，主要介绍集成学习相关内容以及对应算法，包括随机森林，Adaboost和GBDT。

1 集成学习

常见的集成学习框架有三种：Bagging，Boosting 和 Stacking。

1.1 Bagging

Bagging(Boostrap aggregating),每个基学习器都会对训练集进行有放回的抽样得到子训练集。

每个基学习器基于不同的子训练集进行训练，并松鹤所有基学习器的结果汇总为最后结果。常见的纵膈方法是投票法，投票最多的结果为最终的结果。

1.2 Boosting

Boosting 训练过程为阶梯状，基模型的训练是有顺序的，每个基模型都会在前一个基模型学习的基础上进行学习，最终综合所有基模型的预测值产生最终的预测结果，用的比较多的综合方式为加权法。

1.3 Stacking

Stacking 是先用全部数据训练好基模型，然后每个基模型都对每个训练样本进行的预测，其预测值将作为训练样本的特征值，最终会得到新的训练样本，然后基于新的训练样本进行训练得到模型，然后得到最终预测结果。

1.4 偏差与方差

这里对于偏差与方差不做过多的介绍，只简单说一下重点。

• 偏差(Bias)：模型预测结果与真实结果的差距。要想预测的好，就需要复杂化模型，容易过拟合。
• 方差(Variance)：模型预测值的离散程度。要想方差小，需要减少复杂度，容易欠拟合。

以打靶为例，低偏差说明说明打得准，低方差说明子弹散开程度小。两者通常处于一个平衡状态，很难同时做到同时低。

对于集成学习中，Bagging 和 Stacking 中的基模型为强模型（偏差低，方差高），而Boosting 中的基模型为弱模型（偏差高，方差低）。

对于集成学习模型来说，模型的总体期望：

$\begin{aligned} E(F) &=E\left(\sum_{i}^{m} r_{i} f_{i}\right) \\ &=\sum_{i}^{m} r_{i} E\left(f_{i}\right) \end{aligned}$

模型的总体方差：

$\begin{aligned} \operatorname{Var}(F) &=\operatorname{Var}\left(\sum_{i}^{m} r_{i} f_{i}\right) \\ &=\sum_{i}^{m} \operatorname{Var}\left(r_{i} f_{i}\right)+\sum_{i \neq j}^{m} \operatorname{Cov}\left(r_{i} f_{i}, r_{j} f_{j}\right) \\ &=\sum_{i}^{m} r_{i}^{2} \operatorname{Var}\left(f_{i}\right)+\sum_{i \neq j}^{m} \rho r_{i} r_{j} \sqrt{\operatorname{Var}\left(f_{i}\right)} \sqrt{\operatorname{Var}\left(f_{j}\right)} \\ &=m r^{2} \sigma^{2}+m(m-1) \rho r^{2} \sigma^{2} \\ &=m r^{2} \sigma^{2}(1-\rho)+m^{2} r^{2} \sigma^{2} \rho \end{aligned}$

模型总体的准确度可由方差和偏差共同决定：

$\text { Error }=\text { bias }^{2}+\text { var }+\xi$

1.4.1 Bagging

对于bagging来说，每个基模型的权重等于1/m且期望近似相等，因此可得：

$\begin{aligned} E(F) &=\sum_{i}^{m} r_{i} E\left(f_{i}\right) \\ &=m \frac{1}{m} \mu \\ &=\mu \\ \operatorname{Var}(F) &=m r^{2} \sigma^{2}(1-\rho)+m^{2} r^{2} \sigma^{2} \rho \\ &=m \frac{1}{m^{2}} \sigma^{2}(1-\rho)+m^{2} \frac{1}{m^{2}} \sigma^{2} \rho \\ &=\frac{\sigma^{2}(1-\rho)}{m}+\sigma^{2} \rho \end{aligned}$

通过上面可得

• 整体模型的期望等于基模型的期望，意味着整体模型的偏差与基模型的偏差近似
• 整体模型的方差小于等于基模型的方差，随着基模型数量的增多，整体方差减少，从而防止过拟合的能力增强，从而防止过拟合的能力增强，模型准确度提高

因此，bagging的基模型为强模型是为了提高模型的偏差。如果是弱模型，则模型整体的偏差增高。

1.4.2 Boosting

Boosting共用一套训练集，所以基模型之间具有强相关性，方差和期望的公式简化为

$\begin{aligned} E(F) &=\sum_{i}^{m} r_{i} E\left(f_{i}\right) \\ \operatorname{Var}(F) &=m r^{2} \sigma^{2}(1-\rho)+m^{2} r^{2} \sigma^{2} \rho \\ &=m \frac{1}{m^{2}} \sigma^{2}(1-1)+m^{2} \frac{1}{m^{2}} \sigma^{2} 1 \\ &=\sigma^{2} \end{aligned}$

• 整体模型的方差等于基模型的方差，基模型为弱模型，方差叫小，从而防止过拟合。
• **模型整体的期望由基模型的期望累加而成，**所以随基模型数量的增加，模型整体的准确度提高。

2 随机森林

用随机的方式建立一个森林，森林由许多决策树组成，每一颗决策树之间没有关联。建立完森林后，每当新样本进入，每颗决策树都会分别进行判断，然后基于投票法给出分类结果。

2.1 基本介绍

随机森林是Bagging的拓展，在以决策树为基学习器构建Bagging的基础上，在训练过程引入了随机特征选择，整个流程包括4部分：

1.随机样本选择(放回抽样)

2.随机特征选择

3.构建决策树

4.随机森林投票

随机特征选择是指每棵树的特征为随机的特征子集，然后再以最优的策略从特征子集选择。这种随机性会导致偏差稍有增加，但是由于随机森林的平均特性，会导致方差减少。方差的减少弥补了偏差的增大。

同时，随机采样的采样方法保证了数据的随机性，每棵树都是最大可能生长，不剪枝也不会出现过拟合。

随机森林过程中包含了双随机：随机的数据采样和随机的特征选择

2.2 优点

• 容易并行
• 可以处理高纬度数据，不用做特征选择

3 Adaboost

AdaBoost（Adaptive Boosting，自适应增强）。

自适应：前一个基本分类器分错的样本会得到加强，加权后的全体样本再次被用来训练下一个基本分类器。同时，在每一轮中加入一个新的弱分类器，直到达到某个预定的足够小的错误率或达到预先指定的最大迭代次数。

3.1 基本流程

1. 初始化训练样本的权重分布，每个样本权重相同
2. 训练弱分类器，基于自适应的原理更新样本的权重。用更新过权重的样本训练下一个分类器
3. 将所有弱分类器组合成强分类器，同时根据每个分类器的分类误差率，对各个弱分类器分配不同的权重。

3.2 损失函数

Adaboost 模型是加法模型，学习算法为前向分步学习算法，损失函数为指数函数的分类问题。

加法模型：最终的强分类器是由若干个弱分类器加权平均得到的。

前向分布学习算法：算法是通过一轮轮的弱学习器学习，利用前一个弱学习器的结果来更新后一个弱学习器的训练集权重。

第K轮的强学习器为：

$F_{k}(x)=\sum_{i=1}^{k} \alpha_{i} f_{i}(x)=F_{k-1}(x)+\alpha_{k} f_{k}(x)$

定义损失函数为n个样本的指数损失函数：

$L(y, F)=\sum_{i=1}^{n} \exp \left(-y_{i} F_{k}\left(x_{i}\right)\right)$

根据前向分布学习算法可得：

$\begin{aligned} L(y, F) &=\sum_{i=1}^{m} \exp \left[\left(-y_{i}\right)\left(F_{k-1}\left(x_{i}\right)+\alpha_{k} f_{k}\left(x_{i}\right)\right)\right] \\ &=\sum_{i=1}^{m} \exp \left[-y_{i} F_{k-1}\left(x_{i}\right)-y_{i} \alpha_{k} f_{k}\left(x_{i}\right)\right] \\ &=\sum_{i=1}^{m} \exp \left[-y_{i} F_{k-1}\left(x_{i}\right)\right] \exp \left[-y_{i} \alpha_{k} f_{k}\left(x_{i}\right)\right] \end{aligned}$

其中，上一步中的$F_{k-1}$已知，所以令$w_{k,i}=exp(-y_{i}F_{k-1}(x_{i}))$。将上一步的损失作为这一步的权重。每一轮迭代时的损失函数变为：

$L(y, F(x))=\sum_{i=1}^{m} w_{k, i} \exp \left[-y_{i} \alpha_{k} f_{k}\left(x_{i}\right)\right]$

对$f_{k}(x)$求解，得：

$f_{k}(x)=\operatorname{argmin} \sum_{i=1}^{m} w_{k, i} I\left(y_{i} \neq f_{k}\left(x_{i}\right)\right)$

带入损失函数，并对$\alpha$求导，得：

$\alpha_{k}=\frac{1}{2} \log \frac{1-e_{k}}{e_{k}}$

其中，$e_{k}$为前面的分类误差率：

$e_{k}=\frac{\sum_{i=1}^{m} w_{k i}^{\prime} I\left(y_{i} \neq f_{k}\left(x_{i}\right)\right)}{\sum_{i=1}^{m} w_{k i}^{\prime}}=\sum_{i=1}^{m} w_{k i} I\left(y_{i} \neq f_{k}\left(x_{i}\right)\right)$

根据之前公式，样本权重的更新公式为：

$w_{k+1, i}=w_{k i} \exp \left[-y_{i} \alpha_{k} f_{k}\left(x_{i}\right)\right]$

3.3 正则化

对于目标函数，为了防止过拟合，加入正则化：

$F_{k}(x)=F_{k-1}(x)+\mu \alpha_{k} f_{k}(x)$

通过$\mu$来控制迭代的次数，通常来说，较小的$/mu$意味着需要更多的弱学习器的迭代次数。

3.4 优缺点

优点

• 分类精度高
• 可以用各种分类模型构建弱学习器，灵活
• 不易过拟合

缺点

• 对异常点敏感，异常点会获得较高的权重

4 GBDT

GBDT（Gradient Boosting Decision Tree）是一种迭代的决策树算法，该算法由多棵决策树组成，属于 Boosting 策略。

4.1 基本过程

4.1 概述

GBDT（Gradient Boosting Decision Tree）是一种迭代的决策树算法，该算法由多棵决策树组成，属于 Boosting 策略。其中弱学习器限制了只能使用CART回归树，迭代思路与Adaboost也有所不同。GBDT每一轮迭代的目标是是最小化残差。比如有个人30岁，第一个学习器的输出是20岁，损失为10岁，后面的模型去拟合这个10岁。假设输出为6岁，那么此刻残差为4岁，模型继续拟合4岁。每一轮迭代，都使得损失变得更小。

GBDT的核心是累加所有树的结果作为最终结果，模型的最终预测值可以表示为：

$F_{k}(x)=\sum_{i=1}^{k} f_{i}(x)$

$f_{i}(x)$可以表示为基模型与其权重的乘积，模型的训练目标是使预测值$F_{k}(x)$逼近真实值y，因此每个基模型的预测值都要各自逼近要预测部分的真实值。对应的训练思路为：每次只训练一个基模型，整体的模型迭代公式为：

$F_{k}(x)=F_{k-1}(x)+f_{k}(x)$

在每一轮迭代中，只集中解决一个基模型的训练。

其中，GBDT中的树都是回归树，不是分类树。

因为对分类树来说，结果的加减没有意义。回归树结果的加减才有意义。

回归树在分枝时会穷举每一个特征的每一个阈值，以最小均方误差作为衡量标准，找到最好的分割点。

4.2 负梯度拟合

针对损失函数的拟合方法问题，GBDT采用了损失函数的负梯度来拟合本轮损失的近似值。

第t轮第i分样本的损失函数的负梯度表示为：

$r_{t i}=-\left[\frac{\left.\partial L\left(y_{i}, f\left(x_{i}\right)\right)\right)}{\partial f\left(x_{i}\right)}\right]_{f(x)=f_{t-1}(x)}$

由公式17，利用$(x_{i},r_{ti})$来拟合一颗CART回归树。针对每一个叶子结点里的样本，求出使损失函数最小，也就是拟合叶子节点最好的输出值$_{ctj}$:

$c_{t j}=\underbrace{\arg \min }_{c} \sum_{x_{i} \in R_{t j}} L\left(y_{i}, f_{t-1}\left(x_{i}\right)+c\right)$

其中$R_{tj}$为叶节点区域。

本轮的拟合函数为：

$h_{t}(x)=\sum_{j=1}^{J} c_{t j} I\left(x \in R_{t j}\right)$

通过损失函数的负梯度来拟合，我们找到了一种通用的拟合损失误差的办法，这样无轮是分类问题还是回归问题，我们通过其损失函数的负梯度的拟合，就可以用GBDT来解决我们的分类回归问题。区别仅仅在于损失函数不同导致的负梯度不同而已。

注意：只有当损失函数为均方误差时，负梯度刚好为残差

$-\frac{\partial\left(\frac{1}{2}\left(y-F_{k}(x)\right)^{2}\right)}{\partial F_{k}(x)}=y-F_{k}(x)$

拟合残差只是考虑到损失函数为平方损失的特殊情况，负梯度是更加广义上的拟合项，更具普适性。

4.3 损失函数

常见的损失函数为：

• 均方误差

  常用损失，但对异常点比较敏感

  $L(y, f(x))=(y-f(x))^{2}$

• 绝对损失

  $L(y, f(x))=|y-f(x)|$

  负梯度误差为：

  $\operatorname{sign}\left(y_{i}-f\left(x_{i}\right)\right)$

• Huber损失

  均方误差和绝对损失的折中产物，相比均方误差能更好的处理异常点

  $L(y, f(x))=\left\{\begin{aligned} \frac{1}{2}(y-f(x))^{2} &|y-f(x) \leq \delta| \\ \delta\left(|y-f(x)|-\frac{\delta}{2}\right) &|y-f(x)>\delta| \end{aligned}\right.$

• 分位数损失

  比较少见，对应分位数回归的损失函数，主要目的还是减少异常点对模型的影响

  $r\left(y_{i}, f\left(x_{i}\right)\right)=\left\{\begin{aligned} \theta & y_{i} \geq f\left(x_{i}\right) \\ \theta-1 & y_{i}<f\left(x_{i}\right) \end{aligned}\right.$

4.4 算法流程

4.4.1 回归

训练集样本T：$T=\left\{\left(x, y_{1}\right),\left(x_{2}, y_{2}\right), \ldots\left(x_{m}, y_{m}\right)\right\}$

最大迭代次数：T

损失函数：L

1. 初始化弱学习器

   $f_{0}(x)=\underbrace{\operatorname{argmin}}_{c} \sum_{i=1}^{m} L\left(y_{i}, c\right)$

2. 对迭代轮数t=1,2,..T,

   1. 对于样本i=1,2,..,m 计算负梯度

      $r_{t i}=-\left[\frac{\left.\partial L\left(y_{i}, f\left(x_{i}\right)\right)\right)}{\partial f\left(x_{i}\right)}\right]_{f(x)=f_{t-1}(x)}$

   2. 利用$(x_i,r_{ti})$，拟合一颗CART回归树，对应的叶子节点区域为$R_{tj},j=1,2,...,J$,为回归树t的叶子结点的个数。

   3. 对于叶子区域$j=1,2,3...,J$，计算最佳拟合值

      $c_{t j}=\underbrace{\arg \min }_{c} \sum_{x_{i} \in R_{t j}} L\left(y_{i}, f_{t-1}\left(x_{i}\right)+c\right)$

   4. 更新强学习器

      $f_{t}(x)=f_{t-1}(x)+\sum_{j=1}^{J} c_{t j} I\left(x \in R_{t j}\right)$

3. 最终强学习器

   $f(x)=f_{T}(x)=f_{0}(x)+\sum_{t=1}^{T} \sum_{j=1}^{J} c_{t j} I\left(x \in R_{t j}\right)$

4.4.2 分类

为了解决分类输出不是连续值的问题，主要有两个方法，一个是用指数损失函数，此时GBDT退化为Adaboost算法。另一种方法是用类似于逻辑回归的对数似然损失函数的方法。也就是说，我们用的是类别的预测概率值和真实概率值的差来拟合损失。本文仅讨论用对数似然损失函数的GBDT分类。而对于对数似然损失函数，我们又有二元分类和多元分类的区别。

4.4.2.1 二元GBDT分类

损失函数改为对数似然损失函数：

$L(y, f(x))=\log (1+\exp (-y f(x)))$

此时的负梯度误差为:

$r_{t i}=-\left[\frac{\left.\partial L\left(y, f\left(x_{i}\right)\right)\right)}{\partial f\left(x_{i}\right)}\right]_{f(x)=f_{t-1}(x)}=y_{i} /\left(1+\exp \left(y_{i} f\left(x_{i}\right)\right)\right)$

叶子节点的最佳拟合值：

$c_{t j}=\underbrace{\arg \min }_{c} \sum_{x_{i} \in R_{t j}} \log \left(1+\exp \left(-y_{i}\left(f_{t-1}\left(x_{i}\right)+c\right)\right)\right)$

因为较难优化，使用近似值替代：

$c_{t j}=\sum_{x_{i} \in R_{t j}} r_{t i} / \sum_{x_{i} \in R_{t j}}\left|r_{t i}\right|\left(1-\left|r_{t i}\right|\right)$

4.4.2.2 多元GBDT分类

假设类别数为K，对数似然损失函数为：

$L(y, f(x))=-\sum_{k=1}^{K} y_{k} \log p_{k}(x)$

第k类的概率$p_k(x)$的表达式为：

$p_{k}(x)=\exp \left(f_{k}(x)\right) / \sum_{l=1}^{K} \exp \left(f_{l}(x)\right)$

对应的负梯度误差：

$r_{t i l}=-\left[\frac{\left.\partial L\left(y_{i}, f\left(x_{i}\right)\right)\right)}{\partial f\left(x_{i}\right)}\right]_{f_{k}(x)=f l, t-1(x)}=y_{i l}-p_{l, t-1}\left(x_{i}\right)$

这里的误差就是样本𝑖i对应类别𝑙l的真实概率和𝑡−1t−1轮预测概率的差值。

叶子节点最佳拟合值：

$c_{t j l}=\underbrace{\arg \min }_{c_{j l}} \sum_{i=0}^{m} \sum_{k=1}^{K} L\left(y_{k}, f_{t-1, l}(x)+\sum_{j=0}^{J} c_{j l} I\left(x_{i} \in R_{t j l}\right)\right)$

近似值替代：

$c_{t j l}=\frac{K-1}{K} \frac{\sum_{x_{i} \in R_{t j l}} r_{t i l}}{\sum_{x_{i} \in R_{t i l}}\left|r_{t i l}\right|\left(1-\left|r_{t i l}\right|\right)}$

4.5 正则化

GBDT正则化有三种方式

• Shrinkage

  对每一棵树设置一个权重，类似learning rate，通过权重的变化，增加弱学习器的迭代次数。

  $F_{i}(x)=F_{i-1}(x)+\mu f_{i}(x) \quad(0<\mu \leq 1)$

• 子采样

  取值为(0,1]。注意这里的子采样和随机森林不一样，随机森林使用的是放回抽样，而这里是不放回抽样。如果取值为1，则全部样本都使用，等于没有使用子采样。如果取值小于1，则只有一部分样本会去做GBDT的决策树拟合。选择小于1的比例可以减少方差，即防止过拟合，但是会增加样本拟合的偏差，因此取值不能太低。推荐在[0.5, 0.8]之间。

• 剪枝

  对CART树进行正则化剪枝

4.6 优缺点

优点：

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

缺点：

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

4.7 对比Adaboost

相同：

• 都属于boosting家族，使用弱分类器
• 使用前向分布算法

不同：

• 迭代思路不同。Adaboost通过提升错分的数据点的权重来弥补模型不足；GBDT通过计算梯度来提升模型。

参考资料

决策树（中）——Random Forest、Adaboost、GBDT

[梯度提升树(GBDT)原理小结](https://www.cnblogs.com/pinard/p/6140514.html)