添加Universum數(shù)據(jù)的最小二乘投影雙支持向量機

魯淑霞,佟樂,朱晨旭

(1.河北大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院,河北保定　071002；2.西北農(nóng)林科技大學(xué)理學(xué)院,陜西楊凌　712100)

?

添加Universum數(shù)據(jù)的最小二乘投影雙支持向量機

魯淑霞1,佟樂1,朱晨旭2

(1.河北大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院,河北保定071002；2.西北農(nóng)林科技大學(xué)理學(xué)院,陜西楊凌712100)

摘要：通過添加Universum數(shù)據(jù),引入了與分類樣本無關(guān)的樣本,并借此引入了先驗域信息,構(gòu)建了添加Universum數(shù)據(jù)的最小二乘投影雙支持向量機(ULSPTSVM).此外,還將方法擴展到遞歸學(xué)習(xí)方法,用于進一步提高ULSPTSVM的分類性能.實驗表明,ULSPTSVM方法可以直接減少帶有Universum數(shù)據(jù)的雙支持向量機(USVM)方法的訓(xùn)練時間,而且在多數(shù)情況下ULSPTSVM方法的測試精度優(yōu)于最小二乘投影雙支持向量機(LSPTSVM)方法的測試精度.

關(guān)鍵詞：Universum數(shù)據(jù);支持向量機;雙支持向量機;投影

Universum數(shù)據(jù)表示不屬于分類問題中任何一類的數(shù)據(jù)集合,與有標(biāo)記樣本來自不同的分布,Universum數(shù)據(jù)與需要分類的樣本分布在同一個區(qū)域內(nèi),因此樣本中也帶有了樣本分布的先驗域信息.添加Universum數(shù)據(jù)的算法就是在已有的算法中加入新的數(shù)據(jù),從而引入先驗信息來輔助形成分類決策面,提高分類性能.

Weston等[1]學(xué)者提出了添加Universum數(shù)據(jù)的SVM方法(USVM),不同的Universum數(shù)據(jù)對于分類精度有著很大的影響,適當(dāng)添加Universum數(shù)據(jù)能提高分類性能；Cherkassky等[2]學(xué)者利用標(biāo)準(zhǔn)的SVM作為參照,驗證了USVM方法在處理高維稀疏數(shù)據(jù)時具有很好的分類效果,并總結(jié)出USVM方法發(fā)揮作用的條件,即樣本的分布要廣泛且在分類邊界的附近；Sinz等[3]學(xué)者分析了USVM方法,并提出了最小二乘USVM算法；還有學(xué)者在選取有價值的Universum數(shù)據(jù)等方面進行了研究[4-5].

Jayadeva等[6]學(xué)者提出了雙支持向量機(TSVM),其通過求解2個較小的二次規(guī)劃問題獲得2個非平行的超平面；最近,很多學(xué)者提出了各種改進的TSVM方法[7-9]；為了快速求解TSVM,文獻[10-11]提出了最小二乘投影雙支持向量機.為了更好地利用嵌入在Universum數(shù)據(jù)中的先驗信息,本文提出了一種添加Universum數(shù)據(jù)的最小二乘投影雙支持向量機方法(ULSPTSVM),用以提高分類性能.

1添加Universum數(shù)據(jù)的最小二乘投影雙支持向量機

有關(guān)最小二乘投影雙支持向量機(LSPTSVM)方法的介紹可以參考文獻[10].為了更好地利用嵌入在Universum數(shù)據(jù)中的先驗信息,提出了一種添加Universum數(shù)據(jù)的最小二乘投影雙支持向量機(ULSPTSVM)方法.ULSPTSVM的決策函數(shù)可以直接從原問題中獲得,且優(yōu)化問題僅有等式約束,可以利用嵌入在Universum數(shù)據(jù)中的先驗信息來構(gòu)造最終的分類器,改善ULSPTSVM的分類性能.

1.1ULSPTSVM算法

ULSPTSVM的優(yōu)化問題如下:

(1)

(2)

設(shè)φ=(φ1,…,φl)T,φ=(φ1,…,φl)T,參數(shù)c1>0,c2>0,c3>,c4>0,cu>0.ξk、ηk、φp、φp均為非負松弛變量.優(yōu)化問題(1)中目標(biāo)函數(shù)的第1項是使類1中投影數(shù)據(jù)點的類內(nèi)方差盡可能小,第2項是第2類數(shù)據(jù)的損失函數(shù),第3項是正則化項,使得分類間隔盡可能大,第4項是添加的Universum數(shù)據(jù)的損失函數(shù),優(yōu)化問題(1)中的第1個約束條件是使得第2類的數(shù)據(jù)到第1類數(shù)據(jù)均值的投影距離近似為1,第2個約束條件是使得Universum數(shù)據(jù)位于分類邊界面附近.優(yōu)化問題(2)有類似的解釋.

為了簡化上述方程,給出如下定義

利用上述定義,優(yōu)化問題(1)和(2)可化簡為

