一种改进的投影孪生支持向量机

花小朋，孙一颗，丁世飞

(1.盐城工学院 信息工程学院，江苏 盐城 224051； 2. 中国矿业大学 计算机学院，江苏 徐州 221116)



一种改进的投影孪生支持向量机

花小朋1，孙一颗1，丁世飞2

(1.盐城工学院 信息工程学院，江苏 盐城 224051； 2. 中国矿业大学 计算机学院，江苏 徐州 221116)

摘要：针对投影孪生支持向量机(PTSVM)在训练阶段欠考虑样本空间局部结构和局部信息的缺陷，提出一种具有一定局部学习能力的有监督分类方法：加权投影孪生支持向量机(weighted PTSVM，WPTSVM)。相比于PTSVM，WPTSVM优势在于：通过构造类内近邻图为每个样本获取特定的权值，并且以加权均值取代标准均值，在一定程度上提高了算法的局部学习能力；选取异类样本集中少量边界点构造优化问题的约束条件，很大程度上降低了二次规划求解的时间复杂度；继承了PTSVM的优点，可以看成PTSVM的推广算法。理论分析及其在人造数据集和真实数据集上的测试结果表明该方法具有上述优势。

关键词：分类；投影孪生支持向量机；局部信息；加权均值；近邻图；二次规划；约束条件；时间复杂度

在分类问题中，经典支持向量机(SVM)依据间隔最大化准则生成分类决策面，存在训练时间复杂度偏高和欠考虑样本分布情况的缺陷[1-2]。近年来，作为经典SVM的改进方法，非平行超平面分类器(nonparellel hyperplane classifiers，NHCs)[3]已经成为模式识别领域新的研究热点之一。孪生支持向量机(twin support vector machine，TWSVM)[4]是NHCs方法中主要代表性算法之一，其主要思想源于泛化特征值中心支持向量机(generalized eigenvalue proximal SVM，GEPSVM)[5]。TWSVM将GEPSVM中两个优化子问题转换成两个形如SVM的小规模二次规划问题，从而使其训练时间复杂度缩减为经典SVM的1/4。除了训练速度上的优势，TWSVM还继承了GEPSVM能够在线性模式很好地处理异或(XOR)样本分类问题的优势。然而，当两类样本具有不同散度分布时，TWSVM的泛化性能欠佳[6]。文献[7]提出一种新的非平行超平面分类器：投影孪生支持向量机 (projection twin support vector machine，PTSVM)。与TWSVM不同的是，PTSVM优化目的是为每类样本寻找最佳投影轴，而且通过递归迭代算法，PTSVM能够生成多个正交投影轴。实验结果表明，PTSVM对复杂的XOR问题具有更好的分类能力。为解决非线性分类问题。文献[8]进一步提出PTSVM的非线性方法。

然而分析发现，PTSVM在训练过程中仅仅考虑样本空间的全局结构和全局信息，忽视了样本空间的局部结构和局部信息。许多研究结果表明同类数据集中大部分样本在局部上是关联的(即数据集中存在潜藏的局部几何结构)，而这种内在的局部信息对数据分类又是至关重要的[9]。这种潜在的局部信息可以通过数据集中样本间的k近邻关系进行挖掘[9-11]。

基于上述分析，本文基于PTSVM提出一种新的具有一定局部学习能力的非平行超平面分类器算法：加权投影孪生支持向量机(weighted PTSVM，WPTSVM)。相比于PTSVM，WPTSVM优势体现在以下4个方面：1)通过构造类内近邻图为每个样本获取特定的权值，并且以加权均值取代标准均值，在一定程度上提高了算法的局部学习能力；2)选取异类样本集中少量边界点构造优化问题的约束条件，很大程度上降低了二次规划求解的时间复杂度；3)WPTSVM继承了PTSVM的优点，可以看成PTSVM的推广算法。4)WPTSVM具有更好分类性能。

1投影孪生支持向量机(PTSVM)

第1类超平面的优化准则

(2)

式中C1是惩罚参数，l为损失变量。

2加权投影孪生支持向量机(WPTSVM)

2.1算法构造

为刻画同类样本集内在的紧凑型和异类样本集间的分散性，依据图论[10,12]为每类决策面构建类内近邻图Gs和类间近邻图Gd。

