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

【参考书籍】机器学习实战（Machine Learning in Action）

AdaBoost，一种元算法（meta-algorithm）或者集成方法（ensemble method），是对其他算法进行组合的一种方式。有人认为AdaBoost是最好的监督学习的方法。使用集成算法时，可是不同算法的集成，也可是同一算法在不同设置下的集成，还可是数据集不同部分分配不同分类器之后的集成。

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

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

在S个数据集建好后，将某个机器学习算法分别作用于某个数据集就得到S个分类器。对新数据分类时，可应用这S个分类器进行分类。选择分类器投票结果中最多的类别作为最后的分类结果。一种更先进的bagging方法，随机森林（random forest）

Boosting与bagging类似，都使用多个分类器。但Boosting中，不同分类器是通过串行训练得到的，每个新分类器都根据已训练出的分类器的性能进行训练。Boosting是通过集中关注被已有分类器错分的那些数据获得新的分类器。Boosting分类结果基于所有分类器的加权求和结果，而bagging中的分类器权重是相等的。

最流行的Boosting方法是AdaBoost，AdaBoot的大部分时间都用于训练上，分类器将多次在同一数据集上训练弱分类器。

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

ϵ=未正确分类的样本数目所有样本数目

alpha的计算公式如下：

α=12ln(1−ϵϵ)

得到alpha值后，对权重向量D进行更新。若某个样本被正确分类，则该样本的权重更改为：

D(t+1)i=Dtie−αSum(D)

若样本被错分，则该样本的权重更改为：

D(t+1)i=DtieαSum(D)

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

单层决策树（decision stump，也称为决策树桩），仅基于单个特征来做决策。

测试错误率在达到了一个最小值之后，又开始上升，这种现象称为过拟合（overfitting，也称过学习）。有文献称，对于表现好的数据集，AdaBoost的测试错误率就会达到一个稳定值，并不会随着分类器的增多而上升。

AdaBoost和SVM是监督机器学习中最强大的两种方法，两者拥有不少相似之处，可将弱分类器想象成SVM中的一个核函数，也可按照最大化某个最小间隔的方式重写AdaBoost算法，它们的不同在于其所定义的间隔计算方式有所不同，在高维空间下，这两者间的差异会更加明显。

非均衡分类问题

前述的所有分类问题中，都假设所有类别的分类代价都一样。但大多数情况下，不同类别的分类代价是不一样的。分类器性能度量方法，非均衡问题。

分类性能度量指标：正确率、召回率及ROC曲线。错误率：是在所有测试样例中错分的样例比例。这样度量错误掩盖了样例如何被错分的事实。混淆矩阵（confusion matrix）帮助人们了解分类中的错误。

表1　一个二类问题的混淆矩阵，其中的输出采用了不同的类别标签 预测结果+1-1真实结果+1真正例（TP，True Positive，真阳）伪反例（FN，False Negative，假阴）-1伪正例（FP，False Positive，假阳）真反例（TN，True Negative，真阴）

将一个正例判为正例，产生一个真正例（True Positive，TP，真阳）。将一个反例判为反例，产生一个真反例（True Negative，TN，真阴）。例外两种情况称为伪反例（False Negative，FN，假阴），和伪正例（False Positive，FP，假阳）。正确率（Precision）=TP/(TP+FP)，给出的是预测为正例的样本中真正正例的比例。召回率（Recall）=TP/(TP+FN)，给出的是预测为正例的真实正例占所有真实正例的比例。在召回率很大的分类器中，真正判错的正例的数目并不多。很难保证一个分类器同时具有高正确率和高召回率。

另一个度量分类中的非均衡性的工具是ROC曲线（ROC Curve），ROC代表接受者操作特征（receiver operating characteristic），在图1中的ROC曲线中，横轴为伪正例的比例（假阳率=FP/(TP+TN)），纵轴为真正例的比例（真阳率=TP/(TP+FN)）。ROC曲线不但用于比较分类器，还可基于成本效益分析（cost-versus-benefit）来做出决策。理想中的分类器应该尽可能处于左上角，在假阳率很低的同时获取很高的真阳率。

图1　利用10个单层决策树的AdaBoost马疝病检测系统的ROC曲线

