多分類研究中的boosting算法*

哈爾濱醫(yī)科大學(xué)公共衛(wèi)生學(xué)院衛(wèi)生統(tǒng)計學(xué)教研室(150081) 張圓圓 侯 艷 李 康

boosting算法起源于PAC (probably approximately correct)學(xué)習(xí)模型，由Schapire在1990年首次提出，是一種基于一系列基礎(chǔ)分類器的組合分類模型算法，基礎(chǔ)分類器可以選擇任意一種弱分類模型(如決策樹)[1]。隨后，F(xiàn)reund和Schapire在此基礎(chǔ)上于1995年提出了著名的Adaboost算法[2]。到目前為止，許多研究者圍繞如何選擇基礎(chǔ)分類器、錯分樣品權(quán)重的確定方法以及損失函數(shù)的選擇與優(yōu)化，相繼提出多種boosting算法[3]。本文對多分類研究中的boosting算法進行綜述。

基本原理與方法

(1)

其中

βt=εt/(1-εt)，εt

(2)

εt為損失函數(shù)，組合分類器模型為

αt=log(1/βt)

(3)

單標(biāo)簽建模的boosting算法

單標(biāo)簽數(shù)據(jù)指對于每一個樣本，其僅屬于一個類別，主要有如下幾種方法：

1.AdaBoost.M1

AdaBoost.M1通過使用多分類弱分類器如決策樹等將原始AdaBoost算法直接擴展至多分類,用指示函數(shù)I[ht(xi)≠yi]表示分類器的錯誤率errt，替換原始算法中的誤差|ht(xi)-yi|，屬于一種直接多分類方式[4]。AdaBoost.M1實現(xiàn)起來較為簡單，但是K類別多分類問題僅要求其分類正確率大于1/K，二分類AdaBoost要求弱分類器的分類正確率要大于1/2，直接進行擴展時該條件過于苛刻。

2.SAMME算法

針對AdaBoost.M1方式對弱分類器的要求過于嚴(yán)格的問題，2009年，Hastie等人在AdaBoost算法的基礎(chǔ)上提出了SAMME算法以及其變體SAMME.R算法[5]。SAMME與AdaBoost框架基本相同，主要不同之處在于αt的計算方式，SAMME在AdaBoost的基礎(chǔ)上添加了log(K-1)這一項，即

(4)

為保證αt>0，只需要保證分類器的正確率1-errt>1/K即可，當(dāng)K=2 時，SAMME等同于二分類的AdaBoost.M1算法。相比于AdaBoost要求分類器分類效果大于1/2的條件來說，在多分類條件下，SAMME的分類誤差可以大于1/2且賦予錯分樣本的權(quán)重要比AdaBoost更大。當(dāng)K=2時，多分類指數(shù)損失函數(shù)同二分類保持一致，等同于前向梯度可加模型，在理論上證明了添加項log(K-1)的合理性，且模擬實驗表明SAMME在較小的迭代次數(shù)下即可快速地降低泛化誤差，收斂較快，具有良好的分類性能。

在SAMME的基礎(chǔ)上，Hastie等人同時提出了其變體形式SAMME.R算法，不同于SAMME關(guān)注經(jīng)驗損失，后者通過估計類別的加權(quán)概率來更新下一個模型，在收斂速度上要比SAMME快，分類性能稍好于SAMME。2016年，楊新武等人在SAMME算法的基礎(chǔ)上進行了改進，限定各類別中分類正確的樣本權(quán)值和大于錯分樣本權(quán)值之和，既保證弱分類器的有效性，又滿足了強分類器最終預(yù)測效果的提高[6]。

3.AdaBoost.M2算法

AdaBoost.M2算法由Freund和Schapire于1996年提出[4]，該算法在計算損失函數(shù)時，不是使用單一的預(yù)測值和實測值的差值，而是根據(jù)所有類別的預(yù)測獲得相應(yīng)的權(quán)重計算偽損失函數(shù)：

(5)

其中N為樣本例數(shù)，yi為原始標(biāo)簽，Dt(i)為樣本的權(quán)重分布，qt(i,y)代表每個樣本對應(yīng)的錯分標(biāo)簽的權(quán)重，表示各錯分標(biāo)簽的相對重要性。樣本的最終分類標(biāo)簽為弱分類器ht(x)的加權(quán)平均達到最大時所對應(yīng)的標(biāo)簽，分類效果越好偽損失函數(shù)越小。AdaBoost.M2方法的優(yōu)點在于其在建立預(yù)測模型時，不僅關(guān)注錯分的樣本，同時還關(guān)注容易錯分的程度，即以大概率錯分和小概率錯分的情況不同。

