花小朋，丁世飛

?

基于魯棒局部嵌入的孿生支持向量機(jī)

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

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

針對(duì)已有非平行超平面支持向量機(jī)(NHSVM)分類方法僅考慮訓(xùn)練樣本的全局信息卻忽視訓(xùn)練樣本之間局部幾何結(jié)構(gòu)的問(wèn)題，將魯棒局部線性嵌入(ARLE)方法的基本思想引入NHSVM中，提出一種基于魯棒局部嵌入的孿生支持向量機(jī)(ARLEBTSVM)。該方法不但繼承NHSVM方法具有的異或(XOR)問(wèn)題處理能力；而且可以很好地保持訓(xùn)練樣本空間的局部信息，同時(shí)通過(guò)考慮樣本的全局分布來(lái)自動(dòng)抑制野值樣本點(diǎn)對(duì)嵌入的影響，從而在一定程度上提高分類算法的泛化性能。為了更好地處理非線性分類問(wèn)題，通過(guò)核映射方法構(gòu)造非線性ARLEBTSVM。在人造數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，結(jié)果表明ARLEBTSVM方法具有更好的分類性能。

分類；非平行超平面支持向量機(jī)；局部線性嵌入；異或問(wèn)題；核映射

對(duì)于二分類問(wèn)題，傳統(tǒng)SVM依據(jù)大間隔原則生成單一的分類超平面[1]。存在的缺陷是計(jì)算復(fù)雜度高且沒(méi)有充分考慮樣本的分布[2]。近年來(lái)，作為SVM的拓展方向之一，非平行超平面支持向量機(jī)(nonparallel hyperplane SVM, NHSVM)分類方法正逐漸成為模式識(shí)別領(lǐng)域新的研究熱點(diǎn)。該類方法的研究源于Mangasarian和Wild在TPAMI上提出的廣義特征值近似支持向量機(jī)(generalized eigenvalue proximal SVM, GEPSVM)[3]。GEPSVM摒棄了近似支持向量機(jī)(proximal SVM, PSVM)中平行約束的條件，優(yōu)化目標(biāo)要求超平面離本類樣本盡可能的近，離他類樣本盡可能遠(yuǎn)，問(wèn)題歸結(jié)為求解2個(gè)廣義特征值問(wèn)題。與SVM相比，除了速度上的優(yōu)勢(shì)，GEPSVM能較好地處理異(XOR)問(wèn)題[4?5]?；贕EPSVM，近年發(fā)展了許多NHSVM分類方法，如孿生支持向量機(jī)(twin SVM, TWSVM)[6]、投影孿生支持向量機(jī)(projection twin support vector machine, PTSVM)[7]、最小二乘孿生支持向量回歸機(jī)[8]等。然而，經(jīng)分析發(fā)現(xiàn)，已有的NHSVM分類方法在學(xué)習(xí)過(guò)程中僅考慮訓(xùn)練樣本的全局分布，并沒(méi)有充分考慮樣本之間的局部幾何結(jié)構(gòu)及所蘊(yùn)含的鑒別信息。為了有效揭示樣本內(nèi)部蘊(yùn)含的局部幾何結(jié)構(gòu)，文獻(xiàn)[9?12]分別提出了幾種具有一定代表性的流行學(xué)習(xí)方法：等距映射(isometric mapping, IM)、局部線性嵌入(locally linear embedding, LLE)、拉普拉斯特征映射(laplacian eigenmap, LE)和局部保持投影(locality preserving projections, LPP)。這些方法假設(shè)數(shù)據(jù)位于高維空間中的低維流行上，通過(guò)與譜圖理論相結(jié)合，分別從局部刻畫了高維空間中的數(shù)據(jù)低維非線性流行，并在低維嵌入空間中保持了相應(yīng)的流行結(jié)構(gòu)。盡管這些算法能夠更加有效地挖掘出數(shù)據(jù)的結(jié)構(gòu)信息，但是其中的大部分算法對(duì)數(shù)據(jù)集中的野值都很敏感。而且基于局部的算法往往忽略了數(shù)據(jù)的全局結(jié)構(gòu)信息，導(dǎo)致低維嵌入在反映數(shù)據(jù)流行結(jié)構(gòu)時(shí)發(fā)生偏 差[13]。文獻(xiàn)[13]針對(duì)典型的局部非線性流行學(xué)習(xí)方法LLE，提出了一種新的無(wú)監(jiān)督局部嵌入算法：魯棒局部嵌入(alternative robust local embedding，ARLE)。ARLE充分考慮了數(shù)據(jù)流行的局部結(jié)構(gòu)信息，而且自動(dòng)地抑制了野值對(duì)嵌入的影響，具有比LLE更準(zhǔn)確的嵌入。文獻(xiàn)[14]將ARLE與SVM相結(jié)合，提出一種全局追求支持向量機(jī)(glocalization pursuit SVM, GPSVM)。然而，GPSVM屬于單面支持向量機(jī)范疇。因此，本文作者將ARLE思想引入到NHSVM分類方法中，提出一種基于魯棒局部嵌入的孿生支持向量機(jī)(alternative robust local embedding based twin SVM, ARLEBTSVM)。該方法具有如下優(yōu)勢(shì)：繼承了NHSVM分類方法的特色，如線性模式下對(duì)XOR類數(shù)據(jù)集的分類能力；將ARLE思想引入NHSVM分類方法中，充分考慮了蘊(yùn)含在樣本空間中的局部及全局鑒別信息，從而在一定程度上可以提高算法的泛化性能; 采用核映射方法，ARLEBTSVM可以很容易進(jìn)行非線性嵌入，得到非線性分類方法。

