第七章 利用AdaBoost元算法提高分类性能

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

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

集成方法(ensemble method)或者元算法(meta-algorithm)：将不同的分类器组合起来。使用集成方法时会有多种形式：可以是不同算法的集成，也可以是同一算法在不同设置下的集成，还可以是数据集不同部分分配给不同分类器之后的集成。

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

自举汇聚法(bootstrap aggregating)，也即bagging方法：从原始数据集选择S次后得到S个新数据集的一种计数。S个新数据集和原始数据集的大小相等，每个数据集都是通过原始数据集中随机选择一个样本来进行替换而得到的。在S个数据集建好之后，将某个学习算法分别作用于每个数据集就得到了S个分类器。当我们要对新数据进行分类时，就可以应用这S个分类器进行分类。选择分类器投票结果中最多的类别作为最后的分类结果。

boosting

boosting是通过集中关注被已有分类器错分的那些数据来获得新的分类器。boosting分类的结果是基于所有分类器的加权求和结果的，分类器每个权重代表的是其对应分类器在上一轮迭代中的成功度。而bagging中的分类器权重是相等的。这里关注boosting最流行的版本AdaBoost。

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

AdaBoost(adaptive boosting)：训练数据中的每个样本，并赋予其一个权重，这些权重构成了向量D。一开始，这些权重都初始化成相等值。首先在训练数据上训练出一个弱分类器并计算该分类器的错误率，然后在同一数据集上再次训练弱分类器。重新调整每个样本的权重，第一次分对的样本的权重将会降低，分错的样本的权重将会提高。AdaBoost为每个分类器都分配了一个权重值alpha，其基于每个弱分类器的错误率进行计算的。错误率的定义：

alpha的计算公式：

AdaBoost算法的流程图

对权重向量D更新，如果某个样本被正确分类，那么该样本的权重改为：

如果被错分，样本权重为：

计算出D后，AdaBoost继续迭代重复训练调整权重，直到训练错误率为0或者弱分类器的数据达到用户指定值为止。

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

单层决策树(decision stump)：基于单个特征来做决策。只有一次分裂过程。通过使用多颗单层决策树，就可以构建出一个能够对该数据集完全正确分类的分类器。

伪代码：

将最小错误率minError设为正无穷

对数据集中的每一个特征

对每个步长

对每个不等号

建立一颗单层决策树并利用加权数据集对它进行测试

如果错误率低于minError，则将当前单层决策树设为最佳单层决策树

返回最佳单层决策树

coding:

[python] view plain copy

1. #!/usr/bin/env python  
2. # coding=utf-8  
3. from numpy import *  
4. import matplotlib.pyplot as plt  
5.   
6. def loadSimpData():  
7.     datMat = matrix([[1., 2.1],  
8.                      [2. , 1.1],  
9.                      [1.3, 1. ],  
10.                      [1. , 1. ],  
11.                      [2. , 1. ]])  
12.     classLabels = [1.0, 1.0, -1.0, -1.0, 1.0]  
13.     return datMat, classLabels  
14.   
15. #===========单层决策树生成函数=======================  
16. def stumpClassify(dataMatrix, dimen, threshVal, threshIneq):  
17.     retArray = ones((shape(dataMatrix)[0],1))  
18.     if threshIneq == "lt":   
19.         retArray[dataMatrix[:,dimen] <= threshVal] = -1.0       #对dimen维的所有值小于等于阈值  
20.     else:  
21.         retArray[dataMatrix[:,dimen] > threshVal]  = -1.0  
22.     return retArray  
23.   
24. def buildStump(dataArr, classLabels, D):  
25.     dataMatrix = mat(dataArr)  
26.     labelMat     = mat(classLabels).T  
27.     m, n         = shape(dataMatrix)  
28.     numSteps     = 10.0  
29.     bestStump    = {}  
30.     bestClassEst = mat(zeros((m,1)))  
31.     minError     = inf  
32.     for i in range(n):                                  #对每个特征来说  
33.         rangeMin = dataMatrix[:,i].min()  
34.         rangeMax = dataMatrix[:,i].max()  
35.         stepSize = (rangeMax - rangeMin)/numSteps       #得到每个特征的步长大小  
36.         for j in range(-1, int(numSteps)+1):  
37.             for inequal in ["lt","gt"]:                 #大于还是小于  
38.                 threshVal = rangeMin + float(j)*stepSize  
39.                 predictedVals = stumpClassify(dataMatrix, i, threshVal, inequal)#对于大于和小于两种情况都预测数据的类别  
40.                 errArr        = mat(ones((m,1)))  
41.                 errArr[predictedVals == labelMat] = 0               #预测对了，误差为0,否则为1  
42.                 weightedError                     = D.T*errArr      #计算权重误差  
43.                 print "split: dim %d, thresh %.2f, thresh inequal: %s, the weighted error is %.3f "%(i, threshVal, inequal, weightedError)  
44.                 if weightedError < minError:  
45.                     minError = weightedError  
46.                     bestClassEst = predictedVals.copy()  
47.                     bestStump["dim"] = i  
48.                     bestStump["thresh"] = threshVal  
49.                     bestStump["ineq"]   = inequal  
50.     return bestStump, minError, bestClassEst  
51.   
52.   
53. datMat, classLabels = loadSimpData()  
54. D = mat(ones((5,1))/5)  
55. print buildStump(datMat, classLabels, D)  

