基于弱分類器調(diào)整的多分類Adaboost算法

楊新武　　馬　壯　　袁　順(北京工業(yè)大學(xué)計算機(jī)學(xué)院　北京　100124)

?

基于弱分類器調(diào)整的多分類Adaboost算法

楊新武*馬壯袁順
(北京工業(yè)大學(xué)計算機(jī)學(xué)院北京100124)

摘要：Adaboost.M1算法要求每個弱分類器的正確率大于1/2，但在多分類問題中尋找這樣的弱分類器較為困難。有學(xué)者提出了多類指數(shù)損失函數(shù)的逐步添加模型(SAMME)，把弱分類器的正確率要求降低到大于1/k(k為類別數(shù))，降低了尋找弱分類器的難度。由于SAMME算法無法保證弱分類器的有效性，從而并不能保證最終強(qiáng)分類器正確率的提升。為此，該文通過圖示法及數(shù)學(xué)方法分析了多分類Adaboost算法的原理，進(jìn)而提出一種新的既可以降低弱分類器的要求，又可以確保弱分類器有效性的多分類方法。在UCI數(shù)據(jù)集上的對比實驗表明，該文提出的算法的結(jié)果要好于SAMME算法，并達(dá)到了不弱于Adaboost.M1算法的效果。

關(guān)鍵詞：多類分類器；多類指數(shù)損失函數(shù)的逐步添加模型；Adaboost.M1

1　引言

Adaboost算法的思想起源于VALIANT提出的PAC(Probably Approximately Correct)學(xué)習(xí)模型[1]。SCHAPIRE提出了Boosting[2]算法，Boosting[3-5]算法是一種通過結(jié)合多個弱分類器提高最終分類準(zhǔn)確率的方法。基于Boosting算法，1995年，F(xiàn)REUND提出的Boost-by-majority算法[3]，在某種意義上說是最佳的Boosting算法，而1997年FREUND和SCHAPIRE提出的Adaboost算法[6]是更面向于實際應(yīng)用的方法。Boosting方法一般只適用于二分類問題，在實際應(yīng)用中，大多數(shù)的應(yīng)用場景會多于兩個類別，像檢測[7]，人臉識別，物體和動作檢測[8]等。

簡單地把Boosting算法從兩類擴(kuò)展到多類存在許多問題，比如在兩類問題中，對弱分類器的要求只要比隨機(jī)猜測好就能被接受，也就是正確率大于1/2。而在多分類問題中，尤其是在類別數(shù)較大的情況下，隨機(jī)猜測正確率較低，很難滿足正確率大于1/2的要求。像決策樹這種簡單的弱分類器就很不容易滿足對弱分類器的要求。1996年FREUND和SCHAPIRE也通過結(jié)合這些弱分類器，提高了最終的分類準(zhǔn)確率[9]。文獻(xiàn)[10]是ALLWEIN等人在2000年提出的，其把多分類問題化簡為多個二分類問題也是現(xiàn)在較為常見的思路[11]。

基于AdaBoost的多類別分類方法主要有AdaBoost.M1[9]，AdaBoost.M2[9]和AdaBoost.MH[12]。1996年FREUND和SCHAPIRE提出了Adaboost.M1[9]算法，它比較直接地把Adaboost算法泛化到多類問題上，但其對弱分類器的要求較高，要求弱分類器正確率大于1/2[13]。但在多分類問題中，由于隨機(jī)猜測的正確率只有1/k，與兩類AdaBoost方法相比，多分類AdaBoost.M1算法難以找到正確率大于1/2的弱分類器，可能導(dǎo)致在實際應(yīng)用中得到的弱分類器個數(shù)不足，無法保證得到足夠好的強(qiáng)分類器。為此，學(xué)者針對這一問題提出了許多改進(jìn)算法，通常把多類問題化簡為多個二分類問題，再進(jìn)行分類決策。AdaBoost.M2，AdaBoost.MH等算法多采用這種思想解決多類問題[13]。

