开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 人工智能 -> 机器学习实战第七章利用AdaBoost元算法提高分类性能 -> 正文阅读

[人工智能]机器学习实战第七章利用AdaBoost元算法提高分类性能

作者:recommend-item-box type_blog clearfix

7.1基于数据集多重抽样的分类器

????前面已经介绍了五种不同的分类器，我们可以很自然地将不同的分类器组合起来，而这种组合结果则被称为集成方法或者元算法。使用集成方法时会有多种形式：可以是不同算法的集成，也可以是同一种算法在不同设置下的集成，还可以是数据集不同部分分配给不同分类器之后的集成。
????集成方法通过组合多个学习器来完成学习任务。基分类器一般采用的是弱可学习分类器，通过集成方法，组合成一个强可学习分类器。弱可学习分类器就是学习之后分类器的正确率很低，略优于猜的正确率。强可学习分类器是指学习之后分类器的正确率较高。
????集成方法主要包括Bagging和Boosting两种方法，Bagging和Boosting都是将已有的分类或回归算法通过一定方式组合起来，形成一个性能更加强大的分类器，更准确的说这是一种分类算法的组装方法，即将弱分类器组装成强分类器的方法。
????接下来我们将会学习如何利用机器学习问题的框架来应用AdaBoost算法。
AdaBoost算法的优缺点：

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

7.1.1bagging：基于数据随机重抽样的分类器构建方法

????自举汇聚法，也称bagging方法。是在从原始数据集选择S次后得到S个新数据集的一种技术。每个数据集都是通过在原始数据集中随机选择一个样本来进行替换而得到的。
????在S个数据集建好后，将某个学习算法分别作用于每个数据集就得到了S个分类器。当我们要对新数据进行分类时，就可以应用这S个分类器进行分类。与此同时，选择分类器投票结果中最多的类别作为最后的结果。

7.1.2boosting

????boosting：重赋权法迭代地训练基分类器。不同的分类器是通过串行训练而获得的，每个新分类器都根据已训练出的分类器的性能来进行训练。boosting分类的结果是基于所有分类器的加权求和结果的。
????boosting方法拥有多个版本，下面将讨论的是一个最流行的版本AdaBoost。
AdaBoost的一般流程：

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

7.1.3bagging、boosting二者之间的区别

????样本选择上：
????Bagging：训练集是在原始集中有放回选取的，从原始集中选出的各轮训练集之间是独立的。
????Boosting：每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化。而权值是根据上一轮的分类结果进行调整。
????样例权重：
????Bagging：使用均匀取样，每个样例的权重相等。
????Boosting：根据错误率不断调整样例的权值，错误率越大则权重越大。
????预测函数：
????Bagging：所有预测函数的权重相等。
????Boosting：每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重。
????并行计算：
????Bagging：各个预测函数可以并行生成。
????Boosting：各个预测函数只能顺序生成，因为后一个模型参数需要前一轮模型的结果。
????总结
????这两种方法都是把若干个分类器整合为一个分类器的方法，只是整合的方式不一样，最终得到不一样的效果，将不同的分类算法套入到此类算法框架中一定程度上提高了原单一分类器的分类效果，但是也增大了计算量。

7.2训练算法：基于错误提升分类器的性能

????AdaBoost是adaptive boosting（自适应boosting）的缩写，其运行过程如下：
????1、计算样本权重
????训练数据中的每个样本，并赋予其一个权重，这些权重构成了向量D。一开始，这些权重都初始化成相等值。
????2、计算错误率
????在训练数据上训练出一个弱分类器并计算该分类器的错误率 $\varepsilon$ 。错误率 $\varepsilon$ 的定义为：
$\varepsilon =\frac {未正确分类的样本数目}{所有样本数目}$
????3、计算弱分类器权重
????为了从所有弱分类器中得到最终的分类器结果，AdaBoost为每个分类器都分配了一个权重值alpha，这些alpha值是基于每个弱分类器的错误率计算的。alpha的计算公式如下： $\alpha =\frac{1}{2}ln(\frac{1-\varepsilon}{\varepsilon})$
????4、更新样本权重
????在同一数据集上再次训练弱分类器。在训练器的第二次训练中，将会重新调整每个样本的权重，其中第一次分对的样本的权重会降低，而第一次分错的样本的权重将会提高。
????如果样本被正确分类，那么该样本的权重更改为：
$D_{i}^{(t+1)}=\frac {D_{i}^{(t)}e^{-\alpha}}{Sum(D)}$
????如果样本被错分，那么该样本的权重更改为：
$D_{i}^{(t+1)}=\frac {D_{i}^{(t)}e^{\alpha}}{Sum(D)}$
????5、重复训练和调整权重
????在计算出D之后，AdaBoost又开始进入下一轮迭代。AdaBoost算法会不断地重复训练和调整权重的过程，知道训练错误率为0或者弱分类器的数目达到用户的指定值为止。
????AdaBoost算法的流程如下图所示：
在这里插入图片描述

