尹麗東 范麗亞

( 聊城大學(xué)數(shù)學(xué)科學(xué)學(xué)院,山東聊城252059 )

幾種SVM的優(yōu)劣性比較①

尹麗東 范麗亞

( 聊城大學(xué)數(shù)學(xué)科學(xué)學(xué)院,山東聊城252059 )

支持向量機(jī)(Support Vector Machine, SVM)是將樣本進(jìn)行分類和回歸的一種強(qiáng)大的數(shù)學(xué)工具，尤其是對(duì)高維領(lǐng)域，效果尤為顯著.支持向量機(jī)工作原理是針對(duì)樣本數(shù)據(jù)集，尋找決策函數(shù)來(lái)對(duì)樣本數(shù)據(jù)進(jìn)行分類的.如今已經(jīng)衍生出多種SVM的相關(guān)模型.最為常見(jiàn)是有孿生支持向量機(jī)(T-SVM)，正則化支持向量機(jī)(RT-SVM)，最小二乘支持向量機(jī)(LSSVM).這幾類模型的出發(fā)點(diǎn)和建構(gòu)模型的思想有些許不同之處.本文則選取了三種常見(jiàn)的SVM模型，分析和比較它們之間的優(yōu)勢(shì)以及劣勢(shì), 能讓讀者更加深入的了解這類算法, 并且在實(shí)際問(wèn)題中更具有選擇應(yīng)用性.

支持向量機(jī)，有效稀疏， 孿生支持向量機(jī)，正則化支持向量機(jī)

0 引言

目前的時(shí)代是一個(gè) “大數(shù)據(jù)”的時(shí)代，當(dāng)人們談到“大數(shù)據(jù)”時(shí)候, 首先映入腦海的就是海量的數(shù)據(jù)和高維的數(shù)據(jù)，如網(wǎng)絡(luò)挖掘、網(wǎng)絡(luò)信息更新、基因表示分析、高頻金融數(shù)據(jù)等.如何能在海量高維的數(shù)據(jù)中挖掘提取出有用信息,并且利用這些有用信息，來(lái)進(jìn)行數(shù)據(jù)分析是非常必要的一個(gè)研究領(lǐng)域和研究方向, 也是廣大研究學(xué)者非常關(guān)注的一個(gè)研究方向..眾所周知, 在海量數(shù)據(jù)中挖掘提取出有用信息，這工作量往往也是非常龐大的, 利用這些有用信息進(jìn)行數(shù)據(jù)分析與處理, 一般都會(huì)導(dǎo)致算法學(xué)習(xí)時(shí)間過(guò)與慢長(zhǎng), 甚至達(dá)到失效的結(jié)果.而支持向量機(jī)(Support Vector Machine, SVM)[1]作為數(shù)據(jù)監(jiān)督學(xué)習(xí)[2]的一個(gè)強(qiáng)而有力工具, 為了降低其計(jì)算復(fù)雜程度, Suykens等人[3]提出了最小二乘SVM (Least Squares SVM, LSSVM).支持向量機(jī)，自1995年提出之后, 應(yīng)用數(shù)學(xué)的學(xué)者們得到了廣泛的關(guān)注和研究, 并應(yīng)用于諸多領(lǐng)域, 如人臉檢測(cè)識(shí)別、語(yǔ)音識(shí)別、文字手寫體識(shí)別、圖像處理等領(lǐng)域.然而，我們研究發(fā)現(xiàn)SVM所具有的稀疏性對(duì)于處理大數(shù)據(jù)和分析問(wèn)題也是極其重要的.之后，2007年, Jayadeva等人[8]針對(duì)二類分類問(wèn)題提出了孿生SVM(Twin SVM, TSVM), 它是主要思想是解決兩個(gè)規(guī)模較小的二次規(guī)劃問(wèn)題，而不是一個(gè)大規(guī)模的二次規(guī)劃問(wèn)題, 從而得到兩個(gè)非平行超平面, 使每個(gè)超平面距離一類盡可能近，而距離另一類盡可能遠(yuǎn).TSVM的計(jì)算速度比SVM快很多, 通過(guò)理論計(jì)算推導(dǎo)，其計(jì)算速度大約是SVM速度的4倍, 從而大大縮減了算法的學(xué)習(xí)時(shí)間, 對(duì)于處理這類海量高維的大數(shù)據(jù)非常有幫助. 但是TSVM仍然需要求解兩個(gè)二次規(guī)劃問(wèn)題, 當(dāng)學(xué)習(xí)的數(shù)據(jù)樣本數(shù)據(jù)較大時(shí), 仍然有比較高的計(jì)算復(fù)雜性.為了解決此問(wèn)題, Kumar等人[9]提出了最小二乘TSVM (Least Squares TSVM, LSTSVM).

