郭亞琴 王正群

摘 要:提出一種新的基于二叉樹結(jié)構(gòu)的支持向量機(jī)(SVM)多類分類方法。該方法解決了現(xiàn)有主要算法中存在的不可分區(qū)域問(wèn)題,具有簡(jiǎn)單、直觀、重復(fù)訓(xùn)練樣本少的優(yōu)點(diǎn)。為了提高分類模型的推廣能力,必須使樣本分布好的類處于二叉樹的上層節(jié)點(diǎn),才能獲得更大的劃分空間。因此,該算法采用類間散布度量與類內(nèi)散布度量的比值作為二叉樹的生成算法。采用UCI標(biāo)準(zhǔn)數(shù)據(jù)集實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果表明該算法具有一定的優(yōu)越性。

關(guān)鍵詞:支持向量機(jī);多類分類;二叉樹;多類支持向量機(jī)

中圖分類號(hào):TP391文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):1004-373X(2009)20-143-04

Improved Multiclass Classification Methods for Support Vector Machine

GUO Yaqin1,WANG Zhengqun2

(1.ZiLang Vocational Technical College,Nantong,226002,China;2.School of Information Engineering,Yangzhou University,Yangzhou,225009,China)

Abstract:The multiclass SVM methods based on binary tree are proposed.The new method can resolve the unclassifiable region problems in the conventional multiclass SVM method,it is simple and has little duplicating training samples.To maintain high generalization ability,the most widespread class should be separated at the upper nodes of a binary tree.The ratio of between-class scatter and within-class scatter is used to be rules of constructing binary tree.Numerical experiment results show that the multiclass SVM methods are suitable for practical use.

Keywords:support vector machines;multiclass classification;binary tree;multiclass support vector machine

0 引 言

支持向量機(jī)(Support Vector Machine,SVM)方法最初是針對(duì)二類模式分類而提出的,如何將其有效地推廣到多類別分類仍是當(dāng)前支持向量機(jī)研究的重要內(nèi)容之一。目前,對(duì)于多類分類問(wèn)題,SVM的解決途徑有兩種:

(1) 通過(guò)構(gòu)造多個(gè)SVM二值分類器并將它們組合起來(lái)實(shí)現(xiàn)多類分類,例如one-versus-rest[1],one-versus-one和DAGSVM[2],雖然這三種方法是目前最常用且性能較優(yōu)的,但one-versus-rest和one-versus-one方法的泛化誤差是無(wú)界的。再者one-versus-one所需構(gòu)造的子分類器的數(shù)量關(guān)于類別數(shù)k成超線性增長(zhǎng),共k(k-1)/2個(gè),且在分類階段,都必須計(jì)算所有子分類判據(jù)函數(shù)。one-versus-one方法還有一個(gè)最明顯的缺點(diǎn)是,每個(gè)子分類器都要非常仔細(xì)的調(diào)整,如果某個(gè)子分類器不規(guī)范化,則整個(gè)分類系統(tǒng)將趨于過(guò)學(xué)習(xí)。DAGSVM方法解決了不可分區(qū)域問(wèn)題,而且不一定要計(jì)算所有的子分類判決函數(shù),但各個(gè)子分類器在有向無(wú)環(huán)圖中的位置也會(huì)對(duì)分類系統(tǒng)產(chǎn)生較大的影響。

(2) 直接在一個(gè)優(yōu)化公式中同時(shí)考慮所有子分類器的參數(shù)優(yōu)化。嚴(yán)格的講,它的思想類似于one-versus -rest方法,只不過(guò)是把k個(gè)二值SVM優(yōu)化問(wèn)題放在一個(gè)最優(yōu)化公式中同時(shí)優(yōu)化,所以它也存在one-versus-rest方法相同的缺點(diǎn)。另外,這種思想盡管看起來(lái)簡(jiǎn)潔,但在最優(yōu)化問(wèn)題求解過(guò)程中的變量遠(yuǎn)遠(yuǎn)多于第1種,訓(xùn)練速度不及第1種,且在分類精度上也不占優(yōu)[3]。當(dāng)訓(xùn)練樣本數(shù)非常大時(shí),這一問(wèn)題更加突出。因此,在對(duì)現(xiàn)有主要的SVM多類分類算法作簡(jiǎn)單介紹的基礎(chǔ)上,提出了新的基于二叉樹的SVM多類分類方法,該方法采用類間散布度量與類內(nèi)散布度量的比值作為二叉樹的生成算法,并通過(guò)一系列實(shí)驗(yàn)分析、比較了各種算法的特點(diǎn)。

