文章快速检索  
  高级检索
一种改进的投影孪生支持向量机
花小朋1,孙一颗1,丁世飞2
1. 盐城工学院 信息工程学院, 江苏 盐城 224051;
2. 中国矿业大学 计算机学院, 江苏 徐州 221116
基金项目: 国家重点基础研究计划项目(2013CB329502);国家自然科学基金项目(61379101);江苏省自然科学基金项目(BK20151299).    
摘要: 针对投影孪生支持向量机(PTSVM)在训练阶段欠考虑样本空间局部结构和局部信息的缺陷,提出一种具有一定局部学习能力的有监督分类方法:加权投影孪生支持向量机(weighted PTSVM,WPTSVM)。相比于PTSVM,WPTSVM优势在于:通过构造类内近邻图为每个样本获取特定的权值,并且以加权均值取代标准均值,在一定程度上提高了算法的局部学习能力;选取异类样本集中少量边界点构造优化问题的约束条件,很大程度上降低了二次规划求解的时间复杂度;继承了PTSVM的优点,可以看成PTSVM的推广算法。理论分析及其在人造数据集和真实数据集上的测试结果表明该方法具有上述优势。
关键词: 分类     投影孪生支持向量机     局部信息     加权均值     近邻图     二次规划     约束条件     时间复杂度    
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.
Key words: classification     projection twin support vector machine     local information     weighted mean     neighborhood graph     quadratic programming     constraint condition     time complexity    

在分类问题中,经典支持向量机(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,10,11]

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

假定两类学习样本集分别表示为实数矩阵A∈Rm1×n和B∈Rm2×n。n为样本维度,m1m2分别为第1类(+1类)和第2类(-1类)样本数目,并且令m=m1+m2。 PTSVM算法的优化目标可以看作是在实数空间中寻找两个最佳投影轴为w1w2的决策超平面:

xTw 1+b1=0,xT w2+b2=0. (1)

需要注意的是,这里的偏置 b1=-e1TAw1/m1b2=-e2T Bw2/m2e1e2是两个实体为1的列向量,A=[x1(1)> x2(1) … xm1(1)]T ,xBx=[x1(2) x(2)2 …,xm2(2)]T,xj(i)表示第i类的第j个样本。

第1类超平面的优化准则PTSVM-1:

\[\begin{align} & \min \frac{1}{2}{{\sum\limits_{i=1}^{{{m}_{1}}}{\left( w_{1}^{T}x_{i}^{\left( 1 \right)}-w_{1}^{T}\frac{1}{{{m}_{1}}}\sum\limits_{j=1}^{{{m}_{1}}}{x_{j}^{\left( x \right)}} \right)}}^{2}}+{{c}_{1}}\sum\limits_{i=1}^{{{m}_{2}}}{{{\zeta }_{i}}} \\ & s.t-\left( w_{1}^{T}x_{1}^{\left( 2 \right)}-w_{1}^{T}\frac{1}{m}\sum\limits_{j=1}^{{{m}_{1}}}{x_{i}^{\left( 1 \right)}} \right)+{{\zeta }_{t}}\ge 1,{{\zeta }_{1}}\ge 0, \\ \end{align}\] (2)
式中C1是惩罚参数,${{\zeta }_{t}}$为损失变量。

显然,PTSVM在优化目标函数中考虑的训练样本集内在的散度${{\sum\limits_{i=1}^{{{m}_{1}}}{\left( w_{1}^{T}x_{i}^{\left( 1 \right)}-w_{1}^{T}\frac{1}{{{m}_{1}}}\sum\limits_{j=1}^{{{m}_{1}}}{x_{j}^{\left( x \right)}} \right)}}^{2}}$,体现的是样本集内在的全局分布。故该方法忽视了潜藏在训练样本集内部的局部几何结构。

2 加权投影孪生支持向量机(WPTSVM) 2.1 算法构造

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

定义1 给定第c类中的任意两个样本 xi(c)和xj(c), (c=1,2;i,j=1,2, …,mc), 则类内近邻图Gs的相似矩阵W s(Wijs)m1×m1可定义为