AdaBoost.M2算法在AdaBoost.M1的基礎(chǔ)上，采用偽損失代替弱分類器的正確率來衡量弱分類器。其對弱分類器的分類精度要求稍有降低，只要偽損失稍比隨機(jī)猜測好就可以。并且，由于使用偽損失，使每一次迭代的弱分類器不僅注重錯分樣本，同時還關(guān)注到了難以辨別的標(biāo)簽類上。但是，偽損失函數(shù)要比錯分率計算復(fù)雜得多，因此AdaBoost.M2算法比較復(fù)雜，計算成本和時間也相應(yīng)增加[9]。

1999年SCHAPIRE和SINGER提出AdaBoost.MH[12]算法。AdaBoost.MH把每個樣本的分類，轉(zhuǎn)化為k個1和0的標(biāo)簽，是一種直接將k類問題轉(zhuǎn)化為k個兩類問題的算法。由于轉(zhuǎn)化為兩類問題，這樣弱分類器的精度要求可以較容易地得到滿足，多類分類效果改善明顯[12]。但該算法的主要不足之處就是計算過程繁瑣，計算量大，尤其在類別數(shù)k較大時[14]。

2009年ZHU等人[15]提出了一個新的從兩類問題擴(kuò)展到多類問題的方法SAMME(Stagewise Additive Modeling using a Multi-class Exponential loss function)。它將Adaboost算法直接擴(kuò)展到了多類問題上。SAMME算法把弱分類器正確率的要求從1/2降低到1/k，也就是說在多分類問題中，弱分類器的性能只要比隨機(jī)猜測好就可以被接受。因此，SAMME算法從概念上來說是簡單的、容易實現(xiàn)的，且能找到足夠多的弱分類器。但SAMME算法對于弱分類器的要求不足，導(dǎo)致算法并不能夠保證弱分類器能增強(qiáng)最終強(qiáng)分類器的準(zhǔn)確率。

我們在研究中也發(fā)現(xiàn)，在很多UCI數(shù)據(jù)庫上的多分類問題中，SAMME算法的效果并不如Adaboost.M1算法好。究其原因，在于SAMME算法雖然通過放寬弱分類器錯誤率的限制，但其沒有關(guān)注到弱分類器的質(zhì)量，不能保證每次被弱分類器正確分類的訓(xùn)練樣本權(quán)值一定大于其錯分到其它任一類別的訓(xùn)練樣本權(quán)值，從而不能確保最終強(qiáng)分類器正確率的提升。為此，我們分析了多分類Adaboost算法的原理。通過原理分析，使我們可以使用更簡單的弱分類器達(dá)到比較好的效果。針對Adaboost.M1算法，弱分類器正確率要求過高的問題，SAMME算法并沒有按照把多類問題化簡為多個二分類問題的思路，而是直接對AdaBoost算法進(jìn)行泛化，不將多類問題轉(zhuǎn)化為多個兩類問題，直接求解多類分類問題，可大大減小計算量。本文提出的SAMME.R(Stagewise Additive Modeling using a Multi-class Exponential loss function with Resample)算法是針對SAMME算法的不足，提出的改進(jìn)算法。其解決多分類問題的思路與AdaBoost.M1算法，SAMME算法較為相似，與AdaBoost.M2算法及AdaBoost.MH等算法在解決多分類問題上的思路不同。在原理分析及實驗時，本文也將針對AdaBoost.M1算法及SAMME算法進(jìn)行分析。

本文中，我們首先分析了多分類Adaboost算法的原理，在SAMME算法的基礎(chǔ)上提出了SAMME.R算法，該方法既可以把對弱分類器正確率的要求僅為1/k，從而保證更容易獲得弱分類器，又通過重采樣保證了弱分類器的質(zhì)量，從而提高強(qiáng)分類器效果。本文對SAMME.R算法的有效性進(jìn)行了證明。在基準(zhǔn)UCI數(shù)據(jù)集[16]上的對比實驗表明，本文提出的SAMME.R算法的結(jié)果要好于SAMME算法，并取得了不弱于Adaboost.M1算法的效果。