1 TWSVM和PTSVM的簡(jiǎn)單回顧

在已有的NHSVM分類方法中，TWSVM和PTSVM在泛化性能上要優(yōu)于其他分類方法[6-7]。因此，本文選擇這2種非平行超平面支持向量機(jī)分類方法作為比較分析對(duì)象。

1.1 TWSVM

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

要求每個(gè)類超平面離本類樣本盡可能近，離他類樣本盡可能遠(yuǎn)。第1類超平面的優(yōu)化準(zhǔn)則為

顯然，TWSVM優(yōu)化目標(biāo)函數(shù)中沒(méi)有考慮到訓(xùn)練樣本內(nèi)部局部幾何結(jié)構(gòu)中蘊(yùn)含的鑒別信息。

1.2 PTSVM

PTSVM的目標(biāo)也是在維空間中尋找兩個(gè)投影軸和，要求本類樣本投影后盡可能聚集，同時(shí)他類樣本盡可能分散。PTSVM對(duì)應(yīng)的2個(gè)決策超平面為

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

其中：1是第1類樣本的類內(nèi)方差。

顯然，PTSVM的優(yōu)化目標(biāo)函數(shù)考慮的是樣本的散度，類內(nèi)方差1反應(yīng)的是樣本的全局分布，不是樣本之間的局部幾何結(jié)構(gòu)。因此，該方法也沒(méi)有考慮蘊(yùn)含在樣本之間局部鑒別信息。

2 基于魯棒局部嵌入的孿生支持向量機(jī)(ARLEBTSVM)

文獻(xiàn)[13?14]從理論和實(shí)驗(yàn)上系統(tǒng)分析了ARLE方法可以有效的保持樣本空間局部幾何結(jié)構(gòu)信息，而且可以自動(dòng)抑制野值對(duì)嵌入的影響，所以，本文的ARLEBTSVM方法通過(guò)引入ARLE的思想以達(dá)到保持樣本內(nèi)在的局部及全局幾何結(jié)構(gòu)是合理的。

2.1 線性ARLEBTSVM

定義1[14]假定1=，2=，則第(=1, 2)類樣本的類內(nèi)局部及全局保持散度矩陣為

其中：

定義2 線性ARLEBTSVM對(duì)應(yīng)的第1類超平面優(yōu)化準(zhǔn)則為

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

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

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

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

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

將式(10)~(12)代入式(9)得定理1中式(7)成立。

同理可證得定理1中式(8)成立，且

證畢。

線性ARLETSVM的決策函數(shù)為