对不同的ROC曲线进行比较的一个指标是曲线下的面积（Area Unser the Curve，AUC），它给出了分类器的平均性能值。为了画出ROC曲线，分类器必须提供每个样例被判为阳性或者隐形的可信程度值。朴素贝叶斯提供一个可能性，Logistic回归中输入到Sigmoid函数中的是一个数值。在AdaBoost和SVM中，都会计算出一个数值输入到sign()函数中。这些值可用于衡量给定分类器的预测强度。

基于代价函数的分类器决策控制，除调节分类器的阈值外，代价敏感的学习（cost-sensitive learning）也可用于处理非均衡分类。引入代价信息的方法，在AdaBoost中，可基于代价函数来调整错误权重向量D；在朴素贝叶斯中，可选择具有最小期望代价而不是最大概率的类别作为最后的结果；在SVM中，可在代价函数中对于不同的类别选择不同的参数C。这些做法会给较小类更多的权重，即在训练时，小类当中只允许更少的错误。

处理非均衡问题的数据抽样方法，就是对分类器的训练数据进行改造。可通过欠抽样（undersampling）和过抽样（oversampling）来实现。过抽样意味着复制样例，或者加入与已有样例相似的点（加入已有数据点的插值点，可能导致过拟合问题）。欠抽样意味着删除样例，此方法的缺点在于确定哪些样例需要进行剔除，在选择剔除的样例中可能携带了剩余样例中并不包含的有价值信息。一种解决方法，选择那些离决策边界较远的样例进行删除。

小结

多个分类器组合可能会进一步凸显单个分类器的不足，如过拟合问题。若多个分类器间差别显著，可能会缓解这一问题。差别可以是算法本身或者应用于算法上的数据的不同。

针对错误的调节能力是AdaBoost的长处，AdaBoost函数可以应用于任意能够处理加权数据的分类器。AdaBoost算法十分强大，它能够快速处理其他分类器难以处理的数据集。

使用的函数

函数功能arr.argsort()返回的是数组值从小到大的索引值mat1.tolist()将矩阵转换成列表，一般进行迭代循环时，需要使用for i in mat1.tolist()[0]:

程序代码

