第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ｌ为损失变量。 显然，ＰＴＳＶＭ 在优化目标函数中考虑的训练样 本集内在的散度 ∑ ｍ１ ｉ ＝ １ ｗ Ｔ １ ｘ （１） ｉ － ｗ Ｔ １ １ ｍ１ ∑ ｍ１ ｊ ＝ １ ｘ （１） ｊ æ è ç ö ø ÷ ２ ，体 现的是样本集内在的全局分布。 故该方法忽视了潜 藏在训练样本集内部的局部几何结构。 ２ 加权投影孪生支持向量机（ＷＰＴＳＶＭ） ２．１ 算法构造 为刻画同类样本集内在的紧凑型和异类样本集 间的分散性，依据图论［１０，１２］ 为每类决策面构建类内 近邻图 Ｇｓ和类间近邻图 Ｇｄ 。 定义 １ 给定第 ｃ 类中的任意两个样本 ｘ （ｃ） ｉ 和 ｘ （ｃ） ｊ ， （ｃ ＝ １，２；ｉ，ｊ ＝ １，２， …，ｍｃ）， 则类内近邻图 Ｇｓ 的相似矩阵 Ｗ ｓ Ｗ ｓ ｉｊ ( ) ｍ１ ×ｍ１可定义为 Ｗ ｓ ｉｊ ＝ ｅｘｐ（ － ‖ｘ （ｃ） ｉ － ｘ （ｃ） ｊ ‖２ ／ ｔ），ｘ （ｃ） ｊ ∈ Ｎｅ（ｘ （ｃ） ｉ ） 或 ｘ （ｃ） ｉ ∈ Ｎｅ（ｘ （ｃ） ｊ ）， ０， 其他 { （３） 式中：ｔ 为热核参数，Ｎｅ（ｘ）表示 ｘ 的 ｋ 近邻样本集。 定义 ２ ［１２］ 考虑第 ｃ 类样本 ｘ （ｃ） ｉ ，给定相反类 中任意样本 ｘ （ｃ） ｌ （ｌ ＝ １， ２， …，ｍｃ），则类间近邻图 Ｇｄ 的相似矩阵 Ｗ ｄ Ｗ ｄ ｉｌ ( ) ｍ１ ×ｍ２可定义为 Ｗ ｄ ｉｌ ＝ １， ｘ （ｃ） ｌ ｉｓ ｋ ｎｅａｒｅｓｔ ｎｅｉｇｈｂｏｒｓ ｏｆ ｘ （ｃ） ｉ {０， 其他 （４） 依据定义 ２，第 ｃ 类中每一个样本定义权重： 第 ３ 期 花小朋，等：一种改进的投影孪生支持向量机 ·３８５·