“机器学习实战”刻意练习——分类问题：AdaBoost

ゝ一纸荒年。 2023-06-18 13:00 14阅读 0赞

参考：

*  [Python3《机器学习实战》学习笔记（十）：提升分类器性能利器-AdaBoost - Jack-Cui][Python3_-AdaBoost - Jack-Cui]

# 一、概述 #

**元算法**，或者说**集成方法**是对其他算法进行组合的一种方式。

接下来我们将集中关注一个称作**AdaBoost**的最流行的元算法。

使用**集成方法**时会有多种形式：可以是**不同算法**的集成，也可以是**同一算法在不同设置下**的集成，还可以是**数据集不同部分分配给不同分类器**之后的集成。

*  优缺点  
    优点：**泛化错误率低**，**易编码**，可以应用在大部分分类器上，**无参数调整**。  
    缺点：**对离群点敏感**。
 *  适用数据类型：  
    **数值型**和**标称型**数据。
 *  AdaBoost的一般流程

1.  收集数据：可以使用任意方法。
2.  准备数据：依赖于所使用的**弱分类器类型**，我们使用的是**单层决策树**，这种分类器可以处理任何数据类型。作为弱分类器，简单分类器的效果更好。
3.  分析数据：可以使用任意方法。
4.  训练算法：AdaBoost的大部分时间都用在训练上，分类器将多次在同一数据集上训练弱分类器。
5.  测试算法：计算分类的错误率。
6.  使用算法：同SVM一样，AdaBoost预测两个类别中的一个。如果想把它应用到多个类别的场合，那么就要像多类SVM中的做法一样对AdaBoost进行修改。

# 二、相关原理 #

## 1.bagging与boosting ##

**自举汇聚法**（bootstrap aggregating），也称为**bagging方法**，是在从原始数据集选择S次后得到S个新数据集的一种技术。  
每个数据集都是通过在原始数据集中**随机选择**一个样本来进行**替换**而得到的。这里的替换就意味着可以多次地选择同一样本，即新数据集中可以有**重复**的值，而原始数据集的某些值在新集合中则**不再出现**。最后新数据集和原数据集的**大小相等**。

在S个数据集建好之后，将某个学习算法分别作用于每个数据集就得到了S个分类器。当我们要对新数据进行分类时，就可以应用这S个分类器进行分类。与此同时，选择**分类器投票结果中最多的类别**作为最后的分类结果。

当然，还有一些更先进的bagging方法，比如**随机森林**（random forest）。

boosting是一种与bagging类似的技术。  
不论是在boosting还是bagging当中，所使用的多个分类器的类型都是**一致**的。但是在前者当中，不同的分类器是通过**串行训练**而获得的，每个新分类器都根据**已训练出的分类器的性能**来进行训练。  
boosting是通过**集中关注被已有分类器错分的那些数据**来获得新的分类器。

由于boosting分类的结果是基于**所有分类器的加权求和**结果的，因此boosting与bagging不太一样。  
bagging中的分类器权重是**相等**的，而boosting中的分类器权重并不相等，每个权重代表的是其对应分类器在**上一轮迭代中的成功度**。

> Bagging、Boosting二者之间的区别:  
> 1.样本选择上：  
> Bagging：训练集是在原始集中有放回选取的，从原始集中选出的各轮训练集之间是独立的。  
> Boosting：每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化。而权值是根据上一轮的分类结果进行调整。  
> 2.样例权重：  
> Bagging：使用均匀取样，每个样例的权重相等。  
> Boosting：根据错误率不断调整样例的权值，错误率越大则权重越大。  
> 3.预测函数：  
> Bagging：所有预测函数的权重相等。  
> Boosting：每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重。  
> 4.并行计算：  
> Bagging：各个预测函数可以并行生成。  
> Boosting：各个预测函数只能顺序生成，因为后一个模型参数需要前一轮模型的结果。  
> ————————————————  
> 版权声明：本文为CSDN博主「Jack-Cui」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。  
> 原文链接：https://blog.csdn.net/c406495762/article/details/78212124

boosting方法拥有多个版本，我们将只关注其中一个最流行的版本**AdaBoost**。

## 2.AdaBoost算法 ##

