孫少乙1,2，黃志波1
?。?.華北計算機系統工程研究所，北京 100083；2.中電和瑞科技有限公司，北京 100083)
摘要：為了使用支持向量機(SVM)算法進行多類分類，在SVM二分類基礎上，提出使用排序算法中冒泡排序的思想進行SVM多類別數據分類。使用該方法在選取的UCI數據集進行實驗，結果表明，在保證較高正確率的情況下，相對傳統一對一的多分類方法，該方法較大幅地減少了分類時間，是一種應用性較強的SVM多類分類方法。
關鍵詞：支持向量機；多類分類；冒泡排序； LibSVM
0引言
支持向量機(Support Vector Machine，SVM) 是一種在統計學習基礎上發展起來的機器學習方法，其最大特點是根據Vapnik結構風險最小化原則［1］。它的基本模型是定義在特征空間上的間隔最大的線性分類器［2］，在解決小樣本、非線性及高維度等問題上具有傳統的機器學習方法所不具備的優勢［3］。SVM本是針對二分類問題提出的，如何將其應用到多類分類問題將成為對SVM研究的重要問題之一。當前，對于SVM的多分類問題，解決思路有兩種：(1)將問題轉化為SVM直接可解的問題；(2)適當改變原始SVM中最優化問題，使之成為能同時計算出所有分類決策問題的決策函數，從而一次性實現多分類。其中方法（2）看似簡單，但由于其問題最優化求解過程太過復雜，計算量太大，實現困難，未得到廣泛應用［4］。故當前多分類主要采用的是方法（1）的思想。
1SVM原理及多分類方法
1.1SVM分類原理
假設給定一個特征空間的含有N個樣本的訓練數據集T={(X1, Y1)，(X2, Y2)，…，(XN, YN)}，其中，Xi∈Rn，Yi∈{+1，-1}，i=1,2,3，…，N，Xi為第i個特征向量，Yi為Xi的類標記，即Yi=+1時，Xi為正例，Yi=-1時，Xi為反例。SVM就是要找到一個超平面ω·X+b=0，能將兩類樣本分開，并且超平面距兩類樣本的間隔最大，這樣可以將超平面用于對未知樣本進行分類，并且使錯誤最小化。
由于函數間隔可以根據ω和b等比例地放大和縮小，而幾何間隔不會，故選擇幾何間隔作為要最大化的間隔距離。為使間隔最大化，問題可以表示為在式(2)的條件下求式(1)的最小化問題。
求得最優解ω′、b′，得到超平面ω′·x+b′=0即最大間隔分離面。
樣本線性不可分時，存在某些樣本點(xi，yi)不能滿足函數間隔大于等于1的約束條件(2)。為此，在每個樣本點(x，yi)加入一個松弛變量δi≥0，約束條件變為
yi(ω·xi+b)≥1-δi
同時，對每個松弛變量δi添加一個代價δi，故問題轉化為：
δi≥0，i=1，2，…，N(5)
這里C為懲罰因子，根據具體問題而定。
1.2SVM的多分類方法
上文提到的SVM的多分類方法(2)未能得到廣泛應用，故這里只對方法(1)進行闡述。將多分類問題轉化為多個SVM直接可解的二分類問題，主要有“oneagainstrest”(1ar)、“oneagainstone”(1a1)和DAG SVM［5］。
1ar方法構建k個二類分類器，每個分類器都是其中一類（正類）對其他所有類（負類）。分類時，分別計算各個分類器的決策函數值，取測試函數值最大的對應類別為測試數據類別［6］。該方法在分類時需使用k個判別函數進行判別。當訓練樣本較大時，訓練較為困難［7］。
1a1方法由KNERR提出，該方法對k類的每兩個類構造一個分類器，共構造k(k-1)/2個子分類器。對未知樣本分類時，每個子分類器都進行判別，故需使用k(k-1)/2個判別函數進行判別，結果對相應類別投一票，最終統計得票數，票數最多的類為未知樣本所屬類別。由于測試時要對任意類進行比較，訓練和預測速度隨類別數成指數增長［8］。
DAGSVMS方法由PLATT J C等人提出的決策導向的循環圖DDAG導出，是針對1vs1SVMS存在誤分、拒分現象提出的［9］。該算法在訓練階段也要構造k(k-1)/2個子分類器，這些子分類器構成一個有向無環圖。分類時，首先從頂節點開始，根據分類結果進入下一層節點，繼續分類直到葉節點。該方法在分類時需使用k-1個判別函數進行判別。由于它采取的是排除策略，如果在開始階段就決策錯誤的話，那么后面的步驟都沒有意義了［10］。圖1是采用DAGSVM對4類樣本分類決策過程示意圖。
2基于冒泡的多分類思想
本文提出一種冒泡的SVM多分類方法，其受啟發于排序算法中的冒泡排序。在冒泡排序算法中，內層循環是大者上浮或小數下沉（這里用大數據上?。瑢⒈敬蚊芭葜凶畲蟮臄抵饾u上冒，放到最大的位置。如圖2所示，在第一次冒泡中，第一個節點值為4大于第二個節點，故節點4上冒；下一次冒泡中，第二個節點4大于第三節點1，值4節點繼續上冒，依次下去，一輪完成后最大值冒到最右邊位置，即找到圖2例中的值為6的節點為最大值。
相對于具體數值而言，SVM多分類中的每個類別沒有具體的值，但是兩個類別之間的大小關系是可以區分的，即為一個SVM的二分類結果。即如果有一個待預測數據x，使用類別1和類別2訓練樣本訓練出來的分類模型對其進行分類，分類器將其分類為類別2，筆者認為針對于樣本x而言，類2大于類1。有了相對大小之后，就可以像冒泡排序那樣進行冒泡了，一輪下來，針對樣本x的最大的類別yi冒到最右端，則認為x屬于yi。
如圖3所示，類別標簽從1~6，類別標簽后邊的值是針對待分類樣本x各個類別之間的相對虛擬值。如此圖分類下來，最終樣本x被分類為類別5。
若多分類類別有C個，則需要進行C-1個SVM二分類來對一個樣本進行分類，這同DAG SVM是一樣的。同時，與1a1和DAG SVM的分類方法一樣，該方法需要訓練出C·(C-1)/2個分類模型。從算法訓練和分類計算復雜度來說，該方法與DAG SVM相同。
同時該方法可以對類別分組冒泡，即先將所有類別分成若干組，每個組分別冒泡，從每個組中選出改組中相對樣本x最大的組，然后將每組中選出的類別再分組，再從每組中選出最大類別，如此進行下去，直到最后選出所有組的最大類別標簽，即是樣本x的類別。仍用上邊的例子，如圖4所示，將6個類別分成兩組，類標簽為1、2、3的為一組，類標簽為4、5、6為一組，第一組冒泡分類，選出類1，第二組冒泡分類選出類5，然后類1和類5再進行SVM二分類，最終選出類5，則樣本x被分為第5類。
圖4分組冒泡多分類方法這樣分組的好處是可以使分類算法并行進行分類，加快分類速度。如上例，第一組和第二組的冒泡過程各自獨立，可以進行多個線程或者多個進程的并行執行，最后將各自的結果匯總再分類。這種方法可以充分利用現在計算機多核和多臺計算機并行運算的特點。
3實驗及結果分析
為了比較1-a-1與冒泡 SVM多分類方法的性能，選取了UCI機器學習數據庫中3個數據集進行試驗，3個數據集分別為iris、wine和glass。表1列出了數據集實例數、屬性數和類個數。表1數據集信息數據集實例數類個數屬性數iris15035wine178314glass214610LibSVM庫已被廣泛應用到多個領域［11］。實驗使用了LibSVM(版本3.2)庫進行SVM二分類的訓練和預測。為了減小實驗誤差，實驗中沒有使用LibSVM自身的1-a-1多分類，而是分別重寫1-a-1和冒泡函數，它們都調用LibSVM庫的基本二分類算法。訓練時使用的SVM類型為LibSVM的CSVC，其中設C=4，其他均為默認值。實驗使用所選數據集的2/3做訓練數據，剩下的1/3留做預測數據，最后由運行結果對1-a-1與冒泡的預測時間和分類精確度進行了對比。實驗結果見表2，表中為根據以上方法對1-a-1與冒泡多分類方法的預測時間和正確率的對比。
實驗結果表明，冒泡的多分類方法可以在輕微影響分類正確率的情況下極大地降低新樣本的預測時間。理論上看，冒泡多分類方法在訓練上與1-a-1方法相同，而在預測新樣本時，二分類次數由C(C-1)/2降低為C-1，從而減少了預測分類時間。
4結論
本文提出的冒泡SVM多分類方法受啟發于排序算法中的冒泡排序方法，多類分類時較1a1方法有較少的二分類次數，減少了分類時間，同時其分組冒泡分類更可以利用現在計算機并行計算的特點提高分類效率。該方法的一個缺點是，分類時如果有一個二分類結果錯誤，則最終結果就會錯誤，有待進一步改進。
參考文獻
?。?］ VLADIMIR N V. An overview of statistical learning theory［J］. IEEE Transactions on Neural Networks, 1999,10(5):988989.
［2］ 李航. 統計學習方法［M］. 北京：清華大學出版社, 2012.
?。?］ 奉國和. 四種分類方法性能比較［J］. 計算機工程與應用，2011,47(8):2526，145.
?。?］ 楊國鵬,余旭初,陳偉，等. 基于核Fisher判別分析的高光譜遙感影像分類［J］. 遙感學報， 2008，12(4):579585.
［5］ 周愛武, 溫春林, 王浩. 基于二叉樹的SVM多類分類的研究與改進［J］. 微型機與應用, 2013, 32(12):6769.
［6］ 劉勇,全廷偉. 基于DAGSVMS的SVM多類分類方法［J］. 統計與決策, 2007(20):146148.
?。?］ VOJTECH F,VACLAV H.Multiclass support vector machine［C］. Proceedings of the 16th International Conference on Pattern Recognition， 2002:236239.