肖 曉,張 敏

(1.中國礦業(yè)大學(xué) 信息與電氣工程學(xué)院,江蘇 徐州 221008； 2.淮海工學(xué)院 電子工程學(xué)院,江蘇 連云港 222005)

0 引言

支持向量機(jī)(sutopport vector machine,SVM)是Vapnik等人提出的一種針對(duì)小樣本訓(xùn)練和分類的機(jī)器學(xué)習(xí)理論[1]。它是以VC維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則為基礎(chǔ)的機(jī)器學(xué)習(xí),在解決高維模式識(shí)別、小樣本和非線性問題中表現(xiàn)出許多獨(dú)特的優(yōu)勢,在一定程度上克服了“過學(xué)習(xí)”和“維數(shù)災(zāi)難”等傳統(tǒng)問題,并且以統(tǒng)計(jì)學(xué)習(xí)理論(SLT)為基礎(chǔ),明確數(shù)學(xué)模型,因此具有很好的發(fā)展前景。

支持向量機(jī)最初是針對(duì)2類分類問題提出的,不能將其直接應(yīng)用于多類分類問題。但實(shí)際應(yīng)用中經(jīng)常需要對(duì)多類問題進(jìn)行分類,如何將支持向量機(jī)推廣到多類分類問題中并保持其優(yōu)良的性能,已成為學(xué)者們研究的熱點(diǎn)[2]。針對(duì)支持向量機(jī)多類分類算法眾多學(xué)者提出了不同的有效分類方法[3-5],但不同的方法對(duì)大規(guī)模分類的適用性尚不明確?；诖?筆者從目前常用的多類分類方法的基本原理及其特點(diǎn)來對(duì)比分析其在大規(guī)模分類中的適用性,并通過實(shí)驗(yàn)仿真分析來加以驗(yàn)證。

1 SVM多類分類方法

多類SVM實(shí)現(xiàn)方式可以分為2種[6]。第1種方法是一次性求解多類問題,其是在原有2類SVM基礎(chǔ)上,構(gòu)造多值分類模型,對(duì)新模型的目標(biāo)函數(shù)進(jìn)行最優(yōu)化，它其實(shí)是2類分類問題中二次優(yōu)化問題的推廣。由于這種目標(biāo)函數(shù)過于復(fù)雜,效率不高,一般不被采用。第2種方法是通過組合多個(gè)二值SVM分類器,實(shí)現(xiàn)多類別分類。

1.1 一對(duì)多SVM

該算法是最早用于解決多類分類的方法,其基本思想是,解決n類問題需要訓(xùn)練n個(gè)支持向量機(jī)的2類分類器,構(gòu)成n個(gè)SVM模型。將第i類樣本數(shù)據(jù)看作正樣本,不屬于第i類的看成負(fù)樣本。在進(jìn)行決策類別時(shí),比較函數(shù)值中最大者所對(duì)應(yīng)的類別即為數(shù)據(jù)的類別[7]。第i類SVM就是解決如下問題。

(1)

(2)

這里,φ是將xi映射到高維特征空間的映射函數(shù),C是懲罰系數(shù)。

(ωii)Tφ(x)+bi,i=1,2,…,n,

則x屬于哪一類就意味著它可以使判別函數(shù)最大。

一對(duì)多分類方法的優(yōu)點(diǎn)在于,對(duì)于n類問題只需求解n個(gè)二次規(guī)劃問題,所以其分類速度較快。但這種方法每個(gè)子分類器的構(gòu)造都需要所有樣本參與訓(xùn)練,當(dāng)樣本規(guī)模較大時(shí),會(huì)導(dǎo)致訓(xùn)練效率降低。同時(shí),因訓(xùn)練時(shí)總是一類樣本與剩余的多類別構(gòu)造分類超平面,這樣可能會(huì)存在正負(fù)類在訓(xùn)練樣本數(shù)目上極不平衡,進(jìn)而影響分類器的預(yù)測精度。

1.2 一對(duì)一SVM

一對(duì)一方法的優(yōu)點(diǎn)在于每個(gè)支持向量機(jī)子分類器只需訓(xùn)練兩類樣本,降低了構(gòu)造每個(gè)兩類分類器的復(fù)雜度,所以其訓(xùn)練速度較一對(duì)多快。同時(shí),參加訓(xùn)練的兩類樣本數(shù)量能夠達(dá)到基本平衡,降低了不平衡性對(duì)精度的影響。

