简单易学的机器学习算法——梯度提升决策树GBDT「建议收藏」

简单易学的机器学习算法——梯度提升决策树GBDT「建议收藏」梯度提升决策树(GradientBoostingDecisionTree,GBDT)算法是近年来被提及比较多的一个算法,这主要得益于其算法的性能,以及该算法在各类数据挖掘以及机器学习比赛中的卓越表现,有很多人对GBDT算法进行了开源代码的开发,比较火的是陈天奇的XGBoost和微软的LightGBM。一、监督学习1、监督学习的主要任务监督学习是机器学习算法中重要的一种,对于监督学习,假设有mm…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

梯度提升决策树(Gradient Boosting Decision Tree,GBDT)算法是近年来被提及比较多的一个算法,这主要得益于其算法的性能,以及该算法在各类数据挖掘以及机器学习比赛中的卓越表现,有很多人对GBDT算法进行了开源代码的开发,比较火的是陈天奇的XGBoost和微软的LightGBM。

1. 监督学习

1.1. 监督学习的主要任务

监督学习是机器学习算法中重要的一种,对于监督学习,假设有 m m m个训练样本:

{ ( X ( 1 ) , y ( 1 ) ) , ( X ( 2 ) , y ( 2 ) ) , ⋯   , ( X ( m ) , y ( m ) ) } \left \{ \left ( X^{\left ( 1 \right )},y^{\left ( 1 \right )} \right ),\left ( X^{\left ( 2 \right )},y^{\left ( 2 \right )} \right ),\cdots ,\left ( X^{\left ( m \right )},y^{\left ( m \right )} \right ) \right \} {
(X(1),y(1)),(X(2),y(2)),,(X(m),y(m))}

其中, X ( i ) = { x 1 ( i ) , x 2 ( i ) , ⋯   , x m ( i ) } X^{\left ( i \right )}=\left \{ x^{\left ( i \right )}_1,x^{\left ( i \right )}_2,\cdots ,x^{\left ( i \right )}_m \right \} X(i)={
x1(i),x2(i),,xm(i)}
称为第 i i i个样本的特征, y ( i ) y^{\left ( i \right )} y(i)称为第 i i i个样本的标签,样本标签可以为离散值,如分类问题;也可以为连续值,如回归问题。在监督学习中,利用训练样本训练出模型,该模型能够实现从样本特征 X ( i ) X^{\left ( i \right )} X(i)到样本标签 y ( i ) y^{\left ( i \right )} y(i)的映射,即:

X ( i ) → F y ( i ) X^{\left ( i \right )}\overset{F}{\rightarrow} y^{\left ( i \right )} X(i)Fy(i)

为了能够对映射 F ( X ) F\left ( X \right ) F(X)进行求解,通常对模型设置损失函数 L ( y , F ( X ) ) L\left ( y,F\left ( X \right ) \right ) L(y,F(X)),并求得在损失函数最小的情况下的映射为最好的映射:

F ∗ = a r g m i n F ( X )    L ( y , F ( X ) ) F^\ast =\underset{F\left ( X \right )}{argmin}\; L\left ( y,F\left ( X \right ) \right ) F=F(X)argminL(y,F(X))

对于一个具体的问题,如线性回归问题,其映射函数的形式为:

F ( X ; W ) = W X = w 0 + w 1 x 1 + w 2 x 2 + ⋯ + w n x n F\left ( X;W \right )=WX=w_0+w_1x_1+w_2x_2+\cdots +w_nx_n F(X;W)=WX=w0+w1x1+w2x2++wnxn

此时对于最优映射函数 F ( X ; W ) F\left ( X;W \right ) F(X;W)的求解,实质是对映射函数中的参数 W W W的求解。对于参数的求解方法有很多,如梯度下降法。

1.2. 梯度下降法

梯度下降法(Gradient Descent,GD)算法是求解最优化问题最简单、最直接的方法。梯度下降法是一种迭代的优化算法,对于优化问题:

m i n    f ( w ) min\; f\left ( w \right ) minf(w)

其基本步骤为:

  • 随机选择一个初始点 w 0 w_0 w0
  • 重复以下过程:
    • 决定下降的方向: d i = − ∂ ∂ w f ( w ) ∣ w i d_i=-\frac{\partial }{\partial w}f\left ( w \right )\mid _{w_i} di=wf(w)wi
    • 选择步长 ρ \rho ρ
    • 更新: w i + 1 = w i + ρ ⋅ d i w_{i+1}=w_i+\rho \cdot d_i wi+1=wi+ρdi
  • 直到满足终止条件

梯度下降法的具体过程如下图所示:

在这里插入图片描述

由以上的过程,我们可以看出,对于最终的最优解 w ∗ w^\ast w,是由初始值 w 0 w_0 w0经过 M M M代的迭代之后得到的,在这里,设 w 0 = d 0 w_0=d_0 w0=d0,则 w ∗ w^\ast w为:

