机器学习入门（16）——利用AdaBoost算法提高分类性能

本系列代码托管于：https://github.com/chintsan-code/machine-learning-tutorials
本篇使用的项目为：adaboost_trainDS、adaboost_classad、aboost_horseColic

一、集成学习

集成学习(ensemble learning)通过构建并结合多个学习器来完成学习任务，有时也被称为多分类器系统(multi-classifier system)、基于委员会的学习(committee-based learning)等。

下图显示出集成学习的一般结构:先产生一组“个体学习器”(individual learner)，再用某种策略将它们结合起来。个体学习器通常由一个现有的学习算法从训练数据产生，例如C4.5决策树算法、BP神经网络算法等，此时集成中只包含同种类型的个体学习器，例如“决策树集成”中全是决策树，“神经网络集成”中全是神经网络，这样的集成是“同质”(homogeneous)。同质集成中的个体学习器亦称“基学习器”(base learner)，相应的学习算法称为“基学习算法”(base learning algorithm)。集成也可包含不同类型的个体学习器，例如同时包含决策树和神经网络，这样的集成是“异质”的(heterogenous)。异质集成中的个体学习器由不同的学习算法生成，这时就不再有基学习算法；相应的，个体学习器一般不称为基学习器，常称为“组件学习器”(component learner)或直接称为个体学习器。

集成学习通过将多个学习器进行结合，常可获得比单一学习器显著优越的泛化性能这对”弱学习器”(weak learner)尤为明显，因此集成学习的很多理论研究都是针对弱学习器进行的，而基学习器有时也被称为弱学习器，但需要注意的是，虽然从理论上来说使用弱学习器集成足以获得好的性能，但在实践中出于种种考虑，例如希望使用较少的个体学习器，或是重用关于常见学习器的一些经验等，人们往往会使用比较强的学习器。

根据个体学习器的生成方式，目前的集成学习方法大致可分为两大类，即个体学习器问存在强依赖关系、必须串行生成的序列化方法，以及个体学习器间不存在强依赖关系、可同时生成的并行化方法;前者的代表是Boosting，后者的代表是Bagging和”随机森林”(Random Forest)。

二、Bagging和Boosting

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

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

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

当然，还有一些更先进的bagging方法，比如随机森林（random forest）。接下来我们将注意力转向一个与bagging类似的集成分类器方法boosting。

2. boosting

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

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

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

三、AdaBoot算法

能否使用弱分类器和多个实例来构建一个强分类器？这是一个非常有趣的理论问题。这里的“弱”意味着分类器的性能比随机猜测要略好，但是也不会好太多。这就是说，在二分类情况下弱分类器的错误率会高于50%，而“强”分类器的错误率将会低很多。AdaBoost算法即脱胎于上述理论问题。

AdaBoost是adaptive boosting（自适应boosting）的缩写，其运行过程如下：训练数据中的每个样本，并赋予其一个权重，这些权重构成了向量\(D\)。一开始，这些权重都初始化成相等值。首先在训练数据上训练出一个弱分类器并计算该分类器的错误率，然后在同一数据集上再次训练弱分类器。在分类器的第二次训练当中，将会重新调整每个样本的权重，其中第一次分对的样本的权重将会降低，而第一次分错的样本的权重将会提高。为了从所有弱分类器中得到最终的分类结果，AdaBoost为每个分类器都分配了一个权重值\(\alpha\)，这些\(\alpha\)值是基于每个弱分类器的错误率进行计算的。

其中，错误率\(\varepsilon\)的定义为：
$$\varepsilon=\frac{未正确分类的样本数目}{所有样本数目}$$
而\(\alpha\)的计算公式如下：
$$\alpha=\frac{1}{2}\ln(\frac{1-\varepsilon}{\varepsilon})$$

AdaBoost算法的流程如下图所示：

计算出\(\alpha\)值之后，可以对权重向量\(D\)进行更新，以使得那些正确分类的样本的权重降低而错分样本的权重升高。\(D\)的计算方法如下。

如果某个样本被正确分类，那么该样本的权重更改为：
$$D^{(t+1)}_i=\frac{D^{(t)}_ie^{-\alpha}}{sum(D)}$$
而如果某个样本被错分，那么该样本的权重更改为：
$$D^{(t+1)}_i=\frac{D^{(t)}_ie^{\alpha}}{sum(D)}$$

