孫少乙1,2，黃志波1

　　（1.華北計(jì)算機(jī)系統(tǒng)工程研究所，北京 100083；2.中電和瑞科技有限公司，北京 100083)

       摘要：為了使用支持向量機(jī)(SVM)算法進(jìn)行多類分類，在SVM二分類基礎(chǔ)上，提出使用排序算法中冒泡排序的思想進(jìn)行SVM多類別數(shù)據(jù)分類。使用該方法在選取的UCI數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，結(jié)果表明，在保證較高正確率的情況下，相對(duì)傳統(tǒng)一對(duì)一的多分類方法，該方法較大幅地減少了分類時(shí)間，是一種應(yīng)用性較強(qiáng)的SVM多類分類方法。

　　關(guān)鍵詞：支持向量機(jī)；多類分類；冒泡排序； LibSVM

0引言

　　支持向量機(jī)(Support Vector Machine，SVM) 是一種在統(tǒng)計(jì)學(xué)習(xí)基礎(chǔ)上發(fā)展起來(lái)的機(jī)器學(xué)習(xí)方法，其最大特點(diǎn)是根據(jù)Vapnik結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則［1］。它的基本模型是定義在特征空間上的間隔最大的線性分類器［2］，在解決小樣本、非線性及高維度等問(wèn)題上具有傳統(tǒng)的機(jī)器學(xué)習(xí)方法所不具備的優(yōu)勢(shì)［3］。SVM本是針對(duì)二分類問(wèn)題提出的，如何將其應(yīng)用到多類分類問(wèn)題將成為對(duì)SVM研究的重要問(wèn)題之一。當(dāng)前，對(duì)于SVM的多分類問(wèn)題，解決思路有兩種：(1)將問(wèn)題轉(zhuǎn)化為SVM直接可解的問(wèn)題；(2)適當(dāng)改變?cè)糞VM中最優(yōu)化問(wèn)題，使之成為能同時(shí)計(jì)算出所有分類決策問(wèn)題的決策函數(shù)，從而一次性實(shí)現(xiàn)多分類。其中方法（2）看似簡(jiǎn)單，但由于其問(wèn)題最優(yōu)化求解過(guò)程太過(guò)復(fù)雜，計(jì)算量太大，實(shí)現(xiàn)困難，未得到廣泛應(yīng)用［4］。故當(dāng)前多分類主要采用的是方法（1）的思想。

1SVM原理及多分類方法

　　1.1SVM分類原理

　　假設(shè)給定一個(gè)特征空間的含有N個(gè)樣本的訓(xùn)練數(shù)據(jù)集T={(X1, Y1)，(X2, Y2)，…，(XN, YN)}，其中，Xi∈Rn，Yi∈{+1，-1}，i=1,2,3，…，N，Xi為第i個(gè)特征向量，Yi為Xi的類標(biāo)記，即Yi=+1時(shí)，Xi為正例，Yi=-1時(shí)，Xi為反例。SVM就是要找到一個(gè)超平面ω·X+b=0，能將兩類樣本分開(kāi)，并且超平面距兩類樣本的間隔最大，這樣可以將超平面用于對(duì)未知樣本進(jìn)行分類，并且使錯(cuò)誤最小化。

　　由于函數(shù)間隔可以根據(jù)ω和b等比例地放大和縮小，而幾何間隔不會(huì)，故選擇幾何間隔作為要最大化的間隔距離。為使間隔最大化，問(wèn)題可以表示為在式(2)的條件下求式(1)的最小化問(wèn)題。

　　求得最優(yōu)解ω′、b′，得到超平面ω′·x+b′=0即最大間隔分離面。

　　樣本線性不可分時(shí)，存在某些樣本點(diǎn)(xi，yi)不能滿足函數(shù)間隔大于等于1的約束條件(2)。為此，在每個(gè)樣本點(diǎn)(x，yi)加入一個(gè)松弛變量δi≥0，約束條件變?yōu)?/p>

　　yi(ω·xi+b)≥1-δi

　　同時(shí)，對(duì)每個(gè)松弛變量δi添加一個(gè)代價(jià)δi，故問(wèn)題轉(zhuǎn)化為：

　　δi≥0，i=1，2，…，N(5)

　　這里C為懲罰因子，根據(jù)具體問(wèn)題而定。

　　1.2SVM的多分類方法

　　上文提到的SVM的多分類方法(2)未能得到廣泛應(yīng)用，故這里只對(duì)方法(1)進(jìn)行闡述。將多分類問(wèn)題轉(zhuǎn)化為多個(gè)SVM直接可解的二分類問(wèn)題，主要有“oneagainstrest”(1ar)、“oneagainstone”(1a1)和DAG SVM［5］。

　　1ar方法構(gòu)建k個(gè)二類分類器，每個(gè)分類器都是其中一類（正類）對(duì)其他所有類（負(fù)類）。分類時(shí)，分別計(jì)算各個(gè)分類器的決策函數(shù)值，取測(cè)試函數(shù)值最大的對(duì)應(yīng)類別為測(cè)試數(shù)據(jù)類別［6］。該方法在分類時(shí)需使用k個(gè)判別函數(shù)進(jìn)行判別。當(dāng)訓(xùn)練樣本較大時(shí)，訓(xùn)練較為困難［7］。

