一種改進(jìn)的投影孿生支持向量機(jī)

花小朋，孫一顆，丁世飛

(1.鹽城工學(xué)院 信息工程學(xué)院，江蘇 鹽城 224051； 2. 中國(guó)礦業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 徐州 221116)

?

一種改進(jìn)的投影孿生支持向量機(jī)

花小朋1，孫一顆1，丁世飛2

(1.鹽城工學(xué)院 信息工程學(xué)院，江蘇 鹽城 224051； 2. 中國(guó)礦業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 徐州 221116)

摘要：針對(duì)投影孿生支持向量機(jī)(PTSVM)在訓(xùn)練階段欠考慮樣本空間局部結(jié)構(gòu)和局部信息的缺陷，提出一種具有一定局部學(xué)習(xí)能力的有監(jiān)督分類(lèi)方法：加權(quán)投影孿生支持向量機(jī)(weighted PTSVM，WPTSVM)。相比于PTSVM，WPTSVM優(yōu)勢(shì)在于：通過(guò)構(gòu)造類(lèi)內(nèi)近鄰圖為每個(gè)樣本獲取特定的權(quán)值，并且以加權(quán)均值取代標(biāo)準(zhǔn)均值，在一定程度上提高了算法的局部學(xué)習(xí)能力；選取異類(lèi)樣本集中少量邊界點(diǎn)構(gòu)造優(yōu)化問(wèn)題的約束條件，很大程度上降低了二次規(guī)劃求解的時(shí)間復(fù)雜度；繼承了PTSVM的優(yōu)點(diǎn)，可以看成PTSVM的推廣算法。理論分析及其在人造數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上的測(cè)試結(jié)果表明該方法具有上述優(yōu)勢(shì)。

關(guān)鍵詞：分類(lèi)；投影孿生支持向量機(jī)；局部信息；加權(quán)均值；近鄰圖；二次規(guī)劃；約束條件；時(shí)間復(fù)雜度

在分類(lèi)問(wèn)題中，經(jīng)典支持向量機(jī)(SVM)依據(jù)間隔最大化準(zhǔn)則生成分類(lèi)決策面，存在訓(xùn)練時(shí)間復(fù)雜度偏高和欠考慮樣本分布情況的缺陷[1-2]。近年來(lái)，作為經(jīng)典SVM的改進(jìn)方法，非平行超平面分類(lèi)器(nonparellel hyperplane classifiers，NHCs)[3]已經(jīng)成為模式識(shí)別領(lǐng)域新的研究熱點(diǎn)之一。孿生支持向量機(jī)(twin support vector machine，TWSVM)[4]是NHCs方法中主要代表性算法之一，其主要思想源于泛化特征值中心支持向量機(jī)(generalized eigenvalue proximal SVM，GEPSVM)[5]。TWSVM將GEPSVM中兩個(gè)優(yōu)化子問(wèn)題轉(zhuǎn)換成兩個(gè)形如SVM的小規(guī)模二次規(guī)劃問(wèn)題，從而使其訓(xùn)練時(shí)間復(fù)雜度縮減為經(jīng)典SVM的1/4。除了訓(xùn)練速度上的優(yōu)勢(shì)，TWSVM還繼承了GEPSVM能夠在線(xiàn)性模式很好地處理異或(XOR)樣本分類(lèi)問(wèn)題的優(yōu)勢(shì)。然而，當(dāng)兩類(lèi)樣本具有不同散度分布時(shí)，TWSVM的泛化性能欠佳[6]。文獻(xiàn)[7]提出一種新的非平行超平面分類(lèi)器：投影孿生支持向量機(jī) (projection twin support vector machine，PTSVM)。與TWSVM不同的是，PTSVM優(yōu)化目的是為每類(lèi)樣本尋找最佳投影軸，而且通過(guò)遞歸迭代算法，PTSVM能夠生成多個(gè)正交投影軸。實(shí)驗(yàn)結(jié)果表明，PTSVM對(duì)復(fù)雜的XOR問(wèn)題具有更好的分類(lèi)能力。為解決非線(xiàn)性分類(lèi)問(wèn)題。文獻(xiàn)[8]進(jìn)一步提出PTSVM的非線(xiàn)性方法。

