GBDT梯度提升树

定义：

GBDT的全称是Gradient boosting decision tree,它是通过拟合负梯度Gradient boosting和决策回归树decision tree组合而成，该算法由多颗决策树构成，多颗决策树的结果加起来作为最终结论。让损失函数沿着梯度方向的下降。这个就是GDBT 的 GB的核心。GBDT 每轮迭代的时候，都去拟合损失函数在当前模型下的负梯度。（如果损失函数使用的是平方误差损失函数，则这个损失函数的负梯度就可以用残差来代替，以下所说的残差拟合，便是使用了平方误差损失函数）。

为什么使用回归树？

GDBT使用的树是CART回归树，尽管GDBT既可以用来作分类也可以作为回归，但是，该算法中使用的树都是回归树，因为GDBT每次拟合的都是梯度值，是有意义的连续值，比如一个人的岁数可以使10+5-3=12岁，但是男+女+男得到的结果是什么？根本没有意义。

回归树的每个节点都会生成一个预测值，该节点的预测值等于这个节点所有年龄的平均值，分支时一般使用最小化均方差即：

min(（每个人的年龄-预测值）*（每个人的年龄-预测值）/N)

这里怎么理解呢？被预测的人出错的越多，就表示错的越离谱，均方差就越大，每次都通过寻找最小化均方差就能找到靠谱的分支数据，直至分支到每一个叶子节点的值都唯一（基本不可能）或达到预设的终止条件则，若达到条件还不唯一就使用所有节点的平均值作为预测值。

注：（对于分类树一本使用基尼系数或者熵来判别最佳划分点，但是在决策树中，样本的标签是连续值，这个时候用熵之类的来描述就不合理了，所转移一般用平方误差来代替，他能很好的评判拟合程度）

回归树的生成（decision tree）

其实在GDBT中每一次的拟合都是一颗决策树的生成过程，下面来看回归树生成算法：

输入：数据集D

输出：回归树f(x)

在训练数据集所在的输入空间中，递归将每个区域划分为两个子域，构建二叉决策树。

（1）选择最优切分变量j与切分点s，求解：

公式1

遍历变量j扫描切分点s，选择使得公式1最小的对(j,s)

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

公式2

（3）重复公式1和公式2直至满足条件停止

（4）将空间划分为M个区域R1,R2,R3,...,Rm，生成决策树：

决策树生成公式

拟合负梯度(gradient boosting)

GDBT是提升树(boosting tree)的一种改进算法，如何理解提升树呢：

假如一个人的身高是180，我首先用150去拟合，这个时候就有误差30（残差），我再用20去拟合，这个时候误差为10我用8去拟合误差为2，这个时候距离真是身高就差2了如果这个时候迭代的论数还没结束就继续去迭代，每一次的迭代的误差都会减小。最后将每一次拟合的身高加起来就是最终的预测身高了。

拟合负梯度的由来：

首先看提升树的由来：

提升树算法

上述公式中的残差是什么？：

残差计算

这里损失函数使用的是平方损失，GBDT算法使用的就是损失函数的负梯度作为提升算法中的残差近视值。

首先计算梯度一般是对损失函数进行求导，所以第t论第i个样本损失函数的负梯度就是：

负梯度

使用平方损失：

平方损失

负梯度为：

负梯度

此时GDBT的负梯度就变成了残差，通俗的来说就是样本的真实值与预测值之间的误差，一般下一轮使用的真实值就是上一轮的平均误差值

GDBT算法原理：

首先GDBT是通过采用加法模型（即基函数的线性组合），以及不断减小训练过程产生的残差来达到将数据分类或者回归的算法。 GDBT通过多轮迭代,每轮迭代产生一个弱分类器，每个分类器在上一轮分类器的梯度（如果损失函数是平方损失函数，则梯度就是残差值）基础上进行训练。对弱分类器的要求一般是足够简单，并且是低方差和高偏差的。因为训练的过程是通过降低偏差来不断提高最终分类器的精度，（此处是可以证明的）。

GDBT算法