·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的特例，而ｆ （ｃ） ｌ ＝ １， ∃ｉ，Ｗ ｄ ｉｌ ≠ ０ {０， 其他 （５） 显然，权重 ｆ （ｃ） ｌ ＝ １ 样本是第 ｃ 类样本集的边界样本。 定义 ３ ＷＰＴＳＶＭ 算法中，第 １ 类训练样本集 相应决策超平面的优化准则 ＷＰＴＳＶＭ⁃１： ｍｉｎ １ ２ ∑ ｍ１ ｉ ＝ １ ρ （１） ｉ ｗ Ｔ １ ｘ （１） ｉ － ｗ Ｔ １∑ ｍ１ ｊ ＝ １ λ （１） ｊ ｘ （１） ( ｊ ) ２ ＋ Ｃ１∑ ｍ２ ｌ ＝ １ ξｌ ｓ．ｔ． － ｆ （２） ｌ ｗ Ｔ １ ｘ （２） ｌ － ｗ Ｔ １∑ ｍ１ ｊ ＝ １ λ （１） ｊ ｘ （１） ( ｊ ) ＋ ξｌ ≥ ｆ （２） ｌ ，ξｌ ≥ ０ （６） 第 ２ 类超平面优化准则 ＷＰＴＳＶＭ⁃２： ｍｉｎ １ ２ ∑ ｍ２ ｌ ＝ １ ρ （２） ｌ ｗ Ｔ ２ ｘ （２） ｌ － ｗ Ｔ ２∑ ｍ２ ｊ ＝ １ λ （２） ｊ ｘ （２） ( ｊ ) ２ ＋ Ｃ２∑ ｍ１ ｉ ＝ １ ηｉ， ｓ．ｔ．ｆ （１） ｉ ｗ Ｔ ２ ｘ （１） ｉ － ｗ Ｔ ２∑ ｍ２ ｊ ＝ １ λ （２） ｊ ｘ （２） ( ｊ ) ＋ ηｉ ≥ ｆ （１） ｉ ，ηｉ ≥ ０ （７） 式中： Ｃ１ 和 Ｃ２ 是惩罚参数，ξｌ 和 ηｉ 为损失变量， ρ （ｃ） ｉ ＝∑ ｍｃ ｊ ＝ １ Ｗ ｓ ｉｊ，λ （ｃ） ｊ ＝ ρ （ｃ） ｊ ／∑ ｍｃ ｉ ＝ １ ρ （ｃ） ｉ ，ｃ ＝ １，２。 式（６）中，ρ （１） ｉ 代表样本 ｘ （１） ｉ 的权重，ρ （１） ｉ 值越 大，表示 ｘ （１） ｉ 越重要，对保持样本空间局部信息的 贡献程度越大； ∑ ｍ１ ｊ ＝ １ λ （１） ｊ ｘ （１） ｊ 为第 １ 类样本空间的加 权均值，比起式（２）中的标准均值更能体现样本空 间的局部结构［１３］ ；约束条件表明 ＷＰＴＳＶＭ⁃１ 仅仅 考虑第 ２ 类样本中 ｆ （２） ｌ ＝ １ 的边界样本。 显然，式 （６） 优化目标是为第 １ 类样本寻找最佳投影轴 ｘｗｘ１ ，使得权重较大的样本投影后尽可能聚集在加 权均值中心附近，而第 ２ 类中 ｆ （１） ｌ ＝ １ 的边界样本离 中心尽可能远。 式（７） 有类似的几何解释式。 式 （６）矩阵形式为 ｍｉｎ １ ２ Ａｗ１ － ｅ１ ｅ Ｔ １Ｅ （１）Ａｗ１ ( ) Ｔ Ｄ （１） Ａｗ１ － ｅ１ ｅ Ｔ １Ｅ （１）Ａｗ１ ( ) ＋ Ｃ１ ｅ Ｔ ２ ξ ｓ．ｔ． － Ｆ （２） Ｂｗ１ － ｅ２ ｅ Ｔ １Ｅ （１）Ａｗ１ ( ) ＋ ξ ≥ Ｆ （２） ｅ２，ξ ≥０ （８） 式中：ξ２ ＝ （ ξ１ ，…，ξｍ２ ） Ｔ ，Ｄ （１） ＝ ｄｉａｇ（ ρ （１） １ ，…，ρ （１） ｍ１ ）， Ｅ （１）＝ ｄｉａｇ（λ （１） １ ，…，λ （１） ｍ１ ），Ｆ （２）＝ ｄｉａｇ（ｆ （２） １ ，…，ｆ （２） ｍ２ ）。 类似于传统 ＳＶＭ 求解方法，通过引入拉格朗日 函数生成式（８）的对偶问题 ｍｉｎ １ ２ α Ｔ Ｆ （２） Ｂ － ｅ２ ｅ Ｔ １Ｅ （１） ( ( Ａ) ) × Ａ － ｅ１ ｅ Ｔ １Ｅ （１） ( Ａ) ＴＤ （１） Ａ － ｅ１ ｅ Ｔ １Ｅ （１） ( ( Ａ) ) －１ Ｆ （２） Ｂ － ｅ２ ｅ Ｔ １Ｅ （１） ( ( Ａ) ) Ｔα － ｅ Ｔ ２α ｓ．ｔ． ０ ≤ α ≤ Ｃ１ ｅ２ （９） 式中 α＝ ［α１ ，α２ ，…，αｍ２ ］ Ｔ 。 由此对偶问题的求解可得原问题式（６）中投影 轴 ｗ１ 。 类 似 的 方 法， 可 求 原 问 题 式 （ ７） 中 投 影 轴 ｗ２ 。 对于未知样本 ｘ，ＷＰＴＳＶＭ 的决策函数为 ｌａｂｅｌ（ｘ） ＝ ａｒｇｍｉｎ ｃ ＝ １，２ ｛ｄｃ｝ ＝ ｄ１⇒ｘ ∈ 第 １ 类 {ｄ２⇒ｘ ∈ 第 ２ 类 （１０） 式中：ｄｃ ＝ ｗ Ｔ ｃ ｘ－ｗ Ｔ ｃ ∑ ｍｃ ｊ ＝ １ λ （ｃ） ｊ ｘ （ｃ） ｊ ， · 表示绝对值。 ２．２ 算法分析 这里 以 ＷＰＴＳＶＭ 的 第 １ 类 样 本 优 化 问 题 ＷＰＴＳＶＭ⁃１ 为例进行算法分析，第 ２ 类样本优化问 题 ＷＰＴＳＶＭ⁃２ 有类似的算法分析。 考虑 对 偶 形 式 式 （ ９ ）， 假 设 实 对 称 矩 阵 Ａ － ｅ１ ｅ Ｔ １Ｅ （１） ( Ａ) ＴＤ （１） Ａ － ｅ１ ｅ Ｔ １Ｅ （１） ( ( Ａ) ) 可逆（若 不可逆，可采用类似文献［ ３］ 方法引入正则化项 Ｉ（ε＞０），ε 尽 可 能 的 小）。 式 （ １４ ） 中 的 核 函 数 Ｋ（·）只有保证 Ｍｅｒｃｅｒ 核时，才能保证其是二次凸 规划，所求的解才为全局最优解。 为验证这一问题， 给出如下定理。 定理 １ 式（９）为凸二次规划。 证明 式（９）核矩阵： Ｋ ～ ＝ ［ ｋ ～ ｉｊ ＝ Ｆ （２） Ｂ － ｅ２ ｅ Ｔ １Ｅ （１） ( ( Ａ) )· Ａ － ｅ１ ｅ Ｔ １Ｅ （１） ( Ａ) ＴＤ （１） Ａ － ｅ１ ｅ Ｔ １Ｅ （１） ( ( Ａ) ) －１· Ｆ （２） Ｂ － ｅ２ ｅ Ｔ １Ｅ （１） ( ( Ａ) ) Ｔ 是实对称矩阵。 下面证明矩阵 Ｋ ～ 是半正定的。 设 任意 ｘ ∈ Ｒ ｍ２ ， 则有 ｘ ＴＫ ～ ｘ ＝ （ ｘ Ｔ （Ｆ （２） （Ｂ－ｅ２ ｅ Ｔ １ Ｅ （１） Ａ）） （（Ａ－ｅ１ ｅ Ｔ １ Ｅ （１）Ａ） ＴＤ （１） （Ａ－ｅ１ ｅ Ｔ １ Ｅ （１）Ａ）） －１／ ２ ） ２≥ ０，因此 Ｋ ～ 半正定且为 Ｍｅｒｃｅｒ 核函数。 根据文献 ［１４］中引理 ２ 可知，式（９）为凸二次规划。 证毕。 定理 ２ 假定 α 是对偶问题式（９）的解，则 ｗ１ 是原优化问题式（６）的全局最优解。 证明 由定理 １ 的证明可得，式（９） 为凸二次 规划问题，又依据文献［１４］中引理 ３ 的满足条件可 知，该二次规划的解为全局最优解。 证毕。 ２．３ 算法比较 ２．３．１ 泛化性能 定理 ３ ＰＴＳＶＭ 是 ＷＰＴＳＶＭ 的特例。 证明 考虑 ＷＰＴＳＶＭ 的第 １ 类样本的优化准 则（７）。 令 Ｄ （１） ＝ Ｉ∈Ｒ ｍ１ ×ｍ１ ，Ｆ （２） ＝ Ｉ∈Ｒ ｍ２ ×ｍ２ ，则式 （７）转化为 ＰＴＳＶＭ 的第 １ 类样本的优化准则（２）。 对于 ＷＰＴＳＶＭ 的第 ２ 类样本的优化准则（８）有类似 的特 性。 因 此， ＰＴＳＶＭ 是 ＷＰＴＳＶＭ 的 特 例， 而 ·３８６· 智 能 系 统 学 报 第 １１ 卷