Adaboost 算法實(shí)例解析

1 Adaboost的原理

1.1 Adaboost基本介紹

AdaBoost，是英文"Adaptive Boosting"(自適應(yīng)增強(qiáng))的縮寫，由Yoav Freund和Robert Schapire在1995年提出。Adaboost是一種迭代算法，其核心思想是針對同一個訓(xùn)練集訓(xùn)練不同的分類器(弱分類器)，然后把這 Adaboost 些弱分類器集合起來，構(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算法的研究以及應(yīng)用大多集中于分類問題，同時近年也出現(xiàn)了一些在回歸問題上的應(yīng)用。就其應(yīng)用adaBoost系列主要解決了: 兩類問題、多類單標(biāo)簽問題、多類多標(biāo)簽問題、大類單標(biāo)簽問題，回歸問題。它用全部的訓(xùn)練樣本進(jìn)行學(xué)習(xí)。

1.2 Adaboost算法介紹

算法分析

該算法其實(shí)是一個簡單的弱分類算法提升過程，這個過程通過不斷的訓(xùn)練，可以提高對數(shù)據(jù)的分類能???Adaboost

力。整個過程如下所示：

1. 先通過對N個訓(xùn)練樣本的學(xué)習(xí)得到第一個弱分類器；

2. 將分錯的樣本和其他的新數(shù)據(jù)一起構(gòu)成一個新的N個的訓(xùn)練樣本，通過對這個樣本的學(xué)習(xí)得到第二個弱分類器 ；

3. 將1和2都分錯了的樣本加上其他的新樣本構(gòu)成另一個新的N個的訓(xùn)練樣本，通過對這個樣本的學(xué)習(xí)得到第三個弱分類器；

4. 最終經(jīng)過提升的強(qiáng)分類器 。即某個數(shù)據(jù)被分為哪一類要通過 ， ……的多數(shù)表決。

Adaboost的自適應(yīng)在于：前一個基本分類器分錯的樣本會得到加強(qiáng)，加權(quán)后的全體樣本再次被用來訓(xùn)練下一個基本分類器。同時，在每一輪中加入一個新的弱分類器，直到達(dá)到某個預(yù)定的足夠小的錯誤率或達(dá)到預(yù)先指定的最大迭代次數(shù)。

具體說來，整個Adaboost 迭代算法就3步：

初始化訓(xùn)練數(shù)據(jù)的權(quán)值分布。如果有N個樣本，則每一個訓(xùn)練樣本最開始時都被賦予相同的權(quán)重：1/N。

訓(xùn)練弱分類器。具體訓(xùn)練過程中，如果某個樣本點(diǎn)已經(jīng)被準(zhǔn)確地分類，那么在構(gòu)造下一個訓(xùn)練集中，它的權(quán)重就被降低；相反，如果某個樣本點(diǎn)沒有被準(zhǔn)確地分類，那么它的權(quán)重就得到提高。然后，權(quán)重更新過的樣本集被用于訓(xùn)練下一個分類器，整個訓(xùn)練過程如此迭代地進(jìn)行下去。

將各個訓(xùn)練得到的弱分類器組合成強(qiáng)分類器。各個弱分類器的訓(xùn)練過程結(jié)束后，加大分類誤差率小的弱分類器的權(quán)重，使其在最終的分類函數(shù)中起著較大的決定作用，而降低分類誤差率大的弱分類器的權(quán)重，使其在最終的分類函數(shù)中起著較小的決定作用。換言之，誤差率低的弱分類器在最終分類器中占的權(quán)重較大，否則較小。

Adaboost算法流程

對于這個算法需要介紹的是：

1. 算法開始前，需要將每個樣本的權(quán)重初始化為1/m,這樣一開始每個樣本都是等概率的分布，每個分類器都會公正對待。

2. 開始迭代后，需要計(jì)算每個弱分類器的分類錯誤的誤差，誤差等于各個分錯樣本的權(quán)重和，這里就體現(xiàn)了樣本權(quán)重的作用。如果一個分類器正確分類了一個權(quán)重大的樣本，那么這個分類器的誤差就會小，否則就會大。這樣就對分類錯誤的樣本更大的關(guān)注。

3. 獲取最優(yōu)分類器后，需要計(jì)算這個分類器的權(quán)重，然后再更新各個樣本的權(quán)重，然后再歸一化

4. 算法迭代的次數(shù)一般不超過弱分類器的個數(shù)，如果弱分類器的個數(shù)非常之多，那么可以權(quán)衡自己性價(jià)比來折中選擇。

5. 迭代完成后，最后的分類器是由迭代過程中選擇的弱分類器線性加權(quán)得到的。

1.3 Adaboost實(shí)例解析

例1. 下面，給定下列訓(xùn)練樣本，請用AdaBoost算法學(xué)習(xí)一個強(qiáng)分類器。

求解過程：初始化訓(xùn)練數(shù)據(jù)的權(quán)值分布，令每個權(quán)值W1i = 1/N = 0.1，其中，N = 10，i = 1,2, ..., 10，然后分別對于m = 1,2,3, ...等值進(jìn)行迭代。

拿到這10個數(shù)據(jù)的訓(xùn)練樣本后，根據(jù) X 和 Y 的對應(yīng)關(guān)系，要把這10個數(shù)據(jù)分為兩類，一類是“1”，一類是“-1”，根據(jù)數(shù)據(jù)的特點(diǎn)發(fā)現(xiàn)：“0 1 2”這3個數(shù)據(jù)對應(yīng)的類是“1”，“3 4 5”這3個數(shù)據(jù)對應(yīng)的類是“-1”，“6 7 8”這3個數(shù)據(jù)對應(yīng)的類是“1”，9是比較孤獨(dú)的，對應(yīng)類“-1”。拋開孤獨(dú)的9不講，“0 1 2”、“3 4 5”、“6 7 8”這是3類不同的數(shù)據(jù)，分別對應(yīng)的類是1、-1、1，直觀上推測可知，可以找到對應(yīng)的數(shù)據(jù)分界點(diǎn)，比如2.5、5.5、8.5 將那幾類數(shù)據(jù)分成兩類。當(dāng)然，這只是主觀臆測，下面實(shí)際計(jì)算下這個過程。

迭代過程1

對于m=1，在權(quán)值分布為D1(10個數(shù)據(jù)，每個數(shù)據(jù)的權(quán)值皆初始化為0.1)的訓(xùn)練數(shù)據(jù)上，經(jīng)過計(jì)算可得：

閾值v取2.5時誤差率為0.3(x < 2.5時取1，x > 2.5時取-1，則6 7 8分錯，誤差率為0.3)，

閾值v取5.5時誤差率最低為0.4(x < 5.5時取1，x > 5.5時取-1，則3 4 5 6 7 8皆分錯，誤差率0.6大于0.5，不可取。故令x > 5.5時取1，x < 5.5時取-1，則0 1 2 9分錯，誤差率為0.4)，

閾值v取8.5時誤差率為0.3(x < 8.5時取1，x > 8.5時取-1，則3 4 5分錯，誤差率為0.3)。

所以無論閾值v取2.5，還是8.5，總得分錯3個樣本，故可任取其中任意一個如2.5，弄成第一個基本分類器為：

上面說閾值v取2.5時則6 7 8分錯，所以誤差率為0.3，更加詳細(xì)的解釋是：因?yàn)闃颖炯?/p>

