【 GBDT算法】机器学习实例推导计算+公式详细过程（入门必备）

深藏阁楼爱情的钟 2022-04-04 11:20 669阅读 0赞

> > > > # 机器学习 【 GBDT算法】 #

知识准备：  
arg 是变元（即自变量argument）的英文缩写。  
arg min 就是使后面这个式子达到最小值时的变量的取值  
arg max 就是使后面这个式子达到最大值时的变量的取值  
例如 函数F(x,y):  
arg min F(x,y)就是指当F(x,y)取得最小值时，变量x,y的取值  
arg max F(x,y)就是指当F(x,y)取得最大值时，变量x,y的取值

## 一．GBDT概念： ##

GBDT(Gradient Boosting Decision Tree) 又叫 MART （Multiple Additive Regression Tree)，是一种迭代的决策树算法。由多棵决策树组成，最后把所有树的结论累加起来做决策。它是一个泛化能力较强的算法。GBDT里有三个概念：分别是Regression Decistion Tree、Gradient Boosting、Shrinkage。

#### 1． GB–Gradient Boosting 梯度提升树： ####

###### （1）错误思想：求均值就是GBDT。 ######

用三颗决策树预测一个人身高时，决策棵1预测为是1.7米，决策树2预测是1.75米，决策树3预测是1.8米。然后1.7 + 1.75 + 1.8 求均值，这样是不对的。因为只要训练集不变，独立训练三次的三棵树必定完全相同，这样做完全没有意义的。

###### （2）正确思想：把所有树的结论累加起来做决策 ######

我们在用GBDT做预测的时候，每棵树的数值不是身高的实际数值，而是一个残差值，将残差值累加才是真实身高=。每一棵树学的是之前所有树的残差，这个残差累加后能得到真实值。  
例如一个人的身高是1.8米，决策树1预测为1.1米，1.8 - 1.1 = 0.7，那么残差为0.7米。然后决策树2将0.7米拿去训练学习，如果决策树2能把年龄分到0.7米的叶子节点，那累加两棵树的结果：1.1 + 0.7 = 1.8米就是实际身高；如果决策树2的结果是0.5米，那么决策树2将0.5米拿去训练学习，0.7 - 0.5 = 0.2，则还存在0.2米的残差，决策树3继续学。这就是Gradient Boosting的核心思想。

#### 2．DT–Regression Decistion Tree中的树一般是回归树： ####

我们都知道，决策树可以用于回归和分类。回归树用于预测实数值，用户的身高，体重，年龄，爱好，所在地的天气，湿度，温度，是否有风。分类树用于分类标签值，如气温高，低，适中、用户性别，学历，工作类型。数值相加减是有意义的，1米 + 1.5米 + 1.7米 = 3.2米，标签值相加减是无意义的，如男+男+女=到底是男是女？ **GBDT的核心在于累加所有树的结果作为最终结果**。虽然调整后也可用于分类，但不代表GBDT的树是分类树。

#### 3、Shrinkage–缩减，循序渐进： ####

Shrinkage的思想强调的是循序渐进，就好比不能一口吃出一个胖子。每次迭代只走一小步逐渐逼近结果的效果，要比每次迈一大步很快逼近结果的方式更容易避免过拟合。即它不完全信任每一个棵残差树，它认为每棵树只学到了真理的一小部分，累加的时候只累加一小部分，通过多学几棵树弥补不足。

## 二、算法流程： ##

##### 1.模型 #####

提升方法实际采用加法模型（即基函数的线性组合）与前向分布算法。以决策树为基函数的提升方法称为提升树（boosting tree)。提升树模型可以表示为决策树的加法模型： ![在这里插入图片描述][20181216234435503.png]  
其中，![在这里插入图片描述][20181216234459474.png]表示决策树；![在这里插入图片描述][20181216234522741.png]为决策树的参数；M为树的个数

##### 2.学习过程 #####

回归问题提升树使用以下前向分布算法：  
![在这里插入图片描述][20181216234538762.png]  
在前向分布算法的第m步，给定当前模型，需求解  
![在这里插入图片描述][20181216234546444.png]  
得到![在这里插入图片描述][20181216234556390.png]，即第m棵树的参数

当采用平方误差损失函数，![在这里插入图片描述][20181216234625731.png]

其损失变为：![在这里插入图片描述][201812162346420.png]  
其中,![在这里插入图片描述][20181216234653580.png]是当前模型拟合数据的残差（residual）。对于平方损失函数，拟合的就是残差；对于一般损失函数（梯度下降），拟合的就是残差的近似值

##### 3.算法 #####