本文第2節(jié)首先對SAMME算法及其與Adaboost.M1算法的區(qū)別進(jìn)行了簡要介紹；在第3節(jié)中，分析了Adaboost.M1及SAMME算法的原理，并詳細(xì)介紹了本文提出的SAMME.R算法；第4節(jié)中，利用數(shù)學(xué)對SAMME.R算法進(jìn)行了有效性分析；對比實驗的結(jié)果放在了第5節(jié)；最后一節(jié)是結(jié)論。

2　SAMME

對于多類問題，由于隨機(jī)猜測的正確率只有1/k，所以通常難以找到錯誤率小于1/2的弱分類器，以致無法得到足夠數(shù)量的弱分類器，從而不能集成得到足夠好的強(qiáng)分類器。SAMME[15]算法針對此問題，對Adaboost算法的多類擴(kuò)展做出了修改。SAMME算法通過改變權(quán)值分配策略at的計算方法，令，從而有別于Adab o ost.M1算法中的權(quán)值分配策略at=。SAMME算法與AdaBoost.M1算法看上去比較相似，其不同點在于at的計算公式中多加了ln(k -1)項。當(dāng)k為2時(也就是兩類問題)，其權(quán)重分配策略與AdaBoost算法相同。在k(k＞2)類別分類問題中，由于加上ln(k -1)項，SAMME算法中的弱分類器正確率不再要求大于1/2，而是大于1/k即可，這使得SAMME算法在解決多分類問題時的適用范圍更廣泛。

文獻(xiàn)[15]在文獻(xiàn)[17]中提出的統(tǒng)計學(xué)觀點的基礎(chǔ)上，從理論上對ln(k -1)添加項的合理性進(jìn)行了統(tǒng)計分析證明。首先證明SAMME算法是符合向前梯度添加模型的，然后證明符合向前梯度添加模型的算法可以逼近最小化指數(shù)損失函數(shù)，而最小化指數(shù)損失函數(shù)可使分類決策函數(shù)滿足貝葉斯分類規(guī)則，從而證明SAMME算法是滿足貝葉斯分類規(guī)則的最優(yōu)分類器。

但在我們的研究中發(fā)現(xiàn)，在很多基準(zhǔn)UCI數(shù)據(jù)庫上的多分類問題中，SAMME算法的效果并不如Adaboost.M1算法。在AdaBoost.M1算法中，要求弱分類器的正確率要大于1/2，也就是分類正確的樣本的概率，大于分到其他各類樣本的概率和，使得其分類正確的概率，一定大于分到其他各類的概率，根據(jù)大數(shù)定理，隨著弱分類器個數(shù)的增多，最終強(qiáng)分類器的正確率趨近于1。而在SAMME算法中，把對弱分類器正確率的要求從大于1/2，降低到大于1/k，降低了尋找弱分類器的難度。但由于其弱分類器的正確率僅要求大于1/k，并不能保證每類訓(xùn)練樣本分到本類的概率一定大于錯分到其他各類的概率。若存在每類訓(xùn)練樣本分到某一錯誤類的概率大于其分到本類的概率時，經(jīng)過集成投票后，最終強(qiáng)分類器的對該類訓(xùn)練樣本的分類會偏向于錯分類別中概率較大的那一類，導(dǎo)致無法確保最終強(qiáng)分類器正確率的提升。

如果針對多分類問題，既可以把對弱分類器正確率的要求降低到大于1/k，又可以通過限制生成上述的低質(zhì)弱分類器，就能確保得到足夠強(qiáng)的強(qiáng)分類器。

3　SAMME.R

為了清楚地了解SAMME算法的不足，我們借助文獻(xiàn)[18]的分析對此進(jìn)行說明。

