改進(jìn)孿生支持向量機(jī)的一種快速分類算法

高斌斌，劉 霞，李秋林

(1.西南大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院，重慶 400715;

2.新疆大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，烏魯木齊 830046)

支持向量機(jī) (support vector machine，SVM)［1－10］是Vapnik等提出的一種基于統(tǒng)計學(xué)習(xí)理論的機(jī)器學(xué)習(xí)方法，能非常成功地處理分類和回歸問題。由于它采用結(jié)構(gòu)風(fēng)險最小化的原則［11］而具有良好的學(xué)習(xí)能力和泛化性能，因此得到廣泛應(yīng)用(如圖像識別、文本分類、生物信息、金融應(yīng)用)。盡管許多快速 SVM算法(如 Chunking、分塊、SMO和Liblinear等［12］算法)已被相繼提出，但在實際應(yīng)用中面對大規(guī)模數(shù)據(jù)，分類算法需要進(jìn)行大量的二次規(guī)劃計算，分類計算量大、分類速度慢，速度問題在很大程度上限制了SVM的應(yīng)用。

2007年，Jayadeva等［13］提出了孿生支持向量機(jī)(TSVM)。該算法優(yōu)化目標(biāo)要求超平面離本類樣本盡可能的近，離它類樣本盡可能的遠(yuǎn)。TSVM計算時間開銷縮減到SVM的1/4。然而，奇異性問題導(dǎo)致TSVM不能保證得到較好的分類性能?；赥SVM思想，近年來發(fā)展了許多有關(guān)非平行的超平面學(xué)習(xí)方法，如光滑 TSVM［14］、最小二乘TSVM［15］、TBSVM［16］。最近，彭［17］提出了 TPMSVM，該模型通過正、負(fù)參數(shù)間隔超平面間接確定分類最優(yōu)超平面。

為了更好地提高TSVM算法的學(xué)習(xí)速度和泛化能力，提出改進(jìn)的TSVM(ITSVM)模型，并將收縮技術(shù)［18］嵌入坐標(biāo)下降方法［19］求解改進(jìn)模型，十分有效地改善了TSVM的學(xué)習(xí)速度和分類能力。仿真實驗表明:相對于傳統(tǒng)的SVM、TSVM及TPMSVM方法，ITSVM不僅提高了分類的準(zhǔn)確率，而且大大改善了計算效率。

1 改進(jìn)的孿生支持向量機(jī)

給定 2類 n維的 m個訓(xùn)練樣本，T={(xi，yi)}，xi∈Rn，對于二分類問題，yi={+1，－1}(i=1，…，m)作為類別的標(biāo)簽。分別用m1×n的矩陣X+和m2×n的矩陣X－表示為+1類和－1類，m1、m2分別表示2類樣本的數(shù)目。

1.1 改進(jìn)的線性孿生支持向量機(jī)

考慮到現(xiàn)有的孿生模型并不具有類似于SVM的特性，即間隔［20］，基于SVM結(jié)構(gòu)風(fēng)險最小化和最大間隔原則，在TSVM模型原始優(yōu)化問題中添加正則項，使得構(gòu)造的優(yōu)化問題的優(yōu)化目標(biāo)結(jié)構(gòu)風(fēng)險最小，從而提高TSVM的泛化性能。線性情形下，ITSVM也是尋找2個不平行的超平面:

為了獲得這2個超平面，改進(jìn)后的原始問題為:

其中:εi＞0(i=1，2)是正則化參數(shù);ci＞0(i=1，2)是懲罰參數(shù)。

顯然，最優(yōu)超平面wT±x+b±=0與邊界超平面wT±x+b±= ±1 之間的間隔是，因此目標(biāo)函數(shù)極小化正則項和與極大化間隔等價，也就是使得最優(yōu)超平面與邊界超平面的距離盡可能的遠(yuǎn)。原始問題(2)的Lagrangian函數(shù)為

其中 α =(α1，α2，…，αm2)T是 Lagrange乘子。根據(jù)The Karush Kuhn Tucker(KKT)條件:

合并式 (5)、(6)可以得

