一、AdaBoost算法原理

上一偏博客總結(jié)過，集成學(xué)習(xí)基于弱學(xué)習(xí)器之間是否依賴分為Boosting和Bagging兩類, Adaboost就是Boosting中的典型代表。 其核心思想是針對同一個訓(xùn)練集訓(xùn)練不同的學(xué)習(xí)器，然后將這些弱學(xué)習(xí)器集合起來，構(gòu)造一個更強的最終學(xué)習(xí)算法

AdaBoost是英文"Adaptive Boosting"（自適應(yīng)增強）的縮寫，它的自適應(yīng)在于： 基于每一個分類器的誤差率，來更新所有樣本的權(quán)重，前一個分類器被錯誤分類的樣本的權(quán)值會增大，而正確分類的樣本的權(quán)值會減小，并再次用來訓(xùn)練下一個基本分類器。

Adaboost算法分為三步：
（1）初始化權(quán)值：每一個訓(xùn)練樣本最開始權(quán)重相同
（2）訓(xùn)練弱分類器：先訓(xùn)練一個弱分類器，計算其誤差率（被錯誤分類的樣本權(quán)值和），基于誤差率降低分類正確的樣本權(quán)重，提升分類錯誤的樣本權(quán)重。權(quán)值更新過的樣本集被用于訓(xùn)練下一個分類器，整個訓(xùn)練過程如此迭代地進行下去。
（3）組合分類器：各個弱分類器的訓(xùn)練過程結(jié)束后，依據(jù)各分類器的誤差率計算各自在最終分類器中的權(quán)重，誤差率越大，權(quán)重越低，就是你說的越對，那么就越聽你的，你滿嘴跑火車，那就沒人聽你的了

Adaboost有幾個要注意的指標：
① 初始權(quán)重：1/訓(xùn)練樣本數(shù)D
② 誤差率： 被分類錯誤的樣本的權(quán)重和
③ 弱學(xué)習(xí)器的權(quán)重：

③ 更新訓(xùn)練樣本權(quán)重：


④最終的分類器

二、Adaboost的python實現(xiàn)

① 構(gòu)造訓(xùn)練樣本

            
              import numpy as np
import matplotlib.pyplot as plt

# 輸出樣本和類別
def loadsimple():
    datMat = np.matrix([[1., 2.1],
                        [1.5, 1.6],
                        [1.3, 1.],
                        [1., 1.],
                        [2., 1.]])
    classlablels = [1.0, 1.0, -1.0, -1.0, 1.0]
    return datMat, classlablels

            
          

② 訓(xùn)練弱分類器（簡單二分類決策樹）

            
              # 輸出按某特征的某個閾值分類后的類別向量
def stumpClassify(dataMatrix, dimen, threshVal, threshIneq):
    retArray = np.ones((np.shape(dataMatrix)[0], 1))
    if threshIneq == 'lt':
        retArray[dataMatrix[:, dimen] <=threshVal] = -1.0
    else:                                                # threshIneq == 'gt'大于為-1
        retArray[dataMatrix[:, dimen] > threshVal] = -1.0
    return retArray

# 找到使誤差率最小的特征及屬性閾值，就是一棵決策樹，只是判斷特征選擇方法不是根據(jù)基尼指數(shù)和信息增益，而是誤差率
def buildStump(dataArr, classLabels, D):
    dataMatrix = np.mat(dataArr)
    labelMat = np.mat(classLabels).T
    m, n = np.shape(dataMatrix)
    numsteps = 10.0
    bestClassEst = np.mat(np.zeros((m, 1)))
    minError = float('inf')
    bestStump = {}
    for i in range(n):
        rangMin = dataMatrix[:, i].min()
        rangMax = dataMatrix[:, i].max()
        stepSize = (rangMax-rangMin)/numsteps
        for j in range(-1, int(numsteps)+1):
            for inequal in ['lt', 'gt']:
                threshVal = (rangMin + float(j)*stepSize)
                predictedVals = stumpClassify(dataMatrix, i, threshVal, inequal)
                errArr = np.mat(np.ones((m, 1)))
                errArr[predictedVals == labelMat] = 0
                weightedError = D.T * errArr  # 點乘法，為一個值
                if weightedError < minError:
                    minError = weightedError
                    bestClassEst = predictedVals.copy()
                    bestStump['dim'] = i  # 最佳分類特征
                    bestStump['thresh'] = threshVal  # 最佳分類閾值
                    bestStump['ineq'] = inequal # 最佳分類標準，是大于還是小于
    return bestStump, minError, bestClassEst

            
          

