改進孿生支持向量機的一種快速分類算法

高斌斌，劉 霞，李秋林

(1.西南大學數學與統計學院，重慶 400715;

2.新疆大學數學與系統科學學院，烏魯木齊 830046)

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

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

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

1 改進的孿生支持向量機

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

1.1 改進的線性孿生支持向量機

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

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

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

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

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

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

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

由式(12)得

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

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

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

1.2 改進的非線性孿生支持向量機

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

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

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

2 ITSVM的快速求解算法

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

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

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

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

其中:

3 實驗結果

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

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

3.1 人工數據集實驗

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

表1 4種算法在Ripley’s數據上的分類結果

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

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

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

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

3.2 真實數據集實驗

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

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

表2 線性SVM、TSVM、TPMSVM與ITSVM的分類結果

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

由表2和表3可以得到:

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

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

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

4 結束語

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

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

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

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

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

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

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

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

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

［9］唐曉芬，趙秉新.基于支持向量機的農村勞動力轉移預測［J］.安徽農業科學，2011(11):6837－6838.

［10］崔建國，李明，陳希成.基于支持向量機的飛行器健康診斷方法［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］.電子科技大學學報，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.