1 多類SVM分類和基于二叉樹的多類SVM

1.1 多類SVM分類方法簡(jiǎn)介

利用SVM解決多類分類問(wèn)題,目前主要有兩種途徑:把多個(gè)2-類SVM分類器進(jìn)行組合,研究的內(nèi)容包括對(duì)組合方式的改進(jìn)以及對(duì)每個(gè)2-類SVM分類器的改進(jìn);利用Weston等人提出的將2-類SVM從優(yōu)化公式直接進(jìn)行推廣,研究的內(nèi)容包括如何將2-類SVM的一些有效的改進(jìn)措施引入到這種方法。目前,在解決多類問(wèn)題時(shí),一對(duì)多(one-versus-rest)和一對(duì)一(one-versus-one)[1]方法應(yīng)用較為廣泛。

(1) 一對(duì)多 (one-versus-rest,1-v-r)

對(duì)于k-類分類問(wèn)題,構(gòu)造k個(gè)2-類SVM分類器,每一類對(duì)應(yīng)其中的一個(gè),將它與其他的類分開(kāi);其中第i個(gè)2-類SVM分類器是把第i類中的樣本都標(biāo)記為+1,而其他所有的樣本都標(biāo)記為-1。也就是說(shuō),第i個(gè)2-類SVM分類器所構(gòu)造的分類超平面(separating hyperplane),把第i類與其他的(i-1)類分割開(kāi)。這種類型的多類SVM一般稱為1-v-r(它是one-versus-rest的縮寫形式)型SVM。分類時(shí),將待識(shí)樣本模式分別計(jì)算對(duì)應(yīng)于各個(gè)2-類分類器的決策函數(shù)值,并選擇最大的函數(shù)值所對(duì)應(yīng)的類別為待識(shí)樣本模式的所屬類別。

(2) 一對(duì)一 (one-versus-one,1-v-1)

首先構(gòu)造所有可能的2-類SVM分類器,每一個(gè)分類器的訓(xùn)練數(shù)據(jù)集都只取自相應(yīng)的兩類。這時(shí)共需要構(gòu)造N=k(k-1)/2個(gè)2-類SVM分類器。在構(gòu)造第i類與第j類之間的2-類SVM分類器時(shí),訓(xùn)練集中的數(shù)據(jù)只來(lái)自相應(yīng)的兩類,并將第i類與第j類內(nèi)的點(diǎn)分別標(biāo)記為+1和-1。在分類時(shí),將待識(shí)樣本模式分別代入上述的N=k(k-1)/2個(gè)2-類分類器進(jìn)行分類,累計(jì)各類別的得分,選擇得分最高者所對(duì)應(yīng)的類別為待識(shí)樣本模式的所屬類別。

1.2 基于二叉樹的多類SVM

基于二叉樹的多類SVM是先將所有類別分成兩個(gè)子類,再將子類進(jìn)一步劃分成兩個(gè)次級(jí)子類,如此循環(huán)下去,直到所有的節(jié)點(diǎn)都只包含一個(gè)單獨(dú)的類別為止,此節(jié)點(diǎn)也是決策樹中的葉子。該方法將原有的多類問(wèn)題同樣分解成了一系列的兩類分類問(wèn)題,其中兩個(gè)子類間的分類函數(shù)采用SVM。二叉樹方法可以避免傳統(tǒng)方法的不可分情況,并且只需構(gòu)造k-1個(gè)SVM分類器,分類時(shí)并不一定需要計(jì)算所有的分類器判別函數(shù),從而可節(jié)省分類時(shí)間。

二叉樹的結(jié)構(gòu)對(duì)整個(gè)分類模型的分類精度有較大的影響。圖1是一個(gè)4類問(wèn)題的不同的二叉樹法構(gòu)造示意圖。在圖1(a)中,第1個(gè)分割面是由第1類和第2、第3、第4類構(gòu)成,第2個(gè)分割面是由第2類和第3、第4類構(gòu)成,最后一個(gè)分割面是由第3類和第4類構(gòu)成;而圖1(b)的分割順序是第2類,第1類,第3類。從此例可看出,分割順序不一樣,每個(gè)類的分割區(qū)域也不同。因此,多類SVM方法的每個(gè)類的區(qū)域依賴于二叉樹的結(jié)構(gòu),主要是二叉樹節(jié)點(diǎn)所代表的二值SVM分類器的位置。

