集成学习之Boosting

关于集成学习的简介，参考另外一篇博客传送门

1 什么是Boosting？

Boosting是指每个基学习器在前一个基学习器的基础上进行学习，最后综合所有基学习器的预测值产生最终的预测结果。（这里综合的方法常常是加权法。）整个训练和测试过程如下图所示：

具体来说，Boosting是一种串行学习的方法。首先，第一个学习器对训练样本进行学习；然后基于第一个学习器的预测效果对训练样本进行调整，让第一个学习器预测错误的样本在接下来得到更多的关注；基于调整后的样本分布来寻找(或训练)下一个学习器，重复上面的步骤。最后达到设定的学习器数量就终止，对所有的学习器的结果进行加权给出最后的结果。

基于Boosting的方法需要解决其过程中的两个问题：

1. 如何在每一轮改变训练数据的权值和概率分布?
2. 如何将各个学习器组合起来(以发挥更好的效果)？

关于弱学习器和强学习器：一般来说，弱学习器是指准确率一般的学习器(也就是准确率仅仅比随机猜测略高的学习算法)；强学习器是指准确率很高且能在多项式时间内完成的学习算法。在这里，各个学习器一般为弱学习器，它们组合起来可以看做一个强学习器。

2 Adaboost

2.1 Adaboost是什么样的？

Adaboost是最具代表性的Boosting方法。Adaboost的基本思想是：前一个学习器分错的样本会得到更多的关注，加权后的全体样本再次被用来训练下一个基学习器。

Adaboost的步骤为：

1. 初始化训练样本的权值分布，最开始每个样本具有相同的权重。
2. 训练第一个基学习器，如果样本分类正确，则构造下一个训练集的时候它的权值会被降低；如果样本被分类错误，它的权值会被提高。这样做的目的是当前基学习器分类不好的让下一个基学习器去弥补。以此继续下去，直到最后一个基学习器。
3. 所有的基学习器训练完成后，根据各个基学习器的分类的精度来确定它们各自预测结果的权值。也就是说，对各个基学习器的结果进行加权得到最后的预测结果。

这里，Adaboost解决上述的两个问题的方式是：

1. 提高那些被前一轮分类器错误分类的样本的权重，而降低那些被正确分类的样本的权重。这样一来，那些在上一轮分类器中没有得到正确分类的样本，由于其权重的增大而在后一轮的训练中“备受关注”。
2. 各个弱分类器的组合是通过采取加权多数表决的方式，具体来说，加大分类错误率低的弱分类器的权重，因为这些分类器能更好地完成分类任务，而减小分类错误率较大的弱分类器的权重，使其在表决中起较小的作用。

2.2 Adaboost的基本原理

假设给定一个二分类的训练数据集：\(T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \cdots,\left(x_{N}, y_{N}\right)\right\}\)，其中每个样本点由特征与类别组成。特征\(x_{i} \in \mathcal{X} \subseteq \mathbf{R}^{n}\)，类别\(y_{i} \in \mathcal{Y}=\{-1,+1\}\)，\(\mathcal{X}\)是特征空间，$ \(是类别集合，输出最终分类器\)G(x)$。

Adaboost算法如下：

1. 初始化训练数据的分布：\(D_{1}=\left(w_{11}, \cdots, w_{1 i}, \cdots, w_{1 N}\right), \quad w_{1 i}=\frac{1}{N}, \quad i=1,2, \cdots, N\)

2. 对于m=1,2,...,M

   • 使用具有权值分布\(D_m\)的训练数据集进行学习，得到基本分类器：\(G_{m}(x): \mathcal{X} \rightarrow\{-1,+1\}\)

   • 计算\(G_m(x)\)在训练集上的分类误差率\(e_{m}=\sum_{i=1}^{N} P\left(G_{m}\left(x_{i}\right) \neq y_{i}\right)=\sum_{i=1}^{N} w_{m i} I\left(G_{m}\left(x_{i}\right) \neq y_{i}\right)\)
     

   • 计算\(G_m(x)\)的系数\(\alpha_{m}=\frac{1}{2} \log \frac{1-e_{m}}{e_{m}}\)，这里的log是自然对数ln
     

   • 更新训练数据集的权重分布
     \[ \begin{array}{c} D_{m+1}=\left(w_{m+1,1}, \cdots, w_{m+1, i}, \cdots, w_{m+1, N}\right) \\ w_{m+1, i}=\frac{w_{m i}}{Z_{m}} \exp \left(-\alpha_{m} y_{i} G_{m}\left(x_{i}\right)\right), \quad i=1,2, \cdots, N \end{array} \]
     这里的\(Z_m\)是规范化因子，使得\(D_{m+1}\)称为概率分布，\(Z_{m}=\sum_{i=1}^{N} w_{m i} \exp \left(-\alpha_{m} y_{i} G_{m}\left(x_{i}\right)\right)\)

