【机器学习】深入剖析梯度提升决策树(GBDT)分类与回归原创

1. 梯度提升决策树概述

梯度提升决策树（Gradient Boosting Decision Tree，GBDT）是以决策树为基学习器的一种Boosting算法，它在每一轮迭代中建立一个决策树，使当前模型的残差在梯度方向上减少；然后将该决策树与当前模型进行线性组合得到新模型；不断重复，直到决策树数目达到指定的值，得到最终的强学习器。

上一篇博客【机器学习】集成学习——Boosting与AdaBoost原理详解与公式推导对AdaBoost算法做了总结，GBDT与AdaBoost的主要区别有：

1. 迭代策略不同 ：AdaBoost在每一轮迭代中都要更新样本分布；GBDT迭代学习上一轮得到的加法模型与真实值之间的残差，它并不显式改变样本分布，而是利用残差变相地增大错误样本的权重。

2. 组合策略不同 ：AdaBoost中误差率越低的基学习器在最终模型中所占比重越高，而GBDT每棵树的权值都相等。

3. 基学习器限定不同：AdaBoost的基学习器不限，使用最广泛的是决策树和神经网络；而GBDT的基学习器限定为决策树，且是回归树。

4. 损失函数不同：AdaBoost分类算法的损失函数限定为指数损失，而GBDT可以是指数损失函数和对数似然函数。

2. 提升树

在介绍梯度提升决策树之前，我们首先来介绍提升树。

介绍了提升方法本身是采用加法模型和前向分步算法的一种方法，而提升树（Boosting Tree）是以决策树为基学习器的一种提升方法，对分类问题决策树是二叉分类树，对回归问题决策树是二叉回归树。

提升树模型可以表示为决策树的加法模型：

其中， $h \left( x ; \Theta _ { t } \right)$ 表示第棵决策树； $\Theta _ { t }$ 是的参数；是决策树个数。

根据前向分步算法，第步将要得到的提升树模型为：

其中， $H _ { t } ( x )$ 为当前模型。那么第轮迭代的目标是得到能最小化 ${H_t} \ left（x \ right）$ 的损失函数的第棵决策树 $h \left( x ; \Theta _ { t } \right)$ 的参数，即：

对于二类分类问题，只要把AdaBoost中的基分类器限定为二类分类树即可。可以说这时的提升树是AdaBoost的特殊情况。

对于回归问题，当采用平方误差损失函数 $( y - H ) ^ { 2 }$ 时，第次迭代的损失是：

当 $h\left( {x;{\Theta _t}} \right){\rm{ = }}y - {H_{t - 1}}(x){\rm{ = }}{r_t}$ 时，损失最小。也就是说，第次迭代的优化目标是拟合当前模型的残差。

3. 梯度提升决策树原理

在提升方法中，每次迭代的优化问题可以分为两部分：一、求叶结点区域；二、给定叶结点区域，求区域内最优拟合值。

对于第二个问题，它是一个简单的“定位”估计，最优解很容易得到；但对于第一个问题，当损失函数不是平方误差和指数损失，而是一般损失函数时，求解区域是困难的，最小化损失函数问题的简单、快速求解算法是不存在的。

针对这一问题，梯度提升决策树利用最速下降法来近似求解加法模型中的每一颗决策树，具体来说，就是在每次迭代中， 使新建的决策树都沿损失函数减少最快的方向——负梯度方向减少损失函数 。

当前模型的负梯度为：

当损失函数是平方误差时，当前 模型的负梯度就等于残差 ，沿负梯度方向减少损失函数就相当于拟合残差。

但当损失函数不是平方误差时， 负梯度就是残差的近似值 ，称为“ 广义残差或伪残差 ”。例如，当损失函数是绝对误差时，负梯度是残差的符号函数，因此在每次迭代时，决策树将拟合当前残差的符号。

总之， GBDT利用广义残差来拟合每一轮迭代中的回归树。

一些广泛应用的损失函数的梯度如下表：

