经典机器学习算法-第七章AdaBoost

EDUCATION AND TRAINING

一、算法原理

1.1 Boost

    Boosting是机器学习的三大框架之一，其特点是，训练过程中的诸多弱模型，彼此之间有着强依赖关系。Boost也被称为增强学习或提升法。典型的代表算法是AdaBoost算法。集成学习中有两个重要概念，分别为Bagging和Boost。其中Boost也被称为增强学习或提升法，是一种重要的集成学习方法，它能够将预测精度仅仅比随机猜测略高的弱学习器增强为预测精度很高的强学习器。这是在直接构造强学习器较为困难的情况下，为学习算法提供了一种有效的新思路和新方法。其中较为成功的是上个世纪90年代Yoav Freund和Robert Schapire提出的AdaBoost算法。

可以将上图过程总结为：

对原始数据集初始化权重

用带权值数据集训练弱学习器

根据弱学习器的误差计算弱学习器的权重

调整数据集的权重

重复第2-4步K-1次

将K-1个弱学习器的结果进行加权组合

1.2 AdaBoost

1.2.1. 概要介绍

    AdaBoost算法（Adaptive Boosting）是一种有效而实用的Boosting算法，它以一种高度自适应的方式按顺序训练弱学习器。针对分类问题，AdaBoost算法根据前一次的分类效果调整数据的权重，在上一个弱学习器中分类错误的样本的权重会在下一个弱学习器中增加，分类正确的样本的权重则相应减少，并且在每一轮迭代时会向模型加入一个新的弱学习器。不断重复调整权重和训练弱学习器，直到误分类数低于预设值或迭代次数达到指定最大值，最终得到一个强学习器。

简单来说，AdaBoost算法的核心思想就是调整错误样本的权重，进而迭代升级。

    AdaBoost是Adaptive Boosting（自适应增强）的缩写，它的自适应在于：被前一个基本分类器误分类的样本的权值会增大，而正确分类的样本的权值会减小，并再次用来训练下一个基本分类器。同时，在每一轮迭代中，加入一个新的弱分类器，直到达到某个预定的足够小的错误率或预先指定的最大迭代次数再确定最后的强分类器。

从上图来看，AdaBoost算法可以简化为3个步骤：

(1)首先，是初始化训练数据的权值分布D1。假设有N个训练样本数据，则每一个训练样本最开始时，都会被赋予相同的权值：w1 = 1/N。

(2)训练弱分类器Ci。具体训练过程：如果某个训练样本点，被弱分类器Ci准确地分类，那么再构造下一个训练集中，它对应的权值要减小；相反，如果某个训练样本点被错误分类，那么它的权值就应该增大。权值的更新过的样本被用于训练下一个弱分类器，整个过程如此迭代下去。

(3)最后，将各个训练得到的弱分类器组合成一个强分类器。各个弱分类器的训练过程结束后，加大分类误差率小的弱分类器的权重，使其在最终的分类函数中起着较大的决定作用，而降低分类误差率大的弱分类器的权重，使其在最终的分类函数中起着较小的决定作用。换而言之，误差率低的弱分类器在最终分类器中占的权重较大，否则较小。

1.2.2. AdaBoost算法过程

给定训练数据集：（x1,y1）,(x2,y2)···(xn,yn)，其中yi属于{1，-1}用于表示训练样本的类别标签，i=1,...,N。Adaboost的目的就是从训练数据中学习一系列弱分类器或基本分类器，然后将这些弱分类器组合成一个强分类器。

相关符号定义：

Adaboost的算法流程如下：

相关说明：

综合上面的推导，可得样本分错与分对时，其权值更新的公式为：

1.2.3. AdaBoost实例讲解

    例：给定如图所示的训练样本，弱分类器采用平行于坐标轴的直线，用Adaboost算法的实现强分类过程。

数据分析：

    将这10个样本作为训练数据，根据 X 和Y 的对应关系，可把这10个数据分为两类，图中用“+”表示类别1，用“O”表示类别-1。本例使用水平或者垂直的直线作为分类器，图中已经给出了三个弱分类器，即：