3. 构建基本分类器的线性组合\(f(x)=\sum_{m=1}^{M} \alpha_{m} G_{m}(x)\)，得到最终的分类器 \[ \begin{aligned} G(x) &=\operatorname{sign}(f(x)) \\ &=\operatorname{sign}\left(\sum_{m=1}^{M} \alpha_{m} G_{m}(x)\right) \end{aligned} \]

• 对于步骤(1)，假设训练数据的权值分布是均匀分布，是为了使得第一次没有先验信息的条件下每个样本在基本分类器的学习中作用一样。
  

• 对于步骤(2)，每一次迭代产生的基本分类器\(G_m(x)\)在加权训练数据集上的分类错误率\(\begin{aligned}e_{m} &=\sum_{i=1}^{N} P\left(G_{m}\left(x_{i}\right) \neq y_{i}\right) =\sum_{G_{m}\left(x_{i}\right) \neq y_{i}} w_{m i}\end{aligned}\)代表了在\(G_m(x)\)中分类错误的样本权重和，这点直接说明了权重分布\(D_m\)与\(G_m(x)\)的分类错误率\(e_m\)有直接关系。同时，在步骤(2)中，计算基本分类器\(G_m(x)\)的系数\(\alpha_m\)，\(\alpha_{m}=\frac{1}{2} \log \frac{1-e_{m}}{e_{m}}\)，它表示了\(G_m(x)\)在最终分类器的重要性程度，\(\alpha_m\)的取值由基本分类器\(G_m(x)\)的分类错误率有直接关系，当\(e_{m} \leqslant \frac{1}{2}\)时，\(\alpha_{m} \geqslant 0\)，并且\(\alpha_m\)随着\(e_m\)的减少而增大，因此分类错误率越小的基本分类器在最终分类器的作用越大！ 最重要的，对于步骤(2)中的样本权重的更新：
  \[ w_{m+1, i}=\left\{\begin{array}{ll} \frac{w_{m i}}{Z_{m}} \mathrm{e}^{-\alpha_{m}}, & G_{m}\left(x_{i}\right)=y_{i} \\ \frac{w_{m i}}{Z_{m}} \mathrm{e}^{\alpha_{m}}, & G_{m}\left(x_{i}\right) \neq y_{i} \end{array}\right. \]
  因此，从上式可以看到：被基本分类器\(G_m(x)\)错误分类的样本的权重扩大，被正确分类的样本权重减少，二者相比相差\(\mathrm{e}^{2 \alpha_{m}}=\frac{1-e_{m}}{e_{m}}\)倍。

• 对于步骤(3)，线性组合\(f(x)\)实现了将M个基本分类器的加权表决，系数\(\alpha_m\)标志了基本分类器\(G_m(x)\)的重要性，值得注意的是：所有的\(\alpha_m\)之和不为1。\(f(x)\)的符号决定了样本x属于哪一类。

2.3 基于sklearn的Adaboost使用

数据集

UCI的机器学习库里的开源数据集：葡萄酒数据集，该数据集可以在 ( 传送门 )上获得。该数据集包含了178个样本和13个特征，从不同的角度对不同的化学特性进行描述，我们的任务是根据这些数据预测红酒属于哪一个类别。(案例来源《python机器学习(第二版》)

Adaboost使用

# 引入数据科学相关工具包：
import numpy as np
import pandas as pd 
import matplotlib.pyplot as plt
plt.style.use("ggplot")
%matplotlib inline
import seaborn as sns

# 加载训练数据：         
wine = pd.read_csv("https://archive.ics.uci.edu/ml/machine-learning-databases/wine/wine.data",header=None)
wine.columns = ['Class label', 'Alcohol', 'Malic acid', 'Ash', 'Alcalinity of ash','Magnesium', 'Total phenols','Flavanoids', 'Nonflavanoid phenols', 
                'Proanthocyanins','Color intensity', 'Hue','OD280/OD315 of diluted wines','Proline']

# 数据查看：
print("Class labels",np.unique(wine["Class label"]))
# wine.head()

输出：Class labels [1 2 3]

# 数据预处理
# 仅仅考虑2，3类葡萄酒，去除1类
wine = wine[wine['Class label'] != 1]
y = wine['Class label'].values
X = wine[['Alcohol','OD280/OD315 of diluted wines']].values

# 将分类标签变成二进制编码：
from sklearn.preprocessing import LabelEncoder
le = LabelEncoder()
y = le.fit_transform(y)

# 按8：2分割训练集和测试集
from sklearn.model_selection import train_test_split
X_train,X_test,y_train,y_test = train_test_split(X,y,test_size=0.2,random_state=1,stratify=y)  # stratify参数代表了按照y的类别等比例抽样

输出：Decision tree train/test accuracies 0.916/0.875

# 使用单一决策树建模
from sklearn.tree import DecisionTreeClassifier
tree = DecisionTreeClassifier(criterion='entropy',random_state=1,max_depth=1)
from sklearn.metrics import accuracy_score
tree = tree.fit(X_train,y_train)
y_train_pred = tree.predict(X_train)
y_test_pred = tree.predict(X_test)
tree_train = accuracy_score(y_train,y_train_pred)
tree_test = accuracy_score(y_test,y_test_pred)
print('Decision tree train/test accuracies %.3f/%.3f' % (tree_train,tree_test))

# 使用sklearn实现Adaboost(基分类器为决策树)
'''
AdaBoostClassifier相关参数：
base_estimator：基本分类器，默认为DecisionTreeClassifier(max_depth=1)
n_estimators：终止迭代的次数
learning_rate：学习率
algorithm：训练的相关算法，{'SAMME'，'SAMME.R'}，默认='SAMME.R'
random_state：随机种子
'''
from sklearn.ensemble import AdaBoostClassifier
ada = AdaBoostClassifier(base_estimator=tree,n_estimators=500,learning_rate=0.1,random_state=1)
ada = ada.fit(X_train,y_train)
y_train_pred = ada.predict(X_train)
y_test_pred = ada.predict(X_test)
ada_train = accuracy_score(y_train,y_train_pred)
ada_test = accuracy_score(y_test,y_test_pred)
print('Adaboost train/test accuracies %.3f/%.3f' % (ada_train,ada_test))

输出：Adaboost train/test accuracies 1.000/0.917

# 画出单层决策树与Adaboost的决策边界：
x_min = X_train[:, 0].min() - 1
x_max = X_train[:, 0].max() + 1
y_min = X_train[:, 1].min() - 1
y_max = X_train[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, 0.1),np.arange(y_min, y_max, 0.1))
f, axarr = plt.subplots(nrows=1, ncols=2,sharex='col',sharey='row',figsize=(12, 6))
for idx, clf, tt in zip([0, 1],[tree, ada],['Decision tree', 'Adaboost']):
    clf.fit(X_train, y_train)
    Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])
    Z = Z.reshape(xx.shape)
    axarr[idx].contourf(xx, yy, Z, alpha=0.3)
    axarr[idx].scatter(X_train[y_train==0, 0],X_train[y_train==0, 1],c='blue', marker='^')
    axarr[idx].scatter(X_train[y_train==1, 0],X_train[y_train==1, 1],c='red', marker='o')
    axarr[idx].set_title(tt)
axarr[0].set_ylabel('Alcohol', fontsize=12)
plt.tight_layout()
plt.text(0, -0.2,s='OD280/OD315 of diluted wines',ha='center',va='center',fontsize=12,transform=axarr[1].transAxes)
plt.show()

从上面的决策边界图可以看到：Adaboost模型的决策边界比单层决策树的决策边界要复杂的多。也就是说，Adaboost试图用增加模型复杂度而降低偏差的方式去减少总误差，但是过程中引入了方差，可能出现国拟合，因此在训练集和测试集之间的性能存在较大的差距，这就简单地回答的刚刚问题。值的注意的是：与单个分类器相比，Adaboost等Boosting模型增加了计算的复杂度，在实践中需要仔细思考是否愿意为预测性能的相对改善而增加计算成本，而且Boosting方式无法做到现在流行的并行计算的方式进行训练，因为每一步迭代都要基于上一部的基本分类器。

参考

阿泽知乎 传动门

datawhale 传送门