机器学习笔记20——集成/提升（Boosting）系列算法之提升树(BDT) 算法原理以及python实现

发布时间：2025-01-06 14:45

学习编程语言如Java或Python，提升算法应用能力 #生活技巧# #工作学习技巧# #数字技能提升#

提升树引言1、概述2、提升树模型3、提升树算法3.1 分类问题的提升树算法3.2 回归问题的提升树算法

引言

\quad \quad 在集成学习原理一文中，简单的介绍了根据个体学习器学习方式不同划分的两大类集成学习方法；在Boosting方法中介绍了其核心思想；在Adaboost算法一文中,介绍了Boosting家族的一个重要算法Adaboost，回顾一下

集成方法：集成方法，是一种提高弱分类算法准确度的方法，将多个弱分类算法(也叫做基学习器)以一定的集成方式集合在一起，然后再将弱分类器的结果以一定的融合策略融合成一个结果，作为最终的结果输出。

boosting算法：是集成学习算法的一种，核心思想是：
1）基学习器之间存在强依赖关系，每一个基分类器是在前一个基分类器的基础之上生成。具体实现方法跟基学习器有关；
2）将所有基学习器结果进行线性加权求和，作为最终结果输出；
3）是一个加法模型，故优化方法采用前向分步算法。

Adaboost算法：是Boosting家族的一个算法，核心思想：
1）基学习器采用单层决策树；
2）基学习器之间存在强依赖关系，每一个基学习器是在前一个基学习器的基础之上生成，具体实现方式是：提高被弱分类器错分样本的权值，降低正分样本的权值，作为下一轮基本分类器的训练样本。
3）将所有基学习器结果进行线性加权求和，作为最终结果输出；
4）是一个加法模型，故优化方法采用前向分步算法。

接下来，看一看Boosting家族中另一个常用的的算法BDT。

1、概述

\quad \quad 提升树，又称提升决策树（BDT，Boosting Decision Tree），是以分类树或回归树为基本分类器的提升方法。

2、提升树模型

\quad \quad 以决策树为基函数的提升方法称为提升（决策）树（BDT）。

对分类问题决策树是二叉分类树；对回归问题决策树是二叉回归树

提升决策树模型可以表示为决策树的加法模型：
f M ( x ) = ∑ m = 1 M T ( x ; Θ m ) (1.1) f_M(x)=\sum_{m=1}^M T\left(x;\Theta_m\right) \tag{1.1} fM(x)=m=1∑MT(x;Θm)(1.1)
其中， T ( x ; Θ m ) T\left(x;\Theta_m\right) T(x;Θm)表示决策树； Θ m \Theta_m Θm为决策树的参数； M M M为树的个数。

3、提升树算法

提升(决策)树采用前向分步算法。首先确定初始提升决策树 f 0 ( x ) = 0 f_0\left(x\right)=0 f0(x)=0，第 m m m步的模型是
f m ( x ) = f m − 1 ( x ) + T ( x ; Θ m ) (1.2) f_m\left(x\right)=f_{m-1}\left(x\right)+T\left(x;\Theta_m\right) \tag{1.2} fm(x)=fm−1(x)+T(x;Θm)(1.2)
其中， f m − 1 ( x ) f_{m-1}\left(x\right) fm−1(x)为当前模型，通过经验风险极小化确定下一棵决策树的参数 Θ m \Theta_m Θm，
Θ ^ m = arg ⁡ min ⁡ Θ m ∑ i = 1 N L ( y i , f m − 1 ( x i ) + T ( x i ; Θ m ) ) (1.3) \hat{\Theta}_m=\mathop{\arg\min}_{\Theta_m}\sum_{i=1}^N L\left(y_i,f_{m-1}\left(x_i\right)+T\left(x_i;\Theta_m\right)\right) \tag{1.3} Θ^m=argminΘmi=1∑NL(yi,fm−1(xi)+T(xi;Θm))(1.3)

