第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第 １１ 卷第 ３ 期 智 能 系 统 学 报 Ｖｏｌ．１１ №．３ ２０１６ 年 ６ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｊｕｎ． ２０１６ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１６０３０． 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１６０５１３．０９２４．０２４．ｈｔｍｌ 一种改进的投影孪生支持向量机 花小朋１ ，孙一颗１ ，丁世飞２ （１．盐城工学院 信息工程学院，江苏 盐城 ２２４０５１； ２． 中国矿业大学 计算机学院，江苏 徐州 ２２１１１６） 摘 要：针对投影孪生支持向量机（ＰＴＳＶＭ）在训练阶段欠考虑样本空间局部结构和局部信息的缺陷，提出一种具有 一定局部学习能力的有监督分类方法：加权投影孪生支持向量机（ｗｅｉｇｈｔｅｄ ＰＴＳＶＭ，ＷＰＴＳＶＭ）。 相比于 ＰＴＳＶＭ， ＷＰＴＳＶＭ 优势在于：通过构造类内近邻图为每个样本获取特定的权值，并且以加权均值取代标准均值，在一定程度 上提高了算法的局部学习能力；选取异类样本集中少量边界点构造优化问题的约束条件，很大程度上降低了二次规 划求解的时间复杂度；继承了 ＰＴＳＶＭ 的优点，可以看成 ＰＴＳＶＭ 的推广算法。 理论分析及其在人造数据集和真实数 据集上的测试结果表明该方法具有上述优势。 关键词：分类；投影孪生支持向量机；局部信息；加权均值；近邻图；二次规划；约束条件；时间复杂度 中图分类号：ＴＰ３９１．４ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１６）０３⁃０３８４⁃０６ 中文引用格式：花小朋，孙一颗，丁世飞．一种改进的投影孪生支持向量机［Ｊ］． 智能系统学报， ２０１６， １１（３）： ３８４⁃３９１． 英文引用格式：ＨＵＡ Ｘｉａｏｐｅｎｇ， ＳＵＮ Ｙｉｋｅ， ＤＩＮＧ Ｓｈｉｆｅｉ． Ａｎ ｉｍｐｒｏｖｅｄ ｐｒｏｊｅｃｔｉｏｎ ｔｗｉｎ ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅ［Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃ⁃ ｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１６， １１（３）： ３８４⁃３９１． Ａｎ ｉｍｐｒｏｖｅｄ ｐｒｏｊｅｃｔｉｏｎ ｔｗｉｎ ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅ ＨＵＡ Ｘｉａｏｐｅｎｇ １ ， ＳＵＮ Ｙｉｋｅ １ ， ＤＩＮＧ Ｓｈｉｆｅｉ ２ （１． Ｓｃｈｏｏｌ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｙａｎｃｈｅｎｇ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ， Ｙａｎｃｈｅｎｇ ２２４０５１， Ｃｈｉｎａ； ２． Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， Ｃｈｉｎａ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｍｉｎｉｎｇ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， Ｘｕｚｈｏｕ ２２１１１６， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ａ ｓｕｐｅｒｖｉｓｅｄ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｍｅｔｈｏｄ ｈａｖｉｎｇ ａ ｌｏｃａｌ ｌｅａｒｎｉｎｇ ａｂｉｌｉｔｙ， ｃａｌｌｅｄ ｗｅｉｇｈｔｅｄ ｐｒｏｊｅｃｔｉｏｎ ｔｗｉｎ ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅ （ＷＰＴＳＶＭ）， ｉｓ ｐｒｏｐｏｓｅｄ． Ｔｈｉｓ ｍｅｔｈｏｄ ａｉｍｓ ｔｏ ｉｍｐｒｏｖｅ ｕｐｏｎ ａ ｄｅｆｅｃｔ ｔｈａｔ ｐｒｏｊｅｃｔｉｏｎ ｔｗｉｎ ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅｓ （ＰＴＳＶＭｓ） ｈａｖｅ， ｎａｍｅｌｙ， ｔｈａｔ ＰＴＳＶＭｓ ｄｏ ｎｏｔ ｔａｋｅ ａｃｃｏｕｎｔ ｏｆ ｔｈｅ ｌｏｃａｌ ｓｔｒｕｃｔｕｒｅ ａｎｄ ｌｏｃａｌ ｉｎｆｏｒ⁃ ｍａｔｉｏｎ ｏｆ ａ ｓａｍｐｌｅ ｓｐａｃｅ ｉｎ ｔｈｅ ｔｒａｉｎｉｎｇ ｐｒｏｃｅｓｓ． Ｃｏｍｐａｒｅｄ ｗｉｔｈ ＰＴＳＶＭ， ＷＰＴＳＶＭ ｉｍｐｒｏｖｅｓ ｉｔｓ ｌｏｃａｌ ｌｅａｒｎｉｎｇ ａ⁃ ｂｉｌｉｔｙ ｔｏ ｓｏｍｅ ｅｘｔｅｎｔ ｂｙ ａｔｔａｃｈｉｎｇ ｄｉｆｆｅｒｅｎｔ ｗｅｉｇｈｔｓ ｆｏｒ ｅａｃｈ ｓａｍｐｌｅ ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ｗｉｔｈｉｎ⁃ｃｌａｓｓ ｎｅｉｇｈｂｏｒｈｏｏｄ ｇｒａｐｈ ａｎｄ ｒｅｐｌａｃｉｎｇ ｔｈｅ ｓｔａｎｄａｒｄ ｍｅａｎ ｗｉｔｈ ａ ｗｅｉｇｈｔｅｄ ｍｅａｎ． Ｍｏｒｅｏｖｅｒ， ｔｏ ｒｅｄｕｃｅ ｃｏｍｐｕｔａｔｉｏｎａｌ ｃｏｍｐｌｅｘｉｔｙ， ＷＰＴＳＶＭ ｃｈｏｏｓｅｓ ａ ｓｍａｌｌ ｎｕｍｂｅｒ ｏｆ ｂｏｕｎｄａｒｙ ｐｏｉｎｔｓ ｉｎ ｔｈｅ ｃｏｎｔｒａｒｙ⁃ｃｌａｓｓ ｂａｓｅｄ ｏｎ ｔｈｅ ｂｅｔｗｅｅｎ－ｃｌａｓｓ ｎｅｉｇｈｂｏｒｈｏｏｄ ｇｒａｐｈ ｔｏ ｃｏｎｓｔｒｕｃｔ ｃｏｎｓｔｒａｉｎｔｓ ｏｆ ｔｈｅ ｏｒｉｇｉｎａｌ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍｓ． Ｔｈｅ ｍｅｔｈｏｄ ｉｎｈｅｒｉｔｓ ｔｈｅ ｍｅｒｉｔｓ ｏｆ ＰＴＳＶＭ ａｎｄ ｃａｎ ｂｅ ｒｅ⁃ ｇａｒｄｅｄ ａｓ ａｎ ｉｍｐｒｏｖｅｄ ｖｅｒｓｉｏｎ ｏｆ ＰＴＳＶＭ． Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｏｎ ａｒｔｉｆｉｃｉａｌ ａｎｄ ｒｅａｌ ｄａｔａｓｅｔｓ ｉｎｄｉｃａｔｅ ｔｈｅ ｅｆｆｅｃｔｉｖｅ⁃ ｎｅｓｓ ｏｆ ｔｈｅ ＷＰＴＳＶＭ ｍｅｔｈｏｄ． Ｋｅｙｗｏｒｄｓ：ｃｌａｓｓｉｆｉｃａｔｉｏｎ； ｐｒｏｊｅｃｔｉｏｎ ｔｗｉｎ ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅ； ｌｏｃａｌ ｉｎｆｏｒｍａｔｉｏｎ； ｗｅｉｇｈｔｅｄ ｍｅａｎ； ｎｅｉｇｈｂｏｒｈｏｏｄ ｇｒａｐｈ； ｑｕａｄｒａｔｉｃ ｐｒｏｇｒａｍｍｉｎｇ； ｃｏｎｓｔｒａｉｎｔ ｃｏｎｄｉｔｉｏｎ； ｔｉｍｅ ｃｏｍｐｌｅｘｉｔｙ 收稿日期：２０１６⁃０３⁃２０． 网络出版日期：２０１６⁃０５⁃１３． 基金项目：国家重点基础研究计划项目（２０１３ＣＢ３２９５０２）；国家自然科学 基 金 项 目 （ ６１３７９１０１ ）； 江 苏 省 自 然 科 学 基 金 项 目 （ＢＫ２０１５１２９９）． 通信作者：花小朋． Ｅ⁃ｍａｉｌ：ｘｐ＿ｈｕａ＠ １６３．ｃｏｍ． 在分类问题中，经典支持向量机（ＳＶＭ）依据间 隔最大化准则生成分类决策面，存在训练时间复杂 度偏高和欠考虑样本分布情况的缺陷［１⁃２］ 。 近年 来，作为经典 ＳＶＭ 的改进方法，非平行超平面分类 器（ ｎｏｎｐａｒｅｌｌｅｌ ｈｙｐｅｒｐｌａｎｅ ｃｌａｓｓｉｆｉｅｒｓ，ＮＨＣｓ） ［３］ 已经 成为模式识别领域新的研究热点之一。 孪生支持向