　　1a1方法由KNERR提出，該方法對(duì)k類的每?jī)蓚€(gè)類構(gòu)造一個(gè)分類器，共構(gòu)造k(k-1)/2個(gè)子分類器。對(duì)未知樣本分類時(shí)，每個(gè)子分類器都進(jìn)行判別，故需使用k(k-1)/2個(gè)判別函數(shù)進(jìn)行判別，結(jié)果對(duì)相應(yīng)類別投一票，最終統(tǒng)計(jì)得票數(shù)，票數(shù)最多的類為未知樣本所屬類別。由于測(cè)試時(shí)要對(duì)任意類進(jìn)行比較，訓(xùn)練和預(yù)測(cè)速度隨類別數(shù)成指數(shù)增長(zhǎng)［8］。

　　DAGSVMS方法由PLATT J C等人提出的決策導(dǎo)向的循環(huán)圖DDAG導(dǎo)出，是針對(duì)1vs1SVMS存在誤分、拒分現(xiàn)象提出的［9］。該算法在訓(xùn)練階段也要構(gòu)造k(k-1)/2個(gè)子分類器，這些子分類器構(gòu)成一個(gè)有向無(wú)環(huán)圖。分類時(shí)，首先從頂節(jié)點(diǎn)開(kāi)始，根據(jù)分類結(jié)果進(jìn)入下一層節(jié)點(diǎn)，繼續(xù)分類直到葉節(jié)點(diǎn)。該方法在分類時(shí)需使用k-1個(gè)判別函數(shù)進(jìn)行判別。由于它采取的是排除策略，如果在開(kāi)始階段就決策錯(cuò)誤的話，那么后面的步驟都沒(méi)有意義了［10］。圖1是采用DAGSVM對(duì)4類樣本分類決策過(guò)程示意圖。

2基于冒泡的多分類思想

　　本文提出一種冒泡的SVM多分類方法，其受啟發(fā)于排序算法中的冒泡排序。在冒泡排序算法中，內(nèi)層循環(huán)是大者上浮或小數(shù)下沉（這里用大數(shù)據(jù)上?。?，將本次冒泡中最大的數(shù)逐漸上冒，放到最大的位置。如圖2所示，在第一次冒泡中，第一個(gè)節(jié)點(diǎn)值為4大于第二個(gè)節(jié)點(diǎn)，故節(jié)點(diǎn)4上冒；下一次冒泡中，第二個(gè)節(jié)點(diǎn)4大于第三節(jié)點(diǎn)1，值4節(jié)點(diǎn)繼續(xù)上冒，依次下去，一輪完成后最大值冒到最右邊位置，即找到圖2例中的值為6的節(jié)點(diǎn)為最大值。

　　相對(duì)于具體數(shù)值而言，SVM多分類中的每個(gè)類別沒(méi)有具體的值，但是兩個(gè)類別之間的大小關(guān)系是可以區(qū)分的，即為一個(gè)SVM的二分類結(jié)果。即如果有一個(gè)待預(yù)測(cè)數(shù)據(jù)x，使用類別1和類別2訓(xùn)練樣本訓(xùn)練出來(lái)的分類模型對(duì)其進(jìn)行分類，分類器將其分類為類別2，筆者認(rèn)為針對(duì)于樣本x而言，類2大于類1。有了相對(duì)大小之后，就可以像冒泡排序那樣進(jìn)行冒泡了，一輪下來(lái)，針對(duì)樣本x的最大的類別yi冒到最右端，則認(rèn)為x屬于yi。

　　如圖3所示，類別標(biāo)簽從1~6，類別標(biāo)簽后邊的值是針對(duì)待分類樣本x各個(gè)類別之間的相對(duì)虛擬值。如此圖分類下來(lái)，最終樣本x被分類為類別5。

　　若多分類類別有C個(gè)，則需要進(jìn)行C-1個(gè)SVM二分類來(lái)對(duì)一個(gè)樣本進(jìn)行分類，這同DAG SVM是一樣的。同時(shí)，與1a1和DAG SVM的分類方法一樣，該方法需要訓(xùn)練出C·(C-1)/2個(gè)分類模型。從算法訓(xùn)練和分類計(jì)算復(fù)雜度來(lái)說(shuō)，該方法與DAG SVM相同。

　　同時(shí)該方法可以對(duì)類別分組冒泡，即先將所有類別分成若干組，每個(gè)組分別冒泡，從每個(gè)組中選出改組中相對(duì)樣本x最大的組，然后將每組中選出的類別再分組，再?gòu)拿拷M中選出最大類別，如此進(jìn)行下去，直到最后選出所有組的最大類別標(biāo)簽，即是樣本x的類別。仍用上邊的例子，如圖4所示，將6個(gè)類別分成兩組，類標(biāo)簽為1、2、3的為一組，類標(biāo)簽為4、5、6為一組，第一組冒泡分類，選出類1，第二組冒泡分類選出類5，然后類1和類5再進(jìn)行SVM二分類，最終選出類5，則樣本x被分為第5類。

