基于支持向量機的多類分類算法綜述

宋召青，陳 垚

（海軍航空工程學(xué)院a.七系；b.研究生管理大隊，山東煙臺264001）

基于支持向量機的多類分類算法綜述

宋召青a，陳 垚b

（海軍航空工程學(xué)院a.七系；b.研究生管理大隊，山東煙臺264001）

作為一種新興的機器學(xué)習方法，基于統(tǒng)計學(xué)習理論的支持向量機，最初是用來解決二類分類問題的。對于實際中主要遇到的多類分類問題，目前常用的兩大類改進推廣方法為“分解—重組”法和“直接求解”法。文章對二類方法進行了介紹和分析，指出其優(yōu)缺點和未來的改進方向。

支持向量機；多類分類；算法

基于統(tǒng)計學(xué)習理論的支持向量機（Support Vector Machine，SVM）自1995年由Vapnik[1]提出以來，由于其對于解決小樣本、高維數(shù)、非線性等問題有很好的效果，受到了廣泛的關(guān)注，成為繼神經(jīng)網(wǎng)絡(luò)之后機器學(xué)習領(lǐng)域新的研究熱點，并取得了快速的發(fā)展。

1 支持向量機

SVM設(shè)計之初是用于解決二類分類問題，目標是尋找一個最優(yōu)超平面，使得其能將二類樣本分開，并且與二類樣本的距離即分類間隔最大。

考慮如下訓(xùn)練樣本集：

對于線性可分問題，分類超平面的求解可以轉(zhuǎn)換為對如下的二次規(guī)劃（Quadratic Programming，QP）問題的求解[2]：

式中：ω為行向量，是超平面的法向量；b為分類閾值；C為懲罰因子；ξi為松弛變量。

這個二次規(guī)劃問題可用拉格朗日乘子法求解[3]，最終得到分類函數(shù)表達式：

對于線性不可分問題，引入了核函數(shù)[4]K(·,·)的概念，將樣本從低維空間映射到高維空間，將線性不可分轉(zhuǎn)化為高維空間的線性可分問題，而樣本在轉(zhuǎn)化前后的內(nèi)積保持不變。分類函數(shù)表達式變?yōu)?/p>

核函數(shù)有很多種，其中最為常用的是高斯徑向基（RBF）核函數(shù)：K(α,β)=exp(-‖α-β‖2/2σ2)。

2 多類分類支持向量機

在實際應(yīng)用中大部分的分類問題都是多類分類問題，用標準的SVM無法直接解決，目前學(xué)者采用的方法主要分為兩大類。

2.1 “分解—重組”法

第一類是“分解—重組”法，這類方法的主要思想是將多類分類問題拆分成為一系列的二類分類問題，再以一定的決策規(guī)則將這些二類分類器重新組合在一起得到分類結(jié)果。這類方法常用的包括：“一對多（One-Against-Rest，OAR）法[5]”、“一對一（One-Against-One，OAO）法[6]”、“有向無環(huán)圖（Directed Acyclic Graph，DAG）法[7]”、“二叉樹（Binary Tree）法[8]”、“糾錯編碼法[9]”、“模糊SVM法[10]”等等。這類方法的應(yīng)用比較廣泛，下面簡要介紹幾種方法。

OAR法的基本思想是對一個N類分類問題，訓(xùn)練出N個二類分類器，每個分類器用于將某一類與其他所有類區(qū)分開，得到N個分類函數(shù)。在測試未知樣本時，將其代入每個分類函數(shù)，得到函數(shù)值最大的那類即判定為未知樣本的類別。該算法只需訓(xùn)練N個二類分類SVM，速度較快。缺點是：每個分類器的訓(xùn)練都需要所有樣本參與，當樣本規(guī)模較大時訓(xùn)練速度會下降；在每個分類器的訓(xùn)練過程中，正類樣本數(shù)和負類樣本數(shù)一般會存在很大的差距，會導(dǎo)致分類超平面的偏斜，從而降低了分類準確度；存在樣本不可分的情況，即測試樣本被每個分類函數(shù)都判為負類。