\[W_{ij}^{s}=\left\{ \begin{align} & \exp \left( -{{\left\| x_{i}^{\left( c \right)}-x_{j}^{\left( c \right)} \right\|}^{2}}/t \right),x_{j}^{\left( c \right)}\in Ne\left( x_{i}^{\left( c \right)} \right)x_{j}^{\left( c \right)}\in Ne\left( x_{i}^{\left( c \right)} \right), \\ & 0, \\ \end{align} \right.\] (3)
式中:t为热核参数,Ne(x)表示x的k近邻样本集。

定义 2[12] 考虑第c类样本xi(c),给定相反类中任意样本xl(c)(l=1, 2, …,mc),则类间近邻图Gd的相似矩阵W dW (ild)m1×m2可定义为

\[W_{ij}^{s}=\left\{ \begin{align} & 1x_{1}^{\left( \tau \right)}isk\text{nearest neighbors of}x_{i}^{\left( e \right)} \\ & 0, \\ \end{align} \right.\] (4)

依据定义2,第c类中每一个样本定义权重:

\[f_{t}^{\left( \pi \right)}=\left\{ \begin{align} & 1,\exists i,W_{it}^{d}\ne 0 \\ & 0, \\ \end{align} \right.\] (5)
显然,权重fl(c)=1样本是第c类样本集的边界样本。

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

\[\begin{align} & \min \frac{1}{2}\sum\limits_{i=1}^{{{m}_{1}}}{\rho _{i}^{\left( 1 \right)}}{{\left( w_{1}^{T}x_{i}^{\left( 1 \right)}-w_{1}^{T}\sum\limits_{j=1}^{{{m}_{1}}}{\lambda _{j}^{\left( 1 \right)}x_{j}^{\left( 1 \right)}} \right)}^{2}}+{{c}_{1}}\sum\limits_{t=1}^{{{m}_{2}}}{{{\zeta }_{t}}} \\ & s.t.-f_{t}^{\left( 2 \right)}\left( w_{1}^{T}x_{1}^{\left( 2 \right)}-w_{1}^{T}\sum\limits_{j=1}^{{{m}_{1}}}{\lambda _{j}^{\left( 1 \right)}x_{j}^{\left( 1 \right)}} \right)+{{\zeta }_{t}}\ge f_{t}^{\left( 2 \right)},{{\zeta }_{t\ge }}0 \\ \end{align}\] (6)

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

\[\begin{align} & \min \frac{1}{2}\sum\limits_{i=1}^{{{m}_{1}}}{\rho _{i}^{\left( 2 \right)}}{{\left( w_{2}^{T}x_{i}^{\left( 2 \right)}-w_{2}^{T}\sum\limits_{j=1}^{{{m}_{1}}}{\lambda _{j}^{\left( 2 \right)}x_{j}^{\left( 2 \right)}} \right)}^{2}}+{{c}_{2}}\sum\limits_{t=1}^{{{m}_{2}}}{{{\zeta }_{t}}} \\ & s.t.-f_{t}^{\left( 1 \right)}\left( w_{2}^{T}x_{1}^{\left( 1 \right)}-w_{2}^{T}\sum\limits_{j=1}^{{{m}_{1}}}{\lambda _{j}^{\left( 2 \right)}x_{j}^{\left( 2 \right)}} \right)+{{\zeta }_{t}}\ge f_{t}^{\left( 1 \right)},{{\zeta }_{t\ge }}0 \\ \end{align}\] (7)
(7) 式中:C1C2是惩罚参数,ξl和ηi为损失变量,
\[p_{i}^{\left( c \right)}=\sum\limits_{j=1}^{{{m}_{c}}}{W_{ij}^{s}},\lambda _{j}^{\left( c \right)}=p_{j}^{\left( c \right)}/\sum\limits_{i=1}^{{{m}_{c}}}{p_{i}^{\left( c \right)}},c=1.2\]

式(6)中,ρi(1)代表样本xi(1)的权重,ρi(1)值越大,表示xi(1)越重要,对保持样本空间局部信息的贡献程度越大;$\sum\limits_{j=1}^{{{m}_{1}}}{\lambda _{j}^{\left( 1 \right)}}x_{j}^{\left( 1 \right)}$为第1类样本空间的加权均值,比起式(2)中的标准均值更能体现样本空间的局部结构[13];约束条件表明 WPTSVM-1仅仅考虑第2类样本中fl(2)=1的边界样本。显然,式(6)优化目标是为第1类样本寻找最佳投影轴xw x1,使得权重较大的样本投影后尽可能聚集在加权均值中心附近,而第2类中fl(1)=1的边界样本离中心尽可能远。式(7)有类似的几何解释式。式(6)矩阵形式为

\[\begin{align} & \min \frac{1}{2}{{\left( A{{w}_{1}}-{{e}_{1}}e_{1}^{T}{{E}^{\left( 1 \right)}}A{{w}_{1}} \right)}^{T}} \\ & {{D}^{\left( 1 \right)}}\left( A{{w}_{1}}-{{e}_{1}}e_{1}^{T}{{E}^{\left( 1 \right)}}A{{w}_{1}} \right)+{{c}_{1}}e_{2}^{T}\zeta \\ & s.t.-{{F}^{\left( 1 \right)}}\left( B{{w}_{1}}-{{e}_{1}}e_{1}^{T}{{E}^{\left( 1 \right)}}A{{w}_{1}} \right)+\zeta \ge {{F}^{\left( 2 \right)}}{{e}_{2}},\zeta \ge 0 \\ \end{align}\] (8)
式中:ξ2=(ξ1,…,ξm2)T,D(1)=diag1(1),…,ρm1(1)),E (1)=diag1(1),…,λm1(1)),F(2)= diag(f(2),…,fm2(2))。

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

\[\begin{align} & \min \frac{1}{2}{{\alpha }^{T}}\left( {{F}^{\left( 2 \right)}}\left( B-{{e}_{2}}e_{1}^{T}{{E}^{\left( 1 \right)}}A \right) \right)\times \\ & {{\left( {{\left( A-{{e}_{1}}e_{1}^{T}{{E}^{\left( 1 \right)}}A \right)}^{T}}{{D}^{\left( 1 \right)}}\left( A-{{e}_{1}}e_{1}^{T}{{E}^{\left( 1 \right)}}A \right) \right)}^{-1}} \\ & {{\left( {{F}^{\left( 2 \right)}}\left( B-{{e}_{2}}e_{1}^{T}{{E}^{\left( 1 \right)}}A \right) \right)}^{T}}\alpha -e_{2}^{T}\alpha \\ & s.t.0\le \alpha \le {{c}_{1}}{{e}_{2}} \\ \end{align}\] (9)
式中α=[α12,…,αm2]T

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

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

\[{\rm{label}}\left( x \right) = \mathop {{\rm{argmin}}}\limits_{c = 1,2} {\mkern 1mu} \left\{ {{d_c}} \right\} = \left\{ \begin{array}{l} {d_1} \Rightarrow x \in 1\\ {d_2} \Rightarrow x \in 2 \end{array} \right.\] (10)
式中:${{d}_{c}}=\left| w_{c}^{T}x-w_{c}^{T}\sum\limits_{j=1}^{{{m}_{c}}}{\lambda _{j}^{\left( c \right)}x_{j}^{\left( c \right)}} \right|,\left| . \right|$表示绝对值。

2.2 算法分析

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

考虑对偶形式式(9),假设实对称矩阵 ((Ae1eT1 E(1)AT D)(1) (A-e1e1TE(1)A)可逆(若不可逆,可采用 类似文献[3]方法引入正则化项I(ε>0), ε尽可能的小)。式(14)中的核函数 K(·) 只有保证Mercer核时,才能保证其是二次凸规划,所求的解才为全局最优解。为验证这一问题,给出如下定理。

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

证明 式(9)核矩阵:

K~=[k~ij=(F(2)(B-e2eT1 E(1)A))· ((A-e1e1T E(1)A)T D(1)(A-e1e1TE(1)A))-1· (F(2)B-e2eT 1E(1)A))T
是实对称矩阵。下面证明矩阵 K~是半正定的。设任意 x∈Rm2,则有xTK~x=(xT (F(2)(B-e2eT1E(1)A)) ((A-e1eT1E(1)A)T D(1)(A-e1e1TE(1)A))-1/2)2≥0,因此K~半正定且为Mercer核函数。 根据文献[14]中引理2可知,式(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 训练时间复杂度

从二次规划求解角度分析,PTSVM在训练阶段要针对每类中全部样本进行求解,所以计算复杂度为 o(m31+m23),而WPTSVM优化准则中约束条件指明只对fl(c)=1的样本(边界样本)进行二次规划求解,计算复杂度为o(m1-SV3+m2-SV3),其中m1-SVm2-SV分别为第1类样本及第2类样本中相应边界样本点数。诚然,WPTSVM在训练阶段要事先求出每个样本的类内权重及类间权重,计算复杂度分别为o(m12+m22)和o(2m1·m2)。

2.3.3 构造非线性分类算法

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

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

\[\begin{align} & \min \frac{1}{2}{{\left( K\left( A,{{C}^{T}} \right){{u}_{1}}-{{e}_{1}}e_{1}^{\text{T}}{{E}^{\left( 1 \right)}}K\left( A,{{C}^{T}} \right){{u}_{1}} \right)}^{T}}{{D}^{\left( 1 \right)}}. \\ & \left( K\left( A,{{C}^{T}} \right){{u}_{1}}-{{e}_{1}}e_{1}^{T}{{E}^{\left( 1 \right)}}K\left( A,{{C}^{T}} \right){{u}_{1}} \right)+{{C}_{1}}e_{2}^{T}\zeta , \\ & s.t.-{{F}^{\left( 2 \right)}}\left( K\left( B,{{C}^{T}} \right){{u}_{1}}-{{e}_{2}}e_{1}^{T}{{E}^{\left( 1 \right)}}K\left( A,{{C}^{T}} \right){{u}_{1}} \right)+ \\ & \zeta \ge {{F}^{\left( 2 \right)}}{{e}_{2}},\zeta \ge 0 \\ \end{align}\] (11)

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

\[\begin{align} & \min \frac{1}{2}{{\left( K\left( B,{{C}^{T}} \right){{u}_{2}}-{{e}_{2}}e_{2}^{\text{T}}{{E}^{\left( 2 \right)}}K\left( B,{{C}^{T}} \right){{u}_{2}} \right)}^{T}}{{D}^{\left( 2 \right)}}. \\ & \left( K\left( A,{{C}^{T}} \right){{u}_{2}}-{{e}_{2}}e_{2}^{T}{{E}^{\left( 2 \right)}}K\left( A,{{C}^{T}} \right){{u}_{2}} \right)+{{C}_{2}}e_{1}^{T}\zeta , \\ & s.t.-{{F}^{\left( 1 \right)}}\left( K\left( B,{{C}^{T}} \right){{u}_{2}}-{{e}_{1}}e_{2}^{T}{{E}^{\left( 2 \right)}}K\left( A,{{C}^{T}} \right){{u}_{2}} \right)+ \\ & \zeta \ge {{F}^{\left( 1 \right)}}{{e}_{1}},\zeta \ge 0 \\ \end{align}\] (12)

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

\[{\rm{label(x) = }}\mathop {{\rm{argmin}}}\limits_{c = 1,2} {\mkern 1mu} \left\{ {{d_c}} \right\} = \left\{ \begin{array}{l} {d_1} \Rightarrow x \in 1\\ {d_2} \Rightarrow x \in 2 \end{array} \right.\] (13)
式中${{d}_{c}}=\left| k\left( {{x}^{T}},{{c}^{T}} \right){{u}_{i}}-\sum\limits_{j=1}^{{{m}_{c}}}{\lambda _{j}^{\left( c \right)}k\left( {{\left( x_{j}^{\left( c \right)} \right)}^{T}},{{c}^{T}} \right){{u}_{i}}} \right|$。

3 实验分析

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

3.1 复杂交叉数据集

相对于经典SVM,线性模式下对XOR问题的测试能力是非平行超平面分离器优势之一[3,4,5]。因此,本节首先验证MPTSVM测试交叉数据集的能力。图2给出一种较复杂的人造交叉数据集:Comxor[7]。表1给出了TWSVM、PTSVM和WPTSVM三种算法在该测试数据集上10折交叉验证结果。参数 C1C2的搜索范围为{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

表 1 3种算法在复杂交叉数据集上的分类精度(%)比较 Table 1 Classification comparision of three algorithms on comxor dataset
DatasetTWSVMPTSVMWPTSVM
Comxor93.76±6.7095.67±4.73 97.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算法的局部学习能力。

表 2 3种算法在双月形数据集上的分类精度(%)比较 Table 2 Classification comparision of three algorithms on two-moons dataset
Dataset TWSVMPTSVMWPTSVM
two-moons77.17±13.7276.33±12.3678.83±8.86
3.3 UCI数据集

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

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

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

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

表 3 线性模式下3种算法的实验比较 Table 3 Experimental comparision of three algorithms on UCI datasets with linear kernel
Dataset TWSVMPTSVMWPTSVM
正确率/%训练时间/s正确率/%训练时间/s正确率/%训练时间/s
Hepatitis(155×19) 84.17±7.79 3.84 83.67±10.80 3.46 87.33±9.17 1.36
Cleve (296×13) 82.42±4.21 5.40 82.08±3.38 5.26 83.46±3.71 2.56
Sonar (208×60) 66.00±16.85 3.93 66.36±14.27 3.82 68.07±13.60 1.58
Bupa_liver(345×6) 68.69±3.23 2.42 67.59±5.30 2.84 70.20±6.42 2.17
Wdbc (569×30) 96.99±1.63 19.77 96.99±1.63 19.95 97.53±1.65 1.14
Haberman (306×3) 74.50±2.11 4.09 74.56±7.90 5.74 75.44±5.03 1.36
Heart (270×13) 84.07±5.25 5.30 84.07±5.51 5.38 85.19±5.49 2.40
Monks2 (432×6) 67.14±4.98 2.84 67.84±3.15 2.56 67.13±3.20 0.78
Monks3 (432×6) 77.41±11.32 6.07 80.74±13.05 6.32 81.69±12.85 3.76
Australian(690×14) 86.26±4.76 13.37 86.28±4.91 11.90 86.83±5.25 2.81
Pima_india(768×8) 77.17±2.80 40.91 76.41±3.53 42.81 76.79±4.05 10.25
Tic_tac_toe(958×9) 64.93±2.31 18.07 63.11±5.33 18.21 78.72±6.13 6.24

表 4 非线性模式下3种算法的实验比较 Table 4 Experimental comparision of three algorithms on UCI datasets with nonlinear kernel
Dataset TWSVM PTSVM WPTSVM
正确率/% 训练时间/s 正确率/% 训练时间/s 正确率/% 训练时间/s
Spectf (267×46) 83.43±7.15 14.63 82.49±8.36 14.65 84.03±5.17 1.73
Cleve (296×13) 85.12±5.77 7.22 85.93±4.90 7.82 85.24±4.56 3.40
Wpbc (198×33) 79.36±5.52 4.12 78.03±6.59 1.72 79.98±6.62 0.59
P_gene (106×57) 65.50±18.23 2.25 64.13±21.17 2.22 68.13±16.71 1.19
Sonar (208×60) 63.29±18.65 7.55 64.50±13.50 8.63 68.43±13.26 2.78
Spect (267×22) 84.42±9.04 11.42 84.42±7.43 4.01 84.80±8.27 5.54
Monks2 (432×6) 68.77±15.24 5.02 68.71±3.43 6.43 68.99±11.07 4.57
Vertebral (310×6) 85.81±6.32 5.63 84.52±6.42 6.02 86.13±6.46 2.87
Monks3 (432×6) 98.70±3.89 11.09 98.52±4.44 9.97 99.26±2.22 8.03
Breast_gy(277×9) 75.86±5.89 5.24 73.57±4.10 4.04 75.94±6.69 0.87
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.
DOI: 10.11992/tis.2016030
中国人工智能学会和哈尔滨工程大学联合主办。
0

文章信息

花小朋, 孙一颗, 丁世飞
HUA Xiaopeng, SUN Yike, DING Shifei
一种改进的投影孪生支持向量机
An improved projection twin support vector machine
智能系统学报, 2016, 11(3): 384-389.
CAAI Transactions on Intelligent Systems, 2016, 11(3): 384-389.
DOI: 10.11992/tis.2016030

文章历史

收稿日期: 2016-3-20
网络出版日期: 2016-05-13

相关文章

工作空间