### （1）训练算法：基于错误提升分类器的性能 ###

AdaBoost是adaptive boosting（**自适应boosting**）的缩写

AdaBoost运行过程如下：  
训练数据中的每个样本，并**赋予其一个权重**，这些权重构成了向量D。  
一开始，这些权重都初始化成**相等**值。首先在训练数据上训练出一个弱分类器并计算该分类器的错误率，然后在同一数据集上再次训练弱分类器。在分类器的第二次训练当中，将会**重新调整每个样本的权重**，其中**第一次分对的样本的权重将会降低，而第一次分错的样本的权重将会提高**。为了从所有弱分类器中得到最终的分类结果，AdaBoost为每个分类器都分配了一个权重值  α \\alpha α ，这些  α \\alpha α 值是基于每个弱分类器的**错误率**进行计算的。其中，错误率ε的定义为：  
![在这里插入图片描述][20191207161658375.png]  
而  α \\alpha α 的计算公式如下：  
 α = 1 2 l n 1 − ε ε \\alpha =\\frac\{1\}\{2\}ln\\frac\{1-\\varepsilon \}\{\\varepsilon \} α=21lnε1−ε

计算出alpha值之后，可以对权重向量D进行更新，以使得那些正确分类的样本的权重降低而错分样本的权重升高。  
D的计算方法如下:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmFzaGlfRg_size_16_color_FFFFFF_t_70]  
在计算出D之后，AdaBoost又开始进入下一轮迭代。  
AdaBoost算法会不断地重复训练和调整权重的过程，直到**训练错误率为0**或者**弱分类器的数目达到用户的指定值**为止。

# 三、代码实现 #

## 1.基于单层决策树构建弱分类器 ##

**单层决策树**（decision stump），也称决策树桩，它是一种简单的决策树，通过给定的阈值，进行分类。  
首先按惯例建立一个示范数据集

import numpy as np
    import matplotlib.pyplot as plt
    
    def loadSimpData():
        """ 创建单层决策树的数据集 - - - - """
        datMat = np.matrix([[ 1. ,  2.1],
            [ 1.5,  1.6],
            [ 1.3,  1. ],
            [ 1. ,  1. ],
            [ 2. ,  1. ]])
        classLabels = [1.0, 1.0, -1.0, -1.0, 1.0]
        return datMat,classLabels

数据集分布如下图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmFzaGlfRg_size_16_color_FFFFFF_t_70 1]  
如果想要试着从某个坐标轴上选择一个值（即选择一条与坐标轴平行的直线）来将所有的圆形点和方形点分开，显然是不可能的，这就是单层决策树难以处理的。但是通过使用多棵单层决策树，我们就可以构建出一个能够对该数据集完  
全正确分类的分类器。

下面我们将通过遍历，改变不同的阈值，计算最终的分类误差，找到**分类误差最小**的分类方式，即为我们要找的**最佳单层决策树**。

