尹麗東 范麗亞

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

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

尹麗東 范麗亞

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

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

支持向量機，有效稀疏， 孿生支持向量機，正則化支持向量機

0 引言

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

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

1 支持向量分類(SVC)

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

線性分類器尋找一個分類超平面

f(x)=wTx+b,

(1)

(2)

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

(3)

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

(4)

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

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

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

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

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

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

線性TWSVM尋求一對非平行超平面

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

(5)

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

(6)

(7)

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

(8)

和

(9)

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

(10)

和

(11)

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

(12)

和

(13)

通過

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

(14)

2.2 最小二乘SVM(LSSVM)

(15)

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

(16)

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

(17)

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

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

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

2.3 正則項支持向量機(RTSVM)

(18)

(19)

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

(20)

進而有

(21)

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

(22)

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

(23)

同樣地，可以得到(16)式的對偶問題

(24)

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

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

(25)

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

(26)

2.4L2-SVM

(27)

(28)

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

(29)

(30)

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

(31)

3 結(jié)論

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

[1] 鄧乃揚, 田英杰. 數(shù)據(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].聊城大學(xué)學(xué)報：自然科學(xué)版, 2014, 27：54-60.

[15] 高西占,范麗亞.基于最小閉球的多類支持向量[J].聊城大學(xué)學(xué)報：自然科學(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

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

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

O224

A

1672-6634(2017)02-0014-06