Adaboost 算法与集成学习

作者: pdnbplus | 发布时间: 2024/06/25 | 阅读量: 179

# Adaboost 算法与集成学习 -- 潘登同学的Machine Learning笔记 @

书接上文，随机森林算法与集成学习 是利用集成学习中的Bagging方法，而Adaboost则是采用了Boosting的方法

Boosting

  • 多轮迭代（全部数据）每一轮产生一个弱分类器
  • 将弱分类器预测结果相加，得到强分类器的最终结果
  • 模型：Adaboost、GBDT、Xgboost

而将弱分类器相加的方式有：

  • 同权重 $$ G(x) = sign(\sum g(x)) $$
  • 线性（不同权） $$ G(x) = sign(\sum \alpha g(x)) $$
  • 非线性 $$ G(x) = sign(\sum h(g(x))) $$

Adaboost

而Adaboost采用的就是线性的方式 $$ G(x) = sign(\sum \alpha g(x)) $$

如何生成$g(x)$

  • 通过赋予样本不同的权重获得不同的$g(x)$
  • 基分类器$g(x)$大多使用 decision-stump 决策桩(即只有一层的二叉树)
  • 我们通过修改数据的权重，使得本次训练的弱分类器在上次弱分类器做的不好的地方进行训练

Adaboost 中的数据权重 Un

  • 权重与函数的关系
    • 对于同一个算法
      • 训练集不同，生成的模型一定不同
      • 如果训练集相同, 我们调整训练集中数据的权重，生成的模型也一定不同
    • 对于同一个模型
      • 输入的数据权重不同，模型预测的正确率也一定不同
      • 可以通过调整输入数据的权重，让本来还不错的分类器的正确率达到 1/2（1/2就是分类器没用的意思）

目标

  • 定义：
    • 数据预测的错误率 =（错误数据的个数）/（全部数据的个数）
    • 数据预测的权重错误率 =（预测错误数据的权重和）/（全部数据的权重和）

显然，我们的模型是要考虑权重的，所以模型的目标就是最小化这个数据预测的权重错误率；

$$ g_t \leftarrow \argmin_{h\in \mathcal{H}}(\sum_{i=1}^N U_i^t[y_n \neq h(x_i)])\ g_{t+1} \leftarrow \argmin_{h\in \mathcal{H}}(\sum_{i=1}^N U_i^{t+1}[y_n \neq h(x_i)])\ $$

注意 $\mathcal{H}$是希尔伯特空间的意思，表示这个$h(x)$decision-stump 决策桩是属于该空间，因为决策桩本来就是一个简单的二叉树，肯定在这个空间里；

在t时刻，我们根据$U_i^t$得到了当前权重下表现最好的弱分类器--$g(x)$，所以要注意，这个$g(x)$不是指前面说的决策桩，决策桩只是$g(x)$的组成部分 $$g(x) = \sum_{i=1}^N U_i^t h(x_i)$$

所以我们要得到下一轮的$U_n^{t+1}$才能继续下一步，而得到$U_n^{t+1}$的思路是：使得$g_{t+1}(x)在g_t(x)$表现不好的地方得到加强

更新$U_i^{t+1}$

  • 目标： $$ \frac{\sum_{i=1}^N U_n^{t+1}[y_n \neq h(x_i)]}{\sum_{i=1}^N U_n^{t+1}} = \frac{错误权重}{总权重} = \frac{1}{2}\ \Rightarrow 正确权重 = 错误权重 $$

  • 对于t时刻的原本的模型： $$ 正确权重 > 错误权重 $$

  • 要想相等，可以乘上对方，即 $$ 正确权重 * 错误权重 = 错误权重 * 正确权重 $$

注意 左边是原本正确样本权重在t+1时刻的新权重，左边是错误样本在t+1时刻的权重；但这样会有一个问题，就是权重在每一次更新后会变大，这样虽然不会有什么影响，可是数值一大难免会上溢，所以调整一下。

迭代每一轮物理权重$U_i^{t+1}$时的方式

  • 1.定义缩放因子 $$ factor_t = \sqrt{\frac{1-\epsilon_t}{\epsilon_t}} $$
  • 2.更新权重 $$correct_{t+1} \leftarrow \frac{correct_{t}}{factor_t}\ incorrect_{t+1} \leftarrow incorrect_{t} * factor_t$$

