大數據經典算法AdaBoost 講解

1、AdaBoost1 Adaboost 算法算法 算法分析算法分析 算法步驟算法步驟 訓練過程訓練過程 舉例說明舉例說明 算法介紹算法介紹2Adaboost 算法介紹算法介紹Idea AdaBoost(Adaptive Boosting, R.Scharpire, Y.Freund, ICML, 1996)Adaboost是一種迭代算法，其核心思想是針對同一個訓練集訓練不同的分類器（弱分類器），然后把這些弱分類器集合起來，構成一個更強的最終分類器（強分類器）。3Adaboost 算法介紹算法介紹Adaboost算法本身是通過改變數據分布來實現的，它根據每次訓練集之中每個樣本的分類是否正確，以及上

2、次的總體分類的準確率，來確定每個樣本的權值。將修改過權值的新數據集送給下層分類器進行訓練，最后將每次得到的分類器最后融合起來，作為最后的決策分類器。4Adaboost 算法介紹算法介紹目前，對Adaboost算法的研究以及應用大多集中于分類分類問題，同時近年也出現了一些在回歸回歸問題上的應用。就其應用Adaboost系列主要解決了：兩類問題、多類單標簽問題、多類多標簽問題、大類單標簽問題，回歸問題。它用全部的訓練樣本進行學習。使用adaboost分類器可以排除一些不必要的訓練數據特征，并將關鍵放在關鍵的訓練數據上面。5Adaboost 算法分析算法分析該算法其實是一個簡單的弱分類算法提升過程，

3、這個過程通過不斷的訓練，可以提高對數據的分類能力。1、先通過對N個訓練樣本的學習得到第一個弱分類器；2、將分錯的樣本和其他的新數據一起構成一個新的N個的訓練樣本，通過對這個樣本的學習得到第二個弱分類器；3、將1和2都分錯了的樣本加上其他的新樣本構成另一個新的N個的訓練樣本，通過對這個樣本的學習得到第三個弱分類器4、最終經過提升的強分類器。即某個數據被分為哪一類要通過.的多數表決。6Adaboost 算法分析算法分析對于boosting算法，存在兩個問題： 1. 如何調整訓練集，使得在訓練集上訓練的弱分類器得以進行； 2. 如何將訓練得到的各個弱分類器聯合起來形成強分類器。 7Adaboost

4、算法分析算法分析針對以上兩個問題，AdaBoost算法進行了調整：1. 使用加權后選取的訓練數據代替隨機選取的訓練樣本，這樣將訓練的焦點集中在比較難分的訓練數據樣本上； 2. 將弱分類器聯合起來，使用加權加權的投票機制代替平均投票機制。讓分類效果好的弱分類器具有較大的權重，而分類效果差的分類器具有較小的權重。 8Adaboost 算法分析算法分析 AdaBoost算法是Freund和Schapire根據在線分配算法提出的，他們詳細分析了AdaBoost算法錯誤率的上界，以及為了使強分類器達到錯誤率，算法所需要的最多迭代次數等相關問題。 與Boosting算法不同的是，AdaBoost算法不需要

5、預先知道弱學習算法學習正確率的下限即弱分類器的誤差，并且最后得到的強分類器的分類精度依賴于所有弱分類器的分類精度，這樣可以深入挖掘弱分類器算法的能力。 9Adaboost 算法分析算法分析n AdaBoost算法中不同的訓練集是通過調整每個樣本對應的權重來實現的。開始時，每個樣本對應的權重是相同的，即其中n為樣本個數，在此樣本分布下訓練出一弱分類器。對于分類錯誤的樣本，加大對于分類錯誤的樣本，加大其對應的權重；而對于分類正確的樣本，降低其權其對應的權重；而對于分類正確的樣本，降低其權重，這樣分錯的樣本就被突顯出來，重，這樣分錯的樣本就被突顯出來，從而得到一個新的樣本分布。在新的樣本分布下，再次

6、對樣本進行訓練，得到弱分類器。依次類推，經過T次循環(huán)，得到T個弱分類器，把這T個弱分類器按一定的權重疊加（boost）起來，得到最終想要的強分類器。 10Adaboost 算法分析算法分析nAdaboostAdaboost的核心思想的核心思想“關注關注”被錯分的樣本，“器重器重”性能好的弱分類器n怎么實現怎么實現 （1）不同的訓練集調整樣本權重 （2）“關注”增加錯分樣本權重 （3）“器重”好的分類器權重大 （4） 樣本權重間接影響分類器權重11Adaboost 算法步驟算法步驟nAdaBoost算法的具體步驟如下： n1. 給定訓練樣本集S，其中X和Y分別對應于正例樣本和負例樣本；T為訓練的

7、最大循環(huán)次數；n2. 初始化樣本權重為1/n ，即為訓練樣本的初始概率分布； n3. 第一次迭代：(1)訓練樣本的概率分布相當，訓練弱分類器;(2)計算弱分類器的錯誤率;(3)選取合適閾值，使得誤差最?。?4)更新樣本權重； n經T次循環(huán)后，得到T個弱分類器，按更新的權重疊加，最終得到的強分類器。 12Adaboost 算法步驟算法步驟Adaboost算法是經過調整的Boosting算法，其能夠對弱學習得到的弱分類器的錯誤進行適應性(Adaptive)調整。上述算法中迭代了T次的主循環(huán)，每一次循環(huán)根據當前的權重分布對樣本x定一個分布P，然后對這個分布下的樣本使用弱學習算法得到一個弱分類器，對于