def stumpClassify(dataMatrix,dimen,threshVal,threshIneq):
        """ 单层决策树分类 - - - - dataMatrix - 数据矩阵 dimen - 第dimen列，也就是第几个特征 threshVal - 阈值 threshIneq - 标志 """
        #初始化retArray为1
        retArray = np.ones((np.shape(dataMatrix)[0],1))          
        if threshIneq == 'lt':
            #如果小于阈值,则赋值为-1
            retArray[dataMatrix[:,dimen] <= threshVal] = -1.0         
        else:
            #如果大于阈值,则赋值为-1
            retArray[dataMatrix[:,dimen] > threshVal] = -1.0         
        return retArray
    
    def buildStump(dataArr,classLabels,D):
        """ 找到数据集上最佳的单层决策树 - - - - dataArr - 数据矩阵 classLabels - 数据标签 D - 样本权重 """
        dataMatrix = np.mat(dataArr); labelMat = np.mat(classLabels).T
        m,n = np.shape(dataMatrix)
        numSteps = 10.0; bestStump = { }; bestClasEst = np.mat(np.zeros((m,1)))
        #最小误差初始化为正无穷大
        minError = float('inf')  
        #遍历所有特征 
        for i in range(n):   
            #找到特征中最小的值和最大值 
            rangeMin = dataMatrix[:,i].min(); rangeMax = dataMatrix[:,i].max()
            #计算步长 
            stepSize = (rangeMax - rangeMin) / numSteps                                
            for j in range(-1, int(numSteps) + 1):     
                #大于和小于的情况，均遍历。lt:less than，gt:greater than 
                for inequal in ['lt', 'gt']:    
                    #计算阈值 
                    threshVal = (rangeMin + float(j) * stepSize)                     
                    #计算分类结果
                    predictedVals = stumpClassify(dataMatrix, i, threshVal, inequal)
                    #初始化误差矩阵
                    errArr = np.mat(np.ones((m,1)))                   
                    #分类正确的,赋值为0 
                    errArr[predictedVals == labelMat] = 0    
                    #计算误差 
                    weightedError = D.T * errArr                                      
                    print("split: dim %d, thresh %.2f, thresh ineqal: %s, the weighted error is %.3f" % (i, threshVal, inequal, weightedError))
                    #找到误差最小的分类方式
                    if weightedError < minError:                                     
                        minError = weightedError
                        bestClasEst = predictedVals.copy()
                        bestStump['dim'] = i
                        bestStump['thresh'] = threshVal
                        bestStump['ineq'] = inequal
        return bestStump,minError,bestClasEst
    
    if __name__ == '__main__':
        dataArr,classLabels = loadSimpData()
        D = np.mat(np.ones((5, 1)) / 5)
        bestStump,minError,bestClasEst = buildStump(dataArr,classLabels,D)
        print('bestStump:\n', bestStump)
        print('minError:\n', minError)
        print('bestClasEst:\n', bestClasEst)

结果：

split: dim 0, thresh 0.90, thresh ineqal: lt, the weighted error is 0.400
    split: dim 0, thresh 0.90, thresh ineqal: gt, the weighted error is 0.600
    split: dim 0, thresh 1.00, thresh ineqal: lt, the weighted error is 0.400
    ...
    bestStump:
     {'dim': 0, 'thresh': 1.3, 'ineq': 'lt'}
    minError:
     [[0.2]]
    bestClasEst:
     [[-1.]
     [ 1.]
     [-1.]
     [-1.]
     [ 1.]]

## 2.使用AdaBoost提升分类器性能 ##

def adaBoostTrainDS(dataArr, classLabels, numIt = 40):
    	""" 使用AdaBoost算法提升弱分类器性能 - - - - dataArr - 数据矩阵 classLabels - 数据标签 numIt - 最大迭代次数 """
        weakClassArr = []
        m = np.shape(dataArr)[0]
        #初始化权重
        D = np.mat(np.ones((m, 1)) / m)                                            
        aggClassEst = np.mat(np.zeros((m,1)))
        for i in range(numIt):
            #构建单层决策树
            bestStump, error, classEst = buildStump(dataArr, classLabels, D)     
            print("D:",D.T)
            #计算并储存弱学习算法权重alpha,使error不等于0,因为分母不能为0
            alpha = float(0.5 * np.log((1.0 - error) / max(error, 1e-16)))         
            bestStump['alpha'] = alpha
            weakClassArr.append(bestStump)
            print("classEst: ", classEst.T)
            #计算e的指数项
            expon = np.multiply(-1 * alpha * np.mat(classLabels).T, classEst)     
            D = np.multiply(D, np.exp(expon))  
            #根据样本权重公式，更新样本权重 
            D = D / D.sum()                                                        
            #计算AdaBoost误差，当误差为0的时候，退出循环
            aggClassEst += alpha * classEst                                 
            print("aggClassEst: ", aggClassEst.T)
            aggErrors = np.multiply(np.sign(aggClassEst) != np.mat(classLabels).T, np.ones((m,1))) 
            errorRate = aggErrors.sum() / m
            print("total error: ", errorRate)
            if errorRate == 0.0: break
        return weakClassArr, aggClassEst
    
    if __name__ == '__main__':
        dataArr,classLabels = loadSimpData()
        weakClassArr, aggClassEst = adaBoostTrainDS(dataArr, classLabels)
        print(weakClassArr)
        print(aggClassEst)

结果：

