基于树模型的集成算法---AdaBoost

作者: 自由调优师_大废废 | 来源:发表于2020-05-25 20:01 被阅读0次

一、模型介绍

Adaboost 是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器(弱分类器)，然后把这些弱分类器集合起来，构成一个更强的最终分类器（强分类器）。Adaboost 算法本身是通过改变数据分布来实现的，它根据每次训练集之中每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权值。将修改过权值的新数据集送给下层分类器进行训练，最后将每次得到的分类器最后融合起来，作为最后的决策分类器。

二、模型原理

原理：

AdaBoost 在每一轮中加入一个新的弱分类器，直到达到某个预定的足够小的错误率。每一个训练样本都被赋予一个权重，表明它被某个分类器选入训练集的概率。如果某个样本点已经被准确地分类，那么在构造下一个训练集中，它被选中的概率就被降低；相反，如果某个样本点没有被准确地分类，那么它的权重就得到提高。通过这样的方式，AdaBoost 方法能“聚焦于”那些较难分（更富信息）的样本上。在具体实现上，最初令每个样本的权重都相等，对于第 k 次迭代操作，我们就根据这些权重来选取样本点，进而训练分类器 C。然后就根据这个分类器，来提高被它分错的的样本的权重，并降低被正确分类的样本权重。然后，权重更新过的样本集被用于训练下一个分类器 C。整个训练过程如此迭代地进行下去。

步骤：

输入样本集 $\{(x_1,y_1), (x_2, y_2),……(x_m,y_m)\}$ ，输出为 -1 和 +1. 弱分类器算法，弱分类器迭代次数 K。输出最终的强分类器 f(x)

1. 初始化样本集权重

$D_1 = (w_{11},w_{12},……,w_{1m});w_{1i} = \frac{1}{m};i = 1,2,……m$

2. 对于 k = 1,2,……k

a 使用具有权重 $D_k$ 的样本集来训练数据，得到弱分类器 $G_k(x)$ 。
b 计算 $G_k(x)$ 的分类误差率：
$e_k = \frac{\sum_{i=1}^{m}P(G_k(x_i)\neq y_i) }{m}$
考虑更加周全的 AdaBoost 算法在这一步还应该判断是否满足基本条件(例如生成的基学习器是否比随机猜测好), 如果不满足，则当前基学习器被抛弃，学习过程提前终止。
c 计算 $G_k(x)$ 的系数 (即最终集成使用的的基学习器的权重)
$\alpha_k = \frac{1}{2} log\frac{1- e_k}{e_k}$
d 更新训练样本的权重：

$D_{k+1} = (w_{k+1,1}, w_{k+1,2},……w_{k+1,m} )$
$w_{k+1,i} = \frac{w_{k,i}}{Z_k} exp(-\alpha_k y_i G_k(x_i)); i = 1,2……m$
其中 $Z_k$ 是规范化因子，目的是为了使 $D_{k+1}$ 的所有元素和为1。
$Z_k = \sum_{i=1}^{m} w_{k,i} exp(-\alpha_k y_i G_k(x_i))$

3. 构建最终的分类器线性组合

$f(x) = sign(\sum_{i=1}^{m}\alpha_k G_k(x))$

三、模型细节

1 为什么使用 $\alpha_k = \frac{1}{2} log\frac{1- e_k}{e_k}$ 计算弱学习器权重系数？

从上式可以看出，如果分类误差率 $e_k$ 越大，则对应的弱分类器权重系数 $\alpha_k$ 越小。如果分类误差率 $e_k$ 越小，则对应的弱分类器权重系数 $\alpha_k$ 越大。即 AdaBoost 能够适应各个弱分类器的训练误差率，这也是它的名称中 “适应性 (Adaptive) ” 的由来。

2 前向分布算法

Adaboost 算法的最终模型表达式为： $f(x) = sign(\sum_{i=1}^{m}\alpha_k G_k(x))$ 。可以看到这个是一个‘加性模型’。我们希望这个模型在训练集上的经验误差最小，即： $min\sum_{i=1}^{m}L(y_i,f(x)) \Leftrightarrow min\sum_{i=1}^{m}L(y_i, \sum_{i=1}^{K}\alpha_kG_k(x))$
这是一个复杂的优化问题。前向分布算法求解这一优化问题的思想是：因为最终模型是一个加性模型，如果能从前往后，每一步只学习一个基学习器 $G_k(x)$ 及其权重 $\alpha_k$ ，不断迭代得到最终的模型，那么就可以简化问题复杂度。具体的，当我们经过 k-1 轮迭代得到了最优模型 $f_{k-1}(x)$ 时，因为：
$f_k(x) = f_{k-1}(x) + \alpha_kG_k(x)$
所以此轮优化目标为：
$min\sum_{i-1}^{m}L(y_i, f_{k-1}(x) + \alpha_kG_k(x_i))$
求解上式即可得到第 k 个基分类器 $G_k(x)$ 及其权重 $\alpha_k$ 。这样，前向分布算法就通过不断迭代求得了 k=1 到 k=K 的所有基分类器及其权重。

3 AdaBoost 算法证明过程