OAO法的基本思想是在N個類別中的每二類之間均訓(xùn)練一個二類分類器，得到(N-1)N/2個分類器和分類函數(shù)。在測試未知樣本時，將其分別代入每個分類函數(shù)，對各函數(shù)判別結(jié)果采用投票的方式記錄，得票最多的類別判定為未知樣本的類別。這種方法的優(yōu)點是每個二類分類器只需訓(xùn)練二類樣本，簡單快速。但需要訓(xùn)練的分類器數(shù)量較多，特別是N較大時；當不止一類得票最多時，會出現(xiàn)樣本的誤分類。

DAG法可以看作OAO法的推廣，在訓(xùn)練分類器的階段與OAO法相同，訓(xùn)練(N-1)N/2個分類器。在測試階段，DAG法則是構(gòu)造一個有向無環(huán)圖（圖1為N=4時的示意圖）。DAG包含(N-1)N/2個節(jié)點和N個葉節(jié)點，每個節(jié)點對應(yīng)一個二類分類器，每個葉節(jié)點對應(yīng)一個類別。測試未知樣本時，樣本從根節(jié)點的判別函數(shù)開始分類判斷，根據(jù)判斷結(jié)果來決定下一層的移動方向，直到移動到某個葉子為止，該葉子所對應(yīng)的類別即為未知樣本的類別。DAG法的優(yōu)點是避免了OAO法中可能存在的樣本不可分情況，同時每次測試只需要計算N-1個判別函數(shù)，加快了計算速度，減少了測試時間。存在的問題除了和OAO法一樣訓(xùn)練過程較長外，一旦某個節(jié)點出現(xiàn)了誤分類，將無法得到正確的結(jié)果，因此在構(gòu)造DAG時靠上層的節(jié)點應(yīng)選擇不易出現(xiàn)誤分類的二類分類器。

圖1 四類分類問題的DAG示意圖Fig.1 ADAG schematic diagram of 4-class classification problem

二叉樹法的基本思想是，將包含所有類別的集合劃分為2個互斥子集，再將每個子集劃分為2個互斥次級子集，以此類推，直到每個集合只包含一個類別為止。將所有集合作為節(jié)點，構(gòu)成倒置的樹狀結(jié)構(gòu)（圖2為N=4時的示意圖）。每個節(jié)點對應(yīng)一個二類分類SVM，用于區(qū)分其2個子類，這樣共需要訓(xùn)練N-1個分類器。測試樣本的過程與DAG法相同，都是從上層節(jié)點向下單方向進行。這種方法的優(yōu)點是需要訓(xùn)練的二類分類器少，訓(xùn)練和測試的速度都較快，不存在不可分的樣本。缺點是各子節(jié)點的劃分方法對結(jié)果有較大影響，而且同DAG法一樣，在某個節(jié)點出現(xiàn)誤分類后，將無法糾正到正確的結(jié)果。

圖2 四類分類問題的一種二叉樹模型示意圖Fig.2 Abinary tree schematic diagram of 4-class classification problem

這類方法將多類分類問題分解后，每次訓(xùn)練的都是標準的二類分類支持向量機，訓(xùn)練過程簡單。但也存在一些問題：一是遇到包含類別數(shù)較多的問題時，需構(gòu)造的支持向量機數(shù)呈線性甚至幾何倍數(shù)增長，訓(xùn)練和驗證樣本的時間都大大增加；二是在構(gòu)造分類器時大都只是使用了一部分樣本，沒有考慮到所有樣本包含的信息，會對分類的結(jié)果造成一定的影響。

2.2 “直接求解”法

第二類是“直接求解”法，這類方法的基本思想是將多類分類問題作為一個整體求解，只要構(gòu)造一個分類器就可以解決多類分類問題。其優(yōu)點是構(gòu)造的分類器數(shù)量少，同時構(gòu)造過程中利用到了所有樣本的信息。存在的缺點是沒有較統(tǒng)一的構(gòu)造方法，而且一般訓(xùn)練過程比較慢，分類器結(jié)構(gòu)復(fù)雜。相比之下，研究“直接求解”法的學(xué)者較少，取得的成果也不多，所以這類方法有很大的研究空間。

