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

树及其组合算法二:Bagging


树及其组合算法部分其余内容,个人笔记博客传送门
树及其组合算法一:决策树

基本知识介绍

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

1集成学习

1.1集成学习概述

集成学习的基本思路为:
①建模阶段:基于一组独立的训练集,分别建立与之对应的一组回归或分类预测模型,称这里的每个预测模型为基础学习器
②预测阶段:基础学习器将分别给出各自的预测结果,对各预测结果进行平均(回归模型)或投票(分类模型),确定最终的预测结果。

集成学习的特点:
基础学习器通常由一个现有的学习算法从训练数据产生,例如,C4.5决策树算法、BP神经网络算法等,此时集成中只包含同种类型的基础学习器,例如“决策树集成”中全是决策树,“神经网络集成”中全是神经网络,这样的集成是“同质”的。
要获得好的集成,基础学习器应该“好而不同”,即基础学习器要有一定的“准确性”并且要有“多样性”。

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

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

集成学习的优势为:

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

1.2集成学习的原理

  • (1)解决预测模型的高方差问题

集成学习认为:
若能够基于来自同一总体的B个独立的训练集,建立B个基础学习器得到对 X 0 X_0 X0​的B个回归预测值 f ^ ( 1 ) ( X 0 ) , f ^ ( 2 ) ( X 0 ) , . . . , f ^ ( B ) ( X 0 ) \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 ^ a v g ( X 0 ) = 1 B ∑ b = 1 B f ^ ( b ) ( X 0 ) \hat{f}_{avg}(X_0)=\frac{1}{B}\sum_{b=1}^{B}\hat{f}^{(b)}(X_0) f^​avg​(X0​)=B1​∑b=1B​f^​(b)(X0​),其方差降到 σ 2 / B \sigma^2/B σ2/B。这里的B个预测模型彼此独立。同时这B个独立的训练集无法直接获得通常需要模拟生成,并由此建立B个独立的基础学习器,得到对 X 0 X_0 X0​的B个回归预测值。

模拟生成B个独立训练集的常见策略:
重抽样自举法(Bootstrap),给定一个样本量为N的数据集D,有放回地从中随机抽取N个样本,重复B次,得到B组独立的训练集,每组训练集*有N个样本。称 S b ∗ ( b = 1 , 2 , . . . , B ) S_b^{*}(b=1,2,...,B) Sb∗​(b=1,2,...,B)为一个自举样本,B为自举次数。
当N较大时N次均未抽中的概率为 ( 1 − 1 N ) N ≈ 1 e = 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个弱模型对 X 0 X_0 X0​地回归预测值分别为: f ^ ∗ ( 1 ) ( X 0 ) , f ^ ∗ ( 2 ) ( X 0 ) , . . . , f ^ ∗ ( B ) ( X 0 ) \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 ^ α ∗ ( X 0 ) = α 1 f ^ ∗ ( 1 ) ( X 0 ) + α 2 f ^ ∗ ( 2 ) ( X 0 ) + . . . + α B f ^ ∗ ( B ) ( X 0 ) \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​)=α1​f^​∗(1)(X0​)+α2​f^​∗(2)(X0​)+...+αB​f^​∗(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)表示第 b b b棵树, T ^ ∗ ( b ) ( X 0 ) \hat{T}^{*(b)}(X_0) T^∗(b)(X0​)表示第 b b b棵树对输入变量 X 0 X_0 X0​的预测。
那么,回归树中,Bagging袋装预测值为 b b b棵树的预测平均值
f ^ b a g ∗ ( X 0 ) = 1 B ∑ b = 1 B T ^ ∗ ( b ) ( X 0 ) \hat{f}_{bag}^{*}(X_0)=\frac{1}{B}\sum_{b=1}^{B}\hat{T}^{*(b)}(X_0) f^​bag∗​(X0​)=B1​b=1∑B​T^∗(b)(X0​)
K分类预测中,Bagging袋装预测值为占比法,计算预测 X 0 X_0 X0​属于第 k k k类的分类树的占比,占比最高的类别为最终 X 0 X_0 X0​的预测值。
f ^ b a g ∗ ( X 0 ) = arg ⁡ max ⁡ k P k ( X 0 ) \hat{f}_{bag}^{*}(X_0)=\arg \max_{k} P_{k}(X_0) f^​bag∗​(X0​)=argkmax​Pk​(X0​)

2.3 Bagging测试误差的估计

基于OOB(out of bag)袋外观测的估计,第 b b b棵决策树的袋外观测是没有出现在这棵树测训练数据集 S b ∗ S_b^* Sb∗​内的样本观测。