圖1 四類問(wèn)題的不同劃分順序

二叉樹的結(jié)構(gòu)有兩種:一種是在每個(gè)內(nèi)節(jié)點(diǎn)處,由一個(gè)類與剩下的類構(gòu)造分割面;另一種是在內(nèi)節(jié)點(diǎn)處,可以是多個(gè)類與多個(gè)類的分割。這里只考慮前一種情況,即每次分割只分割出一個(gè)類?；诙鏄涞亩囝怱VM,在測(cè)試階段類似DAGSVM,從根節(jié)點(diǎn)開(kāi)始計(jì)算決策函數(shù),根據(jù)值的正負(fù)決定下一節(jié)點(diǎn)如此下去,直到到達(dá)某一葉節(jié)點(diǎn)為止,此葉節(jié)點(diǎn)所代表的類別就是測(cè)試樣本的所屬類別。

目前,基于二叉樹的多類SVM分類方法已有學(xué)者提出,文獻(xiàn)[4-7]的基本思想都是基于二叉樹的分類。但這些方法不是隨機(jī)地生成二叉樹,就是采用二叉樹生成算法并不能很好地提高整個(gè)分類模型的推廣能力。從前面的分析可看出,越上層節(jié)點(diǎn)的分類性能對(duì)整個(gè)分類模型的推廣性影響越大。因此在生成二叉樹的過(guò)程中,應(yīng)該讓最易分割的類最早分割出來(lái),即在二叉樹的上層節(jié)點(diǎn)處分割?；诖?提出根據(jù)訓(xùn)練樣本在屬性空間的分布情況來(lái)生成二叉樹的方法,從而建立一個(gè)推廣性高的多類SVM分類模型。由于支持向量機(jī)的思想是在樣本的屬性空間中構(gòu)造最優(yōu)超平面,線性SVM的屬性空間等價(jià)于輸入空間,但非線性的SVM卻無(wú)法得到具體的屬性空間表達(dá)式。事實(shí)上,樣本在輸入空間中的物理聯(lián)系在屬性空間也同樣存在。所以,只需在輸入空間中考慮樣本的分布情況。

2 改進(jìn)的多分類二叉樹法

節(jié)點(diǎn)的位置。為了提高分類模型的推廣能力,必須利用合理的策略來(lái)生成二叉樹結(jié)構(gòu)。所以,提出以類樣本分布情況作為二叉樹的生成算法,從而構(gòu)造推廣能力好的基于二叉樹的SVM多類分類模型。改進(jìn)算法的基本思想就是在每次生成二叉樹內(nèi)節(jié)點(diǎn)時(shí),選擇最易分割的情況來(lái)構(gòu)造當(dāng)前節(jié)點(diǎn)的二值SVM。

分割順序不一樣,每個(gè)類的分割區(qū)域是不同的,先分割出來(lái)的類更容易有較大的分割區(qū)域。為了讓分布好的類擁有較大的分割區(qū)域,就應(yīng)把這些類最先分割出來(lái)。因?yàn)楦黝悢?shù)據(jù)的真實(shí)分布無(wú)法得知,所以用有限樣本數(shù)據(jù)的分布來(lái)對(duì)真實(shí)分布做近似估計(jì)。樣本分布情況的度量采用了類間分布度量與類內(nèi)分布度量的比值作為判別標(biāo)準(zhǔn)。圖2(a)為3類樣本數(shù)據(jù)的二維輸入空間分布圖,直觀上看,最好的分割順序?yàn)?先以第1類與其他類構(gòu)造分割超平面,然后是第2與第3類構(gòu)造分割超平面,這主要是考慮到各類樣本在空間的分布情況。

圖2 樣本分布和分割示意圖

定義1(類內(nèi)散布度量) 設(shè)類S有n個(gè)d維樣本向量x1,x2,…,xn,xi∈Rd,m為類S的樣本均值向量,類內(nèi)分布度量為:

Dw=1n∑ni=1‖xi-m‖(1)