然而分析發(fā)現(xiàn)，PTSVM在訓(xùn)練過(guò)程中僅僅考慮樣本空間的全局結(jié)構(gòu)和全局信息，忽視了樣本空間的局部結(jié)構(gòu)和局部信息。許多研究結(jié)果表明同類(lèi)數(shù)據(jù)集中大部分樣本在局部上是關(guān)聯(lián)的(即數(shù)據(jù)集中存在潛藏的局部幾何結(jié)構(gòu))，而這種內(nèi)在的局部信息對(duì)數(shù)據(jù)分類(lèi)又是至關(guān)重要的[9]。這種潛在的局部信息可以通過(guò)數(shù)據(jù)集中樣本間的k近鄰關(guān)系進(jìn)行挖掘[9-11]。

基于上述分析，本文基于PTSVM提出一種新的具有一定局部學(xué)習(xí)能力的非平行超平面分類(lèi)器算法：加權(quán)投影孿生支持向量機(jī)(weighted PTSVM，WPTSVM)。相比于PTSVM，WPTSVM優(yōu)勢(shì)體現(xiàn)在以下4個(gè)方面：1)通過(guò)構(gòu)造類(lèi)內(nèi)近鄰圖為每個(gè)樣本獲取特定的權(quán)值，并且以加權(quán)均值取代標(biāo)準(zhǔn)均值，在一定程度上提高了算法的局部學(xué)習(xí)能力；2)選取異類(lèi)樣本集中少量邊界點(diǎn)構(gòu)造優(yōu)化問(wèn)題的約束條件，很大程度上降低了二次規(guī)劃求解的時(shí)間復(fù)雜度；3)WPTSVM繼承了PTSVM的優(yōu)點(diǎn)，可以看成PTSVM的推廣算法。4)WPTSVM具有更好分類(lèi)性能。

1投影孿生支持向量機(jī)(PTSVM)

第1類(lèi)超平面的優(yōu)化準(zhǔn)則

(2)

式中C1是懲罰參數(shù)，l為損失變量。

2加權(quán)投影孿生支持向量機(jī)(WPTSVM)

2.1算法構(gòu)造

為刻畫(huà)同類(lèi)樣本集內(nèi)在的緊湊型和異類(lèi)樣本集間的分散性，依據(jù)圖論[10,12]為每類(lèi)決策面構(gòu)建類(lèi)內(nèi)近鄰圖Gs和類(lèi)間近鄰圖Gd。

(3)

式中：t為熱核參數(shù)，Ne(x)表示x的k近鄰樣本集。

(4)

(5)

定義 3WPTSVM算法中，第1類(lèi)訓(xùn)練樣本集相應(yīng)決策超平面的優(yōu)化準(zhǔn)則WPTSVM-1：

(6)

第2類(lèi)超平面優(yōu)化準(zhǔn)則WPTSVM-2：

(7)

(8)

類(lèi)似于傳統(tǒng)SVM求解方法，通過(guò)引入拉格朗日函數(shù)生成式(8)的對(duì)偶問(wèn)題

(9)

式中α=[α1,α2,…,αm2]T。

由此對(duì)偶問(wèn)題的求解可得原問(wèn)題式(6)中投影軸w1。類(lèi)似的方法，可求原問(wèn)題式(7)中投影軸w2。

對(duì)于未知樣本x，WPTSVM的決策函數(shù)為

(10)

2.2算法分析

這里以WPTSVM的第1類(lèi)樣本優(yōu)化問(wèn)題WPTSVM-1為例進(jìn)行算法分析，第2類(lèi)樣本優(yōu)化問(wèn)題WPTSVM-2有類(lèi)似的算法分析。

定理1式(9)為凸二次規(guī)劃。

證明式(9)核矩陣：

定理 2假定α是對(duì)偶問(wèn)題式(9)的解，則w1是原優(yōu)化問(wèn)題式(6)的全局最優(yōu)解。

證明由定理1的證明可得，式(9)為凸二次規(guī)劃問(wèn)題，又依據(jù)文獻(xiàn)[14]中引理3的滿(mǎn)足條件可知，該二次規(guī)劃的解為全局最優(yōu)解。證畢。

2.3算法比較

2.3.1泛化性能

定理 3PTSVM是WPTSVM的特例。

證明考慮WPTSVM的第1類(lèi)樣本的優(yōu)化準(zhǔn)則(7)。令D(1)=I∈Rm1×m1，F(xiàn)(2)=I∈Rm2×m2，則式(7)轉(zhuǎn)化為PTSVM的第1類(lèi)樣本的優(yōu)化準(zhǔn)則(2)。對(duì)于WPTSVM的第2類(lèi)樣本的優(yōu)化準(zhǔn)則(8)有類(lèi)似的特性。因此，PTSVM是WPTSVM的特例，而WPTSVM是PTSVM的推廣算法。證畢。

