一種改進(jìn)的支持向量機(jī)多類(lèi)分類(lèi)方法

郭亞琴 王正群

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

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

中圖分類(lèi)號(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ì)二類(lèi)模式分類(lèi)而提出的,如何將其有效地推廣到多類(lèi)別分類(lèi)仍是當(dāng)前支持向量機(jī)研究的重要內(nèi)容之一。目前,對(duì)于多類(lèi)分類(lèi)問(wèn)題,SVM的解決途徑有兩種:

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

(2) 直接在一個(gè)優(yōu)化公式中同時(shí)考慮所有子分類(lèi)器的參數(shù)優(yōu)化。嚴(yán)格的講,它的思想類(lèi)似于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種,且在分類(lèi)精度上也不占優(yōu)[3]。當(dāng)訓(xùn)練樣本數(shù)非常大時(shí),這一問(wèn)題更加突出。因此,在對(duì)現(xiàn)有主要的SVM多類(lèi)分類(lèi)算法作簡(jiǎn)單介紹的基礎(chǔ)上,提出了新的基于二叉樹(shù)的SVM多類(lèi)分類(lèi)方法,該方法采用類(lèi)間散布度量與類(lèi)內(nèi)散布度量的比值作為二叉樹(shù)的生成算法,并通過(guò)一系列實(shí)驗(yàn)分析、比較了各種算法的特點(diǎn)。

1 多類(lèi)SVM分類(lèi)和基于二叉樹(shù)的多類(lèi)SVM

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

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

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

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

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

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

1.2 基于二叉樹(shù)的多類(lèi)SVM

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

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

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

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

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

2 改進(jìn)的多分類(lèi)二叉樹(shù)法

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

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

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

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

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

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

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

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

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

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

Di=Dib/Diw(3)

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

具體的算法流程為:

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

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

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

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ù)集中,既有多類(lèi)別大樣本數(shù)據(jù)集,又有多類(lèi)別小樣本數(shù)據(jù)集。表1列出了實(shí)驗(yàn)使用的每個(gè)數(shù)據(jù)集的實(shí)例個(gè)數(shù)、類(lèi)個(gè)數(shù)、屬性個(gè)數(shù)等數(shù)據(jù)信息。

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

數(shù)據(jù)集實(shí)例個(gè)數(shù)類(lèi)個(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í)別率和分類(lèi)時(shí)間的比較,由實(shí)驗(yàn)結(jié)果可以看出,基于二叉樹(shù)的多類(lèi)分類(lèi)算法與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)槎鏄?shù)測(cè)試樣本時(shí)并不需要計(jì)算所有的二值分類(lèi)器。one-versus-one方法的支持向量個(gè)數(shù)遠(yuǎn)遠(yuǎn)多于其他的算法,這是因?yàn)槠涿總€(gè)子分類(lèi)器都需利用到所有的訓(xùn)練樣本,構(gòu)造的分類(lèi)面較其他算法復(fù)雜。one-versus-one和one-versus-rest的時(shí)間相對(duì)較長(zhǎng),是因?yàn)檫@兩種方法必須計(jì)算所有的二值SVM分類(lèi)器判別函數(shù),且one-versus-one的總支持向量數(shù)較多,使得其時(shí)間更長(zhǎng)。

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

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

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

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

參考文獻(xiàn)

[1]方景龍,陳鑠,潘志庚,等.復(fù)雜分類(lèi)問(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]顏根廷,李傳江,馬廣富.支持向量分類(lèi)器的模糊積分集成方法[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào),2008,40(7):1 017-1 020.

[7]張永,遲忠先,米瀅.一類(lèi)直接構(gòu)造的模糊多類(lèi)支持向量分類(lèi)器[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.