# coding=utf-8 from numpy import * def loadSimpData() : datMat = matrix([[1. , 2.1], [2. , 1.1], [1.3, 1. ], [1. , 1. ], [2. , 1. ]]) classLabels = [1.0, 1.0, -1.0, -1.0, 1.0] return datMat, classLabels # 是否有某个值小于或者大于测试的阈值 # threshVal：阈值（threshold） def stumpClassify(dataMatrix, dimen, threshVal, threshIneq) : retArray = ones((shape(dataMatrix)[0], 1)) if threshIneq == 'lt' : retArray[dataMatrix[:, dimen] <= threshVal] = -1.0 else : retArray[dataMatrix[:, dimen] > threshVal] = 1.0 return retArray # 在一个加权数据集中循环，并找到具有最低错误率的单层决策树 # 遍历stumpClassify()函数所有的可能输入值，找到数据集上最佳的单层决策树 # 这里的“最佳”是基于数据的权重向量D来定义的 def buildStump(dataArr, classLabels, D) : dataMatrix = mat(dataArr) labelMat = mat(classLabels).T m,n = shape(dataMatrix) # numSteps用于在特征的所有可能值上进行遍历 numSteps = 10.0 # bestStump用于存储给定权重向量D时所得到的最佳单层决策树的相关信息 bestStump = {} bestClassEst = mat(zeros((m,1))) # minError则在一开始就初始化为正无穷大，之后用于寻找可能的最小错误率 minError = inf # 第一层for循环在数据集的所有特征上遍历 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循环在大于和小于之间切换不等式 for inequal in ['lt', 'gt'] : threshVal = rangeMin + float(j) * stepSize # 在数据集和三个循环变量上调用stumpClassify()函数，其中threshVal与j相关 predictedVals = stumpClassify(dataMatrix, i, threshVal, inequal) # 构建errArr列向量，默认所有元素都为1，如果预测的结果和labelMat中标签值相等，则置为0 errArr = mat(ones((m, 1))) errArr[predictedVals == labelMat] = 0 # 将errArr向量和权重向量D的相应元素相乘并求和，得到数值weightedError，这就是AdaBoost和分类器交互的地方 # 即，计算加权错误率 weightedError = D.T*errArr print "split: dim %d, thresh %.2f, thresh ineqal: %s, the weighted error is %.3f" %\ (i, threshVal, inequal, weightedError) # 将当前的错误率与已有的最小错误率进行对比，如果当前的值较小，那么就在词典bestStump中保存该单层决策树 if weightedError < minError : minError = weightedError bestClassEst = predictedVals.copy() bestStump['dim'] = i bestStump['thresh'] = threshVal bestStump['ineq'] = inequal # 返回字典，错误率和类别估计值 return bestStump, minError, bestClassEst # 基于单层决策树的AdaBoost训练过程 # 输入参数：数据集、类别标签、迭代次数 def adaBoostTrainDS(dataArr, classLabels, numIt=40) : # 存储得到单层决策树 weakClassArr = [] # 数据点的数目 m = shape(dataArr)[0] # 列向量D，包含每个数据点的权重，开始时每个数据点的权重相等，后续迭代会增加错分数据的权重， # 降低正确分类数据的权重。D是一个概率分布向量，所有元素之和为1.0 D = mat(ones((m,1))/m) # 列向量aggClassEst，记录每个数据点的类别估计累计值 aggClassEst = mat(zeros((m,1))) for i in range(numIt) : # 具有最小错误率的单层决策树、最小的错误率，估计的类别向量 bestStump, error, classEst = buildStump(dataArr, classLabels, D) print "D: ", D.T # alpha告诉总分类器本次单层决策树输出结果的权重，其中max(error, 1e-16)确保没有错误时，不会发生除零溢出 alpha = float(0.5*log((1.0-error)/max(error, 1e-16))) bestStump['alpha'] = alpha weakClassArr.append(bestStump) print "classEst: ", classEst.T # 计算下一次迭代中的新的权重向量D expon = multiply(-1*alpha*mat(classLabels).T, classEst) D = multiply(D, exp(expon)) D = D/D.sum() # 错误率累加计算 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, "\n" if errorRate == 0.0 : break # 绘制ROC曲线时，需要返回aggClassEst return weakClassArr, aggClassEst # 基于AdaBoost的分类 # 一个或者多个待分类样例datToClass # classifierArr：多个弱分类器组成的数组 def adaClassify(datToClass, classifierArr) : dataMatrix = mat(datToClass) 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']) aggClassEst += classifierArr[i]['alpha'] * classEst print aggClassEst return sign(aggClassEst) # 自适应数据加载函数，该函数能够自动检测出特征的数目，假定最后一个特征是类别标签 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 # predStrengths: 一个Numpy数组或者一个行向量组成的矩阵，该参数代表的是分类器的预测强度， # 在分类器和训练函数将这些数值应用到sign()函数之前，它们就已经产生 # classLabels: 类别标签 def plotROC(predStrengths, classLabels) : import matplotlib.pyplot as plt # cur保留的是绘制光标的位置 cur = (1.0, 1.0) # ySum则用于计算AUC的值 ySum = 0.0 # 通过数组过滤方式计算正例的数目，并赋给numPosClas，接着在x轴和y轴的0.0到1.0区间上绘点 numPosClas = sum(array(classLabels)==1.0) # 在y轴上的步长 yStep = 1/float(numPosClas) # 在x轴上的步长 xStep = 1/float(len(classLabels) - numPosClas) # 获取排好序的索引sortedIndicies，这些索引从小到大排序。需要从<1, 1>开始绘，一直到<0,0> sortedIndicies = predStrengths.argsort() fig = plt.figure() fig.clf() ax = plt.subplot(111) # 在所有排序值上进行循环。这些值在一个NumPy数组或矩阵中进行排序， # python则需要一个表来进行迭代循环，因此需要调用tolist()方法 for index in sortedIndicies.tolist()[0] : # 每得到一个标签为1.0的类，则要沿着y轴的方向下降一个步长，即降低真阳率 if classLabels[index] == 1.0 : delX = 0; delY = yStep # 对于每个其他的标签，则是x轴方向上倒退一个步长（假阴率方向）， # 代码只关注1这个类别标签，采用1/0标签还是+1/-1标签就无所谓了 else : delX = xStep; delY = 0 # 所有高度的和ySum随着x轴的每次移动而渐次增加 ySum += cur[1] # 一旦决定了在x轴还是y轴方向上进行移动，就可在当前点和新点之间画出一条线段 ax.plot([cur[0], cur[0]-delX], [cur[1], cur[1]-delY], c='b') cur = (cur[0]-delX, cur[1]-delY) ax.plot([0,1], [0,1], 'b--') plt.xlabel('False Positive Rate') plt.ylabel('True Positive Rate') plt.title('ROC curve for AdaBoost Horse Colic Detection System') ax.axis([0,1,0,1]) plt.show() # 计算AUC需要对多个小矩形的面积进行累加，这些小矩形的宽度都是xStep， # 因此可对所有矩形的高度进行累加，然后再乘以xStep得到其总面积 print "the Area Under the Curve is: ", ySum*xStep