w ∗ = ∑ i = 0 M ρ i ⋅ d i w^\ast =\sum_{i=0}^{M}\rho _i\cdot d_i w=i=0Mρidi

1.3. 在函数空间的优化

以上是在指定的函数空间中对最优函数进行搜索,那么,能否直接在函数空间(function space)中查找到最优的函数呢?根据上述的梯度下降法的思路,对于模型的损失函数 L ( y , F ( X ) ) L\left ( y,F\left ( X \right ) \right ) L(y,F(X)),为了能够求解出最优的函数 F ∗ ( X ) F^\ast\left ( X \right ) F(X),首先,设置初始值为:

F 0 ( X ) = f 0 ( X ) F_0\left ( X \right )=f_0\left ( X \right ) F0(X)=f0(X)

以函数 F ( X ) F\left ( X \right ) F(X)作为一个整体,对于每一个样本 X ( i ) X^{\left ( i\right )} X(i),都存在对应的函数值 F ( X ( i ) ) F\left ( X^{\left ( i\right )} \right ) F(X(i))。与梯度下降法的更新过程一致,假设经过 M M M代,得到最有的函数 F ∗ ( X ) F^\ast\left ( X \right ) F(X)为:

F ∗ ( X ) = ∑ i = 0 M f i ( X ) F^\ast\left ( X \right )=\sum_{i=0}^{M}f_i\left ( X \right ) F(X)=i=0Mfi(X)

其中, f i ( X ) f_i\left ( X \right ) fi(X)为:

f i ( X ) = − ρ i g m ( X ) f_i\left ( X \right )=-\rho _ig_m\left ( X \right ) fi(X)=ρigm(X)

其中, g m ( X ) = [ ∂ L ( y , F ( X ) ) ∂ F ( X ) ] F ( X ) = F m − 1 ( X ) g_m\left ( X \right )=\left [ \frac{\partial L\left ( y,F\left ( X \right ) \right )}{\partial F\left ( X \right )} \right ]_{F\left ( X \right )=F_{m-1}\left ( X \right )} gm(X)=[F(X)L(y,F(X))]F(X)=Fm1(X)

由上述的过程可以得到函数 F ( X ) F\left ( X \right ) F(X)的更新过程:

F m ( X ) = ∑ i = 0 m f i ( X ) F_m\left ( X \right )=\sum_{i=0}^{m}f_i\left ( X \right ) Fm(X)=i=0mfi(X)

与上面类似,函数 f ( X ) f\left ( X \right ) f(X)是由参数 a \textbf{a} a决定的,即:

f ( X ) = − ρ ⋅ h ( X ; a ) f\left ( X \right )=-\rho \cdot h\left ( X;\textbf{a} \right ) f(X)=ρh(X;a)

2. Boosting

2.1. 集成方法之Boosting

Boosting方法是集成学习中重要的一种方法,在集成学习方法中最主要的两种方法为Bagging和Boosting,在Bagging中,通过对训练样本重新采样的方法得到不同的训练样本集,在这些新的训练样本集上分别训练学习器,最终合并每一个学习器的结果,作为最终的学习结果,Bagging方法的具体过程如下图所示:

在这里插入图片描述

在Bagging方法中,最重要的算法为随机森林Random Forest算法。由以上的图中可以看出,在Bagging方法中, b b b个学习器之间彼此是相互独立的,这样的特点使得Bagging方法更容易并行。与Bagging方法不同,在Boosting算法中,学习器之间是存在先后顺序的,同时,每一个样本是有权重的,初始时,每一个样本的权重是相等的。首先,第 1 1 1个学习器对训练样本进行学习,当学习完成后,增大错误样本的权重,同时减小正确样本的权重,再利用第 2 2 2个学习器对其进行学习,依次进行下去,最终得到 b b b个学习器,最终,合并这 b b b个学习器的结果,同时,与Bagging中不同的是,每一个学习器的权重也是不一样的。Boosting方法的具体过程如下图所示:

在这里插入图片描述

在Boosting方法中,最重要的方法包括:AdaBoostGBDT

2.2. Gradient Boosting

由上图所示的Boosting方法中,最终的预测结果为 b b b个学习器结果的合并:

f ( X ) = ∑ j = 1 b θ j φ j ( X ) f\left ( X \right )=\sum_{j=1}^{b}\theta _j\varphi _j\left ( X \right ) f(X)=j=1bθjφj(X)

这与上述的在函数空间中的优化类似:

F m ( X ) = ∑ i = 0 m − ρ i ⋅ h ( X ; a i ) F_m\left ( X \right )=\sum_{i=0}^{m}-\rho _i\cdot h\left ( X;\textbf{a}_i \right ) Fm(X)=i=0mρih(X;ai)

根据如上的函数空间中的优化可知,每次对每一个样本的训练的值为:

y ˉ i = [ ∂ L ( y i , F ( X ( i ) ) ) ∂ F ( X ( i ) ) ] F ( X ) = F m − 1 ( X ) \bar{y}_i=\left [ \frac{\partial L\left ( y_i,F\left ( X^{\left ( i \right )} \right ) \right )}{\partial F\left ( X^{\left ( i \right )} \right )} \right ]_{F\left ( X \right )=F_{m-1}\left ( X \right )} yˉi=[F(X(i))L(yi,F(X(i)))]F(X)=Fm1(X)

上建立模型,由于上述是一个求解梯度的过程,因此也称为基于梯度的Boost方法,其具体过程如下所示:

在这里插入图片描述

3. Gradient Boosting Decision Tree

在上面简单介绍了Gradient Boost框架,梯度提升决策树Gradient Boosting Decision Tree是Gradient Boost框架下使用较多的一种模型,在梯度提升决策树中,其基学习器是分类回归树CART,使用的是CART树中的回归树。

3.1. 分类回归树CART

分类回归树CART算法是一种基于二叉树的机器学习算法,其既能处理回归问题,又能处理分类为题,在梯度提升决策树GBDT算法中,使用到的是CART回归树算法,对于CART树算法的更多信息,可以参考简单易学的机器学习算法——分类回归树CART

对于一个包含了 m m m个训练样本的回归问题,其训练样本为:

{ ( X ( 1 ) , y ( 1 ) ) , ( X ( 2 ) , y ( 2 ) ) , ⋯   , ( X ( m ) , y ( m ) ) } \left \{ \left ( X^{\left ( 1 \right )},y^{\left ( 1 \right )} \right ),\left ( X^{\left ( 2 \right )},y^{\left ( 2 \right )} \right ),\cdots ,\left ( X^{\left ( m \right )},y^{\left ( m \right )} \right ) \right \} {
(X(1),y(1)),(X(2),y(2)),,(X(m),y(m))}

其中, X ( i ) X^{\left ( i \right )} X(i) n n n维向量,表示的是第 i i i个样本的特征, y ( i ) y^{\left ( i \right )} y(i)为样本的标签,在回归问题中,标签 y ( i ) y^{\left ( i \right )} y(i)为一系列连续的值。此时,利用训练样本训练一棵CART回归树:

  • 开始时,CART树中只包含了根结点,所有样本都被划分在根结点上:

在这里插入图片描述
此时,计算该节点上的样本的方差(此处要乘以 m m m),方差表示的是数据的波动程度。那么,根节点的方差的 m m m倍为:

s 2 ⋅ m = ( y ( 1 ) − y ˉ ) 2 + ( y ( 2 ) − y ˉ ) 2 + ⋯ + ( y ( m ) − y ˉ ) 2 s^2\cdot m=\left ( y^{\left ( 1 \right )}-\bar{y} \right )^2+\left ( y^{\left ( 2 \right )}-\bar{y} \right )^2+\cdots +\left ( y^{\left ( m \right )}-\bar{y} \right )^2 s2m=(y(1)yˉ)2+(y(2)yˉ)2++(y(m)yˉ)2

其中, y ˉ \bar{y} yˉ为标签的均值。此时,从 n n n维特征中选择第 j j j维特征,从 m m m个样本中选择一个样本的值: x j x_j xj作为划分的标准,当样本 i i i的第 j j j维特征小于等于 x j x_j xj时,将样本划分到左子树中,否则,划分到右子树中,通过以上的操作,划分到左子树中的样本个数为 m 1 m_1 m1,划分到右子树的样本的个数为 m 2 = m − m 1 m_2=m-m_1 m2=mm1,其划分的结果如下图所示:

在这里插入图片描述

那么,什么样本的划分才是当前的最好划分呢?此时计算左右子树的方差之和: s 1 2 ⋅ m 1 + s 2 2 ⋅ m 2 s_1^2\cdot m_1+s_2^2\cdot m_2 s12m1+s22m2

s 1 2 ⋅ m 1 + s 2 2 ⋅ m 2 = ∑ X ( i ) ∈ l e f t ( y ( i ) − y ˉ 1 ) 2 + ∑ X ( j ) ∈ r i g h t ( y ( j ) − y ˉ 2 ) 2 s_1^2\cdot m_1+s_2^2\cdot m_2=\sum_{X^{\left ( i \right )}\in left}\left ( y^{\left ( i \right )}-\bar{y}_1 \right )^2+\sum_{X^{\left ( j \right )}\in right}\left ( y^{\left ( j \right )}-\bar{y}_2 \right )^2 s12m1+s22m2=X(i)left(y(i)yˉ1)2+X(j)right(y(j)yˉ2)2

其中, y ˉ 1 \bar{y}_1 yˉ1为左子树中节点标签的均值,同理, y ˉ 2 \bar{y}_2 yˉ2为右子树中节点标签的均值。选择其中 s 1 2 ⋅ m 1 + s 2 2 ⋅ m 2 s_1^2\cdot m_1+s_2^2\cdot m_2 s12m1+s22m2最小的划分作为最终的划分,依次这样划分下去,直到得到最终的划分,划分的结果为:

