Adaboost算法:基于集成学习的又一经典分类算法

对于集成学习而言，常用的有bagging和boosting两种策略，在之前的文章中，介绍了bagging策略的经典算法-随机森林，本文介绍基于boosting策略的经典分类算法-Adaboost。

boosting策略的框架如下所示

和bagging策略不同之处主要有两点，首先是迭代的过程是链式依赖的，而bagging策略是相互独立的；其次每次弱分类器是带不同的权重值的，而bagging策略每个分类器权重相等。经典的boosting系列算有有以下几种

1. Adaboost

2. GBDT

3. XGboost

其中Adaboost是最早提出，最为经典的一种监督学习算法，通过多次迭代的方式来构建多个弱分类器，并最终组合成为一个强分类器。

该算法的迭代的过程是一个相互依赖的过程，从第一次迭代开始，每个样本都赋予一个权重值，然后进行训练，根据训练出来的分类器的错误率来计算该分类器的权重，并据此调整样本的各个权重值，作为下一次迭代的输入，最终的强分类器由多个弱分类器的加权函数构成。

在具体的计算过程中，需要理解以下几个关键点

#### 1. 分类器误差率

分类器误差率的计算公式如下

表示的是分类错误的样本点的权重之和。

#### 2. 分类器的权重

对于每个弱分类器，需要计算其权重值，计算公式如下

其中的e表示该分类器的误差率。

#### 3. 样本权重

样本权重在第一次迭代时，统一赋值1/N, 其中N是样本总数，在接下来的迭代过程中，用分类器的误差率进行调整，公式如下

其中的Z表示规范化因子，计算公式如下

#### 4. 最终模型

最终模型由多个弱分类器的线性组合构成，公式如下

最终的分类结果通过sign函数来实现，公式如下

下面以一个实际的例子来说明该算法的迭代过程， 该数据包含10个样本，x1和x2两个特征，如下所示

1. 第一次迭代

每个样本的初始权重为1/10， 同时true用1表示，false用-1表示。由于具体分类器的模型可以有多种选择，为了这里直接给出分类的效果，以专注于理解分类器权重和样本权重的计算过程。

分类结果用prediction列表示

分类错误的样本有3个，每个样本的权重值都为0.1， 所以该分类器的误差率为0.3，带入公式，可以求得该分类器的权重

>>> 1/2 * np.log((1-0.3)/0.3)
0.42364893019360184

计算矫正之后的样本权重

# 初始权重
>>> a = np.array([0.1  for i in range(10)]).reshape(-1, 1)
# 实际值
>>> y = np.array([1, 1, 1, -1, -1, 1, -1, 1, -1, -1]).reshape(-1, 1)
# 预测值
>>> p = np.array([1, 1, -1, -1, -1, -1, -1, -1, -1, -1]).reshape(-1, 1)
# 重新计算样本的权重值
>>> a * np.e ** (y * p * 1/2 * -(np.log((1-0.3)/0.3)))
array([[0.06546537],
       [0.06546537],
       [0.15275252],
       [0.06546537],
       [0.06546537],
       [0.15275252],
       [0.06546537],
       [0.15275252],
       [0.06546537],
       [0.06546537]])
# z值
>>> (a * np.e ** (y * p * 1/2 * -(np.log((1-0.3)/0.3)))).sum()
0.9165151389911682
# 用z值进行矫正
>>> a * np.e ** (y * p * 1/2 * -(np.log((1-0.3)/0.3))) / (a * np.e ** (y * p * 1/2 * -(np.log((1-0.3)/0.3)))).sum()
array([[0.07142857],
       [0.07142857],
       [0.16666667],
       [0.07142857],
       [0.07142857],
       [0.16666667],
       [0.07142857],
       [0.16666667],
       [0.07142857],
       [0.07142857]])

第一次迭代完，每个样本的权重值如下

2. 第二次迭代

第二次迭代的预测结果如下

根据之前的公式，可以推导出新的样本权重值

3. 第三次迭代

结果如下

4. 第四次迭代

结果如下

5. 最终模型

经过4次迭代之后，迭代终止，组合4次迭代的结果就可以得到最终模型

计算过程如下

>>> alpha = np.array([0.42, 0.65, 0.38, 1.1]).reshape(-1, 1)
>>> r1 = np.array([1, 1, -1, -1, -1, -1, -1, -1, -1, -1]).reshape(-1, 1)
>>> r2 = np.array([-1, -1, 1, -1, -1, 1, -1, 1, 1, -1]).reshape(-1, 1)
>>> r3 = np.array([1, 1, -1, -1, -1, -1, -1, -1, -1, -1]).reshape(-1, 1)
>>> r4 = np.array([1, 1, 1, 1, 1, 1, 1, 1, -1, -1]).reshape(-1, 1)
# 线性组合
>>> alpha[0] * r1 + alpha[1] * r2 + alpha[2] * r3 + alpha[3] * r4
array([[ 1.25],
       [ 1.25],
       [ 0.95],
       [-0.35],
       [-0.35],
       [ 0.95],
       [-0.35],
       [ 0.95],
       [-1.25],
       [-2.55]])
# 通过sign函数来计算最终的分类
>>> np.sign(alpha[0] * r1 + alpha[1] * r2 + alpha[2] * r3 + alpha[3] * r4)
array([[ 1.],
       [ 1.],
       [ 1.],
       [-1.],
       [-1.],
       [ 1.],
       [-1.],
       [ 1.],
       [-1.],
       [-1.]])

以上就是Adaboost算法通过迭代调整样本权重，以及汇总多个分类器的具体计算过程。在实际运用中，通常用CART决策树作为核心的分类模型。

在scikit-learn中，使用该算法的代码如下

>>> from sklearn.ensemble import AdaBoostClassifier
>>> from sklearn.datasets import make_classification
>>> X, y = make_classification(n_samples=1000, n_features=4,
... n_informative=2, n_redundant=0,
... random_state=0, shuffle=False)
>>>
>>> clf = AdaBoostClassifier(n_estimators=100, random_state=0)
>>> clf.fit(X, y)
AdaBoostClassifier(n_estimators=100, random_state=0)
>>> clf.predict([[0, 0, 0, 0]])
array([1])

通过集成多个弱分类器的效果，Adaboost算法可以提高分类的准确率，同时具有较强的解释性；缺点在于对异常值比较敏感，异常点需要进行过滤。

·end·