失眠网 > 【机器学习】树及其组合算法（二）（Bagging Boosting GBDT XGboost Adaboost 随机森林）

【机器学习】树及其组合算法（二）（Bagging Boosting GBDT XGboost Adaboost 随机森林）

时间：2024-07-18 13:18:30

树及其组合算法二：Bagging

1集成学习1.1集成学习概述1.2集成学习的原理2 Bagging2.1 Bagging的建模2.2 Bagging的预测2.3 Bagging测试误差的估计2.4 Bagging袋装法的缺点3 随机森林3.1随机森林降低树间相似性的基本策略：3.2随机森林建模过程4 AdaBoost5 GBDT5.1提升树5.2梯度提升算法5.3GBDT算法用于分类6 XGBoost

树及其组合算法部分其余内容，个人笔记博客传送门

树及其组合算法一：决策树

决策树有一种“天然”的高方差特征，解决预测高方差问题的一般方法是集成学习(Ensemble Learning)。

1集成学习

1.1集成学习概述

集成学习的基本思路为：

①建模阶段：基于一组独立的训练集，分别建立与之对应的一组回归或分类预测模型，称这里的每个预测模型为基础学习器

②预测阶段：基础学习器将分别给出各自的预测结果，对各预测结果进行平均(回归模型)或投票(分类模型)，确定最终的预测结果。

集成学习的特点：

基础学习器通常由一个现有的学习算法从训练数据产生，例如，C4.5决策树算法、BP神经网络算法等，此时集成中只包含同种类型的基础学习器，例如“决策树集成”中全是决策树，“神经网络集成”中全是神经网络，这样的集成是“同质”的。

要获得好的集成，基础学习器应该“好而不同”，即基础学习器要有一定的“准确性”并且要有“多样性”。

集成学习方法大致分为两类：

基础学习器之间存在强依赖关系、必须串行生成的序列化方法，代表是Boosting。基础学习器之间不存在强依赖关系，可同时生成的并行化方法，代表是Bagging和“随机森林”。

集成学习的优势为：

解决预测模型的高方差问题将一组弱模型联合起来使其成为一个强模型。

1.2集成学习的原理

（1）解决预测模型的高方差问题

集成学习认为：

若能够基于来自同一总体的B个独立的训练集，建立B个基础学习器得到对X0X_0X0的B个回归预测值f^(1)(X0)，f^(2)(X0)，...，f^(B)(X0)\hat{f}^{(1)(X_0)}，\hat{f}^{(2)(X_0)}，...，\hat{f}^{(B)(X_0)}f^(1)(X0)，f^(2)(X0)，...，f^(B)(X0)，若其方差等于σ2\sigma^2σ2则B个回归预测值的平均值f^avg(X0)=1B∑b=1Bf^(b)(X0)\hat{f}_{avg}(X_0)=\frac{1}{B}\sum_{b=1}^{B}\hat{f}^{(b)}(X_0)f^avg(X0)=B1∑b=1Bf^(b)(X0)，其方差降到σ2/B\sigma^2/Bσ2/B。这里的B个预测模型彼此独立。同时这B个独立的训练集无法直接获得通常需要模拟生成，并由此建立B个独立的基础学习器，得到对X0X_0X0的B个回归预测值。

模拟生成B个独立训练集的常见策略：

重抽样自举法(Bootstrap)，给定一个样本量为N的数据集D，有放回地从中随机抽取N个样本，重复B次，得到B组独立的训练集，每组训练集中共有N个样本。称Sb∗(b=1,2,...,B)S_b^{*}(b=1,2,...,B)Sb∗(b=1,2,...,B)为一个自举样本，B为自举次数。

当N较大时N次均未抽中的概率为(1−1N)N≈1e=0.368(1-\frac{1}{N})^{N}\approx \frac{1}{e}=0.368(1−N1)N≈e1=0.368，这也意味着大约有0.368的样本不会进入最后样本，因此，重抽样自举法也被称为0.632自举法。

基于重抽样自举地常见集成学习方法：

袋装法（Bagging）和随机森林（Random Forest）

（2）从弱模型到强模型地构建

复杂模型导致高方差以及模型过拟合。集成学习将一组弱模型（基础学习器）组成一个“联合委员会”并最终称为强模型。弱模型一般指比随机猜测的误差略低的模型

