Adaboost算法流程和證明

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

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

3、其權(quán)重，這樣分錯的樣本就被突出出來，從而得到一個新的樣本分布。在新的樣本分布下，再次對弱分類器進行訓練，得到弱分類器。依次類推，經(jīng)過次循環(huán)，得到個弱分類器，把這個弱分類器按一定的權(quán)重疊加(boost)起來，得到最終想要的強分類器。 Adaboost算法的具體步驟如下：設(shè)輸入的個訓練樣本為：,其中是輸入的訓練樣本，分別表示正樣本和負樣本，其中正樣本數(shù)為，負樣本數(shù)。，具體步驟如下：初始化每個樣本的權(quán)重；對每個(為弱分類器的個數(shù))：把權(quán)重歸一化為一個概率分布對每個特征，訓練一個弱分類器計算對應(yīng)所有特征的弱分類器的加權(quán)錯誤率選取最正確的弱分類器(擁有最小錯誤率)：按照這個最正確弱分類器，調(diào)整權(quán)重其中表

4、示被正確地分類，表示被錯誤地分類最后的強分類器為：，3、Adaboost算法應(yīng)用 隨著Adaboost算法的開展，目前Adaboost算法廣泛的應(yīng)用于人臉檢測、目標識別等領(lǐng)域，其中有在人臉識別、汽車識別、駕駛員眨眼識別的方面的應(yīng)用和研究。Discete-Adaboost算法1、給定訓練集：，其中，表示的正確的類別標簽， ,表示第副圖像的第個特征值2、訓練集上樣本的初始分布：3、尋找弱分類器()對于每個樣本中的第個特征，可以得到一個弱分類器，即可得到閾值和方向，使得到達最小，而弱分類器為：其中決定不等式的方向, 只有兩種情況。4、將所有特征()中挑選出一個具有最小誤差的弱分類器。5、對所有的樣本

5、權(quán)重進行更新其中是使得歸一化因子。6、經(jīng)過輪訓練得到個最優(yōu)的弱分類器，此時組成一個強分類器；在Adaboost算法的弱學習中，將產(chǎn)生錯誤率為的弱分類器。如果每個錯誤率，那么強分類器的總錯誤率一切都從強分類器的錯誤率開始首先權(quán)值更新其中然后強分類器的錯誤率使這個錯誤率快速下降？為歸一化因子。轉(zhuǎn)化為求的最小值了！此時我們用貪心算法求出的一個局部最小值對中的求導此時將固定令導數(shù)為零解出此時繪制關(guān)于的曲線圖從這幅圖上我們可以看出，當錯誤率越小或者越大只要不在中點處徘徊的時候快速收斂到0。越小：說明錯誤越小的分類器能快速識別出正例。越大: 說明錯誤越大的分類器也能快速識別出正例。既然最大，只要我把弱分類器取反，這樣錯誤率就是最小，這樣還是收斂到0。從以上的證明，我們知道只要是弱分類器的錯誤率都取最小，于是我們就能組合得到一個強分類器。接下來我們就找出一個弱分類器錯誤率很小。找個聯(lián)合起來就得到了強分類器！怎么找弱分類器？決策樹ID3，C4.5，C5.0ID3 生成樹用CIG類別屬性增益法C4.5 生成樹用Gain Ratio增益比率法修剪樹用(Rule post-pruning規(guī)那么修剪)C5.