GBDT

转自：https://blog.csdn.net/zpalyq110/article/details/79527653

【尊重原创，转载请注明出处】http://blog.csdn.net/zpalyq110/article/details/79527653

 

---

 

写在前面： 去年学习GBDT之初，为了加强对算法的理解，整理了一篇笔记形式的文章，发出去之后发现阅读量越来越多，渐渐也有了评论，评论中大多指出来了笔者理解或者编辑的错误，故重新编辑一版文章，内容更加翔实，并且在GitHub上实现了和本文一致的GBDT简易版（包括回归、二分类、多分类以及可视化），供大家交流探讨。感谢各位的点赞和评论，希望继续指出错误~

  Github：https://github.com/Freemanzxp/GBDT_Simple_Tutorial

 

---

 

简介：

 

  GBDT 的全称是 Gradient Boosting Decision Tree，梯度提升树，在传统机器学习算法中，GBDT算的上TOP3的算法。想要理解GBDT的真正意义，那就必须理解GBDT中的Gradient Boosting 和Decision Tree分别是什么？

 

1. Decision Tree：CART回归树

 

  首先，GBDT使用的决策树是CART回归树，无论是处理回归问题还是二分类以及多分类，GBDT使用的决策树通通都是都是CART回归树。为什么不用CART分类树呢？因为GBDT每次迭代要拟合的是梯度值，是连续值所以要用回归树。

  对于回归树算法来说最重要的是寻找最佳的划分点，那么回归树中的可划分点包含了所有特征的所有可取的值。在分类树中最佳划分点的判别标准是熵或者基尼系数，都是用纯度来衡量的，但是在回归树中的样本标签是连续数值，所以再使用熵之类的指标不再合适，取而代之的是平方误差，它能很好的评判拟合程度。

 

---

 

回归树生成算法：

输入：训练数据集DD DD:

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

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

（1）选择最优切分变量jj jj与切分点ss ss，求解

minj,s[minc1∑xi∈R1(j,s)(yi−c1)2+minc2∑xi∈R2(j,s)(yi−c2)2 ]minj,s[minc1∑xi∈R1(j,s)(yi−c1)2+minc2∑xi∈R2(j,s)(yi−c2)2 ] \underset{j,s}{min}\left [ \underset{c_1}{min}\underset{x_i\in R_1(j,s)}{\sum}(y_i-c_1)^2 + \underset{c_2}{min}\underset{x_i\in R_2(j,s)}{\sum}(y_i-c_2)^2 \right ]j,smin​⎣⎡​c1​min​xi​∈R1​(j,s)∑​(yi​−c1​)2+c2​min​xi​∈R2​(j,s)∑​(yi​−c2​)2 ⎦⎤​遍历变量jj jj，对固定的切分变量jj jj扫描切分点ss ss，选择使得上式达到最小值的对(j,s)(j,s) (j,s)(j,s).

（2）用选定的对(j,s)(j,s) (j,s)(j,s)划分区域并决定相应的输出值：R1(j,s)=x∣x(j)≤s,R2(j,s)=x∣x(j)>sR1(j,s)=x∣x(j)≤s,R2(j,s)=x∣x(j)>s R_1(j,s)={x|x^{(j)}\leq s}, R_2(j,s)={x|x^{(j)}> s}R1​(j,s)=x∣x(j)≤s,R2​(j,s)=x∣x(j)>scmˆ=1N∑x1∈Rm(j,s)yi,x∈Rm,m=1,2cm^=1N∑x1∈Rm(j,s)yi,x∈Rm,m=1,2 \hat{c_m} =\frac{1}{N}\underset{x_1\in R_m(j,s)}{\sum}y_i, x \in R_m, m=1,2cm​^​=N1​x1​∈Rm​(j,s)∑​yi​,x∈Rm​,m=1,2（3）继续对两个子区域调用步骤（1）和（2），直至满足停止条件。

（4）将输入空间划分为MM MM个区域 R1,R2,...RMR1,R2,...RM R_1,R_2,...R_MR1​,R2​,...RM​，生成决策树：

f(x)=∑Mm=1cˆmI(x∈Rm)f(x)=∑m=1Mc^mI(x∈Rm) f(x)=\sum_{m=1}^{M}\hat{c}m I(x \in R_m)f(x)=m=1∑M​c^m​I(x∈Rm​)

 

---

 

2. Gradient Boosting： 拟合负梯度

 

  梯度提升树（Grandient Boosting）是提升树（Boosting Tree）的一种改进算法，所以在讲梯度提升树之前先来说一下提升树。

 

