花小朋，丁世飛

?

魯棒的加權孿生支持向量機

花小朋1, 2，丁世飛2, 3

(1. 鹽城工學院信息工程學院，江蘇鹽城，224051；2. 中國礦業(yè)大學計算機科學與技術學院，江蘇徐州，221116；3. 中國科學院計算技術研究所智能信息處理重點實驗室，北京，100190)

基于局部信息的加權孿生支持向量機(WLTSVM)借用類內(nèi)及類間近鄰圖分別表示類內(nèi)樣本的緊湊性和類間樣本的分散性，克服孿生支持向量機(TWSVM)欠考慮訓練樣本間相似性的缺陷，并且在一定程度上降低二次規(guī)劃求解的計算復雜度。然而，WLTSVM仍不能充分刻畫類內(nèi)樣本潛在的局部幾何結構，并且存在對噪聲點敏感的風險?；谝陨喜蛔?，提出一種魯棒的加權孿生支持向量機(RWTSVM)。與WLTSVM相比，RWTSVM的優(yōu)勢在于：選用熱核函數(shù)定義類內(nèi)近鄰圖權值矩陣，可以更好地刻畫類內(nèi)樣本潛在的局部幾何結構及蘊含的鑒別信息；用類間近鄰圖選取邊界點，同時結合類內(nèi)近鄰圖使得超平面遠離邊界點中權重較大的樣本，降低算法對噪聲點敏感的風險。人造數(shù)據(jù)集和真實數(shù)據(jù)集上的測試結果驗證算法RWTSVM的有效性。

孿生支持向量機；局部幾何結構；噪聲點；魯棒性；分類

對于二分類問題，傳統(tǒng)支持向量機(SVM)依據(jù)大間隔原則生成分類超平面，存在的缺陷是計算復雜度高且沒有充分考慮樣本的分布[1,2]。近年來，作為SVM的拓展方向之一，以孿生支持向量機(TWSVM)[3]為主要代表的非平行超平面分類器(NHCs)[4]正逐漸成為模式識別領域新的研究熱點。TWSVM思想源于廣義特征值近似支持向量機(GEPSVM)[5]，將GEPSVM問題轉(zhuǎn)換為兩個規(guī)模較小的形如SVM的二次規(guī)劃問題，計算復雜度縮減為SVM的1/4。除了速度上的優(yōu)勢，TWSVM繼承了GEPSVM的優(yōu)勢，即線性模式下能夠較好地處理異或(XOR)問題。基于TWSVM，近年發(fā)展了許多改進方法[6?10]。特別是文獻[6]提出的基于局部信息的加權孿生支持向量機(WLTSVM)，借用類內(nèi)及類間近鄰圖分別表示類內(nèi)樣本的緊湊性和類間樣本的分散性，克服了孿生支持向量機(TWSVM)欠考慮訓練樣本間相似性的缺陷。相比于TWSVM和WLTSVM不僅具有更好的泛化性能，而且選取少量邊界點作為支持向量，進一步降低了二次規(guī)劃求解的計算開銷。然而，WLTSVM仍然存在如下不足：1) 簡單的類內(nèi)近鄰圖權值矩陣的定義不能充分的刻畫類內(nèi)樣本潛在的局部幾何結構，容易影響算法的泛化性能；2) 用類間近鄰圖選取相反類中少量邊界樣本點進行算法求解，很大程度上降低了計算復雜度，但這同時也提高了算法對噪聲點敏感的風險?；谏鲜霾蛔?，本文提出一種魯棒的加權孿生支持向量機(RWTSVM)。相比于WLTSVM，RWTSVM的優(yōu)勢在于：1) 選用熱核函數(shù)定義類內(nèi)權值矩陣，RWTSVM能更好地刻畫類內(nèi)樣本潛在的局部幾何結構及蘊含的鑒別信息；2) 用類間近鄰圖選取相反類中少量邊界樣本點進行二次規(guī)劃求解，并且結合類內(nèi)近鄰圖使得超平面遠離邊界點中權重較大的樣本，這使得RWTSVM不敏感于噪聲點；3) RWTSVM在保證計算復雜度相當?shù)那闆r下具有更好的分類能力。