下面介绍GBDT回归算法，也可以当做GBDT的通用算法。必须声明的是，无论是GBDT分类算法还是回归算法，弱学习器都是 回归树 ，这是由残差本质决定的。

输入：训练集 $D = \left\{ \left( x _ { i } , y _ { i } \right) \right\} _ { i = 1 } ^ { m }$ ，其中 $x _ { i } \in \chi \subseteq R ^ { d}$ ， $y _ { i } \in \mathcal { Y } \subseteq \mathbf { R }$ ；损失函数。

（1）初始化模型 $H _ { 0 } ( x )$ ，估计使损失函数最小化的常数值 $\gamma$ ，初始模型是只有一个根结点的树。

（2）对迭代轮次 ${t = 1,2，\ ldots，T}$

（a）对样本 $i = 1,2 , \cdots , m$ ，计算当前模型的广义残差：

（b）利用 $\left( {{x_i},{r_{ti}}} \right),i = 1,2, \ldots ,m$ 拟合一棵回归树，得到第棵树的叶结点区域 ${R_{tj}},j = 1,2, \cdots ,J$ ；

（c）对每个叶结点区域 ${R_{tj}},j = 1,2, \cdots ,J$ ，计算能使区域 ${R_{tj}}$ 损失函数最小化的最佳预测值 ${\gamma _{tj}}$ ：

（d）得到本轮迭代最佳拟合回归树：

（e）更新本轮迭代的加法模型：

（3）得到最终的强学习器：

输出：回归树 H ( x ) 。

5. 二元GBDT分类算法

在分类任务中，由于样本输出是离散值，无法从输出类别拟合残差，因此使用类别的预测概率值和真实概率值的差来当做残差。

GBDT分类算法的损失函数可以取指数损失函数和对数似然函数，如果选择指数损失函数，则GBDT退化为AdaBoost。因此我们这里只讨论对数似然损失函数。

二元分类的对数似然损失函数是：

负梯度为：

利用 $\left( {{x_i},{r_{ti}}} \right),i = 1,2, \ldots ,m$ 拟合一棵回归树，得到第棵树的叶结点区域 ${R_{tj}},j = 1,2, \cdots ,J$ ；

每个叶结点区域 ${R_{tj}},j = 1,2, \cdots ,J$ 的最佳预测值 ${\gamma _{tj}}$ 为：

由于上式比较难优化，我们用近似值代替：

除了负梯度计算和叶子节点最佳预测值计算不同，其他都与回归算法一致。

得到最终的模型 $H ( x ) = H _ { T } ( x ) = \sum _ { t = 1 } ^ { T } \sum _ { j = 1 } ^ { J } \gamma _ { t j } I \left( x \in R _ { t j } \right)$ 后，用来进行概率估计得到：

6. GBDT优缺点

1. 可以灵活处理混合型数据（异构特征）；

2. 强大的预测能力；

3. 在输出空间中对异常点的鲁棒性(通过具有鲁棒性的损失函数实现，如Huber损失函数和分位数损失函数)。

1. 在更大规模的数据集或复杂度更高的模型上的可扩展性差；

2. 由于提升算法的有序性，因此很难做到并行。

参考文献：

1. 《统计学习方法》第八章提升方法——李航

2. 《统计学习基础》第十章提升和加法树——Trevor Hastie等

3. 论文《Greedy Function Approximation: A Gradient Boosting Machine》——Jerome H. Friedman

4. 梯度提升树(GBDT)原理小结

5. GBDT原理详解

6. Scikit-learn 0.19.x 中文文档 Gradient Tree Boosting（梯度树提升）