(3)

(4)

將優(yōu)化問題(3)、(4)中的等式約束帶入到目標(biāo)函數(shù)中,(3)、(4)變?yōu)?/p>

(5)

(6)

上述2式(5)、(6)關(guān)于w1,w2求梯度,并令梯度為0,則

(7)

(8)

據(jù)(7)、(8)式分別解出投影軸得

(9)

通過方程(9)求解完最優(yōu)投影軸后,ULSPTSVM的訓(xùn)練過程就結(jié)束了.在測試過程中,新樣本的類標(biāo)由其到投影類均值的投影距離來確定,即由下式表示

(10)

1.2遞歸ULSPTSVM

ULSPTSVM方法的目標(biāo)是找投影方向,為了進一步增強ULSPTSVM的分類性能,將方法擴展到獲得多個正交方向的情況,得到遞歸ULSPTSVM算法.遞歸ULSPTSVM算法由以下2步組成：

i)根據(jù)方程(9)確定2類的最優(yōu)投影軸w1和w2.

ii)產(chǎn)生新的數(shù)據(jù)點,將原始數(shù)據(jù)點分別投影到正交于w1和w2的2個子空間中.

算法：遞歸ULSPTSVM.

1)初始化迭代次數(shù)t=0,訓(xùn)練集S1(t)=S2(t)={xi|i=1,2,…,m}.

2)在數(shù)據(jù)集S1(t)和S2(t)上求解原始問題(3)和(4),確定最佳投影方向w1(t)和w2(t).

4)將樣本點投影到正交于w1和w2的2個子空間中,得到2個新的數(shù)據(jù)集,即

5)如果滿足預(yù)定準(zhǔn)則就終止程序.

6)令t=t+1,轉(zhuǎn)到步驟2).

分別用W1={w1(t),t=0,1,2,…}和W2={w2(t),t=0,1,2,…}表示類1和類2的解集.在具有多個正交投影方向的情況下,決策準(zhǔn)則(10)擴展為

(11)

2實驗分析

為了驗證所提ULSPTSVM算法的性能,在9個UCI基準(zhǔn)數(shù)據(jù)集和David Musicant的NDC數(shù)據(jù)集上進行了實驗,并將ULSPTSVM算法與TSVM,USVM,LSPTSVM算法進行了比較研究.所有的實驗均使用2010版本的MATLAB軟件,上機環(huán)境為英特爾(R)酷睿2雙核處理器(2.79 GHz)和4 GB的RAM.使用交叉驗證方法選擇參數(shù)，參數(shù)從{2-8,…,28}中選擇,在實驗中設(shè)定c1=c2=c3=c4=cu.

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

對于每一個UCI數(shù)據(jù)集,隨機從不同類數(shù)據(jù)中選擇數(shù)量相同的數(shù)據(jù),組成一個數(shù)據(jù)集.選擇每個數(shù)據(jù)集的30%用于訓(xùn)練,每個數(shù)據(jù)集的35%用來生成Universum數(shù)據(jù),每個數(shù)據(jù)集的其余35%部分用于測試.生成Universum數(shù)據(jù)的方法是,從2個不同類別的數(shù)據(jù)集中選出數(shù)據(jù),然后用平均系數(shù)法生成Universum數(shù)據(jù)，每種實驗重復(fù)10次,實驗的平均結(jié)果見表1、表2.

從表1、表2中看到,添加Universum數(shù)據(jù)的ULSPTSVM和USVM的分類精度在大多數(shù)情況下要優(yōu)于LSPTSVM和TSVM的分類精度.ULSPTSVM和LSPTSVM通過求解線性方程組獲得優(yōu)化問題的解,而USVM和TSVM需要求解二次規(guī)劃問題,在訓(xùn)練時間上,ULSPTSVM、LSPTSVM與USVM、TSVM相比需要較少的訓(xùn)練時間.

表1　ULSPTSVM和LSPTSVM方法在UCI數(shù)據(jù)集上的測試精度和訓(xùn)練時間比較

表2　USVM和TSVM方法在UCI數(shù)據(jù)集上的測試精度和訓(xùn)練時間比較

2.2NDC數(shù)據(jù)集

使用David Musicants的NDC數(shù)據(jù)生成器生成數(shù)據(jù)集,表3給出了NDC數(shù)據(jù)集的具體描述.NDC數(shù)據(jù)集被分成訓(xùn)練集和測試集,添加的Universum數(shù)據(jù)數(shù)目為訓(xùn)練數(shù)據(jù)的1/2,通過高斯分布隨機生成(與訓(xùn)練數(shù)據(jù)具有不同的分布).在實驗中,參數(shù)均設(shè)為1(c1=c2=c3=c4=cu=1).

表4給出了LSPTSVM和ULSPTSVM這2種算法在NDC數(shù)據(jù)集上的測試精度和訓(xùn)練時間的比較.可以看出添加Universum數(shù)據(jù)的ULSPTSVM算法的精度在大多數(shù)情況下要優(yōu)于LSPTSVM算法的精度.