输入：训练数据集![在这里插入图片描述][20181216234709863.png]  
输出：提升树![在这里插入图片描述][20181216234715686.png]  
算法流程：  
（1）初始化 ![在这里插入图片描述][20181216234724637.png]  
（2）对m = 1,2,…，M

1.计算残差![在这里插入图片描述][20181216234736837.png]

2.拟合残差学习一个回归树，得到![在这里插入图片描述][20181216234745543.png]  
3.更新![在这里插入图片描述][20181216234752153.png]  
4.得到回归问题提升树

![在这里插入图片描述][20181216234757130.png]

## 三、实例详解： ##

如下表所示：一组数据，特征为年龄、体重，身高为标签值。共有5条数据，前四条为训练样本，最后一条为要预测的样本。  
　　![在这里插入图片描述][20181216234815587.png]

##### 1.初始化弱学习器: #####

![在这里插入图片描述][20181216234826644.png]  
　　求导：  
![在这里插入图片描述][20181216234905515.png]

所以初始化时，r取值为所有训练样本标签值的均值。r=(1.1+1.3+1.7+1.8)/4=1.475，此时得到初始学习器![在这里插入图片描述][20181216234945473.png]  
![在这里插入图片描述][20181216234959455.png]

##### 2.对迭代轮数m=1: #####

计算负梯度——残差  
　　![在这里插入图片描述][20181216235008702.png]

残差在下表列出：  
初始化![在这里插入图片描述][20181216235020586.png]： r  
残差：真实值 - r  
![在这里插入图片描述][20181216235032238.png]

此时将残差作为样本的真实值训练f1(x)，即下表数据  
![在这里插入图片描述][2018121623504488.png]  
接着，寻找回归树的最佳划分节点，遍历每个特征的每个可能取值。从年龄特征的5开始，到体重特征的70结束，分别计算方差，找到使方差最小的那个划分节点即为最佳划分节点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTE5NDE3MQ_size_16_color_FFFFFF_t_70]

以上划分点是的总方差最小为0.0125有两个划分点：年龄21和体重60，所以随机选一个作为划分点，这里我们选年龄21。  
此时还需要做一件事情，给这两个叶子节点分别赋一个参数，来拟合残差。  
![在这里插入图片描述][20181216235122277.png]  
这里其实和上面初始化学习器是一个道理，平方损失，求导，令导数等于零，化简之后得到每个叶子节点的参数r，其实就是标签值的均值。  
根据上述划分节点：  
样本1，2为左叶子节点，(x1,x2∈R11)，所以r11=(−0.375−0.175)/2=−0.275  
样本3，4为右叶子节点，(x3,x4∈R21)，所以r21=(0.225+0.325)/2=0.275  
此时可更新强学习器 ：  
![在这里插入图片描述][20181216235138649.png]  
当年龄 < 21岁时，f1 = 1.475 + (-0.275) = 1.2  
当年龄 > 21岁时，f1 = 1.475 + 0.275 = 1.75

##### 3.对迭代轮数m=2,3,4,5,…,M: #####

循环迭代M次，M是人为控制的参数，迭代结束生成M棵树

##### 4.得到最后的强学习器（回归提升树）： #####

为了方别展示和理解，我们假设Ｍ＝１，根据上述结果得到强学习器：  
![在这里插入图片描述][20181216235310770.png]  
如图所示得到只迭代一次，只有一颗树的GBDT：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTE5NDE3MQ_size_16_color_FFFFFF_t_70 1]

此时可更新强学习器：  
f1 = 1.475 + (-0.275) = 1.2  
f1 = 1.475 + 0.275 = 1.75

##### 5.预测样本： #####

样本在根节点中（即初始学习器）被预测为1.475，样本的年龄为25，大于划分节点21岁，所以被分到了右边的叶子节点，同时被预测为0.275。此时便得到样本的最总预测值为1.75。

## 四、流程总结： ##

###### 1.初始化残差，构成弱学习器1。（预测特征所对应得特征值求平均值） ######

###### 2.计算残差（实际值 - 弱学习器1）。 ######

###### 3.寻找回归树的最佳划分点（阈值）。遍历每个特征的每个特征值作为阈值，通过阈值将数据二分，分别计算方差，找到使方差最小的特征值为最佳二分阈值 ######

###### 4.将二分后的残差值更新为实际值，计算实际值平均值 作为残差。构成弱学习器2。 ######

###### 5.合并强学习器。（弱学习器1 + 弱学习器2） ######

###### 6.满足条件迭代停止。 ######

## 五、GBDT分析总结： ##