例如，回归预测中：

B个弱模型对X0X_0X0地回归预测值分别为：f^∗(1)(X0)，f^∗(2)(X0)，...，f^∗(B)(X0)\hat{f}^{*(1)}(X_0)，\hat{f}^{*(2)}(X_0)，...，\hat{f}^{*(B)}(X_0)f^∗(1)(X0)，f^∗(2)(X0)，...，f^∗(B)(X0)

“联合委员会”的联合预测结果：f^α∗(X0)=α1f^∗(1)(X0)+α2f^∗(2)(X0)+...+αBf^∗(B)(X0)\hat{f}_{\alpha}^{*}(X_0)=\alpha_1 \hat{f}^{*(1)}(X_0)+\alpha_2 \hat{f}^{*(2)}(X_0)+...+\alpha_B \hat{f}^{*(B)(X_0)}f^α∗(X0)=α1f^∗(1)(X0)+α2f^∗(2)(X0)+...+αBf^∗(B)(X0)，其中αb(b=1,2,...,B)\alpha_b(b=1,2,...,B)αb(b=1,2,...,B)为模型权重。

从弱模型到强模型的常见的集成学习法：

提升法（Boosting），梯度提升树，这里的B个弱模型具有顺序相关性

2 Bagging

Bagging （bootstrap aggregating）又称袋装法，是集成学习算法中的一种。

2.1 Bagging的建模

训练B个基础学习器通常基础学习器是训练误差较低的相对复杂的模型，例如回归树或分类树。

2.2 Bagging的预测

T^∗(b)\hat{T}^{*(b)}T^∗(b)表示第bbb棵树，T^∗(b)(X0)\hat{T}^{*(b)}(X_0)T^∗(b)(X0)表示第bbb棵树对输入变量X0X_0X0的预测。

那么，回归树中，Bagging袋装预测值为bbb棵树的预测平均值：

f^bag∗(X0)=1B∑b=1BT^∗(b)(X0)\hat{f}_{bag}^{*}(X_0)=\frac{1}{B}\sum_{b=1}^{B}\hat{T}^{*(b)}(X_0)f^bag∗(X0)=B1b=1∑BT^∗(b)(X0)

K分类预测中，Bagging袋装预测值为占比法，计算预测X0X_0X0属于第kkk类的分类树的占比，占比最高的类别为最终X0X_0X0的预测值。

f^bag∗(X0)=arg⁡max⁡kPk(X0)\hat{f}_{bag}^{*}(X_0)=\arg \max_{k} P_{k}(X_0)f^bag∗(X0)=argkmaxPk(X0)

2.3 Bagging测试误差的估计

基于OOB（out of bag）袋外观测的估计，第bbb棵决策树的袋外观测是没有出现在这棵树测训练数据集Sb∗S_b^*Sb∗内的样本观测。

原样本数据集D中共有N个样本，Sb∗S_b^*Sb∗是从D中有放回随机抽取的训练数据集，样本大小也为N，用于构造第bbb棵决策树。对于原样本集D中的每个样本Xi(i=1,2,...N)X_i(i=1,2,...N)Xi(i=1,2,...N)，得到其作为袋外观测OOB时基础学习器的预测结果。

具体是如何得到XiX_iXi作为OOB的Bagging预测值呢？

若XiX_iXi在建模过程中有q(q<B)q(q<B)q(q<B)次作为OOB观测，也即有qqq棵决策树的建模过程中没有用到XiX_iXi这个样本，那么只有这qqq个基础学习器提供预测值，最终Bagging的预测结果是这q个预测值的平均或投票。

2.4 Bagging袋装法的缺点

袋装法降低预测方差的基本理论是：

来自同一总体的、方差等于σ2\sigma^2σ2的B个预测值T^∗(b)(X0)\hat{T}^{*(b)}(X_0)T^∗(b)(X0)，假设这B个预测值彼此独立，因此取其均值f^bag∗(X0)\hat{f}_{bag}^{*}(X_0)f^bag∗(X0)的方差降至σ2/B\sigma^2/Bσ2/B

但是：