在这里插入图片描述

注意:对于上述最优划分标准的选择,以上的计算过程可以进一步优化。

首先,对于 s 2 ⋅ m s^2\cdot m s2m

s 2 ⋅ m = ∑ X ( i ) ( y ( i ) − y ˉ ) 2 = ∑ X ( i ) ( ( y ( i ) ) 2 − 2 y ( i ) ⋅ y ˉ + ( y ˉ ) 2 ) = ∑ X ( i ) ( y ( i ) ) 2 − 2 m ( ∑ X ( i ) y ( i ) ) 2 + 1 m ( ∑ X ( i ) y ( i ) ) 2 = ∑ X ( i ) ( y ( i ) ) 2 − 1 m ( ∑ X ( i ) y ( i ) ) 2 \begin{align*} s^2\cdot m &=\sum_{X^{\left ( i \right )}}\left ( y^{\left ( i \right )}-\bar{y} \right )^2\\ &= \sum_{X^{\left ( i \right )}}\left ( \left ( y^{\left ( i \right )} \right )^2-2y^{\left ( i \right )}\cdot \bar{y}+\left ( \bar{y} \right )^2\right )\\ &=\sum_{X^{\left ( i \right )}}\left ( y^{\left ( i \right )} \right )^2-\frac{2}{m}\left ( \sum_{X^{\left ( i \right )}} y^{\left ( i \right )} \right )^2+\frac{1}{m}\left ( \sum_{X^{\left ( i \right )}} y^{\left ( i \right )} \right )^2 \\ &= \sum_{X^{\left ( i \right )}}\left ( y^{\left ( i \right )} \right )^2-\frac{1}{m}\left ( \sum_{X^{\left ( i \right )}} y^{\left ( i \right )} \right )^2 \end{align*} s2m=X(i)(y(i)yˉ)2=X(i)((y(i))22y(i)yˉ+(yˉ)2)=X(i)(y(i))2m2(X(i)y(i))2+m1(X(i)y(i))2=X(i)(y(i))2m1(X(i)y(i))2

而对于 s 1 2 ⋅ m 1 + s 2 2 ⋅ m 2 s_1^2\cdot m_1+s_2^2\cdot m_2 s12m1+s22m2

s 1 2 ⋅ m 1 + s 2 2 ⋅ m 2 = ∑ X ( i ) ∈ l e f t ( y ( i ) − y ˉ 1 ) 2 + ∑ X ( j ) ∈ r i g h t ( y ( j ) − y ˉ 2 ) 2 = ∑ X ( i ) ∈ l e f t ( ( y ( i ) ) 2 − 2 y ( i ) ⋅ y ˉ 1 + ( y ˉ 1 ) 2 ) + ∑ X ( j ) ∈ r i g h t ( ( y ( j ) ) 2 − 2 y ( j ) ⋅ y ˉ 2 + ( y ˉ 2 ) 2 ) \begin{align*} s_1^2\cdot m_1+s_2^2\cdot m_2 &= \sum_{X^{\left ( i \right )}\in left}\left ( y^{\left ( i \right )}-\bar{y}_1 \right )^2+\sum_{X^{\left ( j \right )}\in right}\left ( y^{\left ( j \right )}-\bar{y}_2 \right )^2\\ &= \sum_{X^{\left ( i \right )}\in left}\left ( \left ( y^{\left ( i \right )} \right )^2-2y^{\left ( i \right )}\cdot \bar{y}_1+\left ( \bar{y}_1 \right )^2\right )+\sum_{X^{\left ( j \right )}\in right}\left ( \left ( y^{\left ( j \right )} \right )^2-2y^{\left ( j \right )}\cdot \bar{y}_2+\left ( \bar{y}_2 \right )^2 \right ) \end{align*} s12m1+s22m2=X(i)left(y(i)yˉ1)2+X(j)right(y(j)yˉ2)2=X(i)left((y(i))22y(i)yˉ1+(yˉ1)2)+X(j)right((y(j))22y(j)yˉ2+(yˉ2)2)

