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

宋召青，陳 垚

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

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

宋召青a，陳 垚b

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

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

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

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

1 支持向量機

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

考慮如下訓練樣本集：

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

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

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

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

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

2 多類分類支持向量機

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

2.1 “分解—重組”法

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

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

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

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

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

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

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

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

2.2 “直接求解”法

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

3 多類分類支持向量機算法應用

3.1 “分解—重組”法應用

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

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

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

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

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

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

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

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

3.2 “直接求解”法應用

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

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

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

4 總結和展望

綜述了基于支持向量機的多類分類算法，對已有的主要方法進行介紹和分析，討論了這些方法的優缺點，并列舉了國內外的研究應用現狀。總結發現，學者主要研究方向都是將多類分類問題轉化為二類分類問題進行求解，對直接求解法鮮有關注且沒有快速有效的方法提出。

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

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

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

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

[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，FRANCIS 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].計算機工程與設計，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].計算機科學，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].軟件導刊，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].計算機應用與軟件，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

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

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