独立的假设条件在实际情况中是很难实现的，因为树是相似的，即先选某个特征xix_ixi进行分支，再选某个特征xjx_jxj进行分支，这些划分点的选取以及顺序都是类似的，因此树的形状会很相似。

Var(Zˉ)=var(1N∑i=1NZi)=1N2[Nσ2+N(N−1)ρσ2]=σ2+(N−1)ρσ2N=ρσ2+1−ρNσ2\begin{aligned} Var(\bar{Z})&=var(\frac{1}{N}\sum_{i=1}^{N}Z_i)\\ &=\frac{1}{N^2}[N\sigma^2+N(N-1)\rho \sigma^2]\\ &=\frac{\sigma^2+(N-1)\rho \sigma^2}{N}\\ &=\rho \sigma^2+\frac{1-\rho}{N}\sigma^2 \end{aligned} Var(Zˉ)=var(N1i=1∑NZi)=N21[Nσ2+N(N−1)ρσ2]=Nσ2+(N−1)ρσ2=ρσ2+N1−ρσ2

若满足彼此独立的条件，则ρ=0\rho=0ρ=0，var(Zˉ)=σ2Nvar(\bar{Z})=\frac{\sigma^2}{N}var(Zˉ)=Nσ2；若不满足彼此独立的条件，即ρ≠0\rho \neq 0ρ=0，var(Zˉ)var(\bar{Z})var(Zˉ)有以上两项。

3 随机森林

用随机方式建立包含多棵决策树的森林。每棵树都是一个基础学习器，“整片”森林对应集成学习。通过随机方式使每棵树的“外观”因彼此“看上去不相同”而不相关。随机森林通过减少预测相关性，即通过降低树间的相似性(高相似的决策树给出高相关的预测值)的策略降低方差。

3.1随机森林降低树间相似性的基本策略：

对训练数据增加随机性扰动：重抽样自举法。对输入变量增加随机性扰动：决策树建立过程中的当前“最佳”分组变量，是来自输入变量的一个随机子集中的变量。

3.2随机森林建模过程

进行b=1,2,...,Bb=1,2,...,Bb=1,2,...,B次如下迭代，得到包括B棵树的随机森林：

①对样本量等于N的数据集进行重抽样自举，得到自举样本Sb∗S_b^{*}Sb∗

②基于自举样本Sb∗S_b^{*}Sb∗建立树T^∗b\hat{T}^{*b}T^∗b。树从根节点开始按如下方式不断生长，直到满足树的预修剪参数为止：对于决策树的每个节点，先从该节点的属性集合中随机选择一个包含k个属性的子集，然后再从这个子集中选择一个最优属性用于划分。

这里代表子集的大小的参数kkk控制了随机性的引入程度，若令k=dk=dk=d，则基决策树的构建与传统决策树相同，若令k=1k=1k=1，则是随机选择一个属性用于划分；一般情况下，k=[log⁡2d]k=[\log_2 d]k=[log2d]或者k=[d]k=[\sqrt{d}]k=[d]，其中ddd表示原数据集中总的特征属性的个数。

4 AdaBoost

Boosting是一种可以将弱模型提升为强模型的算法。这一类算法的核心类似于：先从初始训练集训练出一个基础学习器，再根据基础学习器的表现对训练样本的分布进行调整，使得先前的基础学习器中预测错误的训练样本再后续得到更多关注，然后基于调整后的样本分布来训练下一个基础学习器；重复操作直至得到一定个数T的基础学习器，将T个基础学习器的预测结果进行加权平均。
周志华《机器学习》

提升法的经典是AdaBoost(Adaptive Boosting)适应性提升法，提出时主要针对二分类预测问题，分类标签为-1和+1两个类别。AdaBoost算法中涉及两个权重：样本的分布，即迭代更新后第b个模型使用的N个样本的分布w(b)=[w1(b),w2(b)，...wN(b)]w^{(b)}=[w_1^{(b)},w_2^{(b)}，...w_N^{(b)}]w(b)=[w1(b),w2(b)，...wN(b)]和第b个弱模型的权重αb\alpha_bαb。适应性提升的表现：基于w(b−1)w^{(b-1)}w(b−1)得到w(b)w^{(b)}w(b)

对于提升方法来说，有两个问题需要回答，AdaBoost有对应的做法：
李航《统计学习方法》

