第11卷第3期 智能系统学报 Vol.11 No.3 2016年6月 CAAI Transactions on Intelligent Systems Jun.2016 D0I:10.11992/is.2016030. 网s络出版地址：http:/www.cnki.net/kcms/detail/23.1538.TP.20160513.0924.024.html 一种改进的投影孪生支持向量机 花小朋，孙一颗，丁世飞2 (1.盐城工学院信息工程学院，江苏盐城224051；2.中国矿业大学计算机学院，江苏徐州221116) 摘要：针对投影孪生支持向量机(PTSVM)在训练阶段欠考虑样本空间局部结构和局部信息的缺陷，提出一种具有 一定局部学习能力的有监督分类方法：加权投影孪生支持向量机(weighted PTSVM,WPTSVM)。相比于PTSVM, WPTSVM优势在于：通过构造类内近邻图为每个样本获取特定的权值，并且以加权均值取代标准均值，在一定程度 上提高了算法的局部学习能力：选取异类样本集中少量边界点构造优化问题的约束条件，很大程度上降低了二次规 划求解的时间复杂度：继承了PTSVM的优点，可以看成PTSVM的推广算法。理论分析及其在人造数据集和真实数 据集上的测试结果表明该方法具有上述优势。 关键词：分类：投影孪生支持向量机；局部信息；加权均值；近邻图；二次规划；约束条件；时间复杂度 中图分类号：TP391.4文献标志码：A文章编号：1673-4785(2016)03-0384-06 中文引用格式：花小朋，孙一颗，丁世飞.一种改进的投影孪生支持向量机[J].智能系统学报，2016,11(3)：384-391. 英文引用格式：HUA Xiaopeng,SUN Yike,.DING Shifei..An improved projection twin support vector machine[J].CAAI transac- tions on intelligent systems,2016,11(3):384-391. An improved projection twin support vector machine HUA Xiaopeng',SUN Yike',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 infor- mation of a sample space in the training process.Compared with PTSVM,WPTSVM improves its local learning a- bility 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 re- garded as an improved version of PTSVM.Experimental results on artificial and real datasets indicate the effective- ness of the WPTSVM method. Keywords:classification;projection twin support vector machine;local information;weighted mean;neighborhood graph;quadratic programming;constraint condition;time complexity 在分类问题中，经典支持向量机(SVM)依据间 隔最大化准则生成分类决策面，存在训练时间复杂 度偏高和欠考虑样本分布情况的缺陷2。近年 收稿日期：2016-03-20.网络出版日期：2016-05-13. 来，作为经典SVM的改进方法，非平行超平面分类 基金项目：国家重点基础研究计划项目(2013CB329s02):国家自然科学器(nonparellel hyperplane classifiers,NHCs)[)已经 基金项目(61379101)：江苏省自然科学基金项目 (BK20151299). 成为模式识别领域新的研究热点之一。孪生支持向 通信作者：花小朋.E-mail:xp_hua@163.com
第 １１ 卷第 ３ 期 智 能 系 统 学 报 Ｖｏｌ．１１ №．３ ２０１６ 年 ６ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｊｕｎ． ２０１６ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１６０３０． 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１６０５１３．０９２４．０２４．ｈｔｍｌ 一种改进的投影孪生支持向量机 花小朋１ ，孙一颗１ ，丁世飞２ （１．盐城工学院 信息工程学院，江苏 盐城 ２２４０５１； ２． 中国矿业大学 计算机学院，江苏 徐州 ２２１１１６） 摘 要：针对投影孪生支持向量机（ＰＴＳＶＭ）在训练阶段欠考虑样本空间局部结构和局部信息的缺陷，提出一种具有 一定局部学习能力的有监督分类方法：加权投影孪生支持向量机（ｗｅｉｇｈｔｅｄ ＰＴＳＶＭ，ＷＰＴＳＶＭ）。 相比于 ＰＴＳＶＭ， ＷＰＴＳＶＭ 优势在于：通过构造类内近邻图为每个样本获取特定的权值，并且以加权均值取代标准均值，在一定程度 上提高了算法的局部学习能力；选取异类样本集中少量边界点构造优化问题的约束条件，很大程度上降低了二次规 划求解的时间复杂度；继承了 ＰＴＳＶＭ 的优点，可以看成 ＰＴＳＶＭ 的推广算法。 理论分析及其在人造数据集和真实数 据集上的测试结果表明该方法具有上述优势。 关键词：分类；投影孪生支持向量机；局部信息；加权均值；近邻图；二次规划；约束条件；时间复杂度 中图分类号：ＴＰ３９１．４ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１６）０３⁃０３８４⁃０６ 中文引用格式：花小朋，孙一颗，丁世飞．一种改进的投影孪生支持向量机［Ｊ］． 智能系统学报， ２０１６， １１（３）： ３８４⁃３９１． 英文引用格式：ＨＵＡ Ｘｉａｏｐｅｎｇ， ＳＵＮ Ｙｉｋｅ， ＤＩＮＧ Ｓｈｉｆｅｉ． Ａｎ ｉｍｐｒｏｖｅｄ ｐｒｏｊｅｃｔｉｏｎ ｔｗｉｎ ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅ［Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃ⁃ ｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１６， １１（３）： ３８４⁃３９１． Ａｎ ｉｍｐｒｏｖｅｄ ｐｒｏｊｅｃｔｉｏｎ ｔｗｉｎ ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅ ＨＵＡ Ｘｉａｏｐｅｎｇ １ ， ＳＵＮ Ｙｉｋｅ １ ， ＤＩＮＧ Ｓｈｉｆｅｉ ２ （１． Ｓｃｈｏｏｌ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｙａｎｃｈｅｎｇ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ， Ｙａｎｃｈｅｎｇ ２２４０５１， Ｃｈｉｎａ； ２． Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， Ｃｈｉｎａ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｍｉｎｉｎｇ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， Ｘｕｚｈｏｕ ２２１１１６， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ａ ｓｕｐｅｒｖｉｓｅｄ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｍｅｔｈｏｄ ｈａｖｉｎｇ ａ ｌｏｃａｌ ｌｅａｒｎｉｎｇ ａｂｉｌｉｔｙ， ｃａｌｌｅｄ ｗｅｉｇｈｔｅｄ ｐｒｏｊｅｃｔｉｏｎ ｔｗｉｎ ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅ （ＷＰＴＳＶＭ）， ｉｓ ｐｒｏｐｏｓｅｄ． Ｔｈｉｓ ｍｅｔｈｏｄ ａｉｍｓ ｔｏ ｉｍｐｒｏｖｅ ｕｐｏｎ ａ ｄｅｆｅｃｔ ｔｈａｔ ｐｒｏｊｅｃｔｉｏｎ ｔｗｉｎ ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅｓ （ＰＴＳＶＭｓ） ｈａｖｅ， ｎａｍｅｌｙ， ｔｈａｔ ＰＴＳＶＭｓ ｄｏ ｎｏｔ ｔａｋｅ ａｃｃｏｕｎｔ ｏｆ ｔｈｅ ｌｏｃａｌ ｓｔｒｕｃｔｕｒｅ ａｎｄ ｌｏｃａｌ ｉｎｆｏｒ⁃ ｍａｔｉｏｎ ｏｆ ａ ｓａｍｐｌｅ ｓｐａｃｅ ｉｎ ｔｈｅ ｔｒａｉｎｉｎｇ ｐｒｏｃｅｓｓ． Ｃｏｍｐａｒｅｄ ｗｉｔｈ ＰＴＳＶＭ， ＷＰＴＳＶＭ ｉｍｐｒｏｖｅｓ ｉｔｓ ｌｏｃａｌ ｌｅａｒｎｉｎｇ ａ⁃ ｂｉｌｉｔｙ ｔｏ ｓｏｍｅ ｅｘｔｅｎｔ ｂｙ ａｔｔａｃｈｉｎｇ ｄｉｆｆｅｒｅｎｔ ｗｅｉｇｈｔｓ ｆｏｒ ｅａｃｈ ｓａｍｐｌｅ ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ｗｉｔｈｉｎ⁃ｃｌａｓｓ ｎｅｉｇｈｂｏｒｈｏｏｄ ｇｒａｐｈ ａｎｄ ｒｅｐｌａｃｉｎｇ ｔｈｅ ｓｔａｎｄａｒｄ ｍｅａｎ ｗｉｔｈ ａ ｗｅｉｇｈｔｅｄ ｍｅａｎ． Ｍｏｒｅｏｖｅｒ， ｔｏ ｒｅｄｕｃｅ ｃｏｍｐｕｔａｔｉｏｎａｌ ｃｏｍｐｌｅｘｉｔｙ， ＷＰＴＳＶＭ ｃｈｏｏｓｅｓ ａ ｓｍａｌｌ ｎｕｍｂｅｒ ｏｆ ｂｏｕｎｄａｒｙ ｐｏｉｎｔｓ ｉｎ ｔｈｅ ｃｏｎｔｒａｒｙ⁃ｃｌａｓｓ ｂａｓｅｄ ｏｎ ｔｈｅ ｂｅｔｗｅｅｎ－ｃｌａｓｓ ｎｅｉｇｈｂｏｒｈｏｏｄ ｇｒａｐｈ ｔｏ ｃｏｎｓｔｒｕｃｔ ｃｏｎｓｔｒａｉｎｔｓ ｏｆ ｔｈｅ ｏｒｉｇｉｎａｌ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍｓ． Ｔｈｅ ｍｅｔｈｏｄ ｉｎｈｅｒｉｔｓ ｔｈｅ ｍｅｒｉｔｓ ｏｆ ＰＴＳＶＭ ａｎｄ ｃａｎ ｂｅ ｒｅ⁃ ｇａｒｄｅｄ ａｓ ａｎ ｉｍｐｒｏｖｅｄ ｖｅｒｓｉｏｎ ｏｆ ＰＴＳＶＭ． Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｏｎ ａｒｔｉｆｉｃｉａｌ ａｎｄ ｒｅａｌ ｄａｔａｓｅｔｓ ｉｎｄｉｃａｔｅ ｔｈｅ ｅｆｆｅｃｔｉｖｅ⁃ ｎｅｓｓ ｏｆ ｔｈｅ ＷＰＴＳＶＭ ｍｅｔｈｏｄ． Ｋｅｙｗｏｒｄｓ：ｃｌａｓｓｉｆｉｃａｔｉｏｎ； ｐｒｏｊｅｃｔｉｏｎ ｔｗｉｎ ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅ； ｌｏｃａｌ ｉｎｆｏｒｍａｔｉｏｎ； ｗｅｉｇｈｔｅｄ ｍｅａｎ； ｎｅｉｇｈｂｏｒｈｏｏｄ ｇｒａｐｈ； ｑｕａｄｒａｔｉｃ ｐｒｏｇｒａｍｍｉｎｇ； ｃｏｎｓｔｒａｉｎｔ ｃｏｎｄｉｔｉｏｎ； ｔｉｍｅ ｃｏｍｐｌｅｘｉｔｙ 收稿日期：２０１６⁃０３⁃２０． 网络出版日期：２０１６⁃０５⁃１３． 基金项目：国家重点基础研究计划项目（２０１３ＣＢ３２９５０２）；国家自然科学 基 金 项 目 （ ６１３７９１０１ ）； 江 苏 省 自 然 科 学 基 金 项 目 （ＢＫ２０１５１２９９）． 通信作者：花小朋． Ｅ⁃ｍａｉｌ：ｘｐ＿ｈｕａ＠ １６３．ｃｏｍ． 在分类问题中，经典支持向量机（ＳＶＭ）依据间 隔最大化准则生成分类决策面，存在训练时间复杂 度偏高和欠考虑样本分布情况的缺陷［１⁃２］ 。 近年 来，作为经典 ＳＶＭ 的改进方法，非平行超平面分类 器（ ｎｏｎｐａｒｅｌｌｅｌ ｈｙｐｅｒｐｌａｎｅ ｃｌａｓｓｉｆｉｅｒｓ，ＮＨＣｓ） ［３］ 已经 成为模式识别领域新的研究热点之一。 孪生支持向
第3期 花小朋，等：一种改进的投影孪生支持向量机 ·385· 量机(twin support vector machine,TWSVM)[a是 1 投影孪生支持向量机(PTSVM) NHCs方法中主要代表性算法之一，其主要思想源 于泛化特征值中心支持向量机(generalized eigenval- 假定两类学习样本集分别表示为实数矩阵 ue proximal SVM,GEPSVM)[。TWSVM将GEPS- A∈Rmxa和B∈R“。n为样本维度，m1和m2分别 VM中两个优化子问题转换成两个形如SVM的小 为第1类(+1类)和第2类(-1类)样本数目，并且 规模二次规划问题，从而使其训练时间复杂度缩减 令m=m,+m2。PTSVM算法的优化目标可以看作是 为经典SVM的1/4。除了训练速度上的优势，TWS 在实数空间中寻找两个最佳投影轴为w,和w2的 VM还继承了GEPSVM能够在线性模式很好地处理 决策超平面： 异或(XOR)样本分类问题的优势。然而，当两类样 x'w1+b1=0,x'w2+b2=0. (1) 本具有不同散度分布时，TWSVM的泛化性能欠 佳6。文献[7]提出一种新的非平行超平面分类 需要注意的是，这里的偏置b,=-eAw,/m1, 器：投影孪生支持向量机(projection twin support b2=-eBw2/m2,e1和e2是两个实体为1的列向量， vector machine,PTSVM)。与TWSVM不同的是， A=[x"x"…],xBx=[x2x2…,],x0 PTSVM优化目的是为每类样本寻找最佳投影轴，而 表示第i类的第j个样本。 且通过递归迭代算法，PTSVM能够生成多个正交投 第1类超平面的优化准则PTSVM-1: 影轴。实验结果表明，PTSVM对复杂的XOR问题 min 具有更好的分类能力。为解决非线性分类问题。文 i-) 献[8]进一步提出PTSVM的非线性方法。 然而分析发现，PTSVM在训练过程中仅仅考虑 s.t. xe-w)∑0+≥1,5 样本空间的全局结构和全局信息，忽视了样本空间 (2) 的局部结构和局部信息。许多研究结果表明同类数 式中C1是惩罚参数，为损失变量。 据集中大部分样本在局部上是关联的（即数据集中 显然，PTSVM在优化目标函数中考虑的训练样 存在潜藏的局部几何结构)，而这种内在的局部信 息对数据分类又是至关重要的[。这种潜在的局 本集内在的散度 )体 部信息可以通过数据集中样本间的k近邻关系进行 m1j=1 现的是样本集内在的全局分布。故该方法忽视了潜 挖掘[11山」 藏在训练样本集内部的局部几何结构。 基于上述分析，本文基于PTSVM提出一种新 的具有一定局部学习能力的非平行超平面分类器算 2加权投影孪生支持向量机(WPTSVM) 法：加权投影孪生支持向量机(weighted PTSVM, WPTSVM)。相比于PTSVM,WPTSVM优势体现在 2.1算法构造 以下4个方面：1)通过构造类内近邻图为每个样本 为刻画同类样本集内在的紧凑型和异类样本集 获取特定的权值，并且以加权均值取代标准均值，在 间的分散性，依据图论1,11为每类决策面构建类内 一定程度上提高了算法的局部学习能力：2)选取异 近邻图G和类间近邻图G· 类样本集中少量边界点构造优化问题的约束条件， 定义1给定第c类中的任意两个样本x)和 很大程度上降低了二次规划求解的时间复杂度； x⊙，(c=1,2;i,j=1,2,…,m),则类内近邻图G, 3)WPTSVM继承了PTSVM的优点，可以看成PTS 的相似矩阵W(W)mm,可定义为 VM的推广算法。4)WPTSVM具有更好分类性能。 听=ep(-En-Im9eNe(9)或0ee(s. (3) (0,其他 式中：t为热核参数，Ne(x)表示x的k近邻样本集。 1, is k nearest neighbors of 定义2]考虑第c类样本x⊙，给定相反类 W- 0 其他 中任意样本x(l=1,2,…,m),则类间近邻图Gd (4) 的相似矩阵W(W)ma,可定义为 依据定义2，第c类中每一个样本定义权重：
量机 （ ｔｗｉｎ ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅ， ＴＷＳＶＭ） ［４］ 是 ＮＨＣｓ 方法中主要代表性算法之一，其主要思想源 于泛化特征值中心支持向量机（ｇｅｎｅｒａｌｉｚｅｄ ｅｉｇｅｎｖａｌ⁃ ｕｅ ｐｒｏｘｉｍａｌ ＳＶＭ，ＧＥＰＳＶＭ） ［５］ 。 ＴＷＳＶＭ 将 ＧＥＰＳ⁃ ＶＭ 中两个优化子问题转换成两个形如 ＳＶＭ 的小 规模二次规划问题，从而使其训练时间复杂度缩减 为经典 ＳＶＭ 的 １ ／ ４。 除了训练速度上的优势，ＴＷＳ⁃ ＶＭ 还继承了 ＧＥＰＳＶＭ 能够在线性模式很好地处理 异或（ＸＯＲ）样本分类问题的优势。 然而，当两类样 本具有不同散度分布时， ＴＷＳＶＭ 的泛化性能欠 佳［６］ 。 文献［７］ 提出一种新的非平行超平面分类 器：投影孪生支持向量机 （ ｐｒｏｊｅｃｔｉｏｎ ｔｗｉｎ ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅ， ＰＴＳＶＭ）。 与 ＴＷＳＶＭ 不 同 的 是， ＰＴＳＶＭ 优化目的是为每类样本寻找最佳投影轴，而 且通过递归迭代算法，ＰＴＳＶＭ 能够生成多个正交投 影轴。 实验结果表明，ＰＴＳＶＭ 对复杂的 ＸＯＲ 问题 具有更好的分类能力。 为解决非线性分类问题。 文 献［８］进一步提出 ＰＴＳＶＭ 的非线性方法。 然而分析发现，ＰＴＳＶＭ 在训练过程中仅仅考虑 样本空间的全局结构和全局信息，忽视了样本空间 的局部结构和局部信息。 许多研究结果表明同类数 据集中大部分样本在局部上是关联的（即数据集中 存在潜藏的局部几何结构），而这种内在的局部信 息对数据分类又是至关重要的［９］ 。 这种潜在的局 部信息可以通过数据集中样本间的 ｋ 近邻关系进行 挖掘［９⁃１１］ 。 基于上述分析，本文基于 ＰＴＳＶＭ 提出一种新 的具有一定局部学习能力的非平行超平面分类器算 法：加权投影孪生支持向量机 （ ｗｅｉｇｈｔｅｄ ＰＴＳＶＭ， ＷＰＴＳＶＭ）。 相比于 ＰＴＳＶＭ，ＷＰＴＳＶＭ 优势体现在 以下 ４ 个方面：１）通过构造类内近邻图为每个样本 获取特定的权值，并且以加权均值取代标准均值，在 一定程度上提高了算法的局部学习能力；２）选取异 类样本集中少量边界点构造优化问题的约束条件， 很大程度上降低了二次规划求解的时间复杂度； ３）ＷＰＴＳＶＭ继承了 ＰＴＳＶＭ 的优点，可以看成 ＰＴＳ⁃ ＶＭ 的推广算法。 ４）ＷＰＴＳＶＭ 具有更好分类性能。 １ 投影孪生支持向量机（ＰＴＳＶＭ） 假定两类学习样本集分别表示为实数矩阵 Ａ∈Ｒ ｍ１ ×ｎ和 Ｂ∈Ｒ ｍ２ ×ｎ 。 ｎ 为样本维度，ｍ１ 和 ｍ２ 分别 为第 １ 类（＋１ 类）和第 ２ 类（ －１ 类）样本数目，并且 令 ｍ ＝ｍ１ ＋ｍ２ 。 ＰＴＳＶＭ 算法的优化目标可以看作是 在实数空间中寻找两个最佳投影轴为 ｗ１ 和 ｗ２ 的 决策超平面： ｘ Ｔｗ１ ＋ ｂ１ ＝ ０，ｘ Ｔｗ２ ＋ ｂ２ ＝ ０． （１） 需要注意的是，这里的偏置ｂ１ ＝ － ｅ Ｔ １Ａｗ１ ／ ｍ１ ， ｂ２ ＝ －ｅ Ｔ ２Ｂｗ２ ／ ｍ２ ，ｅ１ 和 ｅ２ 是两个实体为 １ 的列向量， Ａ＝ ［ｘ （１） １ ｘ （１） ２ … ｘ （１） ｍ１ ］ Ｔ ， ｘＢｘ ＝ ［ｘ （２） １ ｘ （２） ２ …，ｘ （２） ｍ２ ］ Ｔ ， ｘ （ｉ） ｊ 表示第 ｉ 类的第 ｊ 个样本。 第 １ 类超平面的优化准则 ＰＴＳＶＭ⁃１： ｍｉｎ １ ２ ∑ ｍ１ ｉ ＝ １ ｗ Ｔ １ ｘ （１） ｉ － ｗ Ｔ １ １ ｍ１ ∑ ｍ１ ｊ ＝ １ ｘ （１） ｊ æ è ç ö ø ÷ ２ ＋ Ｃ１∑ ｍ２ ｌ ＝ １ ξｌ ｓ．ｔ． － ｗ Ｔ １ ｘ （２） ｌ － ｗ Ｔ １ １ ｍ１ ）∑ ｍ１ ｊ ＝ １ ｘ （１） ｌ æ è ç ö ø ÷ ＋ ξｌ ≥ １，ξｌ ≥ ０， （２） 式中 Ｃ１ 是惩罚参数，xｌ为损失变量。 显然，ＰＴＳＶＭ 在优化目标函数中考虑的训练样 本集内在的散度 ∑ ｍ１ ｉ ＝ １ ｗ Ｔ １ ｘ （１） ｉ － ｗ Ｔ １ １ ｍ１ ∑ ｍ１ ｊ ＝ １ ｘ （１） ｊ æ è ç ö ø ÷ ２ ，体 现的是样本集内在的全局分布。 故该方法忽视了潜 藏在训练样本集内部的局部几何结构。 ２ 加权投影孪生支持向量机（ＷＰＴＳＶＭ） ２．１ 算法构造 为刻画同类样本集内在的紧凑型和异类样本集 间的分散性，依据图论［１０，１２］ 为每类决策面构建类内 近邻图 Ｇｓ和类间近邻图 Ｇｄ 。 定义 １ 给定第 ｃ 类中的任意两个样本 ｘ （ｃ） ｉ 和 ｘ （ｃ） ｊ ， （ｃ ＝ １，２；ｉ，ｊ ＝ １，２， …，ｍｃ）， 则类内近邻图 Ｇｓ 的相似矩阵 Ｗ ｓ Ｗ ｓ ｉｊ ( ) ｍ１ ×ｍ１可定义为 Ｗ ｓ ｉｊ ＝ ｅｘｐ（ － ‖ｘ （ｃ） ｉ － ｘ （ｃ） ｊ ‖２ ／ ｔ），ｘ （ｃ） ｊ ∈ Ｎｅ（ｘ （ｃ） ｉ ） 或 ｘ （ｃ） ｉ ∈ Ｎｅ（ｘ （ｃ） ｊ ）， ０， 其他 { （３） 式中：ｔ 为热核参数，Ｎｅ（ｘ）表示 ｘ 的 ｋ 近邻样本集。 定义 ２ ［１２］ 考虑第 ｃ 类样本 ｘ （ｃ） ｉ ，给定相反类 中任意样本 ｘ （ｃ） ｌ （ｌ ＝ １， ２， …，ｍｃ），则类间近邻图 Ｇｄ 的相似矩阵 Ｗ ｄ Ｗ ｄ ｉｌ ( ) ｍ１ ×ｍ２可定义为 Ｗ ｄ ｉｌ ＝ １， ｘ （ｃ） ｌ ｉｓ ｋ ｎｅａｒｅｓｔ ｎｅｉｇｈｂｏｒｓ ｏｆ ｘ （ｃ） ｉ {０， 其他 （４） 依据定义 ２，第 ｃ 类中每一个样本定义权重： 第 ３ 期 花小朋，等：一种改进的投影孪生支持向量机 ·３８５·
·386. 智能系统学报 第11卷 1, 3i,W≠0 和= (5) 式中a=[a1,a,…,a,]T。 0, 其他 由此对偶问题的求解可得原问题式(6)中投影 显然，权重=1样本是第c类样本集的边界样本。 轴"1。类似的方法，可求原问题式(7)中投影 定义3 WPTSVM算法中，第1类训练样本集 轴w2o 相应决策超平面的优化准则WPTSVM-1: 对于未知样本x,WPTSVM的决策函数为 2 (d,→x∈第1类 2=1 label(x)=argmind= 1=1 e=1.2 d,→x∈第2类 st-(wx9-w9g"）+5≥P点≥0 (10) (6) 式中：d,=wx-w2入x1,·表示绝对值。 1 第2类超平面优化准则WPTSVM-2: 2.2算法分析 1 2 这里以WPTSVM的第1类样本优化问题 WPTSVM-1为例进行算法分析，第2类样本优化问 题WPTSVM-2有类似的算法分析。 s.tf"(wx-w∑2x2）+n:≥f,m:≥0 考虑对偶形式式(9)，假设实对称矩阵 i=1 (7) (A-e,eE"A)'Dm(A-e,eE"A))可逆（若 式中：C1和C2是惩罚参数，，和7：为损失变量， 不可逆，可采用类似文献[3]方法引入正则化项 p9-2wA9=p/p°，e=1,2。 I(e>0),e尽可能的小)。式(14)中的核函数 K(·)只有保证Mercer核时，才能保证其是二次凸 i= i=1 式(6)中，P)代表样本x)的权重，p)值越 规划，所求的解才为全局最优解。为验证这一问题， 大，表示x)越重要，对保持样本空间局部信息的 给出如下定理。 定理1式(9)为凸二次规划。 贡献程度越大：∑入x:”为第1类样本空间的加 证明式(9)核矩阵： i三1 权均值，比起式(2)中的标准均值更能体现样本空 K=[kg=(F(2)(B -e2eE(DA)). 间的局部结构)；约束条件表明WPTSVM-1仅仅 ((A -e,eE(DA)D((A -eeE(A))-1. 考虑第2类样本中2=1的边界样本。显然，式 (F2②(B-e2eEA))T (6)优化目标是为第1类样本寻找最佳投影轴 xwx1,使得权重较大的样本投影后尽可能聚集在加 是实对称矩阵。下面证明矩阵K是半正定的。设 权均值中心附近，而第2类中”=1的边界样本离 任意x∈R,则有x'Kr=(x(F2)(B-e2eE四 中心尽可能远。式(7)有类似的几何解释式。式 A)(A-eeE”A)TD0(A-e,eEDA)2)2≥ (6)矩阵形式为 O,因此K半正定且为Mercer核函数。根据文献 min 2 (Aw -eeE(Aw )T [14]中引理2可知，式(9)为凸二次规划。证毕。 定理2假定：是对偶问题式(9)的解，则w D((Aw:-e:eE(Aw)+Ces 是原优化问题式(6)的全局最优解。 s.t-F②(Bw1-e,eEAw,)+专≥F2e2,专≥0 证明由定理1的证明可得，式(9)为凸二次 (8) 规划问题，又依据文献[14]中引理3的满足条件可 式中：52=(，…，专)'，D0=diag(p0,…,p), 知，该二次规划的解为全局最优解。证毕。 Ew=diag(A",…,9),F2=diag2,…f)。 2.3算法比较 类似于传统SVM求解方法，通过引入拉格朗日 2.3.1泛化性能 函数生成式(8)的对偶问题 定理3 PTSVM是WPTSVM的特例。 min2d(F(B-eeiE"A)× 证明考虑WPTSVM的第1类样本的优化准 则(7)。令D1)=I∈Rmm,F(2)=1∈R2Xm,则式 ((A -e:eE(DA)D(D(A -e eE(DA)) (7)转化为PTSVM的第1类样本的优化准则(2)。 (F2(B-ezeE(DA))a -eia 对于WPTSVM的第2类样本的优化准则(8)有类似 s.t.0≤w≤C1e2 (9) 的特性。因此，PTSVM是WPTSVM的特例，而
ｆ （ｃ） ｌ ＝ １， ∃ｉ，Ｗ ｄ ｉｌ ≠ ０ {０， 其他 （５） 显然，权重 ｆ （ｃ） ｌ ＝ １ 样本是第 ｃ 类样本集的边界样本。 定义 ３ ＷＰＴＳＶＭ 算法中，第 １ 类训练样本集 相应决策超平面的优化准则 ＷＰＴＳＶＭ⁃１： ｍｉｎ １ ２ ∑ ｍ１ ｉ ＝ １ ρ （１） ｉ ｗ Ｔ １ ｘ （１） ｉ － ｗ Ｔ １∑ ｍ１ ｊ ＝ １ λ （１） ｊ ｘ （１） ( ｊ ) ２ ＋ Ｃ１∑ ｍ２ ｌ ＝ １ ξｌ ｓ．ｔ． － ｆ （２） ｌ ｗ Ｔ １ ｘ （２） ｌ － ｗ Ｔ １∑ ｍ１ ｊ ＝ １ λ （１） ｊ ｘ （１） ( ｊ ) ＋ ξｌ ≥ ｆ （２） ｌ ，ξｌ ≥ ０ （６） 第 ２ 类超平面优化准则 ＷＰＴＳＶＭ⁃２： ｍｉｎ １ ２ ∑ ｍ２ ｌ ＝ １ ρ （２） ｌ ｗ Ｔ ２ ｘ （２） ｌ － ｗ Ｔ ２∑ ｍ２ ｊ ＝ １ λ （２） ｊ ｘ （２） ( ｊ ) ２ ＋ Ｃ２∑ ｍ１ ｉ ＝ １ ηｉ， ｓ．ｔ．ｆ （１） ｉ ｗ Ｔ ２ ｘ （１） ｉ － ｗ Ｔ ２∑ ｍ２ ｊ ＝ １ λ （２） ｊ ｘ （２） ( ｊ ) ＋ ηｉ ≥ ｆ （１） ｉ ，ηｉ ≥ ０ （７） 式中： Ｃ１ 和 Ｃ２ 是惩罚参数，ξｌ 和 ηｉ 为损失变量， ρ （ｃ） ｉ ＝∑ ｍｃ ｊ ＝ １ Ｗ ｓ ｉｊ，λ （ｃ） ｊ ＝ ρ （ｃ） ｊ ／∑ ｍｃ ｉ ＝ １ ρ （ｃ） ｉ ，ｃ ＝ １，２。 式（６）中，ρ （１） ｉ 代表样本 ｘ （１） ｉ 的权重，ρ （１） ｉ 值越 大，表示 ｘ （１） ｉ 越重要，对保持样本空间局部信息的 贡献程度越大； ∑ ｍ１ ｊ ＝ １ λ （１） ｊ ｘ （１） ｊ 为第 １ 类样本空间的加 权均值，比起式（２）中的标准均值更能体现样本空 间的局部结构［１３］ ；约束条件表明 ＷＰＴＳＶＭ⁃１ 仅仅 考虑第 ２ 类样本中 ｆ （２） ｌ ＝ １ 的边界样本。 显然，式 （６） 优化目标是为第 １ 类样本寻找最佳投影轴 ｘｗｘ１ ，使得权重较大的样本投影后尽可能聚集在加 权均值中心附近，而第 ２ 类中 ｆ （１） ｌ ＝ １ 的边界样本离 中心尽可能远。 式（７） 有类似的几何解释式。 式 （６）矩阵形式为 ｍｉｎ １ ２ Ａｗ１ － ｅ１ ｅ Ｔ １Ｅ （１）Ａｗ１ ( ) Ｔ Ｄ （１） Ａｗ１ － ｅ１ ｅ Ｔ １Ｅ （１）Ａｗ１ ( ) ＋ Ｃ１ ｅ Ｔ ２ ξ ｓ．ｔ． － Ｆ （２） Ｂｗ１ － ｅ２ ｅ Ｔ １Ｅ （１）Ａｗ１ ( ) ＋ ξ ≥ Ｆ （２） ｅ２，ξ ≥０ （８） 式中：ξ２ ＝ （ ξ１ ，…，ξｍ２ ） Ｔ ，Ｄ （１） ＝ ｄｉａｇ（ ρ （１） １ ，…，ρ （１） ｍ１ ）， Ｅ （１）＝ ｄｉａｇ（λ （１） １ ，…，λ （１） ｍ１ ），Ｆ （２）＝ ｄｉａｇ（ｆ （２） １ ，…，ｆ （２） ｍ２ ）。 类似于传统 ＳＶＭ 求解方法，通过引入拉格朗日 函数生成式（８）的对偶问题 ｍｉｎ １ ２ α Ｔ Ｆ （２） Ｂ － ｅ２ ｅ Ｔ １Ｅ （１） ( ( Ａ) ) × Ａ － ｅ１ ｅ Ｔ １Ｅ （１） ( Ａ) ＴＤ （１） Ａ － ｅ１ ｅ Ｔ １Ｅ （１） ( ( Ａ) ) －１ Ｆ （２） Ｂ － ｅ２ ｅ Ｔ １Ｅ （１） ( ( Ａ) ) Ｔα － ｅ Ｔ ２α ｓ．ｔ． ０ ≤ α ≤ Ｃ１ ｅ２ （９） 式中 α＝ ［α１ ，α２ ，…，αｍ２ ］ Ｔ 。 由此对偶问题的求解可得原问题式（６）中投影 轴 ｗ１ 。 类 似 的 方 法， 可 求 原 问 题 式 （ ７） 中 投 影 轴 ｗ２ 。 对于未知样本 ｘ，ＷＰＴＳＶＭ 的决策函数为 ｌａｂｅｌ（ｘ） ＝ ａｒｇｍｉｎ ｃ ＝ １，２ ｛ｄｃ｝ ＝ ｄ１⇒ｘ ∈ 第 １ 类 {ｄ２⇒ｘ ∈ 第 ２ 类 （１０） 式中：ｄｃ ＝ ｗ Ｔ ｃ ｘ－ｗ Ｔ ｃ ∑ ｍｃ ｊ ＝ １ λ （ｃ） ｊ ｘ （ｃ） ｊ ， · 表示绝对值。 ２．２ 算法分析 这里 以 ＷＰＴＳＶＭ 的 第 １ 类 样 本 优 化 问 题 ＷＰＴＳＶＭ⁃１ 为例进行算法分析，第 ２ 类样本优化问 题 ＷＰＴＳＶＭ⁃２ 有类似的算法分析。 考虑 对 偶 形 式 式 （ ９ ）， 假 设 实 对 称 矩 阵 Ａ － ｅ１ ｅ Ｔ １Ｅ （１） ( Ａ) ＴＤ （１） Ａ － ｅ１ ｅ Ｔ １Ｅ （１） ( ( Ａ) ) 可逆（若 不可逆，可采用类似文献［ ３］ 方法引入正则化项 Ｉ（ε＞０），ε 尽 可 能 的 小）。 式 （ １４ ） 中 的 核 函 数 Ｋ（·）只有保证 Ｍｅｒｃｅｒ 核时，才能保证其是二次凸 规划，所求的解才为全局最优解。 为验证这一问题， 给出如下定理。 定理 １ 式（９）为凸二次规划。 证明 式（９）核矩阵： Ｋ ～ ＝ ［ ｋ ～ ｉｊ ＝ Ｆ （２） Ｂ － ｅ２ ｅ Ｔ １Ｅ （１） ( ( Ａ) )· Ａ － ｅ１ ｅ Ｔ １Ｅ （１） ( Ａ) ＴＤ （１） Ａ － ｅ１ ｅ Ｔ １Ｅ （１） ( ( Ａ) ) －１· Ｆ （２） Ｂ － ｅ２ ｅ Ｔ １Ｅ （１） ( ( Ａ) ) Ｔ 是实对称矩阵。 下面证明矩阵 Ｋ ～ 是半正定的。 设 任意 ｘ ∈ Ｒ ｍ２ ， 则有 ｘ ＴＫ ～ ｘ ＝ （ ｘ Ｔ （Ｆ （２） （Ｂ－ｅ２ ｅ Ｔ １ Ｅ （１） Ａ）） （（Ａ－ｅ１ ｅ Ｔ １ Ｅ （１）Ａ） ＴＤ （１） （Ａ－ｅ１ ｅ Ｔ １ Ｅ （１）Ａ）） －１／ ２ ） ２≥ ０，因此 Ｋ ～ 半正定且为 Ｍｅｒｃｅｒ 核函数。 根据文献 ［１４］中引理 ２ 可知，式（９）为凸二次规划。 证毕。 定理 ２ 假定 α 是对偶问题式（９）的解，则 ｗ１ 是原优化问题式（６）的全局最优解。 证明 由定理 １ 的证明可得，式（９） 为凸二次 规划问题，又依据文献［１４］中引理 ３ 的满足条件可 知，该二次规划的解为全局最优解。 证毕。 ２．３ 算法比较 ２．３．１ 泛化性能 定理 ３ ＰＴＳＶＭ 是 ＷＰＴＳＶＭ 的特例。 证明 考虑 ＷＰＴＳＶＭ 的第 １ 类样本的优化准 则（７）。 令 Ｄ （１） ＝ Ｉ∈Ｒ ｍ１ ×ｍ１ ，Ｆ （２） ＝ Ｉ∈Ｒ ｍ２ ×ｍ２ ，则式 （７）转化为 ＰＴＳＶＭ 的第 １ 类样本的优化准则（２）。 对于 ＷＰＴＳＶＭ 的第 ２ 类样本的优化准则（８）有类似 的特 性。 因 此， ＰＴＳＶＭ 是 ＷＰＴＳＶＭ 的 特 例， 而 ·３８６· 智 能 系 统 学 报 第 １１ 卷
第3期 花小朋，等：一种改进的投影孪生支持向量机 .387. WPTSVM是PTSVM的推广算法。证毕。 第2类超平面的优化准则为 定理3说明了本文提出的WPTSVM算法继承 了PTSVM的优点。进一步比较式(7)和(2)可知， min(K(B.C)u:-e(BC) PTSVM仅仅考虑类内样本的全局信息，而WPTSVM (K(B,CT)u,-e,eE2K(B,CT)u2)C2ein, 用加权均值代替PTSVM中标准均值，可以在一定 s.t.F((K(A.C")uz -eeEK(B.CT)u2)+ 程度上提高算法的局部学习能力，因为基于近邻图 n≥F"e1,n≥0 (12) 的加权均值比起标准均值更能体现样本空间的局部 通过引入拉格朗日函数，可按照类似上述 结构)。除此之外，WPTSVM还在优化目标函数中 WPTSVM算法的推导过程分别得出式(11)和(12) 引入了样本权值，权值越大，说明该样本越重要，对 的对偶形式，然后通过二次规划求解可求得投影矢 保持训练样本集潜在局部信息的贡献程度越大。图 量u,和u2。NWPTSVM的决策函数为 1给出了WPTSVM与PTSVM在人造数据集上的分 (d,→x∈第1类 类决策面。不难看出，WPTSVM的决策面能够在一 label(x)=argmind. (d2→xe第2类 定程度上体现样本集内在局部流形结构，而PTSVM (13) 相对较弱。 1.09w 式中d.=K(x',C),- 9K9)r.c)m。 =1 0.6 PTSVM 3实验分析 0.2 -0.2 实验选用人造数据集和真实数据集，进一步验 -0.6 WPTSVM 证本文WPTSVM方法的有效性。实验环境： -1.0 2.3 GHz CPU,2GB内存，实验软件MATLAB7.1。 -0.8-0.6-0.4-0.200.20.40.60.81.0 3.1复杂交叉数据集 图1两种算法人造数据集上的比较 相对于经典SVM,线性模式下对XOR问题的 Fig.1 Comparision of two algorithms on artificial dataset 测试能力是非平行超平面分离器优势之一[3。因 2.3.2训练时间复杂度 此，本节首先验证MPTSVM测试交叉数据集的能 从二次规划求解角度分析，PTSVM在训练阶段 力。图2给出一种较复杂的人造交叉数据集：Comx- 要针对每类中全部样本进行求解，所以计算复杂度 or)。表1给出了TWSVM,.PTSVM和WPTSVM三 为o(m+m2),而WPTSVM优化准则中约束条件指 种算法在该测试数据集上10折交叉验证结果。参 明只对=1的样本（边界样本）进行二次规划求 数C,与C,的搜索范围为{21i=-8,-6,…,+8}: 解，计算复杂度为o(m-y+m2-v),其中m1-w,m2-w WPTSVM中类内近邻参数k,的搜索范围为{1,2， 分别为第1类样本及第2类样本中相应边界样本点 …,9},类间近邻参数k2=5,热核参数t的搜索范围 数。诚然，WPTSVM在训练阶段要事先求出每个样 为{2Ii=-1,0,…,8}。从表1实验结果来看，PTS 本的类内权重及类间权重，计算复杂度分别为0 VM分类性能优于TWSVM,而本文WPTSVM则具 (m+m)和o(2m1·m2)。 有更佳的分类性能。 2.3.3构造非线性分类算法 1.0 针对线性不可分情况，本文进一步提出基于核 0.6 PTSVM 空间的非线性WPTSVM算法一NWPTSVM。 0.2 定义4 NWPTSVM的第1类超平面的优化准 则为 WPTSVM -0.6 mi5Ka.c'4,-eeiE"(A.c)'D" -1.0 -0.8-0.6-0.4-0.200.2040.60.81.0 (K(A,C)u-eeE(K(A,C")u)+Ce, s.t.-F (K(B.CT)u:-ezeEK(A.CT)u)+ 图2复杂交叉数据集 专≥F2e2,5≥0 (11) Fig.2 Compxor dataset
ＷＰＴＳＶＭ 是 ＰＴＳＶＭ 的推广算法。 证毕。 定理 ３ 说明了本文提出的 ＷＰＴＳＶＭ 算法继承 了 ＰＴＳＶＭ 的优点。 进一步比较式（７）和（２）可知， ＰＴＳＶＭ 仅仅考虑类内样本的全局信息，而 ＷＰＴＳＶＭ 用加权均值代替 ＰＴＳＶＭ 中标准均值，可以在一定 程度上提高算法的局部学习能力，因为基于近邻图 的加权均值比起标准均值更能体现样本空间的局部 结构［１３］ 。 除此之外，ＷＰＴＳＶＭ 还在优化目标函数中 引入了样本权值，权值越大，说明该样本越重要，对 保持训练样本集潜在局部信息的贡献程度越大。 图 １ 给出了 ＷＰＴＳＶＭ 与 ＰＴＳＶＭ 在人造数据集上的分 类决策面。 不难看出，ＷＰＴＳＶＭ 的决策面能够在一 定程度上体现样本集内在局部流形结构，而 ＰＴＳＶＭ 相对较弱。 图 １ 两种算法人造数据集上的比较 Ｆｉｇ．１ Ｃｏｍｐａｒｉｓｉｏｎ ｏｆ ｔｗｏ ａｌｇｏｒｉｔｈｍｓ ｏｎ ａｒｔｉｆｉｃｉａｌ ｄａｔａｓｅｔ ２．３．２ 训练时间复杂度 从二次规划求解角度分析，ＰＴＳＶＭ 在训练阶段 要针对每类中全部样本进行求解，所以计算复杂度 为 ｏ（ｍ ３ １ ＋ｍ ３ ２ ），而 ＷＰＴＳＶＭ 优化准则中约束条件指 明只对 ｆ （ｃ） ｌ ＝ １ 的样本（边界样本）进行二次规划求 解，计算复杂度为 ｏ（ｍ ３ １－ＳＶ ＋ｍ ３ ２－ＳＶ ），其中 ｍ１－ＳＶ ，ｍ２－ＳＶ 分别为第 １ 类样本及第 ２ 类样本中相应边界样本点 数。 诚然，ＷＰＴＳＶＭ 在训练阶段要事先求出每个样 本的类内权重及类间权重，计算复杂度分别为 ｏ （ｍ ２ １ ＋ｍ ２ ２ ）和 ｏ（２ｍ１·ｍ２ ）。 ２．３．３ 构造非线性分类算法 针对线性不可分情况，本文进一步提出基于核 空间的非线性 ＷＰＴＳＶＭ 算法———ＮＷＰＴＳＶＭ。 定义 ４ ＮＷＰＴＳＶＭ 的第 １ 类超平面的优化准 则为 ｍｉｎ １ ２ Ｋ（Ａ，Ｃ Ｔ ）ｕ１ － ｅ１ ｅ Ｔ １Ｅ （１）Ｋ（Ａ，Ｃ Ｔ ）ｕ１ ( ) ＴＤ （１）· Ｋ（Ａ，Ｃ Ｔ ）ｕ１ － ｅ１ ｅ Ｔ １Ｅ （１）Ｋ（Ａ，Ｃ Ｔ ）ｕ１ ( ) ＋ Ｃ１ ｅ Ｔ ２ ξ， ｓ．ｔ． － Ｆ （２） Ｋ（Ｂ，Ｃ Ｔ ）ｕ１ － ｅ２ ｅ Ｔ １Ｅ （１）Ｋ（Ａ，Ｃ Ｔ ）ｕ１ ( ) ＋ ξ ≥ Ｆ （２） ｅ２ ，ξ ≥ ０ （１１） 第 ２ 类超平面的优化准则为 ｍｉｎ １ ２ Ｋ（Ｂ，Ｃ Ｔ ）ｕ２ － ｅ２ ｅ Ｔ ２Ｅ （２）Ｋ（Ｂ，Ｃ Ｔ ）ｕ２ ( ) ＴＤ （２）· Ｋ（Ｂ，Ｃ Ｔ ）ｕ２ － ｅ２ ｅ Ｔ ２Ｅ （２）Ｋ（Ｂ，Ｃ Ｔ ）ｕ２ ( ) ＋ Ｃ２ ｅ Ｔ １η， ｓ．ｔ． Ｆ （１） Ｋ（Ａ，Ｃ Ｔ ）ｕ２ － ｅ１ ｅ Ｔ ２Ｅ （２）Ｋ（Ｂ，Ｃ Ｔ ）ｕ２ ( ) ＋ η ≥ Ｆ （１） ｅ１ ，η ≥ ０ （１２） 通 过 引 入 拉 格 朗 日 函 数， 可 按 照 类 似 上 述 ＷＰＴＳＶＭ 算法的推导过程分别得出式（１１）和（１２） 的对偶形式，然后通过二次规划求解可求得投影矢 量 ｕ１ 和 ｕ２ 。 ＮＷＰＴＳＶＭ 的决策函数为 ｌａｂｅｌ（ｘ） ＝ ａｒｇｍｉｎ ｃ ＝ １，２ ｛ｄｃ｝ ＝ ｄ１⇒ｘ ∈ 第 １ 类 {ｄ２⇒ｘ ∈ 第 ２ 类 （１３） 式中 ｄｃ ＝ Ｋ（ｘ Ｔ ，Ｃ Ｔ ）ｕｉ －∑ ｍｃ ｊ ＝ １ λ （ｃ） ｊ Ｋ（（ｘ （ｃ） ｊ ） Ｔ ，Ｃ Ｔ ）ｕｉ 。 ３ 实验分析 实验选用人造数据集和真实数据集，进一步验 证本 文 ＷＰＴＳＶＭ 方 法 的 有 效 性。 实 验 环 境： ２．３ ＧＨｚ ＣＰＵ，２ ＧＢ 内存，实验软件 ＭＡＴＬＡＢ ７．１。 ３．１ 复杂交叉数据集 相对于经典 ＳＶＭ，线性模式下对 ＸＯＲ 问题的 测试能力是非平行超平面分离器优势之一［３⁃５］ 。 因 此，本节首先验证 ＭＰＴＳＶＭ 测试交叉数据集的能 力。 图 ２ 给出一种较复杂的人造交叉数据集：Ｃｏｍｘ⁃ ｏｒ ［７］ 。 表 １ 给出了 ＴＷＳＶＭ、ＰＴＳＶＭ 和 ＷＰＴＳＶＭ 三 种算法在该测试数据集上 １０ 折交叉验证结果。 参 数 Ｃ１与 Ｃ２ 的搜索范围为｛２ ｉ ｜ ｉ ＝ － ８，－ ６，…，＋ ８｝； ＷＰＴＳＶＭ 中类内近邻参数 ｋ１ 的搜索范围为｛ １，２， …，９｝，类间近邻参数 ｋ２ ＝ ５，热核参数 ｔ 的搜索范围 为｛２ ｉ ｜ ｉ ＝ －１，０，…，８｝。 从表 １ 实验结果来看，ＰＴＳ⁃ ＶＭ 分类性能优于 ＴＷＳＶＭ，而本文 ＷＰＴＳＶＭ 则具 有更佳的分类性能。 图 ２ 复杂交叉数据集 Ｆｉｇ．２ Ｃｏｍｐｘｏｒ ｄａｔａｓｅｔ 第 ３ 期 花小朋，等：一种改进的投影孪生支持向量机 ·３８７·
·388 智能系统学报 第11卷 表13种算法在复杂交叉数据集上的分类精度(%)比较 (见表2)。显然，WPTSVM方法具有更好的测试效 Table 1 Classification comparision of three algorithms on 果，这说明本文加权措施的确能够在一定程度上提 comxor dataset 高PTSVM算法的局部学习能力。 Dataset TWSVM PTSVM WPTSVM 表23种算法在双月形数据集上的分类精度(%)比较 Table 2 Classification comparision of three algorithms on Comxor 93.76±6.70 95.67±4.73 97.36±2.90 two-moons dataset 3.2流形数据集 Dataset TWSVM PTSVM WPTSVM 数据集two-moons(如图3所示)的结构具有 two-moons 77.17±13.7276.33±12.36 78.83±8.86 明显局部流形，所以该数据集多用于测试算法的局 3.3 UCI数据集 部学习能力[2,1)。这里通过测试two-moons数据集， UCI数据集经常被用来验证算法的分类精 并与TWSVM和PTSVM方法进行比较，验证本文 度[37,1s16)。该数据集包含若干数据子集，涉及诸多 WPTSVM方法局部学习能力。 应用领域。 1.0 0 0.8 实验中选取部分数据子集，利用10-折交叉验 0 0. 04 og°g 证法测试算法分类性能。非线性算法实验中，选择 0. 08 00 高斯核exp(-‖x,-x:‖2/o)作为核函数，参数σ的 0 0 8 0 搜索范围为{21i=-1,0,…,7},其他参数搜索范围 -0.4 -0.6 同3.1节。线性模式及非线性模式下实验结果如表 -0.8 8 -1.0 3和表4分别所示。 -0.8-0.6-0.4-0.200.20.40.60.81.0 从训练时间上看：TWSVM与PTSVM相 当，WPTSVM明显比这两种算法快。原因是WPTS 图3Two-moons数据集 VM选用少量边界样本进行二次规划求解，而其他 Fig.3 Two-moons dataset 两种算法则选择异类中全部样本。 实验选择正负类样本各为50的two-moons数 从分类性能上看：本文提出的WPTSVM算法具 据集。随机抽取40%训练集和60%测试集进行实 有更好的分类能力，这也进一步佐证了本文提高 验，重复此过程10次并记录实验结果的平均值 PTSVM算法局部学习能力的措施确实有效。 表3 线性模式下3种算法的实验比较 Table 3 Experimental comparision of three algorithms on UCI datasets with linear kernel TWSVM PTSVM WPTSVM Dataset 正确率/% 训练时间/s 正确率/% 训练时间/s 正确率/% 训练时间/s Hepatitis(155x19) 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 (306x3) 74.50±2.11 4.09 74.56±7.90 5.74 75.44±5.03 1.36 Heart (270x13) 84.07±5.25 5.30 84.07±5.51 5.38 85.19±5.49 2.40 Monks2 (432x6) 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(690x14)） 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
表 １ ３ 种算法在复杂交叉数据集上的分类精度（％）比较 Ｔａｂｌｅ １ Ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｃｏｍｐａｒｉｓｉｏｎ ｏｆ ｔｈｒｅｅ ａｌｇｏｒｉｔｈｍｓ ｏｎ ｃｏｍｘｏｒ ｄａｔａｓｅｔ Ｄａｔａｓｅｔ ＴＷＳＶＭ ＰＴＳＶＭ ＷＰＴＳＶＭ Ｃｏｍｘｏｒ ９３．７６±６．７０ ９５．６７±４．７３ ９７．３６±２．９０ ３．２ 流形数据集 数据集 ｔｗｏ⁃ｍｏｏｎｓ （如图 ３ 所示） 的结构具有 明显局部流形，所以该数据集多用于测试算法的局 部学习能力［２，１３］ 。 这里通过测试 ｔｗｏ⁃ｍｏｏｎｓ 数据集， 并与 ＴＷＳＶＭ 和 ＰＴＳＶＭ 方法进行比较，验证本文 ＷＰＴＳＶＭ 方法局部学习能力。 图 ３ Ｔｗｏ⁃ｍｏｏｎｓ 数据集 Ｆｉｇ．３ Ｔｗｏ⁃ｍｏｏｎｓ ｄａｔａｓｅｔ 实验选择正负类样本各为 ５０ 的 ｔｗｏ⁃ｍｏｏｎｓ 数 据集。 随机抽取 ４０％训练集和 ６０％测试集进行实 验，重复此过程 １０ 次并记录实验结果的平均值 （见表 ２）。 显然，ＷＰＴＳＶＭ 方法具有更好的测试效 果，这说明本文加权措施的确能够在一定程度上提 高 ＰＴＳＶＭ 算法的局部学习能力。 表 ２ ３ 种算法在双月形数据集上的分类精度（％）比较 Ｔａｂｌｅ ２ Ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｃｏｍｐａｒｉｓｉｏｎ ｏｆ ｔｈｒｅｅ ａｌｇｏｒｉｔｈｍｓ ｏｎ ｔｗｏ⁃ｍｏｏｎｓ ｄａｔａｓｅｔ Ｄａｔａｓｅｔ ＴＷＳＶＭ ＰＴＳＶＭ ＷＰＴＳＶＭ ｔｗｏ⁃ｍｏｏｎｓ ７７．１７±１３．７２ ７６．３３±１２．３６ ７８．８３±８．８６ ３．３ ＵＣＩ 数据集 ＵＣＩ 数据集经常被用来验 证 算 法 的 分 类 精 度［３⁃７，１５⁃１６］ 。 该数据集包含若干数据子集，涉及诸多 应用领域。 实验中选取部分数据子集，利用 １０－折交叉验 证法测试算法分类性能。 非线性算法实验中，选择 高斯核 ｅｘｐ（－‖ｘｉ －ｘｊ‖２ ／ σ）作为核函数，参数 σ 的 搜索范围为｛２ ｉ ｜ ｉ ＝ －１，０， …，７｝，其他参数搜索范围 同 ３．１ 节。 线性模式及非线性模式下实验结果如表 ３ 和表 ４ 分别所示。 从训练时间上看： ＴＷＳＶＭ 与 ＰＴＳＶＭ 相 当，ＷＰＴＳＶＭ 明显比这两种算法快。 原因是 ＷＰＴＳ⁃ ＶＭ 选用少量边界样本进行二次规划求解，而其他 两种算法则选择异类中全部样本。 从分类性能上看：本文提出的 ＷＰＴＳＶＭ 算法具 有更好的分类能力，这也进一步佐证了本文提高 ＰＴＳＶＭ 算法局部学习能力的措施确实有效。 表 ３ 线性模式下 ３ 种算法的实验比较 Ｔａｂｌｅ ３ Ｅｘｐｅｒｉｍｅｎｔａｌ ｃｏｍｐａｒｉｓｉｏｎ ｏｆ ｔｈｒｅｅ ａｌｇｏｒｉｔｈｍｓ ｏｎ ＵＣＩ ｄａｔａｓｅｔｓ ｗｉｔｈ ｌｉｎｅａｒ ｋｅｒｎｅｌ Ｄａｔａｓｅｔ ＴＷＳＶＭ ＰＴＳＶＭ ＷＰＴＳＶＭ 正确率／ ％ 训练时间／ ｓ 正确率／ ％ 训练时间／ ｓ 正确率／ ％ 训练时间／ ｓ Ｈｅｐａｔｉｔｉｓ（１５５×１９） ８４．１７±７．７９ ３．８４ ８３．６７±１０．８０ ３．４６ ８７．３３±９．１７ １．３６ Ｃｌｅｖｅ （２９６×１３） ８２．４２±４．２１ ５．４０ ８２．０８±３．３８ ５．２６ ８３．４６±３．７１ ２．５６ Ｓｏｎａｒ （２０８×６０） ６６．００±１６．８５ ３．９３ ６６．３６±１４．２７ ３．８２ ６８．０７±１３．６０ １．５８ Ｂｕｐａ＿ｌｉｖｅｒ（３４５×６） ６８．６９±３．２３ ２．４２ ６７．５９±５．３０ ２．８４ ７０．２０±６．４２ ２．１７ Ｗｄｂｃ （５６９×３０） ９６．９９±１．６３ １９．７７ ９６．９９±１．６３ １９．９５ ９７．５３±１．６５ １．１４ Ｈａｂｅｒｍａｎ （３０６×３） ７４．５０±２．１１ ４．０９ ７４．５６±７．９０ ５．７４ ７５．４４±５．０３ １．３６ Ｈｅａｒｔ （２７０×１３） ８４．０７±５．２５ ５．３０ ８４．０７±５．５１ ５．３８ ８５．１９±５．４９ ２．４０ Ｍｏｎｋｓ２ （４３２×６） ６７．１４±４．９８ ２．８４ ６７．８４±３．１５ ２．５６ ６７．１３±３．２０ ０．７８ Ｍｏｎｋｓ３ （４３２×６） ７７．４１±１１．３２ ６．０７ ８０．７４±１３．０５ ６．３２ ８１．６９±１２．８５ ３．７６ Ａｕｓｔｒａｌｉａｎ（６９０×１４） ８６．２６±４．７６ １３．３７ ８６．２８±４．９１ １１．９０ ８６．８３±５．２５ ２．８１ Ｐｉｍａ＿ｉｎｄｉａ（７６８×８） ７７．１７±２．８０ ４０．９１ ７６．４１±３．５３ ４２．８１ ７６．７９±４．０５ １０．２５ Ｔｉｃ＿ｔａｃ＿ｔｏｅ（９５８×９） ６４．９３±２．３１ １８．０７ ６３．１１±５．３３ １８．２１ ７８．７２±６．１３ ６．２４ ·３８８· 智 能 系 统 学 报 第 １１ 卷
第3期 花小朋，等：一种改进的投影孪生支持向量机 .389. 表4非线性模式下3种算法的实验比较 Table 4 Experimental comparision of three algorithms on UCI datasets with nonlinear kernel TWSVM PTSVM WPTSVM Dataset 正确率/% 训练时间/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 (296x13) 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 (267x22) 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 (310x6) 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 结束语 [5]MANGASARIAN O L,WILD E W.MultisurFace proximal support vector machine classification via generalized eigen- 本文基于投影孪生支持向量机(PTSVM)提出一 values [J].IEEE transactions on pattern analysis and ma- chine intelligence,2006,28 (1):69-74. 种新的的非平行超平面分类器方法：加权投影孪生支 [6]PENG Xinjun,XU Dong.Bi-density twin support vector ma- 持向量机(WPTSVM)。WPTSVM不仅继承了PTS chines for pattern recognition[J].Neurocomputing,2013, VM方法的优点，而且在一定程度上提高了算法局部 99:134-143. 学习能力。除此之外，WPTSVM通过类间近邻图选 [7]CHEN Xiaobo,YANG Jian,YE Qiaolin,et al.Recursive 择少量边界样本构造优化问题约束条件，相当程度上 projection twin support vector machine via within-class vari- ance minimization[J].Pattern recognition,2011,44 (10/ 降低了二次规划求解时间复杂度。理论分析及实验 11):2643-2655. 结果均验证了本文所提算法的有效性。诚然，WPTS- [8 ]SHAO Yuanhai,WANG Zhen,CHEN Weijie,et al.A reg- VM在构造类内及类间近邻图时，需要花费额外的计 ularization 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.Proxi- mal support vector machine using local information [J]. 参考文献： Neurocomputing,2009,73(1):357-365. [10]COVER T M,HART P E.Nearest neighbor pattern classi- [1]皋军，王士同，邓赵红.基于全局和局部保持的半监督 fication [J ]IEEE transactions on information theory, 支持向量机[J].电子学报，2010,38(7)：1626-1633. 1967,13(1):21-27. GAO Jun,WANG Shitong,DENG Zhaohong.Global and local [11]WANG Xiaoming,CHUNG Fulai,WANG Shitong.On preserving based semi-supervised support vector machine minimum class locality preserving variance support vector [J].Acta electronica sinica,2010,38(7):1626-1633. machine[J].Patter recognition,2010,43(8):2753- [2]花小朋，丁世飞.局部保持对支持向量机[J].计算机研 2762. 究与发展，2014,51(3)：590-597. [12]YE Qiaolin,ZhAO Chunxia,YE Ning,et al.Localized HUAxiaopeng,DING Shifei.Locality preserving twin sup- twin svm via convex minimization[J].Neurocomputing, port vector machines [J].Journal of computer research and 2011.74(4):580-587. development,2014,51(3):590-597. [13]皋军，黄丽莉，王士同.基于局部子域的最大间距判别 [3]DING Shifei,HUA Xiaopeng,YU Junzhao.An overview on 分析[J].控制与决策，2014,29(5)：827-832. nonparallel hyperplane support vector machines[J].Neural GAO Jun,HUANG Lili,WANG Shitong.Local sub-do- computing and applications,2014,25(5):975-982. mains based maximum margin criterion [J].Control and [4]JAYADEVA,KHEMCHAND R,CHANDRA S.Twin sup- decision,2014,29(5):827-832. port vector machines for pattern classification [J].IEEE [14]邓乃杨，田英杰.支持向量机一理论、算法与拓展[M] transaction on pattern analysis and machine intelligence, 北京：科学出版社，2009：164-223. 2007,29(5):905-910. [l5]丁立中，廖士中.KMA-a:一个支持向量机核矩阵的近
表 ４ 非线性模式下 ３ 种算法的实验比较 Ｔａｂｌｅ ４ Ｅｘｐｅｒｉｍｅｎｔａｌ ｃｏｍｐａｒｉｓｉｏｎ ｏｆ ｔｈｒｅｅ ａｌｇｏｒｉｔｈｍｓ ｏｎ ＵＣＩ ｄａｔａｓｅｔｓ ｗｉｔｈ ｎｏｎｌｉｎｅａｒ ｋｅｒｎｅｌ Ｄａｔａｓｅｔ ＴＷＳＶＭ ＰＴＳＶＭ ＷＰＴＳＶＭ 正确率／ ％ 训练时间／ ｓ 正确率／ ％ 训练时间／ ｓ 正确率／ ％ 训练时间／ ｓ Ｓｐｅｃｔｆ （２６７×４６） ８３．４３±７．１５ １４．６３ ８２．４９±８．３６ １４．６５ ８４．０３±５．１７ １．７３ Ｃｌｅｖｅ （２９６×１３） ８５．１２±５．７７ ７．２２ ８５．９３±４．９０ ７．８２ ８５．２４±４．５６ ３．４０ Ｗｐｂｃ （１９８×３３） ７９．３６±５．５２ ４．１２ ７８．０３±６．５９ １．７２ ７９．９８±６．６２ ０．５９ Ｐ＿ｇｅｎｅ （１０６×５７） ６５．５０±１８．２３ ２．２５ ６４．１３±２１．１７ ２．２２ ６８．１３±１６．７１ １．１９ Ｓｏｎａｒ （２０８×６０） ６３．２９±１８．６５ ７．５５ ６４．５０±１３．５０ ８．６３ ６８．４３±１３．２６ ２．７８ Ｓｐｅｃｔ （２６７×２２） ８４．４２±９．０４ １１．４２ ８４．４２±７．４３ ４．０１ ８４．８０±８．２７ ５．５４ Ｍｏｎｋｓ２ （４３２×６） ６８．７７±１５．２４ ５．０２ ６８．７１±３．４３ ６．４３ ６８．９９±１１．０７ ４．５７ Ｖｅｒｔｅｂｒａｌ （３１０×６） ８５．８１±６．３２ ５．６３ ８４．５２±６．４２ ６．０２ ８６．１３±６．４６ ２．８７ Ｍｏｎｋｓ３ （４３２×６） ９８．７０±３．８９ １１．０９ ９８．５２±４．４４ ９．９７ ９９．２６±２．２２ ８．０３ Ｂｒｅａｓｔ＿ｇｙ（２７７×９） ７５．８６±５．８９ ５．２４ ７３．５７±４．１０ ４．０４ ７５．９４±６．６９ ０．８７ ４ 结束语 本文基于投影孪生支持向量机（ＰＴＳＶＭ ）提出一 种新的的非平行超平面分类器方法：加权投影孪生支 持向量机（ＷＰＴＳＶＭ ）。 ＷＰＴＳＶＭ 不仅继承了 ＰＴＳ⁃ ＶＭ 方法的优点，而且在一定程度上提高了算法局部 学习能力。 除此之外，ＷＰＴＳＶＭ 通过类间近邻图选 择少量边界样本构造优化问题约束条件，相当程度上 降低了二次规划求解时间复杂度。 理论分析及实验 结果均验证了本文所提算法的有效性。 诚然，ＷＰＴＳ⁃ ＶＭ 在构造类内及类间近邻图时，需要花费额外的计 算开销，特别是在学习样本数目较大时，算法计算复 杂度会偏高，这也是今后进一步研究的目标。 参考文献： ［１］皋军， 王士同， 邓赵红． 基于全局和局部保持的半监督 支持向量机［Ｊ］． 电子学报， ２０１０， ３８（７）： １６２６⁃１６３３． ＧＡＯ Ｊｕｎ， ＷＡＮＧ Ｓｈｉｔｏｎｇ， ＤＥＮＧ Ｚｈａｏｈｏｎｇ． Ｇｌｏｂａｌ ａｎｄ ｌｏｃａｌ ｐｒｅｓｅｒｖｉｎｇ ｂａｓｅｄ ｓｅｍｉ⁃ｓｕｐｅｒｖｉｓｅｄ ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅ ［Ｊ］． Ａｃｔａ ｅｌｅｃｔｒｏｎｉｃａ ｓｉｎｉｃａ， ２０１０， ３８（７）： １６２６⁃１６３３． ［２］花小朋， 丁世飞． 局部保持对支持向量机［ Ｊ］． 计算机研 究与发展， ２０１４， ５１（３）： ５９０⁃５９７． ＨＵＡｘｉａｏｐｅｎｇ， ＤＩＮＧ Ｓｈｉｆｅｉ． Ｌｏｃａｌｉｔｙ ｐｒｅｓｅｒｖｉｎｇ ｔｗｉｎ ｓｕｐ⁃ ｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅｓ ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｃｏｍｐｕｔｅｒ ｒｅｓｅａｒｃｈ ａｎｄ ｄｅｖｅｌｏｐｍｅｎｔ， ２０１４， ５１（３）： ５９０⁃５９７． ［３］ＤＩＮＧ Ｓｈｉｆｅｉ， ＨＵＡ Ｘｉａｏｐｅｎｇ， ＹＵ Ｊｕｎｚｈａｏ． Ａｎ ｏｖｅｒｖｉｅｗ ｏｎ ｎｏｎｐａｒａｌｌｅｌ ｈｙｐｅｒｐｌａｎｅ ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅｓ［ Ｊ］． Ｎｅｕｒａｌ ｃｏｍｐｕｔｉｎｇ ａｎｄ ａｐｐｌｉｃａｔｉｏｎｓ， ２０１４， ２５（５）： ９７５⁃９８２． ［４］ＪＡＹＡＤＥＶＡ， ＫＨＥＭＣＨＡＮＤ Ｒ， ＣＨＡＮＤＲＡ Ｓ． Ｔｗｉｎ ｓｕｐ⁃ ｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅｓ ｆｏｒ ｐａｔｔｅｒｎ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ［ Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎ ｏｎ ｐａｔｔｅｒｎ ａｎａｌｙｓｉｓ ａｎｄ ｍａｃｈｉｎｅ ｉｎｔｅｌｌｉｇｅｎｃｅ， ２００７， ２９ （５）： ９０５⁃９１０． ［５］ ＭＡＮＧＡＳＡＲＩＡＮ Ｏ Ｌ， ＷＩＬＤ Ｅ Ｗ． ＭｕｌｔｉｓｕｒＦａｃｅ ｐｒｏｘｉｍａｌ ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｖｉａ ｇｅｎｅｒａｌｉｚｅｄ ｅｉｇｅｎ⁃ ｖａｌｕｅｓ ［ Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｐａｔｔｅｒｎ ａｎａｌｙｓｉｓ ａｎｄ ｍａ⁃ ｃｈｉｎｅ ｉｎｔｅｌｌｉｇｅｎｃｅ， ２００６， ２８ （１）： ６９⁃７４． ［６］ＰＥＮＧ Ｘｉｎｊｕｎ，ＸＵ Ｄｏｎｇ． Ｂｉ－ｄｅｎｓｉｔｙ ｔｗｉｎ ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａ⁃ ｃｈｉｎｅｓ ｆｏｒ ｐａｔｔｅｒｎ ｒｅｃｏｇｎｉｔｉｏｎ［ Ｊ］． Ｎｅｕｒｏｃｏｍｐｕｔｉｎｇ， ２０１３， ９９： １３４⁃１４３． ［７］ ＣＨＥＮ Ｘｉａｏｂｏ， ＹＡＮＧ Ｊｉａｎ， ＹＥ Ｑｉａｏｌｉｎ， ｅｔ ａｌ． Ｒｅｃｕｒｓｉｖｅ ｐｒｏｊｅｃｔｉｏｎ ｔｗｉｎ ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅ ｖｉａ ｗｉｔｈｉｎ⁃ｃｌａｓｓ ｖａｒｉ⁃ ａｎｃｅ ｍｉｎｉｍｉｚａｔｉｏｎ［Ｊ］． Ｐａｔｔｅｒｎ ｒｅｃｏｇｎｉｔｉｏｎ， ２０１１， ４４ （１０ ／ １１）： ２６４３⁃２６５５． ［８］ＳＨＡＯ Ｙｕａｎｈａｉ， ＷＡＮＧ Ｚｈｅｎ， ＣＨＥＮ Ｗｅｉｊｉｅ， ｅｔ ａｌ． Ａ ｒｅｇ⁃ ｕｌａｒｉｚａｔｉｏｎ ｆｏｒ ｔｈｅ ｐｒｏｊｅｃｔｉｏｎ ｔｗｉｎ ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅ ［Ｊ］． Ｋｎｏｗｌｅｄｇｅ⁃ｂａｓｅｄ ｓｙｓｔｅｍｓ， ２０１３， ３７ （１）： ２０３⁃２１０． ［９］ＹＡＮＧ Ｘｕｂｉｎｇ， ＣＨＥＮ Ｓｏｎｇｃａｎ， ＣＨＥＮ Ｂｉｎ， ｅｔ ａｌ． Ｐｒｏｘｉ⁃ ｍａｌ ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅ ｕｓｉｎｇ ｌｏｃａｌ ｉｎｆｏｒｍａｔｉｏｎ ［ Ｊ］． Ｎｅｕｒｏｃｏｍｐｕｔｉｎｇ， ２００９， ７３（１）： ３５７⁃３６５． ［１０］ＣＯＶＥＲ Ｔ Ｍ， ＨＡＲＴ Ｐ Ｅ． Ｎｅａｒｅｓｔ ｎｅｉｇｈｂｏｒ ｐａｔｔｅｒｎ ｃｌａｓｓｉ⁃ ｆｉｃａｔｉｏｎ ［ Ｊ ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｆｏｒｍａｔｉｏｎ ｔｈｅｏｒｙ， １９６７， １３ （１）： ２１⁃２７． ［１１］ ＷＡＮＧ Ｘｉａｏｍｉｎｇ， ＣＨＵＮＧ Ｆｕｌａｉ， ＷＡＮＧ Ｓｈｉｔｏｎｇ． Ｏｎ ｍｉｎｉｍｕｍ ｃｌａｓｓ ｌｏｃａｌｉｔｙ ｐｒｅｓｅｒｖｉｎｇ ｖａｒｉａｎｃｅ ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅ［ Ｊ］． Ｐａｔｔｅｒ ｒｅｃｏｇｎｉｔｉｏｎ， ２０１０， ４３ （ ８）： ２７５３⁃ ２７６２． ［１２］ ＹＥ Ｑｉａｏｌｉｎ， ＺｈＡＯ Ｃｈｕｎｘｉａ， ＹＥ Ｎｉｎｇ， ｅｔ ａｌ． Ｌｏｃａｌｉｚｅｄ ｔｗｉｎ ｓｖｍ ｖｉａ ｃｏｎｖｅｘ ｍｉｎｉｍｉｚａｔｉｏｎ ［ Ｊ］． Ｎｅｕｒｏｃｏｍｐｕｔｉｎｇ， ２０１１， ７４（４）： ５８０⁃５８７． ［１３］皋军， 黄丽莉， 王士同． 基于局部子域的最大间距判别 分析 ［Ｊ ］． 控制与决策， ２０１４， ２９ （５）： ８２７⁃８３２． ＧＡＯ Ｊｕｎ， ＨＵＡＮＧ Ｌｉｌｉ， ＷＡＮＧ Ｓｈｉｔｏｎｇ． Ｌｏｃａｌ ｓｕｂ －ｄｏ⁃ ｍａｉｎｓ ｂａｓｅｄ ｍａｘｉｍｕｍ ｍａｒｇｉｎ ｃｒｉｔｅｒｉｏｎ ［ Ｊ］． Ｃｏｎｔｒｏｌ ａｎｄ ｄｅｃｉｓｉｏｎ， ２０１４， ２９ （５）： ８２７⁃８３２． ［１４］邓乃杨， 田英杰． 支持向量机—理论、算法与拓展［Ｍ］． 北京： 科学出版社， ２００９： １６４⁃２２３． ［１５］丁立中， 廖士中． ＫＭＡ－ａ： 一个支持向量机核矩阵的近 第 ３ 期 花小朋，等：一种改进的投影孪生支持向量机 ·３８９·
.390. 智能系统学报 第11卷 似计算算法[J].计算机研究与发展，2012,49(4)： 孙一颗，男，1993年生，硕士研究生，主 746-753. 要研究方向为机器学习、数据挖掘，申 DING Lizhong,LIAO Shizhong.KMA-a:a kernel matrix 请发明专利2项。 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. 丁世飞，男，1963年生，教授，博士 作者简介： 生导师，中国计算机学会高级会员，中 花小朋，男，1975年生，副教授，博 国人工智能学会高级会员，江苏省计算 士，主要研究方向为机器学习与数据挖 机学会人工智能专业委员会委员，主要 掘，发表学术论文10余篇。 研究方向为智能信息处理，目前主持国 家973项目1项、国家自然科学基金项目1项，发表学术论 文60余篇。 2016年第9届FAC智能自主车辆研讨会 2016 9th IFAC Symposium on Intelligent Autonomous Vehicles (IAV) The Symposium targets topics in the field of intelligent autonomous vehicles (IAV).It presents methods and representative tech- niques to either solve typical problems or to document successful test cases and applications.The addressed modality of the vehicles may range from land,sea and air to space and they may be designed as multi vehicle systems in swarms or networked platoons as well as indi- vidual carriers. The covered key topics will include (but will not be limited to): 1)Architectures for autonomous vehicles and teams of IAVs; 2)Perception including sensing,sensor integration,smart sensors and sensor networks; 3)Recognition; 4)Decision support systems,driver support systems,Advanced driver assistance systems; 5)Planning and mission control; 6)Local and global roadmap planning,trajectory tracking and path following; 7)Localization including SLAM and map building; 8)Navigation,guidance and control,motion control,controller design,stability analysis; 9)Human vehicle interaction; 10)Transportation systems; 11)Remote control,monitoring and teleoperation; 12)Fault detection,diagnosis and removal in IAVs and systems; 13)Domestic robots,service and rehabilitation robots; 14)Field robotics,maritime and ocean robots: 15)Networked IAVs: 16)Swarm robotics; 17)Communication and cooperation for teams for IAVs. Website:http://iav2016.inf.h-brs.de/
似计算算法［ Ｊ］． 计算机研究与发展， ２０１２， ４９ （ ４）： ７４６⁃７５３． ＤＩＮＧ Ｌｉｚｈｏｎｇ， ＬＩＡＯ Ｓｈｉｚｈｏｎｇ． ＫＭＡ－ａ： ａ ｋｅｒｎｅｌ ｍａｔｒｉｘ ａｐｐｒｏｘｉｍａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅｓ ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｃｏｍｐｕｔｅｒ ｒｅｓｅａｒｃｈ ａｎｄ ｄｅｖｅｌｏｐｍｅｎｔ， ２０１２， ４９ （４）： ７４６⁃７５３． ［１６］ＸＵＥ Ｈｕｉ， ＣＨＥＮ Ｓｏｎｇｃｈａｎ． Ｇｌｏｃａｌｉｚａｔｉｏｎ ｐｕｒｓｕｉｔ ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅ ［ Ｊ］． Ｎｅｕｒａｌ ｃｏｍｐｕｔｉｎｇ ａｎｄ ａｐｐｌｉｃａｔｉｏｎｓ， ２０１１， ２０（７）：１０４３⁃１０５３． 作者简介： 花小朋，男，１９７５ 年生，副教授，博 士，主要研究方向为机器学习与数据挖 掘，发表学术论文 １０ 余篇。 孙一颗，男，１９９３ 年生，硕士研究生，主 要研究方向为机器学习、数据挖掘，申 请发明专利 ２ 项。 丁世飞，男，１９６３ 年生，教授，博士 生导师，中国计算机学会高级会员，中 国人工智能学会高级会员，江苏省计算 机学会人工智能专业委员会委员，主要 研究方向为智能信息处理，目前主持国 家 ９７３ 项目 １ 项、国家自然科学基金项目 １ 项，发表学术论 文 ６０ 余篇。 ２０１６ 年第 ９ 届 ＩＦＡＣ 智能自主车辆研讨会 ２０１６ ９ｔｈ ＩＦＡＣ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ａｕｔｏｎｏｍｏｕｓ Ｖｅｈｉｃｌｅｓ （ＩＡＶ） Ｔｈｅ Ｓｙｍｐｏｓｉｕｍ ｔａｒｇｅｔｓ ｔｏｐｉｃｓ ｉｎ ｔｈｅ ｆｉｅｌｄ ｏｆ ｉｎｔｅｌｌｉｇｅｎｔ ａｕｔｏｎｏｍｏｕｓ ｖｅｈｉｃｌｅｓ （ ＩＡＶ）． Ｉｔ ｐｒｅｓｅｎｔｓ ｍｅｔｈｏｄｓ ａｎｄ ｒｅｐｒｅｓｅｎｔａｔｉｖｅ ｔｅｃｈ⁃ ｎｉｑｕｅｓ ｔｏ ｅｉｔｈｅｒ ｓｏｌｖｅ ｔｙｐｉｃａｌ ｐｒｏｂｌｅｍｓ ｏｒ ｔｏ ｄｏｃｕｍｅｎｔ ｓｕｃｃｅｓｓｆｕｌ ｔｅｓｔ ｃａｓｅｓ ａｎｄ ａｐｐｌｉｃａｔｉｏｎｓ． Ｔｈｅ ａｄｄｒｅｓｓｅｄ ｍｏｄａｌｉｔｙ ｏｆ ｔｈｅ ｖｅｈｉｃｌｅｓ ｍａｙ ｒａｎｇｅ ｆｒｏｍ ｌａｎｄ， ｓｅａ ａｎｄ ａｉｒ ｔｏ ｓｐａｃｅ ａｎｄ ｔｈｅｙ ｍａｙ ｂｅ ｄｅｓｉｇｎｅｄ ａｓ ｍｕｌｔｉ ｖｅｈｉｃｌｅ ｓｙｓｔｅｍｓ ｉｎ ｓｗａｒｍｓ ｏｒ ｎｅｔｗｏｒｋｅｄ ｐｌａｔｏｏｎｓ ａｓ ｗｅｌｌ ａｓ ｉｎｄｉ⁃ ｖｉｄｕａｌ ｃａｒｒｉｅｒｓ． Ｔｈｅ ｃｏｖｅｒｅｄ ｋｅｙ ｔｏｐｉｃｓ ｗｉｌｌ ｉｎｃｌｕｄｅ （ｂｕｔ ｗｉｌｌ ｎｏｔ ｂｅ ｌｉｍｉｔｅｄ ｔｏ）： １）Ａｒｃｈｉｔｅｃｔｕｒｅｓ ｆｏｒ ａｕｔｏｎｏｍｏｕｓ ｖｅｈｉｃｌｅｓ ａｎｄ ｔｅａｍｓ ｏｆ ＩＡＶｓ； ２）Ｐｅｒｃｅｐｔｉｏｎ ｉｎｃｌｕｄｉｎｇ ｓｅｎｓｉｎｇ， ｓｅｎｓｏｒ ｉｎｔｅｇｒａｔｉｏｎ， ｓｍａｒｔ ｓｅｎｓｏｒｓ ａｎｄ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ； ３）Ｒｅｃｏｇｎｉｔｉｏｎ； ４）Ｄｅｃｉｓｉｏｎ ｓｕｐｐｏｒｔ ｓｙｓｔｅｍｓ， ｄｒｉｖｅｒ ｓｕｐｐｏｒｔ ｓｙｓｔｅｍｓ， Ａｄｖａｎｃｅｄ ｄｒｉｖｅｒ ａｓｓｉｓｔａｎｃｅ ｓｙｓｔｅｍｓ； ５）Ｐｌａｎｎｉｎｇ ａｎｄ ｍｉｓｓｉｏｎ ｃｏｎｔｒｏｌ； ６）Ｌｏｃａｌ ａｎｄ ｇｌｏｂａｌ ｒｏａｄｍａｐ ｐｌａｎｎｉｎｇ， ｔｒａｊｅｃｔｏｒｙ ｔｒａｃｋｉｎｇ ａｎｄ ｐａｔｈ ｆｏｌｌｏｗｉｎｇ； ７）Ｌｏｃａｌｉｚａｔｉｏｎ ｉｎｃｌｕｄｉｎｇ ＳＬＡＭ ａｎｄ ｍａｐ ｂｕｉｌｄｉｎｇ； ８）Ｎａｖｉｇａｔｉｏｎ， ｇｕｉｄａｎｃｅ ａｎｄ ｃｏｎｔｒｏｌ， ｍｏｔｉｏｎ ｃｏｎｔｒｏｌ， ｃｏｎｔｒｏｌｌｅｒ ｄｅｓｉｇｎ， ｓｔａｂｉｌｉｔｙ ａｎａｌｙｓｉｓ； ９）Ｈｕｍａｎ ｖｅｈｉｃｌｅ ｉｎｔｅｒａｃｔｉｏｎ； １０）Ｔｒａｎｓｐｏｒｔａｔｉｏｎ ｓｙｓｔｅｍｓ； １１）Ｒｅｍｏｔｅ ｃｏｎｔｒｏｌ， ｍｏｎｉｔｏｒｉｎｇ ａｎｄ ｔｅｌｅｏｐｅｒａｔｉｏｎ； １２）Ｆａｕｌｔ ｄｅｔｅｃｔｉｏｎ， ｄｉａｇｎｏｓｉｓ ａｎｄ ｒｅｍｏｖａｌ ｉｎ ＩＡＶｓ ａｎｄ ｓｙｓｔｅｍｓ； １３）Ｄｏｍｅｓｔｉｃ ｒｏｂｏｔｓ， ｓｅｒｖｉｃｅ ａｎｄ ｒｅｈａｂｉｌｉｔａｔｉｏｎ ｒｏｂｏｔｓ； １４）Ｆｉｅｌｄ ｒｏｂｏｔｉｃｓ， ｍａｒｉｔｉｍｅ ａｎｄ ｏｃｅａｎ ｒｏｂｏｔｓ； １５）Ｎｅｔｗｏｒｋｅｄ ＩＡＶｓ； １６）Ｓｗａｒｍ ｒｏｂｏｔｉｃｓ； １７）Ｃｏｍｍｕｎｉｃａｔｉｏｎ ａｎｄ ｃｏｏｐｅｒａｔｉｏｎ ｆｏｒ ｔｅａｍｓ ｆｏｒ ＩＡＶｓ． Ｗｅｂｓｉｔｅ： ｈｔｔｐ：／ ／ ｉａｖ２０１６．ｉｎｆ．ｈ⁃ｂｒｓ．ｄｅ ／ ·３９０· 智 能 系 统 学 报 第 １１ 卷