= ∑ X ( i ) ( y ( i ) ) 2 − 2 m 1 ( ∑ X ( i ) ∈ l e f t y ( i ) ) 2 + 1 m 1 ( ∑ X ( i ) ∈ l e f t y ( i ) ) 2 − 2 m 2 ( ∑ X ( j ) ∈ r i g h t y ( j ) ) 2 + 1 m 2 ( ∑ X ( j ) ∈ r i g h t y ( j ) ) 2 = ∑ X ( i ) ( y ( i ) ) 2 − 1 m 1 ( ∑ X ( i ) ∈ l e f t y ( i ) ) 2 − 1 m 2 ( ∑ X ( j ) ∈ r i g h t y ( j ) ) 2 \begin{align*} &=\sum_{X^{\left ( i \right )}}\left ( y^{\left ( i \right )} \right )^2-\frac{2}{m_1}\left ( \sum_{X^{\left ( i \right )}\in left} y^{\left ( i \right )} \right )^2+\frac{1}{m_1}\left ( \sum_{X^{\left ( i \right )}\in left} y^{\left ( i \right )} \right )^2 \\ &- \frac{2}{m_2}\left ( \sum_{X^{\left ( j \right )}\in right} y^{\left ( j \right )} \right )^2+\frac{1}{m_2}\left ( \sum_{X^{\left ( j \right )}\in right} y^{\left ( j \right )} \right )^2\\ &= \sum_{X^{\left ( i \right )}}\left ( y^{\left ( i \right )} \right )^2-\frac{1}{m_1}\left ( \sum_{X^{\left ( i \right )}\in left} y^{\left ( i \right )} \right )^2-\frac{1}{m_2}\left ( \sum_{X^{\left ( j \right )}\in right} y^{\left ( j \right )} \right )^2 \end{align*} =X(i)(y(i))2m12
X(i)lefty(i)
2
+m11
X(i)lefty(i)
2
m22
X(j)righty(j)
2
+m21
X(j)righty(j)
2
=X(i)(y(i))2m11
X(i)lefty(i)
2
m21
X(j)righty(j)
2

通过以上的过程,我们发现,划分前,记录节点的值为:

1 m ( ∑ X ( i ) y ( i ) ) 2 \frac{1}{m}\left ( \sum_{X^{\left ( i \right )}} y^{\left ( i \right )} \right )^2 m1(X(i)y(i))2

当划分后,两个节点的值的和为:

1 m 1 ( ∑ X ( i ) ∈ l e f t y ( i ) ) 2 + 1 m 2 ( ∑ X ( j ) ∈ r i g h t y ( j ) ) 2 \frac{1}{m_1}\left ( \sum_{X^{\left ( i \right )}\in left} y^{\left ( i \right )} \right )^2+\frac{1}{m_2}\left ( \sum_{X^{\left ( j \right )}\in right} y^{\left ( j \right )} \right )^2 m11
X(i)lefty(i)
2
+
m21
X(j)righty(j)
2

最好的划分,对应着两个节点的值的和的最大值。

3.2. GBDT——二分类

在梯度提升决策树GBDT中,通过定义不同的损失函数,可以完成不同的学习任务,二分类是机器学习中一类比较重要的分类算法,在二分类中,其损失函数为:

L ( y , F ) = l o g ( 1 + e x p ( − 2 y F ) ) ,    y ∈ { − 1 , 1 } L\left ( y,F \right )=log\left ( 1+exp\left ( -2yF \right ) \right ),\; y\in\left \{ -1,1 \right \} L(y,F)=log(1+exp(2yF)),y{
1,1}

套用上面介绍的GB框架,得到下述的二分类GBDT的算法:

在这里插入图片描述

在构建每一棵CART回归树的过程中,对一个样本的预测值应与 y ~ \tilde{y} y~尽可能一致,对于 y ~ \tilde{y} y~,其计算过程为:

y ~ ( i ) = − [ ∂ L ( y ( i ) , F ( X ( i ) ) ) ∂ F ( X ( i ) ) ] F ( X ) = F m − 1 ( X ) = − [ ∂ l o g ( 1 + e x p ( − 2 y ( i ) F ( X ( i ) ) ) ) ∂ F ( X ( i ) ) ] F ( X ) = F m − 1 ( X ) = − [ 1 1 + e x p ( − 2 y ( i ) F ( X ( i ) ) ) ⋅ e x p ( − 2 y ( i ) F ( X ( i ) ) ) ⋅ ( − 2 y ( i ) ) ] F ( X ) = F m − 1 ( X ) \begin{align*} \tilde{y}^{\left (i \right )} &= -\left [ \frac{\partial L\left ( y^{\left ( i \right )},F\left ( X^{\left ( i \right )} \right ) \right )}{\partial F\left ( X^{\left ( i \right )} \right )} \right ]_{F\left ( X \right )=F_{m-1}\left ( X \right )}\\ &= -\left [ \frac{\partial log\left ( 1+exp\left ( -2y^{\left ( i \right )}F\left ( X^{\left ( i \right )} \right ) \right ) \right )}{\partial F\left ( X^{\left ( i \right )} \right )} \right ]_{F\left ( X \right )=F_{m-1}\left ( X \right )}\\ &= -\left [ \frac{1}{1+exp\left ( -2y^{\left ( i \right )}F\left ( X^{\left ( i \right )} \right ) \right )}\cdot exp\left ( -2y^{\left ( i \right )}F\left ( X^{\left ( i \right )} \right ) \right )\cdot \left ( -2y^{\left ( i \right )} \right ) \right ]_{F\left ( X \right )=F_{m-1}\left ( X \right )} \end{align*} y~(i)=[F(X(i))L(y(i),F(X(i)))]F(X)=Fm1(X)=[F(X(i))log(1+exp(2y(i)F(X(i))))]F(X)=Fm1(X)=[1+exp(2y(i)F(X(i)))1exp(2y(i)F(X(i)))(2y(i))]F(X)=Fm1(X)