0 1 2對應(yīng)的類(Y)是1，因它們本身都小于2.5，所以被G1(x)分在了相應(yīng)的類“1”中，分對了。

3 4 5本身對應(yīng)的類(Y)是-1，因它們本身都大于2.5，所以被G1(x)分在了相應(yīng)的類“-1”中，分對了。

但6 7 8本身對應(yīng)類(Y)是1，卻因它們本身大于2.5而被G1(x)分在了類"-1"中，所以這3個樣本被分錯了。

9本身對應(yīng)的類(Y)是-1，因它本身大于2.5，所以被G1(x)分在了相應(yīng)的類“-1”中，分對了。

從而得到G1(x)在訓(xùn)練數(shù)據(jù)集上的誤差率(被G1(x)誤分類樣本“6 7 8”的權(quán)值之和)e1=P(G1(xi)≠yi) = 3*0.1 = 0.3。

然后根據(jù)誤差率e1計(jì)算G1的系數(shù)：

這個a1代表G1(x)在最終的分類函數(shù)中所占的權(quán)重，為0.4236。

接著更新訓(xùn)練數(shù)據(jù)的權(quán)值分布，用于下一輪迭代：

值得一提的是，由權(quán)值更新的公式可知，每個樣本的新權(quán)值是變大還是變小，取決于它是被分錯還是被分正確。

即如果某個樣本被分錯了，則yi * Gm(xi)為負(fù)，負(fù)負(fù)等正，結(jié)果使得整個式子變大(樣本權(quán)值變大)，否則變小。

第一輪迭代后，最后得到各個數(shù)據(jù)新的權(quán)值分布D2= (0.0715, 0.0715, 0.0715, 0.0715, 0.0715, ?0.0715,?0.1666, 0.1666, 0.1666, 0.0715)。由此可以看出，因?yàn)闃颖局惺菙?shù)據(jù)“6 7 8”被G1(x)分錯了，所以它們的權(quán)值由之前的0.1增大到0.1666，反之，其它數(shù)據(jù)皆被分正確，所以它們的權(quán)值皆由之前的0.1減小到0.0715。

