Adaboost算法流程和證明

1、Adaboost 算法1、Adaboost 算法簡介Adaboost算法是Freund和Schapire根據(jù)在線分配算法提出的，他 們詳細(xì)分析了 Adaboost 算法錯誤率的上界，以及為了使強(qiáng)分類器達(dá)到 錯誤率，算法所需要的最多迭代次數(shù)等相關(guān)問題。與 Boosting 算法不 同的是，Adaboost算法不需要預(yù)先知道弱學(xué)習(xí)算法學(xué)習(xí)正確率的下限 即弱分類器的誤差，并且最后得到的強(qiáng)分類器的分類精度依賴于所有 弱分類器的分類精度，這樣可以深入挖掘弱分類器算法的能力。2、Adaboost 算法基本原理Adaboost 是一種迭代算法，其核心思想是針對同一個訓(xùn)練集訓(xùn)練 不同的分類器 （ 弱分類器 ）

2、 ，然后把這些弱分類器集合起來，構(gòu)成一個 更強(qiáng)的最終分類器 （ 強(qiáng)分類器 ） 。其算法本身是通過改變數(shù)據(jù)分布來實(shí) 現(xiàn)的，它根據(jù)每次訓(xùn)練集之中每個樣本的分類是否正確，以及上次的 總體分類的準(zhǔn)確率，來確定每個樣本的權(quán)值。將修改過權(quán)值的新數(shù)據(jù) 集送給下層分類器進(jìn)行訓(xùn)練，最后將每次訓(xùn)練得到的分類器最后融合 起來，作為最后的決策分類器。使用Adaboost 分類器可以排除一些不必要的訓(xùn)練數(shù)據(jù)特征，并將關(guān)鍵放在關(guān)鍵的訓(xùn)練數(shù)據(jù)上面。Adaboost 算法中不同的訓(xùn)練集是通過調(diào)整每個樣本對應(yīng)的權(quán)重來 實(shí)現(xiàn)的。開始時，每個樣本對應(yīng)的權(quán)重是相同的，即其中 n 為樣本個 數(shù)，在此樣本分布下訓(xùn)練出一弱分類器。對于分類

3、錯誤的樣本，加大 其對應(yīng)的權(quán)重；而對于分類正確的樣本，降低其權(quán)重，這樣分錯的樣 本就被突出出來，從而得到一個新的樣本分布。在新的樣本分布下，再次對弱分類器進(jìn)行訓(xùn)練，得到弱分類器。依次類推，經(jīng)過 T次循環(huán)， 得到T個弱分類器，把這T個弱分類器按一定的權(quán)重疊加（boost）起 來，得到最終想要的強(qiáng)分類器。Adaboost算法的具體步驟如下：設(shè)輸入的n個訓(xùn)練樣本為：（ Xi, yj,（ X2, 丫2）丄,（xn, yn）,其中Xj 是輸入的訓(xùn)練樣本，yj 0,1分別表示正樣本和負(fù)樣本，其中正樣本 數(shù)為I，負(fù)樣本數(shù)m。n I m，具體步驟如下：初始化每個樣本的權(quán)重 Wj,i D（i）；對每個t 1,L

4、 ,T （T為弱分類器的個數(shù)）： 把權(quán)重歸一化為一個概率分布 對每個特征f，訓(xùn)練一個弱分類器hj計(jì)算對應(yīng)所有特征的弱分 類器的加權(quán)錯誤率 選取最佳的弱分類器ht（擁有最小錯誤率）：t按照這個最佳弱分類器，調(diào)整權(quán)重其中i o表示被正確地分類，i 1，表示被錯誤地分類最后的強(qiáng)分類器為:1 h(x)0log ttht(x)1 t2 t 1otherwise3、Adaboost算法應(yīng)用隨著Adaboost算法的發(fā)展，目前 Adaboost算法廣泛的應(yīng)用于人 臉檢測、目標(biāo)識別等領(lǐng)域，其中有在人臉識別、汽車識別、駕駛員眨 眼識別的方面的應(yīng)用和研究。Discete-Adaboost 算法、給定訓(xùn)練集：捲,比

5、,L , Xnn ,其中yi 1, 1，表示Xi的正確的 類別標(biāo)簽，i 1,L ,N , gj(xj表示第i副圖像的第j個特征值2、 訓(xùn)練集上樣本的初始分布：D1 i丄m3、尋找弱分類器ht ( t 1,L ,T)對于每個樣本中的第j個特征，可以得到一個弱分類器hj ,即可N得到閾值j和方向Pj，使得jDt(x)hj(xJ yi達(dá)到最小，而弱分類器i 1hj為：其中Pj決定不等式的方向，只有1兩種情況。4、 將所有特征(j )中挑選出一個具有最小誤差t的弱分類器ht。5、對所有的樣本權(quán)重進(jìn)行更新N其中Zt是使 Dt1(x) 1得歸一化因子。i 16、經(jīng)過T輪訓(xùn)練得到T個最優(yōu)的弱分類器，此時組成

6、一個強(qiáng)分類 器；在Adaboost算法的弱學(xué)習(xí)中，將產(chǎn)生錯誤率為1,t的弱分類器。如果每個錯誤率t寸，則強(qiáng)分類器的總錯誤率e 2 一切都從強(qiáng)分類器的錯誤率開始首先權(quán)值更新其中 f(xDt tht(x)然后強(qiáng)分類器的錯誤率 使這個錯誤率快速下降? 乙為歸一化因子。轉(zhuǎn)化為求Zt的最小值了！此時我們用貪心算法求出Zt的一個局部最小值對乙中的t求導(dǎo)此時將t固定令導(dǎo)數(shù)為零趟0解出d t此時繪制Zt關(guān)于t的曲線圖從這幅圖上我們可以看出，當(dāng)錯誤率越小或者越大（只要不在中點(diǎn)處徘徊）的時候Zt快速收斂到0。越?。赫f明錯誤越小的分類器能快速識別出正例。越大:說明錯誤越大的分類器也能快速識別出正例。既然最大，只要我把弱分類器取反，這樣錯誤率就是最小，這樣還是 收斂到0。從以上的證明，我們知道只要是弱分類器的錯誤率都取最小，于是我們就能組合得到一個強(qiáng)分類器。接下來我們就找出一個弱分類器h（x）錯誤率1很小。找T個聯(lián)合起來就得到了強(qiáng)分類器H”nai X ！怎么找弱分類器？ID3生成樹用（CIG類別屬性增益法）修剪樹用（Rule post-pruning