大數(shù)據(jù)十大經(jīng)典算法AdaBoost-講解

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

2、數(shù)據(jù)集送給下層分類器進行訓練，最后將每次得到的分類器最后融合起來，作為最后的決策分類器。4Adaboost 算法介紹目前，對Adaboost算法的研究以及應(yīng)用大多集中于分類問題，同時近年也出現(xiàn)了一些在回歸問題上的應(yīng)用。就其應(yīng)用Adaboost系列主要解決了：兩類問題、多類單標簽問題、多類多標簽問題、大類單標簽問題，回歸問題。它用全部的訓練樣本進行學習。使用adaboost分類器可以排除一些不必要的訓練數(shù)據(jù)特征，并將關(guān)鍵放在關(guān)鍵的訓練數(shù)據(jù)上面。5Adaboost 算法分析該算法其實是一個簡單的弱分類算法提升過程，這個過程通過不斷的訓練，可以提高對數(shù)據(jù)的分類能力。1、先通過對N個訓練樣本的學習得到

3、第一個弱分類器；2、將分錯的樣本和其他的新數(shù)據(jù)一起構(gòu)成一個新的N個的訓練樣本，通過對這個樣本的學習得到第二個弱分類器；3、將1和2都分錯了的樣本加上其他的新樣本構(gòu)成另一個新的N個的訓練樣本，通過對這個樣本的學習得到第三個弱分類器4、最終經(jīng)過提升的強分類器。即某個數(shù)據(jù)被分為哪一類要通過.的多數(shù)表決。6Adaboost 算法分析對于boosting算法，存在兩個問題： 1. 如何調(diào)整訓練集，使得在訓練集上訓練的弱分類器得以進行； 2. 如何將訓練得到的各個弱分類器聯(lián)合起來形成強分類器。 7Adaboost 算法分析針對以上兩個問題，AdaBoost算法進行了調(diào)整：1. 使用加權(quán)后選取的訓練數(shù)據(jù)代替

4、隨機選取的訓練樣本，這樣將訓練的焦點集中在比較難分的訓練數(shù)據(jù)樣本上； 2. 將弱分類器聯(lián)合起來，使用加權(quán)的投票機制代替平均投票機制。讓分類效果好的弱分類器具有較大的權(quán)重，而分類效果差的分類器具有較小的權(quán)重。 8Adaboost 算法分析 AdaBoost算法是Freund和Schapire根據(jù)在線分配算法提出的，他們詳細分析了AdaBoost算法錯誤率的上界，以及為了使強分類器達到錯誤率，算法所需要的最多迭代次數(shù)等相關(guān)問題。 與Boosting算法不同的是，AdaBoost算法不需要預先知道弱學習算法學習正確率的下限即弱分類器的誤差，并且最后得到的強分類器的分類精度依賴于所有弱分類器的分類精度

5、，這樣可以深入挖掘弱分類器算法的能力。 9Adaboost 算法分析 AdaBoost算法中不同的訓練集是通過調(diào)整每個樣本對應(yīng)的權(quán)重來實現(xiàn)的。開始時，每個樣本對應(yīng)的權(quán)重是相同的，即其中n為樣本個數(shù)，在此樣本分布下訓練出一弱分類器。對于分類錯誤的樣本，加大其對應(yīng)的權(quán)重；而對于分類正確的樣本，降低其權(quán)重，這樣分錯的樣本就被突顯出來，從而得到一個新的樣本分布。在新的樣本分布下，再次對樣本進行訓練，得到弱分類器。依次類推，經(jīng)過T次循環(huán)，得到T個弱分類器，把這T個弱分類器按一定的權(quán)重疊加（boost）起來，得到最終想要的強分類器。 10Adaboost 算法分析Adaboost的核心思想“關(guān)注”被錯分的

6、樣本，“器重”性能好的弱分類器怎么實現(xiàn) （1）不同的訓練集調(diào)整樣本權(quán)重 （2）“關(guān)注”增加錯分樣本權(quán)重 （3）“器重”好的分類器權(quán)重大 （4） 樣本權(quán)重間接影響分類器權(quán)重11Adaboost 算法步驟AdaBoost算法的具體步驟如下： 1. 給定訓練樣本集S，其中X和Y分別對應(yīng)于正例樣本和負例樣本；T為訓練的最大循環(huán)次數(shù)；2. 初始化樣本權(quán)重為1/n ，即為訓練樣本的初始概率分布； 3. 第一次迭代：(1)訓練樣本的概率分布相當，訓練弱分類器;(2)計算弱分類器的錯誤率;(3)選取合適閾值，使得誤差最??；(4)更新樣本權(quán)重； 經(jīng)T次循環(huán)后，得到T個弱分類器，按更新的權(quán)重疊加，最終得到的強分類