原样本数据集D*有N个样本, S b ∗ S_b^* Sb∗​是从D中有放回随机抽取的训练数据集,样本大小也为N,用于构造第 b b b棵决策树。对于原样本集D中的每个样本 X i ( i = 1 , 2 , . . . N ) X_i(i=1,2,...N) Xi​(i=1,2,...N),得到其作为袋外观测OOB时基础学习器的预测结果。
具体是如何得到 X i X_i Xi​作为OOB的Bagging预测值呢?
若 X i X_i Xi​在建模过程中有 q ( q < B ) q(q<B) q(q<B)次作为OOB观测,也即有 q q q棵决策树的建模过程中没有用到 X i X_i Xi​这个样本,那么只有这 q q q个基础学习器提供预测值,最终Bagging的预测结果是这q个预测值的平均或投票

2.4 Bagging袋装法的缺点

袋装法降低预测方差的基本理论是:
来自同一总体的、方差等于 σ 2 \sigma^2 σ2的B个预测值 T ^ ∗ ( b ) ( X 0 ) \hat{T}^{*(b)}(X_0) T^∗(b)(X0​),假设这B个预测值彼此独立,因此取其均值 f ^ b a g ∗ ( X 0 ) \hat{f}_{bag}^{*}(X_0) f^​bag∗​(X0​)的方差降至 σ 2 / B \sigma^2/B σ2/B

但是:
独立的假设条件在实际情况中是很难实现的,因为树是相似的,即先选某个特征 x i x_i xi​进行分支,再选某个特征 x j x_j xj​进行分支,这些划分点的选取以及顺序都是类似的,因此树的形状会很相似。
V a r ( Z ˉ ) = v a r ( 1 N ∑ i = 1 N Z i ) = 1 N 2 [ N σ 2 + N ( N − 1 ) ρ σ 2 ] = σ 2 + ( N − 1 ) ρ σ 2 N = ρ σ 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(N1​i=1∑N​Zi​)=N21​[Nσ2+N(N−1)ρσ2]=Nσ2+(N−1)ρσ2​=ρσ2+N1−ρ​σ2​
若满足彼此独立的条件,则 ρ = 0 \rho=0 ρ=0, v a r ( Z ˉ ) = σ 2 N var(\bar{Z})=\frac{\sigma^2}{N} var(Zˉ)=Nσ2​;若不满足彼此独立的条件,即 ρ ≠ 0 \rho \neq 0 ρ​=0, v a r ( Z ˉ ) var(\bar{Z}) var(Zˉ)有以上两项。

3 随机森林

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

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

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

3.2随机森林建模过程

进行 b = 1 , 2 , . . . , B b=1,2,...,B b=1,2,...,B次如下迭代,得到包括B棵树的随机森林:
①对样本量等于N的数据集进行重抽样自举,得到自举样本 S b ∗ S_b^{*} Sb∗​
②基于自举样本 S b ∗ S_b^{*} Sb∗​建立树 T ^ ∗ b \hat{T}^{*b} T^∗b。树从根节点开始按如下方式不断生长,直到满足树的预修剪参数为止:对于决策树的每个节点,先从该节点的属性集合中随机选择一个包含k个属性的子集,然后再从这个子集中选择一个最优属性用于划分

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

4 AdaBoost

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