split: dim 0, thresh 0.90, thresh ineqal: lt, the weighted error is 0.400
    split: dim 0, thresh 0.90, thresh ineqal: gt, the weighted error is 0.600
    split: dim 0, thresh 1.00, thresh ineqal: lt, the weighted error is 0.400
    ...
    D: [[0.28571429 0.07142857 0.07142857 0.07142857 0.5       ]]
    classEst:  [[1. 1. 1. 1. 1.]]
    aggClassEst:  [[ 1.17568763  2.56198199 -0.77022252 -0.77022252  0.61607184]]
    total error:  0.0
    [{'dim': 0, 'thresh': 1.3, 'ineq': 'lt', 'alpha': 0.6931471805599453}, {'dim': 1, 'thresh': 1.0, 'ineq': 'lt', 'alpha': 0.9729550745276565}, {'dim': 0, 'thresh': 0.9, 'ineq': 'lt', 'alpha': 0.8958797346140273}]
    [[ 1.17568763]
     [ 2.56198199]
     [-0.77022252]
     [-0.77022252]
     [ 0.61607184]]

观察结果可以发现，该数组包含三部词典，其中包含了分类所需要的所有信息。

## 3.测试算法：基于 AdaBoost 的分类 ##

一旦拥有了多个弱分类器以及其对应的alpha值，进行测试就变得相当容易了。每个弱分类器的结果以其对应的alpha值作为权重,所有这些弱分类器的结果**加权求和**就得到了最后的结果。

def adaClassify(datToClass,classifierArr):
        """ AdaBoost分类函数 - - - - datToClass - 待分类样例 classifierArr - 训练好的分类器 """
        dataMatrix = np.mat(datToClass)
        m = np.shape(dataMatrix)[0]
        aggClassEst = np.mat(np.zeros((m,1)))
        for i in range(len(classifierArr)):                                        #遍历所有分类器，进行分类
            classEst = stumpClassify(dataMatrix, classifierArr[i]['dim'], classifierArr[i]['thresh'], classifierArr[i]['ineq'])            
            aggClassEst += classifierArr[i]['alpha'] * classEst
            print(aggClassEst)
        return np.sign(aggClassEst)
    
    if __name__ == '__main__':
        dataArr,classLabels = loadSimpData()
        weakClassArr, aggClassEst = adaBoostTrainDS(dataArr, classLabels)
        print(adaClassify([[0,0],[5,5]], weakClassArr))

结果：

...
    D: [[0.28571429 0.07142857 0.07142857 0.07142857 0.5       ]]
    classEst:  [[1. 1. 1. 1. 1.]]
    aggClassEst:  [[ 1.17568763  2.56198199 -0.77022252 -0.77022252  0.61607184]]
    total error:  0.0
    [[-0.69314718]
     [ 0.69314718]]
    [[-1.66610226]
     [ 1.66610226]]
    [[-2.56198199]
     [ 2.56198199]]
    [[-1.]
     [ 1.]]

可以看到，分类没有问题，(5,5)属于正类，(0,0)属于负类。

# 四、扩展：非均衡分类问题 #

在我们结束分类这个主题之前，还必须讨论一个问题。在前面的所有分类介绍中，我们都假设所有类别的分类代价是一样的。我们构建了分类器，但是并没有对分类后的情形加以讨论。

之前我们构建了一个用于检测患疝病的马匹是否存活的系统，假如某人给我们牵来一匹马，他希望我们能预测这匹马能否生存。我们说马会死，那么他们就可能会对马实施安乐死，而不是通过给马喂药来延缓其不可避免的死亡过程。  
我们的预测也许是错误的，马本来是可以继续活着的。毕竟，我们的分类器只有80%的精确率（accuracy）。如果我们预测错误，那么我们将会错杀了一个如此昂贵的动物，更不要说人对马还存在情感上的依恋。

还可以举出很多很多这样的例子，坦白地说，在大多数情况下**不同类别的分类代价并不相等**。

到现在为止，本书都是基于错误率来衡量分类器任务的成功程度的。错误率指的是在所有测试样例中错分的样例比例。实际上，这样的度量错误掩盖了样例如何被分错的事实。在机器学习中，有一个普遍适用的称为**混淆矩阵**（confusion matrix）的工具，它可以帮助人们更好地了解分类中的错误。