梯度提升 决策树 （ GBDT ）1 基于残差学习的梯度提升树 2 梯度提升 决策树 （ GBDT ）3 算法实践梯度提升 决策树 （ GBDT ），在传统 机器学习 中算得上是TOP3的算法。 GBDT 使用的基学习器是CART 回归树，而且无论是回归还是分类，都使用的是回归树。为什么不使用 决策树 呢？因为 GBDT 每次迭代要拟合的是梯度值，也就是说样本标签是连续的，因此需要使用回归树。（对于 决策树 的构造原理可以参考我这篇文章） 1 基于残差学习的梯度提升树要想理解 GBDT ，我们先来看一下基于残差学习的梯度提升树 (即，基于残差学习的加法模型 1. 提升树 ¶ 梯度提升树（Grandient Boosting）是提升树（Boosting Tree）的一种改进算法，所以在讲梯度提升树之前先来说一下提升树。先来个通俗理解：假如有个人30岁，我们首先用20岁去拟合，发现损失有10岁，这时我们用6岁去拟合剩下的损失，发现差距还有4岁，第三轮我们用3岁拟合剩下的差距，差距就只有一岁了。如果我们的迭代轮数还没有完，可以继续迭代下面，每一轮迭代，拟合的岁数误差都会减小。最后将每次拟合的岁数加起来便是模型输出的结果。上面提到的残差是什么呢？ GBDT ，全称为Gradient Boosting Decision Tree，即梯度提升 决策树 ，是一种迭代的 决策树 算法，也被称作MART（Multiple Additive Regression Tree）。它通过将多个 决策树 （弱学习器）的结果进行累加来得到最终的预测输出，是集成学习算法的一种，具体属于Boosting类型。文章目录总结综述一、Regression Decision Tree：回归树二、Boosting Decision Tree：提升树算法三、Gradient Boosting Decision Tree：梯度提升 决策树 四、重要参数的意义及设置五、拓展回归树：用均方误差的最小二乘法作为选择特征、划分树节点的依据，构造回归树提升树：迭代多颗回归树，新树以上一棵树的残差来构造。最终结果是树相同位置节点值的和。梯度提升 决策树 ：在提升树的基础上，用梯度来替代残差构造新树。 GBDT (Gradi 提升树是以分类树或回归树为基本分类器的提升方法。提升树被认为是统计学习中性能最好的方法之一。提升方法实际采用。以 决策树 为基函数的提升方法称为提升树（boosting tree）。对 决策树 是，对 决策树 是。：线性可分训练数据集T{(x1y1x2y2xNyN)} 其中，xi∈XRnyi∈Yi12N；弱学习算法：提升树 fMx 不同问题的提升树学习算法，其主要区别在于使用的损失函数不同。梯度提升 决策树 （Gradient Boosting Decision Tree， GBDT ）算法是近年来被提及比较多的一个算法，这主要得益于其算法的性能，以及该算法在各类数据挖掘以及 机器学习 比赛中的卓越表现，有很多人对 GBDT 算法进行了开源代码的开发，比较火的是陈天奇的XGBoost和微软的LightGBM。一、监督学习1、监督学习的主要任务监督学习是 机器学习 算法中重要的一种，对于监督学习，假设有mm... GBDT （Gradient Boosting Decision Tree），全名叫梯度提升 决策树 ，是一种迭代的 决策树 算法，又叫 MART（Multiple Additive Regression Tree），它通过构造一组弱的学习器（树），并把多颗 决策树 的结果累加起来作为最终的预测输出。该算法将 决策树 与集成思想进行了有效的结合。本文的主要内容是基于Python 机器学习 基础教程 决策树 部分进行整理和总结。梯度提升回归树和随机森林一样，是一种 决策树 集成方法，通过合并多个 决策树 来构建一个更为强大的模型。虽然名字中有“ 回归 ”，但是该方法既能用于回归问题，也能用于分类问题，与随机森林不同的是，梯度提升回归树（ GBDT ）采用连续的方式构造树，每棵树都在试图修正前一棵树的错误。默认情况下，梯度提升回归树没有随机化，而是用到了... 1. 机器学习 之梯度提升 决策树 ( GBDT )_谓之小一的博客-CSDN博客_ 梯度提升 决策树 2. GBDT 的原理、公式推导、Python实现、可视化和应用 - 知乎 3. 《统计学习方法第二版》.李航