4.Adaboost.OC

輸出編碼矩陣是一種常見的多分類問題處理方式，設(shè)K×L二維矩陣表示糾錯編碼輸出矩陣(ECOC)，L表示編碼的長度，K表示多分類問題的分類數(shù)，矩陣中的每一行表示一個類別的編碼，每一列表示一個二分類器，在預(yù)測階段通過綜合各個二分類器的輸出結(jié)果和編碼矩陣之間的距離(通常采用漢明距離或者歐式距離)來判斷樣本的所屬類別。對于所有的拆解分類法來說，最終的結(jié)果都可以統(tǒng)一到一個編碼矩陣中，通過改變編碼得到不同的結(jié)果[7]。Adaboost.OC由AdaBoost.M2結(jié)合輸出編碼矩陣演變而來，在每次迭代的過程中不僅重新改變樣本的權(quán)重，同時也會依據(jù)距離的改變對樣本的標(biāo)簽進行重新編碼。弱學(xué)習(xí)分類器的目標(biāo)在于最小化重新加標(biāo)簽加權(quán)的數(shù)據(jù)的訓(xùn)練誤差：

μt:y→{0,1}

(6)

其中μt(yi) 表示著色函數(shù)，相當(dāng)于根據(jù)類別給出的編碼向量，其具體選擇方法可參考相應(yīng)文獻[8]。ht(xi)表示依據(jù)每次重新編碼的二值標(biāo)簽建立的弱分類器，Dt(i)表示每次迭代時樣本的權(quán)重。對于新樣本，弱分類器每次預(yù)測的二分類結(jié)果對應(yīng)的原始所有類別均獲得相同的票數(shù)，最終類別是多個弱分類器輸出標(biāo)簽的綜合投票結(jié)果。

5.Adaboost.ECC與Adaboost.ERP

Adaboost.ECC改進對弱分類假設(shè)加權(quán)投票的權(quán)重計算方法提高分類效果。先用著色函數(shù)μt將原始標(biāo)簽y轉(zhuǎn)化成多個二分類標(biāo)簽[9]，但權(quán)重的更新并不依賴于Adaboost.OC中的偽損失，而是分別計算ht:x→{-1,+1}的正負(fù)投票權(quán)重αt與βt，定義：當(dāng)ht(x)=+1 時，gt(x)=αt；當(dāng)ht(x)=-1時，gt(x)=-βt，更新權(quán)重為：

(7)

相比于Adaboost.OC來說其分類效果明顯提升，但由于原始標(biāo)簽劃分為二分類標(biāo)簽過程完全隨機，Adaboost.ECC未考慮原始的數(shù)據(jù)特點，依然無法避免丟失原始數(shù)據(jù)的結(jié)構(gòu)信息。ECOC將多分類問題轉(zhuǎn)化為多個二分類問題的集合，主要受編碼矩陣的糾錯能力以及弱二分類器的分類性能，糾錯能力過強的編碼矩陣可能無法尋找到合適的弱分類器，分類效果可能不是最優(yōu)。在權(quán)衡編碼矩陣的糾錯性能和二分類器的學(xué)習(xí)性能之后，2006年，Li在Adaboost.ECC的基礎(chǔ)上，通過修改編碼矩陣進一步提出Adaboost.ERP算法[10]。在該算法中，每一次迭代時都會對原始多分類標(biāo)簽分配不同的重新編碼(編碼矩陣的每一列視為一區(qū))，重新分區(qū)的實際意義在于根據(jù)目前分類器的性能確定一個合適的編碼矩陣，實驗證明Adaboost.ERP在訓(xùn)練損失、測試集預(yù)測效果以及運算速度上都較之前的方法有了較大提高。

6.MCBoost算法

Saberian等人認(rèn)為直接多分類雖然能夠統(tǒng)一處理多分類問題，但對分類間隔無實質(zhì)性提升，傾向于拆解方式，于2012年提出CD-MCBoost以及GD-MCBoost算法[11]。以MCBoost為框架，前者使用坐標(biāo)下降法，在每次迭代過程中僅更新預(yù)測變量中的一個成分；后者使用梯度下降法，在每次迭代過程中更新預(yù)測變量中全部成分。坐標(biāo)下降中下降方向是沿著每一維的坐標(biāo)軸方向進行的，而梯度下降法中，下降方向變換為函數(shù)在當(dāng)前點的梯度方向。然后結(jié)合樣本-標(biāo)簽的編碼矩陣，選用二分類基分類器對分類間隔進行目標(biāo)最大化。這兩種方式的優(yōu)點在于可以容納不同的模型，且實例證明其分類效果較為理想。