---

 

  先来个通俗理解：假如有个人30岁，我们首先用20岁去拟合，发现损失有10岁，这时我们用6岁去拟合剩下的损失，发现差距还有4岁，第三轮我们用3岁拟合剩下的差距，差距就只有一岁了。如果我们的迭代轮数还没有完，可以继续迭代下面，每一轮迭代，拟合的岁数误差都会减小。最后将每次拟合的岁数加起来便是模型输出的结果。

 

---

 

提升树算法：

（1）初始化f0(x)=0f0(x)=0 f_0(x)=0f0​(x)=0

（2）对m=1,2,...,Mm=1,2,...,M m=1,2,...,Mm=1,2,...,M

 （a）计算残差rmi=yi−fm−1(x),i=1,2,...,Nrmi=yi−fm−1(x),i=1,2,...,N r{mi}=y_i-f_{m-1}(x), i=1,2,...,Nrmi​=yi​−fm−1​(x),i=1,2,...,N （b）拟合残差rmirmi r_{mi}rmi​学习一个回归树，得到hm(x)hm(x) h_m(x)hm​(x)

 （c）更新fm(x)=fm−1+hm(x)fm(x)=fm−1+hm(x) f_m(x) = f_{m-1}+h_m(x)fm​(x)=fm−1​+hm​(x)

（3）得到回归问题提升树fM(x)=∑Mm=1hm(x)fM(x)=∑m=1Mhm(x) f_M(x)=\sum_{m=1}^Mh_m(x)fM​(x)=m=1∑M​hm​(x)

 

---

 

上面伪代码中的残差是什么？

在提升树算法中，假设我们前一轮迭代得到的强学习器是ft−1(x)ft−1(x) f_{t−1}(x)ft−1​(x)损失函数是L(y,ft−1(x))L(y,ft−1(x)) L(y,f_{t−1}(x))L(y,ft−1​(x))我们本轮迭代的目标是找到一个弱学习器ht(x)ht(x) h_t(x)ht​(x)最小化让本轮的损失L(y,ft(x))=L(y,ft−1(x)+ht(x))L(y,ft(x))=L(y,ft−1(x)+ht(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,ft−1(x)+ht(x))L(y,ft−1(x)+ht(x)) L(y,f_{t−1}(x)+h_t(x))L(y,ft−1​(x)+ht​(x))=(y−ft−1(x)−ht(x))2=(y−ft−1(x)−ht(x))2 =(y-f_{t−1}(x)-h_t(x))^2=(y−ft−1​(x)−ht​(x))2=(r−ht(x))2=(r−ht(x))2 =(r-h_t(x))^2=(r−ht​(x))2这里，r=y−ft−1(x)r=y−ft−1(x) r=y-f_{t−1}(x)r=y−ft−1​(x)是当前模型拟合数据的残差（residual）所以，对于提升树来说只需要简单地拟合当前模型的残差。

  回到我们上面讲的那个通俗易懂的例子中，第一次迭代的残差是10岁，第二 次残差4岁……

 

---

 

  当损失函数是平方损失和指数损失函数时，梯度提升树每一步优化是很简单的，但是对于一般损失函数而言，往往每一步优化起来不那么容易，针对这一问题，Friedman提出了梯度提升树算法，这是利用最速下降的近似方法，其关键是利用损失函数的负梯度作为提升树算法中的残差的近似值。

那么负梯度长什么样呢？

第t轮的第i个样本的损失函数的负梯度为：Unexpected text node: '    'Unexpected text node: '    '−[∂f(xi​)∂L(y,f(xi​)))​]f(x)=ft−1​(x)​此时不同的损失函数将会得到不同的负梯度，如果选择平方损失L(y,f(xi))=12(y−f(xi))2L(y,f(xi))=12(y−f(xi))2 L(y,f(x_i)) = \frac{1}{2}(y-f(x_i))^2L(y,f(xi​))=21​(y−f(xi​))2负梯度为Unexpected text node: '    'Unexpected text node: '    '−[∂f(xi​)∂L(y,f(xi​)))​]f(x)=ft−1​(x)​=y−f(xi​)  此时我们发现GBDT的负梯度就是残差，所以说对于回归问题，我们要拟合的就是残差。

  那么对于分类问题呢？二分类和多分类的损失函数都是loglosslogloss log losslogloss，本文以回归问题为例进行讲解。

 

---

 

3. GBDT算法原理

 

  上面两节分别将Decision Tree和Gradient Boosting介绍完了，下面将这两部分组合在一起就是我们的GBDT了。

 

---

 

GBDT算法：

（1）初始化弱学习器

