监督学习集成模型——AdaBoost

一、集成学习与Boosting

集成学习是指将多个弱学习器组合成一个强学习器，这个强学习器能取所有弱学习器之所长，达到相对的最佳性能的一种学习范式。

集成学习主要包括Boosting和Bagging两种学习框架。Boosting是一种将弱学习器提升为强学习器的算法，所以也叫提升算法。

以分类问题为例，给定一个训练数据集，训练弱分类器要比训练强分类器相对容易很多，从第一个弱分类器开始，Boosting通过训练多个弱分类器，并在训练过程中不断改变训练样本的概率分布，使得每次训练时算法都会更加关注上一个弱分类器的错误。通过组合多个这样的弱分类器，便可以获得一个接近相对完美的强分类器。boosting方法的核心理念在于博采众长，正所谓"三个臭皮匠，顶个诸葛亮"，这也使得boosting方法要好于大多数单模型算法。

二、AdaBoost模型

AdaBoost基本原理

AdaBoost的全称为Adaptive Boosting，可以翻译为自适应提升算法。（提升方法是将弱学习算法提升为强学习算法的统计学习方法。）

AdaBoost是一种通过改变训练样本权重来学习多个弱分类器并线性组合成强学习器的Boosting算法。

Boosting要解决两个关键问题：

• 一是在训练过程中如何改变训练样本的权重或者概率分布。
• 二是如何将多个弱分类器组合成一个强分类器。

针对这两个问题，Adaboost是做法非常朴素，第一个就是提高前一轮被弱分类器分类错误的样本的权重、而降低分类正确的样本权重；第二则是对多个弱分类器进行线性组合，提高分类效果好的弱分类器权重，减小分类误差率大的弱分类器权重。

给定训练数据集D=(x1,y1),(x2,y2),⋯,(xN,yN)" role="presentation" style="position: relative;">D=(x1,y1),(x2,y2),⋯,(xN,yN)$D=(x_1,y_1),(x_2,y_2),\cdots ,(x_N,y_N)$，其中xi∈χ⊆Rn，yi∈Y=−1,+1" role="presentation" style="position: relative;">xi∈χ⊆Rn，yi∈Y=−1,+1$x_i\in \chi \subseteq R^n，y_i\in Y=-1,+1$，AdaBoost训练算法如下。

1. 初始化训练数据样本的权值分布，即为每个训练样本分配一个初始权值：D1=(w11,⋯,w1i,⋯w1N),w1i=1/N,i=1,2,⋯,N" role="presentation" style="position: relative;">D1=(w11,⋯,w1i,⋯w1N),w1i=1/N,i=1,2,⋯,N$D_1=(w_{11},\cdots ,w_{1i},\cdots w_{1N}),w_{1i}=1/N,i=1,2,\cdots ,N$

2. 对于t=1,2,⋯,T" role="presentation" style="position: relative;">t=1,2,⋯,T$t=1,2,\cdots ,T$，分别执行以下步骤。

• 对包含权值分布Dm" role="presentation" style="position: relative;">Dm$D_m$的训练数据集进行训练并得到弱分类器Gt(x)" role="presentation" style="position: relative;">Gt(x)$G_t(x)$。

• 计算Gt(x)" role="presentation" style="position: relative;">Gt(x)$G_t(x)$在当前加权训练集上的分类误差率ϵt" role="presentation" style="position: relative;">ϵt${ϵ}_t$：

  ϵt=P(Gt(xi)≠yi)=∑i=1NwtiI(Gt(xi)≠yi)" role="presentation" style="position: relative;">ϵt=P(Gt(xi)≠yi)=∑Ni=1wtiI(Gt(xi)≠yi)${ϵ}_t=P(G_t(x_i)\ne y_i)={\sum }_{i=1}^N{w}_{ti}I(G_t(x_i)\ne y_i)$

• 根据分类误差率ϵt" role="presentation" style="position: relative;">ϵt${ϵ}_t$计算当前弱分类器的权重系数αt" role="presentation" style="position: relative;">αt${\alpha }_t$：

  αt=1/2log(1−ϵt)/ϵt" role="presentation" style="position: relative;">αt=1/2log(1−ϵt)/ϵt${\alpha }_t=1/2log(1-{ϵ}_t)/{ϵ}_t$

