正在加载图片...
第5期 史颂辉，等：基于能量的结构化最小二乘孪生支持向量机 ·1015· 中有Cw个簇。那么S-TWSVM的优化问题可以 min 表述为 -b-月 Bw+ear+号0gt w6+)+∑n (2) 如 2 lAw,+eb+cies+ca()+ s.t.Aw-+e,b+n=E, 9w∑0. 1 式中：c(i=1,2,…,6)是惩罚参数；5、7是松弛变 + s.L-(Bw+e_b)+5≥e-,≥0 量；E,和E是超平面的能量因子：∑， min ++∑：∑=∑%++∑：∑，和 b_月 2 Bw-+eb-+caecs(l)+ 1 w∑n 分别是对应于2个类中的第i个簇和第广个 s.t.(Aw-+e,b)+n≥e+,7≥0 簇的协方差矩阵，i=1,2,…,Cp,j=1,2,…,Cn0 式中：c≥0(i=1,2…,6)是惩罚参数；专、刀是松弛 将等式约束条件代入目标函数式(1)中得到： 变量：，、。.是元素全为1的列向量：∑ Aw.+e.b.lP+SlBw.+e.b.+E+ 1 政 ∑++∑∑=∑、+∑∑和∑ 号0，后+的+∑ C3 2 是2类中的每一个簇的相应协方差矩阵，其中 (3) i=1,2,…,Cp,j=1,2,…,Cwo 分别对式(3)中w+和b求导，并且由 新的数据点被分配给正类还是负类取决于得 KKT条件得： 到的2个超平面wx+b+=0和wx+b.=0中它 AT(Aw.+e.b.)+cBT(Bw.+e_b.+E_)+ 距离哪一个超平面更近，即 cw,+c∑.w,=0 (4) Label(x)argminwix+b..wIx+b_ e:(Aw:+e:b+)+cie(Bw:+e_b.+E_)+c2b.=0 (5) 将式(4)、（⑤）整理成矩阵的形式为 2 ES-LSTWSVM 在本节中，提出了一种基于能量的结构化孪 生支持向量机(ES-LSTWSVM)。该算法主要分 gle+o =0 为2步：1)用某种聚类方法提取类内的结构信息； 2)最小化每个类中各个簇之间的紧密度并将其嵌 入到目标函数中。此外，利用核技巧使模型能够 解决非线性可分问题。在下面的小节中，将具体 讨论这些步骤。 使P=[Ae,],2=[Be.】,并且 2.1线性ES-LSTWSVM 0 。则解可表示为 有很多聚类方法可被用于提取类内的结构信 W+ 息，例如：k均值算法7、模糊聚类和密度聚类82刘。 z1= b+】 =-c1(Pp+c0'0+cI+c∑，)'gE. 使用拐点图2来确定最佳聚类数目。聚类之后， 同理，式(2)可表示为 通过计算类中各个簇的协方差矩阵将结构信息引 w- 入到优化问题中。因此，聚类之后的簇应该是紧 3= b =c(OTQ+caPTP+csI+c>PE. 凑的并且是球形的。鉴于此，采用Ward's link- 是适当维数的单位 age聚类算法，这是一种层次聚类方法，为协方差 矩阵的计算提供了基础。 矩阵。 假设从正类和负类中分别得到了C。和Cm个 ES-LSTWSVM通过如下的决策函数判定新 簇，即A=PU...UP;U...UPc,B=N1UUNU 样本的类别标签： UWc.。对于线性可分的二分类问题，ES-LSTWS Label(x)= (xw.+b.x"w-+b- w_‖ VM模型可表示为 hw,l 1 2.2非线性ES-LSTWSVM min Aw,+e.bP+号55+ 对于非线性分类问题，利用核技巧进行处 el6+的)+号∑m C2 (1) 理。首先将原始特征空间中的数据映射到希尔伯 -(Bwt+e_b)+5=E. 特空间中：Φ：Rm→H。类似于线性情形，决策函中有 CN 个簇。那么 S-TWSVM 的优化问题可以 表述为 min w+,b+,ξ 1 2 ∥Aw+ +e+b+∥ 2 2 +c1e T − ξ + 1 2 c2(∥w+∥ 2 2 +b 2 + )+ 1 2 c3w T + ∑ + w+ s.t. −(Bw+ +e−b+)+ξ ⩾ e−, ξ ⩾ 0 min w−,b−,η 1 2 ∥Bw− +e−b−∥ 2 2 +c4e T +η+ 1 2 c5(∥w−∥ 2 2 +b 2 − )+ 1 2 c6w T − ∑ − w− s.t. (Aw− +e+b−)+η ⩾ e+,η ⩾ 0 ci ⩾ 0(i = 1,2,··· ,6) ξ η e+ e− ∑ + = ∑ P1 +···+ ∑ PCP ∑ − = ∑ N1 +···+ ∑ NCN ∑ Pi ∑ Nj i = 1,2,··· ,CP, j = 1,2,··· ,CN 式中： 是惩罚参数； 、 是松弛 变量； 、 是元素全 为 1 的列向量； ； ； 和 是 2 类中的每一个簇的相应协方差矩阵，其中， 。 w T + x+b+ = 0 w T − x+b− = 0 新的数据点被分配给正类还是负类取决于得 到的 2 个超平面 和 中它 距离哪一个超平面更近，即 Label(x) = argmin +,− { w T + x+b+ , w T − x+b− } 2 ES-LSTWSVM 在本节中，提出了一种基于能量的结构化孪 生支持向量机 (ES-LSTWSVM)。该算法主要分 为 2 步：1) 用某种聚类方法提取类内的结构信息; 2) 最小化每个类中各个簇之间的紧密度并将其嵌 入到目标函数中。此外，利用核技巧使模型能够 解决非线性可分问题。在下面的小节中，将具体 讨论这些步骤。 2.1 线性 ES-LSTWSVM 有很多聚类方法可被用于提取类内的结构信 息，例如：k 均值算法[17] 、模糊聚类和密度聚类[18-21]。 使用拐点图[22] 来确定最佳聚类数目。聚类之后， 通过计算类中各个簇的协方差矩阵将结构信息引 入到优化问题中。因此，聚类之后的簇应该是紧 凑的并且是球形的。鉴于此，采用 Ward’s linkage 聚类算法，这是一种层次聚类方法，为协方差 矩阵的计算提供了基础。 Cp Cn A = P1 ∪ ··· ∪ Pi ∪ ··· ∪ PCp B = N1 ∪ ··· ∪Ni ∪ ··· ∪NCn 假设从正类和负类中分别得到了 和 个 簇，即 ， 。对于线性可分的二分类问题，ES-LSTWSVM 模型可表示为 min w+,b+,ξ 1 2 ∥Aw+ +e+b+∥ 2 + c1 2 ξ T ξ+ c2 2 (∥w+∥ 2 2 +b 2 + )+ c3 2 w T + ∑ + w+ s.t. −(Bw+ +e−b+) +ξ = E− (1) min w−,b−,η 1 2 ∥Bw− +e−b−∥ 2 + c4 2 η Tη+ c5 2 (∥w−∥ 2 2 +b 2 − )+ c6 2 w T − ∑ − w− s.t. Aw− +e+b− +η = E+ (2) ci(i = 1,2,··· ,6) ξ η E+ E− ∑ + = ∑ P1 +···+ ∑ PCP ∑ − = ∑ N1 +···+ ∑ NCN ∑ ∑ Pi Nj i = 1,2,··· ,CP, j = 1,2,··· ,Cn 式中： 是惩罚参数； 、 是松弛变 量 ； 和 是超平面的能量因子； ； ； 和 分别是对应于 2 个类中的第 i 个簇和第 j 个 簇的协方差矩阵， 。 将等式约束条件代入目标函数式 (1) 中得到： min w+,b+ 1 2 ∥Aw+ +e+b+∥ 2 + c1 2 ∥Bw+ +e−b+ + E−∥ 2+ c2 2 (∥w+∥ 2 2 +b 2 + )+ c3 2 w T + ∑ + w+ (3) 分别对 式 ( 3 ) 中 w+ 和 b+ 求导，并且 由 KKT 条件得： A T (Aw+ +e+b+)+c1B T (Bw+ +e−b+ + E−)+ c2w+ +c3 ∑ + w+ = 0 (4) e T + (Aw+ +e+b+)+c1e T − (Bw+ +e−b+ + E−)+c2b+ = 0 (5) 将式 (4)、(5) 整理成矩阵的形式为 [ A TA AT e+ e T +A eT + e+ ] [ w+ b+ ] +c1 [ B TB B T e− e T −B eT − e− ] [ w+ b+ ] + c1 [ B T e T − ] E− +c2 [ w+ b+ ] +c3 ∑ + w+ 0 = 0 [ A T e T + ] [ A e+ ] [ w+ b+ ] +c1 [ B T e T − ] [ B e− ] [ w+ b+ ] + c2 [ w+ b+ ] +c3 ∑ + w+ 0 = −c1 [ B T e T − ] E− P = [ A e+ ] Q = [ B e− ] ∑ 1 = ∑ + 0 0 0 使 ， ，并且 。则解可表示为 z1 = [ w+ b+ ] = −c1(P T P+c1Q TQ+c2I +c3 ∑ 1 ) −1Q TE− 同理，式 (2) 可表示为 z2 = [ w− b− ] = c4(Q TQ+c4P T P+c5I +c6 ∑ 2 ) −1P TE+ ∑ 2 = ∑ − 0 0 0 式中： ； I 是适当维数的单位 矩阵。 ES-LSTWSVM 通过如下的决策函数判定新 样本的类别标签： Label(x) = x Tw+ +b+ ∥w+∥ , x Tw− +b− ∥w−∥ 2.2 非线性 ES-LSTWSVM Φ : R m → H 对于非线性分类问题，利用核技巧进行处 理。首先将原始特征空间中的数据映射到希尔伯 特空间中： 。类似于线性情形，决策函 第 5 期 史颂辉，等：基于能量的结构化最小二乘孪生支持向量机 ·1015·