分類函數(shù)f1(x)= a1*G1(x) = 0.4236G1(x)。

此時，得到的第一個基本分類器sign(f1(x))在訓(xùn)練數(shù)據(jù)集上有3個誤分類點(diǎn)(即6 7 8)。

從上述第一輪的整個迭代過程可以看出：被誤分類樣本的權(quán)值之和影響誤差率，誤差率影響基本分類器在最終分類器中所占的權(quán)重。

迭代過程2

對于m=2，在權(quán)值分布為D2= (0.0715, 0.0715, 0.0715, 0.0715, 0.0715, ?0.0715, 0.1666, 0.1666, 0.1666, 0.0715)的訓(xùn)練數(shù)據(jù)上，經(jīng)過計(jì)算可得：

閾值v取2.5時誤差率為0.1666*3(x < 2.5時取1，x > 2.5時取-1，則6 7 8分錯，誤差率為0.1666*3)，

閾值v取5.5時誤差率最低為0.0715*4(x > 5.5時取1，x < 5.5時取-1，則0 1 2 9分錯，誤差率為0.0715*3 +?0.0715)，

閾值v取8.5時誤差率為0.0715*3(x < 8.5時取1，x > 8.5時取-1，則3 4 5分錯，誤差率為0.0715*3)。

所以，閾值v取8.5時誤差率最低，故第二個基本分類器為：

面對的還是下述樣本：

很明顯，G2(x)把樣本“3 4 5”分錯了，根據(jù)D2可知它們的權(quán)值為0.0715, 0.0715, ?0.0715，所以G2(x)在訓(xùn)練數(shù)據(jù)集上的誤差率e2=P(G2(xi)≠yi) = 0.0715 * 3 = 0.2143。

計(jì)算G2的系數(shù)：

更新訓(xùn)練數(shù)據(jù)的權(quán)值分布：

D3?= (0.0455, 0.0455, 0.0455,?0.1667, 0.1667, ?0.01667, 0.1060, 0.1060, 0.1060, 0.0455)。被分錯的樣本“3 4 5”的權(quán)值變大，其它被分對的樣本的權(quán)值變小。

f2(x)=0.4236G1(x) + 0.6496G2(x)

此時，得到的第二個基本分類器sign(f2(x))在訓(xùn)練數(shù)據(jù)集上有3個誤分類點(diǎn)(即3 4 5)。

迭代過程3

對于m=3，在權(quán)值分布為D3= (0.0455, 0.0455, 0.0455, 0.1667, 0.1667, ?0.01667, 0.1060, 0.1060, 0.1060, 0.0455)的訓(xùn)練數(shù)據(jù)上，經(jīng)過計(jì)算可得：

閾值v取2.5時誤差率為0.1060*3(x < 2.5時取1，x > 2.5時取-1，則6 7 8分錯，誤差率為0.1060*3)，

閾值v取5.5時誤差率最低為0.0455*4(x > 5.5時取1，x < 5.5時取-1，則0 1 2 9分錯，誤差率為0.0455*3 +?0.0715)，

閾值v取8.5時誤差率為0.1667*3(x < 8.5時取1，x > 8.5時取-1，則3 4 5分錯，誤差率為0.1667*3)。

所以閾值v取5.5時誤差率最低，故第三個基本分類器為(下圖畫反了，待后續(xù)修正)：

依然還是原樣本：

此時，被誤分類的樣本是：0 1 2 9，這4個樣本所對應(yīng)的權(quán)值皆為0.0455，

所以G3(x)在訓(xùn)練數(shù)據(jù)集上的誤差率e3= P(G3(xi)≠yi) = 0.0455*4 = 0.1820。

計(jì)算G3的系數(shù)：

更新訓(xùn)練數(shù)據(jù)的權(quán)值分布：

D4= (0.125, 0.125, 0.125, 0.102, 0.102, ?0.102, 0.065, 0.065, 0.065,?0.125)。被分錯的樣本“0 1 2 9”的權(quán)值變大，其它被分對的樣本的權(quán)值變小。

f3(x)=0.4236G1(x) + 0.6496G2(x)+0.7514G3(x)

此時，得到的第三個基本分類器sign(f3(x))在訓(xùn)練數(shù)據(jù)集上有0個誤分類點(diǎn)。至此，整個訓(xùn)練過程結(jié)束。

G(x) = sign[f3(x)] = sign[ a1 * G1(x) + a2 * G2(x) + a3 * G3(x) ]，將上面計(jì)算得到的a1、a2、a3各值代入G(x)中，得到最終的分類器為：G(x) = sign[f3(x)] = sign[ 0.4236G1(x) + 0.6496G2(x)+0.7514G3(x) ]。