初始化：

    首先需要初始化训练样本数据的权值分布，每一个训练样本最开始时都被赋予相同的权值：wi=1/N，这样训练样本集的初始权值分布D1(i)：

令每个权值w1i = 1/N = 0.1，其中，N = 10，i = 1,2, ..., 10，然后分别对于t= 1,2,3, ...等值进行迭代（t表示迭代次数，表示第t轮），下表已经给出训练样本的权值分布情况：

第1次迭代t=1：

    初试的权值分布D1为1/N（10个数据，每个数据的权值皆初始化为0.1），

D1=[0.1, 0.1, 0.1, 0.1, 0.1, 0.1,0.1, 0.1, 0.1, 0.1]

在权值分布D1的情况下，取已知的三个弱分类器h1、h2和h3中误差率最小的分类器作为第1个基本分类器H1(x)（三个弱分类器的误差率都是0.3，那就取第1个吧）

    在分类器H1(x)=h1情况下，样本点“5 7 8”被错分，因此基本分类器H1(x)的误差率为：

    可见，被误分类样本的权值之和影响误差率e，误差率e影响基本分类器在最终分类器中所占的权重α。

    然后，更新训练样本数据的权值分布，用于下一轮迭代，对于正确分类的训练样本“1 2 3 4 6 9 10”（共7个）的权值更新为：

    这样，第1轮迭代后，最后得到各个样本数据新的权值分布：

D2=[1/14,1/14,1/14,1/14,1/6,1/14,1/6,1/6,1/14,1/14]

由于样本数据“5 7 8”被H1(x)分错了，所以它们的权值由之前的0.1增大到1/6；反之，其它数据皆被分正确，所以它们的权值皆由之前的0.1减小到1/14，下表给出了权值分布的变换情况：

    可得分类函数：f1(x)= α1H1(x) = 0.4236H1(x)。此时，组合一个基本分类器sign(f1(x))作为强分类器在训练数据集上有3个误分类点（即5 7 8），此时强分类器的训练错误为：0.3

第二次迭代t=2：

    在权值分布D2的情况下，再取三个弱分类器h1、h2和h3中误差率最小的分类器作为第2个基本分类器H2(x)：

① 当取弱分类器h1=X1=2.5时，此时被错分的样本点为“5 7 8”：

误差率e=1/6+1/6+1/6=3/6=1/2；

② 当取弱分类器h2=X1=8.5时，此时被错分的样本点为“3 4 6”：

误差率e=1/14+1/14+1/14=3/14；

③ 当取弱分类器h3=X2=6.5时，此时被错分的样本点为“1 2 9”：

误差率e=1/14+1/14+1/14=3/14；

    因此，取当前最小的分类器h2作为第2个基本分类器H2(x)

    显然，H2(x)把样本“3 4 6”分错了，根据D2可知它们的权值为D2(3)=1/14，D2(4)=1/14， D2(6)=1/14，所以H2(x)在训练数据集上的误差率：

    这样，第2轮迭代后，最后得到各个样本数据新的权值分布：

D3=[1/22,1/22,1/6,1/6,7/66,1/6,7/66,7/66,1/22,1/22]

下表给出了权值分布的变换情况：

    可得分类函数：f2(x)=0.4236H1(x) + 0.6496H2(x)。此时，组合两个基本分类器sign(f2(x))作为强分类器在训练数据集上有3个误分类点（即3 4 6），此时强分类器的训练错误为：0.3

第三次迭代t=3:

    在权值分布D3的情况下，再取三个弱分类器h1、h2和h3中误差率最小的分类器作为第3个基本分类器H3(x)：

① 当取弱分类器h1=X1=2.5时，此时被错分的样本点为“5 7 8”：

误差率e=7/66+7/66+7/66=7/22；

② 当取弱分类器h2=X1=8.5时，此时被错分的样本点为“3 4 6”：

