最近做的创新项目终于要结项了，做了一个针对交通数据的时序预测模型，其中一个很重要的组成部件就是梯度提升树GBDT了。近几年在数据挖掘比赛中屡屡斩获奖项的XGBoost与LightGBM都是基于GBDT演算法开发的，这里总结一下^_^

PS：材料参考是李航老师的《统计学习方法》如有错误以书上为准

封面： 电影《秒速五厘米》

1. CART回归树

GBDT是一个集成模型，可以看做是很多个基模型的线性相加，其中的基模型就是CART回归树。

CART树是一个决策树模型，与普通的ID3，C4.5相比，CART树的主要特征是，他是一颗二分树，每个节点特征取值为「是」和「不是」。举个例子，在ID3中如果天气是一个特征，那么基于此的节点特征取值为「晴天」、「阴天」、「雨天」，而CART树中就是「不是晴天」与「是晴天」。

这样的决策树递归的划分每个特征，并且在输入空间的每个划分单元中确定唯一的输出。

1.1 回归树生成

输入：训练数据集D={(x1,y1),(x2,y2),....,(xn,yn)}

输入：一颗回归树 f(x)=sum_{m=1}^{M}{hat{c}_mI(xin R_m)}

一个回归树对应的输入空间的一个划分，假设已经将输入空间划分为M个单元R1,R2,R3....Rm，并且每个单元都有固定的输出值cm，其中I为判别函数。

当输入空间确定时，可以用平方误差来表示回归树在训练数据上的预测误差：

loss=sum_{x_iin R_m}{(y_i - f(x_i))^2}

则知道单元Rm上的最优输出值就是Rm内所有样本xi对应yi的均值。（可以自己求导推一推）

问题是如何对输入空间进行划分？这里和决策树一样，选择的是遍历所有特征，选择最优的特征作为划分，具体的方法是选择第j个变数x^j和它的取值s作为切分变数与切分点，并定义两个区域

R1 = {x|x^j<=s} and R2 = {x|x^j > s}

如果特征是连续变数，那么方法可以是

R1 = {x|x^j==s} and R2 = {x|x^j != s}

然后寻找最优的变数j和最优切分点s，具体的求解

min_{j,s}[min_{c_1}sum_{x_iin R_1}{(y_i-c_1)^2+minc_2}sum_{x_iin R_2}{(y_i-c_2)^2}]

其实就是遍历所有j，s找到本次的最佳划分区域了。然后对每个区域递归这个划分过程，直到满足条件为止。

多说两句，如果是分类树的话就比较麻烦了，一般定义目标函数为基尼指数或者交叉信息熵。

1.2 回归树剪枝

根据奥卡姆剃刀原理，为了使模型有更准确的预测，我们要让模型变得尽量简单，对于决策树来说就是要做剪枝处理。

剪枝的损失函数可以如下表示：

C_a(T)=C(T)+alpha|T|

其中C(T)为对训练数据的误差，|T|为树的节点数量，其中alpha类似于一个turning parameter，调节的是到底要精准度还是要模型的简单性。（过拟合与欠拟合）

具体的演算法如下，先从整体树T0开始，对内部任意节点t，比较以t作为单节点树的损失与t作为根节点树的损失，如果单节点比下面一棵树还要好，就给剪掉。剪完后的树继续重复此过程。

2. GBDT模型

GBDT模型是一个集成模型，是很多CART树的线性相加。

GBDT模型可以表示为以下形式，我们约定f---t-(x)表示第t轮的模型，ht(x)表示第t颗决策树，模型定义如下：

f_t(x)=sum_{t=1}^{T}{h_t(x)}

提升树采用前向分步演算法。第t步的模型由第t-1步的模型形成，可以写成：

f_t(x)=f_{t-1}(x)+h_t(x)

损失函数自然定义为这样的：

L(f_t(x),y)=L(f_{t-1}+h_t(x),y)

虽然整体思路都挺清晰的，但是怎么确定第t步该加上一颗什么样的树确是个大问题。针对这个问题， Freidman提出了用损失函数的负梯度来拟合本轮损失的近似值，进而拟合一个CART回归树。即每次需要拟合的是模型的负梯度。第t轮的第i个样本的损失函数的负梯度表示为:

r_{t,i}=-[frac{delta L(y,f(x_i))}{delta f(x_i)}]

那天看了这个公式后，我整个人都蒙蔽了，说好了GBDT树每一步是在拟合上一步的残差呢？为什么成了拟合模型的负梯度了，拟合梯度是什么鬼啊，梯度不是一个方向吗为什么你们要拟合他？（哭唧唧）

后来终于想清楚，tm的d((y-f(x))^2) / d(f(x))不就是 y-f(x)不就是残差吗！！！啊啊啊啊啊啊啊啊啊！！！

这里可以借用SGD的观点看一看，每一步的树相当于是往梯度方向前进一步，这样不考虑残差，也挺好，嘻嘻。

总之，我们可以光明正大的这样写了：

r_{t,i}=-[frac{delta L(y,f(x_i))}{delta f(x_i)}]=y_i-f_{m-1}(x_i)

利用(xi, rti) (i=1,2,...m),我们可以拟合一颗CART回归树，得到了第t颗回归树，其对应的叶节点区域Rtj, j=1,2,...,J。其中J为叶子节点的个数。

针对每一个叶子节点里的样本，我们求出使损失函数最小，也就是拟合叶子节点最好的的输出值ctj如下(注意这里的yi是真实值，不是残差)：

c_{t,j}=argminsum_{x_iin R_{t,j}}{L(y_i,f_{t-1}(x_i)+c)}

此时本轮的决策树拟合函数就得到了：

h_t(x)=sum_{j=1}^{J}{c_{t,j}I(xin R_{t,j})}

然后本轮的强学习器也就得到了：

f_t(x)=f_{t-1}(x)+sum_{j=1}^{J}{c_{t,j}I(xin R_{t,j})}

之后一直迭代下去，直到损失函数收敛，完工！


推荐阅读：
相关文章