Adaboost算法理论详解与实现

Posted by mudux on February 29, 2020

  前面介绍了Bagging方法中代表性的Random Forest方法,这里介绍Boosting中最具代表性的AdaBoost算法。
  AdaBoost算法包括AdaBoost分类算法和AdaBoost回归算法,如AdaBoost R2等。这里仅介绍AdaBoost分类算法。

1. AdaBoost算法

  假设给定一个二类分类的训练数据集

  其中,每个样本点由实例与标记组成。实例$x_i\in \subseteq R^n$,标记,$X$是实例空间,$y$是标记集合。AdaBoost利用以下算法,从训练数据中学习一系列弱分类器或基分类器,并将这些弱分类器线性组合成为一个强分类器。
  算法1.1 (AdaBoost):
  输入:训练数据集,其中,$x_i\in \subseteq R^n$,标记;弱学习算法;
  输出:最终分类器$G(x)$。

  1. 初始化训练数据的权值分布

  2. 对$m=1,2,\cdots,M$
    • 使用具有权值分布$D_m$的训练数据集学习,得到基本分类器

    • 计算$G_m(x)$ 在训练数据集上的分类误差率

    • 计算$G_m(x)$的系数

      这里的对数是自然对数。

    • 更新训练数据集的权值分布

      这里,$Z_m$是规范化因子

      它使$D_{m+1}$成为一个概率分布。

  3. 构建基本分类器的线性组合

    得到最终分类器

式(1.4)可以写成:

  由此可知,被基分类器$G_m(x)$误分类样本的权值得以扩大,而被正确分类样本的权值得以缩小,两相比较,误分类样本的权值被放大$e^{2\alpha_m}=\frac{1-e_m}{e_m}$倍。因此,五分类样本在下一轮学习中起更大的作用。不改变所给的训练数据,而不断改变训练数据权值的分布,使得训练数据在基分类器的学习中起不同的作用,这时AdaBoost的一个特点。

2. AdaBoost算法训练误差分析

  定理2.1 (AdaBoost的训练误差界) AdaBoost算法最终分类器的训练误差界为

  定理2.2 (二分类问题AdaBoost的训练误差界)

  这里,$\gamma_m=\frac{1}{2}-e_m$.

3. AdaBoost算法的解释

  可认为AdaBoost算法是模型为加法模型、损失函数是指数函数、学习算法为前向分布算法时的二类分类学习方法。

3.1 前向分布算法

  考虑加法模型(additive model)

  其中,$b(x;\gamma_m)$为基函数,$\gamma_m$为基函数的参数,$\beta_m$为基函数的系数。
  在给定训练数据及损失函数$L(y,f(x))$的条件下,学习加法模型$f(x)$成为经验风险最小化即损失函数极小化问题:

  通常这是一个复杂的优化问题。前向分布算法(forward stagewise algorithm)求解这一优化问题的想法是:因为学习的是加法模型,如果能够从前向后,每一步只学习一个基函数及其系数,逐步逼近优化目标函数式(3.2),那么就可以简化优化的复杂度。具体地,每步只需优化如下损失函数:

