添加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