针对不同问题的提升树学习算法，其主要区别在于使用的损失函数不同。包括用平方误差损失函数的回归问题，用指数损失函数的分类问题，以及用一般损失函数的一般决策问题。

3.1 分类问题的提升树算法

\quad \quad 对于二类分类问题来说，提升树算法只需将AdaBoost二类分类算法中的基本分类器限制为二类分类树即可。

输入：训练数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , … , ( x N , y N ) } T=\{\left(x_1,y_1\right),\left(x_2,y_2\right),\dots,\left(x_N,y_N\right)\} T={(x1,y1),(x2,y2),…,(xN,yN)}；其中， x i ∈ χ ⊆ R n x_i\in\chi\subseteq R^n xi∈χ⊆Rn , y i ∈ γ = { − 1 , + 1 } y_i\in\gamma=\{-1,+1\} yi∈γ={−1,+1} ；弱学习算法即弱学习器为二类分类树；
输出：最终分类器G(x)
（1）初始化训练数据的权值分布
D 1 = ( w 11 , . . . , w 1 i , . . . , w 1 N ) , w 1 i = 1 N , i = 1 , 2 , . . . , N D_1=(w_{11},...,w_{1i},...,w_{1N}),w_{1i}=\frac1N,i=1,2,...,N D1=(w11,...,w1i,...,w1N),w1i=N1,i=1,2,...,N
（2）对 m = 1 , 2 , … , M m=1,2,\dots,M m=1,2,…,M
（a）使用具有权值分布 D m D_m Dm的训练数据集学习，得到基分类器
G m ( x ) : χ → { − 1 , + 1 } G_m(x):\chi\rightarrow\{-1,+1\} Gm(x):χ→{−1,+1}
（b）计算 G m ( x ) G_m(x) Gm(x)在训练数据集上的分类误差率——Q(1)
e m = P ( G m ( x i ) ≠ y i ) = ∑ i = 1 N w m i I ( G m ( x i ) ≠ y i ) (8.1) e_m=P(G_m(x_i)\neq y_i)=\sum_{i=1}^Nw_{mi}I(G_m(x_i)\neq y_i)\tag{8.1} em=P(Gm(xi)=yi)=i=1∑NwmiI(Gm(xi)=yi)(8.1)
（c）计算 G m ( x ) G_m(x) Gm(x)的系数——Q（2）
α m = 1 2 l o g 1 − e m e m (8.2) \alpha_m=\frac12log\frac{1-e_m}{e_m}\tag{8.2} αm=21logem1−em(8.2)
这里的对数是自然对数, α m \alpha_m αm表示 G m ( x ) G_m(x) Gm(x)在最终分类器中的重要性。【当 e m ≤ 1 2 e_m\leq\frac12 em≤21时， α m ≥ 0 \alpha_m\geq0 αm≥0,并且 α m \alpha_m αm随着 e m e_m em的减小而增大，所以分类误差率越小的基分类器在最终分类器中的作用越大。】
（d）更新训练数据集的权值分布——Q(3)
D m + 1 = ( w m + 1 , 1 , . . . , w m + 1 , i , . . . , w m + 1 , N ) (8.3) D_{m+1}=(w_{m+1,1},...,w_{m+1,i},...,w_{m+1,N})\tag{8.3} Dm+1=(wm+1,1,...,wm+1,i,...,wm+1,N)(8.3) w m + 1 , i = w m i Z m e x p ( − α m y i G m ( x i ) ) , i = 1 , 2 , . . . , N (8.4) w_{m+1,i}=\frac{w_{mi}}{Z_m}exp(-\alpha_my_iG_m(x_i)),i=1,2,...,N\tag{8.4} wm+1,i=Zmwmiexp(−αmyiGm(xi)),i=1,2,...,N(8.4)
这里， Z m Z_m Zm是规范化因子
Z m = ∑ i = 1 N w m i e x p ( − α m y i G m ( x i ) ) (8.5) Z_m=\sum_{i=1}^Nw_{mi}exp(-\alpha_my_iG_m(x_i))\tag{8.5} Zm=i=1∑Nwmiexp(−αmyiGm(xi))(8.5)
它使 D m + 1 D_m+1 Dm+1成为一个概率分布
（3）构建基本分类器的线性组合
f ( x ) = ∑ i = 1 m α m G m ( x ) (8.6) f\left(x\right)=\sum_{i=1}^m\alpha_mG_m(x)\tag{8.6} f(x)=i=1∑mαmGm(x)(8.6)
得到最终分类器——Q（4） G ( x ) = s i g n ( f ( x ) ) = s i g n ( ∑ i = 1 m α m G m ( x ) ) (8.7) G(x)=sign(f(x))=sign(\sum_{i=1}^m\alpha_mG_m(x))\tag{8.7} G(x)=sign(f(x))=sign(i=1∑mαmGm(x))(8.7)