3 多類分類支持向量機算法應(yīng)用

3.1 “分解—重組”法應(yīng)用

“分解—重組”這類方法由于將多類分類問題拆分成了容易解決的二類分類問題，運算復(fù)雜度降低，故受到許多學(xué)者的關(guān)注和研究，并且在實際中有廣泛的應(yīng)用。

Shiladitya Chowdhury等[11]提出一種加權(quán)多類分類支持向量機（Weighted Multi-Class SVM，WMCSVM），并將其應(yīng)用到人臉識別中。這種方法以“一對多”法為基礎(chǔ)，考慮到不同的訓(xùn)練樣本對訓(xùn)練最優(yōu)分類超平面的貢獻程度不同，為每個樣本引入了不同的權(quán)重，并由概率方法進行計算。重要的樣本被賦予較大的權(quán)重，噪聲等無關(guān)樣本被賦予較小的權(quán)重，這樣訓(xùn)練出的SVM具有更高的分類精度。WMSCVM在人臉識別問題中取得了很好的效果，比改進前的MCSVM有更高的準確率。

Henry Joutsijoki[12]將“一半對一半”多類分類支持向量機（Half-Against-Half Multi-Class SVM，HAHMCSVM）應(yīng)用到了大型底棲無脊椎動物圖像的自動辨識分類中，這種方法結(jié)合了OAR和DAG這2種基本方法，取長補短。作者在文中對2種劃分節(jié)點的方法——散射法和隨機法進行對比，通過大量的實驗，得出的結(jié)論是2種劃分方法均有很高的分類精度，散射法相比之下更優(yōu)。

Maya Kallas等[13]將核主成分分析法（Kernel Principal Component Analysis，KPCA）與OAR法相結(jié)合，提出了一種新的多類分類方法。KPCA法用于特征提取，是主成分分析法（PCA）的改進方法，PCA只能用于線性問題，KPCA通過引入核的概念，將其推廣到了非線性問題中。作者將結(jié)合后的多類分類方法應(yīng)用到心電圖信號的分類識別中，取得了很好的效果，比普通的OAR和OAO法分類精度更高。

單玉剛等[14]針對OAO法中存在不可分區(qū)域的問題，將基于緊密度判決與OAO法相結(jié)合，提出了一種新的多類分類方法。這種方法依據(jù)樣本到類中心之間的距離和基于kNN（k Nearest Neighbor）的樣本分布情況結(jié)合的方式構(gòu)建判別函數(shù)，以此來確定不可分樣本的類別歸屬。作者使用了UCI（University of California Irvine）數(shù)據(jù)集對新算法進行測試，測試結(jié)果表明，該算法能有效地解決不可分區(qū)域問題，而且分類準確率比傳統(tǒng)方法更高。

秦玉平等[15]基于二叉樹SVM提出了一種改進的快速MCSVM算法。這種算法以每類樣本的數(shù)量作為權(quán)重，按照Huffman樹的構(gòu)造過程自下向上地構(gòu)造二叉樹，提高了二叉樹的生成速度，從而提高的算法的效率。作者采用Reuters 21578標準數(shù)據(jù)集驗證改進的算法，實驗結(jié)果證明了該算法的有效性。

肖榮等[16]提出一種改進的OAO算法，先通過粗分類快速選出候選類別，再對候選類別按原OAO法進行投票，相當于減少了類別的數(shù)量，提高了計算速度，對類別較多的問題效果更好。實驗結(jié)果顯示該方法提高了分類效率，且分類準確率有一定程度的提高。

除此之外還有很多研究成果，如文獻[17-27]等。這類方法存在一個共同的問題是在構(gòu)造分類器時都沒有考慮到所有樣本所包含的信息。

3.2 “直接求解”法應(yīng)用