在计算出D之后，AdaBoost又开始进入下一轮迭代。AdaBoost算法会不断地重复训练和调整权重的过程，直到训练错误率为0或者弱分类器的数目达到用户的指定值为止。

接下来，我们将建立完整的AdaBoost算法。在这之前，我们首先必须通过一些代码来建立弱分类器及保存数据集的权重。

四、代码实现

本次我们选用的弱分类器为单层决策树。单层决策树（decision stump，也称决策树桩）是一种简单的决策树。前面我们已经介绍了决策树的工作原理，接下来将构建一个单层决策树，而它仅基于单个特征来做决策。由于这棵树只有一次分裂过程，因此我们也把它称为决策树桩。

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

我们使用下面的程序构建单层决策树：

# 用于测试是否有某个值小于或者大于我们正在测试的阈值
# 通过阈值比较对数据进行分类，所有在阈值一边的数据会分到类别-1，而在另外一边的数据分到类别+1
def stumpClassify(dataMatrix, dimen, threshVal, threshIneq):  # just classify the data
    retArray = ones((shape(dataMatrix)[0], 1))  # 每个数据点类别的累加估计值
    # 通过数组过滤来实现，首先将返回数组retArray的全部元素设置为1，然后将所有不满足不等式要求的元素设置为-1
    if threshIneq == 'lt':  # less than
        retArray[dataMatrix[:, dimen] <= threshVal] = -1.0
    else:  # greater than
        retArray[dataMatrix[:, dimen] > threshVal] = -1.0
    return retArray


# 在一个加权数据集中循环，并找到具有最低错误率的单层决策树(决策树桩)
def buildStump(dataArr, classLabels, D):  # D为计算时的权重向量
    dataMatrix = mat(dataArr)
    labelMat = mat(classLabels).T
    m, n = shape(dataMatrix)  # m:数据集样本数, n:数据集特征数
    numSteps = 10.0
    bestStump = {}  # 用于存储给定权重向量D时所得到的最佳单层决策树的相关信息
    bestClasEst = mat(zeros((m, 1)))
    minError = inf  # init error sum, to +infinity 最小误差率，将其初始值设置为正无穷大，之后用于寻找可能的最小错误率
    for i in range(n):  # loop over all dimensions  # 对所有特征进行遍历
        rangeMin = dataMatrix[:, i].min()
        rangeMax = dataMatrix[:, i].max()
        stepSize = (rangeMax - rangeMin) / numSteps
        for j in range(-1, int(numSteps) + 1):  # loop over all range in current dimension
            for inequal in ['lt', 'gt']:  # go over less than and greater than
                threshVal = (rangeMin + float(j) * stepSize)
                predictedVals = stumpClassify(dataMatrix, i, threshVal,
                                              inequal)  # call stump classify with i, j, lessThan
                errArr = mat(ones((m, 1)))
                errArr[predictedVals == labelMat] = 0  # 预测值等于样本标签，将其置为0
                weightedError = D.T * errArr  # calc total error multiplied by D  计算加权错误率
                print("split: dim %d, thresh %.2f, thresh ineqal: %s, the weighted error is %.3f" % (i, threshVal, inequal, weightedError))
                if weightedError < minError:  # 如果错误率低于minError，则将当前单层决策树设为最佳单层决策树
                    minError = weightedError
                    bestClasEst = predictedVals.copy()
                    bestStump['dim'] = i
                    bestStump['thresh'] = threshVal
                    bestStump['ineq'] = inequal
    return bestStump, minError, bestClasEst  # bestClasEst为估计的类别向量

第一个函数stumpClassify()是通过阈值比较对数据进行分类的。所有在阈值一边的数据会分到类别-1，而在另外一边的数据分到类别+1。该函数可以通过数组过滤来实现，首先将返回数组的全部元素设置为1，然后将所有不满足不等式要求的元素设置为-1。可以基于数据集中的任一元素进行比较，同时也可以将不等号在大于、小于之间切换。事实上这个阈值就是在上图中的坐标轴中选取一个值，将数据一分为二(决策树桩)。