　　圖4分組冒泡多分類方法這樣分組的好處是可以使分類算法并行進(jìn)行分類，加快分類速度。如上例，第一組和第二組的冒泡過(guò)程各自獨(dú)立，可以進(jìn)行多個(gè)線程或者多個(gè)進(jìn)程的并行執(zhí)行，最后將各自的結(jié)果匯總再分類。這種方法可以充分利用現(xiàn)在計(jì)算機(jī)多核和多臺(tái)計(jì)算機(jī)并行運(yùn)算的特點(diǎn)。

3實(shí)驗(yàn)及結(jié)果分析

　　為了比較1-a-1與冒泡 SVM多分類方法的性能，選取了UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中3個(gè)數(shù)據(jù)集進(jìn)行試驗(yàn)，3個(gè)數(shù)據(jù)集分別為iris、wine和glass。表1列出了數(shù)據(jù)集實(shí)例數(shù)、屬性數(shù)和類個(gè)數(shù)。表1數(shù)據(jù)集信息數(shù)據(jù)集實(shí)例數(shù)類個(gè)數(shù)屬性數(shù)iris15035wine178314glass214610LibSVM庫(kù)已被廣泛應(yīng)用到多個(gè)領(lǐng)域［11］。實(shí)驗(yàn)使用了LibSVM(版本3.2)庫(kù)進(jìn)行SVM二分類的訓(xùn)練和預(yù)測(cè)。為了減小實(shí)驗(yàn)誤差，實(shí)驗(yàn)中沒(méi)有使用LibSVM自身的1-a-1多分類，而是分別重寫1-a-1和冒泡函數(shù)，它們都調(diào)用LibSVM庫(kù)的基本二分類算法。訓(xùn)練時(shí)使用的SVM類型為L(zhǎng)ibSVM的CSVC，其中設(shè)C=4，其他均為默認(rèn)值。實(shí)驗(yàn)使用所選數(shù)據(jù)集的2/3做訓(xùn)練數(shù)據(jù)，剩下的1/3留做預(yù)測(cè)數(shù)據(jù)，最后由運(yùn)行結(jié)果對(duì)1-a-1與冒泡的預(yù)測(cè)時(shí)間和分類精確度進(jìn)行了對(duì)比。實(shí)驗(yàn)結(jié)果見(jiàn)表2，表中為根據(jù)以上方法對(duì)1-a-1與冒泡多分類方法的預(yù)測(cè)時(shí)間和正確率的對(duì)比。

　　實(shí)驗(yàn)結(jié)果表明，冒泡的多分類方法可以在輕微影響分類正確率的情況下極大地降低新樣本的預(yù)測(cè)時(shí)間。理論上看，冒泡多分類方法在訓(xùn)練上與1-a-1方法相同，而在預(yù)測(cè)新樣本時(shí)，二分類次數(shù)由C(C-1)/2降低為C-1，從而減少了預(yù)測(cè)分類時(shí)間。

4結(jié)論

　　本文提出的冒泡SVM多分類方法受啟發(fā)于排序算法中的冒泡排序方法，多類分類時(shí)較1a1方法有較少的二分類次數(shù)，減少了分類時(shí)間，同時(shí)其分組冒泡分類更可以利用現(xiàn)在計(jì)算機(jī)并行計(jì)算的特點(diǎn)提高分類效率。該方法的一個(gè)缺點(diǎn)是，分類時(shí)如果有一個(gè)二分類結(jié)果錯(cuò)誤，則最終結(jié)果就會(huì)錯(cuò)誤，有待進(jìn)一步改進(jìn)。

參考文獻(xiàn)

　?。?］ VLADIMIR N V. An overview of statistical learning theory［J］. IEEE Transactions on Neural Networks, 1999,10(5):988989.

　?。?］ 李航. 統(tǒng)計(jì)學(xué)習(xí)方法［M］. 北京：清華大學(xué)出版社, 2012.

　　［3］ 奉國(guó)和. 四種分類方法性能比較［J］. 計(jì)算機(jī)工程與應(yīng)用，2011,47(8):2526，145.

　?。?］ 楊國(guó)鵬,余旭初,陳偉，等. 基于核Fisher判別分析的高光譜遙感影像分類［J］. 遙感學(xué)報(bào)， 2008，12(4):579585.

　?。?］ 周愛(ài)武, 溫春林, 王浩. 基于二叉樹(shù)的SVM多類分類的研究與改進(jìn)［J］. 微型機(jī)與應(yīng)用, 2013, 32(12):6769.

　?。?］ 劉勇,全廷偉. 基于DAGSVMS的SVM多類分類方法［J］. 統(tǒng)計(jì)與決策, 2007(20):146148.

　?。?］ VOJTECH F,VACLAV H.Multiclass support vector machine［C］. Proceedings of the 16th International Conference on Pattern Recognition， 2002:236239.