提升法的经典是AdaBoost(Adaptive Boosting)适应性提升法,提出时主要针对二分类预测问题,分类标签为-1和+1两个类别。AdaBoost算法中涉及两个权重:样本的分布,即迭代更新后第b个模型使用的N个样本的分布 w ( b ) = [ w 1 ( b ) , w 2 ( b ) , . . . w N ( 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 ) = [ w 1 ( b ) , w 2 ( b ) , . . . , w N ( b ) ] w^{(b)}=[w_1^{(b)},w_2^{(b)},...,w_N^{(b)}] w(b)=[w1(b)​,w2(b)​,...,wN(b)​]
初始化: w ( 1 ) = [ 1 N , 1 N , . . . , 1 N ] w^{(1)}=[\frac{1}{N},\frac{1}{N},...,\frac{1}{N}] w(1)=[N1​,N1​,...,N1​],给定需要的弱分类器个数 B B B
第一次迭代:
①基于权重 w ( 1 ) w^{(1)} w(1)对原始数据集S(数据量为N)进行加权有放回的随机抽样得到训练集 S 1 S_1 S1​(数据量为N),根据 S 1 S_1 S1​数据集得到弱模型 G 1 ( X ) G_1(X) G1​(X)。
②计算弱模型 G 1 ( X ) G_1(X) G1​(X)的训练误差: e r r ( 1 ) = ∑ i = 1 N P ( y i ≠ G 1 ( X i ) ) = ∑ i = 1 N w i ( 1 ) I ( y i ≠ G 1 ( X i ) ) 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=1N​P(yi​​=G1​(Xi​))=∑i=1N​wi(1)​I(yi​​=G1​(Xi​))
③计算 G 1 ( X ) G_1(X) G1​(X)模型权重 α 1 = 1 2 ln ⁡ ( 1 − e r r ( 1 ) e r r ( 1 ) ) \alpha_1=\frac{1}{2}\ln (\frac{1-err^{(1)}}{err^{(1)}}) α1​=21​ln(err(1)1−err(1)​)
④更新 w ( 2 ) w^{(2)} w(2)得到: w i ( 2 ) = w i ( 1 ) e x p ( − α 1 y i G 1 ( X i ) ) Z 1 w_i^{(2)}=\frac{w_i^{(1)}exp(-\alpha_1y_iG_1(X_i))}{Z_1} wi(2)​=Z1​wi(1)​exp(−α1​yi​G1​(Xi​))​, i = 1 , 2 , . . . , N i=1,2,...,N i=1,2,...,N, Z 1 = ∑ i w i ( 1 ) e x p ( − α 1 y i G 1 ( X i ) ) Z_1=\sum_i w_i^{(1)}exp(-\alpha_1y_iG_1(X_i)) Z1​=∑i​wi(1)​exp(−α1​yi​G1​(Xi​)),这里 Z 1 Z_1 Z1​是规范因子,它使得 w ( 2 ) = [ w 1 ( 2 ) , w 2 ( 2 ) , . . . , w N ( 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进行加权有放回的随机抽样,得到训练集 S 2 S_2 S2​,基于 S 2 S_2 S2​训练集得到相应的弱模型 G 2 ( X ) G_2(X) G2​(X)。注意到这里 G 1 ( X ) G_1(X) G1​(X)模型预测错误的样本有更大的概率进入训练集 S 2 S_2 S2​,同时注意到模型 G 2 ( X ) G_2(X) G2​(X)关注的是 G 1 ( X ) G_1(X) G1​(X)没有正确预测的部分样本
计算 G 2 ( X ) G_2(X) G2​(X)模型的训练误差 e r r ( 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)。
第三次迭代至第 B B B次迭代同理。

最终强模型预测结果为 G ( X ) = s i g n ( ∑ b = 1 B α b ∗ G b ( 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​表示了基础学习器 G b ( X ) G_b(X) Gb​(X)的重要性, α b \alpha_b αb​之和并不为1.

AdaBoost算法的特点

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

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

这里的指数损失函数为 L ( y , G ( x ) ) = e x p ( − 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的二分类问题。

  • 对于回归问题,现在先考虑回归提升树(李航《统计学习方法》)。
    当损失函数采用 平方误差损失函数时,构建新的基础学习器时相当于,拟合之前所有模型加和与真实值之间的差值即残差。
    【机器学习】树及其组合算法(二)(Bagging,Boosting,GBDT,XGboost,Adaboost,随机森林)

5.2梯度提升算法

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

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

【机器学习】树及其组合算法(二)(Bagging,Boosting,GBDT,XGboost,Adaboost,随机森林)
注:
算法初始化部分,估计得到使损失函数极小化的常数值,它是只有一个根节点的树。
第2(a)计算损失函数的负梯度在当前模型的值,作为残差的估计。对于平方损失函数它就是通常所说的残差,对于一般损失函数,它就是残差的近似值。
第2(b)估计回归树叶节点区域,拟合残差的近似值,即把(X, r m i r_{mi} rmi​)作为训练数据训练回归树。
第2(c)步,利用线性搜索估计叶节点区域的值,使损失函数极小化。
第2(d)步,更新回归树。

5.3GBDT算法用于分类

这部分内容摘自相关参考资料中的第5条。

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 = 1 K y k log ⁡ p k ( x ) L(y,f(x))=-\sum_{k=1}^K y_k \log p_k(x) L(y,f(x))=−k=1∑K​yk​logpk​(x)
    p k ( x ) = e x p ( f k ( x ) ) ∑ l = 1 K e x p ( f l ( x ) ) p_k(x)=\frac{exp(f_k(x))}{\sum_{l=1}^K exp(f_l(x))} pk​(x)=∑l=1K​exp(fl​(x))exp(fk​(x))​
    【机器学习】树及其组合算法(二)(Bagging,Boosting,GBDT,XGboost,Adaboost,随机森林)

6 XGBoost

XGBoost(eXtreme Gradient Boosting),它所应用的算法就是Gradient Boosting Decision Trees,它是GB算法的高效实现,既可以用于分类问题中,又可以用于回归问题中。相比较于GBDT算法,在目标函数中加入了正则化项。

通俗理解kaggle比赛大杀器xgboost这一篇已经写的很好了,暂不赘述。。。

相关参考资料

1.有关梯度上升和梯度下降https://www.cnblogs.com/pinard/p/5970503.html
2.这一篇博客中有XGBoost的实例及代码实现Kaggle 神器 xgboost

3.重点参考GBDT算法原理以及实例理解
4.重点参考李航的书《统计学习方法》
5.这篇博客中提到了GBDT提升树用于分类梯度提升树(GBDT)原理小结
6.这一篇中有GBDT分类算法的原理(损失函数为逻辑回归的对数似然函数)深入理解GBDT二分类算法

7.https://www.cnblogs.com/mantch/p/11164221.html

上一篇:号外:友户通支持企业自有用户中心啦


下一篇:集成学习中的随机森林