第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ＷＰＴＳＶＭ 是 ＰＴＳＶＭ 的推广算法。 证毕。 定理 ３ 说明了本文提出的 ＷＰＴＳＶＭ 算法继承 了 ＰＴＳＶＭ 的优点。 进一步比较式（７）和（２）可知， ＰＴＳＶＭ 仅仅考虑类内样本的全局信息，而 ＷＰＴＳＶＭ 用加权均值代替 ＰＴＳＶＭ 中标准均值，可以在一定 程度上提高算法的局部学习能力，因为基于近邻图 的加权均值比起标准均值更能体现样本空间的局部 结构［１３］ 。 除此之外，ＷＰＴＳＶＭ 还在优化目标函数中 引入了样本权值，权值越大，说明该样本越重要，对 保持训练样本集潜在局部信息的贡献程度越大。 图 １ 给出了 ＷＰＴＳＶＭ 与 ＰＴＳＶＭ 在人造数据集上的分 类决策面。 不难看出，ＷＰＴＳＶＭ 的决策面能够在一 定程度上体现样本集内在局部流形结构，而 ＰＴＳＶＭ 相对较弱。 图 １ 两种算法人造数据集上的比较 Ｆｉｇ．１ Ｃｏｍｐａｒｉｓｉｏｎ ｏｆ ｔｗｏ ａｌｇｏｒｉｔｈｍｓ ｏｎ ａｒｔｉｆｉｃｉａｌ ｄａｔａｓｅｔ ２．３．２ 训练时间复杂度 从二次规划求解角度分析，ＰＴＳＶＭ 在训练阶段 要针对每类中全部样本进行求解，所以计算复杂度 为 ｏ（ｍ ３ １ ＋ｍ ３ ２ ），而 ＷＰＴＳＶＭ 优化准则中约束条件指 明只对 ｆ （ｃ） ｌ ＝ １ 的样本（边界样本）进行二次规划求 解，计算复杂度为 ｏ（ｍ ３ １－ＳＶ ＋ｍ ３ ２－ＳＶ ），其中 ｍ１－ＳＶ ，ｍ２－ＳＶ 分别为第 １ 类样本及第 ２ 类样本中相应边界样本点 数。 诚然，ＷＰＴＳＶＭ 在训练阶段要事先求出每个样 本的类内权重及类间权重，计算复杂度分别为 ｏ （ｍ ２ １ ＋ｍ ２ ２ ）和 ｏ（２ｍ１·ｍ２ ）。 ２．３．３ 构造非线性分类算法 针对线性不可分情况，本文进一步提出基于核 空间的非线性 ＷＰＴＳＶＭ 算法———ＮＷＰＴＳＶＭ。 定义 ４ ＮＷＰＴＳＶＭ 的第 １ 类超平面的优化准 则为 ｍｉｎ １ ２ Ｋ（Ａ，Ｃ Ｔ ）ｕ１ － ｅ１ ｅ Ｔ １Ｅ （１）Ｋ（Ａ，Ｃ Ｔ ）ｕ１ ( ) ＴＤ （１）· Ｋ（Ａ，Ｃ Ｔ ）ｕ１ － ｅ１ ｅ Ｔ １Ｅ （１）Ｋ（Ａ，Ｃ Ｔ ）ｕ１ ( ) ＋ Ｃ１ ｅ Ｔ ２ ξ， ｓ．ｔ． － Ｆ （２） Ｋ（Ｂ，Ｃ Ｔ ）ｕ１ － ｅ２ ｅ Ｔ １Ｅ （１）Ｋ（Ａ，Ｃ Ｔ ）ｕ１ ( ) ＋ ξ ≥ Ｆ （２） ｅ２ ，ξ ≥ ０ （１１） 第 ２ 类超平面的优化准则为 ｍｉｎ １ ２ Ｋ（Ｂ，Ｃ Ｔ ）ｕ２ － ｅ２ ｅ Ｔ ２Ｅ （２）Ｋ（Ｂ，Ｃ Ｔ ）ｕ２ ( ) ＴＤ （２）· Ｋ（Ｂ，Ｃ Ｔ ）ｕ２ － ｅ２ ｅ Ｔ ２Ｅ （２）Ｋ（Ｂ，Ｃ Ｔ ）ｕ２ ( ) ＋ Ｃ２ ｅ Ｔ １η， ｓ．ｔ． Ｆ （１） Ｋ（Ａ，Ｃ Ｔ ）ｕ２ － ｅ１ ｅ Ｔ ２Ｅ （２）Ｋ（Ｂ，Ｃ Ｔ ）ｕ２ ( ) ＋ η ≥ Ｆ （１） ｅ１ ，η ≥ ０ （１２） 通 过 引 入 拉 格 朗 日 函 数， 可 按 照 类 似 上 述 ＷＰＴＳＶＭ 算法的推导过程分别得出式（１１）和（１２） 的对偶形式，然后通过二次规划求解可求得投影矢 量 ｕ１ 和 ｕ２ 。 ＮＷＰＴＳＶＭ 的决策函数为 ｌａｂｅｌ（ｘ） ＝ ａｒｇｍｉｎ ｃ ＝ １，２ ｛ｄｃ｝ ＝ ｄ１⇒ｘ ∈ 第 １ 类 {ｄ２⇒ｘ ∈ 第 ２ 类 （１３） 式中 ｄｃ ＝ Ｋ（ｘ Ｔ ，Ｃ Ｔ ）ｕｉ －∑ ｍｃ ｊ ＝ １ λ （ｃ） ｊ Ｋ（（ｘ （ｃ） ｊ ） Ｔ ，Ｃ Ｔ ）ｕｉ 。 ３ 实验分析 实验选用人造数据集和真实数据集，进一步验 证本 文 ＷＰＴＳＶＭ 方 法 的 有 效 性。 实 验 环 境： ２．３ ＧＨｚ ＣＰＵ，２ ＧＢ 内存，实验软件 ＭＡＴＬＡＢ ７．１。 ３．１ 复杂交叉数据集 相对于经典 ＳＶＭ，线性模式下对 ＸＯＲ 问题的 测试能力是非平行超平面分离器优势之一［３⁃５］ 。 因 此，本节首先验证 ＭＰＴＳＶＭ 测试交叉数据集的能 力。 图 ２ 给出一种较复杂的人造交叉数据集：Ｃｏｍｘ⁃ ｏｒ ［７］ 。 表 １ 给出了 ＴＷＳＶＭ、ＰＴＳＶＭ 和 ＷＰＴＳＶＭ 三 种算法在该测试数据集上 １０ 折交叉验证结果。 参 数 Ｃ１与 Ｃ２ 的搜索范围为｛２ ｉ ｜ ｉ ＝ － ８，－ ６，…，＋ ８｝； ＷＰＴＳＶＭ 中类内近邻参数 ｋ１ 的搜索范围为｛ １，２， …，９｝，类间近邻参数 ｋ２ ＝ ５，热核参数 ｔ 的搜索范围 为｛２ ｉ ｜ ｉ ＝ －１，０，…，８｝。 从表 １ 实验结果来看，ＰＴＳ⁃ ＶＭ 分类性能优于 ＴＷＳＶＭ，而本文 ＷＰＴＳＶＭ 则具 有更佳的分类性能。 图 ２ 复杂交叉数据集 Ｆｉｇ．２ Ｃｏｍｐｘｏｒ ｄａｔａｓｅｔ 第 ３ 期 花小朋，等：一种改进的投影孪生支持向量机 ·３８７·