###### 1.GBDT梯度提升树，就是不断减小残差，不断提高模型效果的优化过程。 ######

###### 2.残差分析，残差越小，方差越小，数据离散化程度越小，那么数据更加趋向一类，从而数据预测更加准确。 ######

###### 3.所谓残差就是boost思想中，关注的那一部分没有分对的数据，然后增加权重，给下一个弱分类器重点关注。所以减小残差就是减小代价。残差趋向于0，就是代价降到最小。 ######

## 六、公式推导 ##

**GBDT梯度提升树算法流程**

*  初始化模型
 *  拟合负梯度，得到每一轮的基学习器。
 *  把所有基学习器叠加，最终得到模型。

f ( x ) = f ( x ) = ∑ i = 1 m T ( X ; θ i ) f(x) = f(x) = \\sum\_\{i=1\} ^ m T(X;\\theta\_i) \\quad f(x)=f(x)=i=1∑mT(X;θi)

**GBDT损失函数,拟合负梯度**

##  γ i m = − \[ ∂ L ( y i , f ( x i ) ) ∂ f ( x i ) \] f = f i − 1 \\gamma\_\{im\} = -\[\\frac\{\\partial L(y\_i,f(x\_i))\}\{\\partial f(x\_i)\}\]\_\{f = f\_\{i - 1\}\} \\quad γim=−\[∂f(xi)∂L(yi,f(xi))\]f=fi−1 ##

*  平方损失函数

L ( y i , f ( x i ) ) = 1 2 ( y i − f ( x i ) ) 2 L(y\_i, f(x\_i)) = \\frac\{1\}\{2\}(y\_i - f(x\_i))^2 \\quad L(yi,f(xi))=21(yi−f(xi))2

*  负梯度的值  
     y i − f i − 1 ( x i ) y\_i - f\_\{i - 1\}(x\_i) \\quad yi−fi−1(xi)
 *  初始化损失  
     f 0 ( x i ) = y ‾ f\_0(x\_i) = \\overline\{y\} \\quad f0(xi)=y

**GBDT分类任务**

*  初始化加法模型

f 0 ( x i ) = l o g ( 正 样 本 个 数 负 样 本 个 数 ) f\_0(x\_i) = log(\\frac\{正样本个数\}\{负样本个数\}) \\quad f0(xi)=log(负样本个数正样本个数)

*  log损失函数

L ( y i , f ( x i ) ) = y i l o g ( p i ) + ( 1 − y i ) l o g ( 1 − p i ) L(y\_i, f(x\_i)) = y\_i log(p\_i) + (1 - y\_i) log(1 - p\_i) \\quad L(yi,f(xi))=yilog(pi)\+(1−yi)log(1−pi)

p i = 1 1 + e − f ( x i ) p\_i = \\frac\{1\}\{1 + e^\{-f(x\_i)\}\} \\quad pi=1\+e−f(xi)1

*  负梯度值

y i − 1 1 + e − f i − 1 ( x i ) y\_i - \\frac\{1\}\{1 + e^\{- f\_\{i - 1\} (x\_i)\}\} \\quad yi−1\+e−fi−1(xi)1

**AdaBoost分类**

*  input：训练集：弱学习器为M个
 *  output：最终的强学习器 G ( x ) G(x) G(x)

T = ( x 1 , y 1 ) , ( x 2 , y 2 ) , ( x 3 , y 3 ) , … , ( x n , y n ) , y ∈ − 1 , + 1 T = \{(x\_1, y\_1), (x\_2, y\_2), (x\_3, y\_3), …, (x\_n, y\_n)\}, y \\in \{-1, +1\} \\quad T=(x1,y1),(x2,y2),(x3,y3),…,(xn,yn),y∈−1,\+1

1.初始化样本权重

D 1 = ( w 11 , w 12 , w 13 , … , w 1 N ) w 1 i = 1 N , i = 1 , 2 , 3 , … , N D\_1 = (w\_\{11\}, w\_\{12\},w\_\{13\}, …, w\_\{1N\}) w\_\{1i\} = \\frac\{1\}\{N\}, i = 1, 2, 3, …, N \\quad D1=(w11,w12,w13,…,w1N)w1i=N1,i=1,2,3,…,N

2.对于 m = 1 , 2 , 3 , … , M m = 1, 2, 3, …, M m=1,2,3,…,M

(1)使用具有权值分布 D m D\_m Dm的训练数据训练模型，得到弱学习器 G m ( x ) G\_m (x) Gm(x)

(2)计算 G m ( x ) G\_m (x) Gm(x)的分类误差率

