AdaBoost演算法的原理與實現

導語

AdaBoost演算法與SVM演算法通常被認為是有監督學習中最強大的兩種演算法。上一節講義中對SVM演算法進行了深入講解，本節對AdaBoost演算法進行講解，重點在於理解該演算法的原理，並用python對其進行實現。

1 AdaBoost演算法

AdaBoost的全稱是Adaptive Boosting，是「自適應增強」的意思。AdaBoost演算法的本質，是用來提升分類器的分類性能。它用什麼方法來提升呢？有兩個途徑：

（1）集成的方法。一個分類器性能不好，就通過組合多個分類器來完成，也就是俗語「三個臭皮匠頂一個諸葛亮」的意思。每個基分類器都是弱分類器，通過集成的方法，加權組合成一個強分類器。這就是Boosting的內涵。

（2）自適應的方法。在訓練各個基分類器時，採用順序生成的方法。前一輪訓練中被基分類器錯分的樣本，會在訓練下一個基分類器中得到增強，即在每一輪訓練中加大上一輪中錯分樣本的權重，這就是Adaptive的內涵。

注釋1：:弱分類器的「弱」的意思，即分類器的分類性能比隨機猜測略好，也好不了多少，在二分類的情況下，錯誤率可能會高於50%。而強分類器的錯誤率會低很多。

瞭解AdaBoost演算法內涵之後，可以發現它主要包括以下幾部分：

（1）設計基分類器。你可以根據所處理數據的特點選擇弱分類器，決策樹、kNN、logistic回歸方法等等都可以作為弱分類器。一般來說，作為弱分類器，簡單的分類器效果會更好一些。

（2）訓練基分類器。一開始，訓練數據集中的樣本權重初始化為相等值。訓練過程中，某個樣本分類如果被分錯了，則它在下一個訓練數據集中的權重增加，反之，分對了，它的權值就降低。權值更新後，樣本集用於下一個基分類器的訓練，如此迭代，直至達到某個預定的足夠小的錯誤率或達到預先指定的最大迭代次數。（注意：訓練數據集的樣本值在每一輪中都是不變的，變的是這些樣本的權重。）

（3）組合基分類器。訓練結束後，將各個弱分類器組合成強分類器。組合的方法是，根據每個弱分類器的誤差率，加權相加。即誤差率小的弱分類器分配個較大權重，誤差率大的弱分類器分配個較小的權重。

2 AdaBoost演算法步驟

假設有一個訓練數據集有個樣本點，即 $left{ (x_{1},y_{1}),(x_{2},y_{2}) ,...,(x_{n},y_{n}) ight}$ 。代表數據特徵，代表對應的標籤， $y_{i}inleft{+1,-1 ight}$ 。AdaBoost演算法的步驟如下：

<1> 初始化樣本權重。每個樣本最開始被賦予相等值，即，樣本權重用向量表示，則

$egin{cases} D_{1}=(omega_{11},omega_{12},...,omega_{1n})\ omega_{1i}=frac{1}{n},quad i=1,2,...,n\ end{cases}$

其中， $D_{1}$ 代表第一輪訓練的樣本權重。

<2> 構建弱分類器。可以用決策樹、kNN等等方法來設計弱分類器。例如，在決策樹方法中，可以把最低誤差率的單層決策樹作為基分類器 $G_{m}(x)$ ，代表第輪迭代。

<3> 計算在第輪訓練中 $G_{m}(x)$ 的誤差率 $e_{m}$ 。

$e_{m}=P(G_{m}(x_{i}) e y_{i})\ quadquadquadquad=sum_{i=1}^{n}{omega_{mi}I(G_{m}(x_{i}) e y_{i})}$

可以看出， $G_{m}(x)$ 在訓練數據集上的誤差率 $e_{m}$ 就是被 $G_{m}(x)$ 誤分類樣本的權值之和。

<4> 計算 $G_{m}(x)$ 在最終分類器中的權重 $alpha_{m}$ 。

$alpha_{m}=frac{1}{2}lnfrac{1-e_{m}}{e_{m}}$

分析這個公式，當 $e_{m}leqfrac{1}{2}$ 時， $alpha_{m}geq0$ ，且 $alpha_{m}$ 隨著 $e_{m}$ 的減小而增大，意味著分類誤差率越小的基分類器在最終分類器中的作用越大。