職業(yè)教育是國家教育事業(yè)的重要組成部分，是促進(jìn)經(jīng)濟(jì)社會發(fā)展和勞動就業(yè)的重要途徑。在新時代，職業(yè)教育更是被賦予培養(yǎng)“大國工匠”的歷史重任，寫入了黨的十九大報告，納入重慶科教興市和人才強(qiáng)市行動計劃，其重要性不言而喻。發(fā)展是第一要務(wù)，人才是第一資源。在新一輪改革發(fā)展浪潮中，如何通過加快區(qū)縣職業(yè)教育發(fā)展，推動人才與發(fā)展有效匹配、教育與產(chǎn)業(yè)緊密對接、科技與經(jīng)濟(jì)深度融合，助推實現(xiàn)“兩地”“兩高”目標(biāo)，值得研究和探索。

由式(12)得

將式(13)帶入Lagrangian函數(shù)(4)，使用約束條件(7)～(10)，可以得到問題(2)的Wolfe對偶問題:

類似的方式可以得到問題(3)的Wolfe對偶問題:

求解對偶問題(14)和(15)，得到Lagrange乘子α和β，從而得到權(quán)重向量w±和偏置值b±。對于一個新的輸入x∈Rn是+1類還是－1類，可依據(jù)決策函數(shù)判別，其中是絕對值。

1.2 改進(jìn)的非線性孿生支持向量機(jī)

對于線性不可分問題，引進(jìn)從輸入空間Rn到一個高維的Hilbert空間H的變換φ，這樣在原空間尋找超平面的問題轉(zhuǎn)化為在特征空間H中尋找2個由核生成超平面:

的問題，其中 K(x，y)=φ(x)Tφ(y)為核函數(shù)。為了將線性情況的結(jié)果拓展到非線性情況，構(gòu)造原始優(yōu)化問題

記 S+=［K(X+，XT)e+］，S－ =［K(X－，XT)e－］，引進(jìn)Lagrangian函數(shù)，利用KKT條件，可以獲得原始優(yōu)化問題(17)和(18)的對偶問題:

2 ITSVM的快速求解算法

在ITSVM模型中，需求解對偶問題(14)、(15)、(19)和(20)。易知這4個問題都是凸二次規(guī)劃問題，可以用同樣的方法解決。因此只需要探究問題(14)的求解算法.

文獻(xiàn)［19］將坐標(biāo)下降法成功應(yīng)用于求解SVM的對偶問題。問題(21)和SVM的對偶問題形式類似，但是卻又不同，這是由于問題(21)與文獻(xiàn)［19］的矩陣Q有本質(zhì)的不同。收縮技術(shù)可以有效地處理非常大的數(shù)據(jù)集，該算法有效性已在文獻(xiàn)［18］中得到證明。結(jié)合坐標(biāo)下降算法與收縮技術(shù)的優(yōu)勢，得到了針對ITSVM對偶問題的高效求解算法。

算法的迭代過程由 α0∈Rm2開始，記 αk，1= αk，αk，m2+1= αk+1，且

從 αk，i更新到 αk，i+1:

其中:

3 實驗結(jié)果

為了驗證ITSVM的分類性能，在人工數(shù)據(jù)與UCI數(shù)據(jù)集上對SVM、TSVM、TPSVM和ITSVM分別進(jìn)行對比測試。實驗運行環(huán)境:Windows7操作系統(tǒng)，CPU為 Intel corei3(2.4GHz)，內(nèi)存為2G，Matlab 7.13軟件。對所有方法的線性和非線性情形分別進(jìn)行了測試。非線性情形下使用高斯核函數(shù):K(x，y)=e－‖x－y‖2/(2σ2)。為了對比實驗的執(zhí)行效率，用本文提出的算法求解ITSVM，對SVM、TSVM 和 TPMSVM 使用“qp.m”函數(shù)求解［21］，分類準(zhǔn)確率采用標(biāo)準(zhǔn)的十折交叉驗證方法。

眾所周知，參數(shù)對模型分類準(zhǔn)確率有一定程度的影響，為了簡化參數(shù)的搜索難度，在ITSVM中設(shè)置 ε1=ε2=ε，c1=c2=c，所有算法參數(shù)范圍統(tǒng)一在集合{2i|i=－8，…，8}內(nèi)，隨機(jī)選擇30%的訓(xùn)練集作調(diào)試集，通過網(wǎng)格搜索方法尋找最佳的參數(shù)。一旦參數(shù)被確定下來，調(diào)試集將還原到訓(xùn)練集中。