Unexpected text node: '  'Unexpected text node: '  'f0​(x)=argminc​i=1∑N​L(yi​,c)（2）对m=1,2,...,Mm=1,2,...,M m=1,2,...,Mm=1,2,...,M有：

 （a）对每个样本i=1,2,...,Ni=1,2,...,N i=1,2,...,Ni=1,2,...,N，计算负梯度，即残差

rim=−[∂L(yi,f(xi)))∂f(xi)]f(x)=fm−1(x)rim=−[∂L(yi,f(xi)))∂f(xi)]f(x)=fm−1(x) r_{im} = -\bigg[\frac{\partial L(y_i, f(x_i)))}{\partial f(x_i)}\bigg]{f(x) = f{m-1} (x)}rim​=−[∂f(xi​)∂L(yi​,f(xi​)))​]f(x)=fm−1​(x)​

 （b）将上步得到的残差作为样本新的真实值，并将数据(xi,rim)，i=1,2,..N(xi,rim)，i=1,2,..N (x_i,r_{im})， i=1,2,..N(xi​,rim​)，i=1,2,..N作为下棵树的训练数据，得到一颗新的回归树fm(x)fm(x) f_{m} (x)fm​(x)其对应的叶子节点区域为Rjm,j=1,2,...,JRjm,j=1,2,...,J R_{jm}, j =1,2,..., JRjm​,j=1,2,...,J。其中JJ JJ为回归树t的叶子节点的个数。

 （c）对叶子区域j=1,2,..Jj=1,2,..J j =1,2,..Jj=1,2,..J计算最佳拟合值

Unexpected text node: '  'Unexpected text node: '  'Υjm​=Υargmin​​xi​∈Rjm​∑​L(yi​,fm−1​(xi​)+Υ) （d）更新强学习器

fm(x)=fm−1(x)+∑Jj=1ΥjmI(x∈Rjm)fm(x)=fm−1(x)+∑j=1JΥjmI(x∈Rjm) f_{m}(x) = f_{m-1}(x) + \sum\limits_{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)=fM(x)=f0(x)+∑Mm=1∑Jj=1ΥjmI(x∈Rjm)f(x)=fM(x)=f0(x)+∑m=1M∑j=1JΥjmI(x∈Rjm) f(x) = f_M(x) =f_0(x) + \sum\limits_{m=1}^{M}\sum\limits_{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​)

 

---

 

4. 实例详解

 

本人用python以及pandas库实现GBDT的简易版本，在下面的例子中用到的数据都在github可以找到，大家可以结合代码和下面的例子进行理解，欢迎star~

  Github：https://github.com/Freemanzxp/GBDT_Simple_Tutorial

 

---

 

数据介绍：

 

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

0	5	20	1.1
1	7	30	1.3
2	21	70	1.7
3	30	60	1.8
4(要预测的)	25	65	？

训练阶段：

---

参数设置：

• 学习率：learning_rate=0.1
• 迭代次数：n_trees=5
• 树的深度：max_depth=3

---

1.初始化弱学习器:Unexpected text node: '  'Unexpected text node: '  'f0​(x)=argminc​i=1∑N​L(yi​,c)  损失函数为平方损失，因为平方损失函数是一个凸函数，直接求导，倒数等于零，得到cc cc。
∑Ni=1∂L(yi,c))∂c=∑Ni=1∂(12(yi−c)2)∂c=∑Ni=1c−yi∑i=1N∂L(yi,c))∂c=∑i=1N∂(12(yi−c)2)∂c=∑i=1Nc−yi \sum\limits_{i=1}^{N}\frac{\partial L(y_i,c))}{\partial c}=\sum\limits_{i=1}^{N}\frac{\partial (\frac{1}{2}(y_i-c)^2)}{\partial c}=\sum\limits_{i=1}^{N}c-y_ii=1∑N​∂c∂L(yi​,c))​=i=1∑N​∂c∂(21​(yi​−c)2)​=i=1∑N​c−yi​令导数等于0
∑Ni=1c−yi=0∑i=1Nc−yi=0 \sum\limits_{i=1}^{N}c-y_i=0i=1∑N​c−yi​=0c=(∑Ni=1yi)/Nc=(∑i=1Nyi)/N c=(\sum\limits_{i=1}^{N}y_i)/N c=(i=1∑N​yi​)/N所以初始化时，cc cc取值为所有训练样本标签值的均值。c=(1.1+1.3+1.7+1.8)/4=1.475c=(1.1+1.3+1.7+1.8)/4=1.475 c=(1.1+1.3+1.7+1.8)/4=1.475c=(1.1+1.3+1.7+1.8)/4=1.475，此时得到初始学习器f0(x)f0(x) f_0(x)f0​(x)
f0(x)=c=1.475f0(x)=c=1.475 f_0(x) = c=1.475f0​(x)=c=1.475