第二个函数buildStump()将会遍历stumpClassify()函数所有的可能输入值，并找到数据集上最佳的单层决策树。这里的“最佳”是基于数据的权重向量\(D\)来定义的，实际上就是通过对\(D\)进行加权计算错误率。在确保输入数据符合矩阵格式之后，整个函数就开始执行了。第一层for循环在数据集的所有特征(也就是输入数据集的维数dim，在本例程中数据集为二维数据)上遍历，考虑到数值型的特征，我们就可以通过计算最小值(rangeMin)和最大值(rangeMax)来了解应该需要多大的步长(stepSize)。然后，第二层for循环再在这些值上遍历。甚至将阈值设置为整个取值范围之外也是可以的。因此，在取值范围之外还应该有两个额外的步骤。最后一个for循环则是在大于和小于之间切换不等式。在本函数中构建了一个称为bestStump的空字典，这个字典用于存储给定权重向量\(D\)时所得到的最佳单层决策树的相关信息。变量numSteps用于在特征的所有可能值上进行遍历(用来确定步长stepSize)。而变量minError则在一开始就初始化成正无穷大inf，之后用于寻找可能的最小错误率。

在嵌套的三层for循环之内，我们在数据集及三个循环变量上调用上一个函数stumpClassify()。基于这些循环变量，该函数将会返回分类预测结果。接下来构建一个列向量errArr，如果弱分类器预测值predictedVals中的值不等于labelMat中的真正类别标签值，那么errArr的相应位置为1。将错误向量errArr和权重向量D的相应元素相乘并求和(即通过对\(D\)进行加权计算错误率，分类正确的样本权重置为0，分类错误的样本权重置为1，这样就可以突出分类错误的样本)，就得到了数值weightedError。这就是AdaBoost和弱分类器交互的地方。这里，我们是基于权重向量D而不是其他错误计算指标来评价分类器的。如果需要使用其他分类器的话，就需要考虑D上最佳分类器所定义的计算过程。最后跳出该函数后我们可以得到一个目前效果最佳的弱分类器，以及它的分类错误率minError，这个错误率将在后面用于更新\(\alpha\)和\(D\)。

最后，将当前的错误率与已有的最小错误率进行对比，如果当前的值较小，那么就在词典bestStump中保存该单层决策树。字典、错误率和类别估计值都会返回给AdaBoost算法。

目前我们得到了一个目前效果最佳的弱分类器，接下来我们会根据它的分类错误率minError，来计算该分类器的\(\alpha\)并更新\(D\)用于迭代出下一个弱分类器。

def adaBoostTrainDS(dataArr, classLabels, numIt=40):
    weakClassArr = []
    m = shape(dataArr)[0]
    D = mat(ones((m, 1)) / m)  # init D to all equal
    aggClassEst = mat(zeros((m, 1)))  # 样本的估计累加值
    for i in range(numIt):
        bestStump, error, classEst = buildStump(dataArr, classLabels, D)  # build Stump
        print("D:", D.T)
        alpha = float(
            0.5 * log((1.0 - error) / max(error, 1e-16)))  # calc alpha, throw in max(error,eps) to account for error=0
        bestStump['alpha'] = alpha
        weakClassArr.append(bestStump)  # store Stump Params in Array
        print("classEst: ", classEst.T)  # 当前弱分类器的分类结果
        expon = multiply(-1 * alpha * mat(classLabels).T, classEst)  # exponent for D calc, getting messy
        D = multiply(D, exp(expon))  # Calc New D for next iteration 为下一次迭代更新样本权重D
        D = D / D.sum()
        # calc training error of all classifiers, if this is 0 quit for loop early (use break)
        # 错误率累加计算
        aggClassEst += alpha * classEst  # 记录每个数据点的类别估计累计值
        print("aggClassEst: ", aggClassEst.T)
        aggErrors = multiply(sign(aggClassEst) != mat(classLabels).T, ones((m, 1)))
        errorRate = aggErrors.sum() / m
        print("total error: ", errorRate)
        if errorRate == 0.0:
            break
    return weakClassArr, aggClassEst

AdaBoost算法的输入参数包括数据集、类别标签以及迭代次数numIt，其中numIt是在整个AdaBoost算法中唯一需要用户指定的参数。我们假定迭代次数设为9，如果算法在第三次迭代之后错误率为0，那么就会退出迭代过程，并得到一个由三个弱分类器组成的强分类器，因此，此时就不需要执行所有的9次迭代过程。