e m = ∑ i = 1 N w m i I ( G m ( x i ) ≠ y i ) e\_m = \\sum\_\{i=1\} ^ N w\_\{mi\} I(G\_m (x\_i) \\not= y\_i) \\quad em=i=1∑NwmiI(Gm(xi)=yi)

(3)计算弱学习器的系数

α m = 1 2 l o g 1 − e m e m \\alpha\_m = \\frac\{1\}\{2\} log \\frac\{1 - e\_m\}\{e\_m\} \\quad αm=21logem1−em

(4)更新训练集的权值

D m + 1 = ( w m + 1 , 1 , … , w m + 1 , i , … , w m + 1 , N ) D\_\{m + 1\} = (w\_\{m + 1, 1\}, …, w\_\{m + 1, i\}, …, w\_\{m + 1, N\}) \\quad Dm\+1=(wm\+1,1,…,wm\+1,i,…,wm\+1,N)

w m + 1 , i = w m i Z m e x p ( − α m y i G m ( x i ) ) , i = 1 , 2 , 3 , … , N w\_\{m + 1, i\} = \\frac\{w\_\{mi\}\}\{Z\_m\} exp(-\\alpha\_m y\_i G\_m(x\_i)), i = 1, 2, 3, …,N \\quad wm\+1,i=Zmwmiexp(−αmyiGm(xi)),i=1,2,3,…,N

上式中， Z m Z\_m Zm是规范因子

Z m = ∑ i = 1 N w m i e x p ( − α m y i G m ( x i ) ) Z\_m = \\sum\_\{i=1\} ^ N w\_\{mi\} exp(-\\alpha\_m y\_i G\_m(x\_i)) \\quad Zm=i=1∑Nwmiexp(−αmyiGm(xi))

3.构建线性组合基分类器

f ( x ) = ∑ m = 1 M α m G m ( x ) f(x) = \\sum\_\{m=1\} ^ M \\alpha\_m G\_m (x) \\quad f(x)=m=1∑MαmGm(x)

4.得到强分类器

G ( x ) = s i g n ( f ( x ) ) = s i g n \[ ∑ m = 1 M α m G m ( x ) \] G(x) = sign(f(x)) = sign\[\\sum\_\{m=1\} ^ M \\alpha\_m G\_m (x)\] G(x)=sign(f(x))=sign\[m=1∑MαmGm(x)\]

**AdaBoost回归**

*  input：训练集：弱学习器为M个
 *  output：最终的强学习器 G ( x ) G(x) G(x)

T = ( x 1 , y 1 ) , ( x 2 , y 2 ) , ( x 3 , y 3 ) , … , ( x n , y n ) , y ∈ R T = \{(x\_1, y\_1), (x\_2, y\_2), (x\_3, y\_3), …, (x\_n, y\_n)\}, y \\in R \\quad T=(x1,y1),(x2,y2),(x3,y3),…,(xn,yn),y∈R

1.初始化样本权重

2.对于 m = 1 , 2 , 3 , … , M m = 1, 2, 3, …, M m=1,2,3,…,M

(1)使用具有权值分布 D m D\_m Dm的训练数据训练模型，得到弱学习器 G m ( x ) G\_m (x) Gm(x)

(2)计算$ G\_m (x) $的回归误差率

e m = ∑ i = 1 N w m i ( y i − G m ) 2 E 2 m e\_m = \\sum\_\{i=1\} ^ N w\_\{mi\} \\frac\{(y\_i - G\_m)^2\}\{E\{2\}\_m\} \\quad em=i=1∑NwmiE2m(yi−Gm)2

上式中  
 E m = m a x ∣ y i − G m ∣ , i = 1 , 2 , 3 , … , N E\_m = max |y\_i - G\_m|, i = 1, 2, 3, …, N \\quad Em=max∣yi−Gm∣,i=1,2,3,…,N

(3)计算若学习器的系数 α m \\alpha\_m αm

α m = e m 1 − e m \\alpha\_m = \\frac\{e\_m\}\{1 - e\_m\} \\quad αm=1−emem

(4)更新训练集的权值

w m + 1 , i = w m i Z m α m 1 − e m i w\_\{m + 1, i\} = \\frac\{w\_\{mi\}\}\{Z\_m\} \\alpha^\{1 - e\_\{mi\}\}\_m \\quad wm\+1,i=Zmwmiαm1−emi

上式中， Z m Z\_m Zm是规范因子

Z m = ∑ i = 1 N w m i α m 1 − e m i Z\_m = \\sum\_\{i=1\} ^ N w\_\{mi\} \\alpha^\{1 - e\_\{mi\}\}\_m \\quad Zm=i=1∑Nwmiαm1−emi