---

2.对迭代轮数m=1，2,…,M:
  由于我们设置了迭代次数：n_trees=5，这里的M=5M=5 M=5M=5。
  计算负梯度，根据上文损失函数为平方损失时，负梯度就是残差残差，再直白一点就是 yy yy与上一轮得到的学习器fm−1fm−1 f_{m-1}fm−1​的差值
　　ri1=−[∂L(yi,f(xi)))∂f(xi)]f(x)=f0(x)ri1=−[∂L(yi,f(xi)))∂f(xi)]f(x)=f0(x) r_{i1} = -\bigg[\frac{\partial L(y_i, f(x_i)))}{\partial f(x_i)}\bigg]_{f(x) = f_{0} (x)}ri1​=−[∂f(xi​)∂L(yi​,f(xi​)))​]f(x)=f0​(x)​
残差在下表列出：

0	1.1	1.475	-0.375
1	1.3	1.475	-0.175
2	1.7	1.475	0.225
3	1.8	1.475	0.325

此时将残差作为样本的真实值来训练弱学习器f1(x)f1(x) f_{1} (x)f1​(x)，即下表数据

0	5	20	-0.375
1	7	30	-0.175
2	21	70	0.225
3	30	60	0.325

  接着，寻找回归树的最佳划分节点，遍历每个特征的每个可能取值。从年龄特征的5开始，到体重特征的70结束，分别计算分裂后两组数据的平方损失（Square Error），SElSEl SE_lSEl​左节点平方损失，SErSEr SE_rSEr​右节点平方损失，找到使平方损失和SEsum=SEl+SErSEsum=SEl+SEr SE_{sum}=SE_l+SE_rSEsum​=SEl​+SEr​最小的那个划分节点，即为最佳划分节点。
  例如：以年龄7为划分节点，将小于7的样本划分为到左节点，大于等于7的样本划分为右节点。左节点包括x0x0 x_0x0​，右节点包括样本x1,x2,x3x1,x2,x3 x_1,x_2,x_3x1​,x2​,x3​，SEl=0,SEr=0.140,SEsum=0.140SEl=0,SEr=0.140,SEsum=0.140 SE_l = 0,SE_r=0.140,SE_{sum}=0.140SEl​=0,SEr​=0.140,SEsum​=0.140，所有可能划分情况如下表所示：

年龄5	/	0，1，2，3	0	0.327	0.327
年龄7	0	1，2，3	0	0.140	0.140
年龄21	0，1	2，3	0.020	0.005	0.025
年龄30	0，1，2	3	0.187	0	0.187
体重20	/	0，1，2，3	0	0.327	0.327
体重30	0	1，2，3	0	0.140	0.140
体重60	0，1	2，3	0.020	0.005	0.025
体重70	0，1，3	2	0.260	0	0.260

  以上划分点是的总平方损失最小为0.025有两个划分点：年龄21和体重60，所以随机选一个作为划分点，这里我们选 年龄21
  现在我们的第一棵树长这个样子：

  我们设置的参数中树的深度max_depth=3，现在树的深度只有2，需要再进行一次划分，这次划分要对左右两个节点分别进行划分：

---

  对于左节点，只含有0,1两个样本，根据下表我们选择年龄7划分

年龄5	/	0，1	0	0.020	0.020
年龄7	0	1	0	0	0
体重20	/	0，1	0	0.020	0.020
体重30	0	1	0	0	0

  对于右节点，只含有2,3两个样本，根据下表我们选择年龄30划分（也可以选体重70）