圖1　Adaboost.M1分類圖

在Adaboost.M1算法中，如圖1所示，在弱分類器訓(xùn)練中，我們把分類正確的樣本標(biāo)注為白色，分類錯誤的樣本標(biāo)為灰色。則每行的白色部分表示該弱分類器本次迭代中正確分類的部分，當(dāng)每行白色部分比例大于一半時，多次迭代訓(xùn)練得到多個弱分類器后，由于每次分類的正確率大于1/2，圖中白色部分比灰色部分多，對于每個樣本來說，必然會有很多樣本白色部分所占比例大于一半。如果不同弱分類器正確分類的樣本獨立，且分布均勻，則隨著迭代次數(shù)的增加，即訓(xùn)練樣本中越來越多的樣本被超過一半的弱分類器分類正確。無窮次迭代后，分類正確的標(biāo)簽一定比分到其他類的標(biāo)簽的數(shù)量多，保證最終的強(qiáng)分類器正確。

在SAMME算法中，只要求正確率大于1/k。如圖2所示，同之前圖示相同，每一行的白色部分代表弱分類器對訓(xùn)練集分類正確的樣本。該弱分類器可以滿足SAMME算法正確率大于1/k的條件，但對于某個屬于n類的樣本，弱分類器將其分至某一不為n類的概率大于其分到n類的概率的情況經(jīng)常出現(xiàn)，無窮次迭代后，強(qiáng)分類器最終會導(dǎo)致分類結(jié)果錯誤。

圖2　SAMME分類圖

與Adaboost.M1算法不同，SAMME算法中，由于每次分類的正確率為，而不是，T次訓(xùn)練得到T個弱分類器后，不能保證樣本分類正確的標(biāo)簽的權(quán)值一定大于分到其他任意一類的標(biāo)簽的權(quán)值，以至于不能保證最終分類效果的提升。而在Adaboost.M1算法中，弱分類器的正確率為，則分到正確類的樣本權(quán)值一定大于分到其他各類的樣本的權(quán)值之和，從而其分類正確樣本權(quán)值一定大于分到其他任意一類的權(quán)值，保證了當(dāng)T趨近于無窮時，最終分類結(jié)果的正確率趨近于1。

要保證在最后的綜合投票中分類正確的樣本所占的數(shù)量是最多的，僅要求弱分類器的正確率大于1/k是不夠的，需要添加一定的限制條件。為此，本文提出在訓(xùn)練弱分類器時，判斷該弱分類器的結(jié)果，在所有同屬一類的樣本的分類中，正確分類的樣本的權(quán)值和是否比分到其他任意一類的權(quán)值和大。如果滿足該條件則繼續(xù)進(jìn)行權(quán)值調(diào)整和下一次迭代。如果不滿足，則可能是由于訓(xùn)練出的弱分類器不夠好，可以在權(quán)值不變的情況下重新訓(xùn)練弱分類器，然后再次判斷新的弱分類器是否滿足上邊所說的條件，如果滿足進(jìn)入下一次調(diào)整，不滿足則重新訓(xùn)練弱分類器。經(jīng)過此條件的限制，當(dāng)T趨近于無窮時，分類正確的標(biāo)簽一定比分到其他各類的標(biāo)簽的數(shù)量多，最終分類器的錯誤率趨近于0。

在此基礎(chǔ)上，本文提出了SAMME.R算法，該算法流程如下：

(a)循環(huán)計算各類中，分到各類樣本的權(quán)值和：

(b)判斷各類中分類正確的樣本權(quán)值和是否大于分到其他各類的樣本的權(quán)值和。若滿足，則進(jìn)行下一次循環(huán)。若不滿足，則返回步驟2重新開始計算。

(4)計算ht的偽錯誤率：

(5)置

(6)計算新的權(quán)重向量：

步驟3最終強(qiáng)分類器為

