学习笔记-随机森林、提升树、GBDT

2020-03-11 本文已影响0人 Pluto_wl

在之前的章节里，学习了集成学习的两个代表方式：bagging和boosting，现在来看如果将bagging和boosting运用在决策树中。

随机森林(random forest)

随机森林是决策树和Bagging的结合体，并且为了增加多样性，随机森林加入了样本的随机选择。

随机采样的到m个子集
随机森林使用boostrap的方式对原始数据集采样，即有放回的采样。每个子集采样n(数据集的大小)次，所以子集中可能有的样本出现多次，有的样本没有出现。所以得到m个大小和原始数据大小一样的样本子集。

图片来自于网络

对特征采样
传统决策树在选择划分属性时，选择当前所有属性中的最优属性作为决策树的划分属性。但随机森林中，对决策树中的每个结点，先从该结点中随机选取k个属性作为当前结点的属性子集，然后再从这子集中选择最优的属性。下图展示的是两次不同结点所选择的特征。通常推荐 $k=log_2d$ ,d表示当前结点所有属性的个数。

图片来自网络
最终决策
最终决策使用的是投票方式，少数服从多数。

图片来网络

需要注意的是：并不是决策树的个数越多越好。
优点
简单、容易实现、计算开销小、具有强大的性能。性能强大的原因是不仅包含了bagging中的样本多样性，还包含了来自样本自己特征的多样性。

提升树

在之前的笔记中，学习了cart如果解决回归问题和boosting集成方式，现在来看看如何将boosting集成方法应用到回归问题中。

提升树：以决策树为基函数的提升方法。在提升树中，每个基决策树是由一个根结点直接连接的两个也结点的简单决策树，即决策树桩。提升树模型可以表示为决策树的加法模型
$f_M(x)=\sum_{m=1}^M T(x;\theta _m) \tag{1}，T(x\theta)=\sum^J_{j=1} c_jI(x \in R_j)$
其中， $T(x;\theta _m)$ 表示决策树，m表示第m课决策树桩，M为决策树的个数, $J$ 表示将输入空间划分为 $J$ 个互不相交的区域， $R_1,R_2,...,R_J$ ,并且在每个区域上的输出为 $c_1,c_2,...,c_J$ , $\theta=\{ (R_1,c_1), (R_2,c_2),...,(R_J,c_J)\}$ 表示树的空间划分和每个区域上确定的输出常量 $c_j$ 。

回归问题下使用前向分布算法
第一步：设
$f(x)=0 \tag{2}$
第二步：
$f_m=f_{m-1} + T(x; \theta)，m=1,2,...,M \tag{3}$
第三步：整体模型表示
$f_M=\sum_{m=1}^M T(x;\theta) \tag{4}$
第四步：写出第m步的损失函数
在回归问题中，使用mse作为损失函数，所以决策树的目标是最小化mse损失函数。
$argmin \sum_{i=1}^N L(y_i-f_m) \tag{5}$
在第m步，给定当前模型 $f_{m-1}(x)$ ，即前m-1个决策树。（在第m步，前m-1个模型肯定是已经求出）
所以第m步的损失函数可以将式（5）改写为：
$argmin \sum_{i=1}^N L(y_i-f_{m-1}(x_i) -T(x_i;\theta)) \tag{6}$
第五步：求参数 $\theta$
回归问题使用MSE作为损失函数
$L(y, f(x))=(y-f_{m}(x))^2 \tag{7}$
$L(y, f(x))=(y-f_{m-1}(x) -T(x;\theta)) ^2 \tag{8}$
令 $r=y-f_{m-1}(x)$ ，损失函数变为
$L(y, f(x))=(r -T(x;\theta)) ^2 \tag{9}$

r就是当前模型需要拟合的残差，所以提升树的回归问题来说就是简单的拟合数据的残差即可。
为什么拟合残差就行
拟合残差意味着使当前模型的输出逼近残差，从式(9)可以看到损失函数变为了 $(r -T(x;\theta)) ^2$ ,要最小化损失函数只需要最小化 $r$ 与当前模型输出的差值即可，并且构成 $r$ 的 $y$ 与 $f_{m-1}(x)$ 都是已知的。所以提升树在回归问题中拟合残差即可。
例子（来自于统计学习方法P180）
现在有输入数据x和输出数据y