效果：

buildStump函数得到构建AdaBoost算法需要所有信息，字典、错误率、类别估计值等。

7.4 完整AdaBoost算法的实现

伪代码

对每次迭代：

利用buildStump()函数找到最佳的单层决策树

将最佳单层决策树加入到单层决策树数组

计算alpha

计算新的权重向量D

更新累计类别估计值

如果错误率等于0.0，则退出循环

coding

[python] view plain copy

1. #=======基于单层决策树的AdaBoost训练过程=====================  
2. def adaBoostTrainDS(dataArr, classLabels, numIt = 40):              #DS:decision stump单层决策树，  
3.     weakClassArr = []  
4.     m = shape(dataArr)[0]  
5.     D = mat(ones((m,1))/m)                                          #初始权重  
6.     aggClassEst = mat(zeros((m,1)))                                 #记录每个数据点的类别估计累计值  
7.     for i in range(numIt):  
8.         bestStump, error, classEst = buildStump(dataArr, classLabels, D)  
9.         print "D:",D.T  
10.         alpha = float(0.5*log((1.0-error)/max(error, 1e-16)))  
11.         bestStump["alpha"] = alpha  
12.     weakClassArr.append(bestStump)  
13.         print "classEst: ", classEst.T  
14.         expon = multiply(-1*alpha*mat(classLabels).T, classEst)         #multiply矩阵点乘，若是矩阵和向量，则矩阵每行与向量点乘得到新矩阵  
15.         D     = multiply(D, exp(expon))  
16.         D     = D/D.sum()                                           #得到新的D，用于下次计算  
17.         aggClassEst +=alpha*classEst  
18.         print "aggClassEst: ",aggClassEst.T  
19.         aggErrors = multiply(sign(aggClassEst)!=mat(classLabels).T, ones((m,1)))#sign(aggClassEst)即为预测的类别，等于真实值  
20.         errorRate = aggErrors.sum()/m                                           #预测的和真实的全相等，aggErrors才会全为0,errorRate才会全为0  
21.         print "total error: ",errorRate, "\n"  
22.         if errorRate == 0.0:  
23.             break  
24.     return weakClassArr  
25.   
26. classifierArray = adaBoostTrainDS(datMat, classLabels,9)  
27. print classifierArray  

效果

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

通过上述AdaBoost算法训练得到多个弱分类器以及对应的alpha值，就可以进行测试。

coding

[python] view plain copy

1. #========AdaBoost分类函数====================================  
2. def adaClassify(datToClass, classifierArr):#classifierArr包含了每次得到的弱分类器分类所需要的信息  
3.     dataMatrix = mat(datToClass)  
4.     m = shape(dataMatrix)[0]  
5.     aggClassEst = mat(zeros((m,1)))  
6.     for i in range(len(classifierArr)):  
7.         classEst = stumpClassify(dataMatrix, classifierArr[i]["dim"], classifierArr[i]["thresh"], classifierArr[i]["ineq"])          #得到每个弱分类器分类的结果  
8.         aggClassEst += classifierArr[i]["alpha"]*classEst   #每个弱分类器的权值乘以分类的正负得到估计值  
9.         print aggClassEst  
10.     return sign(aggClassEst)  
11.   
12. datArr, labelArr = loadSimpData()  
13. classifierArr    = adaBoostTrainDS(datArr, labelArr, 30)  
14.   
15. print adaClassify([0,0],classifierArr)  
16. print ""  
17. print adaClassify([[5,5],[0,0]],classifierArr)  

效果

Figure 7-5：测试分类结果

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

coding

[python] view plain copy

1. #==========自适应数据加载函数================================  
2. def loadDataSet(fileName):  
3.     numFeat  = len(open(fileName).readline().split("\t"))  
4.     dataMat  = []  
5.     labelMat = []  
6.     fr = open(fileName)  
7.     for line in fr.readlines():  
8.         lineArr = []  
9.         curLine = line.strip().split("\t")  
10.         for i in range(numFeat-1):  
11.             lineArr.append(float(curLine[i]))  
12.         dataMat.append(lineArr)  
13.         labelMat.append(float(curLine[-1]))  
14.     return dataMat, labelMat  
15.   
16. datArr, labelArr = loadDataSet("horseColicTraining2.txt")  
17. classifierArray  = adaBoostTrainDS(datArr, labelArr, 10)  
18.   
19. #print classifierArray  
20. testArr, testLabelArr = loadDataSet("horseColicTest2.txt")  
21. prediction10 = adaClassify(testArr, classifierArray)  
22. errArr = mat(ones((67,1)))  
23. print errArr[prediction10!=mat(testLabelArr).T].sum()  