本文對SAMME算法的改進(jìn)，并未影響其滿足的向前梯度添加模型。因此，SAMME.R算法仍然滿足貝葉斯最佳分類規(guī)則。

4　SAMME.R算法數(shù)學(xué)分析

上文中以一個簡單的例子介紹了本文提出的SAMME.R算法，在本節(jié)中，將針對多分類問題，對Adaboost.M1，SAMME，SAMME.R算法的有效性進(jìn)行數(shù)學(xué)分析。

Adaboost.M1算法中，在k分類問題中，若采用簡單投票法構(gòu)造強(qiáng)分類器，即H(x)=。則對任意訓(xùn)練集St，輸出一個最大錯誤率為的分類器，相互獨立選取不同的St得到不同的。定義隨機(jī)變量序列Zt：

則Zt是一個均值為，方差為的隨機(jī)變量。記

由于訓(xùn)練集相互間是獨立的，因此可認(rèn)為Zt是獨立的，于是

由大數(shù)定理，?ε有

根據(jù)Zt的定義，當(dāng)T→∞，對任意實例x，滿足比的個數(shù)平均多μ個，采取簡單投票法，，對x的分類錯誤率將趨于零。

SAMME算法中，在k分類問題中，若采用簡單投票法構(gòu)造強(qiáng)分類器，即H(x)=。則對任意訓(xùn)練集St，輸出一個最大錯誤率為的分類器，，相互獨立選取不同的St得到不同的。定義隨機(jī)變量序列Zt，同式(6)。則Zt是一個均值為，方差為的隨機(jī)變量。記

由于訓(xùn)練集相互間是獨立的，因此可認(rèn)為Zt是獨立的，且，于是

由大數(shù)定理，?ε有

當(dāng)k＞2時，μ不一定大于0，根據(jù)Zt的定義，當(dāng)T→∞，對任意實例x，滿足的個數(shù)，不一定滿足的個數(shù)多，采取簡單投票法，，對x的分類錯誤率可能不會趨于零。

因此，本文提出了SAMME.R算法，在k分類問題中，若采用簡單投票法構(gòu)造強(qiáng)分類器，即。則對任意訓(xùn)練集St，輸出一個最大錯誤率為的分類器，分類到k類的最小概率分別為，且。SAMME.R算法中要求，若，則。設(shè)m的概率為p，，則的概率為。

定義隨機(jī)變量序列Zt：

則Zt是一個均值為，方差為的隨機(jī)變量。記μ=。由于訓(xùn)練集相互間是獨立的，因此可認(rèn)為Zt是獨立的，于是

由大數(shù)定理，?ε有

5　實驗結(jié)果

在本節(jié)中，我們在基準(zhǔn)UCI數(shù)據(jù)集上[16]，對SAMME.R，SAMME以及AdaboostM1算法進(jìn)行比較測試。我們在Segmentation，Vowel，Balance-scale，Ecoli，Wine，Yeast 6個數(shù)據(jù)集上進(jìn)行了測試。其中，Segmentation數(shù)據(jù)集和Vowel數(shù)據(jù)集預(yù)先指定了訓(xùn)練集和測試集的內(nèi)容。其他的數(shù)據(jù)集，我們隨機(jī)挑選一半的樣本作為訓(xùn)練集，其余部分作為測試集。

數(shù)據(jù)集的基本情況如表1所示。

本文用最近鄰的方法作為弱分類器。在上述數(shù)據(jù)集上進(jìn)行的實驗中，實驗數(shù)據(jù)為5次試驗后的平均值。

表1　測試數(shù)據(jù)集信息

分別計算了SAMME.R算法、SAMME算法以及Adaboost.M1算法，在200次迭代、400次迭代和600次迭代時的分類識別的錯誤率，實驗結(jié)果如表2所示。