对于以上数据，可能的切分点有。
(1) 对于所有可能的切分点计算MSE损失和最优输出
例如以1.5作为分界点
,
,
所以
同理计算其他切分点的损失，如下图所示

（2）选择使损失最小的切分点
当时，损失函数最小为1.93,对应的划分输出为,,得到树

(3) 根据树计算下一个树需要拟合的残差

（4）重复上述过程，依次计算

(5) 将所有树的区间叠加得到
这步根据式（1）得到

GBDT

提升树利用加法模型与前向分步算法实现学习的优化过程。当损失函数使平方损失和指数损失时，每一步的优化是很简单的。但对于一般损失函数而言，每一步优化并不容易。GBDT利用损失函数的负梯度在当前模型的值
$-[\frac {\partial L(y,f(x_i)) }{\partial f(x_i)}]_{f(x)= f_{m-1}(x)}$
作为回归问题提升树算法中的残差的近似值，拟合一个回归树。
注意：当损失函数为MSE时，负梯度就是残差，其他损失函数时，只是近似残差。

从泰勒展开看看GBDT
泰勒展开式如下:

来自[5]

GBDT的损失函数如下：
$L(y, f_m(x_i))=L(y, f_{m-1}(x)+T(x;\theta))$
使用一阶泰勒展开损失函数，将此处的 $f_{m-1}$ 当作a， $T(x;\theta)$ 当作h，带入泰勒展开式得到
$L(y, f_{m-1}(x)+T(x_i;\theta)=L(y, f_{m-1})+f^{\prime }_{m- 1(x)} T(x;\theta)$
要使损失函数最小，等式右边 $L(y, f_{m-1})$ 是个常数，那么令 $T(x;\theta)$ 为 $f^{\prime }_{m- 1(x)}$ 的负方向即可保证等式右边的损失函数比前一个树的损失函数小
$T(x;\theta)=-f^{\prime }_{m- 1(x)}$
带入式中得到
$L(y, f_{m-1}(x)+T(x_i;\theta)=L(y, f_{m-1})+f^{\prime }_{m- 1(x)} T(x;\theta)$ 变为 $L(y, f_{m-1}(x)+T(x_i;\theta)=L(y, f_{m-1})-f^{\prime 2}_{m- 1(x)}$
综上所述，拟合损失函数的负梯度即可保证模型趋向拟合。

GDBT流程
输入：训练数据集 $T={(x_1,y_1),(x_2,y_2),...,(x_n,y_n)}$ ,损失函数为 $L(y,f(x))$
输出回归树
（1）初始化
$f_0(x)=\underset{c}{argmin} \sum^{N}_{i=1} L(y_i,c)$ ，这里的c是所有均值
（2）对 $m=1,2,...,M$

对 $i=1,2,...,N$ ,计算
$r_{mi}=-[\frac {\partial L(y,f(x_i)) }{\partial f(x_i)}]_{f(x)= f_{m-1}(x)}$ ,这里计算每个x对于的残差值
对 $r_{mi}$ 拟合一个回归树，得到第m棵树的叶结点区域 $R_{mj}$ , $j=1,2,...,J$ .
对, $j=1,2,...,J$ ,计算
$c_{mj}=\underset{c}{argmin} \sum_{x_i \in R_{mj}} L(y_i,f_{m-1}(x_i)+c)$ ,这里的c是每一个子区域 $R_{mj}$ 的均值，具体的，这里的 $c$ 表示第m棵树在 $j$ 这个子领域的输出值。
更新 $f_m(x)=f_{m-1}(x) + \sum^J_{j=1} c_{mj}I(x \in R_{mj})$
(3) 得到回归树
$\hat{f(}x)=f_M(x)=\sum^M_{m=1} \sum^J_{j=1} c_{mj}I(x \in R_{mj})$