·938· 智能系统学报 第13卷 非+a侧-小- 由 8 2=0→k-∑apx)→M=1/y∑aw4x) 若定义矩阵M为 M={0地0 得 st 因矩阵M可逆，则 aiyivip(xi)= w=∑Meyx) (12) L5∑wawwywywoFw4au- 因此有 zq"((R'R/A)8K@Y)a wR-∑∑Momp/y (17) 因此有 由于 (PMrP=∑MMd -3a(PMPOK@Y）a- ia'(《G1)©K8n+ 则由(12)可得： J-UIC)at1- wf=∑PMP,my -zq((PM-P+G/y)K@Y)a+ (13) ar(PrM2P)⑧K⑧Y)a J.+J-QICa 同时有 又： 22a.m-mf=∑a∑MG-Mx =1= 器=07+2-+ (Md-Ma,ayy,(x,p(r）= aJ 224∑ML-2M0 (14) =0→4-∑d4=n∑ jEpl 由此可得： aiaiyiyo(x)p(x）= 2a(PrM(D-Q)M-P)⑧K⑧Y)a J--jq(PM-P+RR/ysKeY)a- 式中：Q是对称矩阵，且记对角矩阵D为 _a(PM-P+RR/yGK)a-o(/C)a Du= ∑0,1= J=-2a'(《PMP+RR)©K@(Y+D+I1Ca t≠ 将(12、(13)代入(8)有 原始问题的对偶问题如下： 人72mf+希22a-f max-2a'HasL.a≥0，a1=1 (18) 式中： axyawpx)=27c（PMPK@Y H=(PMrP+RR/y)⑧K⑧(Y+E)+I/C(19) K为核矩阵； 子e(prD-QMr'mcKey) (15) Y=y'yy=y2…a] E=1×1;1=[1112…1nJ' a-a(PMF)⑧K⑧Y）a= 由此，SVC-CVM方法中虽然包含了多个数 -jo((PM-P)sksy)a 据流，但其对偶问题仍相当于核空间中的另一个 则由(7可知 SVM问题，可以用常规方法来求解，其算法时间 J--jg(PM-P)8KgY)a+ 复杂度为O㎡)，在算法效率上并不具有优势。因 J-dlC)a (16) 此下文将介绍SVC-CVM的快速求解方法。 2.2核心向量机 下面求解J,。 求解最小包含球(minimum enclosing ball,, =Y∑Iwaf-〉之awoo(x) MEB)是一个数学问题，等价于求解一个二次规 划问题19，如式(20)所示：1 T   wt +λ ∑T s=1 Qts(wt −ws)   = ∑ j∈ptk αjyjφ(xj) 若定义矩阵 M 为 Mst = { (1+λ ∑ k Qtk)/T, s = t −λQts/T, s , t 因矩阵 M 可逆，则 wt = ∑ j M−1 tt(j)αjyjφ(xj) (12) 因此有 ∑T t=1 ∥wt∥ 2 = ∑ t ∑ i j M−1 tt(i)M−1 tt(j)αiαjyiyjφ(xi)φ(xj) 由于 ( P TM−2P ) i j = ∑ t M−1 tt(i)M−1 tt(j) 则由 (12) 可得： ∑T t=1 ∥wt∥ 2 = ∑ i j ( P TM−2P ) i j αiαjyiyjφ(xi)φ(xj) = α T ( (P TM−2P)⊗ K ⊗Y ) α (13) 同时有 ∑T t=1 ∑T s=1 Qts∥wt −ws∥ 2 = ∑ ts Qts∑ i j (M−1 tt(i) − M−1 ss(i) )× (M−1 tt(j) − M−1 ss(j) )αiαjyiyjφ(xi)φ(xj) = ∑ i j 2(∑ t M−1 tt(i)M−1 tt(j) Dtt − ∑ ts M−1 tt(i)M−1 st(j)Qts)× αiαjyiyjφ(xi)φ(xj) = 2α T ( (P TM−1 (D−Q)M−1P)⊗ K ⊗Y ) α (14) 式中：Q 是对称矩阵，且记对角矩阵 D 为 Dts =    ∑ k Qtk, t = s 0, t , s 将 (12)、(13) 代入 (8) 有 Jw = 1 2T ∑T t=1 ∥wt∥ 2 + λ 4T ∑T t=1 ∑T s=1 Qts∥wt −ws∥ 2− ∑n i=1 αiyiwt(i)φ(xi) = 1 2T α T ( (P TM−2P)⊗ K ⊗Y ) α+ λ 2T α T ( (P TM−1 (D−Q)M−1P)⊗ K ⊗Y ) α−α T ( (P TM−1P)⊗ K ⊗Y ) α = − 1 2 α T ( (P TM−1P)⊗ K ⊗Y ) α (15) 则由 (7) 可知 J=− 1 2 α T ( (P TM−1P)⊗ K ⊗Y ) α+ Jv + Jb + Jd − 1 2 α T (I/C)α (16) 下面求解 Jv。 Jv= γ 2 ∑T t=1 ∑K k=1 ∥vtk∥ 2 − ∑n i=1 αiyivtk (i)φ(xi) 由 ∂J ∂vtk = 0 ⇒ γvtk − ∑ j∈ptk αiyiφ(xi) ⇒ vtk = 1/γ∑ j∈ptk αiyiφ(xi) 得 Jv= γ 2 ∑T t=1 ∑K k=1 ∥vtk∥ 2 − ∑n i=1 αiyivtk (i)φ(xi) = − 1 2γ ∑T t=1 ∑K k=1 ∑ i, j∈ptk αtk(i)αtk(j)ytk(i)ytk(j)φ(xtk(i))φ(xtk(j)) = − 1 2 α T ( (R TR / λ 2 )⊗ K ⊗Y ) α (17) 因此有 J=− 1 2 α T ( (P TM−1P)⊗ K ⊗Y ) α− 1 2 α T ((G/λ2)⊗ K ⊗Y)α+ Jb + Jd − 1 2 α T (I/C)α+α T 1= − 1 2 α T ( (P TM−1P+G/γ)⊗ K ⊗Y ) α+ Jb + Jd − 1 2 α T (I/C)α 又： ∂J ∂bt = 0 ⇒ 1 T bt + λ T ∑T s=1 Qst(bs −bt)+ ∑ j∈ptk αjyj ∂J ∂dtk = 0 ⇒ γdtk − ∑ j∈ptk αiyi ⇒ dtk = 1/γ∑ j∈ptk αiyi 由此可得： J=− 1 2 α T ( (P TM−1P+ R TR/γ)⊗ K ⊗Y ) α− 1 2 α T ( (P TM−1P+ R TR/γ)⊗ K ) α− 1 2 α T (I/C)α J=− 1 2 α T ( (P TM−1P+ R TR/γ) ⊗ K ⊗(Y + E)+ I/C)α 原始问题的对偶问题如下： max α − 1 2 α THα s.t. α ⩾ 0,α T1 = 1 (18) 式中： H = (P TM−1P+ R TR/γ)⊗ K ⊗(Y + E)+ I/C (19) K 为核矩阵； Y = y T y y = [y1 y2 ··· yn] E = 1×1 T ;1 = [11 12 ··· 1n] T O(n 3 ) 由此，SVC-CVM 方法中虽然包含了多个数 据流，但其对偶问题仍相当于核空间中的另一个 SVM 问题，可以用常规方法来求解，其算法时间 复杂度为 ，在算法效率上并不具有优势。因 此下文将介绍 SVC-CVM 的快速求解方法。 2.2 核心向量机 求解最小包含球 (minimum enclosing ball, MEB) 是一个数学问题，等价于求解一个二次规 划问题[17-19] ，如式 (20) 所示： ·938· 智 能 系 统 学 报 第 13 卷