第13卷第5期 智能系统学报 Vol.13 No.5 2018年10月 CAAI Transactions on Intelligent Systems Oct.2018 D0:10.11992/tis.201703013 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20170702.1547.026html 结合稀疏表示与约束传递的半监督谱聚类算法 赵晓晓，周治平 (江南大学物联网技术应用教育部工程研究中心，江苏无锡214122) 摘要：针对半监督谱聚类不能有效处理大规模数据，没有考虑约束传递不能充分利用有限约束信息的问题， 提出一种结合稀疏表示和约束传递的半监督谱聚类算法。首先，根据约束信息生成约束矩阵，将其引入到谱聚 类中；然后，将约束集合中的数据作为地标点构造稀疏表示矩阵，近似获得图相似度矩阵，从而改进约束谱聚 类模型：同时，根据地标点的相似度矩阵生成连通区域，在每个连通区域内动态调整近邻点，利用约束传递进 一步提高聚类准确率。实验表明，所提算法和约束谱聚类相比，在算法效率方面具有明显优势，且准确率没有 明显下降：和快速谱聚类方法相比，在聚类准确率上有所提升。 关键词：数据挖掘：聚类分析：谱聚类：半监督学习：稀硫表示：约束传递 中图分类号：TP18 文献标志码：A文章编号：1673-4785(2018)05-0855-09 中文引用格式：赵晓晓，周治平.结合稀疏表示与约束传递的半监督谱聚类算法L.智能系统学报，2018,13(5)：855-863. 英文引用格式：ZHAO Xiaoxiao,ZHOU Zhiping.A semi-supervised spectral clustering algorithm combined with sparse representa- tion and constraint propagation[J CAAI transactions on intelligent systems,2018,13(5):855-863. A semi-supervised spectral clustering algorithm combined with sparse representation and constraint propagation ZHAO Xiaoxiao,ZHOU Zhiping (Engineering Research Center of Internet of Things Technology Applications Ministry of Education,Jiangnan University,Wuxi 214122,China) Abstract:The semi-supervised spectral clustering algorithm does not deal with large-scale datasets effectively and does not fully utilize the constraint information because it does not consider the constraint propagation.To address these drawbacks,this paper proposes a semi-supervised spectral clustering algorithm that combines sparse representation and constraint propagation.The algorithm first generates the constraint matrix according to the constraint information,intro- duces it into the spectral clustering,and then constructs a sparse representation matrix by taking the data points in the constrained sets as the landmarks to approximate the graph similarity matrix,thereby revising the constrained spectral clustering model.Meanwhile,the connected region is generated according to the similarity matrix of the landmark data points,and the neighboring nodes are dynamically adjusted in each connected region.The clustering accuracy is further improved using the constraint propagation.Experimental results show that the proposed method is more efficient than constrained spectral clustering algorithms,and their accuracy levels are similar.Moreover,its clustering accuracy ex- ceeds those of the fast spectral clustering algorithms. Keywords:data mining;cluster analysis;spectral clustering;semi-supervised learning;sparse representation;constraint propagation 谱聚类作为聚类分析一种有效的方法，建立 收稿日期：2017-03-10.网络出版日期：2017-07-02 在谱图划分的基础上，可将数据集从原始空间转 基金项目：国家自然科学基金项目(61373126). 通信作者：赵晓晓.E-mail:6l519050I9@vip,jiangnan.edu.cn. 换到低维特征空间，使原始数据变成线性可分四
DOI: 10.11992/tis.201703013 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20170702.1547.026.html 结合稀疏表示与约束传递的半监督谱聚类算法 赵晓晓，周治平 （江南大学 物联网技术应用教育部工程研究中心，江苏 无锡 214122） 摘 要：针对半监督谱聚类不能有效处理大规模数据，没有考虑约束传递不能充分利用有限约束信息的问题， 提出一种结合稀疏表示和约束传递的半监督谱聚类算法。首先，根据约束信息生成约束矩阵，将其引入到谱聚 类中；然后，将约束集合中的数据作为地标点构造稀疏表示矩阵，近似获得图相似度矩阵，从而改进约束谱聚 类模型；同时，根据地标点的相似度矩阵生成连通区域，在每个连通区域内动态调整近邻点，利用约束传递进 一步提高聚类准确率。实验表明，所提算法和约束谱聚类相比，在算法效率方面具有明显优势，且准确率没有 明显下降；和快速谱聚类方法相比，在聚类准确率上有所提升。 关键词：数据挖掘；聚类分析；谱聚类；半监督学习；稀疏表示；约束传递 中图分类号：TP18 文献标志码：A 文章编号：1673−4785(2018)05−0855−09 中文引用格式：赵晓晓, 周治平. 结合稀疏表示与约束传递的半监督谱聚类算法[J]. 智能系统学报, 2018, 13(5): 855–863. 英文引用格式：ZHAO Xiaoxiao, ZHOU Zhiping. A semi-supervised spectral clustering algorithm combined with sparse representation and constraint propagation[J]. CAAI transactions on intelligent systems, 2018, 13(5): 855–863. A semi-supervised spectral clustering algorithm combined with sparse representation and constraint propagation ZHAO Xiaoxiao，ZHOU Zhiping (Engineering Research Center of Internet of Things Technology Applications Ministry of Education, Jiangnan University, Wuxi 214122, China) Abstract: The semi-supervised spectral clustering algorithm does not deal with large-scale datasets effectively and does not fully utilize the constraint information because it does not consider the constraint propagation. To address these drawbacks, this paper proposes a semi-supervised spectral clustering algorithm that combines sparse representation and constraint propagation. The algorithm first generates the constraint matrix according to the constraint information, introduces it into the spectral clustering, and then constructs a sparse representation matrix by taking the data points in the constrained sets as the landmarks to approximate the graph similarity matrix, thereby revising the constrained spectral clustering model. Meanwhile, the connected region is generated according to the similarity matrix of the landmark data points, and the neighboring nodes are dynamically adjusted in each connected region. The clustering accuracy is further improved using the constraint propagation. Experimental results show that the proposed method is more efficient than constrained spectral clustering algorithms, and their accuracy levels are similar. Moreover, its clustering accuracy exceeds those of the fast spectral clustering algorithms. Keywords: data mining; cluster analysis; spectral clustering; semi-supervised learning; sparse representation; constraint propagation 谱聚类作为聚类分析一种有效的方法，建立 在谱图划分的基础上，可将数据集从原始空间转 换到低维特征空间，使原始数据变成线性可分[1] ， 收稿日期：2017−03−10. 网络出版日期：2017−07−02. 基金项目：国家自然科学基金项目 (61373126). 通信作者：赵晓晓. E-mail：6151905019@vip.jiangnan.edu.cn. 第 13 卷第 5 期 智 能 系 统 学 报 Vol.13 No.5 2018 年 10 月 CAAI Transactions on Intelligent Systems Oct. 2018
·856· 智能系统学报 第13卷 目前已广泛应用于图像分割、人脸识别等领域。 明，本文算法对这些大规模数据具有较好适应 另一方面，半监督学习是机器学习领域的研究热 性，且在有效降低算法复杂度的同时，保证了约 点，已被用于解决实际问题6，在聚类分析中引 束谱聚类算法结果的准确率。 入一些监督信息来指导聚类过程，能够提高聚类 准确率。 1算法基本原理 半监督聚类算法的约束信息包括“必连”和 1.1约束NCut算法 “勿连”约束集合，引入这些约束信息可指导聚类 对于数据集X={x1,x:∈R,数据之间的相 过程。目前，针对半监督谱聚类算法已有大量的 似度矩阵为W,度矩阵D为对角阵，其内元素表 研究，Kamvar等m根据约束关系调整数据之间的 相似度，将调整后的相似度矩阵用于改进谱聚 示为Da=∑W规范化拉普拉斯矩阵表示为L=一 类，但是不能充分利用初始有限的约束关系；蒋 D-1PWD-1r,I表示单位矩阵。 伟进等劉提出一种纠错式主动学习成对约束算 标准NCut的目标函数为 法，将挖掘到的监督信息用于调整数据点之间的 argminv'Lv,s.t.yy =1,vL1 (1) 距离矩阵，但约束集合对聚类结果影响较大；丁 世飞等通过优化高斯核参数和引入成对约束信 式中v表示松弛化的类指示向量。 息来调整相似度矩阵，但过多的约束信息会对聚 假设已知“必连”约束集合M与“勿连”约束集 类准确率造成负面的影响；Cucuringu等"ol将“必 合C,文献[11]根据约束信息生成约束矩阵Q,可 连”和“勿连”约束矩阵均视为图拉普拉斯矩阵，把 表示为 约束聚类转化为广义特征值问题，针对2类划分 (x,x)∈M 效率和准确率显著提高。王翔等提出一种柔性 Q -1,(x,x)eC (2) 0, 约束谱聚类框架，引入大量硬约束和软约束信息 无约束信息 建立新的约束优化问题，有效提高聚类准确率， 通过式(3)来衡量Q中约束关系与v的一致程度： 但是不具备约束关系传递。基于约束信息的半监 ov-> (3) 督聚类算法，通常能获取数据的约束关系是非常 1j1 有限的，通过约束传递来获得大量可靠的成对约 定义软约束v∈R,QER",如果数据x,和x,是 束信息，可显著提高半监督聚类的性能。余志文 同一类，那么Q为正；否则为负。Q的绝对值表示 等2提出一种增强型半监督聚类集成框架(incre- 约束权重，vQ的值越大，表明v与Q中的约束信 mental semi-supervised clustering ensemble,ISSCE), 息就越一致。基于上述软约束，不一定要严格满 采用卢志武等提出的约束传递方法，即基于 足每个指定的约束条件，忽略部分约束信息可降 k近邻图的标签传播方法，将少量标签样本的监 低计算开销，通过用户指定阈值来确定约束的下 督信息传递给未标签样本，但如果相似度错误反 界值，即vQy≥a。 映数据点之间的相似性，会造成约束关系的错误 约束NCut的目标函数为 传递。传统的谱聚类及上述大部分半监督谱聚类 argminy Lv,s.t.yQv>a.vy=1.vL1 (4) 算法均需要存储数据的相似度矩阵且对拉普拉斯 上述问题可转化为求解矩阵的特征向量)， 矩阵进行特征分解，空间和时间的计算复杂度比 但是空间和时间复杂度分别为0(2)和0()，对于 较高，在处理大规模数据集时计算代价难以承受。 大规模数据集，计算复杂度过高；而且不具备约 为了提升谱聚类的扩展性，蔡登等1提出基于地 标点表示的谱聚类算法，通过数据点与地标点之 束传递功能，不能充分利用有限的约束信息。 间的相似度矩阵乘积来近似得到整体数据点的相 1.2依据稀疏表示的相似度矩阵 似度矩阵，然后利用近似性质实现快速特征分解。 蔡登等提出基于图稀疏表示的谱聚类算 本文将采用基于地标点近似表示的方法，通 法，通过地标点的线性组合来实现所有数据点 过稀疏表示构造的相似度矩阵对柔性约束谱聚类 X的近似表示X≈YZ。对于给定的任一数据点 算法模型进行改进，并且根据约束集合内地标 x,其近似数据点e,可以表示为 点的关系，利用Tarjan算法自动检测连通区域， (5) 在每个连通区域内部动态调整近邻点，传递约束 1 关系，从而更新稀疏表示矩阵提高聚类准确率。 式中：y,是Y∈Rwp的列向量，Z是ZeRw的第j行 在5个大规模标准数据集上进行实验的结果表 第i列元素
目前已广泛应用于图像分割、人脸识别等领域[2-3]。 另一方面，半监督学习是机器学习领域的研究热 点，已被用于解决实际问题[4-6] ，在聚类分析中引 入一些监督信息来指导聚类过程，能够提高聚类 准确率。 半监督聚类算法的约束信息包括“必连”和 “勿连”约束集合，引入这些约束信息可指导聚类 过程。目前，针对半监督谱聚类算法已有大量的 研究，Kamvar 等 [7]根据约束关系调整数据之间的 相似度，将调整后的相似度矩阵用于改进谱聚 类，但是不能充分利用初始有限的约束关系；蒋 伟进等[8]提出一种纠错式主动学习成对约束算 法，将挖掘到的监督信息用于调整数据点之间的 距离矩阵，但约束集合对聚类结果影响较大；丁 世飞等[9]通过优化高斯核参数和引入成对约束信 息来调整相似度矩阵，但过多的约束信息会对聚 类准确率造成负面的影响；Cucuringu 等 [10]将“必 连”和“勿连”约束矩阵均视为图拉普拉斯矩阵，把 约束聚类转化为广义特征值问题，针对 2 类划分 效率和准确率显著提高。王翔等[11]提出一种柔性 约束谱聚类框架，引入大量硬约束和软约束信息 建立新的约束优化问题，有效提高聚类准确率， 但是不具备约束关系传递。基于约束信息的半监 督聚类算法，通常能获取数据的约束关系是非常 有限的，通过约束传递来获得大量可靠的成对约 束信息，可显著提高半监督聚类的性能。余志文 等 [12]提出一种增强型半监督聚类集成框架 (incremental semi-supervised clustering ensemble，ISSCE)， 采用卢志武等[ 1 3 ]提出的约束传递方法，即基于 k 近邻图的标签传播方法，将少量标签样本的监 督信息传递给未标签样本，但如果相似度错误反 映数据点之间的相似性，会造成约束关系的错误 传递。传统的谱聚类及上述大部分半监督谱聚类 算法均需要存储数据的相似度矩阵且对拉普拉斯 矩阵进行特征分解，空间和时间的计算复杂度比 较高，在处理大规模数据集时计算代价难以承受。 为了提升谱聚类的扩展性，蔡登等[14]提出基于地 标点表示的谱聚类算法，通过数据点与地标点之 间的相似度矩阵乘积来近似得到整体数据点的相 似度矩阵，然后利用近似性质实现快速特征分解。 本文将采用基于地标点近似表示的方法，通 过稀疏表示构造的相似度矩阵对柔性约束谱聚类 算法模型[11]进行改进，并且根据约束集合内地标 点的关系，利用 Tarjan 算法[15]自动检测连通区域， 在每个连通区域内部动态调整近邻点，传递约束 关系，从而更新稀疏表示矩阵提高聚类准确率。 在 5 个大规模标准数据集上进行实验的结果表 明，本文算法对这些大规模数据具有较好适应 性，且在有效降低算法复杂度的同时，保证了约 束谱聚类算法结果的准确率。 1 算法基本原理 1.1 约束 NCut 算法 X = {xi} n i=1 , xi ∈ R d Dii = ∑ j Wi j L = I− D −1/2W D−1/2 对于数据集 ，数据之间的相 似度矩阵为 W，度矩阵 D 为对角阵，其内元素表 示为 ，规范化拉普拉斯矩阵表示为 ，I 表示单位矩阵。 标准 NCut 的目标函数为 argmin v∈Rn v T Lv, s.t.v T v = 1, v⊥1 (1) 式中 v 表示松弛化的类指示向量。 Q 假设已知“必连”约束集合 M 与“勿连”约束集 合 C，文献[11]根据约束信息生成约束矩阵 ，可 表示为 Qi j= 1, (xi , xj) ∈ M −1, (xi , xj) ∈ C 0, 无约束信息 (2) 通过式 (3) 来衡量 Q 中约束关系与 v 的一致程度： v TQv = ∑n i=1 ∑n j=1 vivjQi j (3) v ∈ R n Q ∈ R n×n xi xj Q Q v TQv Q v TQv ⩾ α 定义软约束 ， ，如果数据 和 是 同一类，那么 为正；否则为负。 的绝对值表示 约束权重， 的值越大，表明 v 与 中的约束信 息就越一致。基于上述软约束，不一定要严格满 足每个指定的约束条件，忽略部分约束信息可降 低计算开销，通过用户指定阈值来确定约束的下 界值，即 。 约束 NCut 的目标函数为 argmin v∈ n v T Lv, s.t.v TQv ⩾ α, v T v = 1, v⊥1 (4) O ( n 2 ) O ( n 3 ) 上述问题可转化为求解矩阵的特征向量[11] ， 但是空间和时间复杂度分别为 和 ，对于 大规模数据集，计算复杂度过高；而且不具备约 束传递功能，不能充分利用有限的约束信息。 1.2 依据稀疏表示的相似度矩阵 X ≈ YZ xi xˆi 蔡登等[14]提出基于图稀疏表示的谱聚类算 法，通过地标点的线性组合来实现所有数据点 X 的近似表示 。对于给定的任一数据点 ，其近似数据点 可以表示为 xˆi = ∑p j=1 Zjiyj (5) yj Y ∈ R d×p Zji Z ∈ R 式中： 是 的列向量， 是 p×n的第 j 行 第 i 列元素。 ·856· 智 能 系 统 学 报 第 13 卷
第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·
·858· 智能系统学报 第13卷 特征分解，大大降低算法的复杂度，能够很好地 根据lookupVec更新2； 适应于大规模数据集；另一方面，在连通区域内 end for 部进行约束关系传递，更新矩阵2，改进模型即式 5)依据约束关系生成约束矩阵Q,计算 (13)中S和A也随着更新，可以充分利用初始有限 3=22r,0=202r; 的约束信息，提高聚类的准确率。 6)求解Ox=ySx的最大特征值ymx; 为了求解式(13)，引入拉格朗日乘子，可扩展 7)ifB>ymax,类label的向量V=O; 约束NCut问题转化为 8)else求解式(16)的特征向量； A(u.Ap)=uAu-a(u'Qu-a)-u(u"Su-1)(14) 9)找出所有正特征值所对应的特征向量{u, 需要满足KKT条件，即 1 {u中每个元素乘 Au-AOu-uSu=0 (15) u Su uQu >a 10)去掉{u中与1S不正交的特征向量； uSu =1 I1)计算uA,寻找m个特征向量使Au,最 1TSu=0 小，m=min{k-1,lu,并把这些特征向量作为 ≥0 V的列向量； A(u"Qu-a)=0 12)计算V=2rV(I-VrAV),并对其进行k- 当A=0时，式(15)变为Au-S=0,意昧着并 means聚类。 没有考虑相关约束信息，所以为了充分使用约束 2.3算法复杂度分析 信息，只考虑>0的情况，即⑨u=a。 基于地标点近似表示的谱聚类算法需要构造 假设B=-兑式(15)变为 稀疏矩阵Z,该步骤的时间复杂度为O(pm),对矩 Au=a(0-BS)u 阵Z进行奇异值分解获得相似度矩阵的特征向 (16) 量，该步骤的时间复杂度为O(p3+p2m)；所提算法 通过求解式(16)的特征值和特征向量，计算复杂 也要构造矩阵Z,生成个连通区域进行近邻点 度远远降低。 约束关系传递的时间复杂度为O(⑩，计算矩阵 还需要考虑如何设置参数B和α，由于矩阵 S的时间复杂度为0(p2m,求解式(16)的特征值计 A是半正定的，可得 算复杂度为0(p),远远小于文献[11]约束谱聚类 F(@-B的)u=A(a-B)≥0 算法特征分解所需要的时间复杂度On),p≤n, 即参数B是a的下界值，a作为约束的下界值，所以 计算2Q2T的时间复杂度为O(kp2+kpm)。 只需要指定参数B值即可，参数B可调意味着算法 对噪声等额外信息的处理更加灵活。为了保证 3实验与分析 式(16)有i个有意义的特征向量，需要满足B<Y, 3.1实验环境 其中y,表示Ox=y3x的第i个最大的特征值。 为了验证本文算法的性能，选取规模较大的 算法结合稀疏表示与约束传递的半监督谱 数据集进行实验，依次为物体图像数据集 聚类算法 COIL100,人脸数据集CMU-PIE,手写数字数据 输入数据集X,约束集合M和C,聚类个 集USPS、MNIST和UCI标准库中的森林植被类 数k,参数B; 数据集CoverType,数据集的特性如表1所示。仿 输出类label。 真实验基于MATLAB2014b平台，计算机的硬件 1)将在约束集合内的p个点选为地标点，并 配置为Intel i7-4770CPU3.40GHz、16 GB RAM. 作为矩阵U的列向量； 表1实验数据集的特性 2)根据式(6)构造Z,并计算2=D-12Z Table 1 Experimental datasets features 3)使用Tarjan算法，根据地标点之间的约束 关系计算连通区域CC; 数据集 数据集个数 类 维数 4)for每个连通区域CCdo: COIL100 7200 100 1024 计算连通区域的邻接子矩阵L; USPS 9298 10 256 根据近邻点出现频率的次数构建向量Iook- CMU-PIE 11554 68 1024 upVec; MNIST 70000 10 784 根据式(9)将约束关系传递给该区域内剩余 CoverType 581012 7 54 数据点；
Zˆ Sˆ A 特征分解，大大降低算法的复杂度，能够很好地 适应于大规模数据集；另一方面，在连通区域内 部进行约束关系传递，更新矩阵 ，改进模型即式 (13) 中 和 也随着更新，可以充分利用初始有限 的约束信息，提高聚类的准确率。 为了求解式 (13)，引入拉格朗日乘子，可扩展 约束 NCut 问题转化为 Λ(u, λ, µ) = u TAu−λ ( u TQuˆ −α ) −µ ( u TSuˆ −1 ) (14) 需要满足 KKT 条件，即 Au−λQuˆ −µSuˆ = 0 (15) u TQuˆ ⩾ α u TSuˆ = 1 1 TSuˆ = 0 λ ⩾ 0 λ ( u TQuˆ −α ) = 0 λ = 0 Au−µSuˆ = 0 λ > 0 u TQuˆ = α 当 时，式 (15) 变为 ，意味着并 没有考虑相关约束信息，所以为了充分使用约束 信息，只考虑 的情况，即 。 β = − µ λ 假设 ，式 (15) 变为 Au = λ ( Qˆ −βSˆ ) u (16) 通过求解式 (16) 的特征值和特征向量，计算复杂 度远远降低。 还需要考虑如何设置参数 β 和α，由于矩阵 A 是半正定的，可得 λu T ( Qˆ −βSˆ ) u = λ(α−β) ⩾ 0 β α α β β β < γi γi Qˆ x = γSˆ x 即参数 是 的下界值， 作为约束的下界值，所以 只需要指定参数 值即可，参数 可调意味着算法 对噪声等额外信息的处理更加灵活。为了保证 式 (16) 有 i 个有意义的特征向量，需要满足 ， 其中 表示 的第 i 个最大的特征值。 算法 结合稀疏表示与约束传递的半监督谱 聚类算法 β 输入 数据集 X，约束集合 M 和 C，聚类个 数 k，参数 ； 输出 类 label。 1) 将在约束集合内的 p 个点选为地标点，并 作为矩阵 U 的列向量； Zˆ =D −1/2 2) 根据式 (6) 构造 Z，并计算 Z ； 3) 使用 Tarjan 算法，根据地标点之间的约束 关系计算连通区域 CC； 4) for 每个连通区域 CC do： 计算连通区域的邻接子矩阵 LTa； 根据近邻点出现频率的次数构建向量 lookupVec； 根据式 (9) 将约束关系传递给该区域内剩余 数据点； 根据 lookupVec 更新 Zˆ ； end for Q Sˆ = Zˆ Zˆ T Qˆ = ZQˆ Zˆ T 5) 依据约束关系生成约束矩阵 ，计算 ， ； Qˆ x = γSˆ 6) 求解 x的最大特征值 γmax； 7) if β ⩾ γmax，类 label 的向量 V =Ø； 8) else 求解式 (16) 的特征向量 u； { u + i } { u + i } √ 1 uiSuˆ i 9) 找出所有正特征值所对应的特征向量 ， 中每个元素乘 ； { u + i } 1 10) 去掉 中与 TSˆ不正交的特征向量； u T i Aui u T i Aui m = min{ k−1, { u + i } } V 11) 计算 ，寻找 m 个特征向量使 最 小 ， ，并把这些特征向量作为 的列向量； V (r) = Zˆ TV ( I−V TAV) 12) 计算 ，并对其进行 kmeans 聚类。 2.3 算法复杂度分析 Z O(pn) O ( p 3 + p 2n ) |H| O(r|H|) Sˆ O ( p 2n ) O ( p 3 ) O(n 3 ), p ≪ n ZQˆ Zˆ T O ( kp2 +kpn) 基于地标点近似表示的谱聚类算法需要构造 稀疏矩阵 ，该步骤的时间复杂度为 ，对矩 阵 Z 进行奇异值分解获得相似度矩阵的特征向 量，该步骤的时间复杂度为 ；所提算法 也要构造矩阵 Z，生成 个连通区域进行近邻点 约束关系传递的时间复杂度为 ，计算矩阵 的时间复杂度为 ，求解式 (16) 的特征值计 算复杂度为 ，远远小于文献[11]约束谱聚类 算法特征分解所需要的时间复杂度 ， 计算 的时间复杂度为 。 3 实验与分析 3.1 实验环境 为了验证本文算法的性能，选取规模较大的 数据集进行实验，依次为物体图像数据 集 COIL100，人脸数据集 CMU-PIE，手写数字数据 集 USPS、MNIST 和 UCI 标准库中的森林植被类 数据集 CoverType，数据集的特性如表 1 所示。仿 真实验基于 MATLAB2014b 平台，计算机的硬件 配置为 Intel i7-4770 CPU 3.40 GHz、16 GB RAM。 表 1 实验数据集的特性 Table 1 Experimental datasets features 数据集 数据集个数 类 维数 COIL100 7 200 100 1 024 USPS 9 298 10 256 CMU-PIE 11 554 68 1 024 MNIST 70 000 10 784 CoverType 581 012 7 54 ·858· 智 能 系 统 学 报 第 13 卷
第5期 赵晓晓，等：结合稀疏表示与约束传递的半监督谱聚类算法 ·859· 本文算法和文献[11]的约束谱聚类方法CSP, PC算法相比，本文算法在CMU-PIE数据集上 文献[14]的基于地标点采样的快速谱聚类算法 ACC、NMⅡ分别提升了79.12%和38.58%.在Cov- LSC-R和LSC-K,文献[I5]所提出的针对大规模数 erType数据集上ACC和NMI分别提升了15.02% 据集的半监督谱聚类算法SC-PC进行对比，LSC- 和39.94%。因为在处理高维数据时，采用稀疏表 R是通过随机采样来获取p个地标点，LSC-K是 示能够过滤一些异常点和噪声，同时指定约束下 利用k-means算法来获得p个地标点。须指出， 界，可去除一些噪声等约束关系的负面影响。因 由于CSP算法在CMU-PIE、MNIST和Cover- 此，引入约束信息来改变谱聚类算法的目标函 Type数据集上计算负担过大，并没有进行相关实 数，并通过在连通区域内进行约束关系传递，能 验的比较。 够有效提高聚类的准确率。 鉴于比较的公平性，具体的参数设置如下：其 表2各数据集实验结果 中文献[14-15]和本文算法的地标点个数p均设置 Table 2 Experimental results of different datasets 为1000，所有算法中k-means部分的迭代次数均 数据集 算法 ACC NMI 时间/s 设置为500，所有稀疏表示矩阵构造过程中的近 CSP 0.67390.8237 19656.02 邻点个数r设置为5。约束的下界即参数B=Boyk-1, 其中A=05+04x号为0：=5：的第k-1个最 LSC-K0.54560.7632 4.13 COIL100 LSC-R0.4896 0.7315 2.33 大的特征值。 SC-PC 0.59680.7718 2.59 通过数据集中每个样本预定义的类标签来实 现对聚类结果的评价，采用聚类准确率ACC和归 本文 0.66600.7975 3.51 一化互信息NM两种度量指标对聚类结果进 CSP 0.86440.8049 26932.75 行评估和比较分析。两个评价指标的取值范围均 LSC-K0.77530.7915 1.19 是在0~1之间，值越大表示聚类效果越好。 USPS LSC-R0.75240.7541 0.62 3.2实验分析 SC-PC 0.80740.7697 0.75 各种算法在上述数据集的实验结果如表2 本文 0.84350.7731 1.88 所示。 CSP 根据表2可以看出，约束谱聚类算法CSP在 LSC-K 0.0956 0.2126 COL100和USPS两个数据集上的ACC和NMI 5.39 均取得最佳结果，因为其考虑引入约束矩阵建立 CMU-PIE LSC-R 0.09360.2148 4.48 约束优化问题，提高聚类准确率，但是在上述两 SC-PC 0.17240.2623 4.84 个数据集上的运行时间太长，耗时将近5~7h,对 本文 0.30880.3635 6.45 于更大的数据集CMU-PIE、MNIST和Cover- CSP Type数据集，计算负担过大，没能进行验证。本 LSC-K0.72700.7222 12.58 文算法在COIL100和USPS数据集的ACC分别 MNIST LSC-R0.5890 0.5911 8.80 为0.6660和0.8435，NMI指标分别为0.7975和 SC-PC 0.73440.6978 11.08 0.7731,和CSP相比稍有降低；但从运行时间上， 本文 0.78390.6728 24.98 本文算法的运行时间仅在秒级别，耗时分别为 CSP 3.51s和1.88s,远远少于CSP的运行时间，而且 在包含581012个样本的大规模CoverType数据 LSC-K 0.2552 0.0673 355.11 集上运行时间只需要747.36s,所以本文算法基于 CoverType LSC-R 0.22900.0681 78.18 稀疏表示矩阵来建立相似度矩阵，降低了矩阵分 SC-PC0.2563 0.0721 149.71 解的复杂度，提高了半监督聚类算法的可扩展性。 本文0.29480.1009 747.36 另一方面，本文算法和LSC-K、LSC-R、SC-PC 三种均为提升谱聚类的效率的算法，即快速谱聚 为了分析初始约束信息对聚类结果的影响， 类算法相比，在准确率ACC和归一化互信息NM 添加了地标点个数p(对应半监督聚类中能获取的 两个指标上有所提高，且在CMU-PIE和Cover- 初始约束信息)对聚类指标影响的对比实验。同 Type数据集上两个指标具有明显的提升；和SC 样，CSP算法只在USPS和COIL1O0两个数据集
本文算法和文献[11]的约束谱聚类方法 CSP， 文献[14]的基于地标点采样的快速谱聚类算法 LSC-R 和 LSC-K，文献[15]所提出的针对大规模数 据集的半监督谱聚类算法 SC-PC 进行对比，LSCR 是通过随机采样来获取 p 个地标点，LSC-K 是 利用 k-means 算法来获得 p 个地标点。须指出， 由于 CSP 算法在 CMU-PIE、MNIST 和 CoverType 数据集上计算负担过大，并没有进行相关实 验的比较。 β = β0γk−1 β0 = 0.5+0.4× p n γk−1 Qˆ x = γSˆ x k−1 鉴于比较的公平性，具体的参数设置如下：其 中文献[14-15]和本文算法的地标点个数 p 均设置 为 1 000，所有算法中 k-means 部分的迭代次数均 设置为 500，所有稀疏表示矩阵构造过程中的近 邻点个数 r 设置为 5。约束的下界即参数 ， 其中 ， 为 的第 个最 大的特征值。 通过数据集中每个样本预定义的类标签来实 现对聚类结果的评价，采用聚类准确率 ACC 和归 一化互信息 NMI 两种度量指标[14]对聚类结果进 行评估和比较分析。两个评价指标的取值范围均 是在 0~1 之间，值越大表示聚类效果越好。 3.2 实验分析 各种算法在上述数据集的实验结果如表 2 所示。 根据表 2 可以看出，约束谱聚类算法 CSP 在 COIL100 和 USPS 两个数据集上的 ACC 和 NMI 均取得最佳结果，因为其考虑引入约束矩阵建立 约束优化问题，提高聚类准确率，但是在上述两 个数据集上的运行时间太长，耗时将近 5~7 h，对 于更大的数据集 CMU-PIE、MNIST 和 CoverType 数据集，计算负担过大，没能进行验证。本 文算法在 COIL100 和 USPS 数据集的 ACC 分别 为 0.666 0 和 0.843 5，NMI 指标分别为 0.797 5 和 0.773 1，和 CSP 相比稍有降低；但从运行时间上， 本文算法的运行时间仅在秒级别，耗时分别为 3.51 s 和 1.88 s，远远少于 CSP 的运行时间，而且 在包含 581 012 个样本的大规模 CoverType 数据 集上运行时间只需要 747.36 s，所以本文算法基于 稀疏表示矩阵来建立相似度矩阵，降低了矩阵分 解的复杂度，提高了半监督聚类算法的可扩展性。 另一方面，本文算法和 LSC-K、LSC-R、SC-PC 三种均为提升谱聚类的效率的算法，即快速谱聚 类算法相比，在准确率 ACC 和归一化互信息 NMI 两个指标上有所提高，且在 CMU-PIE 和 CoverType 数据集上两个指标具有明显的提升；和 SCPC 算法相比，本文算法在 CMU-PIE 数据集上 ACC、NMI 分别提升了 79.12% 和 38.58%，在 CoverType 数据集上 ACC 和 NMI 分别提升了 15.02% 和 39.94%。因为在处理高维数据时，采用稀疏表 示能够过滤一些异常点和噪声，同时指定约束下 界，可去除一些噪声等约束关系的负面影响。因 此，引入约束信息来改变谱聚类算法的目标函 数，并通过在连通区域内进行约束关系传递，能 够有效提高聚类的准确率。 为了分析初始约束信息对聚类结果的影响， 添加了地标点个数 p(对应半监督聚类中能获取的 初始约束信息) 对聚类指标影响的对比实验。同 样，CSP 算法只在 USPS 和 COIL100 两个数据集 表 2 各数据集实验结果 Table 2 Experimental results of different datasets 数据集 算法 ACC NMI 时间/s COIL100 CSP 0.673 9 0.823 7 19 656.02 LSC-K 0.545 6 0.763 2 4.13 LSC-R 0.489 6 0.731 5 2.33 SC-PC 0.596 8 0.771 8 2.59 本文 0.666 0 0.797 5 3.51 USPS CSP 0.864 4 0.804 9 26 932.75 LSC-K 0.775 3 0.791 5 1.19 LSC-R 0.752 4 0.754 1 0.62 SC-PC 0.807 4 0.769 7 0.75 本文 0.843 5 0.773 1 1.88 CMU-PIE CSP — — — LSC-K 0.095 6 0.212 6 5.39 LSC-R 0.093 6 0.214 8 4.48 SC-PC 0.172 4 0.262 3 4.84 本文 0.308 8 0.363 5 6.45 MNIST CSP — — — LSC-K 0.727 0 0.722 2 12.58 LSC-R 0.589 0 0.591 1 8.80 SC-PC 0.734 4 0.697 8 11.08 本文 0.783 9 0.672 8 24.98 CoverType CSP — — — LSC-K 0.255 2 0.067 3 355.11 LSC-R 0.229 0 0.068 1 78.18 SC-PC 0.256 3 0.072 1 149.71 本文 0.294 8 0.100 9 747.36 第 5 期 赵晓晓，等：结合稀疏表示与约束传递的半监督谱聚类算法 ·859·