Gradient Boosting Decision Tree（GBDT）-梯度提升决策树

GBDT是集成学习的又一代表作，以boosting为基础的分部加法模型，活跃在各个应用领域，十分受欢迎。所以我们首先来了解一下boosting算法。

一、boosting

boosting是集成学习三大模式（bagging、stacking和boosting）之一。

boosting基本原理：

假设样本集{（xi, yi）} i = 1、...N，迭代H轮

1、选择样本集{（xi, yi）} i = 1、...N；

2、根据样本集训练CART弱分类器Gj；

3、分部加法得到Fj（x） = Fj-1（x） + Gj； 

原理图如下

二、GBDT

GBDT示意图

GBDT是一种梯度提升树算法，重心就在于用损失函数在Fm-1（x）处的负梯度去拟合上一轮输入与输出的差，并把它作为下一轮输入。

GBDT是分部加法模型；

假设迭代H轮，权值映射f(x)，f(x) = rh(x:a)，h（x:a） = I{x->R}： 

FH（x） = f1（x） + ...+fH(x);

Fm(x) = Fm-1(x) + fj(x) = Fm-1(x) + rmh(x:am)=Fm-1(x)+rmI{x->Rm};

GBDT目标函数：

obj = min sum(L(yi,F(xi))) i = 1、...N

F* = argmin(F) sum(L(yi,F)) i =1、...N

GBDT算法流程如下：

对于1，无约束优化这里采用泰勒一阶展开，对经验风险进行一阶泰勒展开，然后展开后经验风险的一阶导数等于0，得F0（x）；

对于3，求损失函数在Fm-1（x）处的逆梯度；

对于4，利用CART树得到am；

对于5，无约束优化这里采用泰勒二阶展开，对经验风险进行二阶泰勒展开，然后对展开后经验风险的一阶导数等于0，得到权系数；

对于6，这里还隐含了缩放过程

GBDT算法的优缺点：

优点：

1、预测精度高；

2、可以处理非线性数据；

3、对于低维数据效果很好；

缺点：

1、很难并行；

2、数据纬度较高的时候，计算量和复杂度都提升了。