(3)

式中：t为热核参数，Ne(x)表示x的k近邻样本集。

(4)

(5)

定义 3WPTSVM算法中，第1类训练样本集相应决策超平面的优化准则WPTSVM-1：

(6)

第2类超平面优化准则WPTSVM-2：

(7)

(8)

类似于传统SVM求解方法，通过引入拉格朗日函数生成式(8)的对偶问题

(9)

式中α=[α1,α2,…,αm2]T。

由此对偶问题的求解可得原问题式(6)中投影轴w1。类似的方法，可求原问题式(7)中投影轴w2。

对于未知样本x，WPTSVM的决策函数为

(10)

2.2算法分析

这里以WPTSVM的第1类样本优化问题WPTSVM-1为例进行算法分析，第2类样本优化问题WPTSVM-2有类似的算法分析。

定理1式(9)为凸二次规划。

证明式(9)核矩阵：

定理 2假定α是对偶问题式(9)的解，则w1是原优化问题式(6)的全局最优解。

证明由定理1的证明可得，式(9)为凸二次规划问题，又依据文献[14]中引理3的满足条件可知，该二次规划的解为全局最优解。证毕。

2.3算法比较

2.3.1泛化性能

定理 3PTSVM是WPTSVM的特例。

证明考虑WPTSVM的第1类样本的优化准则(7)。令D(1)=I∈Rm1×m1，F(2)=I∈Rm2×m2，则式(7)转化为PTSVM的第1类样本的优化准则(2)。对于WPTSVM的第2类样本的优化准则(8)有类似的特性。因此，PTSVM是WPTSVM的特例，而WPTSVM是PTSVM的推广算法。证毕。

定理3说明了本文提出的WPTSVM算法继承了PTSVM的优点。进一步比较式(7)和(2)可知， PTSVM仅仅考虑类内样本的全局信息，而WPTSVM用加权均值代替PTSVM中标准均值，可以在一定程度上提高算法的局部学习能力，因为基于近邻图的加权均值比起标准均值更能体现样本空间的局部结构[13]。除此之外，WPTSVM还在优化目标函数中引入了样本权值，权值越大，说明该样本越重要，对保持训练样本集潜在局部信息的贡献程度越大。图1给出了WPTSVM与PTSVM在人造数据集上的分类决策面。不难看出，WPTSVM的决策面能够在一定程度上体现样本集内在局部流形结构，而PTSVM相对较弱。

图1　两种算法人造数据集上的比较Fig.1　Comparision of two algorithms on artificial dataset

2.3.2训练时间复杂度

2.3.3构造非线性分类算法

针对线性不可分情况，本文进一步提出基于核空间的非线性WPTSVM算法——NWPTSVM。

定义4NWPTSVM的第1类超平面的优化准则为

(11)

第2类超平面的优化准则为

(12)

通过引入拉格朗日函数，可按照类似上述WPTSVM算法的推导过程分别得出式(11)和(12)的对偶形式，然后通过二次规划求解可求得投影矢量u1和u2。NWPTSVM的决策函数为

(13)

3实验分析

实验选用人造数据集和真实数据集，进一步验证本文WPTSVM方法的有效性。实验环境：2.3 GHz CPU，2 GB内存，实验软件MATLAB 7.1。

3.1复杂交叉数据集

相对于经典SVM，线性模式下对XOR问题的测试能力是非平行超平面分离器优势之一[3-5]。因此，本节首先验证MPTSVM测试交叉数据集的能力。图2给出一种较复杂的人造交叉数据集：Comxor[7]。表1给出了TWSVM、PTSVM和WPTSVM三种算法在该测试数据集上10折交叉验证结果。参数C1与C2的搜索范围为{2i|i=-8，-6，…，+8}；WPTSVM中类内近邻参数k1的搜索范围为{1,2，…,9}，类间近邻参数k2=5，热核参数t的搜索范围为{2i|i=-1，0，…，8}。从表1实验结果来看，PTSVM分类性能优于TWSVM，而本文WPTSVM则具有更佳的分类性能。

图2　复杂交叉数据集Fig.2　Compxor dataset

Table 1Classification comparision of three algorithms on comxor dataset

DatasetTWSVMPTSVMWPTSVMComxor93.76±6.7095.67±4.7397.36±2.90