③ 構(gòu)造Adaboost分類器

            
               # 構(gòu)造Adaboost分類器
def adaBoostTrainDS(dataArr, classlabels, numIt = 40):
    weakClassArr = []
    m = np.shape(dataArr)[0]  # 樣本個數(shù)
    D = np.mat(np.ones((m, 1))/m)  # 初始訓(xùn)練樣本權(quán)重
    aggClassEst = np.mat(np.zeros((m, 1)))
    for i in range(numIt):
        bestStump, error, classEst = buildStump(dataArr, classlabels, D)
        # 計算分類器的權(quán)重
        alpha = float(0.5 * np.log((1.0 - error)/max(error, 1e-16))) #計算弱學(xué)習(xí)算法權(quán)重alpha,使error不等于0,因為分母不能為0
        bestStump['alpha'] = alpha  # 一個弱分類器是一個詞典，包含了分類的特征、閾值，分類結(jié)果，及弱分類器的權(quán)重
        weakClassArr.append(bestStump)
        # 重新計算每個樣本的權(quán)重D
        expon = np.multiply(-1 * alpha * np.mat(classlabels).T, classEst) # #數(shù)組對應(yīng)元素位置相乘
        D = np.multiply(D, np.exp(expon))
        D = D/D.sum()
        # 計算AdaBoost誤差，當(dāng)誤差為0的時候，退出循環(huán)
        aggClassEst += alpha * classEst
        aggErrors = np.multiply(np.sign(aggClassEst) != np.mat(classEst).T, np.ones((m, 1)))
        errorRate = aggErrors.sum()/m
        print('totol error:', errorRate)
        if errorRate == 0.0:
            break
    return weakClassArr, aggClassEst

            
          

④使用生成的Adaboost分類器進行分類

            
              # 使用Adaboost分類器進行分類
def adaClassify(datatoClass, classifierArr):
    dataMatrix = np.mat(datatoClass)
    m = np.shape(dataMatrix)[0]
    aggClassEst = np.mat(np.zeros((m, 1)))
    for i in range(len(classifierArr)):
        # 迭代每一個弱分類器，并將每一個弱分類器的分類結(jié)果與權(quán)重相乘法，再求和，結(jié)果的符號就是最終分類結(jié)果
        classEst = stumpClassify(dataMatrix, classifierArr[i]['dim'],
                                 classifierArr[i]['thresh'], classifierArr[i]['ineq'])
        aggClassEst += classifierArr[i]['alpha']*classEst
    return np.sign(aggClassEst)

            
          

⑤ 主函數(shù)調(diào)用

            
              if __name__ == '__main__':
    dataArr, classlabels = loadsimple()
    weakClassArr,aggClassEst = adaBoostTrainDS(dataArr, classlabels)
    print(weakClassArr)
    print(aggClassEst)
    print(adaClassify([[0, 0, 6, 10],[1, 5, 6,-3]], weakClassArr))

            
          

Adaboost分類器如下：

所有代碼如下：

            
              import numpy as np
import matplotlib.pyplot as plt
    
# 輸出樣本和類別
def loadsimple():
    datMat = np.matrix([[1., 2.1],
                        [1.5, 1.6],
                        [1.3, 1.],
                        [1., 1.],
                        [2., 1.]])
    classlablels = [1.0, 1.0, -1.0, -1.0, 1.0]
    return datMat, classlablels    

# 輸出按某特征的某個閾值分類后的類別向量
def stumpClassify(dataMatrix, dimen, threshVal, threshIneq):
    retArray = np.ones((np.shape(dataMatrix)[0], 1))
    if threshIneq == 'lt':
        retArray[dataMatrix[:, dimen] <=threshVal] = -1.0
    else:                                                # threshIneq == 'gt'大于為-1
        retArray[dataMatrix[:, dimen] > threshVal] = -1.0
    return retArray    