式中,‖?‖表示歐式距離,其中m=1n∑ni=1xi。

二叉樹多類分類法的每個(gè)類的區(qū)域依賴于二叉樹的生成順序,主要是二值SVM分類器所在的類。

定義2(類間散布度量) 設(shè)樣本類別數(shù)為k,樣本均值向量分別為m1,m2,…,mk,對(duì)于第i類樣本類間分布度量為:

Db=1C-1∑k-1j=1‖mi-mj‖,且i≠j(2)

定義3(類散布度量) 設(shè)樣本類別數(shù)為c,第i類樣本的分布度量為:

Di=Dib/Diw(3)

式中:Dib和Diw分別表示第i類樣本的類間散布度量和類內(nèi)散布度量。

具體的算法流程為:

Step 1:根據(jù)式(3)計(jì)算各類樣本數(shù)據(jù)的類散布度量Di(i=1,2,…,k);

Step 2:根據(jù)各類的散布度量由大到小的順序,對(duì)類別進(jìn)行排序。當(dāng)存在兩個(gè)或兩個(gè)以上的類別具有相同類散布度量時(shí),把類標(biāo)號(hào)小的類排在前面。最后得到所有類別的排列n1,n2,…,nk;此處ni∈{1,2,…,k},i=1,2,…,k為類標(biāo)號(hào);

Step 3:利用二值分類的SVM訓(xùn)練算法構(gòu)造二叉樹各內(nèi)節(jié)點(diǎn)的最優(yōu)超平面。在根節(jié)點(diǎn)處,從樣本集中選擇第n1類樣本為正樣本集,其他樣本為負(fù)樣本集,利用SVM訓(xùn)練算法構(gòu)造最優(yōu)超平面,然后把屬于第n1類的樣本從樣本集中刪除。在第2個(gè)節(jié)點(diǎn)處從樣本集中選擇第n2類樣本為正樣本集,其他剩余的樣本為負(fù)樣本集,利用SVM訓(xùn)練算法構(gòu)造最優(yōu)超平面,然后把屬于第n2類的樣本從樣本集中刪除。依次下去,最終可得到基于二叉樹的多類別SVM分類模型;

Step 4:算法結(jié)束。

3 實(shí)驗(yàn)比較

3.1 實(shí)驗(yàn)數(shù)據(jù)

為了比較多種SVM算法的性能,在UCI機(jī)器學(xué)習(xí)庫(kù)[8]中選用了7個(gè)數(shù)據(jù)集,分別是zoo,iris,wine,waveform,Segment,Backup,Glassdata,選用的7個(gè)數(shù)據(jù)集中,既有多類別大樣本數(shù)據(jù)集,又有多類別小樣本數(shù)據(jù)集。表1列出了實(shí)驗(yàn)使用的每個(gè)數(shù)據(jù)集的實(shí)例個(gè)數(shù)、類個(gè)數(shù)、屬性個(gè)數(shù)等數(shù)據(jù)信息。

表1 數(shù)據(jù)集的構(gòu)成描述

數(shù)據(jù)集實(shí)例個(gè)數(shù)類個(gè)數(shù)屬性個(gè)數(shù)

zoo101717

iris15035

wine178314

wave5 000322

Segment2 100719

GlassData214610

Backup3051836

3.2 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)中,懲罰參數(shù)C=100,核函數(shù)使用徑向基核函數(shù)K(xi,xj)=exp(-‖xi-xj‖2/2γ2)。為了使實(shí)驗(yàn)更具有說(shuō)服力,每個(gè)算法在實(shí)現(xiàn)過(guò)程中,核函數(shù)中的參數(shù)使用幾個(gè)不同的值,采用5倍交叉驗(yàn)證法進(jìn)行比較,表2列出了這3種方法的識(shí)別率和分類時(shí)間的比較,由實(shí)驗(yàn)結(jié)果可以看出,基于二叉樹的多類分類算法與one-versus-one和one-versus-rest相比,識(shí)別率都有了提高。

