**一. 關于boosting算法的起源** boost 算法系列的起源來自于PAC Learnability（直譯過來稱為：PAC 可學習性）。這套理論主要研究的是什么時候一個問題是可被學習的。 我們知道，**可計算性**在計算理論中已經有定義，而**可學習性**正是PAC Learnability理論所要定義的內容。另外，在計算理論中還有很大一部分精力花在研究問題是可計算的時候，其復雜度又是什么樣的。因此，在計算學習理論中，也有研究可學習的問題的復雜度的內容，主要是樣本復雜度 (Sample Complexity) 。 最后，在可計算的時候，得到實現計算的具體算法也是計算理論中的一個重要部分；而更多的在“機器學習”這個領域中，我們往往會探討針對可學習的問題的具體的學習算法。 聽起來很復雜，簡而言之，就是：**PAC 模型的作用相當于提供了一套嚴格的形式化語言來陳述以及刻畫這里所提及的可學習性 Learnability 以及（樣本）復雜度 (Sample) Complexity 問題。** 這套理論是由Valiant提出來的，作者曾獲得了2010年的圖靈獎。  PAC 定義了學習算法的強弱： 弱學習算法：識別錯誤率小于1/2（即準確率僅比隨機猜測略高的學習算法）；? 強學習算法：識別準確率很高并能在多項式時間內完成的學習算法。 更為嚴格的定義： 弱學習算法：一個概念如果存在一個多項式的學習算法能夠學習它，并且學習的正確率僅比隨機猜測略好(高于50%)，那么，這個概念是弱可學習的； 強學習算法：一個概念如果存在一個多項式的學習算法能夠學習它，并且正確率很高，那么，這個概念是強可學習的。 同時 ,Valiant和Kearns還提出了PAC學習模型中弱學習算法和強學習算法的等價性問題，即**任意給定僅比隨機猜測略好的弱學習算法 ,是否可以將其提升為強學習算法 ?**?如果弱學習算法和強學習算法二者等價 ,那么只需找到一個比隨機猜測略好的弱學習算法就可以將其提升為強學習算法 ,而不必尋找很難獲得的強學習算法。 也就是這種猜測，讓無數研究人員去設計算法來驗證PAC理論的正確性。 不過很長一段時間都沒有一個切實可行的辦法來實現這個理想。細節決定成敗，再好的理論也需要有效的算法來執行。終于功夫不負有心人， Schapire在1996年提出一個有效的算法真正實現了這個夙愿，它的名字叫AdaBoost。AdaBoost把多個不同的決策樹用一種非隨機的方式組合起來，表現出驚人的性能和優點： 1. 把決策樹的準確率大大提高，可以與SVM媲美； 2. 當使用簡單分類器時，計算出的結果是可以理解的。而且弱分類器構造極其簡單 3. 速度快，且基本不用調參數； 4. 簡單，無需做特征篩選； 5. 不用擔心Overfitting。 “我估計當時Breiman和Friedman肯定高興壞了，因為眼看著他們提出的CART正在被SVM比下去的時候，AdaBoost讓決策樹起死回生！Breiman情不自禁地在他的論文里贊揚AdaBoost是最好的現貨方法（off-the-shelf，即“拿下了就可以用”的意思）。”（這段話摘自統計學習那些事） **二. 基于數據集多重抽樣的分類器** 前面我們已經嘗試設計多種分類器，如果我們嘗試將不同的分類器組合在一起，這種組合的結果就是**集成方法（或稱為元算法）**。使用集成方法時會有多種形式，它可以是不同算法的集成，也可以是同一算法在不同設置下的集成，還可以是數據集的不同部分分配給不同分類器后的集成。通常的集成方法有bagging方法和boosting方法。 **1.bagging：基于數據隨機重抽樣的分類器構建方法** bagging方法，又稱為自舉匯聚法(bootstrap aggregating)，是在從原始數據集重選擇（有放回，可以重復）得到S個新數據集的一種技術，新數據集與原數據集大小相等，每個數據集都是通過在原始數據集中隨機選擇一個樣本來進行替換而得到。 建立好S個新數據集后，將某個學習算法分別作用于每一個數據集，就得到S個分類器。對這S個分類器進行疊加，他們的權重都相等(當然這里S個分類器采用的分類算法不一樣的話，可以考慮使用投票)，這樣就可以得到一個強學習器。 以下給出bagging方法的主要步驟： 1. 重復地從一個樣本集合D中采樣n個樣本 2. 針對每次采樣的子樣本集，進行統計學習，獲得假設Hi 3. 將若干個假設進行組合，形成最終的假設Hfinal 4. 將最終的假設用于具體的分類任務 **2.boosting方法** 書中給出以下解釋：boosting是一種與bagging很類似的技術。不論是在boosting還是bagging方法中，所使用的多個分類器的類型都是一致的。不同的是，bagging方法通過串行訓練獲得不同的分類器，每個新分類器都根據以訓練出的分類器性能來進行訓練；**boosting則是通過集中關注被已有分類器錯分的那些數據來獲得新的分類器。** boosting方法的分類結果是基于所有分類器的加權求和結果，每個分類結果的權重并不相等，每個權重代表的是其對應分類器在上一輪迭代中的成功度。 boosting方法擁有多個版本，Adaboost就是屬于其中一種。 **三. Adaboost：基于錯誤提升分類器的性能** Adaboost是一種迭代算法，其核心思想是針對同一個訓練集訓練不同的分類器，即弱分類器，然后把這些弱分類器集合起來，構造一個更強的最終分類器，比起弱分類器，這個“強”分類器的錯誤率會低很多。 Adaboost算法本身是改變數據分布實現的，它根據每次訓練集之中的每個樣本的分類是否正確，以及上次的總體分類的準確率，來確定每個樣本的權值。將修改權值的新數據送給下層分類器進行訓練，然后將每次訓練得到的分類器融合起來，作為最后的決策分類器。以下給出 Adaboost算法的運行過程： 1. 訓練數據中的每個樣本，并賦予其一個權重，這些權重構成向量D，一開始時權重D初始化為相等的值； 2. 先在訓練樣本上訓練得到第一個弱分類器并計算分類器的**錯誤率**?； 3. 在同一數據集上再次訓練弱分類器，在分類器的二次訓練中，會重新調整每個樣本的權重，其中第一次分類正確的樣本的權重將會降低，而分類錯誤的樣本權重將會提高 ； 4. 為了從所有弱分類器中得到最終的分類結果，Adaboost為每個分類器都分配了一個權重值alpha，這一組值是基于每個弱分類器的**錯誤率**進行計算的。 其中，**錯誤率**由以下公式定義：  而alpha的計算公式如下：  Adaboost算法的流程圖如下：  圖中的左邊表示數據集，其中直方圖的不同寬度表示每個樣例上的不同權重。在經過一個分類器之后，加權的預測結果會通過三角形中的alpha值進行加權，每個三角形中輸出的加權結果在圓形中求和，從而得到最終的輸出結果。 計算出alpha值后，**可以對權重向量D進行更新，使得那些正確分類的樣本的權重降低而錯分樣本的權重升高。**計算方法如下： 對于正確分類的樣本，其權重更改為：  對于錯誤分類的樣本，其權重更改為：  在計算出權重向量D后，Adaboost方法開始進入下一輪的迭代。Adaboost方法會不斷地重復訓練和調整權重的過程，知道訓練錯誤率為0（或達到用戶指定的條件）為止。 **一個博客給出一種容易理解的解釋**：Adaboost的訓練過程有如一個學生學習的過程：我們把每個訓練樣例看做一道練習題，所有的訓練樣本看做一本習題集。第一次做題的時候，由于每道題都沒有做過，不知道哪些難哪些簡單，所以一視同仁，做完了對照答案，可能會有很多題目做的不對，那么對于做錯的題目，我們就重點標記，給予更高的重視程度，這個用權重w來標示，到第二輪做題的時候就重視這些沒做對的“難題”，對于第一次就做對的題目，可以認為是比較簡單的，那么第二次的時候稍微看下就可以了，可以降低他的權重。并且，對于第一輪做完以后的效果給一個整體的評分，評價這輪做題的能力，這個就是alpha。在第二輪做題的時候，就按照上一輪調整過的權重對不同的題目給予不同的重視程度和時間分配。如此不斷練習，幾輪下來，難題就逐漸被攻克了。每輪做題都是有收獲的，只不過每次收獲的知識權重不同（alpha），這樣，我們最后就得到m個分類器，綜合每個分類器的權重，我們就能得到一個“學習成績很好”的分類器了。 **四. 基于單層決策樹構建分類器** 使用Python實現： ~~~ def loadSimDat(): dataMat = matrix([[1, 2.1], [2.0, 1.1], [1.3, 1.0], [1.0, 1.0], [2.0, 1.0]]) classLabels = [1.0, 1.0, -1.0, -1.0, 1.0] return dataMat, classLabels # 單層決策樹生成函數 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 = {}; bestClassEst = 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 #這里的error是錯誤向量errArr和權重向量D的相應元素相乘得到的即加權錯誤率 #print "split: dim %d, thresh %.2f, thresh inequal: %s, the weighted error is %.3f" %(i, threshVal, inequal, weightedError) if weightedError < minError: minError = weightedError bestClassEst = predictedVals.copy() bestStump['dim'] = i bestStump['thresh'] = threshVal bestStump['ineq'] = inequal return bestStump, minError, bestClassEst ~~~ 下一節將應用Adaboost算法，處理非均衡的分類問題。 參考鏈接：? [http://blog.csdn.net/lu597203933/article/details/38666303](http://blog.csdn.net/lu597203933/article/details/38666303)? [http://blog.csdn.net/lskyne/article/details/8425507](http://blog.csdn.net/lskyne/article/details/8425507)