效果

上表中显示测试错误率在达到了一个最小值之后又开始上升了。即过拟合。对于表现好的数据集，AdaBoost的测试错误率就会达到一个稳定值，并不会随着分类器的增多而上升。

7.7 非均衡分类问题

其他分类性能度量指标：正确率、召回率及ROC曲线

混淆矩阵（confusion matrix）可以帮助人们更好地了解分类中的错误。如果混淆矩阵为对角阵，那么分类器是完美的。

真正例（True Positive, TP, 真阳）：将正例分为正例。

真反例（True Negative, TN,真阴）：将反例分为反例。

伪反例（False Negative, FN, 假阴）：正分为反。

伪正例（False Positive, FP, 假阳）：反分为正。

正确率（Precision） = TP(TP+FP)，召回率（Recall）=TP/（TP+FN）。

另一个用于度量分类中的非均衡性的工具是ROC曲线（ROC curve）。

ROC曲线横轴是伪正例的比例（假阳率=FP/（FP+TN）），纵轴是真正例的比例（真阳率=TP/TP+FN）。ROC曲线给出的是当阈值变化时假阳率和真阳率的变化情况。左下角的点所对应的是将所有样例判为反例的情况。 而右上角的点对应的则是将所有样例判为正例的情况。虚线给出的是随机猜测的结果曲线。

在理想的情况下，最佳的分类器应该尽可能地处手左上角，这就意味着分类器在假阳率很低的同时获得了很高的真阳率。

对不同的ROC曲线进行比较的一个指标是曲线下的面积（Area Unser the Curve, AUC）。AUC给出的是分类器的平均性能值。

coding:

[python] view plain copy

1. #=================ROC曲线的绘制及AUC计算函数=================  
2. def plotROC(predStrengths, classLabels):  
3.     cur = (1.0,1.0)   
4.     ySum = 0.0  
5.     numPosClas = sum(array(classLabels)==1.0)  
6.     yStep = 1/float(numPosClas)  
7.     xStep = 1/float(len(classLabels) - numPosClas)  
8.     sortedIndicies = predStrengths.argsort()  
9.     fig = plt.figure()  
10.     fig.clf()  
11.     ax = plt.subplot(111)  
12.     for index in sortedIndicies.tolist()[0]:  
13.         if classLabels[index] == 1.0:  
14.             delX = 0  
15.             delY = yStep  
16.         else:  
17.             delX = xStep  
18.             delY = 0  
19.             ySum += cur[1]  
20.         ax.plot([cur[0],cur[0]-delX],[cur[1],cur[1]-delY],c="b")  
21.         cur = (cur[0]-delX, cur[1]-delY)  
22.     ax.plot([0,1],[0,1],"b--")  
23.     plt.xlabel("False Positive Rate")  
24.     plt.ylabel("True Positive Rate")  
25.     plt.title("ROC curve for AdaBoost Horse Colic Detection System")  
26.     ax.axis([0,1,0,1])  
27.     plt.show()  
28.     print "the Area Under the Curve is: ",ySum*xStep  
29.      
30. datArr, labelArr = loadDataSet("horseColicTraining2.txt")  
31. classifierArray, aggClassEst = adaBoostTrainDS(datArr, labelArr,10)  
32. print plotROC(aggClassEst.T, labelArr)  

效果：

Figure 7-7: ROC曲线

Figure 7-8: AUC的值

基于代价函数的分类器决策控制

除了调节分类器的阈值之外，还可以使用代价敏感的学习（cost-sensitive learning）。在分类算法中，有很多方法用来引入代价信息。在AdaBoost中，可以基于代价函数来调整错误权重向量D。在朴素贝叶斯中，可以选择具有最小期望代价而不是最大概率的类别作为最后的结果。在SVM中，可以在代价函数中对于不同的类别选择不同的参数C。

处理非均衡问题的数据抽样方法

另外可以通过欠抽样（undersampling）或者过抽样（oversampling）来实现。要对正例类别进行过抽样，我们可以复制已有样例或者加人与已有样例相似的点。一种方法是加人已有数据点的插值点,但是这种做法可能会导致过拟合的问题。

7.8 小结

集成方法通过组合多个分类器的分类结果, 获得了比简单的单分类器更好的分类结果。多个分类器组合可能会进一步凸显出单分类器的不足,比如过拟合问题。 如果分类器之间差别显著，那么多个分类器组合就可能会缓解这一问题。
这一章的两种集成方法bagging和boosting,前者是通过随机抽样的替换方法，得到了与原始数据集规模一样的数据集。而后者在数据集上顺序用了多个不同的分类器。另外还有随机森林。
boosting中最流行的为AdaBoosting算法，其以弱学习器作为基fenleqii，并且输入数据，使其通过权重向量进行加权。迭代中分错的数据的权重会增大，这种针对错误的调节能力正是AdaBoost的长处。
AdaBoost分类器主要由单层决策树作为弱学习来构建。AdaBoost可以应用于任意分类器，只要该分类器能够处理加权数据即可。