提升树模型

回归问题的提升树方法

算法1：

输入：训练数据集$ T={(x_1,y_1),(x_2,y_2),…,(x_N,y_N)}, x_i \in X \subseteq R^n, y_i \in Y \subseteq R $

输出：提升树$ f_m(x) $

(1) 初始化$ f_0(x)=0 $

(2) 对$ m=1,2,…,M $

(2.1) 按式(1)计算残差$ r_{mi}=y_i-f_{m-1}(x_i) $

(2.2) 拟合残差$r_{mi}$学习一个回归树，得到$T(x;\Theta_m)$

(2.3) 更新$ f_m(x)=f_{m-1}(x)+T(x;\Theta_m) $

(3) 得到回归问题的提升树$ f_M(x)=\displaystyle\sum_{m=1}^M T(x;\Theta_m) $

例子：

求$ T_1(x) $

2.1 训练数据的某一个划分点s: $ R_1= \lbrace x|x \leq s \rbrace, R_2= \lbrace x|x \gt s \rbrace $

在集合$R_1,R_2$中，计算$ c_1,c_2 $为 $ c_1=\frac{1}{N_1}\displaystyle\sum_{x_i \in R_1} y_i$, $c_2=\frac{1}{N_2}\displaystyle\sum_{x_i \in R_2} y_i $, 这里的$N_1,N_2$分别为$R_1,R_2$的样本点数。

设定切分点s，根据训练集样本可知，考虑如下切分点（也可用本身数据值作划分）： 1.5，2.5，3.5，4.5，5.5，6.5，7.5，8.5，9.5

根据优化问题的公式：$m(s)=\min_s[\min_{c_1}\displaystyle\sum_{x_i \in R_1}(y_i-c_1)^2 + min_{c_2}\displaystyle\sum_{x_i \in R_2}(y_i-c_2)^2]$ 求出相应的$R_1,R_2,c_1,c_2$及$ m(s) $

当s=1.5时，$ R_1=\lbrace 1 \rbrace , R_2=\lbrace 2,3,…,10 \rbrace, c_1=5.56, c_2=7.50, m(s)=0+15.72=15.72 $

将s和$m(s)$的计算结果列出如下表1：

$$表1 计算数据表$$

由表1可知，当s=6.5时$m(s)$达到最大值，此时 $ R_1=\lbrace 1,2,…,6 \rbrace , R_2=\lbrace 7,8,9,10 \rbrace, c_1=6.24, c_2=8.91 $， 所以回归树$ T_1(x) $为 $$ T_1(x) = \begin{cases} 6.24, & x \lt 6.5 \\ 8.91, & x \ge 6.5 \end{cases} $$ $$ f_1(x)=T_1(x) $$

用$ f_1(x) $拟合数据的残差（输出值和真实值之差）见表2所示，表中$ r_{2i}=y_i-f_1(x_i),i=1,2,…,10 $

$$ 表2 数据残差表 $$

此时，用$ f_1(x) $拟合训练数据的平方损失误差为：$$ L(y,f_1(x))=\displaystyle\sum_{i=1}^{10}(y_i-f_1(x_i))^2=1.93 $$

求$T_2(x)$

同理，求$T_2(x)$和求$T_1(x)$的方法是一样的，只是$ f_1(x) $拟合数据的残差，$ f_2(x) $拟合的数据为表2的残差，求得 $$ T_2(x) = \begin{cases} -0.52, & x \lt 3.5 \\ 0.22, & x \ge 3.5 \end{cases} $$ $$ f_2(x)=f_1(x)+T_2(x)= \begin{cases} 5.72, & x \lt 3.5 \\ 6.46, & x \ge 3.5 \cup x \lt 6.5 \\ 9.13, & x \ge 6.5 \end{cases} $$

此时，用$ f_2(x) $拟合表的平方损失误差为：$$ L(y,f_2(x))=\displaystyle\sum_{i=1}^{10}(y_i-f_2(x_i))^2=0.79 $$

继续求得： $$ T_3(x) = \begin{cases} 0.15, & x \lt 6.5 \\ -0.22, & x \ge 6.5 \end{cases}, L(y,f_3(x))=0.47 $$ $$ T_4(x) = \begin{cases} -0.16, & x \lt 4.5 \\ 0.11, & x \ge 4.5 \end{cases}, L(y,f_4(x))=0.30 $$ $$ T_5(x) = \begin{cases} 0.07, & x \lt 6.5 \\ -0.11, & x \ge 6.5 \end{cases}, L(y,f_5(x))=0.23 $$ $$ T_6(x) = \begin{cases} -0.15, & x \lt 2.5 \\ 0.04, & x \ge 2.5 \end{cases}, f_6(x)=f_5(x)+T_6(x)= \begin{cases} 5.63, & x \lt 2.5 \\ 5.82, & x \ge 2.5 \cup x \lt 3.5 \\ 6.56, & x \ge 3.5 \cup x \lt 4.5 \\ 6.83, & x \ge 4.5 \cup x \lt 5.5 \\ 8.95, & x \ge 6.5 \end{cases} $$

此时，用$ f_6(x) $拟合表的平方损失误差为：$$ L(y,f_6(x))=\displaystyle\sum_{i=1}^{10}(y_i-f_6(x_i))^2=0.17 $$

假设当前的误差0.17已经满足误差要求，则$f(x)=f_6(x)$为所求的提升树。

梯度提升

当损失函数是平方损失和指数损失函数时，每一步的优化是很简单的，但是对于一般的损失函数而言， 往往每一步优化没那么容易。因此，有研究人员提出了梯度提升算法，这是利用最速下降法的近似方 法，关键是利用损失函数的负梯度在当前模型的值$$ -[\frac{\partial L(y,f(x_i))}{\partial f(x_i)}]_{f(x)=f_m-1(x)} $$作为回归问题 提升树算法中的残差的近似值，拟合一回归树。

算法2：

输入：训练数据集$ T={(x_1,y_1),(x_2,y_2),…,(x_N,y_N)}, x_i \in X \subseteq R^n, y_i \in Y \subseteq R $

输出：回归树$ f(x) $

(1) 初始化$ f_0(x)=argmin_c \displaystyle\sum_{i=1}^N L(y_i,c) $

(2) 对$ m=1,2,…,M $

(2.1) 对$ i=1,2,…,N $，计算 $$ r_{mi}=-[\frac{\partial L(y,f(x_i))}{\partial f(x_i)}]_{f(x)=f_m-1(x)} $$

(2.2) 对$r_{mi}$拟合一个回归树，得到第m棵树的叶结点区域$R_mj,j=1,2,…,J$

(2.3) 对$j=1,2,…,J$，计算$ c_{mi}=argmin_c \displaystyle\sum_{xi \in R_mj} L(y_i,f_{m-1}(x_i)+c) $

(2.4) 更新$ f_m(x)=f{m-1}(x)+\displaystyle\sum_{j=1}^J c_{mj}I(x \in R_{mj}) $

(3) 得到回归问题$ f(x)=f_M(x)=\displaystyle\sum_{m=1}^M \displaystyle\sum_{j=1}^J c_{mj}I(x \in R_{mj}) $

说明：

第（1）步初始化，估计使损失函数最小化的常数值

第（2.1）步计算损失函数的负梯度在当前模型的值，将它作为残差的估计。注：对于平方损失函数，为残差；对于一般的损失函数，为残差近似值

第（2.2）步估计回归树叶结点区域，以拟合残差的近似值

第（2.3）步利用线性搜索估计叶结点区域的值，使损失函数最小化

第（2.4）步更新回归树

第（3）步得到输出的最终模型$f(x)$

代码实现：

1