接下來(lái)的部分,我們對(duì)分類器(Support vector classification,SVC)和孿生支持向量機(jī)(Twin Support vector Machine,TSVM)等作簡(jiǎn)要概述和比較研究.

1 支持向量分類(SVC)

考慮二類分類問(wèn)題的訓(xùn)練集T={(x1,y1),(x2,y2),…,(xm,ym)}，其中xi∈Rn是輸入值，yi∈{+1,-1}是對(duì)應(yīng)的輸入向量.

線性分類器尋找一個(gè)分類超平面

f(x)=wTx+b,

(1)

(2)

其中C>0是參數(shù).使得正則項(xiàng)1/2‖w‖2最小化等價(jià)于兩個(gè)平行的支持超平面wTx+b=1和wTx+b=-1之間的間隔最大化，其中ξi≥0,i=1,…,n為松弛變量,C>0為調(diào)節(jié)參數(shù). 若令2ξ=(ξ1,…,ξm)T, 則問(wèn)題(2)可表示為矩陣形式

(3)

考慮問(wèn)題(3)的Lagrange函數(shù)

(4)

進(jìn)而可構(gòu)造最優(yōu)分類超平面〈w*,x〉+b*=0, 使得y=sign(〈w*,x〉+b*).

通過(guò)理論推導(dǎo)計(jì)算，我們不難發(fā)現(xiàn)軟間隔SVM的優(yōu)點(diǎn)，其具有稀疏性，還有較強(qiáng)的推廣能力.但這種軟間隔支持向量機(jī)需要求解一個(gè)QPP. 當(dāng)樣本個(gè)數(shù)m較大時(shí), 無(wú)疑會(huì)導(dǎo)致計(jì)算時(shí)間變長(zhǎng).

2 幾種SVM型算法及其優(yōu)勢(shì)比較

本節(jié)主要介紹幾種具有代表性的支持向量機(jī), 并且對(duì)它們各自的優(yōu)勢(shì)和劣勢(shì)加以分析比較.(注：本節(jié)所用符號(hào)同上一節(jié)).

2.1 孿生支持向量機(jī)(T-WSVM)

現(xiàn)考慮如下問(wèn)題.假定用A∈Rm1×n所有表示正類的數(shù)據(jù)點(diǎn),Ai∈Rn表示A的第i行.類似地,用B∈Rm2×n表示負(fù)類的數(shù)據(jù)點(diǎn).

線性TWSVM尋求一對(duì)非平行超平面

f1(x)=w1x+b1=0和f2(x)=w2x+b2=0.

(5)

每一個(gè)超平面都逼近其中一類數(shù)據(jù)點(diǎn)，并且遠(yuǎn)離另一類,其中w1∈Rn,w2∈Rn,b1∈R,b2∈R.經(jīng)驗(yàn)風(fēng)險(xiǎn)可以由以下式子來(lái)測(cè)量

(6)

(7)

其中c1>0和c2>0為參數(shù).通過(guò)引入松弛向量ξ,ξ*,η和η*,原始問(wèn)題可以表示為

(8)

和

(9)

為了得到相應(yīng)的對(duì)偶問(wèn)題,TWSVM假設(shè)HTH和GTG都是非奇異的,其中H=[Ae1],G=[Be2].在此條件下，對(duì)偶問(wèn)題分別是

(10)

和

(11)

為處理HTH和GTG奇異和避免病態(tài)的情況, (HTH)-1和(GTG)-1可以分別由(HTH+εI)-1和(GTG+εI)-1來(lái)代替,其中I是合適維數(shù)的單位陣,ε是一個(gè)正標(biāo)量.因此以上偶對(duì)問(wèn)題可以修改為