3.1 人工數(shù)據(jù)集實驗

2 維數(shù)據(jù) Ripley’s synathetic［22］常用于測試分類算法的性能，此數(shù)據(jù)有250個訓(xùn)練點，1 000個測試點。本節(jié)將通過此數(shù)據(jù)測試ITSVM與SVM、TSVM、TPMSVM在分類準(zhǔn)確率與分類效率上的性能。在線性與非線性下分別通過訓(xùn)練集訓(xùn)練4種模型，然后對測試數(shù)據(jù)分別進(jìn)行分類預(yù)測。記錄預(yù)測的準(zhǔn)確率和模型的訓(xùn)練時間如表1所示，4種方法的決策超平面如圖1、2所示。

表1 4種算法在Ripley’s數(shù)據(jù)上的分類結(jié)果

圖1 非線性的SVM與TSVM分類超平面

圖2 非線性的TPMSVM與ITSVM分類超平面

從圖1、2可以看出:經(jīng)典SVM的決策邊界是一個超平面，而TSVM、TPMSVM和ITSVM有2個超平面;ITSVM兩條超曲線的位置相對TSVM、TPMSVM更加合理。

從表1結(jié)果可以知道:在測試準(zhǔn)確率上，非線性的ITSVM獲得了最佳的分類準(zhǔn)確率，而在線性情形下傳統(tǒng)的SVM獲得了最佳的分類準(zhǔn)確率;在算法的執(zhí)行效率上，本文提出的方法相對于已有的SVM、FSVM、TSVM方法具有明顯的優(yōu)勢，尤其是在線性情形下算法的執(zhí)行效率表現(xiàn)得更為出色。

3.2 真實數(shù)據(jù)集實驗

為了進(jìn)一步測試ITSVM算法的有效性和實用性，在公開的UCI機(jī)器學(xué)習(xí)數(shù)據(jù)集［23］上選取了8個常用的數(shù)據(jù)，同相關(guān)方法SVM、TSVM、TPMSVM做對比實驗，以更全面說明本文算法的分類性能。

數(shù)據(jù)集中同時包括二分類和多分類數(shù)據(jù)。對于多分類數(shù)據(jù)，處理方法是把類別數(shù)量比例較高的作為+1類，其余的作為－1類，從而轉(zhuǎn)化為二分類問題。在實驗之前，為了減少樣本的不同特征的數(shù)量差別，歸一化所有的樣本數(shù)據(jù)在區(qū)間［－1，1］。表2和表3顯示了在線性和非線性情況下本文所提方法 ITSVM與SVM，TSVM及 TPMSVM方法在給定數(shù)據(jù)集上的模式分類精度和學(xué)習(xí)的CPU時間。

表2 線性SVM、TSVM、TPMSVM與ITSVM的分類結(jié)果

表3 非線性SVM、TSVM、TPMSVM與ITSVM的分類結(jié)果

由表2和表3可以得到:

1)采用非線性核能明顯增強(qiáng)4種分類方法在幾乎所有數(shù)據(jù)集上的分類性能。

2)無論是在線性情形還是非線性情形下，與已有方法SVM、TSVM及TPMSVM相比，ITSVM在絕大部分?jǐn)?shù)據(jù)集上均具有優(yōu)于其他方法的模式分類性能。

3)在算法的執(zhí)行效率上，TSVM及 TPMSVM相對于SVM明顯高效，但是本文提出的算法的分類速度表現(xiàn)更加出色，在線性情形下更具優(yōu)勢。

4 結(jié)束語

本文在TSVM的基礎(chǔ)上，借鑒SVM結(jié)構(gòu)風(fēng)險最小化思想來構(gòu)建原始優(yōu)化問題，提出ITSVM分類模型。該模型的對偶問題為凸二次規(guī)劃問題，可以得到全局唯一解。針對此模型，提出一種新穎的坐標(biāo)下降算法，能有效地求解ITSVM的對偶問題。在人工數(shù)據(jù)與UCI數(shù)據(jù)集上測試證實:在線性和非線性情況下，本文方法ITSVM的分類準(zhǔn)確率和執(zhí)行效率優(yōu)于或等于相關(guān)方法。但是，ITSVM模型中有4個參數(shù)需要確定，這增加了參數(shù)選擇的難度。如何更好地選擇參數(shù)，同時將此方法應(yīng)用于多分類問題和回歸問題，都是接下來要進(jìn)行的研究工作。