4.得到强分类器

G ( x ) = ∑ m = 1 M ( l n ( 1 a m ) ) g ( x ) = \[ ∑ m = 1 M ( l n ( 1 a m ) ) \] g ( x ) G(x) = \\sum\_\{m=1\} ^ M (ln(\\frac\{1\}\{a\_m\})) g(x) = \[\\sum\_\{m=1\} ^ M (ln(\\frac\{1\}\{a\_m\}))\] g(x) \\quad G(x)=m=1∑M(ln(am1))g(x)=\[m=1∑M(ln(am1))\]g(x)

上式中 g ( x ) g(x) g(x)是所有 α m G m ( x ) , m = 1 , 2 , 3 , … , M \\alpha\_m G\_m(x), m = 1, 2, 3,…, M αmGm(x),m=1,2,3,…,M 的中位数

> > > #### 欢迎大家交流学习，任何问题都可以留言 ####

参考资料：

https://blog.csdn.net/molu\_chase/article/details/78111148  
https://blog.csdn.net/google19890102/article/details/51746402  
https://blog.csdn.net/a819825294/article/details/51188740  
http://blog.csdn.net/zpalyq110/article/details/79527653

[20181216234435503.png]: /images/20220404/d53cdb5b06af4edab3f26f18a0885f15.png
[20181216234459474.png]: https://img-blog.csdnimg.cn/20181216234459474.png
[20181216234522741.png]: /images/20220404/e4316b52f7bc454a91e085c332f99339.png
[20181216234538762.png]: /images/20220404/7cfec06d29f245079d2efa1b31a6736b.png
[20181216234546444.png]: /images/20220404/fa4f5939808143a69085810ea49a28b0.png
[20181216234556390.png]: /images/20220404/d7535442a27b43bbb56ad6d25eaf6e11.png
[20181216234625731.png]: /images/20220404/edb5bca99f724c088aa26765c68c96a4.png
[201812162346420.png]: /images/20220404/c4491d449f3b4bfc9324c55db8429230.png
[20181216234653580.png]: /images/20220404/3797d0b93755492ebcce9e36915dec21.png
[20181216234709863.png]: /images/20220404/4f5a754c690f43c58f453eb7eb2ae157.png
[20181216234715686.png]: /images/20220404/e3aa172b582444a5b75ca92d878fa602.png
[20181216234724637.png]: /images/20220404/64b73926fe0b49449d7c07e0e691107b.png
[20181216234736837.png]: /images/20220404/12c62f8dacd74c5f8cac4b7566e1e173.png
[20181216234745543.png]: /images/20220404/985939a69f634cfcb93731fb2a6ff84f.png
[20181216234752153.png]: /images/20220404/6c7948d04908433a8e5d8ad2c3ffbc4b.png
[20181216234757130.png]: /images/20220404/df223cf30d1a4c26ba3c9e2c42d95763.png
[20181216234815587.png]: /images/20220404/6e1fb0b7400540959141123e0eb83e05.png
[20181216234826644.png]: /images/20220404/4f01b81eda1a40e295f88f7711f8151d.png
[20181216234905515.png]: /images/20220404/92b8bf132e354a389147617258ad5dac.png
[20181216234945473.png]: /images/20220404/ad6e5df99a254549bcfde3dcb94b1a55.png
[20181216234959455.png]: /images/20220404/fca3d3a4bf5d492b9ae4182b14ccdd43.png
[20181216235008702.png]: /images/20220404/cd9dbc8de79546628accda569d10ab23.png
[20181216235020586.png]: /images/20220404/1c7727e8ca27408bb278e9c0ed69ff70.png
[20181216235032238.png]: /images/20220404/cbf1025d6a214ad4919c7804d8303048.png
[2018121623504488.png]: /images/20220404/4f1130de82724c8ab63c202aa638c66a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTE5NDE3MQ_size_16_color_FFFFFF_t_70]: /images/20220404/d75ff1dad3104e2c9e284f45937a8ad0.png
[20181216235122277.png]: /images/20220404/a72c63cae6c24f48973c86eeb2def470.png
[20181216235138649.png]: /images/20220404/5cfa5dc1251c49deae8ee66af95f294a.png
[20181216235310770.png]: /images/20220404/ccd12226346447a79f0dbcbbfdf344f4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTE5NDE3MQ_size_16_color_FFFFFF_t_70 1]: /images/20220404/db276653e1be4ddc9c0671bbda45926e.png