• 调整训练数据集的权值分布：

  Dt+1=(wt+1,1,⋯,wt+1,i,⋯wt+1,N)" role="presentation" style="position: relative;">Dt+1=(wt+1,1,⋯,wt+1,i,⋯wt+1,N)$D_{t+1}=(w_{t+1},1,\cdots ,w_{t+1},i,\cdots w_{t+1},N)$

  wt+1,i=wti/Ztexp(−αtyiGt(xi))" role="presentation" style="position: relative;">wt+1,i=wti/Ztexp(−αtyiGt(xi))$w_{t+1},i=w_{t}i/Z_{t}exp(-{\alpha }_t{y}_i{G}_t(x_i))$

  分类正确的权重下降，分类错误权重上升

  其中Zt" role="presentation" style="position: relative;">Zt$Z_t$为归一化因子，Zt=∑i=1Nwtiexp(−αtyiGt(xi))" role="presentation" style="position: relative;">Zt=∑Ni=1wtiexp(−αtyiGt(xi))$Z_t={\sum }_{i=1}^N{w}_{ti}exp(-{\alpha }_t{y}_i{G}_t(x_i))$。

3. 最后构建T个弱分类器的线性组合：

   f(x)=∑i=1TαtGt(x)" role="presentation" style="position: relative;">f(x)=∑Ti=1αtGt(x)$f(x)={\sum }_{i=1}^T{\alpha }_t{G}_t(x)$

最终的AdaBoost强分类器可以写为：
G(x)=sign(f(x))=sign(∑i=1NαtGt(x))" role="presentation" style="position: relative;">G(x)=sign(f(x))=sign(∑Ni=1αtGt(x))$G(x)=sign(f(x))=sign({\sum }_{i=1}^N{\alpha }_t{G}_t(x))$

在弱分类器权重系数计算过程中，当弱分类器的分类误差率ϵt≤1/2" role="presentation" style="position: relative;">ϵt≤1/2${ϵ}_t\le 1/2$时，αt≥0" role="presentation" style="position: relative;">αt≥0${\alpha }_t\ge 0$，且αt" role="presentation" style="position: relative;">αt${\alpha }_t$随着ϵt" role="presentation" style="position: relative;">ϵt${ϵ}_t$的减小而变大，这也正是弱分类器权重系数计算公式的设计思想，它能够使得分类误差率较低的分类器有较大的权重系数。AdaBoost训练样本权值分布可以写为：