7.3基于单层决策树构建弱分类器

????单层决策树（decision stump，也称决策树桩）是一种简单地决策树。
创建一个adaboost.py文件，添加下列代码：

import numpy as np
import matplotlib.pyplot as plt

def loadSimpData():
    """
    创建单层决策树的数据集
    Returns:
        dataMat - 数据矩阵
        classLabels - 数据标签
    """
    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
def showDataSet(dataMat, labelMat):
    """
    数据可视化
    Parameters:
        dataMat - 数据矩阵
        labelMat - 数据标签
    Returns:
        无
    """
    data_plus = []                                  #正样本
    data_minus = []                                 #负样本
    for i in range(len(dataMat)):
        if labelMat[i] > 0:
            data_plus.append(dataMat[i])
        else:
            data_minus.append(dataMat[i])
    data_plus_np = np.array(data_plus)                                             #转换为numpy矩阵
    data_minus_np = np.array(data_minus)                                         #转换为numpy矩阵
    plt.scatter(np.transpose(data_plus_np)[0], np.transpose(data_plus_np)[1])        #正样本散点图
    plt.scatter(np.transpose(data_minus_np)[0], np.transpose(data_minus_np)[1])     #负样本散点图
    plt.show()

测试代码：

import adaboost

dataArr, classLabels = adaboost.loadSimpData()
adaboost.showDataSet(dataArr, classLabels)

结果：
在这里插入图片描述
分析：
????可以看到，如果想要试着从某个坐标轴上选择一个值（即选择一条与坐标轴平行的直线）来将所有的蓝色圆点和橘色圆点分开，这显然是不可能的。这就是单层决策树难以处理的一个著名问题。

????通过使用多颗单层决策树，我们可以构建出一个能够对该数据集完全正确分类的分类器。程序的伪代码大致如下：

将最小错误率minError设为+∞
对数据集中的每一个特征（第一层循环）：
????对每个步长（第二层循环）：
????????对每个不等号（第三层循环）：
????????????建立一颗单层决策树并利用加权数据集对它进行测试
????????????如果错误率低于minError，则将当前单层决策树设为最佳单层决策树
返回最佳单层决策树

在adaboost.py中添加代码：

def stumpClassify(dataMatrix, dimen, threshVal, threshIneq):
    """
    单层决策树分类函数
    Parameters:
        dataMatrix - 数据矩阵
        dimen - 第dimen列，也就是第几个特征
        threshVal - 阈值
        threshIneq - 标志
    Returns:
        retArray - 分类结果
    """
    retArray = np.ones((np.shape(dataMatrix)[0], 1))  # 初始化retArray为1
    if threshIneq == 'lt':
        retArray[dataMatrix[:, dimen] <= threshVal] = -1.0  # 如果小于阈值,则赋值为-1
    else:
        retArray[dataMatrix[:, dimen] > threshVal] = -1.0  # 如果大于阈值,则赋值为-1
    return retArray


def buildStump(dataArr, classLabels, D):
    """
    找到数据集上最佳的单层决策树
    Parameters:
        dataArr - 数据矩阵
        classLabels - 数据标签
        D - 样本权重
    Returns:
        bestStump - 最佳单层决策树信息
        minError - 最小误差
        bestClasEst - 最佳的分类结果
    """
    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):
            for inequal in ['lt', 'gt']:  # 大于和小于的情况，均遍历。lt:less than，gt:greater than
                threshVal = (rangeMin + float(j) * stepSize)  # 计算阈值
                predictedVals = stumpClassify(dataMatrix, i, threshVal, inequal)  # 计算分类结果
                errArr = np.mat(np.ones((m, 1)))  # 初始化误差矩阵
                errArr[predictedVals == labelMat] = 0  # 分类正确的,赋值为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

测试代码：

import adaboost
import numpy as np

dataArr,classLabels = adaboost.loadSimpData()
D = np.mat(np.ones((5, 1)) / 5)
bestStump,minError,bestClasEst = adaboost.buildStump(dataArr,classLabels,D)
print('bestStump:\n', bestStump)
print('minError:\n', minError)
print('bestClasEst:\n', bestClasEst)

结果：
在这里插入图片描述
分析：
????程序通过遍历，改变不同的阈值，计算最终的分类误差，找到分类误差最小的分类方式，即为我们要找的最佳单层决策树。这里lt表示less than，表示分类方式，对于小于阈值的样本点赋值为-1，gt表示greater than，也是表示分类方式，对于大于阈值的样本点赋值为-1。
????经过遍历，我们找到，训练好的最佳单层局册数的最小分类误差为0.2，就是对于该数据集，无论用什么样的单层决策树，分类误差最小就是0.2。

7.4完整AdaBoost算法的实现

