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

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

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

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

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

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

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

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

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

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

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

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

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

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