郭亞琴 王正群

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

關鍵詞:支持向量機;多類分類;二叉樹;多類支持向量機

中圖分類號:TP391文獻標識碼:A

文章編號: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 引 言

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

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

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

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

1.1 多類SVM分類方法簡介

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

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

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

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

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

1.2 基于二叉樹的多類SVM

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

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

圖1 四類問題的不同劃分順序

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

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

2 改進的多分類二叉樹法

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

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

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

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

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

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

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

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

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

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

Di=Dib/Diw(3)

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

具體的算法流程為:

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

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

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

Step 4:算法結束。

3 實驗比較

3.1 實驗數(shù)據(jù)

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

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

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

zoo101717

iris15035

wine178314

wave5 000322

Segment2 100719

GlassData214610

Backup3051836

3.2 實驗結果與分析

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

表2中時間是5次實驗的平均值,時間是以程序運行的CPU時間為準,單位為s。從表2可以看出,本文算法的時間與one-versus-one和one-versus-rest相比,都有了明顯減少,因為二叉樹測試樣本時并不需要計算所有的二值分類器。one-versus-one方法的支持向量個數(shù)遠遠多于其他的算法,這是因為其每個子分類器都需利用到所有的訓練樣本,構造的分類面較其他算法復雜。one-versus-one和one-versus-rest的時間相對較長,是因為這兩種方法必須計算所有的二值SVM分類器判別函數(shù),且one-versus-one的總支持向量數(shù)較多,使得其時間更長。

表2 三種方法的實驗結果

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

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

識別率分類時間/s識別率分類時間/s識別率分類時間/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 結 語

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

參考文獻

[1]方景龍,陳鑠,潘志庚,等.復雜分類問題支持向量機的簡化[J].電子學報,2007(11):78-82.

[2]徐曉燕,王昱,張斌.一種集成logistic回歸與支持向量機的判別分析規(guī)則[J].系統(tǒng)工程理論與實踐,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è)大學學報,2008,40(7):1 017-1 020.

[7]張永,遲忠先,米瀅.一類直接構造的模糊多類支持向量分類器[J].計算機工程與應用,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.