8、這個算法定義的弱學習算法，對所有的樣本都有錯誤率，而這個錯誤率的上限并不需要事先知道，實際上。每一次迭代，都要對權重進行更新。更新的規(guī)則是：減小弱分類器分類效果較好的數據的概率，增大減小弱分類器分類效果較好的數據的概率，增大弱分類器分類效果較差的數據的概率。最終的分類器弱分類器分類效果較差的數據的概率。最終的分類器是個弱分類器的加權平均是個弱分類器的加權平均13一.樣本樣本Given: m examples (x1, y1), , (xm, ym) where xiX, yiY=-1, +1 xi表示X中第i個元素， yi表示與xi對應元素的屬性值，+1表示xi屬于某個分類， -1表示xi不屬

9、于某個分類二.初始化訓練樣本初始化訓練樣本xi的權重的權重D(i) :i=1,，m; (1).若正負樣本數目一致，D1(i) = 1/m (2).若正負樣本數目m+, m-則正樣本D1(i) = = 1/m+， 負樣本D1(i) = 1/m-Schapire Adaboost Algorithm14三三. .訓練弱分類器訓練弱分類器For t=1,TTrain learner ht with min error 若劃分正確，則不計入誤差，若所有元素都被正確劃分，則誤差為0若劃分錯誤，則計入誤差2. If t0.5, then stop3. Compute the hypothesis weig

10、ht 4.5.最后得到的強分類器:Schapire Adaboost AlgorithmPr ( )tti Dtiih xy ttt1ln21The weight Adapts. The bigger t becomes the smaller t becomes.TtttxhxH1)(sign)(15 Adaboost 算法的優(yōu)點算法的優(yōu)點1)Adaboost是一種有很高精度的分類器2)可以使用各種方法構建子分類器,Adaboost算法 提供的是框架3)當使用簡單分類器時，計算出的結果是可以理解的。 而且弱分類器構造極其簡單4)簡單，不用做特征篩選5)不用擔心overfitting(過度擬合

11、)！16 Adaboost 實例詳解實例詳解下面我們舉一個簡單的例子來看看adaboost 的實現過程：圖中，“+”和“-”分別表示兩種類別，在這個過程中，我們使用水平或者垂直的直線作為分類器，來進行分類。17 Adaboost 實例詳解實例詳解根據分類的正確率，得到一個新的樣本分布(樣本中每個元素的權重分布)D2，一個子分類器h1。其中劃圈的樣本表示被分錯的。在右邊的途中，比較大的“+”表示對該樣本做了加權。也許你對上面的1，1 怎么算的也不是很理解。算法最開始給了一個均勻分布 D 。所以h1 里的每個點的值是0.1。當劃分后，有三個點劃分錯了，根據算法誤差表達式 得到誤差為分錯的三個點的值

12、之和，所以。t=(0.1+0.1+0.1)=0.3,然后根據算法把分錯點的權值變大，分錯點的權值計算如下：對于分類正確的7個點，其權值保持不變，為0.1；對于分類錯誤的3個點，其權值為|)(|1titimitxhyD42.03.03.01ln211ln211112333.03.03.011.0-1i)（111D18 Adaboost 實例詳解實例詳解19 Adaboost 實例詳解實例詳解根據分類的正確率，得到一個新的樣本分布D3，一個子分類器h2如上圖所示，弱分類器h2 中有三個“-”符號分類錯誤，分類錯誤的權值為：we2=0.1*3=0.3；上圖中十個點的總權值為：wt2=0.1*7+0.

13、233*3=1.3990；錯誤率為：2=we2/wt2=0.3/1.399= 0.2144;對于分類錯誤的三個點，其權值為:于是，分類錯誤的三個點誤差增加為0.3664如此迭代6493.02144.02144.01ln211ln212223644.02144.02144.011.0-1i)（222D20 Adaboost 實例詳解實例詳解21 Adaboost 實例詳解實例詳解得到一個子分類器h3如上圖所示，弱分類器h3 中有兩個“+”符號和一個“-”符號分類錯誤，分類錯誤的權值為we3=0.1*2+0.1*1=0.3；上圖中十個點的總權值為：wt3=0.1*4+0.233*3+0.3664*

14、3=2.1982；錯誤率為： t=we3/wt3=0.3/2.1982= 0.1365;對于分類錯誤的三個點，其權值為:于是，分類錯誤的三個點誤差增加為0.6326如此迭代9223.01365.01365.01ln211ln213336326.01365.01365.011.0-1i)（333D22 Adaboost 實例詳解實例詳解每個區(qū)域是屬于哪個屬性，由這個區(qū)域所在分類器的權值綜合決定。比如左下角的區(qū)域，屬于藍色分類區(qū)的權重為h1 中的0.42和h2 中的0.65，其和為1.07；屬于淡紅色分類區(qū)域的權重為h3 中的0.92；屬于淡紅色分類區(qū)的權重小于屬于藍色分類區(qū)的權值，因此左下角屬于

15、藍色分類區(qū)。因此可以得到整合的結果如上圖所示，從結果圖中看，即使是簡單的分類器，組合起來也能獲得很好的分類效果。23Adaboost 權值調整的原因 注意到算法最后的表到式為這里面的t表示的權值，是由 得到的。而是關于誤差的表達式，到這里就可以得到比較清晰的答案了，所有的一切都指向了誤差。提高錯誤點的權值，當下一次分類器再次分錯了這些點之后，會提高整體的錯誤率，這樣就導致t變的很小，最終導致這個分類器在整個混合分類器的權值變低。也就是說，這個算法讓優(yōu)秀的分類器占整體的權值更高，而挫的分類器權值更低。這個就很符合常理了。到此，我認為對adaboost 已經有了一個透徹的理解了。24ttt1ln21）)(（)（1tTttxhsignxH 總結總結最后，我們可以總結下adaboost算法的一些實際可以使用的場景：1）用于二分類或多分類的應用場景2）用于做分類任務的baseli