1 魯棒的加權孿生支持向量機(RWTSVM)

1.1 線性RWTSVM

給定兩類維實數(shù)空間中個訓練樣本點，分別用1×的矩陣和2×的矩陣表示第1類(+1類)和第2類(?1類)。這里，1和2分別是兩類樣本的數(shù)目，，，表示第(=1，2)類的第個樣本。線性RWTSVM的目標是在維空間中尋找2個超平面：

要求每個類超平面離本類具有高密度相關的樣本點盡可能近，離相反類中具有較大權重的邊界樣本點盡可能遠。

為此，受譜圖理論啟發(fā)[7, 11]，針對每一類超平面，構造一對近鄰圖G和G分別刻畫類內(nèi)樣本的緊湊性及類間樣本的分散性。

其中：為熱核參數(shù).

定義2[6]考慮第1類樣本，給定第2類中任意樣本(=1，2，…，2)，則圖G的權值矩陣可定義為：

依據(jù)定義2，第2類中每一個樣本定義權重

定義3 線性RWTSVM的第1類超平面的優(yōu)化準則(RWTSVM1)為

第2類超平面的優(yōu)化準則(RWTSVM2)為

其中：1和2為懲罰參數(shù)，和為損失變量。

定義3中式(5)優(yōu)化目標函數(shù)第1項要求第1類的超平面離本類中權重較大的樣本盡可能近，相反，那些權重較小的樣本點對超平面的影響不大。約束條件要求第2類中相對于第1類的邊界點離超平面的距離至少為。事實上，越大(即越屬于第2類)，樣本離超平面越遠。式(6)具有相似的幾何解釋。式(5)和(6)用矩陣形式分別表示為

(RWTSVM1)

和

(RWTSVM2)

其中：1=(，…，)T，2=(，…，)T，1和2是2個實體為1的列向量，，。

定理1 線性RWTSVM優(yōu)化準則式(7)對應的對偶問題(DRWTSVM1)為

優(yōu)化準則式(8)對應的對偶問題(DRWTSVM2)為

其中：=[1]，=[2]。

證明?？紤]線性RWTSVM的優(yōu)化準則式(7)，對應的拉格朗日函數(shù)為

根據(jù)Karush-Kuhn-Tucker(KKT)條件可得：

令=[1]，=[2]，由式(12)和(13)可推得

將式(14)和(15)代入式(11)得定理1中對偶問題式(9)成立。

同理可證得定理1中對偶問題式(10)成立，且

證畢。

通過求解定理1中2個對偶問題，可以分別求得拉格朗日系數(shù)和，并在此基礎上求出兩類樣本的決策超平面式(1)。線性RWTSVM的決策函數(shù)為

從式(15)和(16)可知：RWTSVM在求解過程中需要計算(T(1))?1和(T(2))?1，而(T(1))和(T(2))是正半定矩陣，因此，該方法不是嚴格的凸規(guī)劃問題(強凸問題)，特別是在小樣本情況下確實存在矩陣的奇異性。實際應用中，可以采用文獻[3, 5?6]方法通過引入規(guī)則項(＞0)解決RWTSVM存在的奇異性問題，即(T(1))-1和(T(2))?1分別用(T(1)+)?1和(T(2)+)?1替代，盡可能的小。

1.2 非線性RWTSVM

當樣本內(nèi)在的幾何結構呈現(xiàn)出高維非線性流行時，線性RWTSVM方法不能得到非線性流行結構的，因此本文進一步提出基于核空間(KFS)的非線性RWTSVM(NRWTSVM)方法。NRWTSVM優(yōu)化目標是在高維核空間中尋找2個超平面：

其中：=[TT]T。

定義4 NRWTSVM的第1類超平面的優(yōu)化準則(NRWTSVM1)為

(19)

第2類超平面的優(yōu)化準則(NRWTSVM2)為

定理2 NRWTSVM優(yōu)化準則式(19)對應的對偶問題(DNRWTSVM1)為

(21)