1.3 有向無環(huán)圖支持向量機(jī)

該分類方法的優(yōu)點(diǎn)是在進(jìn)行判別時(shí),無需遍歷所有的二類分類支持向量機(jī)。對(duì)于n類別問題,只需經(jīng)過n-1個(gè)決策函數(shù)就可以得出結(jié)果,有效地提高了分類速度,而且,不存在不可分區(qū)域。其缺點(diǎn)有兩類:一類是存在自上而下的“誤差累積”現(xiàn)象,這是DAGSVM的弊端。假如在某個(gè)節(jié)點(diǎn)上發(fā)生分類錯(cuò)誤,則會(huì)把分類錯(cuò)誤延續(xù)到該節(jié)點(diǎn)的后續(xù)節(jié)點(diǎn)上,累積誤差隨著類別數(shù)目的增加而增加。而且分類錯(cuò)誤在越靠近根節(jié)點(diǎn)的地方發(fā)生,誤差累積效應(yīng)越明顯,將嚴(yán)重影響分類的性能。另一類缺點(diǎn)是該方法最后輸出結(jié)果對(duì)節(jié)點(diǎn)的排序依賴性很大,節(jié)點(diǎn)的排序不同將會(huì)導(dǎo)致不同分類結(jié)果,從而降低分類精度。

除上述幾種常見方法外,還有二叉樹的多類分類方法[11]，一次性求解方法[12]，糾錯(cuò)編碼SVM[13-14]，M-ary分類方法[15]，多級(jí)支持向量機(jī)方法[16]以及其他求解多類別的方法等[11]。這些方法各有優(yōu)缺點(diǎn),針對(duì)不同問題,采用不同的分類方法。

2 實(shí)驗(yàn)仿真分析

2.1 實(shí)驗(yàn)環(huán)境及數(shù)據(jù)

表1 實(shí)驗(yàn)數(shù)據(jù)統(tǒng)計(jì)

由于所使用的iris數(shù)據(jù)沒有測試集,筆者任意選擇100組樣本數(shù)據(jù)進(jìn)行訓(xùn)練,剩余50組樣本作為測試集,共測試10次取其均值。實(shí)驗(yàn)所用數(shù)據(jù)都?xì)w一化到[-1,1],這樣做可以減少取值范圍大的屬性特征值對(duì)取值范圍小的屬性特征值產(chǎn)生的影響,以提高訓(xùn)練精度和測試精度。剩下兩組數(shù)據(jù)劃分為訓(xùn)練集和測試集兩部分,實(shí)驗(yàn)時(shí)采用5折交叉驗(yàn)證進(jìn)行測試,這樣既保證提供足夠的數(shù)據(jù)用于模型學(xué)習(xí),又能夠驗(yàn)證模型的效果。

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

實(shí)驗(yàn)分析表明,一對(duì)一方法、有向無環(huán)圖方法在測試精度上相差不大,但一對(duì)多方法精度較差;除此之外,參數(shù)的選擇也是比較關(guān)鍵的,試驗(yàn)中用了交叉驗(yàn)證的方法來選擇最優(yōu)的參數(shù)(C,g)(見表2)。

表2 多類分類方法實(shí)驗(yàn)結(jié)果對(duì)比

以上得到結(jié)果是多次試驗(yàn)得到的最好結(jié)果,是否有比這更好的參數(shù)還有待進(jìn)一步的研究。還可以看出當(dāng)樣本數(shù)目較大時(shí),有向無環(huán)圖的分類準(zhǔn)確率最高,一對(duì)一多類分類方法次之,一對(duì)多的分類準(zhǔn)確率稍差些,這可能是正負(fù)類樣本在訓(xùn)練數(shù)目上的不平衡影響到預(yù)測精度。因此,為了獲得較高的分類準(zhǔn)確率，應(yīng)該優(yōu)先選擇有向無環(huán)圖多類分類方法。