由表可以看出，在Segmentation，Balance-scale，Ecoli，Wine，Yeast數(shù)據(jù)庫上，SAMME.R算法得出的結(jié)果都要優(yōu)于SAMME算法和Adaboost.M1算法，只有在Vowel數(shù)據(jù)集上的表現(xiàn)不如Adaboost.M1算法，但SAMME.R的效果，仍然要比SAMME算法要好。

在實驗結(jié)果中，我們發(fā)現(xiàn)Vowel數(shù)據(jù)集上SAMME.R算法的分類效果不如AdaBoost.M1算法。究其原因，由于SAMME算法和SAMME.R算法，為了能夠更容易地找到弱分類器，降低了弱分類器對錯誤率的要求，權(quán)值調(diào)整at也因此加大。在下一次的迭代分類中，與AdaBoost.M1算法相比，SAMME算法與SAMME.R算法會更加偏向于本次分類錯誤的樣本。導(dǎo)致下一次迭代中，弱分類器的分類正確率略有下降，造成弱分類器性能的下降。在弱學(xué)習(xí)算法中，弱分類器的質(zhì)量會影響強(qiáng)分類器的分類效果，因此，SAMME.R算法對弱分類器性能弱化的要求，可使最終的強(qiáng)分類器性能提升，但個別情況下不如AdaBoost.M1算法的結(jié)果。Vowel數(shù)據(jù)集在所測試的所有數(shù)據(jù)集中，其類別數(shù)k最多，造成1/k較小，其對弱分類器正確率的要求也最低。而AdaBoost.M1算法，在任何數(shù)據(jù)集上都要求弱分類器正確率大于1/2。因此，在Vowel數(shù)據(jù)集上，SAMME.R算法的弱分類器性能有更大的可能性與AdaBoost.M1算法相差較大，造成SAMME.R算法對弱分類器性能弱化的要求，雖然保證了強(qiáng)分類器效果的提升，但最終的分類效果仍不如AdaBoost.M1算法好。

表2　測試錯誤率（%）

除在這些數(shù)據(jù)集上的測試外，我們還在Letter，Nursery，Pendigits，Satimage這幾個數(shù)據(jù)集上進(jìn)行了實驗，由于實驗過程中，未出現(xiàn)SAMME.R中需要重新訓(xùn)練弱分類器的情況，所以在這4個數(shù)據(jù)集上SAMME.R算法相當(dāng)于SAMME算法。

對比實驗表明，本文提出的SAMME.R算法的結(jié)果要好于SAMME算法，并達(dá)到了不弱于Adaboost.M1算法的效果。不但使其更容易應(yīng)用到實際應(yīng)用中，同時提高了其分類的準(zhǔn)確性。通過實驗發(fā)現(xiàn)在訓(xùn)練集較小的情況下，SAMME.R算法對SAMME算法有較明顯的改進(jìn)。

6　結(jié)束語

本文對多分類Adaboost算法的原理進(jìn)行了分析，在此基礎(chǔ)上針對SAMME算法的不足提出了改進(jìn)的SAMME.R算法。SAMME.R算法要求弱分類器的性能只要比隨機(jī)猜測好就可以被接受，降低了尋找弱分類器的難度。SAMME.R算法通過增加對弱分類器的限制，從而保證了弱分類器的有效性，確保強(qiáng)分類器的分類正確率得到提升。本文算法對弱分類器的要求，會比SAMME嚴(yán)格一點，但顯然低于Adaboost.M1算法。與Adaboost.M1算法和SAMME算法相比，SAMME.R算法在絕大多數(shù)情況下有更好的分類效果。

本文只是從一個比較直觀的角度分析了多分類Adaboost算法的原理。最近也有很多學(xué)者從不同的角度提出了新的多分類Boosting算法，有多分類DeepBoost[19]，其從兩類的DeepBoost[20]算法泛化而來的。DMCBoost[21]算法通過擴(kuò)展兩類的Direct Boost[22]算法而得出，也是一種直接的多類Boosting算法，其使用多類決策樹作為基分類器[23]。PIboost[24]算法，把多分類問題轉(zhuǎn)化為多個二分類問題，并且關(guān)注到了類的不對稱分布的問題。