NRWTSVM優(yōu)化準則式(20)對應的對偶問題(DNRWTSVM2)為

其中：=[(，T)1]，=[(，T)2]。

證明：考慮NRWTSVM的優(yōu)化準則式(19)，對應的拉格朗日函數(shù)為

根據(jù)Karush-Kuhn-Tucker(KKT)條件可得：

(25)

令=[(，T)1]，=[(，T)2]，由式(24)和(25)可推得

將式(26)和(27)代入式(23)得定理2中對偶問題式(21)成立。

同理可證得定理2中對偶問題式(22)成立，且

證畢。

NRWTSVM的決策函數(shù)為

2 RWTSVM與WLTSVM比較

2.1 泛化性能比較

WLTSVM第1類超平面的優(yōu)化準則(WLTSVM1)為

顯然，與本文定義1中式(2)不同。圖1所示為RWTSVM和WLTSVM在人造數(shù)據(jù)集上的決策超平面。RWTSVM明顯區(qū)別于WLTSVM。RWTSVM的2個超平面反映了2類樣本的內(nèi)在局部幾何結構，而WLTSVM沒有能夠充分反映2類樣本內(nèi)在的局部幾何結構。盡管2種算法對圖1中人造數(shù)據(jù)集都可以得到100%學習精度，但從泛化性能層面上講，RWTSVM明顯優(yōu)于WLTSVM。這充分說明WLTSVM中類內(nèi)近鄰圖G的權值矩陣定義沒有本文RWTSVM中的合理。事實上，當式(2)中熱核參數(shù)時，等價于式(31)，這說明WLTSVM是本文RWTSVM的特例。

圖1 RWTSVM與WLTSVM在人造數(shù)據(jù)集上的決策超平面

進一步考慮WLTSVM1優(yōu)化準則式(30)中約束條件，可以看出：WLTSVM1是利用相反類中部分邊界樣本點()來構造限制約束。這在很大程度上降低了二次規(guī)劃求解的計算復雜度，但是，若邊界點中存在噪聲點，則可能會影響到算法的泛化性能。與WLTSVM1相比，本文提出的RWTSVM1優(yōu)化準則式(5)中約束條件中不僅考慮的是的樣本點，而且還考慮到這些邊界樣本點的類內(nèi)權重(即權重越大，離超平面的距離越遠)。這樣，不僅能夠保證算法具有較低的計算復雜度，而且可以很好地克服噪聲點問題。

2.2 計算復雜度比較

本文RWTSVM在訓練階段需要求解2個規(guī)模較小的二次規(guī)劃問題，計算復雜度為，其中和分別為第1類樣本及第2類樣本中相應邊界樣本點數(shù)。除此之外，還要求出每個樣本的類內(nèi)權重及類間權重，計算復雜度分別為和。分析WLTSVM可知，本文RWTSVM在訓練過程中需要花費計算開銷的部分與WLTSVM完全類似，因此本文RWTSVM與WLTSVM計算復雜度相當。

3 實驗分析

在人工數(shù)據(jù)集和真實數(shù)據(jù)集上分別對TWSVM，WLTSVM與RWTSVM進行實驗。實驗環(huán)境：Windows 7 操作系統(tǒng)，CPU為i3-2350M 2.3GHz，內(nèi)存為2GB，運行軟件為MATLAB 7.1。

3.1 測試人造數(shù)據(jù)集

相對于傳統(tǒng)支持向量機，線性模式下對XOR問題的求解能力是NDCs算法優(yōu)勢之一[3?5]。圖2所示為TWSVM，WLTSVM與RWTSVM 3個分類器在交叉數(shù)據(jù)集上“Crossplanes”(XOR的推廣)[3,5]上的分類性能。顯然3個算法產(chǎn)生的分類面重合，而且可以較好的求解XOR問題，并得到100%的學習精度。這也進一步證明了本文RWTSVM繼承了NDCs算法的特色，即線性模式下對XOR問題的求解能力優(yōu)于傳統(tǒng)支持向量機算法。