????整个实现的伪代码如下：
对每次迭代：
????利用buildStump()函数找到最佳的单层决策树
????将最佳单层决策树加入到单层决策树数组
????计算alpha
????计算新的权重向量D
????更新累计类别估计值
????如果错误率等于0.0，则退出循环

在adaboost.py中添加代码：

def adaBoostTrainDS(dataArr, classLabels, numIt = 40):
    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 = float(0.5 * np.log((1.0 - error) / max(error, 1e-16)))         #计算弱学习算法权重alpha,使error不等于0,因为分母不能为0
        bestStump['alpha'] = alpha                                          #存储弱学习算法权重
        weakClassArr.append(bestStump)                                      #存储单层决策树
        print("classEst: ", classEst.T)
        expon = np.multiply(-1 * alpha * np.mat(classLabels).T, classEst)     #计算e的指数项
        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                                             #误差为0，退出循环
    return weakClassArr, aggClassEst

测试代码：

import adaboost

dataArr,classLabels = adaboost.loadSimpData()
weakClassArr, aggClassEst = adaboost.adaBoostTrainDS(dataArr, classLabels)
print(weakClassArr)
print(aggClassEst)

结果：
第一轮迭代：
在这里插入图片描述
第二轮迭代：

第三轮迭代：
在这里插入图片描述
分析：
????在第一轮迭代中，D中的所有值都相等。于是，只有第一个数据点被错分了。因此在第二轮迭代中，D向量给第一个数据点0.5的权重。这就可以通过变量aggClassEst的符号来了解总的类别。第二次迭代之后，我们就会发现第一个数据点已经正确分类了，但此时最后一个数据点却是错分了。D向量中的最后一个元素变为0.5，而D向量中的其他值都变得非常小。最后，第三次迭代之后aggClassEst所有值的符号和真是类别标签都完全吻合，那么训练错误率为0，程序终止运行。

7.5测试算法：基于AdaBoost的分类

????现在需要做的就只是将弱分类器的训练过程从程序中抽出来，然后应用到某个具体的实例上去。每个弱分类器的结果以其对应的alpha值作为权重。所有这些弱分类器的结果加权求和就得到了最后的结果。

在adaboost.py中添加代码：

def adaClassify(datToClass,classifierArr):
    """
    AdaBoost分类函数
    Parameters:
        datToClass - 待分类样例
        classifierArr - 训练好的分类器
    Returns:
        分类结果
    """
    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)

测试代码：

import adaboost

dataArr,classLabels = adaboost.loadSimpData()
weakClassArr, aggClassEst = adaboost.adaBoostTrainDS(dataArr, classLabels)
print(adaboost.adaClassify([[0,0],[5,5]], weakClassArr))

结果：
在这里插入图片描述

分析：
????添加的adaClassify()函数遍历所有训练得到的弱分类器，利用单层决策树，输出的类别估计值乘以该单层决策树的分类器权重alpha，然后累加到aggClassEst上，最后通过sign函数最终的结果。
????可以看到，分类没有问题，测试(5,5)属于正类，(0,0)属于负类。

7.6示例：在一个难数据集上应用AdaBoost

在adaboost.py中添加代码：

def loadDataSet(fileName):
    numFeat = len((open(fileName).readline().split('\t')))
    dataMat = []; labelMat = []
    fr = open(fileName)
    for line in fr.readlines():
        lineArr = []
        curLine = line.strip().split('\t')
        for i in range(numFeat - 1):
            lineArr.append(float(curLine[i]))
        dataMat.append(lineArr)
        labelMat.append(float(curLine[-1]))
    return dataMat, labelMat

测试代码：

import adaboost
import numpy as np


dataArr, LabelArr = adaboost.loadDataSet('horseColicTraining2.txt')
weakClassArr, aggClassEst = adaboost.adaBoostTrainDS(dataArr, LabelArr)
testArr, testLabelArr = adaboost.loadDataSet('horseColicTest2.txt')
predictions0 = adaboost.adaClassify(dataArr, weakClassArr)
errArr0 = np.mat(np.ones((len(dataArr), 1)))
predictions1 = adaboost.adaClassify(testArr, weakClassArr)
errArr1 = np.mat(np.ones((len(testArr), 1)))
print('训练集的错误率:%.3f%%' % float(errArr0[predictions0 != np.mat(LabelArr).T].sum() / len(dataArr) * 100))
print('测试集的错误率:%.3f%%' % float(errArr1[predictions1 != np.mat(testLabelArr).T].sum() / len(testArr) * 100))

结果：
在这里插入图片描述

分析：
????训练集的错误率为19.732%，测试集的错误率为19.403%，可以看到相对于第五章的Logistic回归方法，错误率由35.970%下降到了19.403%，降低了很多。
????这个仅仅是我们训练40个弱分类器的结果，如果训练更多弱分类器，效果会更好。但是当弱分类器数量过多的时候，你会发现训练集错误率降低很多，但是测试集错误率提升了很多，这种现象就是过拟合(overfitting)。