误差率e=1/6+1/6+1/6=1/2=0.5；

③ 当取弱分类器h3=X2=6.5时，此时被错分的样本点为“1 2 9”：

误差率e=1/22+1/22+1/22=3/22；

因此，取当前最小的分类器h3作为第3个基本分类器H3(x)：

    这样，第3轮迭代后，得到各个样本数据新的权值分布为：

D4=[1/6,1/6,11/114,11/114,7/114,11/114,7/114,7/114,1/6,1/38]

    下表给出了权值分布的变换情况：

    可得分类函数：f3(x)=0.4236H1(x) + 0.6496H2(x)+0.9229H3(x)。此时，组合三个基本分类器sign(f3(x))作为强分类器，在训练数据集上有0个误分类点。至此，整个训练过程结束。

整合所有分类器，可得最终的强分类器为：

    这个强分类器Hfinal对训练样本的错误率为0！

1.2.4. AdaBoost的优点和缺点

优点

（1）Adaboost提供一种框架，在框架内可以使用各种方法构建子分类器。可以使用简单的弱分类器，不用对特征进行筛选，也不存在过拟合的现象。

（2）Adaboost算法不需要弱分类器的先验知识，最后得到的强分类器的分类精度依赖于所有弱分类器。无论是应用于人造数据还是真实数据，Adaboost都能显著的提高学习精度。

（3）Adaboost算法不需要预先知道弱分类器的错误率上限，且最后得到的强分类器的分类精度依赖于所有弱分类器的分类精度，可以深挖分类器的能力。Adaboost可以根据弱分类器的反馈，自适应地调整假定的错误率，执行的效率高。

（4）Adaboost对同一个训练样本集训练不同的弱分类器，按照一定的方法把这些弱分类器集合起来，构造一个分类能力很强的强分类器，即“三个臭皮匠赛过一个诸葛亮”。

缺点：

在Adaboost训练过程中，Adaboost会使得难于分类样本的权值呈指数增长，训练将会过于偏向这类困难的样本，导致Adaboost算法易受噪声干扰。此外，Adaboost依赖于弱分类器，而弱分类器的训练时间往往很长。

二、Numpy手写代码

import numpy as npimport pandas as pdimport matplotlib.pyplot as plt

from sklearn.model_selection import train_test_split# 导入sklearn模拟二分类数据生成模块from sklearn.datasets.samples_generator import make_blobs# 生成模拟二分类数据集X, y = make_blobs(n_samples=150, n_features=2, centers=2, cluster_std=1.2, random_state=40)# 将标签转换为1/-1y_ = y.copy()y_[y_==0] = -1y_ = y_.astype(float)# 训练/测试数据集划分X_train, X_test, y_train, y_test = train_test_split(X, y_, test_size=0.3, random_state=43)# 设置颜色参数colors = {0:'r', 1:'g'}# 绘制二分类数据集的散点图plt.scatter(X[:,0], X[:,1], marker='o', c=pd.Series(y).map(colors))plt.show();

### 定义决策树桩类作为Adaboost弱分类器

### 定义决策树桩类### 作为Adaboost弱分类器class DecisionStump():    def __init__(self):        # 基于划分阈值决定样本分类为1还是-1        self.label = 1        # 特征索引        self.feature_index = None        # 特征划分阈值        self.threshold = None        # 指示分类准确率的值        self.alpha = None

