魯淑霞,佟樂(lè),朱晨旭

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

?

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

魯淑霞1,佟樂(lè)1,朱晨旭2

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

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

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

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

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

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

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

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

1.1ULSPTSVM算法

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

(1)

(2)

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

為了簡(jiǎn)化上述方程,給出如下定義

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

(3)

(4)

將優(yōu)化問(wèn)題(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)

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

(10)

1.2遞歸ULSPTSVM

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

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

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

算法：遞歸ULSPTSVM.

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

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

4)將樣本點(diǎn)投影到正交于w1和w2的2個(gè)子空間中,得到2個(gè)新的數(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的解集.在具有多個(gè)正交投影方向的情況下,決策準(zhǔn)則(10)擴(kuò)展為

(11)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

參考文獻(xiàn)：

[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

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

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

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

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

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