Weston J等[28]提出一種思想上基于OAR方法的直接求解方法。該方法需構(gòu)造N個二類分類SVM，不同的是通過一個優(yōu)化問題將N個SVM的參數(shù)一次性求解，再通過判別函數(shù)對樣本進行檢測。這種方法減少了優(yōu)化問題的數(shù)量，但大大增加了問題求解的難度，尤其當訓(xùn)練樣本較多時，求解速度很難滿足要求。

Minkook Cho和Hyeyoung Park[29]針對多類分類問題中訓(xùn)練樣本少時存在的泛化能力差的問題提出一種新方法，這種方法訓(xùn)練一個支持向量機來計算樣本之間的相似度量，然后與kNN法相結(jié)合來判斷樣本所屬類別。實驗結(jié)果表明新方法比傳統(tǒng)多類分類方法有更高的分類準確率和更好的泛化能力。

除此之外如文獻[30]等也對“直接求解”這類方法進行過研究。

4 總結(jié)和展望

綜述了基于支持向量機的多類分類算法，對已有的主要方法進行介紹和分析，討論了這些方法的優(yōu)缺點，并列舉了國內(nèi)外的研究應(yīng)用現(xiàn)狀。總結(jié)發(fā)現(xiàn)，學(xué)者主要研究方向都是將多類分類問題轉(zhuǎn)化為二類分類問題進行求解，對直接求解法鮮有關(guān)注且沒有快速有效的方法提出。

對多類分類支持向量機，研究重點主要包括：

1）對于“分解—重組”法，應(yīng)將重點放在求解樣本規(guī)模大、種類多的問題上。樣本數(shù)量大時應(yīng)當對非支持向量進行刪減，縮小樣本規(guī)模。可以采用的方法如計算每個樣本距離樣本中心的幾何距離，剔除距離中心最近的樣本；或是保留不同類別之間距離最近的若干樣本來訓(xùn)練分類超平面；與模糊集合方法相結(jié)合，根據(jù)隸屬度進行篩選等。而樣本種類多時首先應(yīng)盡量不使用OAO法等分類器數(shù)受樣本類別影響較大的方法，相比之下“二叉樹法”需要訓(xùn)練的分類器較少，同時測試樣本時也無須用到每個分類器。須要解決的主要是誤差累積的問題，在每個節(jié)點的劃分都應(yīng)當盡量使得2個子節(jié)點中的樣本集更易區(qū)分。可以采用最大化樣本類間幾何距離的方法劃分各類別，等等。對于OAR、OAO等方法中存在的不可分問題，主要采用幾何距離、隸屬度等對不可分樣本進行歸類。

2）對于“直接求解”法，由于研究成果較少，因而仍有很大空間。目的是設(shè)計少量的甚至只用一個分類器，就可以對多類樣本進行分類，而所設(shè)計的分類器在保證分類準確率的前提下應(yīng)當結(jié)構(gòu)簡單易于訓(xùn)練，才能體現(xiàn)其應(yīng)用價值。設(shè)計思路一方面可以考慮將SVM與其他算法相結(jié)合；另一方面可以考慮改變思路，對多類分類問題進行變型，利用更簡便的算法求解變型后的問題。以這種思想為指導(dǎo)，筆者研究了一種基于支持向量回歸機的多類分類算法，這種算法將回歸的思想用到了分類問題中，把分類樣本直接用支持向量回歸機進行回歸（其中樣本的類標作為回歸樣本的輸出值），得到的回歸函數(shù)擬合了樣本輸入和其類標的映射關(guān)系，即得到了多類分類問題的分類器。對未知樣本進行分類時，由于回歸函數(shù)的輸出是實數(shù)，故需要對結(jié)果進行取整運算，得到即為被測樣本的類別標示。將多類分類問題轉(zhuǎn)化為回歸問題進行求解是一次完成的，算法實現(xiàn)簡單，運行速度快。而且由于采取了取整運算，加強了算法的魯棒性，在輸入樣本有一定噪聲的情況下，也可獲得正確的分類。這種方法可以作為多類分類算法研究的一種新思路，還需進一步的研究。