從式(10)和(13)可知：ARLEBTSVM在求解過(guò)程中需要計(jì)算局部及全局保持類內(nèi)散度矩陣(=1，2)的逆矩陣，而是正半定矩陣，因此，該方法不是嚴(yán)格的凸規(guī)劃問(wèn)題(強(qiáng)凸問(wèn)題)，特別是在小樣本情況下確實(shí)存在矩陣的奇異性。文獻(xiàn)[6]通過(guò)引入規(guī)則項(xiàng)(＞0)解決TWSVM存在的奇異性問(wèn)題，文獻(xiàn)[7]采用類似于PCA降維的方法解決PTSVM存在的奇異性問(wèn)題。這里采用文獻(xiàn)[6]的方法，即ARLEBTSVM方法中用(+)替代，盡可能地小。這樣既可以解決的奇異性，又能保證(+)近似于[5]。

2.2 TWSVM，PTSVM和ARLEBTSVM比較

2.2.1 泛化能力

考慮ARLEBTSVM優(yōu)化目標(biāo)函數(shù)第一項(xiàng)中局部及全局保持類內(nèi)散度矩陣。局部權(quán)反映了樣本點(diǎn)x相對(duì)于x的鄰近程度，其值越大，意味著越有可能是附近的正常樣本點(diǎn)，反之，x可能是離群點(diǎn)。同樣，全局權(quán)反映了樣本點(diǎn)x的局部鄰域相對(duì)于整個(gè)流行結(jié)構(gòu)的自信度，其值越大，表示x的局部鄰域越能刻畫樣本空間的局部幾何結(jié)構(gòu)。以上分析說(shuō)明ARLEBTSVM充分有效考慮了蘊(yùn)含在樣本間局部及全局幾何結(jié)構(gòu)中的鑒別信息。而TWSVM和PTSVM正如1.1及1.2節(jié)分析，兩者均沒(méi)有考慮樣本空間的局部信息。

圖1所示為TWSVM，PTSVM和ARLEBTSVM在人造數(shù)據(jù)集上的決策超平面。顯然，ARLEBTSVM明顯區(qū)別于TWSVM和PTSVM。ARLEBTSVM的2個(gè)超平面反映了2類樣本的內(nèi)在局部流行結(jié)構(gòu); 而TWSVM與PTSVM類似，它們反映的都是每類樣本分布的平均信息。圖1也進(jìn)一步證明了TWSVM和PTSVM確實(shí)沒(méi)有考慮蘊(yùn)含在樣本間局部幾何結(jié)構(gòu)中的鑒別信息。

圖1 ARLEBTSVM，TWSVM與PTSVM三者在人造數(shù)據(jù)集上的決策超平面

2.2.2 時(shí)間復(fù)雜度

TWSVM，PTSVM和ARLEBTSVM3種算法的計(jì)算時(shí)間消耗主要集中在2次規(guī)劃求解上，而三者2次規(guī)劃求解規(guī)模相當(dāng)，所以，宏觀上，三者的計(jì)算時(shí)間復(fù)雜度均為(13+23)。

2.3 非線性ARLEBTSVM

當(dāng)樣本內(nèi)在的幾何結(jié)構(gòu)呈現(xiàn)出高維非線性流行時(shí)，線性ARLEBTSVM方法是沒(méi)有辦法得到非線性流行結(jié)構(gòu)的，因此，本文提出非線性ARLEBTSVM方法。定義一非線性函數(shù)將樣本映射到特征空間，再引入核函數(shù)，結(jié)合特征空間再生理論[14]可以將特征空間中的非線性決策超平面法向量表示為：(其中，表示權(quán)值矢量；=1, 2)。這樣，式(5)和(6)目標(biāo)函數(shù)中的正則化單 元和可分別轉(zhuǎn)換成特征空間中 的正則化單元和，其中。

定義3 非線性ARLEBTSVM對(duì)應(yīng)的第1類超平面優(yōu)化準(zhǔn)則為

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

定理2 非線性ARLEBTSVM優(yōu)化準(zhǔn)則式(16)對(duì)應(yīng)的對(duì)偶問(wèn)題為

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

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

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