1.在每一轮迭代时如何改变训练数据的权值或概率分布

AdaBoost的做法是，提高那些被前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值。

2.如何将弱分类器组合成一个强分类器

AdaBoost采取加权多数表决的方法，具体地加大分类误差率小地弱分类器的权值，使其在表决中起较大的作用；减小分类误差率大的弱分类器的权值，使其在表决中起较小作用。

AdaBoost算法具体步骤：

每个样本观测在每次迭代中都有自己的权重w(b)=[w1(b)，w2(b)，...，wN(b)]w^{(b)}=[w_1^{(b)}，w_2^{(b)}，...，w_N^{(b)}]w(b)=[w1(b)，w2(b)，...，wN(b)]

初始化：w(1)=[1N，1N，...，1N]w^{(1)}=[\frac{1}{N}，\frac{1}{N}，...，\frac{1}{N}]w(1)=[N1，N1，...，N1]，给定需要的弱分类器个数BBB

第一次迭代：

①基于权重w(1)w^{(1)}w(1)对原始数据集S（数据量为N）进行加权有放回的随机抽样得到训练集S1S_1S1（数据量为N），根据S1S_1S1数据集得到弱模型G1(X)G_1(X)G1(X)。

②计算弱模型G1(X)G_1(X)G1(X)的训练误差：err(1)=∑i=1NP(yi≠G1(Xi))=∑i=1Nwi(1)I(yi≠G1(Xi))err^{(1)}=\sum_{i=1}^{N} P(y_i\ne G_1(X_i))=\sum_{i=1}^{N} w_i^{(1)}I(y_i\ne G_1(X_i))err(1)=∑i=1NP(yi=G1(Xi))=∑i=1Nwi(1)I(yi=G1(Xi))

③计算G1(X)G_1(X)G1(X)模型权重α1=12ln⁡(1−err(1)err(1))\alpha_1=\frac{1}{2}\ln (\frac{1-err^{(1)}}{err^{(1)}})α1=21ln(err(1)1−err(1))

④更新w(2)w^{(2)}w(2)得到：wi(2)=wi(1)exp(−α1yiG1(Xi))Z1w_i^{(2)}=\frac{w_i^{(1)}exp(-\alpha_1y_iG_1(X_i))}{Z_1}wi(2)=Z1wi(1)exp(−α1yiG1(Xi))，i=1,2,...,Ni=1,2,...,Ni=1,2,...,N,Z1=∑iwi(1)exp(−α1yiG1(Xi))Z_1=\sum_i w_i^{(1)}exp(-\alpha_1y_iG_1(X_i))Z1=∑iwi(1)exp(−α1yiG1(Xi)),这里Z1Z_1Z1是规范因子，它使得w(2)=[w1(2),w2(2),...,wN(2)]w^{(2)}=[w_1^{(2)},w_2^{(2)},...,w_N^{(2)}]w(2)=[w1(2),w2(2),...,wN(2)]是一个概率分布。

第二次迭代：

根据上一轮更新的训练集分布w(2)w^{(2)}w(2)对原数据集S进行加权有放回的随机抽样，得到训练集S2S_2S2，基于S2S_2S2训练集得到相应的弱模型G2(X)G_2(X)G2(X)。注意到这里G1(X)G_1(X)G1(X)模型预测错误的样本有更大的概率进入训练集S2S_2S2，同时注意到模型G2(X)G_2(X)G2(X)关注的是G1(X)G_1(X)G1(X)没有正确预测的部分样本。

计算G2(X)G_2(X)G2(X)模型的训练误差err(2)err^{(2)}err(2)和模型权重α2\alpha_2α2，并根据α2\alpha_2α2和w(2)w^{(2)}w(2)得到的更新的w(3)w^{(3)}w(3)。

第三次迭代至第BBB次迭代同理。

最终强模型预测结果为G(X)=sign(∑b=1Bαb∗Gb(X))G(X)=sign(\sum_{b=1}^{B} \alpha_b*G_b(X))G(X)=sign(∑b=1Bαb∗Gb(X))

这里αb\alpha_bαb表示了基础学习器Gb(X)G_b(X)Gb(X)的重要性，αb\alpha_bαb之和并不为1.

AdaBoost算法的特点

