花小朋，丁世飛

?

魯棒的加權(quán)孿生支持向量機(jī)

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

(1. 鹽城工學(xué)院信息工程學(xué)院，江蘇鹽城，224051；2. 中國(guó)礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇徐州，221116；3. 中國(guó)科學(xué)院計(jì)算技術(shù)研究所智能信息處理重點(diǎn)實(shí)驗(yàn)室，北京，100190)

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

孿生支持向量機(jī)；局部幾何結(jié)構(gòu)；噪聲點(diǎn)；魯棒性；分類

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

1 魯棒的加權(quán)孿生支持向量機(jī)(RWTSVM)

1.1 線性RWTSVM

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

要求每個(gè)類超平面離本類具有高密度相關(guān)的樣本點(diǎn)盡可能近，離相反類中具有較大權(quán)重的邊界樣本點(diǎn)盡可能遠(yuǎn)。

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

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

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

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

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

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

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

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

(RWTSVM1)

和

(RWTSVM2)

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

定理1 線性RWTSVM優(yōu)化準(zhǔn)則式(7)對(duì)應(yīng)的對(duì)偶問題(DRWTSVM1)為

優(yōu)化準(zhǔn)則式(8)對(duì)應(yīng)的對(duì)偶問題(DRWTSVM2)為

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

證明。考慮線性RWTSVM的優(yōu)化準(zhǔn)則式(7)，對(duì)應(yīng)的拉格朗日函數(shù)為

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

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

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

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

證畢。

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

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

1.2 非線性RWTSVM

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

其中：=[TT]T。

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

(19)

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

定理2 NRWTSVM優(yōu)化準(zhǔn)則式(19)對(duì)應(yīng)的對(duì)偶問題(DNRWTSVM1)為

(21)

NRWTSVM優(yōu)化準(zhǔn)則式(20)對(duì)應(yīng)的對(duì)偶問題(DNRWTSVM2)為

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

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

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

(25)

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

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

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

證畢。

NRWTSVM的決策函數(shù)為

2 RWTSVM與WLTSVM比較

2.1 泛化性能比較

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

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

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

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

2.2 計(jì)算復(fù)雜度比較

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

3 實(shí)驗(yàn)分析

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

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

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

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

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

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

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

表1 線性TWSVM，WLTSVM與RWTSVM的測(cè)試結(jié)果

表2 非線性TWSVM，WLTSVM與RWTSVM的測(cè)試結(jié)果

從訓(xùn)練時(shí)間上看：本文RWTSVM與WLTSVM相當(dāng)，這與2.2節(jié)計(jì)算復(fù)雜度分析一致；但訓(xùn)練速度明顯比TWSVM快，這主要是因?yàn)門WSVM用相反類全部樣本進(jìn)行二次規(guī)劃求解，而RWTSVM與WLTSVM用少量邊界樣本點(diǎn)求解。

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

4 結(jié)論

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

[1] 皋軍, 王士同, 鄧趙紅. 基于全局和局部保持的半監(jiān)督支持向量機(jī)[J]. 電子學(xué)報(bào), 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] 花小朋, 丁世飛. 局部保持對(duì)支持向量機(jī)[J]. 計(jì)算機(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: 一個(gè)支持向量機(jī)核矩陣的近似計(jì)算算法[J]. 計(jì)算機(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

國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃(973 計(jì)劃)項(xiàng)目(2013CB329502)；國(guó)家自然科學(xué)基金資助項(xiàng)目(61379101) (Project (2013CB329502) supported by Major State Basic Research Development Program of China; Project (61379101) supported by the National Natural Science Foundation of China)

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