本文提出的算法也存在一定的不足，在SAMME.R算法重新訓(xùn)練弱分類器時，容易出現(xiàn)經(jīng)過多次訓(xùn)練仍無法找到滿足條件的弱分類器，實驗中需要設(shè)置重新訓(xùn)練弱分類器的上限次數(shù)，使程序避免陷入死循環(huán)中無法跳出。在今后的工作中，需要找到一種更好的辦法，來解決這個問題。

參考文獻(xiàn)

[1]VALIANT L G.A theory of the learnable[J].Communications of the ACM，1984，27(11):1134-1142.doi:10.1145/800057.808710.

[2]SCHAPIRE R E.The strength of weak learnability[J].Machine Learning，1990，5(2):197-227.doi:10.1007/ BF00116037.

[3]FREUND Y.Boosting a weak learning algorithm by majority[J].Information and Computation，1995，121(2):256-285.doi:10.1006/inco.1995.1136.

[4]SCHAPIRE R E.A brief introduction to boosting[C].International Joint Conference on Artificial Intelligence，Sweden，1999:1401-1406.

[5]曹瑩，苗啟廣，劉家辰，等.AdaBoost 算法研究進(jìn)展與展望[J].自動化學(xué)報，2013，39(6):745-758.doi:10.3724/SP.J.1004.2013.00745.CAO Ying，MIAO Qiguang，LIU Jiachen，et al.Advance and prospects of AdaBoost algorithm[J].Acta Automatica Sinica，2013，39(6):745-758.doi:10.3724/SP.J.1004.2013.00745.

[6]FREUND Y and SCHAPIRE R E.A desicion-theoretic generalization of on-line learning and an application to boosting[J].Lecture Notes in Computer Science，1970，55(1):23-37.doi:10.1007/3-540-59119-2_166.

[7]NEGRI P，GOUSSIES N，and LOTITO P.Detecting pedestrians on a movement feature space[J].Pattern Recognition，2014，47(1):56-71.doi:10.1016/j.patcog.2013.05.020.

[8]LIU L，SHAO L，and ROCKETT P.Boosted key-frame selection and correlated pyramidal motion-feature representation for human action recognition[J].Pattern Recognition，2013，46(7):1810-1818.doi:10.1016/j.patcog.2012.10.004.

[9]FREUND Y and SCHAPIRE R E.Experiments with a new boosting algorithm[C].Proceedings of the Thirteenth International Conference on Machine Learning，Italy，1996:148-156.

[10]ALLWEIN E L，SCHAPIRE R E，and SINGER Y.Reducing multiclass to binary:a unifying approach for margin classifiers[J].The Journal of Machine Learning Research，2001，1(2):113-141.doi:10.1162/15324430152733133.

[11]MUKHERJEE I and SCHAPIRE R E.A theory of multiclass boosting[J].The Journal of Machine Learning Research，2013，14(1):437-497.

[12]SCHAPIRE R E and SINGER Y.Improved boosting algorithms using confidence-rated predictions[J].Machine Learning，1999，37(3):297-336.doi:10.1145/279943.279960.

[13]涂承勝，刁力力，魯明羽，等.Boosting 家族 AdaBoost 系列代表算法[J].計算機(jī)科學(xué)，2003，30(3):30-34.TU Chengsheng，DIAO Lili，LU Mingyu，et al.The typical algorithm of AdaBoost series in Boosting family[J].Computer Science，2003，30(3):30-34.

[14]胡金海，駱廣琦，李應(yīng)紅，等.一種基于指數(shù)損失函數(shù)的多類分類 AdaBoost 算法及其應(yīng)用[J].航空學(xué)報，2008，29(4):811-816.HU Jinhai，LUO Guangqi，LI Yinghong，et al.An AdaBoost algorithm for multi-class classification based on exponential loss function and its application[J].Acta Aeronautica et Astronautica Sinica，2008，29(4):811-816.

