支持向量機多分類問題研究*

肖 曉,張 敏

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

0 引言

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

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

1 SVM多類分類方法

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

1.1 一對多SVM

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

(1)

(2)

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

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

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

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

1.2 一對一SVM

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

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

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

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

2 實驗仿真分析

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

表1 實驗數(shù)據(jù)統(tǒng)計

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

2.2 實驗結(jié)果與分析

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

表2 多類分類方法實驗結(jié)果對比

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

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

表3 多類分類時間對比

3 結(jié)束語

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

參考文獻(xiàn):

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

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

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

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

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

[6] 劉志剛,李德仁,秦前清,等.支持向量機在多類分類問題中的推廣[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] 白鵬,張喜斌,張斌,等.支持向量機理論及工程應(yīng)用實例[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] 黃瓊英.支持向量機多類分類算法研究及應(yīng)用[D].天津:河北工業(yè)大學(xué),2005.

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

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

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

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

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