提升树算法

2020-07-28 本文已影响0人墩er

提升方法采用加法模型（基函数的线性组合）和前向分步算法。

基本分类器 $x<v$ 或者 $x>v$ ，是由一个根结点直接连接两个叶结点的简单决策树，即决策树桩。提升树是以二叉分类树或二叉回归树为基本分类器的提升方法。

提升树模型可以表示为 $f_{M}(x)=\sum_{m=1}^M T(x;\theta _{m})$ ，其中 $T(x;\theta _{m})$ 表示决策树， $\theta _{m}$ 为决策树的参数，M为树的个数。

分类问题

使用指数损失函数和AdaBoost算法。

步骤（1）训练数据集具有均匀的权值分布， $G_{1}(x)$ 是在原始数据上学习的。

步骤（2）使用 $D_{m}$ 加权的训练集学习 $G_{m}(x)$ ，该分类器由 $x<v$ 或 $x>v$ 产生，其阈值v使该分类器的分类误差率最低。

分类误差率 $e_{m}$ 是被 $G_{m}(x)$ 误分类样本的权值之和。 $G_{m}(x)$ 在最终分类器中的重要性 $\alpha _{m}$ 随着 $e_{m}$ 的减小而增大。

更新训练数据的权重分布，可以写成：

$w_{m+1,i}=\left\{ \begin{array}{**lr**} \frac{w_{mi}}{Z_{m}}e^{-\alpha _{m}} , G_{m}(x_{i})=y_{i} & \\ \frac{w_{mi}}{Z_{m}}e^{\alpha _{m}} , G_{m}(x_{i})\neq y_{i} & \end{array} \right.$

因此误分类样本的权值扩大，正确分类样本的权值缩小。两者比较，误分类样本的权值扩大 $e^{2\alpha m}=\frac{1-e_{m}}{e_{m}}$ 倍，下一轮学习中起更大的作用，不断减少训练集上的分类误差率。

步骤（3）线性组合 $f(x)$ 实现M个基本分类器的加权表决。所有 $\alpha _{m}$ 之和不为1。

例 8.1

假设弱分类器由 $x<v$ 或 $x>v$ 产生，其阈值v使该分类器的分类误差率最低。

回归问题

使用平方误差损失函数 $L(y,f(x))=(y-f(x))^2$ 。

其损失变为 $L(y,f_{m-1}(x)+T(x;\theta _{m}))=[y-f_{m-1}(x)-T(x;\theta _{m})]^2=[r-T(x;\theta _{m})]^2$

其中， $r=y-f_{m-1}(x)$ 是当前模型拟合数据的残差(residual)

对于回归问题的提升树算法，就是拟合当前模型的残差。

每一个基分类器是决策树桩，即由一个根结点直接连接两个叶结点的简单决策树，是欠拟合模型。

梯度提升

boosting算法中拟合残差是常用的方式（AdaBoost已经不常使用）

参考：《统计学习方法》

上一篇下一篇

猜你喜欢

热点阅读