[15]ZHU J，ZOU H，ROSSET S，et al.Multi-class adaboost[J].Statistics and Its Interface，2009，2(3):349-360.

[16]BLAKE C L and MERZ C J.UCI Repository of machine learning databases[OL].http://www.ics.uci.edu/.1998.

[17]FRIEDMAN J，HASTIE T，and TIBSHIRANI R.Additive logistic regression:a statistical view of boosting(with discussion and a rejoinder by the authors)[J].The Annals of Statistics，2000，28(2):337-407.doi:10.1214/aos/1016120463.

[18]付忠良.關(guān)于 AdaBoost 有效性的分析[J].計算機(jī)研究與發(fā)展，2008，45(10):1747-1755.FU Zhongliang.Effectiveness analysis of AdaBoost[J].Journal of Computer Research and Development，2008，45(10):1747-1755.

[19]KUZNETSOV V，MOHRI M，and SYED U.Multi-class deep boosting[C].Advances in Neural Information Processing Systems，Canada，2014:2501-2509.

[20]CORTES C，MOHRI M，and SYED U.Deep boosting[C].Proceedings of the 31st International Conference on Machine Learning(ICML-14)，Beijing，2014:1179-1187.

[21]ZHAI S，XIA T，and WANG S.A multi-class boosting method with direct optimization[C].Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，New York，2014:273-282.

[22]ZHAI S，XIA T，TAN M，et al.Direct 0-1 loss minimization and margin maximization with boosting[C].Advances in Neural Information Processing Systems，Nevada，2013:872-880.

[23]DOLLAR P.Quickly boosting decision trees-pruning underachieving features early[C].JMLR Workshop ＆Conference Proceedings，2013，28:594-602.

[24]FERNANDEZ B A and BAUMELA L.Multi-class boosting with asymmetric binary weak-learners[J].Pattern Recognition，2014，47(5):2080-2090.doi:10.1016/j.patcog.2013.11.024.

楊新武：男，1971年生，副教授，研究方向為模式識別、遺傳算法.

馬壯：男，1990年生，碩士生，研究方向為模式識別.

袁順：男，1989年生，碩士生，研究方向為模式識別.

Multi-class Adaboost Algorithm Based on the Adjusted Weak Classifier

YANG XinwuMA ZhuangYUAN Shun
(School of Computer Science，Beijing University of Technology，Beijing 100124，China)

Abstract:Adaboost.M1 requires each weak classifier's accuracy rate more than 1/2.But it is difficult to find a weak classifier which accuracy rate more than 1/2 in a multiple classification issues.Some scholars put forward the Stagewise Additive Modeling using a Multi-class Exponential loss function(SAMME)algorithm，it reduces the weak classifier accuracy requirements，from more than 1/2 to more than 1/k(k is the category number).SAMME algorithm reduces the difficulty to find weak classifier.But，due to the SAMME algorithm is no guarantee that the effectiveness of the weak classifier，which does not ensure that the final classifier improves classification accuracy.This paper analyzes the multi-class Adaboost algorithm by graphic method and math method，and then a new kind of multi-class classification method is proposed which not only reduces the weak classifier accuracy requirements，but also ensures the effectiveness of the weak classifier.In the benchmark experiments on UCI data sets show that the proposed algorithm are better than the SAMME，and achieves the effect of Adaboost.M1.

Key words:Multi-class classification; Stagewise Additive Modeling using a Multi-class Exponential loss function(SAMME); Adaboost.M1

*通信作者：楊新武yang_xinwu@bjut.edu.cn

收稿日期：2015-05-11；改回日期：2015-10-08；網(wǎng)絡(luò)出版：2015-11-18

DOI:10.11999/JEIT150544

中圖分類號：TP391.4

文獻(xiàn)標(biāo)識碼：A

文章編號：1009-5896(2016)02-0373-08