肖 曉,張 敏

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

0 引言

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

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

1 SVM多類分類方法

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

1.1 一對多SVM

該算法是最早用于解決多類分類的方法,其基本思想是,解決n類問題需要訓練n個支持向量機的2類分類器,構成n個SVM模型。將第i類樣本數(shù)據(jù)看作正樣本,不屬于第i類的看成負樣本。在進行決策類別時,比較函數(shù)值中最大者所對應的類別即為數(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ī)劃問題,所以其分類速度較快。但這種方法每個子分類器的構造都需要所有樣本參與訓練,當樣本規(guī)模較大時,會導致訓練效率降低。同時,因訓練時總是一類樣本與剩余的多類別構造分類超平面,這樣可能會存在正負類在訓練樣本數(shù)目上極不平衡,進而影響分類器的預測精度。

1.2 一對一SVM

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

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

該分類方法的優(yōu)點是在進行判別時,無需遍歷所有的二類分類支持向量機。對于n類別問題,只需經(jīng)過n-1個決策函數(shù)就可以得出結果,有效地提高了分類速度,而且,不存在不可分區(qū)域。其缺點有兩類:一類是存在自上而下的“誤差累積”現(xiàn)象,這是DAGSVM的弊端。假如在某個節(jié)點上發(fā)生分類錯誤,則會把分類錯誤延續(xù)到該節(jié)點的后續(xù)節(jié)點上,累積誤差隨著類別數(shù)目的增加而增加。而且分類錯誤在越靠近根節(jié)點的地方發(fā)生,誤差累積效應越明顯,將嚴重影響分類的性能。另一類缺點是該方法最后輸出結果對節(jié)點的排序依賴性很大,節(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ù)進行訓練,剩余50組樣本作為測試集,共測試10次取其均值。實驗所用數(shù)據(jù)都歸一化到[-1,1],這樣做可以減少取值范圍大的屬性特征值對取值范圍小的屬性特征值產生的影響,以提高訓練精度和測試精度。剩下兩組數(shù)據(jù)劃分為訓練集和測試集兩部分,實驗時采用5折交叉驗證進行測試,這樣既保證提供足夠的數(shù)據(jù)用于模型學習,又能夠驗證模型的效果。

2.2 實驗結果與分析

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

表2 多類分類方法實驗結果對比

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

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

表3 多類分類時間對比

3 結束語

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

參考文獻:

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

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

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

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

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

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

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

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

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

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

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