3.2 前向分布算法与AdaBoost

  定理3.1: AdaBoost算法是前向分步加法算法的特例。这时,模型是由基本分类器组成的加法模型,损失函数是指数函数。

  接下来证明
  当基函数是基本分类器时,该加法模型等价于AdaBoost的最终分类器

  由基本分类器$G_m(x)$及其系数$\alpha_m$组成,$m=1,2,\cdots,M$。前向分布算法逐一学习基函数,这一过程与AdaBoost算法逐一学习基本分类器的过程一致。
  当前向分布算法的损失函数是指数损失函数

  假设经过$m-1$轮迭代前向分步算法已经得到$f_{m-1}(x)$:

  在第$m$轮迭代得到$\alpha_m,G_m(x)$和$f_m(x)$.

  目标是使前向分步算法得到的$\alpha_m$和$G_m(x)$使$f_m(x)$在训练数据集$T$上的指数损失最小,即

  式(3.4)可以表示为:

  其中,。因为$\overline w_{mi}$即不依赖于$\alpha$也不依赖于$G$,所以与最小化无关。但需注意$\overline w_{mi}$依赖于$f_{m-1}(x)$,随着每一轮迭代而发生改变。
  现证使式(3.5)达到最小的就是AdaBoost算法所得到的,求解式(3.5)分两步:
  首先,求$G_m^{*}(x)$。对任意$\alpha \gt 0$,使式(3.5)最小的$G(x)$由下式得到:

  此分类器即为AdaBoost算法的基分类器$G_m(x)$,因为它是使第$m$轮加权训练数据分类误差率最小的基本分类器。
  之后,求

  将已求得的$G_m^{*}(x)$代入式(3.6),对$\alpha$求导并使导数为0,得到

  其中,$e_m$是分类误差率:

  这里的$\alpha_m^{*}$和AdaBoost的$\alpha_m$完全一致。
  最后来看每一轮样本权值的更新。由

  以及${\overline w_{mi}}=exp[-y_if_{m-1}(x_i)]$,可得

  这和AdaBoost算法的样本权值更新等价,只差规范化因子。

4. AdaBoost算法的正则化

  为了防止AdaBoost过拟合,通常也会加入正则化项,这个正则化项通常称为步长(learning rate)。定义为$v$,对于前面的弱学习器的迭代

  如果加上了正则化项,则有

  $v$的取值范围为$0 \lt v \le 1$。对于同样的训练集学习效果,较小的$v$意味着需要更多的弱学习器的迭代。通常用步长和迭代最大次数一起决定算法的拟合效果。

5. AdaBoos小结

  AdaBoost的主要优点有:

  • AdaBoost作为分类器时,分类精度很高;
  • 在AdaBoost框架下,可以使用各种回归分类器作为弱学习器,非常灵活;
  • 作为简单的二元分类器时,构造简单,结果可理解;
  • 不容易发生过拟合。

  AdaBoost的主要缺点有:

  • 对异常样本敏感,异常样本在迭代中可能会获得较高单位权重,影响最终的强学习器的预测准确性。

6. python代码实现

  AdaBoost.py文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
import numpy as np