表2中時(shí)間是5次實(shí)驗(yàn)的平均值,時(shí)間是以程序運(yùn)行的CPU時(shí)間為準(zhǔn),單位為s。從表2可以看出,本文算法的時(shí)間與one-versus-one和one-versus-rest相比,都有了明顯減少,因?yàn)槎鏄錅y(cè)試樣本時(shí)并不需要計(jì)算所有的二值分類器。one-versus-one方法的支持向量個(gè)數(shù)遠(yuǎn)遠(yuǎn)多于其他的算法,這是因?yàn)槠涿總€(gè)子分類器都需利用到所有的訓(xùn)練樣本,構(gòu)造的分類面較其他算法復(fù)雜。one-versus-one和one-versus-rest的時(shí)間相對(duì)較長(zhǎng),是因?yàn)檫@兩種方法必須計(jì)算所有的二值SVM分類器判別函數(shù),且one-versus-one的總支持向量數(shù)較多,使得其時(shí)間更長(zhǎng)。

表2 三種方法的實(shí)驗(yàn)結(jié)果

數(shù)據(jù)集參數(shù)

1-v-r1-v-1本文方法

識(shí)別率分類時(shí)間/s識(shí)別率分類時(shí)間/s識(shí)別率分類時(shí)間/s

zoo

0.195.130.0795.670.1497.290.05

0.594.590.0993.510.1593.510.06

1.083.240.0888.100.1686.480.05

iris

0.194.030.0594.380.0694.380.03

0.593.680.0693.680.0893.680.04

1.091.920.0691.920.0791.920.04

wine

0.142.610.1442.890.1355.360.07

0.542.610.1041.150.1254.780.06

1.041.150.1041.150.1252.840.06

wave

0.184.6047.7984.6088.3087.4641.65

0.540.2052.3038.9983.3856.2540.20

1.031.7946.8933.4482.8052.8438.65

Segment

0.133.3316.0939.4022.3040.269.37

0.535.9115.9020.1921.5130.829.27

1.035.3615.5016.6320.4031.939.35

Glassdata

0.163.610.2668.190.2871.560.13

0.560.960.2866.500.3567.950.15

1.057.100.2864.810.2966.750.15

Backup

0.183.190.9289.411.7489.390.61

0.573.441.2156.131.7177.900.73

1.053.611.3042.521.7553.940.72

4 結(jié) 語(yǔ)

這里首先分析了當(dāng)前使用得較多的幾種SVM多類分類算法的特點(diǎn)以及存在的一些問(wèn)題。在此基礎(chǔ)上,提出基于二叉樹的SVM多分類算法。新的二叉樹生成算法可以使得分布好的類別在屬性空間中獲得更大的劃分區(qū)域,從而提高多分類模型的推廣性能。最后,通過(guò)幾個(gè)實(shí)驗(yàn),對(duì)這些算法進(jìn)行了比較,實(shí)驗(yàn)結(jié)果表明本文算法可以明顯的減少分類時(shí)間,且分類精度也較理想。 基于本文的方法還有許多需要研究的問(wèn)題,選取更好的生成二叉樹方法,這將是下一步研究的方向。

參考文獻(xiàn)

[1]方景龍,陳鑠,潘志庚,等.復(fù)雜分類問(wèn)題支持向量機(jī)的簡(jiǎn)化[J].電子學(xué)報(bào),2007(11):78-82.

[2]徐曉燕,王昱,張斌.一種集成logistic回歸與支持向量機(jī)的判別分析規(guī)則[J].系統(tǒng)工程理論與實(shí)踐,2007(5):126-131.

[3]Hsu C,Lin C.A Comparison of Methods for Multiclass Support Vector Machines[J].IEEE Trans.on Neural Networks,2002,13(2):415-425.

[4]Takahashi F,Abe S.Decision-Tree-Based Multiclas Support Vector Machines[A].Proc of the 9th Int.Conf.on Neural Information Processing[C].Singapore,2002(3):1 418-1 422.

[5]Sungmoon C,Sang H O,Soo-Young L.Support Vector Machines with Binary Tree Architecture for Multi-class Classification[J].Neural Information Processing-Letters and Reviews,2004,2(3):47-51.

[6]顏根廷,李傳江,馬廣富.支持向量分類器的模糊積分集成方法[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào),2008,40(7):1 017-1 020.

[7]張永,遲忠先,米瀅.一類直接構(gòu)造的模糊多類支持向量分類器[J].計(jì)算機(jī)工程與應(yīng)用,2008,44(8):12-15.

[8]UCI Repository ofMachine Learning Databases and Domain Theories[EB/OL].ftp:// ftp.ics.uci.edu/pub/machine-learning-databases.