3）對基本的支持向量機方法進行改進。如近些年出現(xiàn)的雙生支持向量機（Twin SVM），不再求解二類樣本的最優(yōu)分類超平面，而是尋找2個超平面分別穿過二類樣本，使得二類樣本分別與穿過的平面距離最近，從而減少了優(yōu)化問題的運算時間。利用TSVM代替?zhèn)鹘y(tǒng)的SVM來求解多類分類問題可以有效的縮短訓(xùn)練時間。而代替后是否會出現(xiàn)新的問題，應(yīng)當如何解決等都可以作為研究的方向。

[1]VAPNIK V.The nature of statistical learning theory[M]. New York：Springer-Verlag，1995：25-27.

[2]CORTES C，VAPNIK V.Support-vector networks[J].Machine Learning，1995，20（3）：273-297.

[3]HSU C W，LIN C J.A comparison of methods for multiclass support vector machines[J].IEEE Transactions on Neural Networks，2002，13（2）：415-425.

[4]AIZERMAN M，BRAVERMAN E M，ROZONOER L. Theoretical foundations of the potential function method in pattern recognition[J].Automation and Remote Control，1964，25（6）：917-936.

[5]KREBEL U H G.Pairwise classification and support vector machines[M].Cambridge，MA：MIT Press，1999：255-268.

[6]BENNETT KRISTIN P.Combining support vector and mathematical programming methods for classification [M].Cambridge，MA：MIT Press，1999：307-326.

[7]PLATT J C，CRISTIANINI N，SHAWE TAYLOR J. Large margin DAGs for multiclass classification[C]//Advances in Neural Information Processing Systems.Cambridge，MA：MIT Press，2000：547-553.

[8]CHEONG S，OH S H，LEE S Y.Support vector machines with binary tree architecture for multi-class classification [J].Neural Information Processing Letters and Reviews，2004，2（3）：47-51.

[9]GHANI R.Using error-correcting codes for text classification[C]//The 17th International Conference on Machine Learning.Sydney：Morgan Kaufmann Publishers，2002：303-310.

[10]SHIGEO ABE，TAKUYA INOUE.Fuzzy support vector machines for multiclass problems[C]//European Symposium on Artificial Neural Networks.Bruges：IEEE，2002：113-118.

[11]CHOWDHURY S，SING J K，BASU D K，et al.Weighted multi-class support vector machine for robust face recognition[C]//International Conference on Communications，Devices and Intelligent Systems.Piscataway，N.J.：IEEE，2012：326-329.

[12]HENRY J.Half-against-half multi-class support vector machines in classification of benthic macroinvertebrate images[C]//International Conference on Computer&Information Science.Piscataway，N.J.：IEEE，2012：414-419.

[13]KALLAS M，F(xiàn)RANCIS C，KANAAN L，et al.Multiclass SVM classification combined with kernel PCA feature extraction of ECG signals[C]//The 19thInternational Conference on Telecommunications.Tahiti，Papeete：IEEE，2012：1-5.

[14]單玉剛，王宏，董爽.改進的一對一支持向量機多分類算法[J].計算機工程與設(shè)計，2012，33（5）：1837-1840. SHAN YUGANG，WANG HONG，DONG SHUANG.Improved multi-classifictaion algroithm of one-against-one SVM[J].Computer Engineering and Design，2012，33（5）：1837-1840.（in Chinese）

[15]秦玉平，羅倩，王秀坤.一種快速的支持向量機多類分類算法[J].計算機科學(xué)，2010，37（7）：240-242. QIN YUPING，LUO QIAN，WANG XIUKUN.Fast multiclass classification algorithm of support vector machines [J].Computer Science，2010，37（7）：240-242.（in Chinese）

[16]肖榮，李金鳳，覃俊.一種改進的一對一多類支持向量機[J].軟件導(dǎo)刊，2010，9（10）：109-111. XIAO RONG，LI JINFENG，QIN JUN.An improved oneagainst-one multiclass SVM[J].Software Guide，2010，9（10）：109-111.（in Chinese）

[17]JI YOU，SUN，SHILIANG，LU，YUE.Multitask multiclass privileged information support vector machines[C]// 21stInternational Conference on Pattern Recognition.Piscataway，N.J.：IEEE，2012：2323-2326.

