AdaBoost（自適應boosting，adaptive boosting）算法

算法優缺點：

• 優點：泛化錯誤率低，易編碼，可用在絕大部分分類器上，無參數調整
• 缺點：對離群點敏感
• 適用數據類型：數值型和標稱型
</ul>

元算法（meta algorithm）

在分類問題中，我們可能不會只想用一個分類器，我們會考慮將分類器組合起來使用，這種方法稱為集成方法（ensemble method）或元算法。元算法有多種形式，既可以是不同算法集成也可以是一種算法不同設置的集成。

兩種集成方式（bagging & boosting）

• bagging方法也稱自舉匯聚法（bootstrap aggregating）。思路相當于是從數據集中隨機抽樣得到新的數據集，然后用新的數據集進行訓練，最后的結果是新的數據集形成的分類器中的最多的類 別。如從1000個樣本組成的數據集中進行有放回的抽樣5000次，得到5個新的訓練集，將算法分別用到這五個訓練集上從而得到五個分類器。
• boosting則是一種通過串行訓練得到結果的方法，在bagging中每個分類器的權重一樣，而boosting中分類器的權重則與上一輪的成功度有關。
</ul>

AdaBoost

是一種用的最多的boosting，想法就是下一次的迭代中，將上一次成功的樣本的權重降低，失敗的權重升高。權重變化方式：

alpha（分類器權重）的變化：

數據權重變化：

正確分類的話：

錯誤分類的話


實現思路：

AdaBoost算法實現的是將弱分類器提升成為強分類器，所以這里我們首先要有一個弱分類器，代碼中使用的是單層決策樹，這也是使用的最多的弱分類器，然后我們就可以根據弱分類器構造出強分類器

函數：

stumpClassify(dataMatrix,dimen,threshVal,threshIneq)

單層決策樹的分類器，根據輸入的值與閥值進行比較得到輸出結果，因為是單層決策樹，所以只能比較數據一個dimen的值

buildStump(dataArr,classLabels,D)

構造單層決策樹，這部分的構造的思路和前面的決策樹是一樣的，只是這里的評價體系不是熵而是加權的錯誤率，這里的加權是通過數據的權重D來實現的，每一次build權重都會因上一次分類結果不同而不同。返回的單層決策樹的相關信息存在字典結構中方便接下來的使用

adaBoostTrainDS(dataArr,classLabels,numIt=40)

AdaBoost的訓練函數，用來將一堆的單層決策樹組合起來形成結果。通過不斷調整alpha和D來使得錯誤率不斷趨近0，甚至最終達到0

adaClassify(datToClass,classifierArr)

分類函數，datToClass是要分類的數據，根據生成的一堆單層決策樹的分類結果，加權得到最終結果。

#coding=utf-8
from numpy import *
def loadSimpleData():
    dataMat = 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 dataMat, classLabels

def stumpClassify(dataMatrix,dimen,threshVal,threshIneq):
    retArry = ones((shape(dataMatrix)[0],1))
    if threshIneq == 'lt':
        retArry[dataMatrix[:,dimen] <= threshVal] = -1.0
    else:
        retArry[dataMatrix[:,dimen] > threshVal] = -1.0
    return retArry
D是權重向量
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 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


def adaBoostTrainDS(dataArr,classLabels,numIt=40):
    weakClassArr = []
    m =shape(dataArr)[0]
    D = mat(ones((m,1))/m)#初始化所有樣本的權值一樣
    aggClassEst = mat(zeros((m,1)))#每個數據點的估計值
    for i in range(numIt):
        bestStump,error,classEst = buildStump(dataArr,classLabels,D)

    #計算alpha，max(error,1e-16)保證沒有錯誤的時候不出現除零溢出
    #alpha表示的是這個分類器的權重，錯誤率越低分類器權重越高
    alpha = float(0.5*log((1.0-error)/max(error,1e-16)))
    bestStump['alpha'] = alpha  
    weakClassArr.append(bestStump)
    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)))
    errorRate = aggErrors.sum()/m
    print "total error: ",errorRate
    if errorRate == 0.0: 
        break
return weakClassArr


dataToClass 表示要分類的點或點集
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 main():
    dataMat,classLabels = loadSimpleData()
    D = mat(ones((5,1))/5)
    classifierArr = adaBoostTrainDS(dataMat,classLabels,30)
    t = adaClassify([0,0],classifierArr)
    print t
if name == 'main':
    main()</pre>  來源： AdaBoost的博客