定理3說(shuō)明了本文提出的WPTSVM算法繼承了PTSVM的優(yōu)點(diǎn)。進(jìn)一步比較式(7)和(2)可知， PTSVM僅僅考慮類(lèi)內(nèi)樣本的全局信息，而WPTSVM用加權(quán)均值代替PTSVM中標(biāo)準(zhǔn)均值，可以在一定程度上提高算法的局部學(xué)習(xí)能力，因?yàn)榛诮張D的加權(quán)均值比起標(biāo)準(zhǔn)均值更能體現(xiàn)樣本空間的局部結(jié)構(gòu)[13]。除此之外，WPTSVM還在優(yōu)化目標(biāo)函數(shù)中引入了樣本權(quán)值，權(quán)值越大，說(shuō)明該樣本越重要，對(duì)保持訓(xùn)練樣本集潛在局部信息的貢獻(xiàn)程度越大。圖1給出了WPTSVM與PTSVM在人造數(shù)據(jù)集上的分類(lèi)決策面。不難看出，WPTSVM的決策面能夠在一定程度上體現(xiàn)樣本集內(nèi)在局部流形結(jié)構(gòu)，而PTSVM相對(duì)較弱。

圖1　兩種算法人造數(shù)據(jù)集上的比較Fig.1　Comparision of two algorithms on artificial dataset

2.3.2訓(xùn)練時(shí)間復(fù)雜度

2.3.3構(gòu)造非線(xiàn)性分類(lèi)算法

針對(duì)線(xiàn)性不可分情況，本文進(jìn)一步提出基于核空間的非線(xiàn)性WPTSVM算法——NWPTSVM。

定義4NWPTSVM的第1類(lèi)超平面的優(yōu)化準(zhǔn)則為

(11)

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

(12)

通過(guò)引入拉格朗日函數(shù)，可按照類(lèi)似上述WPTSVM算法的推導(dǎo)過(guò)程分別得出式(11)和(12)的對(duì)偶形式，然后通過(guò)二次規(guī)劃求解可求得投影矢量u1和u2。NWPTSVM的決策函數(shù)為

(13)

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

實(shí)驗(yàn)選用人造數(shù)據(jù)集和真實(shí)數(shù)據(jù)集，進(jìn)一步驗(yàn)證本文WPTSVM方法的有效性。實(shí)驗(yàn)環(huán)境：2.3 GHz CPU，2 GB內(nèi)存，實(shí)驗(yàn)軟件MATLAB 7.1。

3.1復(fù)雜交叉數(shù)據(jù)集

相對(duì)于經(jīng)典SVM，線(xiàn)性模式下對(duì)XOR問(wèn)題的測(cè)試能力是非平行超平面分離器優(yōu)勢(shì)之一[3-5]。因此，本節(jié)首先驗(yàn)證MPTSVM測(cè)試交叉數(shù)據(jù)集的能力。圖2給出一種較復(fù)雜的人造交叉數(shù)據(jù)集：Comxor[7]。表1給出了TWSVM、PTSVM和WPTSVM三種算法在該測(cè)試數(shù)據(jù)集上10折交叉驗(yàn)證結(jié)果。參數(shù)C1與C2的搜索范圍為{2i|i=-8，-6，…，+8}；WPTSVM中類(lèi)內(nèi)近鄰參數(shù)k1的搜索范圍為{1,2，…,9}，類(lèi)間近鄰參數(shù)k2=5，熱核參數(shù)t的搜索范圍為{2i|i=-1，0，…，8}。從表1實(shí)驗(yàn)結(jié)果來(lái)看，PTSVM分類(lèi)性能優(yōu)于TWSVM，而本文WPTSVM則具有更佳的分類(lèi)性能。

圖2　復(fù)雜交叉數(shù)據(jù)集Fig.2　Compxor dataset

Table 1Classification comparision of three algorithms on comxor dataset

DatasetTWSVMPTSVMWPTSVMComxor93.76±6.7095.67±4.7397.36±2.90

3.2流形數(shù)據(jù)集

數(shù)據(jù)集two-moons (如圖3所示) 的結(jié)構(gòu)具有明顯局部流形，所以該數(shù)據(jù)集多用于測(cè)試算法的局部學(xué)習(xí)能力[2,13]。這里通過(guò)測(cè)試two-moons數(shù)據(jù)集，并與TWSVM和PTSVM方法進(jìn)行比較，驗(yàn)證本文WPTSVM方法局部學(xué)習(xí)能力。

圖3　Two-moons數(shù)據(jù)集Fig.3　Two-moons dataset