= 2 y ( i ) ⋅ e x p ( − 2 y ( i ) F ( X ( i ) ) ) 1 + e x p ( − 2 y ( i ) F ( X ( i ) ) ) F ( X ) = F m − 1 ( X ) = 2 y ( i ) 1 + e x p ( 2 y ( i ) F m − 1 ( X ( i ) ) ) \begin{align*} &=\frac{2y^{\left ( i \right )}\cdot exp\left ( -2y^{\left ( i \right )}F\left ( X^{\left ( i \right )} \right ) \right )}{1+exp\left ( -2y^{\left ( i \right )}F\left ( X^{\left ( i \right )} \right ) \right )}_{F\left ( X \right )=F_{m-1}\left ( X \right )}\\ &= \frac{2y^{\left ( i \right )}}{1+exp\left ( 2y^{\left ( i \right )}F_{m-1}\left ( X^{\left ( i \right )} \right ) \right )} \end{align*} =1+exp(2y(i)F(X(i)))2y(i)exp(2y(i)F(X(i)))F(X)=Fm1(X)=1+exp(2y(i)Fm1(X(i)))2y(i)

y ~ \tilde{y} y~(通常有的地方称为残差,在这里,更准确的讲是梯度下降的方向)上构建CART回归树。最终将每一个训练样本划分到对应的叶子节点中,计算此时该叶子节点的预测值:

γ j m = a r g m i n γ ∑ X ( i ) ∈ R j m l o g ( 1 + e x p ( − 2 y ( i ) ( F m − 1 ( X ( i ) ) + γ ) ) ) \gamma _{jm}=\underset{\gamma }{argmin}\sum _{X^{\left ( i \right )}\in R_{jm}}log\left ( 1+exp\left ( -2y^{\left ( i \right )}\left ( F_{m-1}\left ( X^{\left ( i \right )} \right )+\gamma \right ) \right ) \right ) γjm=γargminX(i)Rjmlog(1+exp(2y(i)(Fm1(X(i))+γ)))

由Newton-Raphson迭代公式可得:

γ j m = ∑ X ( i ) ∈ R j m y ~ ( i ) ∑ X ( i ) ∈ R j m ∣ y ~ ( i ) ∣ ( 2 − ∣ y ~ ( i ) ∣ ) \gamma _{jm}=\frac{\sum _{X^{\left ( i \right )}\in R_{jm}}\tilde{y}^{\left (i \right )}}{\sum _{X^{\left ( i \right )}\in R_{jm}}\left | \tilde{y}^{\left (i \right )} \right |\left ( 2-\left | \tilde{y}^{\left (i \right )} \right | \right )} γjm=X(i)Rjm
y~(i)
(2
y~(i)
)
X(i)Rjmy~(i)

以参考文献3 Idiots’ Approach for Display Advertising Challenge中提供的代码为例:

  • GBDT训练的主要代码为:
void GBDT::fit(Problem const &Tr, Problem const &Va)
{ 
   
        bias = calc_bias(Tr.Y); //用于初始化的F

        std::vector<float> F_Tr(Tr.nr_instance, bias), F_Va(Va.nr_instance, bias);

        Timer timer;
        printf("iter time tr_loss va_loss\n");
        // 开始训练每一棵CART树
        for(uint32_t t = 0; t < trees.size(); ++t)
        { 
   
                timer.tic();

                std::vector<float> const &Y = Tr.Y;
                std::vector<float> R(Tr.nr_instance), F1(Tr.nr_instance); // 记录残差和F

                #pragma omp parallel for schedule(static)
                for(uint32_t i = 0; i < Tr.nr_instance; ++i)
                        R[i] = static_cast<float>(Y[i]/(1+exp(Y[i]*F_Tr[i]))); //计算残差,或者称为梯度下降的方向

                // 利用上面的残差值,在此函数中构造一棵树
                trees[t].fit(Tr, R, F1); // 分类树的生成

                double Tr_loss = 0;
                // 用上面训练的结果更新F_Tr,并计算log_loss
                #pragma omp parallel for schedule(static) reduction(+: Tr_loss)
                for(uint32_t i = 0; i < Tr.nr_instance; ++i)
                { 
   
                        F_Tr[i] += F1[i];
                        Tr_loss += log(1+exp(-Y[i]*F_Tr[i]));
                }
                Tr_loss /= static_cast<double>(Tr.nr_instance);

                // 用上面训练的结果预测测试集,打印log_loss
                #pragma omp parallel for schedule(static)
                for(uint32_t i = 0; i < Va.nr_instance; ++i)
                { 
   
                        std::vector<float> x = construct_instance(Va, i);
                        F_Va[i] += trees[t].predict(x.data()).second;
                }

                double Va_loss = 0;
                #pragma omp parallel for schedule(static) reduction(+: Va_loss)
                for(uint32_t i = 0; i < Va.nr_instance; ++i)
                        Va_loss += log(1+exp(-Va.Y[i]*F_Va[i]));
                Va_loss /= static_cast<double>(Va.nr_instance);

                printf("%4d %8.1f %10.5f %10.5f\n", t, timer.toc(), Tr_loss, Va_loss);
                fflush(stdout);
        }
}
  • CART回归树的训练代码为:
void CART::fit(Problem const &prob, std::vector<float> const &R, std::vector<float> &F1){ 
   
	uint32_t const nr_field = prob.nr_field; // 特征的个数
	uint32_t const nr_sparse_field = prob.nr_sparse_field;
	uint32_t const nr_instance = prob.nr_instance; // 样本的个数

	std::vector<Location> locations(nr_instance); // 样本信息

	#pragma omp parallel for schedule(static)
	for(uint32_t i = 0; i < nr_instance; ++i)
		locations[i].r = R[i]; // 记录每一个样本的残差

	for(uint32_t d = 0, offset = 1; d < max_depth; ++d, offset *= 2){ 
   // d:深度

		uint32_t const nr_leaf = static_cast<uint32_t>(pow(2, d)); // 叶子节点的个数


		std::vector<Meta> metas0(nr_leaf); // 叶子节点的信息

		for(uint32_t i = 0; i < nr_instance; ++i){ 
   

			Location &location = locations[i]; //第i个样本的信息
 
			if(location.shrinked)
				continue;

			Meta &meta = metas0[location.tnode_idx-offset]; //找到对应的叶子节点

			meta.s += location.r; //残差之和
			++meta.n;
		}

		std::vector<Defender> defenders(nr_leaf*nr_field); //记录每一个叶节点的每一维特征
		std::vector<Defender> defenders_sparse(nr_leaf*nr_sparse_field);
		// 针对每一个叶节点

		for(uint32_t f = 0; f < nr_leaf; ++f){ 
   

			Meta const &meta = metas0[f]; // 叶子节点

			double const ese = meta.s*meta.s/static_cast<double>(meta.n); //该叶子节点的ese

			for(uint32_t j = 0; j < nr_field; ++j)
				defenders[f*nr_field+j].ese = ese;

			for(uint32_t j = 0; j < nr_sparse_field; ++j)
				defenders_sparse[f*nr_sparse_field+j].ese = ese;
		}
		
		std::vector<Defender> defenders_inv = defenders;

		std::thread thread_f(scan, std::ref(prob), std::ref(locations),
				std::ref(metas0), std::ref(defenders), offset, true);
		std::thread thread_b(scan, std::ref(prob), std::ref(locations),
				std::ref(metas0), std::ref(defenders_inv), offset, false);
		scan_sparse(prob, locations, metas0, defenders_sparse, offset, true);
		thread_f.join();
		thread_b.join();

		// 找出最佳的ese,scan里是每个字段的最佳ese,这里是所有字段的最佳ese,赋值给相应的tnode
		for(uint32_t f = 0; f < nr_leaf; ++f){ 
   
			// 对于每一个叶节点都找到最好的划分
			Meta const &meta = metas0[f];
			double best_ese = meta.s*meta.s/static_cast<double>(meta.n);

			TreeNode &tnode = tnodes[f+offset];
			for(uint32_t j = 0; j < nr_field; ++j){ 
   

				Defender defender = defenders[f*nr_field+j];//每一个叶节点都对应着所有的特征

				if(defender.ese > best_ese)
				{ 
   
					best_ese = defender.ese;
					tnode.feature = j;
					tnode.threshold = defender.threshold;
				}

				defender = defenders_inv[f*nr_field+j];
				if(defender.ese > best_ese)
				{ 
   
					best_ese = defender.ese;
					tnode.feature = j;
					tnode.threshold = defender.threshold;
				}
			}
			for(uint32_t j = 0; j < nr_sparse_field; ++j)
			{ 
   
				Defender defender = defenders_sparse[f*nr_sparse_field+j];
				if(defender.ese > best_ese)
				{ 
   
					best_ese = defender.ese;
					tnode.feature = nr_field + j;
					tnode.threshold = defender.threshold;
				}
			}
		}

		// 把每个instance都分配给树里的一个叶节点下
		#pragma omp parallel for schedule(static)
		for(uint32_t i = 0; i < nr_instance; ++i){ 
   

			Location &location = locations[i];
			if(location.shrinked)
				continue;

			uint32_t &tnode_idx = location.tnode_idx;
			TreeNode &tnode = tnodes[tnode_idx];
			if(tnode.feature == -1){ 
   
				location.shrinked = true;
			}else if(static_cast<uint32_t>(tnode.feature) < nr_field){ 
   

				if(prob.Z[tnode.feature][i].v < tnode.threshold)
					tnode_idx = 2*tnode_idx; 
				else
					tnode_idx = 2*tnode_idx+1; 
			}else{ 
   
				uint32_t const target_feature = static_cast<uint32_t>(tnode.feature-nr_field);
				bool is_one = false;
				for(uint64_t p = prob.SJP[i]; p < prob.SJP[i+1]; ++p) 
				{ 
   
					if(prob.SJ[p] == target_feature)
					{ 
   
						is_one = true;
						break;
					}
				}
				if(!is_one)
					tnode_idx = 2*tnode_idx; 
				else
					tnode_idx = 2*tnode_idx+1; 
			}
		}
	}
	
	// 用于计算gamma
	std::vector<std::pair<double, double>> 
		tmp(max_tnodes, std::make_pair(0, 0));
	for(uint32_t i = 0; i < nr_instance; ++i)
	{ 
   
		float const r = locations[i].r;
		uint32_t const tnode_idx = locations[i].tnode_idx;
		tmp[tnode_idx].first += r;
		tmp[tnode_idx].second += fabs(r)*(1-fabs(r));
	}

	for(uint32_t tnode_idx = 1; tnode_idx <= max_tnodes; ++tnode_idx)
	{ 
   
		double a, b;
		std::tie(a, b) = tmp[tnode_idx];
		tnodes[tnode_idx].gamma = (b <= 1e-12)? 0 : static_cast<float>(a/b);
	}

#pragma omp parallel for schedule(static)
	for(uint32_t i = 0; i < nr_instance; ++i)
		F1[i] = tnodes[locations[i].tnode_idx].gamma;// 重新更新F1的值
}