wt+1,i={wtiZte−αt,Gt(xi)=yiwtiZteαt,Gt(xi)≠yi" role="presentation">wt+1,i={wtiZte−αt,wtiZteαt,Gt(xi)=yiGt(xi)≠yi$$w_{t+1,i}=\{\begin{array}{ll}\frac{w_{ti}}{Z_t}{e}^{-{\alpha }_t},& G_t\left(x_i\right)=y_i\\ \frac{w_{ti}}{Z_t}{e}^{{\alpha }_t},& G_t\left(x_i\right)\ne y_i\end{array}$$

当样本被弱分类器正确分类时，对应样本的权重变小；当样本被弱分类器错误分类时，对应样本的权重变大。相比之外，错误分类样本的权重扩大了e2αt" role="presentation" style="position: relative;">e2αt$e^{2{\alpha }_t}$倍，这就使得在下一轮训练中，算法将更加关注这些误分类的样本。

视频讲解：

简博士

https://www.bilibili.com/video/BV18g41197rC

https://www.bilibili.com/video/BV1pF411F7CY/

前向分步算法

从机器学习三要素（模型、策略、算法）的角度来看，AdaBoost可以看作为以加性模型为模型、指数函数为损失函数和前向分步为算法的分类学习算法。

所谓加性模型（additive model），就是由多个基模型求和的形式构造起来的。加性模型可以表示为：

f(x)=∑t=1Tαtb(x;γt)" role="presentation" style="position: relative;">f(x)=∑Tt=1αtb(x;γt)$f(x)={\sum }_{t=1}^T{\alpha }_{t}b(x;{\gamma }_t)$

其中b(x;γt)" role="presentation" style="position: relative;">b(x;γt)$b(x;{\gamma }_t)$为基模型，γt" role="presentation" style="position: relative;">γt${\gamma }_t$为基模型参数，αt" role="presentation" style="position: relative;">αt${\alpha }_t$为基模型系数，可知f(x)是由T个基模型求和的加性模型。

给定训练数据集和损失函数的条件下，加性模型的目标函数为如下最小化损失函数：

minαt,γt∑i=1NL(yi,∑t=1Tαtb(xi;γt))" role="presentation" style="position: relative;">minαt,γt∑Ni=1L(yi,∑Tt=1αtb(xi;γt))$\underset{{\alpha }_t,{\gamma }_t}{min}\sum _{i=1}^{N}L(y_i,\sum _{t=1}^T{\alpha }_{t}b(x_i;{\gamma }_t))$

针对上式这样一个较为复杂的优化问题，可以采用前向分步算法进行求解。其基本思路如下：针对加性模型的特点，从前往后每次只优化一个基模型的参数，每一步优化叠加之后便可逐步逼近目标函数。每一步优化的表达式如下式所示：

minα,γ∑i=1NL(yi,αb(xi;γ))" role="presentation" style="position: relative;">minα,γ∑Ni=1L(yi,αb(xi;γ))$\underset{\alpha ,\gamma }{min}{\sum }_{i=1}^{N}L(y_i,\alpha b(x_i;\gamma ))$

给定训练数据集D=(x1,y1),(x2,y2),⋯,(xN,yN)" role="presentation" style="position: relative;">D=(x1,y1),(x2,y2),⋯,(xN,yN)$D=(x_1,y_1),(x_2,y_2),\cdots ,(x_N,y_N)$，其中xi∈χ⊆Rn，yi∈Y={−1,+1}" role="presentation" style="position: relative;">xi∈χ⊆Rn，yi∈Y={−1,+1}$x_i\in \chi \subseteq R^n，y_i\in Y=\{-1,+1\}$，前向分步算法求解过程如下。

初始化模型f0(x)=0" role="presentation" style="position: relative;">f0(x)=0$f_0(x)=0$。

对于t=1, 2,⋯,T，分别执行以下操作。

以αt" role="presentation" style="position: relative;">αt${\alpha }_t$和γt" role="presentation" style="position: relative;">γt${\gamma }_t$为优化参数，最小化目标损失函数：

(αt,γt)=argminα,γ∑i=1NL(yi,ft−1(xi)+αb(xi;γ))" role="presentation" style="position: relative;">(αt,γt)=argminα,γ∑Ni=1L(yi,ft−1(xi)+αb(xi;γ))$({\alpha }_t,{\gamma }_t)=argmi{n}_{\alpha ,\gamma }{\sum }_{i=1}^{N}L(y_i,f_{t-1}(x_i)+\alpha b(x_i;\gamma ))$

更新加性模型：

ft(x)=ft−1(x)+αtb(x;γt)" role="presentation" style="position: relative;">ft(x)=ft−1(x)+αtb(x;γt)$f_t(x)=f_{t-1}(x)+{\alpha }_{t}b(x;{\gamma }_t)$

可得到最后的加性模型为：

f(x)=fT(x)=∑t=1Tαtb(x;γt)" role="presentation" style="position: relative;">f(x)=fT(x)=∑Tt=1αtb(x;γt)$f(x)=f_T(x)={\sum }_{t=1}^T{\alpha }_{t}b(x;{\gamma }_t)$

从前向分步算法的角度来理解AdaBoost，可以将AdaBoost看作前向分步算法的特例，这时加性模型是以分类器为基模型、以指数函数为损失函数的最优化问题。假设经过t−1次前向分步迭代后已经得到ft−1(x)" role="presentation" style="position: relative;">ft−1(x)$f_{t-1}(x)$，第t次迭代可以得到第t个基模型的权重系数αt" role="presentation" style="position: relative;">αt${\alpha }_t$、第t个基模型Gt(x)" role="presentation" style="position: relative;">Gt(x)$G_t(x)$和t轮迭代后的加性模型ft(x)" role="presentation" style="position: relative;">ft(x)$f_t(x)$。优化目标是使

ft(x)" role="presentation" style="position: relative;">ft(x)$f_t(x)$在给定训练数据集D上的指数损失最小化，有：

(αt,Gt(x))=argminα,G∑i=1Nexp⁡(−yi(ft−1(xi)+αG(xi)))" role="presentation" style="position: relative;">(αt,Gt(x))=argminα,G∑Ni=1exp(−yi(ft−1(xi)+αG(xi)))$({\alpha }_t,G_t(x))=\underset{\alpha ,G}{\mathrm{argmin}}\sum _{i=1}^N\exp (-y_i(f_{t-1}\left(x_i\right)+\alpha G\left(x_i\right)))$

求解上式的最小化指数损失即可得到AdaBoost的优化参数。

三、AdaBoost算法实现

先定义一个基分类器

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

定义AdaBoost算法类

### 定义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

数据测试

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/-1
y_ = y.copy()
y_[y_==0] = -1
y_ = 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模型测试

# 导入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)

Accuracy of AdaBoost by numpy: 0.9777777777777777

导入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)

Accuracy of AdaBoost by sklearn: 0.9777777777777777