將式(21)~(23)代入式(20)得定理2中式(18)成立。

同理可證得定理2中式(19)成立，且

證畢。

非線性ARLEBTSVM的2個(gè)決策超平面為

線性ARLEBTSVM的決策函數(shù)為

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

在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上分別對(duì)TWSVM，PTSVM與ARLEBTSVM進(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ù)集

人造數(shù)據(jù)集經(jīng)常被用來(lái)測(cè)試算法效果[2]，這里分別使用交叉數(shù)據(jù)集和流行數(shù)據(jù)集來(lái)驗(yàn)證本文ARLEBTSVM分類性能，并與TWSVM和PTSVM進(jìn)行對(duì)比。

3.1.1 測(cè)試交叉數(shù)據(jù)集

相對(duì)于單面支持向量機(jī)，線性模式下對(duì)XOR問(wèn)題的求解能力是NHSVM分類算法優(yōu)勢(shì)之一[3?4,6]。因此，這里首先驗(yàn)證ARLEBTSVM求解XOR的能力。圖2給出了TWSVM，PTSVM與ARLEBTSVM 3個(gè)分類器在交叉數(shù)據(jù)集上“Crossplanes”(XOR的推 廣)[3?4, 6]上的分類性能。顯然3個(gè)算法產(chǎn)生的分類面重合，而且可以較好的求解XOR問(wèn)題，并得到100%的學(xué)習(xí)精度。這也進(jìn)一步證明了本文ARLEBTSVM繼承了NHSVM分類算法的特色，即線性模式下對(duì)XOR問(wèn)題的求解能力比單面支持向量機(jī)算法的求解能力強(qiáng)。

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

3.1.2 測(cè)試流行數(shù)據(jù)集

數(shù)據(jù)集two-moons經(jīng)常被用于測(cè)試一些流行學(xué)習(xí)方法[2]。這里通過(guò)與TWSVM和PTSVM方法進(jìn)行比較，測(cè)試本文方法在2種不同復(fù)雜度two-moons數(shù)據(jù)集(圖3(a)和圖3(b))上保持非線性局部流行結(jié)構(gòu)的性能。

(a) two-moons-1; (b) two-moons-2

圖3 2種不同復(fù)雜度的two-moons數(shù)據(jù)集

Fig. 3 Two kinds of two-moons datasets with different complexity.

實(shí)驗(yàn)設(shè)計(jì)：2種two-moons數(shù)據(jù)集均為100，其中正負(fù)類數(shù)據(jù)數(shù)各50，隨機(jī)抽取40%訓(xùn)練集和60%測(cè)試集，重復(fù)10次，分別記錄實(shí)驗(yàn)結(jié)果，且計(jì)算實(shí)驗(yàn)結(jié)果的平均值如表1所示。參數(shù)1與2的搜索范圍均為{2|=?7, ?4, ?1, 0, +3, +7, +10}；核函數(shù)選用GAUSS核，核參數(shù)搜索范圍為{10|=?3, ?2, ?1, …, +3}；規(guī)則項(xiàng)中取值10-6。ARLEBTSVM中熱參數(shù)的搜索范圍為{2|=1, 2, …, 7}，近鄰數(shù)的搜索范圍為{1, 2, …, 10}。

從表1可以看出：1) ARLEBTSVM方法對(duì)于流行數(shù)據(jù)集的測(cè)試性能比TWSVM和PTSVM方法的高，這也進(jìn)一步證明了本文方法能夠更好地保持樣本間非線性局部流行結(jié)構(gòu)鑒別信息。2) 對(duì)于two-moons-1，ARLEBTSVM測(cè)試精度比TSVM和PTSVM平均高2.00%。對(duì)于two-moons-2，ARLEBTSVM測(cè)試精度比TWSVM和PTSVM平均高出2.25%。這表明，當(dāng)數(shù)據(jù)集的拓?fù)浣Y(jié)構(gòu)變得更加復(fù)雜而不規(guī)則時(shí)，本文ARLEBTSVM仍然保持較好的泛化性能。

表1 TWSVM，PTSVM 和 ARLEBTSVM算法的測(cè)試精度比較