class AdaBoostClassifier():
    def __init__(self, max_iter=50, verbose=False):
        self.max_iter = max_iter
        self.verbose = verbose

    def stumpClassify(self, data, dimen, threshVal, threshIneq):
        '''
        @description: decision stump classifier with given dimension
        @param : data - training data
                 dimen - split dimension
                 threshVal - split value
                 threshIneq - greater is 1 or lower is 1
        @return: predict label
        '''
        retArray = np.ones((np.shape(data)[0], 1))
        if threshIneq == 'lt':
            retArray[data[:, dimen] <= threshVal] = -1.0
        else:
            retArray[data[:, dimen] > threshVal] = -1.0
        return retArray
    
    def buildStump(self, data, classLabel, weight):
        '''
        @description: decision stump classifier which choose the best split dimension and split
                      value along all dimension
        @param:  data - training data features
                 classLabel - training data labels
                 weight - weigh array of data instance
        @return: bestStump - the dictionary save the best split dimension, split value, split direction and the alpha value of base classifier
                 minError - minimum predict error
                 bestClasEst - best predict labels
        '''
        m, n = np.shape(data)
        numSteps = 10
        bestStump = {}
        bestClasEst = np.zeros((m, 1))
        minError = np.inf
        for i in range(n):
            rangeMin = data[:, i].min()
            rangeMax = data[:, i].max()
            stepSize = (rangeMax - rangeMin) / numSteps
            for j in range(-1, int(numSteps) + 1):
                for inequal in ['lt', 'gt']:
                    threshVal = (rangeMin + float(j) * stepSize)
                    predictVals = self.stumpClassify(data, i, threshVal, inequal)
                    errArr = np.ones((m, 1))
                    errArr[predictVals == classLabel] = 0
                    weightedError = np.dot(weight.T, errArr)
                    if self.verbose:
                        print("split dim: %d, thresh: %.2f, thresh inequal: %s,\
                            the weighted error: %.3f" % (i, threshVal, inequal, weightedError))
                    if weightedError <= minError:
                        minError = weightedError
                        bestClasEst = predictVals.copy()
                        bestStump['dim'] = i
                        bestStump['thresh'] = threshVal
                        bestStump['ineq'] = inequal
        return bestStump, minError, bestClasEst
    
    def fit(self, data, classLabel):
        '''
        @description: fit function of Adaboost classifier
        @param: data - training data features
                classLabel - training data labels
        @return: all the base learner
        '''
        if not isinstance(data, (np.ndarray, np.generic)):
            data = np.array(data)
        if not isinstance(classLabel, (np.ndarray, np.generic)):
            classLabel = np.array(classLabel)
        self.weakClassArr = []
        m, _ = np.shape(data)
        weight = np.ones((m, 1)) / m
        aggClassEst = np.zeros((m, 1))
        for i in range(self.max_iter):
            if self.verbose:
                print("weight:", weight)            
            bestStump, error, classEst = self.buildStump(data, classLabel, weight)
            alpha = 0.5 * np.log((1.0 - error) / max(error, 1e-16))
            bestStump['alpha'] = alpha
            self.weakClassArr.append(bestStump)
            if self.verbose:
                print("classEst:", classEst.T)
            expon = -alpha * classEst * classLabel
            weight = weight * np.exp(expon)
            weight /= weight.sum()
            aggClassEst += alpha * classEst
            if self.verbose:
                print("aggClassEst:", aggClassEst.T)
            aggErrors = np.sign(aggClassEst) != classLabel
            errorRate = aggErrors.sum() / m
            if self.verbose:
                print("total error:", errorRate)
            if errorRate == 0:
                break
        return self.weakClassArr

    def predict(self, data):
        '''
        @description: prediction the label of test data
        @param : data - test data features
        @return: predicted labels of test data
        '''
        m = np.shape(data)[0]
        aggClassEst = np.zeros((m, 1))
        for i in range(len(self.weakClassArr)):
            classEst = self.stumpClassify(data, self.weakClassArr[i]['dim'], \
                self.weakClassArr[i]['thresh'], self.weakClassArr[i]['ineq'])
            aggClassEst += self.weakClassArr[i]['alpha'] * classEst
        if self.verbose:
            print("predict aggClassEst:", aggClassEst)                
        self.labels_ = np.sign(aggClassEst)
        self.labels_[np.where(self.labels_ == 0)] = -1
        return self.labels_

    def score(self, data, labels):
        '''
        @description: predict the label of test data and calculate the error rate
        @param: data - test data features
                labels - test data labels
        @return: accuracy
        '''
        pred = self.predict(data)
        acc = np.mean(pred == labels)
        if self.verbose:
            print("Accuracy:", acc)
        return acc

测试一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import numpy as np
from sklearn.datasets import load_iris
from sklearn.preprocessing import scale
from sklearn.model_selection import train_test_split
from AdaBoost import AdaBoostClassifier

iris = load_iris()
data = iris['data']
target = iris['target']
m = data.shape[0]
x = scale(data)
y = np.zeros((m, 1))
y[target == 1] = 1
y[target != 1] = -1

trainX, testX, trainY, testY = train_test_split(x, y, test_size=0.2)

ada = AdaBoostClassifier(max_iter=50, verbose=False)
ada.fit(trainX, trainY)
acc = ada.score(testX, testY)
print("Accuracy:", acc)

  输出为:

5.1   在测试集上的准确率为1,可见AdaBoost算法为一个分类精度很高的算法。

7. Reference

1 集成学习之Adaboost算法原理小结
2 决策树(中)
3 统计学习方法第八章-李航