表3　NDC數(shù)據(jù)集

表4　2種方法在NDC數(shù)據(jù)集上的測試精度和訓(xùn)練時間比較

3結(jié)束語

提出了一種添加Universum數(shù)據(jù)的最小二乘投影雙支持向量機(ULSPTSVM)方法,它可以利用嵌入在Universum數(shù)據(jù)中的一些先驗信息,來提高分類性能.方法USVM和TSVM需要求解2個二次規(guī)劃問題,而所提出的ULSPTSVM方法,通過求解線性方程組就可以找到投影方向,是一種非?？焖俚乃惴?這使得ULSPTSVM和LSPTSVM可以解決較大型數(shù)據(jù)集的分類問題.UCI數(shù)據(jù)集和NDC數(shù)據(jù)集的實驗結(jié)果表明,ULSPTSVM方法的分類精度在大多數(shù)情況下要優(yōu)于LSPTSVM.然而,如何添加Universum數(shù)據(jù)問題需要進一步的研究.

參考文獻：

[1]WESTON J,COLLOBERT R,SINZ F,et al.Inference with the Universum[Z].The 23rd International Conference on Machine Learning,Pittsburgh,2006.

[2]CHERKASSKY V,DHAR S,DAI W.Practical conditions for effectiveness of the universum learning[J].IEEE Transactions on Neural Networks,2011,22(8):1241-1255.DOI:10.1109/TNN.2011.2157522.

[3]SINZ F H,CHAPELLE O,AGARWAL A,et al.An analysis of inference with the universum[Z].The 21st Annual Lonference Neural Information Processing Systems,Vancouver,2008.

[4]CHEN S,ZHANG C.Selecting informative universum sample for semisupervised learning[Z].The International Joint Conference on Artificial Intelligent,Pasadna,2009.

[5]SHEN C,WANG P,SHEN F,et al.Uboost:Boosting with the universum[J].IEEE Transaction on Pattern Analysis and Machine Intelligence,2012,34(4):825-832.DOI:10.1109/TPAMI.2011.240.

[6]JAYADEVA R,KHEMCHANDANI S,CHANDRA.Twin support vector machines for pattern classification[J].IEEE Transactions on Pattern Analysis and Machine Intellegence,2007,29(5):905-910.DOI:10.1109/TPAMI.2007.1068.

[7]KUMAR M A,GOPAL M.Application of smoothing technique on twin support vector machines[J].Pattern Recognition Letters,2008,29(13):1842-1848.DOI:10.1016/j.patrec.2008.05.016.

[8]SHAO Y H,ZHANG C H,WANG X B,et al.Improvements on twin support vector machines[J].IEEE Transactions on Neural Networks,2011,22(6):962-968.DOI:10.1109/TNN.2011.2130540.

[9]QI Z Q,TIAN Y J,SHI Y.Twin support vector machine with Universum data[J].Neural Networks,2012,36:112-119.DOI:10.1016/j.neunet.2012.09.004.

[10]SHAO Y H,DENG N Y,YANG Z M.Least square recursive projection twin support vector machine for classification[J].Pattern Recognition,2012,45:229-2307.DOI:10.1016/j.patcog.2011.11.028.

[11]DING S F,HUA X P.Recursive least square projection twin support vector machine for nonlinear classification[J].Neurocomputing,2014,134:3-9.DOI:10.1016/j.neucom.2013.02.046.

[12]MUSICANT D R.NDC:Normally Distributed Clustered Datasets[EB/OL].(1998-01-01)[2015-06-05].1998 .

(責(zé)任編輯：孟素蘭)

Least squares projection twin support vector machine with universum

LU Shuxia1,TONG Le1,ZHU Chenxu2

(1.College of Mathematics and Information Science,Hebei University,Baoding 071002,China;2.College of Science,Northwest Agriculture & Forestry University,Yangling 712100,China )

Abstract:A new algorithm is constructed,called least squares projection twin support vector machine with Universum(ULSPTSVM).By adding Universum data,samples are introduced which have no relation with the samples of classification,which have a priori domain information.In addition,in order to further enhance the performance of ULSPTSVM,the method is extended to recursive learning method.Experiments show that ULSPTSVM can directly improve the training time of twin support vector machine with Universum(UTSVM),and in most cases the experimental accuracy is better than least squares projection twin support vector machine(LSPTSVM).

Key words:Universum data;support vector machine;twin support vector machine;projection

DOI：10.3969/j.issn.1000-1565.2016.01.015

收稿日期：2015-07-01

基金項目：國家自然科學(xué)基金資助項目(61170040)；河北省自然科學(xué)基金資助項目(F2015201185；F2013201220)

中圖分類號：TP391.4

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

文章編號：1000-1565(2016)01-0094-06

第一作者：魯淑霞(1966—),女,河北保定人,河北大學(xué)教授,博士,主要從事機器學(xué)習(xí)研究.E-mail：cmclusx@126.com