Table 1 Classification accuracy of TWSVM, PTSVM and ARLEBTSVM on two kinds of two-moons Datasets %

數(shù)據(jù)集TWSVMPTSVMARLEBTSVM two-moons-197.7597.7599.75 two-moons-296.5096.7598.75

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

為了更全面地說(shuō)明本文ARLEBTSVM分類方法具有的分類性能，測(cè)試UCI數(shù)據(jù)集，同時(shí)與TWSVM，PTSVM進(jìn)行對(duì)比。

UCI數(shù)據(jù)集經(jīng)常被用來(lái)測(cè)試算法的分類精 度[4?7, 16?17]。在該測(cè)試階段，抽取該數(shù)據(jù)集的8個(gè)分類數(shù)據(jù)子集：Hepatitis，Sonar，Glass_12，P_gene，Wpbc，Cleve，Spectf和Haberman來(lái)分別測(cè)試TWSVM，PTSVM和本文GLPBTSVM。對(duì)于每個(gè)數(shù)據(jù)子集，選用5-折交叉驗(yàn)證方法[16]。3種方法均采用SOR[18]技術(shù)進(jìn)行2次規(guī)劃求解，實(shí)驗(yàn)結(jié)果為平均識(shí)別精度和訓(xùn)練時(shí)間。相關(guān)參數(shù)搜索范圍與3.1.2節(jié)中的相同。表2和表3所示分別為線性模式及非線性模式下3種分類方法的測(cè)試結(jié)果。

表2 線性TWSVM，PTSVM與ARLEBTSVM的測(cè)試結(jié)果

表3 非線性TWSVM, PTSVM與ARLEBTSVM的測(cè)試結(jié)果

從泛化性能上看，無(wú)論是線性模式還是非線性模式，本文的ARLEBTSVM方法對(duì)未知樣本的識(shí)別精度總體上均比TWSVM和PTSVM的高。這進(jìn)一步表明，充分考慮樣本空間局部及全局結(jié)構(gòu)信息確實(shí)能夠在一定程度上提高多面分類器的泛化性能。

從訓(xùn)練時(shí)間上看，宏觀上，3種方法基本處于同樣的數(shù)量級(jí)，這主要是因?yàn)?種算法的時(shí)間復(fù)雜度主要都集中在2次規(guī)劃求解上，而三者2次規(guī)劃求解的規(guī)模相當(dāng)；微觀上，本文的ARLEBTSVM要略慢于TWSVM和PTSVM，從實(shí)驗(yàn)過(guò)程上看，這主要是因?yàn)锳RLEBTSVM中c計(jì)算包含計(jì)算最近鄰圖信息，所以計(jì)算量偏高。

4 結(jié)論

1) 根據(jù)已有NHSVM方法存在的不足，將ARLE基本原理引入NHSVM中，提出一種新的方法即ARLEBTSVM。該方法不僅繼承了NHSVM方法較好的異或(XOR)問(wèn)題的求解能力，而且在一定程度上克服了已有NHSVM方法沒(méi)有充分考慮訓(xùn)練樣本間局部幾何結(jié)構(gòu)信息的缺陷。

2)對(duì)于非線性分類問(wèn)題，本文采用核映射方法構(gòu)造非線性特征空間，將線性方法拓展到非線性情況，提出非線性ARLEBTSVM方法。實(shí)驗(yàn)中選用具有代表性的TWSVM和PTSVM進(jìn)行比較，結(jié)果表明本文ARLEBTSVM方法具有較好的泛化性能。

[1] 王雪松, 高陽(yáng), 程玉虎. 基于隨機(jī)子空間—正交局部保持投影的支持向量機(jī)[J]. 電子學(xué)報(bào), 2011, 39(8): 1746?1750.
WANG Xuesong, GAO Yang, CHENG Yuhu. Support vector machine based on random subspace and orthogonal locality preserving projection[J]. Acta Electronica Sinica, 2011, 39(8): 1746?1750.