3.2流形数据集

数据集two-moons (如图3所示) 的结构具有明显局部流形，所以该数据集多用于测试算法的局部学习能力[2,13]。这里通过测试two-moons数据集，并与TWSVM和PTSVM方法进行比较，验证本文WPTSVM方法局部学习能力。

图3　Two-moons数据集Fig.3　Two-moons dataset

实验选择正负类样本各为50的two-moons数据集。随机抽取40%训练集和60%测试集进行实验，重复此过程10次并记录实验结果的平均值

(见表2)。显然，WPTSVM方法具有更好的测试效果，这说明本文加权措施的确能够在一定程度上提高PTSVM算法的局部学习能力。

表23种算法在双月形数据集上的分类精度(%)比较

Table 2Classification comparision of three algorithms on two-moons dataset

DatasetTWSVMPTSVMWPTSVMtwo-moons77.17±13.7276.33±12.3678.83±8.86

3.3UCI数据集

UCI数据集经常被用来验证算法的分类精度[3-7,15-16]。该数据集包含若干数据子集，涉及诸多应用领域。

实验中选取部分数据子集，利用10-折交叉验证法测试算法分类性能。非线性算法实验中，选择高斯核exp(-‖xi-xj‖2/σ)作为核函数，参数σ的搜索范围为{2i|i=-1,0, …,7}，其他参数搜索范围同3.1节。线性模式及非线性模式下实验结果如表3和表4分别所示。

从训练时间上看: TWSVM与PTSVM相当，WPTSVM明显比这两种算法快。原因是WPTSVM选用少量边界样本进行二次规划求解，而其他两种算法则选择异类中全部样本。

从分类性能上看：本文提出的WPTSVM 算法具有更好的分类能力，这也进一步佐证了本文提高PTSVM算法局部学习能力的措施确实有效。

表3　线性模式下3种算法的实验比较

表4　非线性模式下3种算法的实验比较

4结束语

本文基于投影孪生支持向量机(PTSVM )提出一种新的的非平行超平面分类器方法：加权投影孪生支持向量机(WPTSVM )。WPTSVM不仅继承了PTSVM方法的优点，而且在一定程度上提高了算法局部学习能力。除此之外，WPTSVM通过类间近邻图选择少量边界样本构造优化问题约束条件，相当程度上降低了二次规划求解时间复杂度。理论分析及实验结果均验证了本文所提算法的有效性。诚然，WPTSVM在构造类内及类间近邻图时，需要花费额外的计算开销，特别是在学习样本数目较大时，算法计算复杂度会偏高，这也是今后进一步研究的目标。

参考文献:

[1]皋军, 王士同, 邓赵红. 基于全局和局部保持的半监督支持向量机[J]. 电子学报, 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.

[2]花小朋, 丁世飞. 局部保持对支持向量机[J]. 计算机研究与发展, 2014, 51(3): 590-597.

HUAxiaopeng, DING Shifei. Locality preserving twin support vector machines [J]. Journal of computer research and development, 2014, 51(3): 590-597.

[3] DING Shifei, HUA Xiaopeng, YU Junzhao. An overview on nonparallel hyperplane support vector machines[J]. Neural computing and applications, 2014, 25(5): 975-982.

[4]JAYADEVA, KHEMCHAND R, CHANDRA S. Twin support vector machines for pattern classification [J]. IEEE transaction on pattern analysis and machine intelligence, 2007, 29 (5): 905-910.

[5]MANGASARIAN O L, WILD E W. MultisurFace proximal support vector machine classification via generalized eigenvalues [J]. IEEE transactions on pattern analysis and machine intelligence, 2006, 28 (1): 69-74.

[6] PENG Xinjun,XU Dong. Bi-density twin support vector machines for pattern recognition[J]. Neurocomputing, 2013, 99: 134-143.

[7] CHEN Xiaobo, YANG Jian, YE Qiaolin, et al. Recursive projection twin support vector machine via within-class variance minimization[J]. Pattern recognition, 2011, 44 (10/11): 2643-2655.

[8]SHAO Yuanhai, WANG Zhen, CHEN Weijie, et al. A regularization for the projection twin support vector machine[J]. Knowledge-based systems, 2013, 37 (1): 203-210.

