Adaboost提升算法是机器学习中很好用的两个算法之一，另一个是SVM支持向量机；机器学习面试中也会经常提问到Adaboost的一些原理；另外本文还介绍了一下非平衡分类问题的解决方案，这个问题在面试中也经常被提到，比如信用卡数据集中，失信的是少数，5：10000的情况下怎么准确分类？
一 引言
1 元算法（集成算法）：多个弱分类器的组合；弱分类器的准确率很低 50%接近随机了
这种组合可以是 不同算法 或 同一算法不同配置 或是 数据集的不同部分分配给不同分类器;
2 bagging：把原始数据集随机抽样成S个与原始数据集一样大新数据集(允许有重复值)，然后训练S个分类器，最后投票结果集成；
代表：随机森林
3 boosting：关注以后分类器错分的数据，而得到新的分类器；
代表：adaboost
bagging和boosting类似，都是抽样的方式构造多个数据集(特别适用于数据集有限的时候)，并且多个组合分类器的类型都相同，但bagging是串行的，下一个分类器在上一个分类器的基础上继续训练得到的，权重均等；而boosting关注的是错分的数据，错分的数据权重大；
二 adaboost(adaptive boost)自适应提升算法
原理：为每一个样本赋均等的权重(D = 1/n)，先用这个数据集训练第一个弱分类器，计算错误率，错误率是为了计算这个分类器最后投票的权重alpha，见公式：
；错分的样本权重提升
，对分的样本权重降低
; 然后用这个数据集训练第二个若分类器，迭代到弱分类器错误率为0或迭代指定个数的弱分类器停止；
直观如图，第一个分类器每个样本权重均等，最后根据错误率计算alpha=0.69;然后调整样本权重，错分的权重增加，得第二个分类器的alpha0.97；同理第三个分类器的alpha=0.90；最后投票，总的结果是= 0.69*D1 + 0.97*D2 + 0.90*D3
（1）弱分类器：本文采用是时单层分类器，又叫树桩分类器，是决策树最简单的一种；
def stumpClassify(dataMatrix,dimen,threshVal,threshIneq):#just classify the data 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 #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 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 = weightedError bestClasEst = predictedVals.copy() bestStump['dim'] = i bestStump['thresh'] = threshVal bestStump['ineq'] = inequal return bestStump,minError,bestClasEst 原理：遍历每个属性，以一定步长，枚举大于和小于：找一条错误率最小的与垂直坐标轴的直线分开样本点；
例如 ins= (a,b,c) ， 找到的若分类器是 a= 1 or b = 2 or c =3 这样的垂直坐标轴的直线；
（2）adaboost训练分类器的代码;
原理如上介绍，训练分类器就是为了得到若分类器的参数dim,thresh,ineq和alpha,前三个参数dim,thresh,ineq是弱分类器树桩分类器的参数，最后一个alpha是集合多弱分类器结果的权重；
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 'error',error #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.sum() print 'D',D #calc training error of all classifiers, if this is 0 quit for loop early (use break) aggClassEst += alpha*classEst 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
(3)测试adaboost代码：
根据弱i训练分类器得到的参数，使用设置参数的弱分类器对测试样本进行预测，最后结果通过alpha集成；
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)
三 病马数据集实例
datArr,labelArr = loadDataSet('HorseTraining2.txt')classifierArr = adaBoostTrainDS(datArr,labelArr,9)testArr,testLabelArr = loadDataSet('HorseTraining2.txt')prediciton = adaClassify(testArr,classifierArr)error = mat(ones((67,1)))error[prediciton != mat(testLabelArr ).T] .sum() 这个实例就是调用了上面adaboost的接口，值得注意的是，这个病马的数据集是我们在上一篇文章logistics算法时用到的，在logistics里错误率是0.3，因为这个数据集有很多缺失值，难预测；而adaboost的50个弱分类器的错误率只有0.21；
主意： 弱分类器的个数，太少易欠拟合，太多易过拟合，最好的是适当的个数；就像一张经典的图，横坐标是弱分类器的个数，训练样本的错误率越来越低，测试样本的错误率是对勾型，取拐点处个数最好了，既不过拟合也不欠拟合。
四 不平衡分类问题
不平衡问题是正例和负例的比例相差很大，比如信用卡账户是否欠账，5个正例，5000个负例；
1解决方案
1）预处理级：过采样和欠采样及混合采样；
抽样过程可以通过随机或制定的方式实现：
（1）过采样：复制正例样本，增加样本个数；或者增加和正例样本相似的样本；
（2）欠采样：删除距离边界较远负例样本，上例中为了平衡，需要删除4950个负例；
（3）混合过采样和欠采样
2）算法级：代价敏感；
举个例子说明是什么代价敏感分类器：
二分类器代价矩阵：
| 真实结果|预测结果 | +1 | -1 |
| +1 | -5 | 1 |
| -1 | 50 | 0 |
根据代价矩阵表，求出最后的总的代价，选择代价最小的类做为左后的预测结果。
2 AUC计算代码：
就不能把准确率自己作为不平衡问题的评价指标了，因为在不平衡分类中，100个样本，90正例，10负例；则粗暴的把100个全分为正类就可以达到很高的100%准确率。这显然不是我们想要的结果。召回率这时候也起到了作用，正类中分对了多少，90%。
AUC是最为理想的一个指标：(通过正例和负例pairs的排名计算)
def plotROC(predStrengths, classLabels): import matplotlib.pyplot as plt cur = (1.0,1.0) #cursor ySum = 0.0 #variable to calculate AUC numPosClas = sum(array(classLabels)==1.0) yStep = 1/float(numPosClas); xStep = 1/float(len(classLabels)-numPosClas) sortedIndicies = predStrengths.argsort()#get sorted index, it's reverse fig = plt.figure() fig.clf() ax = plt.subplot(111) #loop through all the values, drawing a line segment at each point for index in sortedIndicies.tolist()[0]: if classLabels[index] == 1.0: delX = 0; delY = yStep; else: delX = xStep; delY = 0; ySum += cur[1] #draw line from cur to (cur[0]-delX,cur[1]-delY) 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() print "the Area Under the Curve is: ",ySum*xStep
五 总结
优点：准确度较高，无参数调整；
缺点：对离散值敏感；
数据类型：数值和离散型；