7.AOSO-LogitBoost算法

多分類LogitBoost算法須基于密集的Hessian矩陣進行樹的分離以及獲取節(jié)點值，且滿足下述條件：

(8)

此種方式可用于有序反應(yīng)變量分類研究中。2012年，Li等人考慮到上述兩個條件，在LogitBoost基礎(chǔ)上提出ABC-Logitboost方式[12]，該方式每次迭代過程中自適應(yīng)地選擇某一類別作為基準(zhǔn)類，基準(zhǔn)類不需要進行訓(xùn)練，在每次迭代過程中引入一個K維向量Fj(x)|(j=1,2,…,K)用于擬合樹節(jié)點，這種方式下節(jié)點的獲得以及節(jié)點值的擬合是一個受約束的K維二次優(yōu)化問題，可看做是用于尋找新樹分離點的子問題，對于每一個子問題，僅自適應(yīng)地選取兩個類別進行更新。同年，Sun等人在原始LogitBoost模型基礎(chǔ)上提出AOSO(adaptive one vs one )-LogitBoost算法[13]，為解決Hessian矩陣的尋優(yōu)問題，在每次迭代過程中僅自適應(yīng)選擇兩個類別進行更新，并證明了ABC-Logitboost方式可以看做是AOSO-LogitBoost方式的一個特例，只不過前者較后者要含有一些不靈活的樹模型，真實數(shù)據(jù)驗證表明ABC(8.54%) 和AOSO(8.33%)方式要比SVM(40%)誤差小，且AOSO比ABC的誤差更小。

8.BP-AdaBoost.M2算法

反向傳遞神經(jīng)網(wǎng)絡(luò)(BP neural network)作為人工神經(jīng)網(wǎng)絡(luò)的典型算法，具有很強的非線性關(guān)系處理能力。 Qiao 等人于2013年將AdaBoost.M2同反向傳遞神經(jīng)網(wǎng)絡(luò)相結(jié)合[14]，以BP作為基礎(chǔ)分類器，對原始AdaBoost.M2算法進行相應(yīng)的改進，改進模型系數(shù)為

(9)

其中，t1表示為樣本i第一次被錯判時的迭代次數(shù)，Dj(xi,y)為樣本在每次迭代過程中的權(quán)重分布，在該算法中對樣本更新權(quán)重的閾值η=(N+1)/2N進行限定，當(dāng)樣本權(quán)重超過閾值時，保留上一次權(quán)重不變，避免分類器出現(xiàn)過度學(xué)習(xí)的狀態(tài)。實驗結(jié)果表明，此種集成式分類器分類正確率平均約為0.93，遠高于傳統(tǒng)BP神經(jīng)網(wǎng)絡(luò)的0.79 。

9.GAMBLE算法

rt(j)(x)=K×gt(j)(x)/ft(j)(x),j=1,2,…,K

(10)

則每次迭代獲得的弱分類器為

(11)

損失函數(shù)選用Adaboost指數(shù)損失。實驗結(jié)果表明：GAMBLE的測試集誤差下降速率要快于SAMME，且測試誤差也較SAMME小。這種算法采用直接多分類方式，方法較為穩(wěn)健，對離群點敏感性小，整體算法簡潔明了易于實現(xiàn)。在此基礎(chǔ)上也可以主動選擇樣本，即選擇訓(xùn)練集樣本中最有益的部分建立模型，使收斂速度更快。

10. 全校正Boosting算法

11. HingeBoost算法

在處理多分類問題時，Hinge損失函數(shù)，可表達為

εt=Lh(y,h(x))=max(0,1-yh(x)),

y∈{1,-1}

(12)

Wang Z 從間隔理論出發(fā)，認(rèn)為Hinge損失要更加穩(wěn)健一些，于2011年提出了多分類HingeBoost方法[17]，該方法也可用于處理多分類代價敏感性問題。 同年，Gao 等人基于輸出編碼矩陣提出了Hingeboost.OC算法，同時引入了代價矩陣，即考慮在不同錯分情況下的損失不同[18]。

