Adaboost算法流程和證明

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

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

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

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

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

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