注意 $\epsilon_t$表示t时刻训练的权重错误率，一定是小于等于0.5的

  • 推导步骤二： 设$A$为正确的总权重和， $B$为错误的总权重和，有 $$ A * \epsilon_t = B * (1-\epsilon_t)\ 总权重C = \frac{A}{1-\epsilon_t} = \frac{B}{\epsilon_t}\ A^2 * \frac{\epsilon_t}{1-\epsilon_t} = B^2 * \frac{1-\epsilon_t}{\epsilon_t} \ A * \sqrt{\frac{\epsilon_t}{1-\epsilon_t}} = B * \sqrt{\frac{1-\epsilon_t}{\epsilon_t}} $$

合并生成$G(x)$

线性聚合 $$ G(x) = sign(\sum_{t=1}^T\alpha_tg_t(x)) $$

计算$\alpha$的方法： $$ factor_t = \sqrt{\frac{1-\epsilon_t}{\epsilon_t}} $$ factor其实越大越好，表示的就是权重错误率低，所以这样的$g_t(x)$应该赋予比较大的权重，而factor为1的时候是最差的时候，正确率是0.5，所以权重应该是0，所以只要找到这样一个函数，在1时取0，且递增就行

$$ \alpha = \frac{1}{2}\ln (\frac{1-\epsilon_t}{\epsilon_t})\ 即 \alpha = \ln factor_t $$

总结Adaboost 全局过程

  • 1.初始化权重$U_1$
  • 2.循环迭代
    • 2.1根据$U_t$训练模型$g_t$
    • 2.2根据$g_t$模型在$u_t$数据上计算中间结果factor
    • 2.3根据factor计算下一轮权重$U_{t+1}$
    • 2.4根据factor计算本轮弱分类器权重$\alpha_t$
  • 3.得到一组$g(x)$ 返回$G(x) = sign(\sum_{t=1}^T\alpha_tg_t(x)) $

Adaboost回归问题的算法流程

前面的Adaboost显然就是用于做分类问题的，现在介绍一个回归算法

Adaboost R2回归算法

  • 1.初始化权重$U_1$
  • 2.循环迭代
    • 2.1根据$U_t$训练模型$g_t$
    • 2.2计算训练集上的最大误差 $$ E_t=\max{y_i−g_t(x_i)} i=1,2...m $$
    • 2.3 计算每个样本的相对误差
      • 如果是线性误差, 则$e_{i}^t = \frac{|y_i−g_t(x_i)|}{E_t}$
      • 如果是平方误差, 则$e_{i}^t = \frac{(y_i−g_t(x_i))^2}{E_t}$
      • 如果是指数误差, 则$e_{i}^t = 1-e^{\frac{|y_i−g_t(x_i)|}{E_t}}$
    • 2.4计算回归误差率 $$ e_t = \sum_{i=1}^{m}U_i^te_{i}^t $$
    • 2.5计算弱学习器的系数 $$ \alpha_t = \frac{e_t}{1-e_t} $$
    • 2.6更新样本集的权重$U_i^{t+1}$ $$ U_i^{t+1} = \frac{U_i^{t}}{Z_t}\alpha_t^{1-e_{i}^t}\ 其中Z_t是归一化因子，Z_t = \sum_{i=1}^mU_i^{t}\alpha_t^{1-e_{i}^t} $$
  • 3.得到一组$g(x)$ 返回$G(x) = sign(\sum_{t=1}^T\alpha_tg_t(x))$

代码实现Adaboost

#%% AdaBoostClassifier实战
import numpy as np
import matplotlib.pyplot as plt
from sklearn.ensemble import AdaBoostClassifier
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import make_gaussian_quantiles


# 生成2维正态分布，生成的数据按分位数分为两类，500个样本,2个样本特征，协方差系数为2
X1, y1 = make_gaussian_quantiles(cov=2.0,n_samples=500, n_features=2,n_classes=2, random_state=1)
# 生成2维正态分布，生成的数据按分位数分为两类，400个样本,2个样本特征均值都为3，协方差系数为2
X2, y2 = make_gaussian_quantiles(mean=(3, 3), cov=1.5,n_samples=400, n_features=2, n_classes=2, random_state=1)
#讲两组数据合成一组数据
X = np.concatenate((X1, X2))
y = np.concatenate((y1, - y2 + 1))