多標(biāo)簽建模的boosting算法

多標(biāo)簽數(shù)據(jù)指對于每一個樣本，其可同時屬于不同類別。

1.AdaBoost.MH算法

AdaBoost.MH算法由Schapire和Singer于1999年提出[19]，使用一對多的多分類方式，適合多標(biāo)簽建模，該算法假設(shè)產(chǎn)生預(yù)測標(biāo)簽集，預(yù)測損失依賴于預(yù)測標(biāo)簽集和真實觀察結(jié)果之間的差異，表示為

(13)

其中Δ為對稱差，即預(yù)測標(biāo)簽同原始標(biāo)簽無交集的標(biāo)簽集合，這種形式的損失函數(shù)又稱之為Hamming Loss。最小化Hamming Loss 是將原始標(biāo)簽yi轉(zhuǎn)化為特定的K個二值標(biāo)簽，具體如下所示：

Yi[l]=1(ifl=yi),Yi[l]=-1(ifl≠yi)

(14)

從而原始的多分類問題轉(zhuǎn)化為多個正交的二分類問題，Hamming Loss即可視為K個二分類問題h(x)錯誤率的平均。AdaBoost.MH方式將AdaBoost.M1的直接多分類問題拆解為多個二分類問題。AdaBoost.MH同logistic概率模型相結(jié)合即可衍生出LogitBoost方式，模擬實驗證明當(dāng)樣本數(shù)據(jù)噪聲過多，樣本標(biāo)簽分布不均時，LogitBoost表現(xiàn)比AdaBoost略優(yōu)。

2.Adaboost.MO算法

Adaboost.MO算法由Adaboost.MH同ECOC結(jié)合得到，函數(shù)λ將不同的原始樣本標(biāo)簽y映射至新的二值標(biāo)簽集y′中，且二者的對稱差增大。一旦λ選定之后，就可以在轉(zhuǎn)換后的數(shù)據(jù)(xi,λ(yi))上應(yīng)用Adaboost.MH方式，在預(yù)測樣本標(biāo)簽時選擇滿足arg min|λ(y)ΔH(x)|所對應(yīng)的標(biāo)簽，H(x)表示為最終分類器。這兩種算法的優(yōu)點在于速度快且分類效果和Adaboost.M2或Adaboost.MH相似，同時Adaboost.MO算法還可用于多標(biāo)簽問題。

含無標(biāo)簽建模的boosting算法

實際問題中常遇到無標(biāo)簽樣本過多的情況，傳統(tǒng)的監(jiān)督學(xué)習(xí)方式無法有效地利用樣本的信息。為得到較好的預(yù)測結(jié)果，近年，越來越多的研究者嘗試將半監(jiān)督學(xué)習(xí)方式和boosting結(jié)合在一起。

1.MCSSB算法

Valizadegan等人將boosting和半監(jiān)督思想相結(jié)合，于2008年提出MCSSB(multiclass semi-supervised boosting)算法，挖掘無標(biāo)簽樣本的信息[20]。先利用訓(xùn)練集中一部分帶有分類標(biāo)簽的樣本建立初始化單一分類器，然后用該分類器預(yù)測無分類標(biāo)簽的樣本，所得到的標(biāo)簽視為無分類樣本的偽標(biāo)簽，新的分類器的建立同時基于所有含標(biāo)簽的樣本(包括真實標(biāo)簽和偽標(biāo)簽)。分類器逐漸建立的過程中，無標(biāo)簽樣本的偽標(biāo)簽不斷地隨迭代次數(shù)改變，直至達到停止的標(biāo)準(zhǔn)。為保證結(jié)果的正確性，迭代過程中盡可能地賦予正確的樣本偽標(biāo)簽，同時需要檢驗流體假設(shè)和聚類假設(shè)，保證分類信任度以及樣本之間的相似性。

2.RMS-BOOST算法

2009年，Saffari等人在前人的基礎(chǔ)上提出一種新的半監(jiān)督多分類boosting方法——RMS-BOOST[21]，這種方法將含標(biāo)簽樣本和無標(biāo)簽樣本混合聚類，結(jié)合標(biāo)簽先驗知識和每一類的樣本組成計算每一聚類組的先驗信息，如果某一類中不包括任何標(biāo)簽樣本，則視為該聚類組中所有標(biāo)簽類別概率相等，最終針對目標(biāo)損失函數(shù)進行求解。