我们考虑只针对一个简单的二类问题混淆矩阵，在下表中，给出了该混淆矩阵。

在这个二类问题中，如果将一个正例判为正例，那么就可以认为产生了一个  
真正例（True Positive，TP，也称真阳）；如果对一个反例正确地判为反例，则认为产生了一个真反例（True Negative，TN，也称真阴）。相应地，另外两种情况则分别称为伪反例（False Negative，FN，也称假阴）和伪正例（False Positive，FP，也称假阳）

在分类中，当某个类别的重要性高于其他类别时，我们就可以利用上述定义来定义出多个比错误率更好的新指标:

1.  **正确率**（Precision），它等于TP/(TP+FP)，给出的是预测为正例的样本中的真正正例的比例。
2.  **召回率**（Recall），它等于TP/(TP+FN)，给出的是预测为正例的真实正例占所有真实正例的比例。在召回率很大的分类器中，真正判错的正例的数目并不多。  
    另一个用于度量分类中的非均衡性的工具是**ROC曲线**（ROC curve），ROC代表**接收者操作特征**（receiver operating characteristic）  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmFzaGlfRg_size_16_color_FFFFFF_t_70 2]  
    的ROC曲线中，给出了两条线，一条虚线一条实线。图中的横轴是伪正例的比例（假阳率=FP/(FP+TN)），而纵轴是真正例的比例（真阳率=TP/(TP+FN)）。ROC曲线给出的是**当阈值变化时假阳率和真阳率的变化情况**。左下角的点所对应的是将所有样例判为反例的情况，而右上角的点对应的则是将所有样例判为正例的情况。虚线给出的是随机猜测的结果曲线。

在理想的情况下，最佳的分类器应该**尽可能地处于左上角**，这就意味着分类器在假阳率很低的同时获得了很高的真阳率。  
对不同的ROC曲线进行比较的一个指标是**曲线下的面积**（Area Unser the Curve，AUC）。**AUC**给出的是分类器的平均性能值，当然它并不能完全代替对整条曲线的观察。

# 五、小结 #

**集成方法**通过组合多个分类器的分类结果，获得了比简单的单分类器更好的分类结果。有一些利用不同分类器的集成方法，但是本章只介绍了那些利用同一类分类器的集成方法。  
多个分类器组合可能会进一步凸显出单分类器的不足，比如**过拟合**问题。如果分类器之间差别显著，那么多个分类器组合就可能会缓解这一问题。分类器之间的差别可以是算法本身或者是应用于算法上的数据的不同。  
本章介绍的两种集成方法是**bagging和boosting**。在bagging中，是通过随机抽样的替换方式，得到了与原始数据集规模一样的数据集。而boosting在bagging的思路上更进了一步，它在数据集上顺序应用了多个不同的分类器。

AdaBoost以弱学习器作为基分类器，并且输入数据，使其通过**权重向量**进行加权。在第一次迭代当中，所有数据都等权重。但是在后续的迭代当中，前次迭代中分错的数据的权重会增大。这种针对错误的调节能力正是AdaBoost的长处。  
我们以**单层决策树作为弱学习器**构建了AdaBoost分类器。实际上，AdaBoost函数可以应用于任意分类器，只要该分类器能够处理加权数据即可。AdaBoost算法十分强大，它能够快速处理其他分类器很难处理的数据集。

**非均衡分类问题**是指在分类器训练时正例数目和反例数目不相等（相差很大）。该问题在错分正例和反例的代价不同时也存在。本章不仅考察了一种不同分类器的评价方法——**ROC曲线**，还介绍了**正确率**和**召回率**这两种在类别重要性不同时，度量分类器性能的指标。

[Python3_-AdaBoost - Jack-Cui]: https://blog.csdn.net/c406495762/article/details/78212124
[20191207161658375.png]: https://img-blog.csdnimg.cn/20191207161658375.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmFzaGlfRg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191207164111908.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmFzaGlfRg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmFzaGlfRg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191207165347572.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmFzaGlfRg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmFzaGlfRg_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191209225001593.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmFzaGlfRg==,size_16,color_FFFFFF,t_70