在命令行中执行：

>>> import ml.adaboost as adaboost >>> datMat, classLabels=adaboost.loadSimpData() # 构建单层决策树 >>> from numpy import * >>> D=mat(ones(5,1)/5) >>> adaboost.buildStump(datMat, classLabels, D) 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.400 split: dim 0, thresh 1.00, thresh ineqal: lt, the weighted error is 0.400 ...... split: dim 0, thresh 1.90, thresh ineqal: lt, the weighted error is 0.200 split: dim 0, thresh 1.90, thresh ineqal: gt, the weighted error is 0.400 ...... split: dim 1, thresh 2.10, thresh ineqal: lt, the weighted error is 0.600 split: dim 1, thresh 2.10, thresh ineqal: gt, the weighted error is 0.400 ({'dim': 0, 'ineq': 'lt', 'thresh': 1.3}, matrix([[ 0.2]]), array([[-1.], [ 1.], [-1.], [-1.], [ 1.]])) # 完整AdaBoost算法的实现 >>> reload(adaboost) <module 'ml.adaboost' from 'C:\Python27\ml\adaboost.py'> >>> classifierArray = adaboost.adaBoostTrainDS(datMat, classLabels, 9) D: [[ 0.2 0.2 0.2 0.2 0.2]] classEst: [[-1. 1. -1. -1. 1.]] aggClassEst: [[-0.69314718 0.69314718 -0.69314718 -0.69314718 0.69314718]] total error: 0.2 D: [[ 0.5 0.125 0.125 0.125 0.125]] classEst: [[ 1. 1. -1. -1. -1.]] aggClassEst: [[ 0.27980789 1.66610226 -1.66610226 -1.66610226 -0.27980789]] total error: 0.2 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 >>> reload(adaboost) <module 'ml.adaboost' from 'C:\Python27\ml\adaboost.py'> >>> datArr, labelArr = adaboost.loadSimpData() >>> classifierArr = adaboost.adaBoostTrainDS(datArr, labelArr, 30) >>> adaboost.adaClassify([[5,5],[0,0]],classifierArr) [[ 0.69314718] [-0.69314718]] [[ 1.66610226] [-1.66610226]] [[ 2.56198199] [-2.56198199]] matrix([[ 1.], [-1.]]) # 自适应数据加载 >>> reload(adaboost) >>> dataArr, labelArr = adaboost.loadDataSet('c:\python26\ml\\horseColicTraining2.txt') >>> classifierArray = adaboost.adaBoostTrainDS(dataArr, labelArr, 10) >>> testArr, testLabelArr = adaboost.loadDataSet('c:\python27\ml\\horseColicTest2.txt') >>> prediction10 = adaboost.adaClassify(testArr, classifierArray) # 获取被错误分类的元素个数 >>> errArr = mat(ones((67,1))) >>> errArr[prediction10!=mat(testLabelArr).T].sum() # 绘制ROC >>> reload(adaboost) >>> dataArr, labelArr = adaboost.loadDataSet('c:\python27\ml\\horseColicTraining2.txt') >>> classifierArray, aggClassEst = adaboost.adaBoostTrainDS(dataArr, labelArr, 10) >>> adaboost.plotROC(aggClassEst.T, labelArr) the Area Under the Curve is: 0.858296963506