首先要知道 AdaBoost 的损失函数是指数损失函数。在周志华的书中有说明：指数损失函数是分类任务原本 0/1 损失函数的一致替代损失函数，由于指数损失函数有更好的数学性质，处处可微，所以我们用它代替 0/1 损失作为优化目标。
所以，我们的优化目标为：
$arg Min_{\alpha_k, G_k} \sum_{i=1}^{m} exp(-y_i(f_{k-1}(x) + \alpha_k G_k(x_i)))$
因为 $y_i, f_{k-1}(x)$ 与优化变量 $\alpha 、G$ 无关。
令： $\hat{w}_{k,i} = exp(-y_if_{k-1}(x_i))$
这个 $\hat{w}_{k,i}$ 其实就是前面说的归一化之前的权重。
此时优化目标可以写作：
$agrMin_{\alpha_k, G_k}\sum_{i=1}^{m}\hat{w}_{k,i}exp(-y_i\alpha_kG_k(x_i))$
首先对上式展开：
$\sum_{i=1}^{m}\hat{w}_{k,i}exp(-y_i\alpha G(x_i)) = \sum_{i=1}^{m}\hat{w}_{k,i}e^{-\alpha}I\{y_i = G(x_i) \} + \sum_{i=1}^{m}\hat{w}_{k,i}e^{-\alpha}I\{y_i \neq G(x_i) \}$
$= e^{-\alpha} \sum_{i=1}^{m} \hat{w}_{k,i} + (e^{\alpha}-e^{-\alpha})\sum_{i=1}^{m} \hat{w}_{k,i} I\{ y_i \neq G(x_i)\}$
上式中将指数函数换成指示函数是因为前面说的指数损失函数和 0/1 损失函数是一致等价的。
首先求 $\tilde{G_k(x)}$ :
$\tilde{G_k(x)} = arg Min_{G}\sum_{i=1}^{m} \hat{w}_{k,i} I \{y_i \neq G(x_i) \}$
该式子所示的优化问题其实就是 AdaBoost 算法的基学习器的学习过程。得到 $\tilde{G_k(x)}$ 是使第 k 轮加权训练数据分类错误最小的基分类器。
再求 $\alpha$ ,对其求导：
$\frac{\partial}{\partial \alpha}(e^{-\alpha} \sum_{i=1}^{m} \hat{w}_{k,i} + (e^{\alpha}-e^{-\alpha})\sum_{i=1}^{m} \hat{w}_{k,i} I\{ y_i \neq G(x_i)\})$
$= - e^{-\alpha} \sum_{i=1}^{m} \hat{w}_{k,i} +(e^{\alpha}+e^{-\alpha})\sum_{i=1}^{m} \hat{w}_{k,i} I\{ y_i \neq G(x_i) \} = 0$
即得：
$\frac{e^{\alpha} + e^{-\alpha}}{e^{-\alpha}} = \frac{ \sum_{i=1}^{m} \hat{w}_{k,i} }{\sum_{i=1}^{m} \hat{w}_{k,i} I\{ y_i \neq G(x_i) \}}$
$\alpha_k = \frac{1}{2}log\frac{1-e_k}{e_k}$
其中 $e_k = \frac{\sum_{i=1}^{m} \hat{w}_{k,i} I\{ y_i \neq G(x_i)\}}{ \sum_{i=1}^{m} \hat{w}_{k,i}} = \sum_{i=1}^{m} w_{ki} I\{ y_i \neq G(x_i)\}$
这里的 $\alpha$ 计算表达式就是前文中 $\alpha$ 计算公式的来源。
再看下一轮的权重更新：
$f_k(x) = f_{k-1}(x) + \alpha_k G_k(x)$ 以及
$w_{k,i} = exp(-y_if_{k-1}(x_i))$
可得：
$w_{k+1,i} = w_{k,i} exp(-y_i\alpha_kG_k)$
这里的与前文中样本权值的更新，只相差规范因子，等价的。

4 AdaBoost 算法的正则化

为了防止 AdaBoost 过拟合，我们通常也会加入正则化项，这个正则化项我们通常称为步长。定义为 v, 对于前面的弱学习器的迭代：
$f_k(x) = f_{k-1}(x) + \alpha_k G_k(x)$
加上正则项之后：
$f_k(x) = f_{k-1}(x) + v \alpha_k G_k(x)$
v 的取值范围为 0 到 1。对于同样的训练学习效果，较小的 v 意味着我们需要更多的弱学习器的迭代次数。通常我们用步长和迭代次数一起来决定算法的拟合效果。

四、模型优缺点

优点：

1 Adaboost作为分类器时，分类精度很高。
2 在Adaboost的框架下，可以使用各种回归分类模型来构建弱学习器，非常灵活。
3 作为简单的二元分类器时，构造简单，结果可理解。

缺点：

1 对异常样本敏感，异常样本在迭代中可能会获得较高的权重，影响最终的强学习器的预测准确性。

五、模型使用

from sklearn.ensemble import AdaBoostClassifier
adbst = AdaBoostClassifier(n_estimators=1000, learning_rate=0.5)

基于树模型的集成算法---AdaBoost

一、模型介绍

二、模型原理

原理：

步骤：

1. 初始化样本集权重

2. 对于 k = 1,2,……k

3. 构建最终的分类器线性组合

三、模型细节

1 为什么使用 $\alpha_k = \frac{1}{2} log\frac{1- e_k}{e_k}$ 计算弱学习器权重系数？

2 前向分布算法

3 AdaBoost 算法证明过程

4 AdaBoost 算法的正则化

四、模型优缺点

优点：

缺点：

五、模型使用

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

基于树模型的集成算法---AdaBoost

一、模型介绍

二、模型原理

原理：

步骤：

1. 初始化样本集权重

2. 对于 k = 1,2,……k

3. 构建最终的分类器线性组合

三、模型细节

1 为什么使用 计算弱学习器权重系数？

2 前向分布算法

3 AdaBoost 算法证明过程

4 AdaBoost 算法的正则化

四、模型优缺点

优点：

缺点：

五、模型使用

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

1 为什么使用 $\alpha_k = \frac{1}{2} log\frac{1- e_k}{e_k}$ 计算弱学习器权重系数？