高斌斌,劉 霞,李秋林
(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)確率,而且大大改善了計算效率。
給定 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ù)目。
考慮到現(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ù)判別,其中是絕對值。
對于線性不可分問題,引進(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)的對偶問題:
在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:
其中:
為了驗證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)練集中。
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)得更為出色。
為了進(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)勢。
本文在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.