函数名称尾部的DS代表的就是单层决策树（decision stump），它是AdaBoost中最流行的弱分类器，当然并非唯一可用的弱分类器。上述函数确实是建立于单层决策树之上的，但是我们也可以很容易对此进行修改以引入其他基分类器。实际上，任意分类器都可以作为基分类器，本书前面讲到的任何一个算法都行。上述算法会输出一个单层决策树的数组，因此首先需要建立一个新的Python表(weakClassArr)来对其进行存储。然后，得到数据集中的数据点的数目m，并建立一个列向量\(D\)。

AdaBoost算法的核心在于for循环，该循环运行numIt次或者直到训练错误率为0为止。循环中的第一件事就是利用前面介绍的buildStump()函数建立一个单层决策树。该函数的输入为权重向量D，返回的则是利用D而得到的具有最小错误率的单层决策树，同时返回的还有最小的错误率以及估计的类别向量。

接下来，需要计算的则是\(\alpha\)值。该值会告诉总分类器本次单层决策树输出结果的权重。其中的语句max(error, 1e-16)用于确保在没有错误时不会发生除零溢出。而后，\(\alpha\)值加入到bestStump字典中，该字典又添加到列表中。该字典包括了分类所需要的所有信息。

向量\(D\)非常重要，它包含了每个数据点的权重。一开始，这些权重都赋予了相等的值。在后续的迭代中，AdaBoost算法会在增加错分数据的权重的同时，降低正确分类数据的权重(每迭代一次就新增一个弱分类器，确定此弱分类器的权重，迭代一次样本权重）。\(D\)是一个概率分布向量，因此其所有的元素之和为1.0。为了满足此要求，一开始的所有元素都会被初始化成\(\frac{1}{m}\)，即初始样本权重都是一样的。同时，程序还会建立另一个列向量aggClassEst，记录每个数据点的类别估计累计值，该值只是一个浮点数，为了得到二值分类结果还需要调用sign()函数。如果总错误率为0，则由break语句中止for循环。

五、应用：解决分类问题

一旦拥有了多个弱分类器以及其对应的\(\alpha\)值，进行测试就变得相当容易了。在adaBoostTrainDS()中，我们实际已经写完了大部分的代码。现在，需要做的就只是将弱分类器的训练过程从程序中抽出来，然后应用到某个具体的实例上去。每个弱分类器的结果以其对应的\(\alpha\)值作为权重。所有这些弱分类器的结果加权求和就得到了最后的结果。

adaboost_classad项目关键代码如下：

def adaClassify(datToClass, classifierArr):
    dataMatrix = mat(datToClass)  # do stuff similar to last aggClassEst in adaBoostTrainDS
    m = shape(dataMatrix)[0]
    aggClassEst = mat(zeros((m, 1)))
    for i in range(len(classifierArr)):
        classEst = stumpClassify(dataMatrix, classifierArr[i]['dim'], \
                                 classifierArr[i]['thresh'], \
                                 classifierArr[i]['ineq'])  # call stump classify
        aggClassEst += classifierArr[i]['alpha'] * classEst
        print(aggClassEst)
    return sign(aggClassEst)

上述的adaClassify()函数就是利用训练出的多个弱分类器进行分类的函数。该函数的输入是由一个或者多个待分类样例datToClass以及多个弱分类器组成的数组classifierArr。函数adaClassify()首先将datToClass转换成了一个NumPy矩阵，并且得到datToClass中的待分类样例的个数m。然后构建一个0列向量aggClassEst，这个列向量与adaBoostTrainDS()中的含义一样，即记录每个数据点的类别估计累计值。

接下来，遍历classifierArr中的所有弱分类器，并基于stumpClassify()对每个分类器得到一个类别的估计值。在前面构建单层决策树时，我们已经见过了stumpClassify()函数，在那里，我们在所有可能的树桩值上进行迭代来得到具有最小加权错误率的单层决策树。而这里我们只是简单地应用了单层决策树。输出的类别估计值乘上该单层决策树的alpha权重然后累加到aggClassEst上。最后，程序返回aggClassEst的符号，即如果aggClassEst大于0则返回+1，而如果小于0则返回-1，这一过程同样借助了sign函数。

我们也可以将数据集分为训练数据和测试数据进行实验，具体可以参考adaboost_horseColic这个项目。

---

• 参考：
  1. 《机器学习》 周志华著
  2. 《机器学习实战》 [美]Peter Harrington著，李锐、李鹏、曲亚东、王斌 译