©2020-2024 ioDraw All rights reserved,
Privacy Policy
<>一、算法简介：
GBDT 的全称是 Gradient Boosting Decision Tree，梯度提升树，在传统机器学习算法中，GBDT算的上是TOP前三的算法。
想要理解GBDT的真正意义，那就必须理解GBDT中的Gradient Boosting和Decision Tree分别是什么？
1. Decision Tree：CART回归树
首先，GBDT使用的决策树是CART回归树，无论是处理回归问题还是二分类以及多分类，GBDT使用的决策树通通都是都是CART回归树。
为什么不用CART分类树呢？因为GBDT每次迭代要拟合的是梯度值，是连续值所以要用回归树。
对于回归树算法来说最重要的是寻找最佳的划分点，那么回归树中的可划分点包含了所有特征的所有可取的值。
在分类树中最佳划分点的判别标准是熵或者基尼系数，都是用纯度来衡量的，但是在回归树中的样本标签是连续数值，所以再使用熵之类的指标不再合适，取而代之的是平方误差，它能很好的评判拟合程度。
2.回归树生成算法：
输入：训练数据集 D D D
输出：回归树 f ( x ) f(x) f(x)
在训练数据集所在的输入空间中，递归的将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树:
1）选择最优切分变量 j j j与切分点 s s s，求解:
min j , s [ min c 1 ∑ x i ∈ R 1 ( j , s ) ( y i − c 1 ) 2 + min c 2 ∑ x
i ∈ R 2 ( j , s ) ( y i − c 2 ) 2 \min_{j,s}[\min_{c_1}\sum_{x_i\in
R_1(j,s)}(y_i-c_1)^2+\min_{c_2}\sum_{x_i\in R_2(j,s)}(y_i-c_2)^2j,smin[c1minx
i∈R1(j,s)∑(yi−c1)2+c2minxi∈R2(j,s)∑(yi−c2)2
遍历变量 j j j，对固定的切分变量 j j j扫描切分点 s s s，选择使得上式达到最小值的对 ( j , s ) (j,s) (j,s)。
（2）用选定的对 ( j , s ) (j,s) (j,s)划分区域并决定相应的输出值：
R 1 ( j , s ) = x ∣ x ( j ) ≤ s , R 2 ( j , s ) = x ∣ x ( j ) > s
R_1(j,s)=x|x^{(j)}\leq s\quad ,R_2(j,s)=x|x^{(j)}>sR1(j,s)=x∣x(j)≤s,R2(j,s)=x∣
x(j)>s
c m ^ = 1 N ∑ x i ∈ R m ( j , s ) y i , m = 1 , 2
\hat{c_m}=\frac{1}{N}\sum_{x_i\in R_m(j,s)}y_i\;,\;m=1,2cm^=N1xi∈Rm(j,s)∑y
i,m=1,2
（3）继续对两个子区域调用步骤（1）和（2），直至满足停止条件。
（4）将输入空间划分为 M M M个区域 R 1 , R 2 , ⋯ , R m
R_1\;,\;R_2\;,\;\cdots\;,\;R_mR1,R2,⋯,Rm，生成决策树：
f ( x ) = ∑ m = 1 M c m ^ I ( x ∈ R m ) f(x)=\sum_{m=1}^M\hat{c_m}I(x\in R_m)
f(x)=m=1∑Mcm^I(x∈Rm)
3. Gradient Boosting：拟合负梯度
梯度提升树（Grandient Boosting）是提升树（Boosting Tree）的一种改进算法，所以在讲梯度提升树之前先来说一下提升树。
我们用上一篇文章的例子来理解：
假如有个人30岁，我们首先用20岁去拟合，发现损失有10岁；我们去你和损失，拟合的数值为6岁，发现差距还有4岁，第三轮我们用3岁拟合剩下的差距，差距就只有一岁了。如果我们的迭代轮数还没有完，可以继续迭代下面，每一轮迭代，拟合的岁数误差都会减小。最后将每次拟合的岁数加起来便是模型输出的结果。
提升树算法：
（1）初始化 f 0 ( x ) = 0 f_0(x)=0 f0(x)=0
（2）对 m = 1 , 2 , … , M m=1,2,…,M m=1,2,…,M:
1)计算残差 r m i = y i − f m − 1 ( x i ) , i = 1 , 2 , ⋯ , N
r_{mi}=y_i-f_{m-1}(x_i)\;,\;i=1,2,\cdots,Nrmi=yi−fm−1(xi),i=1,2,⋯,N
2)拟合残差 r m i r_{mi} rmi学习一个回归树，得到 h m ( x ) h_m(x) hm(x)
3)更新 f m ( x ) = f m − 1 ( x ) + h m ( x ) f_m(x)=f_{m-1}(x)+h_m(x) fm(x)=fm−1
(x)+hm(x)
（3）得到回归问题提升树
f M ( x ) = ∑ m = 1 M h m ( x ) f_M(x)=\sum_{m=1}^Mh_m(x) fM(x)=m=1∑Mhm(x)
上面伪代码中的残差是什么？
在提升树算法中，假设我们前一轮迭代得到的强学习器是 f t − 1 ( x ) f_{t-1}(x) ft−1(x)，损失函数是 L ( y , f t
− 1 ( x ) ) L(y,f_{t-1}(x))L(y,ft−1(x))，我们本轮迭代的目标是找到一个弱学习器 h t ( x ) h_t(x) ht
(x)，最小化本轮的损失 L ( y , f t ( x ) ) = L ( y , f t − 1 ( x ) + h t ( x ) )
L(y,f_t(x))=L(y,f_{t-1}(x)+h_t(x))L(y,ft(x))=L(y,ft−1(x)+ht(x))。
当采用平方损失函数时:
L ( y , f t − 1 ( x ) + h t ( x ) ) = ( y − f t − 1 ( x ) − h t ( x ) ) 2 = (
r − h t ( x ) ) 2 L(y,f_{t-1}(x)+h_t(x))=(y-f_{t-1}(x)-h_t(x))^2=(r-h_t(x))^2L(y
,ft−1(x)+ht(x))=(y−ft−1(x)−ht(x))2=(r−ht(x))2
这里: r = y − f t − 1 ( x ) r=y-f_{t-1}(x) r=y−ft−1(x)，是当前模型拟合数据的残差（residual）。
所以，对于提升树来说只需要简单地拟合当前模型的残差。
回到我们上面讲的那个通俗易懂的例子中，第一次迭代的残差是10岁，第二次残差4岁…
当损失函数是平方损失和指数损失函数时，梯度提升树每一步优化是很简单的，但是对于一般损失函数而言，往往每一步优化起来不那么容易，针对这一问题，Freidman提出了梯度提升树算法，这是利用最速下降的近似方法，其关键是利用损失函数的负梯度作为提升树算法中的残差的近似值。那么负梯度长什么样呢？第
t tt轮的第 i i i个样本的损失函数的负梯度为：
− [ ∂ L ( y , f ( x i ) ) ∂ f ( x i ) ] f ( x ) = f t − 1 ( x )
-[\frac{\partial L(y,f(x_i))}{\partial f(x_i)}]_{f(x)=f_{t-1}(x)}−[∂f(xi)∂L(y,f
(xi))]f(x)=ft−1(x)
此时不同的损失函数将会得到不同的负梯度，如果选择平方损失:
L ( y , f ( x i ) ) = 1 2 ( y − f ( x i ) ) 2
L(y,f(x_i))=\frac{1}{2}(y-f(x_i))^2L(y,f(xi))=21(y−f(xi))2
负梯度为:
− [ ∂ L ( y , f ( x i ) ) ∂ f ( x i ) ] f ( x ) = f t − 1 ( x ) = y − f ( x i
) -[\frac{\partial L(y,f(x_i))}{\partial f(x_i)}]_{f(x)=f_{t-1}(x)}=y-f(x_i)−[∂f
(xi)∂L(y,f(xi))]f(x)=ft−1(x)=y−f(xi)
此时我们发现GBDT的负梯度就是残差，所以说对于回归问题，我们要拟合的就是残差。
那么对于分类问题呢？二分类和多分类的损失函数都是log loss，本文以回归问题为例进行讲解。
4. GBDT算法原理
上面两节分别将Decision Tree和Gradient Boosting介绍完了，下面将这两部分组合在一起就是我们的GBDT了。
GBDT算法：
（1）初始化弱学习器
f 0 ( x ) = arg min c ∑ i = 1 N L ( y i , c )
f_0(x)=\arg\min_{c}\sum_{i=1}^NL(y_i,c)f0(x)=argcmini=1∑NL(yi,c)
（2）对 m = 1 , 2 , … , M m=1,2,…,M m=1,2,…,M有：
1）对每个样本 i = 1 , 2 , … , N i=1,2,…,N i=1,2,…,N，计算负梯度，即残差:
r i m = − [ ∂ L ( y i , f ( x i ) ) ∂ f ( x i ) ] f ( x ) = f m − 1 ( x )
r_{im}=-[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}]_{f(x)=f_{m-1}(x)}rim=−
[∂f(xi)∂L(yi,f(xi))]f(x)=fm−1(x)
2）将上步得到的残差作为样本新的真实值，并将数据 ( x i , r i m ) , , i = 1 , 2 , ⋯ , N
(x_i\;,\;r_{im})\;,\;,i=1,2,\cdots,N(xi,rim),,i=1,2,⋯,N作为下棵树的训练数据，得到一颗新的回归树 f
m ( x ) f_m(x)fm(x)，其对应的叶子节点区域为 R j m , j = 1 , 2 , ⋯ , J
R_{jm}\;,\;j=1,2,\cdots,JRjm,j=1,2,⋯,J。其中 J J J为回归树 t t t的叶子节点的个数。
3）对叶子区域 j = 1 , 2 , . . J j =1,2,..J j=1,2,..J计算最佳拟合值
Υ j m = arg min Υ ∑ x i ∈ R j m L ( y i , f m − 1 ( x i ) + Υ
\Upsilon_{jm}=\arg\min_{\Upsilon}\sum_{x_i\in R_{jm}}L(y_i,f_{m-1}(x_i)+\Upsilon
Υjm=argΥminxi∈Rjm∑L(yi,fm−1(xi)+Υ
4）更新强学习器:
f m ( x ) = f m − 1 ( x ) + ∑ j = 1 J Υ j m I ( x ∈ R j m )
f_m(x)=f_{m-1}(x)+\sum_{j=1}^J\Upsilon_{jm}I(x\in R_{jm})fm(x)=fm−1(x)+j=1∑JΥ
jmI(x∈Rjm)
（3）得到最终学习器
f ( x ) = f M ( x ) = f 0 ( x ) + ∑ m = 1 M ∑ j = 1 J Υ j m I ( x ∈ R j m )
f(x)=f_{M}(x)=f_0(x)+\sum_{m=1}^M\sum_{j=1}^J\Upsilon_{jm}I(x\in R_{jm})f(x)=fM
(x)=f0(x)+m=1∑Mj=1∑JΥjmI(x∈Rjm)
<>二、实例详解
数据介绍：
如下表所示：一组数据，特征为年龄、体重，身高为标签值。共有5条数据，前四条为训练样本，最后一条为要预测的样本。
编号年龄（岁）体重（kg）身高（cm）（标签值）
05201.1
17301.3
221701.7
330601.8
4（预测）2565?
训练阶段：
参数设置：
学习率：learning_rate=0.1
迭代次数：n_trees=5
树的深度：max_depth=3
1.初始化弱学习器:
f 0 ( x ) = arg min c ∑ i = 1 N L ( y i , c )
f_0(x)=\arg\min_{c}\sum_{i=1}^NL(y_i,c)f0(x)=argcmini=1∑NL(yi,c)
损失函数为平方损失，因为平方损失函数是一个凸函数，直接求导，倒数等于零，得到 c c c。
∑ i = 1 N ∂ L ( y i , c ) ∂ c = ∑ i = 1 N ∂ ( 1 2 ( y i − c ) 2 ) ∂ c = ∑ i =
1 N ( c − y i ) \sum_{i=1}^N\frac{\partial L(y_i,c)}{\partial
c}=\sum_{i=1}^N\frac{\partial (\frac{1}{2}(y_i-c)^2)}{\partial
c}=\sum_{i=1}^N(c-y_i)i=1∑N∂c∂L(yi,c)=i=1∑N∂c∂(21(yi−c)2)=i=1∑N(c−yi)
令导数等于0:
∑ i = 1 N ( c − y i ) = 0 ⇒ c = ∑ i = 1 N y i / N
\sum_{i=1}^N(c-y_i)=0\Rightarrow c=\sum_{i=1}^Ny_i/Ni=1∑N(c−yi)=0⇒c=i=1∑Nyi/
N
所以初始化时，c取值为所有训练样本标签值的均值:
c = ( 1.1 + 1.3 + 1.7 + 1.8 ) / 4 = 1.475 c=(1.1+1.3+1.7+1.8)/4=1.475 c=(1.1+
1.3+1.7+1.8)/4=1.475
此时得到初始学习器：
f 0 ( x ) = c = 1.475 f_0(x)=c=1.475 f0(x)=c=1.475
2.对迭代轮数m=1，2,…,M
由于我们设置了迭代次数：n_trees=5，这里的M=5。
计算负梯度，根据上文损失函数为平方损失时，负梯度就是残差残差，再直白一点就是y与上一轮得到的学习器 f m − 1 ( x ) f_{m-1}(x) fm−1
(x)的差值:
r i 1 = − [ ∂ L ( y i , f ( x i ) ) ∂ f ( x i ) ] f ( x ) = f 0 ( x )
r_{i1}=-[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}]_{f(x)=f_0(x)}ri1=−[∂f(
xi)∂L(yi,f(xi))]f(x)=f0(x)
残差在下表列出：
编号真实值初始值残差
01.11.475-0.375
11.31.475-0.175
21.71.4750.225
31.81.4750.325
此时将残差作为样本的真实值来训练弱学习器 f 1 ( x ) f_1(x) f1(x)，即下表数据：
编号年龄体重（kg）标签值
0520-0.375
1730-0.175
221700.225
330600.325
接着，寻找回归树的最佳划分节点，遍历每个特征的每个可能取值。从年龄特征的5开始，到体重特征的70结束，分别计算分裂后两组数据的平方损失，左节点平方损失为 S
E l SE_{l}SEl，右节点平方损失为 S E r SE_{r} SEr。
找到使平方损失和 S E s u m = S E l + S E r SE_{sum}=SE_{l}+SE_{r} SEsum=SEl+SEr
最小的那个划分节点，即为最佳划分节点。
例如：以年龄7为划分节点，将小于7的样本划分为到左节点，大于等于7的样本划分为右节点。
左节点包括 x 0 x_0 x0，右节点包括样本 x 1 , x 2 , x 3 x_1\;,\;x_2\;,\;x_3 x1,x
2,x3。 S E l = 0 ， S E r = 0.14 ， S E s u m = S E l + S E r = 0.14
SE_{l}=0，SE_{r}=0.14，SE_{sum}=SE_{l}+SE_{r}=0.14SEl=0，SEr=0.14，SEsum=SEl+SEr
=0.14
我们所有可能划分情况如下表所示：
划分点小于划分点的样本大于等于划分点的样本SE_lSE_rSE_sum
年龄5无0，1，2，300.32750.3275
年龄701，2，300.140.14
年龄210，12，30.020.0050.025
年龄300，1，230.186600.1866
体重20无0，1，2，300.32750.3275
体重3001，2，300.140.14
体重600，12，30.020.0050.025
体重700，1，320.2600.26
以上划分点是的总平方损失最小为0.025有两个划分点：年龄21和体重60，所以随机选一个作为划分点：
我们生成第一棵树为:
根据上图，我们的划分依据为：
选择的划分标准为体重，小于45kg的分为一类，为样本0和1；大于等于45kg的分为一类，为样本2和3。
第一次分开后再以年龄作为选择方式，左支中以6岁为分界线，将样本0和1分开；右支以25.5岁为分界线，将样本2和3分开。
<>计算残差，并把残差当做目标值训练第一棵树
这里其实和上面初始化学习器是一个道理，平方损失求导，令导数等于零，化简之后得到每个叶子节点的参数 y y y，其实就是标签值的均值。这个地方的标签值不是原始的
y yy，而是本轮要拟合的标残差 y − f 0 ( x ) y-f_0(x) y−f0(x)。
此时，第一棵树如下所示：
根据上述划分结果，为了方便表示，规定从左到右为第0，1，2，3样本：
x 0 ∈ R 11 Υ 11 = − 0.375 x_0\in R_{11}\quad \Upsilon_{11}=-0.375 x0∈R11Υ11
=−0.375
x 1 ∈ R 21 Υ 21 = − 0.175 x_1\in R_{21}\quad \Upsilon_{21}=-0.175 x1∈R21Υ21
=−0.175
x 2 ∈ R 31 Υ 31 = 0.225 x_2\in R_{31}\quad \Upsilon_{31}=0.225 x2∈R31Υ31=
0.225
x 3 ∈ R 41 Υ 41 = 0.325 x_3\in R_{41}\quad \Upsilon_{41}=0.325 x3∈R41Υ41=
0.325
此时可更新强学习器，需要用到参数学习率：learning_rate=0.1，在公式中我们用l来表示：
f 1 ( x ) = f 0 ( x ) + l ∗ ∑ j = 1 4 Υ j 1 I ( x ∈ R j 1 )
f_1(x)=f_0(x)+l*\sum_{j=1}^4\Upsilon_{j1}I(x\in \R_{j1})f1(x)=f0(x)+l∗j=1∑4Υj
1I(x∈Rj1)
为什么要用学习率呢？这是Shrinkage的思想，如果每次都全部加上（学习率为1）很容易一步学到位导致过拟合。
Shrinkage的思想我后面会介绍：
我们看一下第二棵树：
我们看第三棵树为:
第四棵树为：
第五棵树为：
得到最后的强学习器：
f ( x ) = f 5 ( x ) = f 0 ( x ) + ∑ m = 1 5 ∑ j = 1 4 Υ j m I ( x ∈ R j m )
f(x)=f_5(x)=f_0(x)+\sum_{m=1}^5\sum_{j=1}^4\Upsilon_{jm}I(x\in \R_{jm})f(x)=f5(
x)=f0(x)+m=1∑5j=1∑4ΥjmI(x∈Rjm)
<>三、预测样本4
样本4为25岁，65kg。
f 0 ( x ) = 1.475 f_0(x)=1.475 f0(x)=1.475
在 f 1 ( x ) f_1(x) f1(x)
中，体重65kg大于45kg（90斤），所以分到右节点；又因为年龄为25岁小于25.5，所以最终的预测值为0.225；
在 f 2 ( x ) f_2(x) f2(x)中，最终预测为0.2025；
在 f 3 ( x ) f_3(x) f3(x)中，最终预测为0.1822；
在 f 4 ( x ) f_4(x) f4(x)中，最终预测为0.164；
在 f 5 ( x ) f_5(x) f5(x)中，最终预测为0.1476；
最终预测结果：
f ( x ) = 1.475 + 0.1 ∗ ( 0.225 + 0.2025 + 0.1822 + 0.164 + 0.1476 ) =
1.56713 f(x)=1.475+0.1*(0.225+0.2025+0.1822+0.164+0.1476)=1.56713f(x)=1.475+0.1∗
(0.225+0.2025+0.1822+0.164+0.1476)=1.56713
<>四、调用GBDT算法包
我们使用sklearn中的GBDT算法包来实现，生成的树为：
此时，我们预测的结果为0.1919。
<>五、源代码
from sklearn.tree import DecisionTreeRegressor import numpy as np from sklearn.
ensembleimport GradientBoostingRegressor import pandas as pd import pydotplus
from pydotplus import graph_from_dot_data from sklearn.tree import
export_graphviz data_1=[[5,40,1.1],[7,60,1.3],[21,140,1.7],[30,120,1.8]] data=pd
.DataFrame(data_1,columns=['age','weight','标签']) X=np.array(data.iloc[:,:-1]).
reshape((-1,2)) y=np.array(data.iloc[:,-1]).reshape((-1,1)) tree_reg1 =
DecisionTreeRegressor(max_depth=4,random_state=10) tree_reg1.fit(X, y) y2 = y -
np.array([1.475]*4).reshape((-1,1)) tree_reg2 = DecisionTreeRegressor(max_depth=
4,random_state=10) tree_reg2.fit(X, y2) y3 = y2 - 0.1*np.array(tree_reg2.predict
(X)).reshape((-1,1)) tree_reg3 = DecisionTreeRegressor(max_depth=4,random_state=
10) tree_reg3.fit(X, y3) y4 = y3 - 0.1*np.array(tree_reg3.predict(X)).reshape((-
1,1)) tree_reg4 = DecisionTreeRegressor(max_depth=4,random_state=10) tree_reg4.
fit(X, y4) y5 = y4 - 0.1*np.array(tree_reg4.predict(X)).reshape((-1,1))
tree_reg5= DecisionTreeRegressor(max_depth=4,random_state=10) tree_reg5.fit(X,
y5) y6 = y5 - 0.1*np.array(tree_reg5.predict(X)).reshape((-1,1)) tree_reg6 =
DecisionTreeRegressor(max_depth=4,random_state=10) tree_reg6.fit(X, y6)
estimator=GradientBoostingRegressor(random_state=10) estimator.fit(data.iloc[:,:
-1],data.iloc[:,-1]) dot_data = export_graphviz(estimator.estimators_[5,0],
out_file=None, filled=True, rounded=True, special_characters=True, precision=4)
graph= pydotplus.graph_from_dot_data(dot_data) graph.write_pdf('estimator.pdf')