# 找到使誤差率最小的特征及屬性閾值，就是一棵決策樹，只是判斷特征選擇方法不是根據(jù)基尼指數(shù)和信息增益，而是誤差率
def buildStump(dataArr, classLabels, D):
    dataMatrix = np.mat(dataArr)
    labelMat = np.mat(classLabels).T
    m, n = np.shape(dataMatrix)
    numsteps = 10.0
    bestClassEst = np.mat(np.zeros((m, 1)))
    minError = float('inf')
    bestStump = {}
    for i in range(n):
        rangMin = dataMatrix[:, i].min()
        rangMax = dataMatrix[:, i].max()
        stepSize = (rangMax-rangMin)/numsteps
        for j in range(-1, int(numsteps)+1):
            for inequal in ['lt', 'gt']:
                threshVal = (rangMin + float(j)*stepSize)
                predictedVals = stumpClassify(dataMatrix, i, threshVal, inequal)
                errArr = np.mat(np.ones((m, 1)))
                errArr[predictedVals == labelMat] = 0
                weightedError = D.T * errArr  # 點乘法，為一個值
                if weightedError < minError:
                    minError = weightedError
                    bestClassEst = predictedVals.copy()
                    bestStump['dim'] = i  # 最佳分類特征
                    bestStump['thresh'] = threshVal  # 最佳分類閾值
                    bestStump['ineq'] = inequal # 最佳分類標準，是大于還是小于
    return bestStump, minError, bestClassEst

# 構(gòu)造Adaboost分類器
def adaBoostTrainDS(dataArr, classlabels, numIt = 40):
    weakClassArr = []
    m = np.shape(dataArr)[0]  # 樣本個數(shù)
    D = np.mat(np.ones((m, 1))/m)  # 初始訓(xùn)練樣本權(quán)重
    aggClassEst = np.mat(np.zeros((m, 1)))
    for i in range(numIt):
        bestStump, error, classEst = buildStump(dataArr, classlabels, D)
        # 計算分類器的權(quán)重
        alpha = float(0.5 * np.log((1.0 - error)/max(error, 1e-16))) #計算弱學(xué)習(xí)算法權(quán)重alpha,使error不等于0,因為分母不能為0
        bestStump['alpha'] = alpha  # 一個弱分類器是一個詞典，包含了分類的特征、閾值，分類結(jié)果，及弱分類器的權(quán)重
        weakClassArr.append(bestStump)
        # 重新計算每個樣本的權(quán)重D
        expon = np.multiply(-1 * alpha * np.mat(classlabels).T, classEst) # #數(shù)組對應(yīng)元素位置相乘
        D = np.multiply(D, np.exp(expon))
        D = D/D.sum()
        # 計算AdaBoost誤差，當(dāng)誤差為0的時候，退出循環(huán)
        aggClassEst += alpha * classEst
        aggErrors = np.multiply(np.sign(aggClassEst) != np.mat(classEst).T, np.ones((m, 1)))
        errorRate = aggErrors.sum()/m
        print('totol error:', errorRate)
        if errorRate == 0.0:
            break
    return weakClassArr, aggClassEst

# 使用Adaboost分類器進行分類
def adaClassify(datatoClass, classifierArr):
    dataMatrix = np.mat(datatoClass)
    m = np.shape(dataMatrix)[0]
    aggClassEst = np.mat(np.zeros((m, 1)))
    for i in range(len(classifierArr)):
        # 迭代每一個弱分類器，并將每一個弱分類器的分類結(jié)果與權(quán)重相乘法，再求和，結(jié)果的符號就是最終分類結(jié)果
        classEst = stumpClassify(dataMatrix, classifierArr[i]['dim'],
                                 classifierArr[i]['thresh'], classifierArr[i]['ineq'])
        aggClassEst += classifierArr[i]['alpha']*classEst
    return np.sign(aggClassEst)

if __name__ == '__main__':
    dataArr, classlabels = loadsimple()
    weakClassArr,aggClassEst = adaBoostTrainDS(dataArr, classlabels)
    print(weakClassArr)
    print(aggClassEst)
    print(adaClassify([[0, 0, 6, 10],[1, 5, 6,-3]], weakClassArr))