GBDT-梯度提升决策树

2023-12-20 18:26:23

梯度提升决策树(Gradient Boosting Decision Tree, GBDT)是一种基于boosting集成学习思想的加法模型,训练时采用前向分布算法进行贪婪学习,每次迭代都学习一棵CART树来拟合之前 t ? 1 t-1 t?1棵树的训练样本真实值的残差。

CART(Classification and Regression tree)

最小二乘回归算法
输入:训练数据集 D D D
输出:回归树 f ( x ) f(x) f(x)
在训练数据集所在的输入空间中,递归地将每个区域划分为两个子区域并决定每个子区域的输出值,构建二叉决策树:

  1. 选择最优切分变量 j j j与切分点 s s s,求解:
    min ? i , s [ min ? C 1 ∑ x i ∈ R 1 ( j , s ) ( y i ? c 1 ) 2 + min ? C 2 ∑ x i ∈ R 2 ( j , s ) ( y i ? c 2 ) 2 ] \min_{i,s} [\min_{C_{1}}\sum_{x_i\in R_1(j,s)}(y_i-c_1)^2+\min_{C_2}\sum_{x_i \in R_2(j,s)}(y_i-c_2)^2 ] i,smin?[C1?min?xi?R1?(j,s)?(yi??c1?)2+C2?min?xi?R2?(j,s)?(yi??c2?)2]
    遍历变量 j j j,对固定的切分变量 j j j扫描切分点 s s s,选择使上式达到最小值的对 ( j , s ) (j,s) (j,s)
  2. 用选择的对 ( j , s ) (j,s) (j,s)划分区域并决定相应的输出值:
    R 1 ( j , s ) = { x ∣ x ( j ) ≤ s } R_1(j,s)=\{x|x^{(j)}\le s\} R1?(j,s)={xx(j)s}
    R 1 ( j , s ) = { x ∣ x ( j ) > s } R_1(j,s)=\{x|x^{(j)}> s\} R1?(j,s)={xx(j)>s}
    C ^ m = 1 N m ∑ x i ∈ R 1 ( j , s ) y i , x ∈ R m , m = 1 , 2 \hat{C}_m=\frac{1}{N_m}\sum_{x_i\in R_1(j,s)}y_i, x\in R_m,m=1,2 C^m?=Nm?1?xi?R1?(j,s)?yi?,xRm?,m=1,2
  3. 继续对两个子区域调用步骤1和2,直至停止条件
  4. 将输入空间划分为 M M M个区域 R 1 , R 2 , . . . , R M R_1,R_2,...,R_M R1?,R2?,...,RM?,生成决策树:
    f ( x ) = ∑ m = 1 M C ^ m I ( x ∈ R m ) f(x)=\sum_{m=1}^{M}\hat{C}_mI(x\in R_m) f(x)=m=1M?C^m?I(xRm?)

GBDT(Gradient Boosting Decision Tree)

假设GBDT里有k个CART。其中第k个CART记为 T k ( X ) T_k(X) Tk?(X),前k个CART的预测值记为
f k ( x ) = ∑ i = 1 k T i ( x ) f_k(x)=\sum_{i=1}^{k}T_i(x) fk?(x)=i=1k?Ti?(x)
GBDT是一种加法模型,它把所有基础模型的预测值累加起来作为最终的预测值,可把前K个CART的预测值表示为一个递归的形式:
f k ( x ) = f k ? 1 ( x ) + T k ( x ) f_k(x)=f_{k-1}(x)+T_k(x) fk?(x)=fk?1?(x)+Tk?(x)
训练第k个CART时,最小化目标函数:
J = ∑ n = 1 N L ( y n , f k ( x n ) ) = ∑ n = 1 N L ( y n , f k ? 1 ( x ) + T k ( x ) ) J=\sum_{n=1}^{N}L(y_n,f_k(x_n))=\sum_{n=1}^{N}L(y_n,f_{k-1}(x)+T_k(x)) J=n=1N?L(yn?,fk?(xn?))=n=1N?L(yn?,fk?1?(x)+Tk?(x))
利用梯度下降法:
f k ( x n ) = f k ? 1 ( x n ) ? α ? J ? f k ? 1 ( x n ) f_k(x_n)=f_{k-1}(x_n)-\alpha \frac{\partial J}{\partial f_{k-1}(x_n)} fk?(xn?)=fk?1?(xn?)?α?fk?1?(xn?)?J?
T k ( x n ) = ? α ? J ? f k ? 1 ( x n ) T_k(x_n)=-\alpha \frac{\partial J}{\partial f_{k-1}(x_n)} Tk?(xn?)=?α?fk?1?(xn?)?J?
通常回归任务中用残差平方和作为目标函数
J = ∑ n = 1 N L ( y n , f k ( x n ) ) = ∑ n ? 1 N 1 2 ( y n ? f k ( x n ) ) 2 J=\sum_{n=1}^{N}L(y_n,f_k(x_n))=\sum_{n-1}^{N}\frac{1}{2}{(y_n-f_k(x_n))}^2 J=n=1N?L(yn?,fk?(xn?))=n?1N?21?(yn??fk?(xn?))2
因此有
T k ( x n ) = ? α ? J ? f k ? 1 ( x n ) = y n ? f k ? 1 ( x n ) T_k(x_n)=-\alpha \frac{\partial J}{\partial f_{k-1}(x_n)}=y_n-f_{k-1}(x_n) Tk?(xn?)=?α?fk?1?(xn?)?J?=yn??fk?1?(xn?)
也就是说,GBDT的每一颗CART树的任务,是拟合之前所有CART留下的残差。

文章来源:https://blog.csdn.net/PyDarren/article/details/135111765
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。