［1］Cortes C，Vapnik V N.Support vector networks［J］.Machine Learning，1995，20(3):273 －297.

［2］余珺，鄭先斌，張小海.基于多核優(yōu)選的裝備費用支持向量機(jī)預(yù)測法［J］.四川兵工學(xué)報，2011(6):118－119.

［3］萬輝.一種基于最小二乘支持向量機(jī)的圖像增強(qiáng)算法［J］.重慶理工大學(xué)學(xué)報:自然科學(xué)版，2011(6):53－57.

［4］王俊偉，吳緯.基于支持向量機(jī)的裝備維修保障專業(yè)優(yōu)化［J］.四川兵工學(xué)報，2010(6):11－13.

［5］鄔嘯，魏延，吳瑕.基于混合核函數(shù)的支持向量機(jī)［J］.重慶理工大學(xué)學(xué)報:自然科學(xué)版，2011(10):66－70.

［6］朱光兆，何偉.基于支持向量機(jī)的混沌時間序列預(yù)測分析［J］.自動化與儀器儀表，2012(1):145－147.

［7］張宏蕾，張立亭，羅亦泳，等.基于支持向量機(jī)的土地利用預(yù)警研究［J］.安徽農(nóng)業(yè)科學(xué)，2010(35):20503－20504.

［8］黃銀蓉，張紹德.MIMO最小二乘支持向量機(jī)污水處理在線軟測量研究［J］.自動化與儀器儀表，2010(4):15－17.

［9］唐曉芬，趙秉新.基于支持向量機(jī)的農(nóng)村勞動力轉(zhuǎn)移預(yù)測［J］.安徽農(nóng)業(yè)科學(xué)，2011(11):6837－6838.

［10］崔建國，李明，陳希成.基于支持向量機(jī)的飛行器健康診斷方法［J］.壓電與聲光，2009(2):266－269.

［11］cholk?pf B S，Smola A.Learning with kernels［M］.Cambridge，MA:MIT Press，2002，62 －75.

［12］Fan R E，Chang K W，Hsieh C J，et al.LIBLINEAR:a library for large linear classification［J］.Journal of Machine Learning Research.2008，9:1871 －1874.

［13］Jayadeva R K，Khemchandani R，Chandra S.Twin support vector machines for pattern classification［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2007，29(5):905 －910.

［14］Kumar M A，Gopal M.Application of smooth in technique on twin support vector machines［J］.Pattern Recognition Letters，2008，29(13):1842 －1848.

［15］Kumar M A，Gopal M.Least squares twin support vector machines for pattern classication［J］.Expert Systems with Applications，2009，36(4):7535 －7543.

［16］Shao Y H，Zhang C H，Wang X B.Improvements on twin support vector machines［J］.IEEE Transactions on neural networks，2011，22(6):962 －968.

［17］Peng X J.TPMSVM:A novel twin parametric－margin support vector machine for pattern recognition［J］.Pattern Recognition，2011，44:2678 －2692.

［18］Hsieh C J，Chang K W，Lin C J.A dual coordinate descent method for large－scale linear SVM［C］//Proceedings of the 25th international conference on machine learning.USA:［s.n.］，2008.

［19］Joachims T.Making large－scale SVM learning practical［M］.Cambridge，MA:MIT Press，1998:169 －184.

［20］丁世飛，齊丙娟，譚紅艷.支持向量機(jī)理論與算法研究綜述［J］.電子科技大學(xué)學(xué)報，2011，40(1):2 －10.

［21］Gunn S R.2001 MATLAB support vector machine toolbox version:2.1［EB/OL］.［2011 －05 －27］.http://www.isis.ecs.soton.ac.uk/resources/svminfo/.

［22］Ripley B D.Pattern Recognition and Neural Networks［M］.Cambridge:Cambridge University Press，1996.

［23］Blake C L，Merz C J.UCI repository for machine learning databases［EB/OL］.［1998 －10 －15］.http://www.ics.uci.edu/～mlearn/MLRepository.html.