圖2 TWSVM，WLTSVM和RWTSVM在交叉數(shù)據(jù)集上產(chǎn)生的分類面

3.2 測試真實數(shù)據(jù)集

為了更全面地說明本文RWTSVM分類方法具有的分類性能，在本節(jié)測試UCI數(shù)據(jù)集，同時與TWSVM，WLTSVM進行對比，以增加本文算法分類性能的說服力。

UCI數(shù)據(jù)集經(jīng)常被用來測試算法的分類精 度[3?6,12?15]。在該測試階段，抽取該數(shù)據(jù)集多個分類數(shù)據(jù)子集來分別測試TWSVM，WLTSVM和本文RWTSVM。對于每個數(shù)據(jù)子集，選用10-折交叉驗證方法[3?6]。實驗結果給出了平均識別精度和訓練時間。參數(shù)1與2的搜索范圍均為{2|=?8，?6，…，8}(簡單起見，實驗中令1=2)，=1×10?6，熱核參數(shù)的搜索范圍為{2|=?3，?2，…，6}，類內(nèi)近鄰參數(shù)的搜索范圍為{1，2，…，9}，類間近鄰參數(shù)設為5。非線性算法采用高斯核函數(shù),核寬參數(shù)的搜索范圍為{2|=?1，0，…，7}。表1和表2所示分別為線性模式及非線性模式下3種分類方法的測試結果。

表1 線性TWSVM，WLTSVM與RWTSVM的測試結果

表2 非線性TWSVM，WLTSVM與RWTSVM的測試結果

從訓練時間上看：本文RWTSVM與WLTSVM相當，這與2.2節(jié)計算復雜度分析一致；但訓練速度明顯比TWSVM快，這主要是因為TWSVM用相反類全部樣本進行二次規(guī)劃求解，而RWTSVM與WLTSVM用少量邊界樣本點求解。

從泛化性能上看：WLTSVM分類性能優(yōu)于TWSVM，這點在文獻[6]中已經(jīng)得到驗證；相比于WLTSVM，本文提出的RWTSVM 算法具有更好的分類能力，這也進一步驗證了本文的改進措施確實可取。

4 結論

針對WLTSVM方法存在的不足，提出一種改進的NHCs方法：魯棒的加權孿生支持向量機(RWTSVM)。該方法不僅繼承了NHCs方法較好的異或(XOR)問題的求解能力，而且在一定程度上克服了WLTSVM方法不能充分刻畫訓練樣本間局部幾何結構信息以及對噪聲點敏感的缺陷。理論分析及實驗結果均證明了本文提出的改進措施切實可行。當訓練樣本數(shù)目趨向于大樣本時，RWTSVM與WLTSVM類似，會因計算復雜度過高而難于處理，因此，進一步研究計劃將著力于解決大樣本學習問題。

[1] 皋軍, 王士同, 鄧趙紅. 基于全局和局部保持的半監(jiān)督支持向量機[J]. 電子學報, 2010, 38(7): 1626?1633. GAO Jun, WANG Shitong, DENG Zhaohong. Global and local preserving based semi-supervised support vector machine[J]. Acta Electronica Sinica, 2010, 38(7): 1626?1633.

[2] 花小朋, 丁世飛. 局部保持對支持向量機[J]. 計算機研究與發(fā)展, 2014, 51(3): 590?597. HUA Xiaopeng, DING Shifei. Locality preserving twin support vector machines[J]. Journal of Computer Research and Development, 2014, 51(3): 590?597.

[3] Jayadeva, Khemchandai R, Chandra S. Twin support vector machines for pattern classification[J]. IEEE Transaction on Pattern Analysis and Machine Intelligence, 2007, 29(5): 905?910.

[4] DING Shifei, HUA Xiaopeng, YU Junzhao. An overview on nonparallel hyperplane support vector machines[J]. Neural Computing and Applications, 2014, 25(5): 975?982.