### 定义AdaBoost算法类class Adaboost:    # 弱分类器个数    def __init__(self, n_estimators=5):        self.n_estimators = n_estimators            # Adaboost拟合算法    def fit(self, X, y):        m, n = X.shape        # (1) 初始化权重分布为均匀分布 1/N        w = np.full(m, (1/m))        # 处初始化基分类器列表        self.estimators = []        # (2) for m in (1,2,...,M)        for _ in range(self.n_estimators):            # (2.a) 训练一个弱分类器：决策树桩            estimator = DecisionStump()            # 设定一个最小化误差            min_error = float('inf')            # 遍历数据集特征，根据最小分类误差率选择最优划分特征            for i in range(n):                # 获取特征值                values = np.expand_dims(X[:, i], axis=1)                # 特征取值去重                unique_values = np.unique(values)                # 尝试将每一个特征值作为分类阈值                for threshold in unique_values:                    p = 1                    # 初始化所有预测值为1                    pred = np.ones(np.shape(y))                    # 小于分类阈值的预测值为-1                    pred[X[:, i] < threshold] = -1                    # 2.b 计算误差率                    error = sum(w[y != pred])                                        # 如果分类误差大于0.5，则进行正负预测翻转                    # 例如 error = 0.6 => (1 - error) = 0.4                    if error > 0.5:                        error = 1 - error                        p = -1
                    # 一旦获得最小误差则保存相关参数配置                    if error < min_error:                        estimator.label = p                        estimator.threshold = threshold                        estimator.feature_index = i                        min_error = error                                    # 2.c 计算基分类器的权重            estimator.alpha = 0.5 * np.log((1.0 - min_error) / (min_error + 1e-9))            # 初始化所有预测值为1            preds = np.ones(np.shape(y))            # 获取所有小于阈值的负类索引            negative_idx = (estimator.label * X[:, estimator.feature_index] < estimator.label * estimator.threshold)            # 将负类设为 '-1'            preds[negative_idx] = -1            # 2.d 更新样本权重            w *= np.exp(-estimator.alpha * y * preds)            w /= np.sum(w)
            # 保存该弱分类器            self.estimators.append(estimator)        # 定义预测函数    def predict(self, X):        m = len(X)        y_pred = np.zeros((m, 1))        # 计算每个弱分类器的预测值        for estimator in self.estimators:            # 初始化所有预测值为1            predictions = np.ones(np.shape(y_pred))            # 获取所有小于阈值的负类索引            negative_idx = (estimator.label * X[:, estimator.feature_index] < estimator.label * estimator.threshold)            # 将负类设为 '-1'            predictions[negative_idx] = -1            # 2.e 对每个弱分类器的预测结果进行加权            y_pred += estimator.alpha * predictions
        # 返回最终预测结果        y_pred = np.sign(y_pred).flatten()        return y_pred

# 导入sklearn准确率计算函数from sklearn.metrics import accuracy_score# 创建Adaboost模型实例clf = Adaboost(n_estimators=5)# 模型拟合clf.fit(X_train, y_train)# 模型预测y_pred = clf.predict(X_test)# 计算模型预测准确率accuracy = accuracy_score(y_test, y_pred)print('Accuracy of AdaBoost by numpy:', accuracy)

三、scikit-learn集成方法

导入sklearn adaboost分类器
from sklearn.ensemble import AdaBoostClassifier创建Adaboost模型实例clf_ = AdaBoostClassifier(n_estimators=5, random_state=0)模型拟合clf_.fit(X_train, y_train)模型预测y_pred_ = clf_.predict(X_test)计算模型预测准确率accuracy = accuracy_score(y_test, y_pred_)

print('Accuracy of AdaBoost by sklearn:', accuracy)

3.1 回归器：

class sklearn.ensemble.AdaBoostRegressor(base_estimator=None, *, n_estimators=50, learning_rate=1.0, loss='linear', random_state=None)

参数介绍：

base_estimator:

    object,optional(default=DecisionTreeRegressor)。 基估计器，理论上可以选择任何回归器，但是这个地方需要支持样本加权重，as well as proper classes_ and n_classes_ attributes.（这个地方不过会翻译）。常用的是CART回归树和神经网络，默认CART回归树，即AdaBoostRegressor默认使用CART回归树DecisionTreeRegressor。

n_estimators :

    integer, optional (default=50)。基估计器的个数。

   learning_rate: 

    float, optional (default=1.)。即每个弱学习器的权重缩减系数νν，在原理篇的正则化章节我们也讲到了，加上了正则化项，我们的强学习器的迭代公式为