plt.scatter(X[:, 0], X[:, 1], marker='o', c=y)

我们生成一些随机数据来做二元分类, 我们通过可视化看看我们的分类数据，它有两个特征，两个输出类别，用颜色区别。

Adaboost样本点

bdt = AdaBoostClassifier(DecisionTreeClassifier(max_depth=2, min_samples_split=20, min_samples_leaf=5),
                         algorithm="SAMME",
                         n_estimators=200, learning_rate=0.8)
bdt.fit(X, y)

x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, 0.02),
                     np.arange(y_min, y_max, 0.02))

Z = bdt.predict(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)
cs = plt.contourf(xx, yy, Z, cmap=plt.cm.Paired)
plt.scatter(X[:, 0], X[:, 1], marker='o', c=y)
plt.show()

print("Score:", bdt.score(X,y))

最终结果与划分的区域如图所示

Adaboost分类结果

Adaboost类库调用

参考scikit-learn Adaboost类库使用小结

Adaboost类库概述

  • scikit-learn中Adaboost类库比较直接，就是AdaBoostClassifier和AdaBoostRegressor两个，从名字就可以看出AdaBoostClassifier用于分类，AdaBoostRegressor用于回归。
  • 当我们对Adaboost调参时，主要要对两部分内容进行调参，第一部分是对我们的Adaboost的框架进行调参， 第二部分是对我们选择的弱分类器进行调参。两者相辅相成。下面就对Adaboost的两个类：AdaBoostClassifier和AdaBoostRegressor从这两部分做一个介绍。

AdaBoostClassifier和AdaBoostRegressor框架参数

  • 1）base_estimator：AdaBoostClassifier和AdaBoostRegressor都有，即我们的弱分类学习器或者弱回归学习器。理论上可以选择任何一个分类或者回归学习器，不过需要支持样本权重。我们常用的一般是CART决策树或者神经网络MLP。默认是决策树，即AdaBoostClassifier默认使用CART分类树DecisionTreeClassifier，而AdaBoostRegressor默认使用CART回归树DecisionTreeRegressor。另外有一个要注意的点是，如果我们选择的AdaBoostClassifier算法是SAMME.R，则我们的弱分类学习器还需要支持概率预测，也就是在scikit-learn中弱分类学习器对应的预测方法除了predict还需要有predict_proba。

  • 2）algorithm：这个参数只有AdaBoostClassifier有。主要原因是scikit-learn实现了两种Adaboost分类算法，SAMME和SAMME.R。两者的主要区别是弱学习器权重的度量，SAMME就是我们前面讲的调整$U_{t+1}的策略，即用对样本集分类效果作为弱学习器权重，而SAMME.R使用了对样本集分类的预测概率大小来作为弱学习器权重。由于SAMME.R使用了概率度量的连续值，迭代一般比SAMME快，因此AdaBoostClassifier的默认算法algorithm的值也是SAMME.R。我们一般使用默认的SAMME.R就够了，但是要注意的是使用了SAMME.R， 则弱分类学习器参数base_estimator必须限制使用支持概率预测的分类器。SAMME算法则没有这个限制。

  • 3）loss：这个参数只有AdaBoostRegressor有，Adaboost.R2算法需要用到。有线性‘linear’, 平方‘square’和指数 ‘exponential’三种选择, 默认是线性，一般使用线性就足够了，

  • 4）n_estimators： AdaBoostClassifier和AdaBoostRegressor都有，就是我们的弱学习器的最大迭代次数，或者说最大的弱学习器的个数。

  • 5）learning_rate: AdaBoostClassifier和AdaBoostRegressor都有，即每个弱学习器的权重缩减系数

AdaBoostClassifier和AdaBoostRegressor弱学习器参数

这个参数基本上就是之前决策树中前剪枝中讲的那些参数了。

几个重要的：

  • 最大特征数max_features
  • 决策树最大深max_depth
  • 内部节点再划分所需最小样本数min_samples_split
  • 叶子节点最少样本数min_samples_leaf
  • 叶子节点最小的样本权重和min_weight_fraction_leaf
  • 最大叶子节点数max_leaf_nodes

Adaboost 算法与集成学习就是这样了, 继续下一章吧！pd的Machine Learning