實(shí)驗(yàn)選擇正負(fù)類(lèi)樣本各為50的two-moons數(shù)據(jù)集。隨機(jī)抽取40%訓(xùn)練集和60%測(cè)試集進(jìn)行實(shí)驗(yàn)，重復(fù)此過(guò)程10次并記錄實(shí)驗(yàn)結(jié)果的平均值

(見(jiàn)表2)。顯然，WPTSVM方法具有更好的測(cè)試效果，這說(shuō)明本文加權(quán)措施的確能夠在一定程度上提高PTSVM算法的局部學(xué)習(xí)能力。

表23種算法在雙月形數(shù)據(jù)集上的分類(lèi)精度(%)比較

Table 2Classification comparision of three algorithms on two-moons dataset

DatasetTWSVMPTSVMWPTSVMtwo-moons77.17±13.7276.33±12.3678.83±8.86

3.3UCI數(shù)據(jù)集

UCI數(shù)據(jù)集經(jīng)常被用來(lái)驗(yàn)證算法的分類(lèi)精度[3-7,15-16]。該數(shù)據(jù)集包含若干數(shù)據(jù)子集，涉及諸多應(yīng)用領(lǐng)域。

實(shí)驗(yàn)中選取部分?jǐn)?shù)據(jù)子集，利用10-折交叉驗(yàn)證法測(cè)試算法分類(lèi)性能。非線(xiàn)性算法實(shí)驗(yàn)中，選擇高斯核exp(-‖xi-xj‖2/σ)作為核函數(shù)，參數(shù)σ的搜索范圍為{2i|i=-1,0, …,7}，其他參數(shù)搜索范圍同3.1節(jié)。線(xiàn)性模式及非線(xiàn)性模式下實(shí)驗(yàn)結(jié)果如表3和表4分別所示。

從訓(xùn)練時(shí)間上看: TWSVM與PTSVM相當(dāng)，WPTSVM明顯比這兩種算法快。原因是WPTSVM選用少量邊界樣本進(jìn)行二次規(guī)劃求解，而其他兩種算法則選擇異類(lèi)中全部樣本。

從分類(lèi)性能上看：本文提出的WPTSVM 算法具有更好的分類(lèi)能力，這也進(jìn)一步佐證了本文提高PTSVM算法局部學(xué)習(xí)能力的措施確實(shí)有效。

表3　線(xiàn)性模式下3種算法的實(shí)驗(yàn)比較

表4　非線(xiàn)性模式下3種算法的實(shí)驗(yàn)比較

4結(jié)束語(yǔ)

本文基于投影孿生支持向量機(jī)(PTSVM )提出一種新的的非平行超平面分類(lèi)器方法：加權(quán)投影孿生支持向量機(jī)(WPTSVM )。WPTSVM不僅繼承了PTSVM方法的優(yōu)點(diǎn)，而且在一定程度上提高了算法局部學(xué)習(xí)能力。除此之外，WPTSVM通過(guò)類(lèi)間近鄰圖選擇少量邊界樣本構(gòu)造優(yōu)化問(wèn)題約束條件，相當(dāng)程度上降低了二次規(guī)劃求解時(shí)間復(fù)雜度。理論分析及實(shí)驗(yàn)結(jié)果均驗(yàn)證了本文所提算法的有效性。誠(chéng)然，WPTSVM在構(gòu)造類(lèi)內(nèi)及類(lèi)間近鄰圖時(shí)，需要花費(fèi)額外的計(jì)算開(kāi)銷(xiāo)，特別是在學(xué)習(xí)樣本數(shù)目較大時(shí)，算法計(jì)算復(fù)雜度會(huì)偏高，這也是今后進(jìn)一步研究的目標(biāo)。

參考文獻(xiàn):

[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.

HUAxiaopeng, DING Shifei. Locality preserving twin support vector machines [J]. Journal of computer research and development, 2014, 51(3): 590-597.

[3] DING Shifei, HUA Xiaopeng, YU Junzhao. An overview on nonparallel hyperplane support vector machines[J]. Neural computing and applications, 2014, 25(5): 975-982.

[4]JAYADEVA, KHEMCHAND R, CHANDRA S. Twin support vector machines for pattern classification [J]. IEEE transaction on pattern analysis and machine intelligence, 2007, 29 (5): 905-910.

[5]MANGASARIAN O L, WILD E W. MultisurFace proximal support vector machine classification via generalized eigenvalues [J]. IEEE transactions on pattern analysis and machine intelligence, 2006, 28 (1): 69-74.

[6] PENG Xinjun,XU Dong. Bi-density twin support vector machines for pattern recognition[J]. Neurocomputing, 2013, 99: 134-143.

[7] 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/11): 2643-2655.

