Adaboost算法流程和證明

Adaboost算法流程和證明Adaboost算法流程和證明本頁(yè)僅作為文檔頁(yè)封面，使用時(shí)可以刪除Thisdocumentisforreferenceonly-rar21year.MarchAdaboost算法1、 Adaboost算法簡(jiǎn)介Adaboost算法是Freund和Schapire根據(jù)在線分配算法提出的，他們?cè)敿?xì)分析了Adaboost算法錯(cuò)誤率的上界，以及為了使強(qiáng)分類器達(dá)到錯(cuò)誤率，算法所需要的最多迭代次數(shù)等相關(guān)問(wèn)題。與Boosting算法不同的是，Adaboost算法不需要預(yù)先知道弱學(xué)習(xí)算法學(xué)習(xí)正確率的下限即弱分類器的誤差，并且最后得到的強(qiáng)分類器的分類精度依賴于所有弱分類器的分類精度，這樣可以深入挖掘弱分類器算法的能力。2、 Adaboost算法基本原理Adaboost是一種迭代算法，其核心思想是針對(duì)同一個(gè)訓(xùn)練集訓(xùn)練不同的分類器（弱分類器），然后把這些弱分類器集合起來(lái)，構(gòu)成一個(gè)更強(qiáng)的最終分類器（強(qiáng)分類器）。其算法本身是通過(guò)改變數(shù)據(jù)分布來(lái)實(shí)現(xiàn)的，它根據(jù)每次訓(xùn)練集之中每個(gè)樣本的分類是否正確，以及上次的總體分類的準(zhǔn)確率，來(lái)確定每個(gè)樣本的權(quán)值。將修改過(guò)權(quán)值的新數(shù)據(jù)集送給下層分類器進(jìn)行訓(xùn)練，最后將每次訓(xùn)練得到的分類器最后融合起來(lái)，作為最后的決策分類器。使用Adaboost分類器可以排除一些不必要的訓(xùn)練數(shù)據(jù)特征，并將關(guān)鍵放在關(guān)鍵的訓(xùn)練數(shù)據(jù)上面。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)練出一弱分類器。對(duì)于分類錯(cuò)誤的樣本，加大其對(duì)應(yīng)的權(quán)重；而對(duì)于分類正確的樣本，降低其權(quán)重，這樣分錯(cuò)的樣本就被突出出來(lái)，從而得到一個(gè)新的樣本分布。在新的樣本分布下，再次對(duì)弱分類器進(jìn)行訓(xùn)練，得到弱分類器。依次類推，經(jīng)過(guò)T次循環(huán)，得到T個(gè)弱分類器，把這T個(gè)弱分類器按一定的權(quán)重疊加（boost）起來(lái)，得到最終想要的強(qiáng)分類器。Adaboost算法的具體步驟如下：設(shè)輸入的n個(gè)訓(xùn)練樣本為：｛（x,v），（X，y）,,（X，y）｝,其中1 ] 2 2七是輸入的訓(xùn)練樣本，y產(chǎn)｛?！唬謩e表示正樣本和負(fù)樣本，其中正???樣本數(shù)為Z，負(fù)樣本數(shù)m。n=1+m，具體步驟如下：⑴初始化每個(gè)樣本的權(quán)重弓,i￡D（i）；⑵對(duì)每個(gè)t=1,，T（t為弱分類器的個(gè)數(shù)）：把權(quán)重歸一化為一個(gè)概率分布???WW=t,it，in旗wt,jj=1對(duì)每個(gè)特征f，訓(xùn)練一個(gè)弱分類器h]計(jì)算對(duì)應(yīng)所有特征的弱分類器的加權(quán)錯(cuò)誤率￡=^nw（x）h（x）。yi=1選取最佳的弱分類器ht（擁有最小錯(cuò)誤率）：￡t按照這個(gè)最佳弱分類器，調(diào)整權(quán)重w.=w.P1-￡i其中e.=0表示被正確地分類，8.=1,表示被錯(cuò)誤地分類⑶最后的強(qiáng)分類器為：h(x)=<~I11h(x)=<~I11t，a=log—-t=1 t ptt=10otherwise3、Adaboost算法應(yīng)用隨著Adaboost算法的發(fā)展，目前Adaboost算法廣泛的應(yīng)用于人臉檢測(cè)、目標(biāo)識(shí)別等領(lǐng)域，其中有在人臉識(shí)別、汽車識(shí)別、駕駛員眨眼識(shí)別的方面的應(yīng)用和研究。Discete-Adaboost算法1、 給定訓(xùn)練集：(x,y),,(x,y)，其中ye(1,-1｝，表示x的正確1 1 NN i i的類別標(biāo)簽，i=1,,N，g.(x)表示第i副圖像的第j個(gè)特征值2、 訓(xùn)練集上樣本的初始分布：？(i)=13、 尋找弱分類器ht(t=1,,T)⑴對(duì)于每個(gè)樣本中的第j個(gè)特征，可以得到一個(gè)弱分類器hj，即可得到閾值0.和方向〃?使得￡=丈D(x)lh(x)豐y|達(dá)到最小，而弱分類j 八 j tijii1i=1器h.為：f1pg(x)<p0

h(x)=[jjjj

j〔Tother其中pj決定不等式的方向，只有±1兩種情況。4、將所有特征(j)中挑選出一個(gè)具有最小誤差￡，的弱分類器h。

5、對(duì)所有的樣本權(quán)重進(jìn)行更新DD(,.)_D(，)exp(-七yh(氣))

t+i1-— Z''''t其中Z是使］Ld1(x)=1得歸一化因子。i=16、經(jīng)過(guò)T輪訓(xùn)練得到T個(gè)最優(yōu)的弱分類器，此時(shí)組成一個(gè)強(qiáng)分類器;Hi(Hi(x)=sign:atht(x),在Adaboost算法的弱學(xué)習(xí)中，將產(chǎn)生錯(cuò)誤率為七,e2七的弱分類器。如果每個(gè)錯(cuò)誤率七<2，則強(qiáng)分類器的總錯(cuò)誤率e<2奸乓)一切都從強(qiáng)分類器的錯(cuò)誤率開(kāi)始 …首先權(quán)值更新D(首先權(quán)值更新D(i)exp(-ayh(x))exp(-2ayh(x)exp(-yf(x))(i)=_t t_L_ti_= titi—- milZDt+1Zt其中f(x,)=2ah.(x)然后強(qiáng)分類器的錯(cuò)誤率mli^Zitrainingerror(H)―trainingerror(H)―if1f七。貝氣)

N [0else=￡2f1ifyf(x.)<0N 0else=-12exp(-yf(x))N iii=2氣沖Ztit使這個(gè)錯(cuò)誤率快速下降？Z=2D(i)exp(-ayh(x))

t t titiiZ為歸一化因子。轉(zhuǎn)化為求z的最小值了！tZ=ZD(尤)exp(-ayh(x))

t ti titii二￡D(x)exp(-a)+￡D(x)exp(a)i:y=H(x) i:y力H(x)yi'i/ yi'i，二(1-8)exp(-a)+8exp(a)t t t t此時(shí)我們用貪心算法求出Zt的一個(gè)局部最小值對(duì)Z中的a求導(dǎo)［此時(shí)將8固定］dZ , 、——鏟=-(1-8)exp(-a)+8exp(a)dat令導(dǎo)數(shù)為零芻二0解出data=—ln( )t2 8t此時(shí)Z=2(8(1-8)繪制Z關(guān)于8,的曲線圖從這幅圖上我們可以看出，當(dāng)錯(cuò)誤率越小或者越大(只要不在中點(diǎn)處徘徊)的時(shí)候Z,快速收斂到0。越?。赫f(shuō)明錯(cuò)誤越小的分類器能快速識(shí)別出正例。越大：說(shuō)明錯(cuò)誤越大的分類器也能快速識(shí)別出正例?！?歹D(x)h(x)。yj tijiii=1既然最大，只要我把弱分類器取反，這樣錯(cuò)誤率就是最小，這樣還是收斂到0。從以上的證明，我們知道只要是弱分類器的錯(cuò)誤率都取最小，于是我們就能組合得到一個(gè)強(qiáng)分類器。接下來(lái)我們就找出一個(gè)弱分類器hi(X)錯(cuò)誤率\很小。找T個(gè)聯(lián)合起來(lái)就得到了強(qiáng)分類器H著x)！怎么找弱分類器？

決策樹(shù)ID3,C4.5,C5.0ID3生成樹(shù)用（CIG類別屬性增益法）C4.5生成樹(shù)用（GainRatio增益比率法）修剪樹(shù)用（Rulepost-pruning規(guī)則修剪）C5.0生成樹(shù)用（Giniindex基尼指數(shù)）修剪樹(shù)用（CRAT回歸樹(shù)修剪）然后給出YoavFreund