(12)

和

(13)

通過(guò)

v1=-(HTH+εI)-1GTα和v2=(GTG+εI)-1HTγ

(14)

2.2 最小二乘SVM(LSSVM)

(15)

這樣做的目的是加快SVM的學(xué)習(xí)時(shí)間. 顯然, 問(wèn)題(15)可以轉(zhuǎn)化為無(wú)約束最優(yōu)化問(wèn)題:

(16)

令?f(w,b)/?w=?f(w,b)/?b=0, 可得

(17)

為不失一般性, 可設(shè)對(duì)稱非負(fù)定陣H+CGGT是非奇異陣(否則將其正則化), 于是有

進(jìn)而可構(gòu)造最優(yōu)分類超平面〈w*,x〉+b*=0使得y=sign(〈w*,x〉+b*).

從上述的推導(dǎo)過(guò)程中可以得出,LSSVM只需要求解線性方程組(7), 無(wú)需求解問(wèn)題(3), 大大減少了SVM的計(jì)算復(fù)雜程度, 這是LSSVM的一個(gè)較好的優(yōu)點(diǎn). 但從問(wèn)題(6)可以看出,LSSVM又失去了SVM所具有的稀疏性,并且需要求解矩陣H+CGGT的逆矩陣, 當(dāng)樣本的特征個(gè)數(shù)n較大時(shí), 求解這個(gè)逆矩陣，又會(huì)花費(fèi)較長(zhǎng)時(shí)間, 這就是LSSVM的不足之處.

2.3 正則項(xiàng)支持向量機(jī)(RTSVM)

(18)

(19)

考慮模型(18)的wolf對(duì)偶形式，考慮其lagrange函數(shù)

(20)

進(jìn)而有

(21)

(HTH+I)v1+GTα=0或v1=-(HTH+I)-1GTα,

(22)

將(22)式帶入到lagrange函數(shù)中，并使用(15)式，得到對(duì)偶問(wèn)題

(23)

同樣地，可以得到(16)式的對(duì)偶問(wèn)題

(24)

這里,γ是lagrange乘子,v2=[w2b2]T可以由以下求得

v2=(GTG+I)-1HTγ.

(25)

一旦問(wèn)題(15)和(16)分別由(20)和(21)得到(w1b1)和(w2b2),一個(gè)新的點(diǎn)x∈Rn被分配到類i(i=+1,-1)，它距離(3)中最近的超平面

(26)

2.4L2-SVM

(27)

(28)

令H=[Ae1],G=[Be2],我們得到(27)和(28)的對(duì)偶問(wèn)題

(29)

(30)

一個(gè)新的點(diǎn)x∈Rn被分配到類i(i=+1,-1)，它距離(5)中最近的超平面

(31)

3 結(jié)論

本文是分析和比較了幾種較具代表性的SVM型算法的優(yōu)劣勢(shì),發(fā)現(xiàn)了經(jīng)典的LSSVM雖然降低了SVM的計(jì)算復(fù)雜程度,但是同時(shí)又缺失了SVM所具有的稀疏性特點(diǎn),而且當(dāng)樣本數(shù)量較大時(shí)，還需要求解矩陣的逆矩陣,這樣又增加了計(jì)算復(fù)雜性.LSTSVM雖然比LSSVM計(jì)算時(shí)間快一些, 但我們知道，其同樣不具有稀疏性，而且還需要求逆矩陣.所以，SVM學(xué)習(xí)算法的計(jì)算復(fù)雜程度和稀疏性對(duì)于分析和處理大數(shù)據(jù)來(lái)說(shuō)，是非常重要的兩個(gè)因素,特別是對(duì)高維數(shù)據(jù).為此,學(xué)者們對(duì)LSSVM和LSTSVM做了改進(jìn)和推廣, 提出了SP-LSSVM,ε-LSSVM,ε-WLSSVM等具有稀疏性的學(xué)習(xí)算法. 類似于SP-LSSVM,ε-LSSVM和ε-WLSSVM, 針對(duì)LSTSVM也可以提出具有稀疏性的學(xué)習(xí)算法, 因篇幅有限, 本文不再加以具體討論.

