添加Universum數據的最小二乘投影雙支持向量機

魯淑霞,佟樂,朱晨旭

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

?

添加Universum數據的最小二乘投影雙支持向量機

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

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

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

關鍵詞：Universum數據;支持向量機;雙支持向量機;投影

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

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

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

1添加Universum數據的最小二乘投影雙支持向量機

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

1.1ULSPTSVM算法

ULSPTSVM的優化問題如下:

(1)

(2)

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

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

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

(3)

(4)

將優化問題(3)、(4)中的等式約束帶入到目標函數中,(3)、(4)變為

(5)

(6)

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

(7)

(8)

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

(9)

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

(10)

1.2遞歸ULSPTSVM

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

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

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

算法：遞歸ULSPTSVM.

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

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

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

5)如果滿足預定準則就終止程序.

6)令t=t+1,轉到步驟2).

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

(11)

2實驗分析

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

2.1UCI數據集

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

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

表1　ULSPTSVM和LSPTSVM方法在UCI數據集上的測試精度和訓練時間比較

表2　USVM和TSVM方法在UCI數據集上的測試精度和訓練時間比較

2.2NDC數據集

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

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

表3　NDC數據集

表4　2種方法在NDC數據集上的測試精度和訓練時間比較

3結束語

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

參考文獻：

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

(責任編輯：孟素蘭)

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

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

中圖分類號：TP391.4

文獻標志碼：A

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

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