[5] Mangasarian O L, Wild E. MultisurFace proximal support vector machine classification via generalized eigenvalues[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006, 28(1): 69?74.

[6] YE Qiaolin, ZHAO Chunxia, GAO Shangbing, et al. Weighted twin support vector machines with local information and its application[J]. Neural Networks, 2012, 35(11): 31?39.

[7] YE Qiaolin, ZHAO Chunxia, YE Ning, et al. Localized twin svm via convex minimization[J]. Neurocomputing, 2011, 74(4): 580?587.

[8] PENG Xinjun, XU Dong. Norm-mixed twin support vector machine classifier and its geometric algorithm[J]. Neurocomputing, 2013, 99(1): 486?495.

[9] QI Zhiquan, TIAN Yingjie, SHI Yong. Structural twin support vector machine for classification[J]. Knowledge-Based Systems, 2013, 43(5): 74?81.

[10] SHAO Yuanhai, DENG Naiyang, YANG Zhimin, et al. Probabilistic outputs for twin support vector machines[J]. Knowledge-Based Systems, 2012, 33(9): 145?151.

[11] YANG Xubing, CHEN Songcan, CHEN Bin, et al. Proximal support vector machine using local information[J]. Neurocomputing, 2009, 73(1): 357?365.

[12] WANG Xiaoming, CHUANG Fulai, WANG Shitong. On minimum class locality preserving variance support vector machine[J]. Patter Recognition, 2010, 43(8): 2753?2762.

[13] CHEN Xiaobo, YANG Jian, YE Qiaolin, et al. Recursive projection twin support vector machine via within-class variance minimization[J]. Pattern Recognition, 2011, 44(10): 2643?2655.

[14] 丁立中, 廖士中. KMA-a: 一個支持向量機核矩陣的近似計算算法[J]. 計算機研究與發(fā)展, 2012, 49(4): 746?753. DING Lizhong, LIAO Shizhong. KMA-a: A kernel matrix approximation algorithm for support vector machines[J]. Journal of Computer Research and Development, 2012, 49(4): 746?753.

[15] XUE Hui, CHEN Songcan. Glocalization pursuit support vector machine[J]. Neural Computing and Applications, 2011, 20(7): 1043?1053.

(編輯 陳愛華)

Robust weighted twin support vector machine

HUA Xiaopeng1, 2, DING Shifei2, 3

(1. School of Information Engineering, Yancheng Institute of Technology, Yancheng 224051, China;2. School of Computer Science and Technology, China University of Mining and Technology, Xuzhou 221116, China;3. Key Laboratory of Intelligent Information Processing, Institute of Computing Technology,Chinese Academy of Science, Beijing 100190, China)

Weighted twin support vector machine with local information (WLTSVM), as a variant of twin support vector machine (TWSVM), uses within-class graph and between-class graph to characterize the intra-class compactness and the inter-class separability, respectively. This makes WLTSVM improve the generalization capability of TWSVM by mining as much underlying similarity information within samples as possible and reduces the time complexity of TWSVM by reducing the support vectors for each class. Despite these advantages, WLTSVM can not fully reflect the local geometry manifold within samples because of using the within-class graph whose weight matrix is defined simply. Moreover, WLTSVM ignores the possible outliers because it chooses boundary points in the contrary class to construct the constraints. Thus a novel method, robust weighted twin support vector machine (RWTSVM) was proposed, which can better characterize the underlying local geometric structure and the descriminant information by using a hot kernel function to define the weight matrix of within-class graph, and reduce the influence of outliers by considering within-class weight of the boundary points used to construct constraints in WLTSVM. The experimental results on the artificial and real datasets indicate the effectiveness of RWTSVM method.

twin support vector machine; local geometric structure; outliers; robust; classification

10.11817/j.issn.1672-7207.2015.06.014

TP391.4

A

1672?7207(2015)06?2074?07

2014?06?13；

2014?08?20

國家重點基礎研究發(fā)展計劃(973 計劃)項目(2013CB329502)；國家自然科學基金資助項目(61379101) (Project (2013CB329502) supported by Major State Basic Research Development Program of China; Project (61379101) supported by the National Natural Science Foundation of China)

花小朋，副教授，博士研究生，從事機器學習與數(shù)據(jù)挖掘研究；E-mail：xp_hua@163.com