對(duì)表3中數(shù)據(jù)分析表明，有向無環(huán)圖的決策時(shí)間相對(duì)來說較快些,因?yàn)闆Q策有向無環(huán)圖無需遍歷所有的分類器,對(duì)于一般規(guī)模的數(shù)據(jù)樣本具有理想的訓(xùn)練和分類效率。一對(duì)多方法也較好,兩種多類分類方法的訓(xùn)練時(shí)間相差不大。此外, 一對(duì)一方法在訓(xùn)練和測試時(shí)所耗費(fèi)的時(shí)間都較其他兩類高,其原因可能在于在訓(xùn)練和測試兩個(gè)階段都需要經(jīng)歷較多的子分類器。

表3 多類分類時(shí)間對(duì)比

3 結(jié)束語

筆者通過對(duì)比分析支持向量機(jī)常用多類分類算法 (一對(duì)多方法、一對(duì)一方法和有向無環(huán)圖多分類方法)的優(yōu)缺點(diǎn),認(rèn)為對(duì)小樣本數(shù)據(jù)進(jìn)行識(shí)別時(shí),3種方法的訓(xùn)練時(shí)間與測試時(shí)間相差無幾,但隨著樣本數(shù)量的增多,常用的一對(duì)多方法、一對(duì)一方法訓(xùn)練速度與分類速度都將大大降低,而有向無環(huán)圖簡單易行,具有理想的訓(xùn)練速度,分類速度略慢,但都快于一對(duì)一和一對(duì)多方法。因此有向無環(huán)圖對(duì)于一般大規(guī)模的多類分類問題是一種有效的分類方法,可以為大規(guī)模樣本的識(shí)別提供參考,具有一定的實(shí)用價(jià)值。

參考文獻(xiàn):

[1] VAPNIK V N.統(tǒng)計(jì)學(xué)習(xí)理論的本質(zhì)[M].張學(xué)工,譯.北京:清華大學(xué)出版社,2000.

[2] 丁然.支持向量機(jī)多分類算法研究[D].哈爾濱:哈爾濱理工大學(xué)，2012.

[3] 劉太安,梁永全,薛欣.一種新的模糊支持向量機(jī)多分類算法[J].計(jì)算機(jī)應(yīng)用研究,2008,25(7):2041-2042.

[4] 徐啟華,楊瑞.一種新的軟間隔支持向量機(jī)分類算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2005,26(9):2316-2318.

[5] 單玉剛,王宏,董爽.改進(jìn)的一對(duì)一支持向量機(jī)多分類算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2012,33(5):1837-1842.

[6] 劉志剛,李德仁,秦前清,等.支持向量機(jī)在多類分類問題中的推廣[J].計(jì)算機(jī)工程與應(yīng)用，2004，40(7):10-14.

[7] HSU C W, LIN C J. A comparison of methods for multi-class support vector machines[J]. IEEE Transactions on Neural Networks, 2002, 13(2): 415-425.

[8] 白鵬,張喜斌,張斌,等.支持向量機(jī)理論及工程應(yīng)用實(shí)例[M].西安:西安電子科技大學(xué)出版社，2008：48-49.

[9] SEBALD D J, BUCHLEW J A. Support vector machine and the multiple hypothesis test problem[J]. IEEE Transactions on Signal Processing, 2001, 49(11): 2865-2872.

[10] PLATT J C, CRISTIANINI N, SHAWE T J. Large margin DAGs for multiclass classification[J]. Advances in Neural Information Processing Systems, 2000,12(3): 547-553.

[11] 黃瓊英.支持向量機(jī)多類分類算法研究及應(yīng)用[D].天津:河北工業(yè)大學(xué),2005.

[12] 余輝,趙暉.支持向量機(jī)多類分類算法新研究[J].計(jì)算機(jī)工程與應(yīng)用,2008,44(7):185-194.

[13] 孔波,鄭喜英.支持向量機(jī)多類分類方法研究[J].河南教育學(xué)院學(xué)報(bào):自然科學(xué)版,2010,19(2):9-13.

[14] 趙春暉,陳萬海,郭春燕,等.多類支持向量機(jī)方法的研究現(xiàn)狀與分析[J].智能系統(tǒng)學(xué)報(bào),2007,2(2):11-18.

[15] 包建,劉然.用糾錯(cuò)編碼改進(jìn)的M-ary支持向量機(jī)多類分類算法[J].計(jì)算機(jī)應(yīng)用,2012,32(3):661-664.

[16] 邢紅杰.多級(jí)支持向量機(jī)[D].保定:河北大學(xué),2003.