adaboost是boosting方法多个版本号中最流行的一个版本号，它是通过构建多个弱分类器。通过各个分类器的结果加权之后得到分类结果的。这里构建多个分类器的过程也是有讲究的，通过关注之前构建的分类器错分的那些数据而获得新的分类器。

这种多个分类器在训练时非常easy得到收敛。

本文主要介绍了通过单层决策树构建弱分类器。同理，也能够用其它的分类算法构建弱分类器。

boost 算法系列的起源来自于PAC Learnability(PAC 可学习性)。这套理论主要研究的是什么时候一个问题是可被学习的，当然也会探讨针对可学习的问题的详细的学习算法。

同一时候 ,Valiant和 Kearns首次提出了 PAC学习模型中弱学习算法和强学习算法的等价性问题,即随意给定仅比随机推測略好的弱学习算法 ,能否够将其提升为强学习算法 ? 假设二者等价 ,那么仅仅需找到一个比随机推測略好的弱学习算法就能够将其提升为强学习算法 ,而不必寻找非常难获得的强学习算法。

PAC 定义了学习算法的强弱

  弱学习算法---识别错误率小于1/2(即准确率仅比随机推測略高的学习算法)

  强学习算法---识别准确率非常高并能在多项式时间内完毕的学习算法

在介绍Boost算法的时候先介绍一下boostrapping 和 bagging算法

1）bootstrapping方法的主要过程

　　主要步骤：

　　i)反复地从一个样本集合D中採样n个样本

　　ii)针对每次採样的子样本集，进行统计学习，获得如果H_i

　　iii)将若干个如果进行组合，形成终于的如果H_final

　　iv)将终于的如果用于详细的分类任务

　　2）bagging方法的主要过程 -----bagging能够有多种抽取方法

　　主要思路：

　　i)训练分类器

　　从总体样本集合中。抽样n^* < N个样本 针对抽样的集合训练分类器C_i

　　ii)分类器进行投票，终于的结果是分类器投票的优胜结果

　　可是，上述这两种方法。都仅仅是将分类器进行简单的组合。实际上，并没有发挥出分类器组合的威力来。

adaboost全称是adaptive boosting(自适应boosting)，首先，对训练数据中每个样本附上一个权重，这些权重构成向量D。一開始给这些权重初始化为同样的值。第一次训练时，权重同样。和原先的训练方法一样。训练结束后，依据训练的错误率。又一次分配权重，第一次分对的样本的权重会减少。分错的样本权重会增大，这样再对第二个分类器进行训练，每个分类器都相应一个alpha权重值，这里的alpha是对于分类器而言，前面的D是对于样本而言。最后训练出一系列的弱分类器，对每个分类器的结果乘以权重值alpha再求和，就是终于的分类结果。

自适应就体如今这里。通过对D的一次次的优化，最后的结果往往能够高速收敛。

这里错误率的定义例如以下：

错误率  =  未正确分类的样本数 /  总的样本数

alpha定义例如以下：

权重D的更新函数例如以下：

这里分为两种情况

1.该样本被正确分类：

2.该样本没有被正确分类：

这里的i代表的是第i个样本，t代表的是第t次训练。

完整的adaboost算法例如以下

# -*- coding: cp936 -*-
‘‘‘
Created on Nov 28, 2010
Adaboost is short for Adaptive Boosting
@author: Peter
‘‘‘
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

def loadDataSet(fileName):      #general function to parse tab -delimited floats
    numFeat = len(open(fileName).readline().split(‘\t‘)) #get number of fields 
    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

#特征：dimen，分类的阈值是 threshVal,分类相应的大小值是threshIneq
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
    
#构建一个简单的单层决策树，作为弱分类器
#D作为每个样本的权重，作为最后计算error的时候多项式乘积的作用
#三层循环
#第一层循环，对特征中的每个特征进行循环。选出单层决策树的划分特征
#对步长进行循环，选出阈值
#对大于。小于进行切换

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)))  #numSteps作为迭代这个单层决策树的步长
    minError = inf #init error sum, to +infinity
    for i in range(n):#loop over all dimensions
        rangeMin = dataMatrix[:,i].min(); rangeMax = dataMatrix[:,i].max();#第i个特征值的最大最小值
        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

#基于单层决策树的AdaBoost的训练过程
#numIt 循环次数，表示构造40个单层决策树
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.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)))  #这里还用到一个sign函数。主要是将概率能够映射到-1,1的类型
        errorRate = aggErrors.sum()/m
        print "total error: ",errorRate
        if errorRate == 0.0: break
    return weakClassArr,aggClassEst

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)

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