背景
决策树是一种基本的分类与回归方法。决策树模型具有分类速度快，模型容易可视化的解释，但是同时是也有容易发生过拟合，虽然有剪枝，但也是差强人意。
提升方法（boosting）在分类问题中，它通过改变训练样本的权重（增加分错样本的权重，减小分队样本的的权重），学习多个分类器，并将这些分类器线性组合，提高分类器性能。boosting数学表示为：
f(x)=w0+∑m=1Mwmϕm(x)
其中w是权重，
ϕ是弱分类器的集合，可以看出最终就是基函数的线性组合。
于是决策树与boosting结合产生许多算法，主要有提升树、GBDT等。本文主要是GBDT学习笔记。
Gradient Boosting
Gradient Boosting是一种Boosting的方法，它主要的思想是，每一次建立模型是在之前建立模型损失函数的梯度下降方向。损失函数是评价模型性能（一般为拟合程度+正则项），认为损失函数越小，性能越好。而让损失函数持续下降，就能使得模型不断改性提升性能，其最好的方法就是使损失函数沿着梯度方向下降（讲道理梯度方向上下降最快）。
Gradient Boost是一个框架，里面可以套入很多不同的算法。
提升树-boosting tree
以决策树为基函数的提升方法称为提升树，其决策树可以是分类树OR回归树。提升树模型可以表示为决策树的加法模型。
fM(x)=∑m=1MT(x;Θm)
其中，
T(x;Θm)表示决策树，
Θm
表示树的参数，M为树的个数。
回归问题提升树算法
输入：训练数据集
T={(x1,y1),(x2,y2),⋅⋅⋅,(xN,yN)},xi∈χ=Rn,yi∈γ={−1,+1}, i=1,2,⋅⋅⋅,N；
输出：提升树
fM(x)
-
初始化
f0(x)=0
-
对于
m=1,2,...M:
-
计算残差（后一棵树拟合前一颗树残差）：
rmi=yi−fm−1(xi)
-
拟合残差学习一个回归树，得到
T(x;Θm)
-
更新
fm(x)=fm−1(x)+T(x;Θm)
-
M次迭代之后得到提升树：
fM(x)=∑m=1MT(x;Θm)
Gradient Boosting Decision Tree
提升树的学习优化过程中，损失函数平方损失和指数损失时候，每一步优化相对简单，但对于一般损失函数优化的问题，Freidman提出了Gradient Boosting算法，其利用了损失函数的负梯度在当前模型的值
−[∂L(y,f(xi))∂f(xi)]f(x)=fm−1(x)
作为回归问题提升树算法的残差近似值，去拟合一个回归树。
算法
输入：训练数据集
T={(x1,y1),(x2,y2),⋅⋅⋅,(xN,yN)},xi∈χ=Rn,yi∈γ={−1,+1}, i=1,2,⋅⋅⋅,N；
输出：回归树
fM(x)
-
初始化
f0(x)=argminc∑i=1NL(yi,c)
-
对m=1,2,..M
-
对i=1,2,…,N，计算
rmi=−[∂L(y,f(xi))∂f(xi)]f(x)=fm−1(x)
-
对
rmi拟合一颗回归树，得到第m棵树的叶结点区域Rmj, j=1,2,...J，即一棵由J个叶子节点组成的树。
-
对
j=1,2,...J，计算
cmj=argminc∑xi∈RmjL(yi,fm−1(xi)+c)
2.2,2.3这一步相当于回归树递归在遍历所有切分变量j和切分点s找到最优j,s，然后在每个节点区域求最优的c。参考回归树生成算法
-
更新
fm(x)=fm−1(x)+∑j=1JcmjI(x∈Rmj)
-
得到回归树
f^(x)=fM(x)=∑m=1Mfm(x)=∑m=1M∑j=1JcmjI(x∈Rmj)
算法1步获得使得损失函数最小的常数估计值，是一个只有根节点的树。在2.1步计算损失函数的负梯度在当前模型的值，将它作为残差估计。在2.2步估计回归树的叶结点区域，来拟合残差的近似值。在2.3步利用线性搜索估计回归树叶结点区域的值，使损失函数最小化。2.4更新回归树。第3步获得输出的最终模型。
Shrinkage
Shrinkage的思想认为，每次走一小步逐渐逼近结果的效果，要比每次迈一大步很快逼近结果的方式更容易避免过拟合。即它不完全信任每一个棵残差树，它认为每棵树只学到了真理的一小部分，累加的时候只累加一小部分，通过多学几棵树弥补不足。
数学方程对比：
- 之前：fm(x)=fm−1(x)+∑j=1JcmjI(x∈Rmj)
- Shrinkage：fm(x)=fm−1(x)+step∗∑j=1JcmjI(x∈Rmj)
Shrinkage仍然以残差作为学习目标，但对于残差学习的结果，只累加一小部分，step一般取值0.001-0.01(非gradient的step)，使得各个树的残差是渐变而不是陡变的，即将大步切成了小步。Shrinkage能减少过拟合发生也是经验证明的，目前还没有看到从理论的证明。
总结
原始的boosting算法开始时，为每一个样本赋上一个权重值。在每一步训练中得到的模型，会使得数据点的估计有对有错，在每一步结束后，增加分错的点的权重，减少分对的点的权重，这样使得某些点如果老是被分错，那么就会被“严重关注”，也就被赋上一个很高的权重。然后等进行了N次迭代（由用户指定），将会得到N个简单的分类器（basic learner），然后我们将它们组合起来（比如说可以对它们进行加权、或者让它们进行投票等），得到一个最终的模型。
那么GBDT算法中并未有权重的改变，哪里有boosting思想 ？
Gradient Boosting与Boosting区别在于，每一计算的是为了减少上一次的残差，下一个模型主要在残差减少的梯度方上建立模型，使得残差往梯度方向上减少。
虽然不同，但是GBDT算法会更关注那些梯度比较大的样本，和Boosting思想类似。
附录
CSDN原文：http://blog.csdn.net/shine19930820/article/details/65633436