結(jié) 語

在醫(yī)學(xué)研究中，boosting算法是一種極其有效的建立組合分類模型的方法，分類效果的優(yōu)劣與選擇的基礎(chǔ)分類器和確定樣本權(quán)重方法有關(guān)，其算法的核心是依據(jù)預(yù)測誤差和損失函數(shù)對各樣本賦予不同的權(quán)重。這種算法不僅能夠?qū)我粯?biāo)簽進行預(yù)測，也能夠?qū)Χ鄻?biāo)簽進行預(yù)測，同時還能夠根據(jù)有標(biāo)簽和無標(biāo)簽的混合樣本進行建模，具有良好的研究價值和應(yīng)用前景。

[1] Mayr A,Hofner B,Waldmann E,et al.An update on statistical boosting in biomedicine.Computational & Mathematical Methods in Medicine,2017(48):1-12.

[2] 章光明,劉晉,賈慧珣,等.隨機梯度boosting算法在代謝組學(xué)研究中的應(yīng)用.中國衛(wèi)生統(tǒng)計,2013,30(3):323-326.

[3] Li L,Wu Y,Ye M.Experimental comparisons of multi-class classifiers.proceedings of the International Symposium on Space Terahertz Technology,F,2015.

[4] Freund Y,Schapire RE.A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting.Journal of Computer & System Sciences,2010,55(1):119-139.

[5] Hastie T,Rosset S,Zhu J,et al.Multi-class AdaBoost.Statistics & Its Interface,2009,2(3):349-360.

[6] 楊新武,馬壯,袁順.基于弱分類器調(diào)整的多分類Adaboost算法.電子與信息學(xué)報,2016,38(2):373-380.

[7] Allwein EL,Schapire RE,Singer Y.Reducing Multiclass to Binary:A Unifying Approach for Margin Classifiers.proceedings of the Seventeenth International Conference on Machine Learning,F,2001.

[8] Schapire RE.Using output codes to boost multiclass learning problems.proceedings of the Fourteenth International Conference on Machine Learning,F,1997.

[9] Guruswami V,Sahai A.Multiclass Learning,Boosting,and Error-Correcting Codes.proceedings of the Twelfth Conference on Computational Learning Theory,F,1999.

[10] Li L.Multiclass boosting with repartitioning.proceedings of the International Conference,F,2006.

[11] Saberian M J,Vasconcelos N.Multiclass Boosting:Theory and Algorithms.Adv Neural Inf Process Syst,2012,2124-2132.

[12] Li P.Robust LogitBoost and Adaptive Base Class (ABC) LogitBoost.Computer Science,2012.

[13] Sun P,Reid M D,Zhou J.AOSO-LogitBoost:Adaptive One-Vs-One LogitBoost for Multi-Class Problem.Eprint Arxiv,2012,1087-1094.

[14] Qiao C,Sun S,Hou Y.Design of Strong Classifier Based on Adaboost M2 and Back Propagation Network.Journal of Computational & Theoretical Nanoscience,2013,10(12):2836-2840.

[15] Huang J,Ertekin S,Song Y,et al.Efficient Multiclass Boosting Classification with Active Learning.proceedings of the Siam International Conference on Data Mining,April 26-28,2007,Minneapolis,Minnesota,Usa,F,2007.

[16] Shen C,Hao Z.A direct formulation for totally-corrective multi-class boosting.proceedings of the Computer Vision and Pattern Recognition,F,2011.

[17] Wang Z.HingeBoost:ROC-Based Boost for Classification and Variable Selection.International Journal of Biostatistics,2011,7(1):13-13.

[18] Gao T,Koller D.Multiclass Boosting with Hinge Loss based on Output Coding.proceedings of the International Conference on Machine Learning,ICML 2011,Bellevue,Washington,Usa,June 28 - July,F,2011.

[19] Schapire RE,Singer Y.Improved Boosting Algorithms Using Confidence-rated Predictions.Machine Learning,1999,37(3):297-336.

[20] Valizadegan H,Jin R,Jain A K.Semi-Supervised Boosting for Multi-Class Classification.proceedings of the Machine Learning and Knowledge Discovery in Databases,European Conference,2008,Antwerp,Belgium,September 15-19,2008,Proceedings,F,2008.

[21] Saffari A,Leistner C,Bischof H.Regularized multi-class semi-supervised boosting.Cvpr,2009,967-974.