[18]JU XUCHAN，TIAN YINGJIE，LIU DALIAN，et al. Nonparallel hyperplanes support vector machine for multi-class classification[J].Procedia Computer Science，2015，51：1574-1582.

[19]LAJNEF T，CHAIBI S，RUBY P，et al.Learning machines and sleeping brains：automatic sleep stage classification using decision-tree multi-class support vector machines[J].Journal of Neuroscience Methods，2015，250：1-12.

[20]LI LEI，GAO ZHIPING，DING WENYAN.Fuzzy multiclass support vector machine based on binary tree in network intrusion detection[C]//International Conference on Electrical and Control Engineering.Piscataway，N.J.：IEEE，2010：1043-1046.

[21]LIU SHUANG，CHEN PENG，LI KEQIU.Multiple subhyper-spheres support vector machine for multi-class classification[J].International Journal of Wavelets Multiresolution&Information Processing，2014，12（3）：75-85.

[22]NASIRI J A，MOGHADAM CHARKARI N，JALILI S. Least squares twin multi-class classification support vector machine[J].Pattern Recognition，2015，48（3）：984-992.

[23]POOYAN N，SHAHBAZIAN M，SALAHSHOOR K，et al.Simultaneous fault diagnosis using multi class support vector machine in a dew point process[J].Journal of Natural Gas Science&Engineering，2015，23：373-379.

[24]SONGSIRI P，PHETKAEW T，KIJSIRIKUL B.Enhancement of multi-class support vector machine construction from binary learners using generalization performance[J]. Neurocomputing，2015，151：434-448.

[25]TOMAR D，AGARWAL S.A comparison on multi-class classification methods based on least squares twin support vector machine[J].Knowledge Based Systems，2015，81：131-147.

[26]YANG X Y，LIU J，ZHANG M Q，et al.A new multiclass SVM algorithm based on one-class SVM[C]//Proceedings of the 7thinternational conference on Computational Science.Berlin：Springer，2007：677-684.

[27]趙亮.一種改進的基于支持向量機的多類分類方法[J].計算機應(yīng)用與軟件，2014，31（12）：233-236. ZHAO LIANG.An improved SVM-based multi-class classification algorithm[J].Computer Applications and Software，2014，31（12）：233-236.（in Chinese）

[28]WESTON J，WATKINS C.Support vector machines for multi-class pattern recognition[C]//The European Symposium onArtificial Neural Networks.Bruges，Belgium：ESANN，1999：219-224.

[29]CHO M，PARK H.A robust SVM design for multi-class classification[C]//Advances in Artificial Intelligence.Berlin：Springer，2005：1335-1338.

[30]ARENAS GARCIA J，PEREZ CRUZ F.Multi-class support vector machines：a new approach[C]//International Conference on Acoustics，Speech，and Signal Processing. Piscataway，N.J.：IEEE，2003：6-10.

An Overview of Multi-Class Algorithm Based on Support Vector Machine

SONG Zhaoqinga,CHEN Yaob
（Naval Aeronautical and Astronautical University a.No.7 Department; b.Graduate Students’Brigade,Yantai Shandong 264001,China）

As a new machine learning method,the support vector machine which is based on statistical learning theory,is used to solve binary classification problem originally.However,most of the classification problems in practice contain more than two classes,and there were two major types of methods to extend the binary SVM to multi-class SVM which are‘Decomposition-Reorganization’method and‘Direct solving’method.In this paper,the two methods were introduced and analyzed and the advantages,disadvantages and the improvement direction in the future are pointed out.

support vector machine;multi-class classification;algorithm

TP391.41

A

1673-1522（2015）05-0442-05

10.7682/j.issn.1673-1522.2015.05.009

2015-06-11；

2015-07-26

國家自然科學(xué)基金資助項目（61433011）；山東省優(yōu)秀中青年科學(xué)家科研獎勵基金資助項目（BS2012DX007）；上海博士后科研資助計劃資助項目（12R21414300）

宋召青（1969-），男，教授，博士。