[2] 皋軍, 王士同, 鄧趙紅. 基于全局和局部保持的半監(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.

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

[4] 業(yè)巧林, 趙春霞, 陳小波. 基于正則化技術(shù)的對(duì)支持向量機(jī)特征選擇算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2011, 48(6): 1029?1037.
YE Qiaolin, ZHAO Chunxia, CHEN Xiaobo. A feature selection method for TWSVM via a regularization technique[J]. Journal of Computer Research and Development, 2011, 48(6): 1029?1037.

[5] Ding S F, Yu J Z, Qi B J. An overview on twin support vector machines[J]. Artificial Intelligence Review, 2014, 42(2): 245?252.

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

[7] Chen X B, Yang J, Ye Q L, et al. Recursive projection twin support vector machine via within-class variance minimization[J]. Pattern Recognition, 2011, 44(10): 2643?2655.

[8] Huang H J, Ding S F, Shi Z Z. Primal least squares twin support vector regression[J]. Journal of Zhejiang University: Science C, 2013, 14(9): 722?732.

[9] Tenenbaum J B, Silva V D, Langford J C. A global geometric framework for nonlinear dimensionality reduction[J]. Science, 2000, 290(5500): 2319?2323.

[10] Roweis S T, Saul L K. Nonlinear dimensionality reduction by locally linear embedding[J]. Science, 2000, 290(5500): 2323?2326.

[11] Belkin M, Niyogi P. Laplacian eigenmaps for dimensionality reduction and data representation[J]. Neural Computation, 2003, 15(6): 1373?1369.

[12] He X F, Niyogi P. Locality preserving projection[EB/OL]. [2012?07?08]. http://www.docin.com/p-202458452.html.

[13] Xue H, Chen S. Alternative robust local embedding[C]// The International Conference on Wavelet Analysis and Pattern Recognition (ICWAPR). Beijing, 2007: 591?596.

[14] Xue H, Chen S. Glocalization pursuit support vector machine[J]. Neural Computing and Applications, 2011, 20(7): 1043?1053.

[15] 鄧乃楊, 田英杰. 支持向量機(jī): 理論、算法與拓展[M]. 北京: 科學(xué)出版社, 2009: 11?17.
DENG Naiyang, TIAN Yingjie. Support vector machine: Theory, algorithm and extension[M]. Beijing: Science Press, 2009: 11?17.

[16] Wang X M, Chung F L, Wang S T. On minimum class locality preserving variance support vector machine[J]. Patter Recognition, 2010, 43(8): 2753?2762.

[17] Ding S F, Hua X P. Recursive least squares projection twin support vector machines for nonlinear classification[J]. Neurocomputing, 2014, 130(4): 3?9.

[18] Shao Y H, Zhang C H, Wang X B, et al. Improvements on twin support vectot machines[J]. IEEE Transactions on Neural Networks, 2011, 22(6): 962?968.

An alternative robust local embding based on twin support vector machines

HUA Xiaopeng1, 2, 3, DING Shifei1, 2

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

Aiming at the problem that many existing nonparallel hyperplane support vector machine (NHSVM) methods only considered the global information of the training samples in the same class and did not fully take into account the local geometric structure and the underlying descriminant information, an alternative robust local embedding based twin support vector machine (ARLEBTSVM) was presented by introducing the basic theories of alternative robust local embedding (ARLE) algorithm into the NHSVM. ARLEBTSVM not only inherits the characteristic of NHSVM methods which can well deal with the XOR problem, but also fully considers the local and global geometric structure of training samples in the same class and shows the local and global underlying discriminant information. In addition, in order to well deal with the nonlinear classification problem, the kernel mapping method was used to extend ARLEBTSVM to the nonlinear case. Experimental results on some artificial datasets and many real UCI datasets indicate that the proposed ARLEBTSVM method has better classification ability.

classification; nonparallel hyperplane support vector machine; locally linear embedding; xor problem; kernel mapping

TP391.4

A

1672?7207(2015)01?0149?08

2014?02?26；

2014?04?30

國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展規(guī)劃(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)

丁世飛，教授，博士生導(dǎo)師，從事機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘研究；E-mail: dingsf@cumt.edu.cn

10.11817/j.issn.1672?7207.2015.01.021

(編輯 楊幼平)