不改变所给的训练数据，而不断改变训练数据权值的分布，使得训练数据在基本分类器的学习中起不同的作用。利用基础学习器的线性组合构建最终分类器。

AdaBoost算法还有另一个解释，即可认为AdaBoost算法是模型为加法模型、损失函数为指数函数、学习算法为前向分步算法的二分类学习方法。
李航《统计学习方法》

这里的指数损失函数为L(y，G(x))=exp(−y∗G(x))L(y，G(x))=exp(-y*G(x))L(y，G(x))=exp(−y∗G(x))

5 GBDT

补充内容：
梯度：在微积分中对多元函数的参数求偏导，将所有参数的偏导结果写成向量形式就是梯度，如∂f(w)∂w\frac{\partial f(w)}{\partial w}∂w∂f(w)。
梯度的几何意义：梯度就是函数在某点变化最快的地方。沿着梯度的方向，是函数增加最快的方向，更容易找到函数的最大值；反过来，沿着梯度的反方向，函数下降最快，更容易找到函数的最小值。
梯度下降算法：沿着梯度的负方向调整。

5.1提升树

提升树是以分类树或回归树为基础学习器的提升方法。针对不同问题的提升树算法，其主要区别在于使用的损失函数不同，包括使用平方误差损失函数的回归问题，用指数损失函数的分类问题，以及用一般损失函数的一般问题。

对于二分类问题，只需要将AdaBoost算法中的基础学习器限制为二类分类树即可，AdaBoost算法原理是基于指数损失函数实现的，并且AdaBoost算法适用于标签为+1，-1的二分类问题。

对于回归问题，现在先考虑回归提升树（李航《统计学习方法》）。

当损失函数采用平方误差损失函数时，构建新的基础学习器时相当于，拟合之前所有模型加和与真实值之间的差值即残差。

5.2梯度提升算法

当损失函数为平方误差损失函数和指数损失函数时，每一步的优化过程是很简单的，但是，对一般损失函数而言，每一步的优化并不那么容易。于是，Freidman提出了梯度提升算法，利用最速下降的近似方法，求一般损失函数的最小值(李航《统计学习方法》)。

GBDT(Gradient Boosted Decision Trees)梯度提升树的核心是：每一棵树学习的都是之前所有树的预测值之和的残差值。这个残差值加上所有树的预测值和正好等于真实值。GBDT算法限制了基础学习器为CART回归树。

注：

算法初始化部分，估计得到使损失函数极小化的常数值，它是只有一个根节点的树。

第2（a）计算损失函数的负梯度在当前模型的值，作为残差的估计。对于平方损失函数它就是通常所说的残差，对于一般损失函数，它就是残差的近似值。

第2（b）估计回归树叶节点区域，拟合残差的近似值，即把(X,rmir_{mi}rmi)作为训练数据训练回归树。

第2（c）步，利用线性搜索估计叶节点区域的值，使损失函数极小化。

第2（d）步，更新回归树。

5.3GBDT算法用于分类

这部分内容摘自相关参考资料中的第5条。
重要：GBDT每次使用全样本

GBDT梯度提升树算法本身是用于CART回归树，这是因为回归树中输出的值是连续的值，损失函数是可导的，但GBDT经过调整也能用于分类。第一种思路是，损失函数定为指数损失函数，这种情况下，GBDT算法退化为AdaBoost；第二种思路是使用类似逻辑回归的对数似然损失函数。重点是对损失函数的调整。

二元GBDT分类算法中，损失函数为L(y,f(x))=log⁡(1+exp⁡(−y∗f(x)))L(y,f(x))=\log (1+\exp(-y*f(x)))L(y,f(x))=log(1+exp(−y∗f(x)))，这里y∈{+1,−1}y\in \{+1,-1\}y∈{+1,−1}多元GBDT分类算法中，损失函数为L(y,f(x))=−∑k=1Kyklog⁡pk(x)L(y,f(x))=-\sum_{k=1}^K y_k \log p_k(x)L(y,f(x))=−k=1∑Kyklogpk(x)

pk(x)=exp(fk(x))∑l=1Kexp(fl(x))p_k(x)=\frac{exp(f_k(x))}{\sum_{l=1}^K exp(f_l(x))}pk(x)=∑l=1Kexp(fl(x))exp(fk(x))