ν的取值范围为0<ν≤1。对于同样的训练集拟合效果，较小的ν意味着我们需要更多的弱学习器的迭代次数。通常我们用步长和迭代最大次数一起来决定算法的拟合效果。所以这两个参数n_estimators和learning_rate要一起调参。一般来说，可以从一个小一点的ν开始调参，默认是1。

loss : 

 {'linear’, 'square’, 'exponential’}, optional (default=’linear’)。Adaboost.R2算法需要用到。有线性'linear’, 平方'square’和指数 'exponential’三种选择, 默认是线性，一般使用线性就足够了，除非你怀疑这个参数导致拟合程度不好。这个值的意义，它对应了我们对第k个弱分类器的中第i个样本的误差的处理，即：

如果是线性误差，则

如果是平方误差，则

如果是指数误差，则

，式中Ek为训练集上的最大误差Ek=max|yi−Gk(xi)|i=1,2...m

random_state : 

    int, RandomState instance or None, optional (default=None)

属性介绍：

estimators_ : list of classifiers

estimator_weights_ : array of floats

estimator_errors_ : array of floats

feature_importances_ : array of shape = [n_features]

方法介绍：

3.2 分类器

class sklearn.ensemble.AdaBoostClassifier(base_estimator=None, *, n_estimators=50, learning_rate=1.0, algorithm='SAMME.R', random_state=None)

参数介绍：

base_estimator :

    object, optional (default=DecisionTreeClassifier)。基估计器，理论上可以选择任何分类器，但是这个地方需要支持样本加权重，as well as proper classes_ and n_classes_ attributes.（这个地方不过会翻译）。常用的是CART决策树和神经网络，默认CART决策树，即AdaBoostClassifier默认使用CART决策树DecisionTreeClassifier。

n_estimators :

    integer, optional (default=50)。基估计器的个数。

learning_rate : 

    float, optional (default=1.)。通过这个参数缩减每个分类器的贡献，learning_rate和n_estimators 两个参数之间存在权衡。

algorithm : 

    {'SAMME’, 'SAMME.R’}, optional (default=’SAMME.R’)。如果'SAMME.R'则使用SAMME.R （Real Boosting） 算法。base_estimator必须支持类概率的计算。如果'SAMME'则使用SAMME （discrete boosting） 算法。SAMME.R算法通常收敛速度高于SAMME，通过较少的升压迭代实现较低的测试误差。（老哥们有好的翻译理解记得评论下！）

    如果我们选择的AdaBoostClassifier算法是SAMME.R，则我们的弱分类学习器还需要支持概率预测，也就是在scikit-learn中弱分类学习器对应的预测方法除了predict还需要有predict_proba。

    两者的主要区别是弱学习器权重的度量，SAMME使用了和我们的原理篇里二元分类Adaboost算法的扩展，即用对样本集分类效果作为弱学习器权重，而SAMME.R使用了对样本集分类的预测概率大小来作为弱学习器权重。由于SAMME.R使用了概率度量的连续值，迭代一般比SAMME快，因此AdaBoostClassifier的默认算法algorithm的值也是SAMME.R。我们一般使用默认的SAMME.R就够了，但是要注意的是使用了SAMME.R， 则弱分类学习器参数base_estimator必须限制使用支持概率预测的分类器。SAMME算法则没有这个限制。

random_state :

    int, RandomState instance or None, optional (default=None)。如果int，random_state是随机数生成器使用的种子; 如果RandomState的实例，random_state是随机数生成器; 如果None，则随机数生成器是由np.random使用的RandomState实例。

属性介绍：

estimators_ : 

    list of classifiers 子估计器

classes_ : 

    array of shape = [n_classes] 类别的标签信息

n_classes_ : 

    int 类别的数量

estimator_weights_ :

    array of floats 每个基估计器的权重

estimator_errors_ : 

    array of floats 每个基估计器的错误率

feature_importances_ :

    array of shape = [n_features] 如果基估计器支持的话