Adaboost算法流程和證明

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

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

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

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

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