第5期 赵晓晓，等：结合稀疏表示与约束传递的半监督谱聚类算法 ·857· 如果x越接近y,Z:会越大，如果y,不在数据 L,和Lp分别表示在同一个连通区域内的数 点x:的r近邻内，可设Z:为0，所以可生成一个稀 据p:和p,的r近邻集合，P,P∈Ta,i,je{1,2,…,T。 疏表示矩阵Z。Yo∈R表示Y的子矩阵，由x的 因为矩阵Z具有高度稀疏性，在同一个连通区域 r近邻组成，Z计算见式(6)： 内的两个数据点p:和p,可能并没有共同近邻点。 K(xiy;) Zi= 所以可考虑对于T内的任一数据点P,将其他数 ∑OKxJ7) i∈1,2，…，n,j∈(i） (6) 据点peT的近邻点也作为p:的近邻点： 式中：K(是核函数，较常用的是高斯核函数 Lp Lm ULp:U...ULnl,ie1.2.....ITal (9) - K(xy)=e;o表示带宽。 根据式(8)、(9)进行约束关系的传递，对矩阵2进 在获得矩阵Z后，可以构造两种形式的图，即 行更新： G=ZZ和S=ZZT,计算立=DPZ,D为对角矩 (i,pj)=lookup Vec (10) 阵，其内元素D=∑乙，所以规范化图的相似度 式中：ieLp,peTa,freq:=freq,i是p,的近邻点， 它出现的频率freq:等于按照升序排列后的频率 矩阵可表示为G=2r2eRam和3=22r∈Rxp,计算 freqz,存储在向量degree Vec中。 G的时间复杂度为O(pm2),计算$的时间复杂度为 2.2 依据稀疏表示的可扩展半监督NCut算法 O(np2)(pn). 根据1.2节所提出的基于稀疏表示建立的相 似度矩阵可知，G=22是数据X的规范化相似度 2所提算法 矩阵，经过2.1节的约束关系传递，已经实现对矩 2.1约束关系传递 阵2的更新，相似度矩阵G也随着更新，且包含更 将在“必连”和“勿连”约束集合中的数据点视 多的约束信息，能够有效地提高聚类结果。 为地标点，其个数为P。根据约束关系生成一个 依据稀疏表示的约束NCut目标函数可表示为 p×p的相似度矩阵，利用Tarjan算法检测强连通 arg miny'Lv,s.t.yOv>a,v'v =1,v11 (11) 区域，会生成多个连通区域；对每个连通区域，动 式中L=I-GeR是规范化的图拉普拉斯矩阵。 态调整其内数据的近邻点，进行约束关系的传 基于文献[11]提出的方法，上述问题的求解 递，对基于地标点近似表示方法中的稀疏表示矩 可以松弛为一般的特征值求解问题： 阵2进行更新。 Lv=A(2-BD)v (12) 根据约束信息所生成的相似度矩阵，利用 式中B是a的下界。 Tarjan算法检测生成H个强连通区域，可表示为 求解式(12)特征向量的时间复杂度为O(π)， T={TUT2UUTa},其中ae(1,2,…,},T1=p, 所以在处理大规模数据集时计算负担过大。为了 T表示第a个连通区域，包含T个数据点，T:表示 使该方法具有可扩展性，能较好地适应于大规模 T的补集，T≡{p.∈Tlp。生T,同一个连通区域内 数据集，根据1.2可知，基于稀疏表示的方法还可 的数据之间相似度最大，在不同连通区域的数据 之间的相似度最小，设置为 以构造另外一种规范化图，其相似度矩阵表示为 2-&hb 3=22T∈Rw,若能将S引入到上述约束NCut的 (7 目标函数中，可以大大降低求解特征向量的时间 每个数据点均有r个近邻点，L.∈R表示 复杂度。因此可将veR表示为2Tu,其中ueRP。 在T内每个数据点与其近邻点之间的稀疏表示矩 将v=2u代入到式(11)。改进后的可扩展约束 阵2集合，依次计算每个近邻点i∈{1,2，…，的出 NCut目标函数可表示为 现次数freq,并且按照升序进行排列，生成一个 argminu Au,s.t.uOu>a,uSu =1,1TSu=0 (13) ER m维的向量degree Vec=(freqr,freq,…,freqm),m是 式中：A=3-$3,0=Z02。 L近邻点出现次数不同的个数，出现次数较多的 该模型等价于式(I1)所表示的约束NCut目 近邻点是P。∈T最近的邻居点，依据线性插值策 标函数，但是有两个改进：一是规范化的拉普拉 略，生成一个m维的lookupVec向量： 斯矩阵LeRm变为矩阵A∈RPP;二是约束矩阵 max-min min+freq x- m≠1 lookupVec.= m-1 (8) QeR变为0∈RP,因为p《n,有效降低了计算 (max,m=1 复杂度。同样和文献[11]所提出的约束Ncut模型 式中：min和max分别表示Lz.中最大和最小相似 相比，一方面，通过地标点所构造的稀疏表示矩 度，∈{1,2，…，m}。 阵来近似获得相似度矩阵，避免对整个数据进行xi yj Zji yj xi Zji Y⟨i⟩ ∈ R d×r xi Zji 如果 越接近 ， 会越大，如果 不在数据 点 的 r 近邻内，可设 为 0，所以可生成一个稀 疏表示矩阵 Z。 表示 Y 的子矩阵，由 的 r 近邻组成， 计算见式 (6)： Zji = K(xi , yj) ∑ j ′∈⟨i⟩ K(xi , yj ′ ) , i ∈ 1,2,··· ,n, j ∈ ⟨i⟩ (6) K(·) K(xi , yj) = e −∥xi−y j∥ 2σ2 σ 式中： 是核函数，较常用的是高斯核函数 ； 表示带宽。 G =Z T Z S = ZZT Zˆ = D −1/2Z Dii = ∑ j Zi j Gˆ =Zˆ T Zˆ ∈ R n×n Sˆ = Zˆ Zˆ T ∈ R p×p Gˆ O ( pn2 ) Sˆ O ( np2 ) (p ≪ n) 在获得矩阵 Z 后，可以构造两种形式的图，即 和 ，计算 ， D 为对角矩 阵，其内元素 ，所以规范化图的相似度 矩阵可表示为 和 ，计算 的时间复杂度为 ，计算 的时间复杂度为 。 2 所提算法 2.1 约束关系传递 p× p Zˆ 将在“必连”和“勿连”约束集合中的数据点视 为地标点，其个数为 p。根据约束关系生成一个 的相似度矩阵，利用 Tarjan 算法检测强连通 区域，会生成多个连通区域；对每个连通区域，动 态调整其内数据的近邻点，进行约束关系的传 递，对基于地标点近似表示方法中的稀疏表示矩 阵 进行更新。 |H| T ≡ {T1 ∪T2 ∪ ··· ∪Ta} a ∈ {1,2,··· ,|H|} |T| = p Ta T|a| T ′ a Ta T ′ a ≡ { p ′ a ∈ T|p ′ a < Ta } 根据约束信息所生成的相似度矩阵，利用 Tarjan 算法检测生成 个强连通区域，可表示为 ，其中 ， ， 表示第 a 个连通区域，包含 个数据点， 表示 的补集， ，同一个连通区域内 的数据之间相似度最大，在不同连通区域的数据 之间的相似度最小，设置为 Zˆ ( pi , pj ) = { 1, { pi ∈ Ta|pj ∈ Ta } 0, { pi ∈ Ta|pj ∈ T ′ a } (7) LTa ∈ R r×|Ta| Ta Zˆ i ∈ {1,2,··· ,r} freqi degreeVec = ( freq1 ′ ,freq2 ′ ,··· ,freqm′ ) LTa pa ∈ Ta 每个数据点均有 r 个近邻点， 表示 在 内每个数据点与其近邻点之间的稀疏表示矩 阵 集合，依次计算每个近邻点 的出 现次数 ，并且按照升序进行排列，生成一个 m 维的向量 ，m 是 近邻点出现次数不同的个数，出现次数较多的 近邻点是 最近的邻居点，依据线性插值策 略，生成一个 m 维的 lookupVec 向量： lookupVeci ′ =    min+freqi ′ × max−min m−1 , m , 1 max, m = 1 (8) LTa i ′ ∈ {1,2,··· ,m} 式中：min 和 max 分别表示 中最大和最小相似 度， 。 Lpi Lpj pi pj pi , pj ∈ Ta i, j ∈ {1,2,··· ,|Ta|} pi pj Ta pi pj ∈ Ta pi 和 分别表示在同一个连通区域内的数 据 和 的 r 近邻集合， ， 。 因为矩阵 Z 具有高度稀疏性，在同一个连通区域 内的两个数据点 和 可能并没有共同近邻点。 所以可考虑对于 内的任一数据点 ，将其他数 据点 的近邻点也作为 的近邻点： Lpi = { Lp1 ∪ Lp2 ∪ ··· ∪ Lp|a| } , i ∈ 1,2,··· ,|Ta| (9) 根据式 (8)、(9) 进行约束关系的传递，对矩阵 Zˆ 进 行更新： Zˆ ( i, pj ) = lookupVeci ′ (10) i ∈ Lpj pj ∈ Ta freqi = freqi ′ pj freqi freqi ′ degreeVec 式中： ， ， ，i 是 的近邻点， 它出现的频率 等于按照升序排列后的频率 ，存储在向量 中。 2.2 依据稀疏表示的可扩展半监督 NCut 算法 Gˆ =Zˆ T Zˆ Zˆ Gˆ 根据 1.2 节所提出的基于稀疏表示建立的相 似度矩阵可知， 是数据 X 的规范化相似度 矩阵，经过 2.1 节的约束关系传递，已经实现对矩 阵 的更新，相似度矩阵 也随着更新，且包含更 多的约束信息，能够有效地提高聚类结果。 依据稀疏表示的约束 NCut 目标函数可表示为 argmin v∈Rn v T Lv¯ , s.t.v TQv ⩾ α, v T v = 1, v⊥1 (11) L¯ = I−Gˆ ∈ R 式中 n×n是规范化的图拉普拉斯矩阵。 基于文献[11]提出的方法，上述问题的求解 可以松弛为一般的特征值求解问题： Lv = λ(Q−βI) v (12) 式中 β 是α的下界。 O ( n 3 ) Sˆ = Zˆ Zˆ T ∈ R p×p Sˆ v ∈ R n Zˆ Tu u ∈ R p v = Zˆ Tu 求解式 (12) 特征向量的时间复杂度为 ， 所以在处理大规模数据集时计算负担过大。为了 使该方法具有可扩展性，能较好地适应于大规模 数据集，根据 1.2 可知，基于稀疏表示的方法还可 以构造另外一种规范化图，其相似度矩阵表示为 ，若能将 引入到上述约束 NCut 的 目标函数中，可以大大降低求解特征向量的时间 复杂度。因此可将 表示为 ，其中 。 将 代入到式 (11)。改进后的可扩展约束 NCut 目标函数可表示为 argmin u∈Rp u TAu, s.t.u TQuˆ ⩾ α,u TSuˆ = 1,1 TSuˆ = 0 (13) A = Sˆ −SˆSˆ, 式中： Qˆ = ZQˆ Zˆ T。 L ∈ R n×n A ∈ R p×p Q ∈ R n×n Qˆ ∈ R p×p p ≪ n 该模型等价于式 (11) 所表示的约束 NCut 目 标函数，但是有两个改进：一是规范化的拉普拉 斯矩阵 变为矩阵 ；二是约束矩阵 变为 ，因为 ，有效降低了计算 复杂度。同样和文献[11]所提出的约束 Ncut 模型 相比，一方面，通过地标点所构造的稀疏表示矩 阵来近似获得相似度矩阵，避免对整个数据进行 第 5 期 赵晓晓，等：结合稀疏表示与约束传递的半监督谱聚类算法 ·857·