该内容完全转载自同名CSDN博客(http://blog.csdn.net/zpalyq110/article/details/79527653)

GitHub
简书
 CSDN
写在前面： 去年学习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每次迭代要拟合的是梯度值，是连续值所以要用回归树。

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

回归树生成算法:
输入: 训练数据集 $D$
输出: 回归树 $f(x)$
在训练数据集所在的输入空间中，递归的将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树：

(1) 选择最优切分变量 $j$ 与切分点 $s$ ，求解:

$\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$ ，对固定的切分变量j扫描切分点 $s$ ，选择使得上式达到最小值的对 $(j,s)$ .简要解释一下上述公式：中括号里面的公式是求出每个特征变量在哪一个划分点时损失函数最小，最外面的 $\min$ 是在所有特征值，求得使损失函数全局最小的特征及其切分点 $(j^*, s^*)$ ;

(2) 用选定的对 $(j,s)$ 划分区域并决定相应的输出值：

$R_1(j, s)=\{x|x^{(j)}\leq s\},R_2(j, s)=\{x|x^{(j)} > s\}$

$\hat {c_m}=\frac{1}{N}\sum_{x_1 \in R_m(j, s)}y_i, x \in R_m, m=1,2$

求划分区域的输出值就是将该区域的所有样本的输出值求平均。

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

(4)将输入空间划分为M个区域 $R_1, R_2...R_M$ ，得到决策树
$f(x)=\sum_{m=1}^M \hat{c_m}I(x \in R_m)$

2. Gradient Boosting：拟合负梯度

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

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

提升树算法:

(1) 初始化 $f_0(x)=0$

(2) 对 $m=1, 2...M$

(a)计算残差
$r_{mi}=y_i-f_{m-1}(x_i), i=1, 2,...,M$

(b) 拟合残差 $r_{mi}$ 学习一个回归树，得到 $h_m(x)$

(3)得到回归树
$f_{M}(x)=\sum_{m=1}^Mh_m(x)$

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

在提升树算法中，假设我们前一轮迭代得到的强学习器是
$f_{t-1}(x)$
损失函数是

$L(y, f_{t-1}(x))$

我们本轮迭代的目标是找到一个弱学习器
$h_{t}(x)$

当采用平方损失函数时

$\begin{aligned} & L(y, f_{t-1}(x)+h_t(x)) \\ & = (y - f_{t-1}(x) - h_t(x))^2 \\ & =(r - h_t(x))^2 \\ \end{aligned}$

这里，
$r = y - f_{t-1}(x)$

是当前模型拟合数据的残差（residual）。所以，对于提升树来说只需要简单地拟合当前模型的残差。

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

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

那么负梯度长什么样呢？

第t轮的第i个样本的损失函数的负梯度为：

$-[\frac{\partial {L(y, f(x_i))}}{\partial {f(x_i)}}]_{f(x)=f_{t-1}(x)}$

此时不同的损失函数将会得到不同的负梯度，如果选择平方损失

$L(y, f(x_i))=\frac{1}{2}(y-f(x_i))^2$

负梯度为
$-[\frac{\partial {L(y, f(x_i))}}{\partial {f(x_i)}}]_{f(x)=f_{t-1}(x)}=-[\frac{\partial \frac{1}{2}(y-f(x_i))^2}{\partial {f(x_i)}}]_{f(x)=f_{t-1}(x)}=y-f(x_i)$

此时我们发现GBDT的负梯度就是残差，所以说对于回归问题，我们要拟合的就是残差。

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

3. GBDT算法原理

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

GBDT算法：
（1）初始化弱学习器
$f_0(x)=\arg \min_{c}\sum_{i=1}^{N}L(y_i, c)$

后面有证明，党委平方损失时， $f_0(x)=\frac{\sum_{i=1}^N y_i}{N}$

(2) 对m=1,2,…,M有：

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

$r_{im}=-[\frac{\partial{L(y_i, f(x_i))}}{\partial f(x_i)}]_{f(x)=f_{m-1}(x)}$

（b）将上步得到的残差作为样本新的真实值，并将数据 $(x_i, x_im), i=1, 2,...,N$ 作为下棵树的训练数据，得到一颗新的回归树 $f_m(x)$ ，其对应的叶子节点区域为 $R_jm, j=1, 2,...,J$ 。其中J为回归树t的叶子节点的个数。

（c）对叶子区域 $j =1,2,..J$ 计算最佳拟合值
$\gamma_{jm}=\arg \min_{\gamma}\sum_{x_i \in R_{jm}}L(y_i, f_{m-1}(x_i)+\gamma) (对 \gamma求导并令导数为0即可求得)$
（d）更新强学习器
$f_m{x}=f_{m-1}(x)+\sum_{j=1}^{J}\gamma_{jm}I(x \in R_{jm})$

(3)得到最终学习器

$f(x)=f_M{x}=f_{0}(x)+\sum_{m=1}^{M}\sum_{j=1}^{J}\gamma_{jm}I(x \in R_{jm})$

4. 实例详解

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

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

数据介绍：

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

[图片上传失败...(image-3f17ae-1556349610350)]

训练阶段：

参数设置：

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

1.初始化弱学习器:

$f_0(x)=arg min_c\sum_{i=1}^N L(y_i, c)$

损失函数为平方损失，因为平方损失函数是一个凸函数，直接求导，倒数等于零，得到 $c$ 。

$\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)$

令导数等于0

$\sum_{i=1}^N(c - y_i)=c - \sum_{i=1}^N y_i = 0$

$c = (\sum_{i=1}^N y_i)/N$

所以初始化时， $c$ 取值为所有训练样本标签值的均值。 $c=(1.1+1.3+1.7+1.8)/4=1.475$ ，此时得到初始学习器 $f_0(x)$

$f_0(x)=c=1.475$

2.对迭代轮数m=1，2,…,M:

由于我们设置了迭代次数：n_trees=5，这里的M=5。

计算负梯度，根据上文损失函数为平方损失时，负梯度就是残差残差，再直白一点就是 y与上一轮得到的学习器 $f_{m-1}$ 的差值

$r_{i1}==-[\frac{\partial{L(y_i, f(x_i))}}{\partial f(x_i)}]_{f(x)=f_{0}(x)}$

残差在下表列出

[图片上传失败...(image-397f0d-1556349610350)]

此时将残差作为样本的真实值来训练弱学习器 $f_1(x)$ ，即下表数据：

[图片上传失败...(image-daae9f-1556349610350)]

接着，寻找回归树的最佳划分节点，遍历每个特征的每个可能取值。从年龄特征的5开始，到体重特征的70结束，分别计算分裂后两组数据的平方损失（Square Error）， $SE_l$ 左节点平方损失， $SE_r$ 右节点平方损失，找到使平方损失和 $SE_{sum}=SE_l+SE_r$ 最小的那个划分节点，即为最佳划分节点。