3.2 回归问题的提升树算法

已知训练数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , … ( x N , y N ) } T=\{\left(x_1,y_1\right),\left(x_2,y_2\right),\dots\left(x_N,y_N\right)\} T={(x1,y1),(x2,y2),…(xN,yN)}， x i ∈ X ⊆ R n x_i\in\mathcal{X}\subseteq\mathbb{R}^n xi∈X⊆Rn， X \mathcal{X} X为输入空间， y i ∈ Y ⊆ R y_i\in\mathcal{Y}\subseteq\mathbb{R} yi∈Y⊆R， Y \mathcal{Y} Y为输出空间。如果将输入空间 X \mathcal{X} X划分为 J J J个互不相交的区域 R 1 , R 2 , … , R J R_1,R_2,\dots,R_J R1,R2,…,RJ，并且在每个区域上确定输出的常量 c j c_j cj，那么回归树可表示为
T ( x ; Θ ) = ∑ j = 1 J c j I ( x ∈ R j ) (2.4) T\left(x;\Theta\right)=\sum_{j=1}^J c_j I\left(x\in R_j\right) \tag{2.4} T(x;Θ)=j=1∑JcjI(x∈Rj)(2.4)
其中，参数 Θ = { ( R 1 , c 1 ) , ( R 2 , c 2 ) , … , ( R J , c J ) } \Theta=\{\left(R_1,c_1\right),\left(R_2,c_2\right),\dots,\left(R_J,c_J\right)\} Θ={(R1,c1),(R2,c2),…,(RJ,cJ)}表示回归树的区域划分和各区域上的常量值。 J J J是决策树的复杂度即叶子结点个数。

回归问题提升树使用以下前向分步算法：
f 0 ( x ) = 0 f m ( x ) = f m − 1 ( x ) + T ( x ; Θ m ) , m = 1 , 2 , … , M f M ( x ) = ∑ m = 1 M T ( x ; Θ m ) f_0 \left(x \right)=0\\ f_m\left(x\right)=f_{m-1}\left(x\right)+T\left(x;\Theta_m\right),\quad m=1,2,\dots,M\\ f_M\left(x\right)=\sum_{m=1}^M T\left(x;\Theta_m\right) f0(x)=0fm(x)=fm−1(x)+T(x;Θm),m=1,2,…,MfM(x)=m=1∑MT(x;Θm)
在前向分步算法的第 m m m步，给定当前模型 f m − 1 ( x ) f_{m-1}\left(x\right) fm−1(x)，需要求解
Θ ^ m = arg ⁡ min ⁡ Θ m ∑ i = 1 N L ( y i , f m − 1 ( x i ) + T ( x i ; Θ m ) ) \hat{\Theta}_m=\mathop{\arg\min}_{\Theta_m}\sum_{i=1}^N L\left(y_i,f_{m-1}\left(x_i\right)+T\left(x_i;\Theta_m\right)\right) Θ^m=argminΘmi=1∑NL(yi,fm−1(xi)+T(xi;Θm))
得到 Θ ^ m \hat{\Theta}_m Θ^m，即第 m m m棵树的参数。

