基于弱分類器調整的多分類Adaboost算法

楊新武　　馬　壯　　袁　順(北京工業大學計算機學院　北京　100124)

?

基于弱分類器調整的多分類Adaboost算法

楊新武*馬壯袁順
(北京工業大學計算機學院北京100124)

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

關鍵詞：多類分類器；多類指數損失函數的逐步添加模型；Adaboost.M1

1　引言

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

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

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

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

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

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

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

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

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

2　SAMME

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

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

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

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

3　SAMME.R

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

圖1　Adaboost.M1分類圖

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

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

圖2　SAMME分類圖

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

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

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

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

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

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

(5)置

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

步驟3最終強分類器為

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

4　SAMME.R算法數學分析

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

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

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

由于訓練集相互間是獨立的，因此可認為Zt是獨立的，于是

由大數定理，?ε有

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

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

由于訓練集相互間是獨立的，因此可認為Zt是獨立的，且，于是

由大數定理，?ε有

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

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

定義隨機變量序列Zt：

則Zt是一個均值為，方差為的隨機變量。記μ=。由于訓練集相互間是獨立的，因此可認為Zt是獨立的，于是

由大數定理，?ε有

5　實驗結果

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

數據集的基本情況如表1所示。

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

表1　測試數據集信息

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

由表可以看出，在Segmentation，Balance-scale，Ecoli，Wine，Yeast數據庫上，SAMME.R算法得出的結果都要優于SAMME算法和Adaboost.M1算法，只有在Vowel數據集上的表現不如Adaboost.M1算法，但SAMME.R的效果，仍然要比SAMME算法要好。

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

表2　測試錯誤率（%）

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

對比實驗表明，本文提出的SAMME.R算法的結果要好于SAMME算法，并達到了不弱于Adaboost.M1算法的效果。不但使其更容易應用到實際應用中，同時提高了其分類的準確性。通過實驗發現在訓練集較小的情況下，SAMME.R算法對SAMME算法有較明顯的改進。

6　結束語

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

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

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

參考文獻

[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].自動化學報，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].計算機科學，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]胡金海，駱廣琦，李應紅，等.一種基于指數損失函數的多類分類 AdaBoost 算法及其應用[J].航空學報，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]付忠良.關于 AdaBoost 有效性的分析[J].計算機研究與發展，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；網絡出版：2015-11-18

DOI:10.11999/JEIT150544

中圖分類號：TP391.4

文獻標識碼：A

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