<5> 更新樣本權重 $D_{m+1}$ ，用於下一輪迭代。

$egin{cases} D_{m+1}=(omega_{m+1,1},omega_{m+1,2},...,omega_{m+1,n})quadquad quad \ omega_{m+1,i}=frac{omega_{m,i}cdot e^{-alpha_{m}y_{i}G_{m}(x_{i})}}{Z_{m}},quad i=1,2,...,n\ Z_{m}=sum_{i=1}^{n}{omega_{m,i}cdot e^{-alpha_{m}y_{i}G_{m}(x_{i})}}quad quad quad quad quad quad end{cases}$

其中， $Z_{m}$ 是歸一化因子。可以看出，如果 $x_{i}$ 分類正確，則 $y_{i}G_{m}(x_{i})=1$ ， $omega_{m+1,i}=frac{omega_{m,i}cdot e^{-alpha_{m}}}{Z_{m}}$ ，權值變小。如果 $x_{i}$ 分類錯誤，則 $y_{i}G_{m}(x_{i})=-1$ ， $omega_{m+1,i}=frac{omega_{m,i}cdot e^{alpha_{m}}}{Z_{m}}$ ，權值變大。這樣，在接下來的訓練中，重點關注這些錯分樣本。

<6> 組合各個基分類器，從而得到最終分類器。

$f(x)=sum_{m=1}^{M}{alpha_{m}G_{m}(x)}$

最終分類器為

$G(x)=sign(f(x))=sign(sum_{m=1}^{M}{alpha_{m}G_{m}(x)})$

至此，AdaBoost演算法結束。

3 AdaBoost演算法的實現

下面，我們用python對AdaBoost演算法進行實現。數據導入的函數就不再羅嗦了，在上一節中有，大同小異。重點聚焦構建弱分類器和用AdaBoost提升分類器性能，這是AdaBoost演算法的核心。

（1）構建弱分類器。可以根據需要構建任意類型的弱分類器，單層決策樹（decision stump）是AdaBoost比較流行的弱分類器，我們以此為例，直接上代碼。

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

在單層決策樹函數中，參數dataMatrix表示輸入的數據矩陣；dimen表示第dimen列，也就是第幾個特徵；threshVal表示閾值，在這個閾值兩側，取不同的分類；threshIneq是定義的一個標誌位，當它為lt（less than）時，則小於閾值的是-1類，大於閾值的是+1類，當它取其它值時，則大於閾值的取-1類，小於閾值的是+1類。

def buildStump(dataArr,classLabels,D): """ 根據給定的權值向量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]: #lt(less than),gt(greater than) 都考慮到 threshVal = (rangeMin + float(j) * stepSize) #計算閾值 predictedVals = stumpClassify(dataMatrix,i,threshVal,inequal) errArr = mat(ones((m,1))) #初始化誤差矩陣為單位矩陣 errArr[predictedVals == labelMat] = 0 #分類正確,誤差矩陣對應值為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

該函數的輸入參數dataArr表示數據矩陣，classLabels表示對應的標籤，D為權值向量。返回參數bestStump為一個字典，保存了最佳單層決策樹信息，minError代表最小誤差，bestClasEst表示最佳分類結果。

（2）AdaBoost演算法訓練弱分類器。

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) #構建單層決策樹作為弱分類器 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 = multiply(D,exp(expon)) #更新樣本的權重矩陣D D = D/D.sum() #計算訓練誤差, 當誤差為0時, 跳出循環 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,aggClassEst

AdaBoost演算法的輸入參數為訓練樣本數據，對應的類標籤，以及最大迭代次數numIt。返回參數weakClassArr為保存的所有弱分類器信息，aggClassEst為每次迭代後輸出的類別值乘以該決策樹的權重，然後累加。根據它的符號可以判斷最終類別，即如果大於0則為+1類，小於0則為-1類。

這樣，我們就得到了多個分類器，以及對應的權重。將這些分類器加權求和，就可得到最終的分類器。此時如果用新的測試樣本，對該分類器性能進行測試，就非常容易了。

def adaClassify(datToClass,classifierArr): """ 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)

至此，AdaBoost演算法就介紹完了。回顧一下，它的作用是提升分類器的性能。基本思想就是在訓練基分類器的過程中，不斷自適應調整樣本權重，將分類重點放在難分類的數據上，最後根據所有基分類器的誤差率加權組合成最終的分類器。