GBDT（梯度提升决策树）算法（详细版）
一、前言
通过之前的文章GBDT算法（简明版）对GBDT的过程做了大概的讲解，我们可以了解到GBDT是一种迭代的决策树算法，由多棵决策树组成，所有树的结论累加起来做最终答案。GBDT是一个应用很广泛的算法，可以用于分类，回归和特征选择，特别是用于和其他算法进行模型组成时，如logistic+GBDT,该算法在很多数据上都有不错的效果，GBDT还有其他的名字，如MART，GBRT和Tree Net等。
二、基础知识
2.1 决策树(DT)
决策树这种算法有着很多良好的特性，比如说训练时间复杂度较低，预测的过程比较快速，模型容易展示（容易将得到的决策树做成图片展示出来）等。但是同时，单决策树又有一些不好的地方，比如说容易over-fitting，虽然有一些方法，如剪枝可以减少这种情况，但是还是不够的。模型组合（比如说有Boosting，Bagging等）与决策树相关的算法比较多，这些算法最终的结果是生成N(可能会有几百棵以上）棵树，这样可以大大的减少单决策树带来的毛病，有点类似于三个臭皮匠等于一个诸葛亮的做法，虽然这几百棵决策树中的每一棵都很简单（相对于C4.5这种单决策树来说），但是他们组合起来确是很强大。
决策树分为两大类，分类树和回归树，分类树是我们比较熟悉的决策树，用于分类标签值，如阴天/晴天，性别预测，垃圾邮件分类，而回归树用于预测实数值，如明天的温度、用户的年龄和网页的相关程度，也就是分类树是定性的，回归树是定量的。
GBDT的核心在于累加所有树的结果作为最终结果，比如对年龄的累加来预测年龄，而分类树的结果显然是没办法累加的，所以GBDT中的树是回归树，不是分类树。
2.2 boosting提升方法
adaboost其实是boosting算法的特例，因为adaboost可以表示为boosting的前向分布算法(Forward stagewise additive modeling)的一个特例，boosting可以表示为：
其中的w是权重，Φ是弱分类器(回归器)的集合,其实就是一个加法模型(即基函数的线性组合)，前向分布算法实际上是一个贪心算法，也就是在每一步求解弱分类器Φ(m)和其参数w(m)的时候不去修改之前已经求好的分类器和参数：
以上就是提升方法（之前向分布算法）的大致结构了，可以看到其中存在变数的部分其实就是极小化损失函数 这关键的一步了，如何选择损失函数决定了算法的最终效果。几个常见的boosting：
三、Gradient Boost (GB)
GB其实是一个框架，里面可以套入很多不同的算法。Gradient Boost与传统的Boost的区别是，每一次的计算是为了减少上一次的残差(residual)，而为了消除残差，我们可以在残差减少的梯度(Gradient)方向上建立一个新的模型。所以说，在Gradient Boost中，每个新的模型的建立是为了使得之前模型的残差往梯度方向减少，与传统Boost对正确、错误的样本进行加权有着很大的区别。我们设F(x,P)是分类函数，P是参数集。将加法函数延伸成如下格式:
上式h(x;a)是基函数，是对输入变量x的单参数化函数,其中a={a1,a2,...,am}。在不同的基函数中，a代表着不同的意思，比如本文的选择基函数CART中，每个函数h(x;am)是表示一棵小的回归树。回归树中参数am表示树的划分变量，划分位置和每棵树中叶子结点的均值等。
对于上式两个参数的求解，是通过优化损失函数求的。
以上可解决方案是利用Greedy Stagewise方法，
然后得到最终分类函数：
上面选用了梯度下降法（是一种线搜索方法）来优化目标值，该方法在之前讲解logistic算法中有详细讲解，可查看前面有关logistic了解。求最小值取负梯度方法为最优下降方向，即：
因此上面上个参数可通过优化如下式求的：
和
可以看到，参数am是对梯度方向进行最小二乘法拟合,即优化参数am,使得构建的下一个基函数（如m-1到m个）能够最接近负梯度方向（最优下降方向）。pm则根据损失函数L的不同的得到不同的算法。对于Gradient Boost算法的伪算法如下：
7. endFor
end Algorithm
四、应用
4.1 损失函数为最小二乘法
那么残差则为：
那么LS_Boost伪算法表示如下：
还有更多的损失函数的不同，可以得到相应的Gradient Boost算法，其中常见的如下
4.2 回归树
当基函数选用的是回归树时，即本文的提到的算法GBDT。在此之前，我们假定每个基函数是由J个结点组成的回归树，对于回归树需要理解为对特征空间的分割，讲解决策树算法文章时，已有提及。那么回归树模型的加法模型可以表示成如下：
上式中l(.)是指示函数，表示如果x在空间Rj中则为1，否则为0。bj是回归树结点上的值。其实就是对应Gradient Boost伪算法中的通过最小二乘法得到的am参数，那么对于回归树，对应Gradient Boost算法的为：
上式可以更新为
其中，
因此对于GBDT算法的伪代码可以表示为如下：
上面伪算法2的意思是利用梯度值rim和输入x构建一棵回归树，回归树将划分出Rjm个空间。同样我们会根据损失L（.）的不同得到不同的GBDT算法，如LS_TreeBoost,LAD_TreeBoost（Least absolute deviation）等。上面也就是GBDT算法的整个框架了，总之所谓Gradient就是去拟合Loss function的梯度，将其作为新的弱回归树加入到总的算法中即可。
五、正则化（regularization）
通常，对训练集拟合太紧密会导致模型泛化能力的下降，正则化通过约束拟合过程能够减小过拟合的影响。常用的技术手段是通过控制决策树M的深度和缩减（Shrinkage）Gredient Boost。
在基函数选用决策树中，增加M值能够减小训练集的误差，但是太大会导致过拟合现象。最佳值M能够通过模型选择方法来估计，如使用独立测试集或交叉验证方法。
而缩减的方法，是算法每次只学习一点点来减小单个特征对整体的影响，修改Gradient Boost的更新规则为：
参数v称为学习率，通常学习率会选择较小的值，小于0.1能够提高算法的泛化能力，但是越小的学习率也会增加算法的迭代次数。
六、总结
本文简单介绍的boost提升方法和讲解了Gredient Boost框架和Gredient Boost框架的应用GBDT,并且介绍了提高算法泛化能力的方法，正则化。还有一些内容本文没有提及，比如Gredient Boost中M回归问题，二分类和M分类的应用，还有其他的一些损失函数相关的应用。如果有兴趣可以参考Friedman大牛的文章：Greedy function approximation : A Gradient Boosting Machine。
PS:文章一些算法的伪代码来自不同教材，个别参数不一致，但是意思是一样的。
参考内容：
http://blog.csdn.net/dark_scope/article/details/24863289
Greedy function approximation : A Gradient Boosting Machine。
李航：《统计学习方法》
免责声明：本文系网络转载。版权归原作者所有。如涉及版权，请联系删除！