[1] 鄧乃揚(yáng), 田英杰. 數(shù)據(jù)挖掘中的新方法: 支持向量機(jī)[M]. 北京科學(xué)出版社, 2006.

[2]DengNY,TianYJ.SupportVectorMachines:Theory,AlgorithmsandExtensions[M].SciencePress,Beijing, 2009.

[3]SuykensJAK,TonyVG,JosDB,etal.LeastSquaresSupportVectorMachines[M].WorldScientific, 2002.

[4]Suykens,JAKVandewalleJ.Leastsquaressupportvectormachineclassifiers[J].NeuralProcessingLetters, 1999, 9 (3)：293-300.

[5]TianYingjie,JuXuchan,QiZhiquan,etal.Efficientsparseleastsquaressupportvectormachineforpatternclassification[J].ComputersandMachematicswithApplications, 2013, 66：1 935-1 947.

[6]HuangXiaolin,ShiLei,JohanAKS.Asymmetricleastsquaressupportvectormachineclassifiers[J].ComputationalStatisticsandDataAnalysis, 2014, 70：395-405.

[7]XuShuoAnXin,QiaoXiaodong,etal.Multi-outputleast-squaressupportvectorregressionmachines[J].PatternRecognitionLetters, 2013, 34：1 078-1 084.

[8]Jayadeva,KhemchandaniR,ChandraS.Twinsupportvectormachineforpatternclassification[J].IEEETransPatternAnalMachIntell, 2007, 29(5)：905-910.

[9]KumarMA,GopalM.Leastsquarestwinsupportvectormachinesforpatternclassification[J].ExpertSystemsApplications, 2009, 36(4)：7 535-7 543.

[10]YangZhiMin,WuHeJi,LiChunNa,etal.Leastsquaresrecursiveprojectiontwinsupportvectormachineformulti-classclassification[J],InternationalJournalofMachineLearningandCybernetics, 2015, 10：1-16.

[11]ChenWeijie,Shaoyuanhai,DengNaiyang,etal.Laplacianleastsquarestwinsupportvectormachineforsemi-supervisedclassification[J].Neurocomputing, 2014, 145：465-476.

[12]JalalANasiri,NasrollahMOghadamCharkari,SaeedJalili.Leastsquarestwinmulti-classclassificationsupportvectormachine[J].PatternRecognition, 2015, 48：984-992.

[13]GaoShangbing,YeQiaolin,YeNing.1-normleastsquaretwinsupportvectormachines[J].Neurocomputing, 2011, 74：3 590-3 597.

[14] 侯明,張欣欣，范麗亞.四類基于支持向量機(jī)的多類分類器的性能比較[J].聊城大學(xué)學(xué)報(bào)：自然科學(xué)版, 2014, 27：54-60.

[15] 高西占,范麗亞.基于最小閉球的多類支持向量[J].聊城大學(xué)學(xué)報(bào)：自然科學(xué)版, 2014, 26：24-29.

Compare the Advantages and Disadvantages of Several SVM

YIN Li-dong FAN Li-ya

(School of Mathematical Sciences, Liaocheng University, Liaocheng 252059,China)

Support Vector Machine (SVM) is a powerful mathematical tool for classification and regression of samples, especially in high-dimensional field. The support vector machine is based on the sample data set and the decision function is used to classify the sample data. Multiple SVM models are now derived. The most common is the twin support vector machine (t-svm), the regularized support vector machine (rt-svm), the least square support vector machine (LSSVM). There are some differences between the starting point and the construction model of these models. In this paper, the selection of the three common SVM model, analyze and compare the advantages and disadvantages between them, could make readers more in-depth understanding of this kind of algorithm, and has more choice applied in the actual problem.

Support Vector Machine, effective sparse, twin support vector machine, regularization support vector machine

2017-03-16

國(guó)家自然科學(xué)基金項(xiàng)目(11501278);山東省自然科學(xué)基金項(xiàng)目(ZR2013AQ011)資助

范麗亞，E-mail:fanliya63@126.com.

O224

A

1672-6634(2017)02-0014-06