利用AdaBoost元算法提高分类性能
元算法(meta-algorithm): 对其他算法进行组合决策。也叫集成方法(ensemble method)
一、基于数据集多重抽样的分类器
集成算法的方式：
- 不同算法的集成
- 同一算法在不同设置下的集成
- 数据集不同部分分配给不同分类器之后的集成
AdaBoost：一种boosting实现方式
优点： 泛化错误率低、易编码、可以应用在大部分分类器上、无参数调整缺点： 对离群点敏感bagging:基于数据随机重抽样的分类器构建方法
有放回地取样得到S个新数据集，将某个学习算法作用到每个数据集上就得到了S个分类器。当对新数据进行分类时，就可以应用这S个分类器进行分类。
boosting
- boosting是通过集中关注被已有分类器错分的那些数据来获得新的分类器。
- boosting分类的结果是基于所有分类器的加权求和得到的。
- AdaBoost是最流行的版本。
二、基于错误提升分类器的性能
AdaBoosting运行过程：
- 首次在训练数据上训练出一个弱分类器，并计算错误率；
- 在分类器的再次训练中，重新调整每个样本的权重D_i，分对的样本的权重将会降低，分错的样本的权重将会提高；
- 每个分类器都被分配一个权重值alpha_i = 0.5*ln(1/ε - 1) 其中ε = 错误分类的样本/总样本；
- 计算出alpha值之后，可以对权重向量D进行更新，以使得正确分类的样本的权重降低，错误分类的样本的权重升高；
- 正确分类的样本：D(t+1;i) = D(t;i)*e^-α / Sum(D);
- 错误分类的样本：D(t+1;i) = D(t;i)*e^α / Sum(D);
- 进入下一轮迭代，直到训练错误率为0或者弱分类器的数目达到用户指定值为止。
三、基于单层决策树构建弱分类器
from numpy import *import matplotlib.pyplot as pp%matplotlib inline
def loadSimpleData(): 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
datMat, classLabels = loadSimpleData()
x0 = []; y0 = []x1 = []; y1 = []for i in range(len(datMat)): if classLabels[i] > 0: x0.append(array(datMat)[i][0]) y0.append(array(datMat)[i][1]) else: x1.append(array(datMat)[i][0]) y1.append(array(datMat)[i][1])pp.scatter(x0,y0,color='r')pp.scatter(x1,y1,color='g')
找不到一条于坐标轴平行的直线来分类，这是单层决策树无法处理的问题。
# 通过阈值比较对数据进行分类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
# 在一个加权数据集中循环，找到具有最低错误率的单层决策树def buildStump(dataArr, classLabels, D): dataMatrix = mat(dataArr); labelMat = mat(classLabels).T m,n = shape(dataMatrix) numSteps = 10.0; bestStump = {}; bestClasEst = mat(zeros((m,1))) minError = 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']: threshVal = (rangeMin + float(j) * stepSize) predictedVals = stumpClassify(dataMatrix, i, threshVal, inequal) errArr = mat(ones((m,1))) errArr[predictedVals == labelMat] = 0 weightedError = D.T*errArr #print('split: dim %d, thresh %.2f, thresh inequal: %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 D = mat(ones((5,1))/5)
buildStump(datMat, classLabels, D)
({'dim': 0, 'ineq': 'lt', 'thresh': 1.3}, matrix([[ 0.2]]), array([[-1.], [ 1.], [-1.], [-1.], [ 1.]])) 四、完整AdaBoost算法的实现
- 利用buildStump()函数找到最佳的单层决策树
- 将最佳单层决策树加入到单层决策树数组
- 计算alpha
- 计算新的权重向量D
- 更新累计类别估计值
- 如果错误率等于0.0，则退出循环
# 基于单层决策树的AdaBoost训练过程def adaBoostTrainDS(dataArr, classLabels, numIt=40): weakClassArr = [] m = shape(dataArr)[0] D = mat (ones((m,1))/m) # 所有数据点Di之和为1 aggClassEst = mat(zeros((m,1))) for i in range(numIt): bestStump,error,classEst = buildStump(dataArr,classLabels,D) #print('D:',D.T) alpha = float(0.5*log((1.0-error)/max(error,1e-16))) bestStump['alpha'] = alpha weakClassArr.append(bestStump) #print('classEst: ',classEst.T) expon = multiply(-1*alpha*mat(classLabels).T,classEst) # 为下一次迭代计算D 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 return weakClassArr adaBoostTrainDS(datMat, classLabels, 9)
total error: 0.2 total error: 0.2 total error: 0.0 [{'alpha': 0.6931471805599453, 'dim': 0, 'ineq': 'lt', 'thresh': 1.3}, {'alpha': 0.9729550745276565, 'dim': 1, 'ineq': 'lt', 'thresh': 1.0}, {'alpha': 0.8958797346140273, 'dim': 0, 'ineq': 'lt', 'thresh': 0.90000000000000002}] 五、测试算法：基于AdaBoost的分类
# AdaBoost分类函数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)
datArr,labelArr = loadSimpleData()
classifierArr = adaBoostTrainDS(datArr, labelArr, 30)
total error: 0.2 total error: 0.2 total error: 0.0
adaClassify([0,0],classifierArr)
matrix([[-1.]])
六、在一个难数据集上应用AdaBoost
准备数据：确保类别标签是+1和-1
# 自适应数据加载函数def loadDataSet(fileName): numFeat = len(open(fileName).readline().split('\t')) #readline返回的是第一行 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 datArr, labelArr = loadDataSet('data/horseColicTraining2.txt') classifierArray = adaBoostTrainDS(datArr,labelArr,10)
total error: 0.284280936455 total error: 0.284280936455 total error: 0.247491638796 total error: 0.247491638796 total error: 0.254180602007 total error: 0.240802675585 total error: 0.240802675585 total error: 0.220735785953 total error: 0.247491638796 total error: 0.230769230769
for DS in classifierArray:print(DS)
{'dim': 9, 'thresh': 3.0, 'ineq': 'gt', 'alpha': 0.4616623792657674}{'dim': 17, 'thresh': 52.5, 'ineq': 'gt', 'alpha': 0.31248245042467104}{'dim': 3, 'thresh': 55.199999999999996, 'ineq': 'gt', 'alpha': 0.2868097320169577}{'dim': 18, 'thresh': 62.300000000000004, 'ineq': 'lt', 'alpha': 0.23297004638939514}{'dim': 10, 'thresh': 0.0, 'ineq': 'lt', 'alpha': 0.19803846151213736}{'dim': 5, 'thresh': 2.0, 'ineq': 'gt', 'alpha': 0.18847887349020642}{'dim': 12, 'thresh': 1.2, 'ineq': 'lt', 'alpha': 0.1522736899747682}{'dim': 7, 'thresh': 1.2, 'ineq': 'gt', 'alpha': 0.15510870821690495}{'dim': 5, 'thresh': 0.0, 'ineq': 'lt', 'alpha': 0.1353619735335938}{'dim': 4, 'thresh': 28.799999999999997, 'ineq': 'lt', 'alpha': 0.12521587326132094} testArr,testLabelArr = loadDataSet('data/horseColicTest2.txt') prediction10 = adaClassify(testArr,classifierArray)
errArr = mat(ones((67,1)))errRate = (errArr[prediction10 != mat(testLabelArr).T].sum())/(len(testLabelArr))errRate
0.23880597014925373
弱分类器的数目从1-10000，训练错误率将越来越低，但测试错误率下降到21%左右后就逐渐升高，因为出现了过拟合的现象。
七、非均衡分类问题---分类器的普遍问题
在大多数情况下不同类别额度分类代价并不相等
1. 正确率、召回率及ROC曲线
正确率和召回率
- 错误率掩盖了样例如何被分错的事实。
- 通过混淆矩阵(confusion matrix)计算正确率(precision, TP/(TP+FP))和召回率(recall, TP/(TP+FN))
- 我们很容易构造一个高正确率或高召回率的分类器，但很难保证两者同时成立
ROC曲线
可以通过调节分类器的阈值处理非均衡分类代价的方法。# ROC曲线的绘制及AUC计算函数def plotROC(predStrengths, classLabels): import matplotlib.pyplot as pp cur = (1.0,1.0) # 绘制光标点 ySum = 0.0 numPosClas = sum(array(classLabels)==1.0) # 通过数组过滤的方式计算正例的数目 yStep = 1/float(numPosClas) xStep = 1/float(len(classLabels)-numPosClas) sortedIndicies = predStrengths.argsort() # 获取排好序的索引 fig = pp.figure() fig.clf() ax = pp.subplot(111) for index in sortedIndicies.tolist()[0]: if classLabels[index] == 1.0: delX = 0 delY = yStep else: delX = xStep delY = 0 ySum += cur[1] 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--') pp.xlabel('False Positive Rate') pp.ylabel('True Positive Rate') pp.title('ROC curve for AdaBoost Horse Colic Detection System') ax.axis([0,1,0,1]) pp.show() print('the Area Under the Curve is: ',ySum*xStep) # 改动返回值def adaBoostTrainDS(dataArr, classLabels, numIt=40): weakClassArr = [] m = shape(dataArr)[0] D = mat (ones((m,1))/m) # 所有数据点Di之和为1 aggClassEst = mat(zeros((m,1))) for i in range(numIt): bestStump,error,classEst = buildStump(dataArr,classLabels,D) #print('D:',D.T) alpha = float(0.5*log((1.0-error)/max(error,1e-16))) bestStump['alpha'] = alpha weakClassArr.append(bestStump) #print('classEst: ',classEst.T) expon = multiply(-1*alpha*mat(classLabels).T,classEst) # 为下一次迭代计算D 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 return weakClassArr, aggClassEst datArr,labelArr = loadDataSet('data/horseColicTraining2.txt') classifierArray,aggClassEst = adaBoostTrainDS(datArr,labelArr,10)
plotROC(aggClassEst.T,labelArr)
the Area Under the Curve is: 0.8582969635063604
- 横轴是假阳率(FP/(FP+TN)),纵轴是真阳率(TP/(TP+FN))
- ROC曲线给出的是当阈值变化时假阳率和真阳率的变化情况
- 左下角↙的点对应的是将所有样例判为反例的情况，右上角↗的点对应的是将所有样例判为正例的情况
- 虚线给出的是随机猜测的结果曲线
- 在理想情况下，最佳的分类器应该尽可能地处于左上角↖，这就意味这分类器在假阳率很低的同时获得了很高的真阳率
- ROC曲线不仅可以比较分类器，还可以基于成本效益(cost-versus-benefit)分析来做出决策
- 对不同的ROC曲线进行比较的一个指标是曲线下的面积AUC(area unser the curve),AUC给出的是平均性能值，完美的AUC=1.0
2. 基于代价函数的分类器决策控制
除了调节分类器的阈值之外，还可以用代价敏感的学习(cost-sensitive learning)。
均衡代价的情况下： cost = TP*0+FN*1+FP*1+TN*0非均衡代价的情况下： cost = TP*(-5)+FN*1+FP*(50)+TN*0如何引入代价信息？
- AdaBoost可以基于代价函数来调整错误权重向量D
- 朴素贝叶斯中，可以选择具有最小期望代价而不是最大概率的类别作为最后结果
- SVM中，可以在代价函数中对不同的类别选择不同的参数C
3. 数据抽样方法
欠抽样(undersampling):删除样例
过抽样(oversampling):复制样例 一种平衡的做法就是正例过抽样，对反例欠抽样(如果正例过少，反例过多)