年龄21	/	2，3	0	0.005	0.005
年龄30	2	3	0	0	0
体重60	/	2，3	0	0.005	0.005
体重70	3	2	0	0	0

  现在我们的第一棵树长这个样子：

  此时我们的树深度满足了设置，还需要做一件事情，给这每个叶子节点分别赋一个参数ΥΥ \UpsilonΥ，来拟合残差。Unexpected text node: '  'Unexpected text node: '  'Υj1​=Υargmin​​xi​∈Rj1​∑​L(yi​,f0​(xi​)+Υ)  这里其实和上面初始化学习器是一个道理，平方损失，求导，令导数等于零，化简之后得到每个叶子节点的参数ΥΥ \UpsilonΥ，其实就是标签值的均值。这个地方的标签值不是原始的 yy yy，而是本轮要拟合的标残差 y−f0(x)y−f0(x) y-f_0(x)y−f0​(x).
  根据上述划分结果，为了方便表示，规定从左到右为第1,2,3,41,2,3,4 1,2,3,41,2,3,4个叶子结点(x0∈R11)，Υ11=−0.375(x0∈R11)，Υ11=−0.375 (x_0 \in R_{11})，\Upsilon_{11}=-0.375(x0​∈R11​)，Υ11​=−0.375(x1∈R21)，Υ21=−0.175(x1∈R21)，Υ21=−0.175 (x_1 \in R_{21})，\Upsilon_{21}=-0.175(x1​∈R21​)，Υ21​=−0.175(x2∈R31)，Υ31=0.225(x2∈R31)，Υ31=0.225 (x_2 \in R_{31})，\Upsilon_{31}=0.225(x2​∈R31​)，Υ31​=0.225(x3∈R41)，Υ41=0.325(x3∈R41)，Υ41=0.325 (x_3 \in R_{41})，\Upsilon_{41}=0.325(x3​∈R41​)，Υ41​=0.325
  此时的树长这个样子：

---

  此时可更新强学习器，需要用到参数学习率：learning_rate=0.1，用lrlr lrlr表示。
f1(x)=f0(x)+lr∗∑4j=1Υj1I(x∈Rj1)f1(x)=f0(x)+lr∗∑j=14Υj1I(x∈Rj1) f_{1}(x) = f_{0}(x) + lr *\sum\limits_{j=1}^{4}\Upsilon_{j1}I(x \in R_{j1})f1​(x)=f0​(x)+lr∗j=1∑4​Υj1​I(x∈Rj1​)
为什么要用学习率呢？这是Shrinkage的思想，如果每次都全部加上（学习率为1）很容易一步学到位导致过拟合。

---

重复此步骤，直到 m>5m>5 m>5m>5 结束，最后生成5棵树。
下面将展示每棵树最终的结构，这些图都是GitHub上的代码生成的，感兴趣的同学可以去一探究竟
Github：https://github.com/Freemanzxp/GBDT_Simple_Tutorial
第一棵树：

第二棵树：

第三棵树：

第四棵树：

第五棵树：

---

4.得到最后的强学习器：
f(x)=f5(x)=f0(x)+∑5m=1∑4j=1ΥjmI(x∈Rjm)f(x)=f5(x)=f0(x)+∑m=15∑j=14ΥjmI(x∈Rjm) f(x) = f_{5}(x) =f_0(x) + \sum\limits_{m=1}^{5}\sum\limits_{j=1}^{4}\Upsilon_{jm}I(x \in R_{jm})f(x)=f5​(x)=f0​(x)+m=1∑5​j=1∑4​Υjm​I(x∈Rjm​)

---

5.预测样本5：
  f0(x)=1.475f0(x)=1.475 f_0(x)=1.475f0​(x)=1.475
  在f1(x)f1(x) f_1(x)f1​(x)中，样本4的年龄为25，大于划分节点21岁，又小于30岁，所以被预测为0.2250。
  在f2(x)f2(x) f_2(x)f2​(x)中，样本4的…此处省略…所以被预测为0.2025
   为什么是0.2025？这是根据第二颗树得到的，可以GitHub简单运行一下代码
  在f3(x)f3(x) f_3(x)f3​(x)中，样本4的…此处省略…所以被预测为0.1823
  在f4(x)f4(x) f_4(x)f4​(x)中，样本4的…此处省略…所以被预测为0.1640
  在f5(x)f5(x) f_5(x)f5​(x)中，样本4的…此处省略…所以被预测为0.1476
最终预测结果：f(x)=1.475+0.1∗(0.225+0.2025+0.1823+0.164+0.1476)=1.56714f(x)=1.475+0.1∗(0.225+0.2025+0.1823+0.164+0.1476)=1.56714 f(x) =1.475+ 0.1 * (0.225+0.2025+0.1823+0.164+0.1476) = 1.56714f(x)=1.475+0.1∗(0.225+0.2025+0.1823+0.164+0.1476)=1.56714

---

4. 总结

本文章从GBDT算法的原理到实例详解进行了详细描述，但是目前只写了回归问题，GitHub上的代码也是实现了回归、二分类、多分类以及树的可视化，希望大家继续批评指正，感谢各位的关注。

---

参考资料

1. 李航 《统计学习方法》
2. Friedman J H . Greedy Function Approximation: A Gradient Boosting Machine[J]. The Annals of Statistics, 2001, 29(5):1189-1232.

【尊重原创，转载请注明出处】 http://blog.csdn.net/zpalyq110/article/details/79527653