Adaboost算法流程和證明

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

2、來，構(gòu)成一個(gè)更強(qiáng)的最終分類器(強(qiáng)分類器)。其算法本身是通過改變數(shù)據(jù)分布來實(shí)現(xiàn)的，它根據(jù)每次訓(xùn)練集之中每個(gè)樣本的分類是否正確，以及上次的總體分類的準(zhǔn)確率，來確定每個(gè)樣本的權(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)整每個(gè)樣本對應(yīng)的權(quán)重來實(shí)現(xiàn)的。開始時(shí)，每個(gè)樣本對應(yīng)的權(quán)重是相同的，即其中 為樣本個(gè)數(shù)，在此樣本分布下訓(xùn)練出一弱分類器。對于分類錯(cuò)誤的樣本，加大其對應(yīng)的權(quán)重；而對于分類正確的樣本，降低

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

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

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