[9]YANG Xubing, CHEN Songcan, CHEN Bin, et al. Proximal support vector machine using local information [J]. Neurocomputing, 2009, 73(1): 357-365.

[10]COVER T M, HART P E. Nearest neighbor pattern classification[J]. IEEE transactions on information theory, 1967, 13 (1): 21-27.

[11]WANG Xiaoming, CHUNG Fulai, WANG Shitong. On minimum class locality preserving variance support vector machine[J]. Patter recognition, 2010, 43(8): 2753-2762.

[12]YE Qiaolin, ZhAO Chunxia, YE Ning, et al. Localized twin svm via convex minimization[J]. Neurocomputing, 2011, 74(4): 580-587.

[13]皋军, 黄丽莉, 王士同. 基于局部子域的最大间距判别分析 [J ]. 控制与决策, 2014, 29 (5): 827-832.

GAO Jun, HUANG Lili, WANG Shitong. Local sub-domains based maximum margin criterion [J]. Control and decision, 2014, 29 (5): 827-832.

[14]邓乃杨, 田英杰. 支持向量机—理论、算法与拓展[M]. 北京: 科学出版社, 2009: 164-223.

[15]丁立中, 廖士中. KMA-a: 一个支持向量机核矩阵的近似计算算法[J]. 计算机研究与发展, 2012, 49(4): 746-753.

DING Lizhong, LIAO Shizhong. KMA-a: a kernel matrix approximation algorithm for support vector machines [J]. Journal of computer research and development, 2012, 49(4): 746-753.

[16]XUE Hui, CHEN Songchan. Glocalization pursuit support vector machine [J].Neural computing and applications, 2011, 20(7):1043-1053.

花小朋，男，1975年生，副教授，博士，主要研究方向为机器学习与数据挖掘，发表学术论文10余篇。

孙一颗，男，1993年生，硕士研究生，主要研究方向为机器学习、数据挖掘，申请发明专利2项。

丁世飞，男，1963年生，教授，博士生导师，中国计算机学会高级会员，中国人工智能学会高级会员，江苏省计算机学会人工智能专业委员会委员，主要研究方向为智能信息处理，目前主持国家973项目1项、国家自然科学基金项目1项，发表学术论文60余篇。

中文引用格式：花小朋，孙一颗，丁世飞.一种改进的投影孪生支持向量机[J]. 智能系统学报， 2016, 11(3): 384-391.

英文引用格式：HUA Xiaopeng， SUN Yike， DING Shifei. An improved projection twin support vector machine[J]. CAAI transactions on intelligent systems, 2016, 11(3): 384-391.

An improved projection twin support vector machine

HUA Xiaopeng1， SUN Yike1， DING Shifei2

(1. School of Information Engineering, Yancheng Institute of Technology, Yancheng 224051, China; 2. School of Computer Science and Technology, China University of Mining and Technology, Xuzhou 221116, China)

Abstract：A supervised classification method having a local learning ability, called weighted projection twin support vector machine (WPTSVM), is proposed. This method aims to improve upon a defect that projection twin support vector machines (PTSVMs) have, namely, that PTSVMs do not take account of the local structure and local information of a sample space in the training process. Compared with PTSVM, WPTSVM improves its local learning ability to some extent by attaching different weights for each sample according to the within-class neighborhood graph and replacing the standard mean with a weighted mean. Moreover, to reduce computational complexity, WPTSVM chooses a small number of boundary points in the contrary-class based on the between-class neighborhood graph to construct constraints of the original optimization problems. The method inherits the merits of PTSVM and can be regarded as an improved version of PTSVM. Experimental results on artificial and real datasets indicate the effectiveness of the WPTSVM method.

Keywords：classification; projection twin support vector machine; local information; weighted mean; neighborhood graph; quadratic programming; constraint condition; time complexity

作者简介：

中图分类号：TP391.4

文献标志码：A

文章编号：1673-4785(2016)03-0384-06

通信作者：花小朋. E-mail：xp_hua@163.com.

基金项目：国家重点基础研究计划项目(2013CB329502);国家自然科学基金项目(61379101); 江苏省自然科学基金项目(BK20151299).

收稿日期：2016-03-20.网络出版日期：2016-05-13.

DOI:10.11992/tis.2016030.

网络出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20160513.0924.024.html