提升树与GBDT的详细算法过程（建议收藏版）

ゝ一纸荒年。 2023-09-28 21:41 53阅读 0赞

GBDT的全称为：梯度提升决策树，英文为：（Gradient Boosting Decison Tree）。

**提升树核心思想：拟合残差**

怎么拟合残差呢？

首先第一步是使用`boosting`技术，对残差使用决策树进行拟合，比如我们常用的CART算法。第二步是使用加法模型，将拟合好的决策树相加。

### 一、提升树算法步骤 ###

输入： D = \{ ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯   , ( x N , y N ) \} D=\\\{(x\_1,y\_1),(x\_2,y\_2),\\cdots,(x\_N,y\_N)\\\} D=\{(x1,y1),(x2,y2),⋯,(xN,yN)\}

（1）初始化 f 0 ( x ) = 0 f\_0(x)=0 f0(x)=0；

（2）对于 m = 1 , 2 , ⋯   , M m=1,2,\\cdots,M m=1,2,⋯,M，针对每一个样本 ( x i , y i ) (x\_i,y\_i) (xi,yi)，计算残差：  
 r m i = y i − f m − 1 ( x i ) , i = 1 , 2 , ⋯   , N r\_\{mi\}=y\_i-f\_\{m-1\}(x\_i)\\quad ,i=1,2,\\cdots,N rmi=yi−fm−1(xi),i=1,2,⋯,N

（3）利用 \{ ( x i , r m i ) \} i = 1 , 2 , ⋯   , N \\\{(x\_i,r\_\{mi\})\\\}\_\{i=1,2,\\cdots,N\} \{(xi,rmi)\}i=1,2,⋯,N训练一个决策树（回归树），得到 T ( x ; Θ m ) T(x;\\Theta\_m) T(x;Θm)

（4）更新 f m ( x ) = f m − 1 ( x ) + T ( x ; Θ m ) f\_m(x)=f\_\{m-1\}(x)+T(x;\\Theta\_m) fm(x)=fm−1(x)\+T(x;Θm)

（5）完成以上迭代，得到提升树:  
 f M ( x ) = ∑ i = 1 M T ( x ; Θ m ) f\_M(x)=\\sum\_\{i=1\}^MT(x;\\Theta\_m) fM(x)=i=1∑MT(x;Θm)

其中， M M M表示决策树个数； R m i R\_\{mi\} Rmi表示残差。

### 二、GBDT算法步骤 ###

输入：训练数据集 D = \{ ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯   , ( x N , y N ) \} D=\\\{(x\_1,y\_1),(x\_2,y\_2),\\cdots,(x\_N,y\_N)\\\} D=\{(x1,y1),(x2,y2),⋯,(xN,yN)\}；损失函数为: L ( y , f ( x ) ) L(y,f(x)) L(y,f(x))。

（1）初始化:  
 f 0 ( x ) = arg ⁡ min ⁡ c ∑ i = 1 N L ( y i , c ) f\_0(x)=\\arg\\min\_\{c\}\\sum\_\{i=1\}^NL(y\_i,c) f0(x)=argcmini=1∑NL(yi,c)

（2）对于 m = 1 , 2 , ⋯   , M m=1,2,\\cdots,M m=1,2,⋯,M，针对每一个样本 ( x i , y i ) (x\_i,y\_i) (xi,yi)，计算残差：  
 r m i = − \[ ∂ L ( y i , f ( x i ) ) ∂ f ( x i ) \] f ( x ) = f m − 1 ( x )    , i = 1 , 2 , ⋯   , N r\_\{mi\}=-\[\\frac\{\\partial L(y\_i,f(x\_i))\}\{\\partial f(x\_i)\}\]\_\{f(x)=f\_\{m-1\}(x)\}\\;,i=1,2,\\cdots,N rmi=−\[∂f(xi)∂L(yi,f(xi))\]f(x)=fm−1(x),i=1,2,⋯,N

（3）利用 \{ ( x i , r m i ) \} i = 1 , 2 , ⋯   , N \\\{(x\_i,r\_\{mi\})\\\}\_\{i=1,2,\\cdots,N\} \{(xi,rmi)\}i=1,2,⋯,N训练出第 m m m棵决策树（回归树） T m T\_m Tm，其中叶节点划分的区域为: R m j    , j = 1 , 2 , ⋯   , J R\_\{mj\}\\;,j=1,2,\\cdots,J Rmj,j=1,2,⋯,J

（4）对于回归树 T m T\_m Tm的每一个叶结点，计算其输出值：  
 c m j = arg ⁡ min ⁡ c ∑ x i ∈ R m j L ( y i , f m − 1 ( x i ) + c )    , j = 1 , 2 , ⋯   , N c\_\{mj\}=\\arg\\min\_\{c\}\\sum\_\{x\_i\\in R\_\{mj\}\}L(y\_i,f\_\{m-1\}(x\_i)+c)\\;,j=1,2,\\cdots,N cmj=argcminxi∈Rmj∑L(yi,fm−1(xi)\+c),j=1,2,⋯,N

（5）更新:  
 f m ( x ) = f m − 1 ( x ) + ∑ j = 1 J c m j I ( x ∈ R m j ) f\_m(x)=f\_\{m-1\}(x)+\\sum\_\{j=1\}^Jc\_\{mj\}I(x\\in R\_\{mj\}) fm(x)=fm−1(x)\+j=1∑JcmjI(x∈Rmj)

（6）得到最终提升回归树：  
 f ( x ) ^ = f M ( x ) = ∑ m = 1 M ∑ j = 1 J c m j I ( x ∈ R m j ) \\hat\{f(x)\}=f\_M(x)=\\sum\_\{m=1\}^M\\sum\_\{j=1\}^Jc\_\{mj\}I(x\\in R\_\{mj\}) f(x)^=fM(x)=m=1∑Mj=1∑JcmjI(x∈Rmj)

输出：提升回归树 f ( x ) ^ \\hat\{f(x)\} f(x)^

### 三、两者之间的区别 ###

1.梯度提升回归树的残差使用负梯度来代替；

2.梯度提升回归树多了一步在叶子节点loss求最优值的计算，这里应该是为了降低优化误差，优化回归树的结果。