[8]SHAO Yuanhai, WANG Zhen, CHEN Weijie, et al. A regularization for the projection twin support vector machine[J]. Knowledge-based systems, 2013, 37 (1): 203-210.

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

[10]COVER T M, HART P E. Nearest neighbor pattern classification[J]. IEEE transactions on information theory, 1967, 13 (1): 21-27.

[11]WANG Xiaoming, CHUNG Fulai, WANG Shitong. On minimum class locality preserving variance support vector machine[J]. Patter recognition, 2010, 43(8): 2753-2762.

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

[13]皋軍, 黃麗莉, 王士同. 基于局部子域的最大間距判別分析 [J ]. 控制與決策, 2014, 29 (5): 827-832.

GAO Jun, HUANG Lili, WANG Shitong. Local sub-domains based maximum margin criterion [J]. Control and decision, 2014, 29 (5): 827-832.

[14]鄧乃楊, 田英杰. 支持向量機(jī)—理論、算法與拓展[M]. 北京: 科學(xué)出版社, 2009: 164-223.

[15]丁立中, 廖士中. 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.

[16]XUE Hui, CHEN Songchan. Glocalization pursuit support vector machine [J].Neural computing and applications, 2011, 20(7):1043-1053.

花小朋，男，1975年生，副教授，博士，主要研究方向?yàn)闄C(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘，發(fā)表學(xué)術(shù)論文10余篇。

孫一顆，男，1993年生，碩士研究生，主要研究方向?yàn)闄C(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘，申請(qǐng)發(fā)明專(zhuān)利2項(xiàng)。

丁世飛，男，1963年生，教授，博士生導(dǎo)師，中國(guó)計(jì)算機(jī)學(xué)會(huì)高級(jí)會(huì)員，中國(guó)人工智能學(xué)會(huì)高級(jí)會(huì)員，江蘇省計(jì)算機(jī)學(xué)會(huì)人工智能專(zhuān)業(yè)委員會(huì)委員，主要研究方向?yàn)橹悄苄畔⑻幚恚壳爸鞒謬?guó)家973項(xiàng)目1項(xiàng)、國(guó)家自然科學(xué)基金項(xiàng)目1項(xiàng)，發(fā)表學(xué)術(shù)論文60余篇。

中文引用格式：花小朋，孫一顆，丁世飛.一種改進(jìn)的投影孿生支持向量機(jī)[J]. 智能系統(tǒng)學(xué)報(bào)， 2016, 11(3): 384-391.

英文引用格式：HUA Xiaopeng， SUN Yike， DING Shifei. An improved projection twin support vector machine[J]. CAAI transactions on intelligent systems, 2016, 11(3): 384-391.

An improved projection twin support vector machine

HUA Xiaopeng1， SUN Yike1， DING Shifei2

(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)

Abstract：A supervised classification method having a local learning ability, called weighted projection twin support vector machine (WPTSVM), is proposed. This method aims to improve upon a defect that projection twin support vector machines (PTSVMs) have, namely, that PTSVMs do not take account of the local structure and local information of a sample space in the training process. Compared with PTSVM, WPTSVM improves its local learning ability to some extent by attaching different weights for each sample according to the within-class neighborhood graph and replacing the standard mean with a weighted mean. Moreover, to reduce computational complexity, WPTSVM chooses a small number of boundary points in the contrary-class based on the between-class neighborhood graph to construct constraints of the original optimization problems. The method inherits the merits of PTSVM and can be regarded as an improved version of PTSVM. Experimental results on artificial and real datasets indicate the effectiveness of the WPTSVM method.

Keywords：classification; projection twin support vector machine; local information; weighted mean; neighborhood graph; quadratic programming; constraint condition; time complexity

作者簡(jiǎn)介：

中圖分類(lèi)號(hào)：TP391.4

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1673-4785(2016)03-0384-06

通信作者：花小朋. E-mail：xp_hua@163.com.

基金項(xiàng)目：國(guó)家重點(diǎn)基礎(chǔ)研究計(jì)劃項(xiàng)目(2013CB329502);國(guó)家自然科學(xué)基金項(xiàng)目(61379101); 江蘇省自然科學(xué)基金項(xiàng)目(BK20151299).

收稿日期：2016-03-20.網(wǎng)絡(luò)出版日期：2016-05-13.

DOI:10.11992/tis.2016030.

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20160513.0924.024.html