当采用平方误差损失函数时，
L ( y , f ( x ) ) = ( y − f ( x ) ) 2 L\left(y,f\left(x\right)\right)=\left(y-f\left(x\right)\right)^2 L(y,f(x))=(y−f(x))2
其损失变为
L ( y , f m − 1 ( x ) + T ( x ; Θ m ) ) = [ y − f m − 1 ( x ) − T ( x ; Θ m ) ] 2 = [ r − T ( x ; Θ m ) ] 2 L\left(y,f_{m-1}\left(x\right)+T\left(x;\Theta_m\right)\right) \\ =\left[y-f_{m-1}\left(x\right)-T\left(x;\Theta_m\right)\right]^2 \\ =\left[r-T\left(x;\Theta_m\right)\right]^2 L(y,fm−1(x)+T(x;Θm))=[y−fm−1(x)−T(x;Θm)]2=[r−T(x;Θm)]2
其中，
r = y − f m − 1 ( x ) (2.5) r=y-f_{m-1}\left(x\right) \tag{2.5} r=y−fm−1(x)(2.5)
是当前模型拟合数据的残差（residual）。对回归问题的提升决策树，只需要简单地拟合当前模型的残差。回归问题的提升树算法如下：

算法8.3 回归问题的提升决策树算法
输入：训练数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , … , ( x N , y N ) } , x i ∈ X ⊆ R n , y i ∈ Y ⊆ R T=\{\left(x_1,y_1\right),\left(x_2,y_2\right),\dots,\left(x_N,y_N\right)\},x_i\in\mathcal{X}\subseteq\mathbb{R}^n,y_i\in\mathcal{Y}\subseteq\mathbb{R} T={(x1,y1),(x2,y2),…,(xN,yN)},xi∈X⊆Rn,yi∈Y⊆R；
输出：提升决策树 f M ( x ) f_M\left(x\right) fM(x)
（1）初始化 f 0 ( x ) = 0 f_0\left(x\right)=0 f0(x)=0
（2）对 m = 1 , 2 , … , M m=1,2,\dots,M m=1,2,…,M
（a）按照式（2.5）计算残差
r m i = y i − f m − 1 ( x i ) , i = 1 , 2 , … , N r_{mi}=y_i-f_{m-1}\left(x_i\right), \quad i=1,2,\dots,N rmi=yi−fm−1(xi),i=1,2,…,N
（b)拟合残差 r m i r_{mi} rmi学习一个回归树，得到 T ( x ; Θ m ) T\left(x;\Theta_m\right) T(x;Θm)
（c）更新 f m ( x ) = f m − 1 ( x ) + T ( x ; Θ m ) f_m\left(x\right)=f_{m-1}\left(x\right)+T\left(x;\Theta_m\right) fm(x)=fm−1(x)+T(x;Θm)
（3）得到回归提升决策树
f M ( x ) = ∑ m = 1 M T ( x ; Θ m ) f_M\left(x\right)=\sum_{m=1}^M T\left(x;\Theta_m\right) fM(x)=m=1∑MT(x;Θm)

在这里插入图片描述

哪个地方体现了boosting算法中，各个基分类器之间存在强依赖关系？这个强依赖关系是怎样的？

步骤(a)(b)体现了这一点。基分类器是回归树，强依赖关系是：每一颗回归树拟合的是样本在前一棵回归树的残差(当损失函数是平方误差损失时)。

整个树结构产生流程

在这里插入图片描述
但是有一个问题：当提升树的损失函数为均方误差、指数损失时，每一步优化(最小化损失函数)是简单的（后一棵树拟合前一棵树的残差），但对于一般损失函数而言，往往每一步的优化并不容易。Freidman提出了梯度提升（Gradient Boosting）算法，利用最速下降的近似方法，其关键是利用损失函数的负梯度在当前模型的值作为提升树算法中残差的近似值，拟合一个回归树。这就是GBDT。