7、器。 12Adaboost 算法步驟Adaboost算法是經(jīng)過調(diào)整的Boosting算法，其能夠?qū)θ鯇W習得到的弱分類器的錯誤進行適應(yīng)性(Adaptive)調(diào)整。上述算法中迭代了T次的主循環(huán)，每一次循環(huán)根據(jù)當前的權(quán)重分布對樣本x定一個分布P，然后對這個分布下的樣本使用弱學習算法得到一個弱分類器，對于這個算法定義的弱學習算法，對所有的樣本都有錯誤率，而這個錯誤率的上限并不需要事先知道，實際上。每一次迭代，都要對權(quán)重進行更新。更新的規(guī)則是：減小弱分類器分類效果較好的數(shù)據(jù)的概率，增大弱分類器分類效果較差的數(shù)據(jù)的概率。最終的分類器是個弱分類器的加權(quán)平均13一.樣本Given: m examples (x

8、1, y1), , (xm, ym) where xiX, yiY=-1, +1 xi表示X中第i個元素， yi表示與xi對應(yīng)元素的屬性值，+1表示xi屬于某個分類， -1表示xi不屬于某個分類二.初始化訓練樣本xi的權(quán)重D(i) :i=1,，m; (1).若正負樣本數(shù)目一致，D1(i) = 1/m (2).若正負樣本數(shù)目m+, m-則正樣本D1(i) = 1/m+， 負樣本D1(i) = 1/m-Schapire Adaboost Algorithm14三.訓練弱分類器For t=1,TTrain learner ht with min error 若劃分正確，則不計入誤差，若所有元素都被正

9、確劃分，則誤差為0若劃分錯誤，則計入誤差2. If t0.5, then stop3. Compute the hypothesis weight 4.5.最后得到的強分類器:Schapire Adaboost AlgorithmThe weight Adapts. The bigger et becomes the smaller at becomes.15 Adaboost 算法的優(yōu)點1)Adaboost是一種有很高精度的分類器2)可以使用各種方法構(gòu)建子分類器,Adaboost算法 提供的是框架3)當使用簡單分類器時，計算出的結(jié)果是可以理解的。 而且弱分類器構(gòu)造極其簡單4)簡單，不用做特征

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

11、達式 得到誤差為分錯的三個點的值之和，所以。t=(0.1+0.1+0.1)=0.3,然后根據(jù)算法把分錯點的權(quán)值變大，分錯點的權(quán)值計算如下：對于分類正確的7個點，其權(quán)值保持不變，為0.1；對于分類錯誤的3個點，其權(quán)值為18 Adaboost 實例詳解19 Adaboost 實例詳解根據(jù)分類的正確率，得到一個新的樣本分布D3，一個子分類器h2如上圖所示，弱分類器h2 中有三個“-”符號分類錯誤，分類錯誤的權(quán)值為：we2=0.1*3=0.3；上圖中十個點的總權(quán)值為：wt2=0.1*7+0.233*3=1.3990；錯誤率為：2=we2/wt2=0.3/1.399= 0.2144;對于分類錯誤的三個點

12、，其權(quán)值為:于是，分類錯誤的三個點誤差增加為0.3664如此迭代20 Adaboost 實例詳解21 Adaboost 實例詳解得到一個子分類器h3如上圖所示，弱分類器h3 中有兩個“+”符號和一個“-”符號分類錯誤，分類錯誤的權(quán)值為we3=0.1*2+0.1*1=0.3；上圖中十個點的總權(quán)值為：wt3=0.1*4+0.233*3+0.3664*3=2.1982；錯誤率為： t=we3/wt3=0.3/2.1982= 0.1365;對于分類錯誤的三個點，其權(quán)值為:于是，分類錯誤的三個點誤差增加為0.6326如此迭代22 Adaboost 實例詳解每個區(qū)域是屬于哪個屬性，由這個區(qū)域所在分類器的權(quán)

13、值綜合決定。比如左下角的區(qū)域，屬于藍色分類區(qū)的權(quán)重為h1 中的0.42和h2 中的0.65，其和為1.07；屬于淡紅色分類區(qū)域的權(quán)重為h3 中的0.92；屬于淡紅色分類區(qū)的權(quán)重小于屬于藍色分類區(qū)的權(quán)值，因此左下角屬于藍色分類區(qū)。因此可以得到整合的結(jié)果如上圖所示，從結(jié)果圖中看，即使是簡單的分類器，組合起來也能獲得很好的分類效果。23Adaboost 權(quán)值調(diào)整的原因 注意到算法最后的表到式為這里面的t表示的權(quán)值，是由 得到的。而是關(guān)于誤差的表達式，到這里就可以得到比較清晰的答案了，所有的一切都指向了誤差。提高錯誤點的權(quán)值，當下一次分類器再次分錯了這些點之后，會提高整體的錯誤率，這樣就導致t變的很小，最終導致這個分類器在整個混合分類器的權(quán)值變低。也就是說，這個算法讓優(yōu)秀的分類器占整體的權(quán)值更高，而挫的分類器權(quán)值更低。這個就很符合常理了。到此，我認為對adaboost 已經(jīng)有了一個透徹的理解了。24 總結(jié)最后，我們可以總結(jié)下adaboost算法的一些實際可以使用的場景：1）用于二分類或多分類的應(yīng)用場景2）用于做分類任務(wù)的baseline，無腦化，簡單，不會overf