在参考文献A simple GBDT in Python中提供了Python实现的GBDT的版本。

参考文献

[1] Greedy Function Approximation: A Gradient Boosting Machine

[2] Gradient boosting machines, a tutorial

[3] 3 Idiots’ Approach for Display Advertising Challenge

[4] 《统计机器学习》

[5] GBDT:梯度提升决策树

[6] 随机森林&GBDT算法以及在MLlib中的实现

[7] A simple GBDT in Python

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/182738.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 低成本高利润产品(高精度测量)

    1,TM7705是完整的16位低成本Σ-Δ模数转换器(ADC);该芯片完全兼容AD7705,程序可以直接替换;2,TM7705两路全差分输入通道,在定制比率应用器件时,差分基准电压输入还能提供极大的灵活性;3,三线串行接口;4,SPI®,QSPI?,MICROWIRE?,DSP兼容;5,SCLK上可接受施密特触发器输入;6,提供模拟输入缓冲;7,工作电压2.7V至3.3V或4.75V…

  • Android MediaPlayer Error/Info Code

    Android MediaPlayer Error/Info Code

  • mysql优化 面试_数据库优化方案整理

    mysql优化 面试_数据库优化方案整理点赞是一种积极的生活态度!有支持才有动力!微信搜索公众号【达摩克利斯之笔】获取更多资源,文末有二维码!前言数据库优化是一个老生常谈的问题,刚入门的小白或者工作N年的光头对这个问题应该都不陌生,你要面试一个中高级工程师那么他就想”哥俩好”一样那么粘,面试官肯定会问这个问题,这篇文章我们就和它哥俩好!而且这个问题就是一个送分题,数据库的优化方案基本就是那些,答案也都是固定的,大家只要好好…

    2022年10月27日
  • Idea激活码永久有效Idea2020.2.3激活码教程-持续更新,一步到位「建议收藏」

    Idea激活码永久有效Idea2020.2.3激活码教程-持续更新,一步到位「建议收藏」Idea激活码永久有效2020.2.3激活码教程-Windows版永久激活-持续更新,Idea激活码2020.2.3成功激活

  • pycharm中文安装包

    pycharm中文安装包pycharm中文安装包如果是自定义安装的,那么他的相应地址应该是下面提供中文安装包链接:https://pan.baidu.com/s/1pf3B-kwZVRwzrWBxj-oZ7g提取码:hduy  这也是俺自己正在用的pycharm中文安装包Pycharm中文安装包一般来说都是放在C:\…

  • Delphi XE5中的新增内容

    Delphi XE5中的新增内容DelphiXE5中的新增内容DelphiXE5是所有Delphi开发人员的必须备升级,并且是来自Embarcadero的获奖的、多设备应用开发解决方案的最新版本。使用DelphiXE5的新特性,以交付应用Android、iOS、Windows和OSX。以PC机、平板电脑和智能手机为目标,更轻松地与更多数据连接-等等!DelphiXE5中的新特性针对设

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号