------- ---- ?用圖解深入淺出的解釋adaboost ---—————

也許你看了上面的介紹或許還是對adaboost算法云里霧里的，沒關(guān)系，百度大牛舉了一個很簡單的例子，你看了就會對這個算法整體上很清晰了。

下面我們舉一個簡單的例子來看看adaboost的實(shí)現(xiàn)過程：

圖中，“+”和“-”分別表示兩種類別，在這個過程中，我們使用水平或者垂直的直線作為分類器，來進(jìn)行分類。

第一步：

根據(jù)分類的正確率，得到一個新的樣本分布D2-，一個子分類器h1

其中劃圈的樣本表示被分錯的。在右邊的途中，比較大的“+”表示對該樣本做了加權(quán)。

也許你對上面的?1，ɑ1怎么算的也不是很理解。下面我們算一下，不要嫌我啰嗦，我最開始就是這樣思考的，只有自己把算法演算一遍，你才會真正的懂這個算法的核心，后面我會再次提到這個。

算法最開始給了一個均勻分布 D 。所以h1 里的每個點(diǎn)的值是0.1。ok，當(dāng)劃分后，有三個點(diǎn)劃分錯了，根據(jù)算法誤差表達(dá)式

得到 誤差為分錯了的三個點(diǎn)的值之和，所以?1=(0.1+0.1+0.1)=0.3，而ɑ1 根據(jù)表達(dá)式

的可以算出來為0.42. 然后就根據(jù)算法 把分錯的點(diǎn)權(quán)值變大。如此迭代，最終完成adaboost算法。

第二步：

根據(jù)分類的正確率，得到一個新的樣本分布D3，一個子分類器h2

第三步：

得到一個子分類器h3

整合所有子分類器：

因此可以得到整合的結(jié)果，從結(jié)果中看，及時簡單的分類器，組合起來也能獲得很好的分類效果，在例子中所有的。

五 Adaboost 疑惑和思考

到這里，也許你已經(jīng)對adaboost算法有了大致的理解。但是也許你會有個問題，為什么每次迭代都要把分錯的點(diǎn)的權(quán)值變大呢？這樣有什么好處呢？不這樣不行嗎? 這就是我當(dāng)時的想法，為什么呢？我看了好幾篇介紹adaboost 的博客，都沒有解答我的疑惑，也許大牛認(rèn)為太簡單了，不值一提，或者他們并沒有意識到這個問題而一筆帶過了。然后我仔細(xì)一想，也許提高錯誤點(diǎn)可以讓后面的分類器權(quán)值更高。然后看了adaboost算法，和我最初的想法很接近，但不全是。 注意到算法最后的表到式為

，這里面的a 表示的權(quán)值，是由

得到的。而a是關(guān)于誤差的表達(dá)式，到這里就可以得到比較清晰的答案了，所有的一切都指向了誤差。提高錯誤點(diǎn)的權(quán)值，當(dāng)下一次分類器再次分錯了這些點(diǎn)之后，會提高整體的錯誤率，這樣就導(dǎo)致 a 變的很小，最終導(dǎo)致這個分類器在整個混合分類器的權(quán)值變低。也就是說，這個算法讓優(yōu)秀的分類器占整體的權(quán)值更高，而挫的分類器權(quán)值更低。這個就很符合常理了。到此，我認(rèn)為對adaboost已經(jīng)有了一個透徹的理解了。

六 總結(jié)

最后，我們可以總結(jié)下adaboost算法的一些實(shí)際可以使用的場景：

1)用于二分類或多分類的應(yīng)用場景

2)用于做分類任務(wù)的baseline

無腦化，簡單，不會overfitting，不用調(diào)分類器

3)用于特征選擇(feature selection)

4)Boosting框架用于對badcase的修正

只需要增加新的分類器，不需要變動原有分類器

由于adaboost算法是一種實(shí)現(xiàn)簡單，應(yīng)用也很簡單的算法。Adaboost算法通過組合弱分類器而得到強(qiáng)分類器，同時具有分類錯誤率上界隨著訓(xùn)練增加而穩(wěn)定下降，不會過擬合等的性質(zhì)，應(yīng)該說是一種很適合于在各種分類場景下應(yīng)用的算法。

這個是我看過對adaboost寫的比較容易懂的文章了，等有空的時候我自己運(yùn)行下adaboost的python代碼，到時候再把這篇文章修改下。

對了，如果看到我的博客后，有意愿和我技術(shù)溝通的，可以加我QQ 340217138 討論。

參考：

http://blog.csdn.net/tiandijun/article/details/48036025

http://blog.csdn.net/haidao2009/article/details/7514787

總結(jié)

以上是生活随笔為你收集整理的adaboost算法java_Adaboost 算法实例解析的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。