GBDT算法原理以及实例理解（含Python代码简单实现版）

一、算法简介：

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$

输出：回归树$f(x)$

在训练数据集所在的输入空间中，递归的将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树:

1）选择最优切分变量$j$与切分点$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)^2 j,smin​[c1​min​xi​∈R1​(j,s)∑​(yi​−c1​)2+c2​min​xi​∈R2​(j,s)∑​(yi​−c2​)2

遍历变量$j$，对固定的切分变量$j$扫描切分点$s$，选择使得上式达到最小值的对$(j,s)$。

（2）用选定的对$(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)}>s R1​(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,2 cm​^​=N1​xi​∈Rm​(j,s)∑​yi​,m=1,2

（3）继续对两个子区域调用步骤（1）和（2），直至满足停止条件。

（4）将输入空间划分为$M$个区域 R 1    ,    R 2    ,    ⋯    ,    R m R_1\;,\;R_2\;,\;\cdots\;,\;R_m R1​,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∑M​cm​^​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,\dots ,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,N rmi​=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∑M​hm​(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))^2 L(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$轮的第$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))^2 L(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)=argcmin​i=1∑N​L(yi​,c)

（2）对$m=1,2,\dots ,M$有：

1）对每个样本$i=1,2,\dots ,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,J Rjm​,j=1,2,⋯,J。其中$J$为回归树$t$的叶子节点的个数。

3）对叶子区域$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Υmin​xi​∈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​Υjm​I(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∑M​j=1∑J​Υjm​I(x∈Rjm​)

二、实例详解

数据介绍：

如下表所示：一组数据，特征为年龄、体重，身高为标签值。共有5条数据，前四条为训练样本，最后一条为要预测的样本。

from sklearn.tree import DecisionTreeRegressorimport numpy as npfrom sklearn.ensemble import GradientBoostingRegressorimport pandas as pdimport pydotplusfrom pydotplus import graph_from_dot_datafrom 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')