基于k-近邻局部线性邻域重建的多视角聚类算法.pdf

第3 6卷第3期纺织高校基础科学学报V o l.3 6,N o.3 2 0 2 3年6月B A S I C S C I E N C E S J O U R N A L O F T E X T I L E U N I V E R S I T I E SJ u n.,2 0 2 3 引文格式:马盈仓,吴也凡,邢志伟,等.基于k-近邻局部线性邻域重建的多视角聚类算法J.纺织高校基础科学学报,2 0 2 3,3 6(3):7 5-8 3.MA Y i n g c a n g,WU Y e f a n,X I NG Z h i w e i,e t a l.M u l t i-v i e w c l u s t e r i n g b a s e d o n k-n e a r e s t n e i g h b o r s l o c a l l i n e a r r e c o n s t r u c t i o nJ.B a s i c S c i e n c e s J o u r n a l o f T e x t i l e U n i v e r s i t i e s,2 0 2 3,3 6(3):7 5-8 3.收稿日期:2 0 2 2-1 2-1 8 修回日期:2 0 2 3-0 1-0 3基金项 目:国 家 自 然 科 学 基 金(6 1 9 7 6 1 3 0);陕 西 省 重 点 研 发 计 划 项 目(2 0 1 8 KW-0 2 1);陕 西 省 自 然 科 学 基 金(2 0 2 2 K RM 1 7 0)通信作者:马盈仓(1 9 7 2-),男,教授,博士,研究方向为不确定性推理理论及机器学习。E-m a i l:m a y i n g c a n g x p u.e d u.c n基于k-近邻局部线性邻域重建的多视角聚类算法马盈仓,吴也凡,邢志伟,袁 林(西安工程大学 理学院,陕西 西安 7 1 0 6 0 0)摘 要 多视图聚类旨在利用不同视图间互为差异、互相补充的信息对数据对象进行聚类,如何融合不同视角的数据是多视角聚类算法的重要问题之一。为了能更准确有效地刻画视角间的相似关系,提出一种基于k-近邻局部线性邻域重建的多视角聚类算法。首先,利用数据点间的距离分配概率近邻,得到各视角数据对应的相似矩阵;其次,通过引入k-近邻,对各视角相似矩阵进行局部线性邻域重建后融合为统一的相似矩阵;同时,引入H S I C刻画不同视角的多样性。通过将统一图的学习与多样性学习整合在统一的框架中,本模型有能力输出一个包含了各视图多样信息的融合图。通过交替迭代算法,所提模型可以被很好地优化。多个公开数据集上的对比实验证明了所提出算法的有效性优于其他已有算法。关键词 多视角聚类;图学习;k-近邻;局部线性;希尔伯特-施密特独立准则开放科学(资源服务)标识码(O S I D)中图分类号:T P 1 8 1 文献标志码:AD O I:1 0.1 3 3 3 8/j.i s s n.1 0 0 6-8 3 4 1.2 0 2 3.0 3.0 1 1M u l t i-v i e w c l u s t e r i n g b a s e d o n k-n e a r e s t n e i g h b o r s l o c a l l i n e a r r e c o n s t r u c t i o nMA Y i n g c a n g,WU Y e f a n,X I NG Z h i w e i,Y U AN L i n(S c h o o l o f S c i e n c e,X ia n P o l y t e c h n i c U n i v e r s i t y,X ia n 7 1 0 6 0 0,C h i n a)A b s t r a c t M u l t i-v i e w c l u s t e r i n g i s a n i m p o r t a n t u n s u p e r v i s e d m a c h i n e l e a r n i n g m e t h o d a n d d a t a m i n i n g t e c h n o l o g y,w h i c h a i m s t o d i v i d e t h e d a t a o b j e c t s b y u s i n g d i s t i n c t i v e a n d c o m p l e m e n t a r y i n f o r m a t i o n a m o n g d i f f e r e n t v i e w s,f o r m u l t i-v i e w c l u s t e r i n g,i t i s a n i m p o r t a n t i s s u e t o e f f e c t i v e l y i n t e g r a t e t h e i n f o r m a t i o n f r o m d i f f e r e n t v i e w s.I n o r d e r t o e f f i c i e n t l y d e p i c t s i m i l a r i t y o f e a c h v i e w,t h e a l g o r i t h m t e r m e d m u l t i-v i e w c l u s t e r i n g b a s e d o n k-n e a r e s t n e i g h b o r s l o c a l l i n e a r r e c o n-s t r u c t i o n w a s p r o p o s e d.F i r s t,t h e s i m i l a r i t y g r a p h o f e a c h v i e w w a s l e a r n e d b a s e d o n t h e p r o b a b i-l i s t i c n e i g h b o r s.S e c o n d,b y r e c o n s t r u c t i n g t h e l o c a l l i n e a r n e i g h b o r s t r u c t u r e s o f e a c h v i e w s s i m i-l a r i t y g r a p h,t h e s h a r e d g r a p h c a n b e f u r t h e r a c q u i r e d.M e a n w h i l e,t h e H i l b e r t-S c h m i d t I n d e p e n d-e n c e C r i t e r i o n(H S I C)w a s u t i l i z e d t o e x t r a c t t h e d i v e r s i t y i n f o r m a t i o n o f d i f f e r e n t v i e w s.A f t e r i n t e g r a t i n g t h e t h r e e p a r t s i n t o a u n i f i e d f r a m e w o r k,t h e d e v e l o p e d a l g o r i t h m e n a b l e s t o p r o d u c e a s h a r e d g r a p h w i t h d i v e r s i t y i n f o r m a t i o n f r o m m u l t i p l e v i e w s.T h e p r o p o s e d m o d e l c a n b e e f f i-c i e n t l y s o l v e d b y t h e a l t e r n a t i v e i t e r a t i o n s t r a t e g y.E x t e n s i v e e x p e r i m e n t s o n s e v e r a l b e n c h m a r k d a t a s e t s d e m o n s t r a t e t h e s u p e r i o r i t y o f t h e d e v e l o p e d a l g o r i t h m t o t h e s t a t e-o f-t h e-a r t a l g o-r i t h m s.K e y w o r d s m u l t i-v i e w c l u s t e r i n g;g r a p h l e a r n i n g;k-n e a r e s t n e i g h b o r;l o c a l l i n e a r;H i l b e r t-S c h m i d t i n d e p e n d e n c e c r i t e r i o n 0 引 言 聚类分析是机器学习领域的一个重要分支,是人们认识和探索数据之间内在联系的有效手段1。早期的聚类算法只对单一视角数据进行聚类,但由于单视角聚类在处理问题时不够全面,忽略了数据间的潜在信息无法全面有效地处理问题。因此利用多种视角和多种特征的多视角聚类应运而生2。但简单地堆积各视角数据不具备可解释性,因此需要利用不同数据的异构和多个视角的信息,获得更准确的聚类结果。常见的多视角聚类可分为以下3类:基于子空间学习的多视角聚类3-5、基于二进制编 码 学 习 的 模 型6-8、基 于 图 学 习 的 多 视 角聚类9-1 1。基于图的多视角聚类算法因具有高效简单等特点而得到广泛应用,这类方法是为了找到一个能被所有视角共享的统一相似矩阵。因为统一相似矩阵直接影响到特征向量的获取,并影响到最终聚类的结果,因此多视角聚类中构造合适相似矩阵是研究的热点问题之一1 2。文献1 3 认为各视角数据应具有相同的潜在结构,并使用H a d a m a r d积将各视角的相似图合成为统一的图。文献1 4 指出各视角的相似矩阵可分解为一致性和不一致性2部分,进一步将每个视角的一致性部分融合,从而得到统一的相似矩阵。文献1 5 同时考虑各视角数据对应子空间之间的互补性和一致性,并将其集合在一个框架中,最终求各视角对应子空间的平均值得到统一相似矩阵。为了挖掘各视角间的潜在信息,文献1 6 提 出 多 样 性 诱 导 的 子 空 间 学 习 方 法,使 用H S I C(H i l b e r t-S c h m i d t i n d e p e n d e n c e c r i t e r i o n)来描述各视角数据对应子空间之间的依赖性,获得各视图之间的互补信息。虽然这些基于图的多视角聚类算法通过不同的方法获得统一的相似矩阵,也取得了较好的结果,但它们没有从局部邻域的角度去构造相似矩阵,而局部邻域信息能更准确有效地刻画视角间的相似关系。针对以上问题,本文利用各视角数据构建不同视角的相似矩阵,再利用k-近邻思想1 7将不同视角的相似矩阵融合为统一相似矩阵,最后采用H i l-b e r t-S c h m i d t独立准则(H S I C)保证各视角相似矩阵尽可能具有多样性1 8,最终得到基于k-近邻局部线性邻域重建的多视角聚类算法,即k-L RMC算法。并通过在多个经典数据集上的对比实验证明其可行性。1预备知识1.1符号说明本文使用大写字母表示矩阵,小写字母表示向量。对于矩阵B,其转置表示为BT,F r o b e n i u s 范数表示为BF。对于方阵B,t r(B)表示它的迹,bi表示矩阵B的第i列。对于向量b,b2表示它的l2范数。In表示单位阵,1n表示元素均为1的n维列向量。1.2 单视角聚类1.2.1 C ANC AN将相似矩阵学习与数据聚类集合在同一个框架中。给定一个数据集X=x1,x2,xn Rdn,S Rnn是以n个数据点为节点的相似矩阵,该算法模型如下1 9:m i nSni,j=1xi-xj22si j+s2i j s.t.i,sTi1=1,0si1,r a n k(Ls)=n-c(1)式中:是正则化参数;Ls=Ds-ST+S2为拉普拉斯矩阵;Ds Rnn为对角矩阵,其第i个对角元素为j(si j+sj i)/2。该模型对通过原始数据学得的相似矩阵的拉普拉斯矩阵施加秩约束:r a n k(Ls)=67 纺 织 高 校 基 础 科 学 学 报 第3 6卷n-c,使学 习到的相似 矩阵具有恰 好c个连 通分支。1.2.2 子空间聚类给定一个数据集X=x1,x2,xn Rdn,其中每一列xi为一个样本向量。通过解决以下优化问题来寻找基于自表示的子空间聚类1 5。m i nZ,EEk+Zls.t.X=X Z+E,d i a g(Z)=0(2)式中:X=X Z+E是自表示模型,Z=z1,znRnn为自表示矩阵。k和 l是2个合适的范数,是权衡参数。1.3 多视角聚类1.3.1 ML AN在多 视 图 聚 类 和 自 适 应 邻 域 半 监 督 分 类(ML AN)中,给 定 多 视 角 数 据 集X=X(1),X(m),其中X(v)=x(v)1,x(v)n Rdvn是第v个视角上的数据,n为样本个数,dv为对应的特征维数。ML AN算法模型为1 9m i nSvw(v)i,jx(v)i-x(v)j22si j+S2Fs.t.sTi1=1,0si j1,r a n k(Ls)=n-c(3)将K y F a ns定理1 9应用于式(3)来解决秩约束r a n k(Ls)=n-c。1.3.2 图融合在文 献 2 0 中,通 过 近 似 平 均 各 视 角 的 图1nmi=1S(v)学习统一相似图S,即m i nSS-1mmv=1S(v)2Fs.t.S1n=1n,S0(4)式中:m是视图个数;S(v)表示第v个视角的相似矩阵。2模型建立及求解2.1 模型建立2.1.1 基于局部距离构造相似矩阵通过对每一个数据点xi分配基于局部距离的最优概率邻域构造各视角相似矩阵,本文使用欧式距离作为距离度量。对于给定的多视角数据X=X(1);X(m),以及任意数据点x(v)i的每一个与它连接的点x(v)j都有1个概率意义的度量权重值s(v)i j。S(v)=(s(v)i j)Rnn,表示x(v)i与x(v)j之间的概率近邻。通常,一个更小的距离x(v)i-x(v)j22应当分配一个更大的概率s(v)i j,概率与距离之间呈负相关,因此确定各视角概率s(v)i j的方法是解决 m i nS(v)ni=1nj=1x(v)i-x(v)j22s(v)i js.t.S(v)T1n=1n,S(v)0,v=1,m(5)等问题。2.1.2 相似矩阵多样性约束项为了降低各视角相似矩阵间的依赖性,提高独立性,式(5)基于每个数据点的局部距离得到各视角数据对应的相似矩阵。通过挖掘各视角相似矩阵间的互补信息,得到更精确更独立的相似矩阵,本文借助H S I C评估标准来评估S(v)和S(w)之间的依赖性1 6。记为H S I C(S(v),S(w)使用内积核K(v)=S(v)TS(v)来计算H S I C,即H S I C(S(v),S(w)=t r(HK(v)HK(w)其中,H=In-1n1n1Tn为中心化矩阵。多视角相似矩阵的多样性约束项为mwvH S I C(S(v),S(w)(6)2.1.3 基于k-近邻局部线性重建融合相似矩阵部分之前的研究是基于图的多视角聚类算法,通过原始数据构造每个视角相似矩阵,再对各视角相似矩阵求平均值1 5-1 6学习出统一相似矩阵。虽然这些方法已经取得不错的性能,但没有提取各视角相似矩阵中最有效的部分信息。为了克服以上全局线性表示的局限,本节引入k-近邻。首先,计算每个数据点的k-近邻,并对各视角相似矩阵用其k-近邻数据点进行局部线性加权表示2 1。这样,可以有效发挥数据点的局部作用,剔除大量不相关点,使计算更为简便,保证各视角相似矩阵提取局部有效信息后再融合为统一的相似矩阵2 2。此外,当选取适当少的k近邻点时,可剔除大量样本点,计算便捷;当选取适当多的k近邻点时,可剔除一些噪声点,使算法更具鲁棒性2 3。基于k-近邻对各视角相似矩阵S(v)进行局部线性重建的模型为m i nW(v)ni=1si-mv=1jNk(x(v)i)w(v)i js(v)j2F+mv=1ni=1w(v)i22s.t.ST1n=1n,S 0,W(v)1n=1n,W(v)0(7)式中:W=W(1),W(m)为线性重构系数矩阵;W(v)=(w(v)i j)Rnn表示在S(v)=(s(v)i j)Rnn上对应权值;mv=1ni=1w(v)i22为自表示矩阵W(v)的正77第3期 马盈仓,等:基于k-近邻局部线性邻域重建的多视角聚类算法则项,引入正则项为了避免W(v)的平凡解,即只与x(v)i最 近 邻 的j对 应 的w(v)i j为1,其 余 均 为0;Nk(x(v)i)表示样本点x(v)i的k近邻构成的集合;jNk(x(v)i)表示x(v)i包含自身的k个近邻所在位置j。2.1.4 目标函数结合以上3部分,将基于局部距离构造相似矩阵、相似矩阵多样性约束项和基于k-近邻局部线性重建融合相似矩阵统一在同一个框架中,提出如下模型,即m i nS,S(v),W(v)mv=1ni=1nj=1x(v)i-x(v)j22s(v)i j+1ni=1si-mv=1jNk(x(v)i)w(v)i js(v)j2F+2mwvH S I C(S(v),S(w)+3mv=1ni=1w(v)i22s.t.ST1n=1n,S0,S(v)T1n=1n,S(v)0,W(v)1n=1n,W(v)0(8)式中:目标函数的第一项是基于局部距离构造相似矩阵项,用于学习各视角数据对应的相似矩阵;第二项是基于k-近邻局部线性重建融合相似矩阵项,对各视角相似矩阵进行k-近邻局部线性表示后融合;第三项是相似矩阵多样性约束项,确保各视角相似矩阵的多样性;第四项是自表示矩阵正则项,用于避免自表示矩阵平凡解;1、2和3表示权衡参数。2.2 模型求解 关于2.1.4节中目标函数(8),采用交替迭代优化算法求解。2.2.1 固定W(v)、S(v),更新SS*=a r g m i n S1ni=1si-mv=1jNk(x(v)i)w(v)i js(v)j2Fs.t.ST1n=1n,S0(9)关于式(9)S的求解,可以分解为以下n个子问题:m i nsisi-m v=1jNk(x(v)i)w(v)i js(v)j2Fs.t.sTi1n=1,0si j1,i=1,n(1 0)问题(1 0)可以用文献2 4 中算法进行求解。2.2.2 固定S、S(v),更新W(v)W(v)*=a r g m i nW(v)1ni=1si-mv=1jNk(x(v)i)w(v)i js(v)j2F+3mv=1ni=1w(v)i22s.t.W(v)1n=1n,W(v)0(1 1)将近邻数记为k,定义矩阵D(v)i=si-s(v)Ni(1),si-s(v)Ni(2),si-s(v)Ni(k)Rnk可求解W(v)的第i个行向量,即 w(v)i=a r g m i n w(v)i1w(v)iG(v)iw(v)Ti+3w(v)iI w(v)Ti=a r g m i n w(v)iw(v)i(1G(v)i+3I)w(v)Tis.t.w(v)i1k=1,w(v)i0(1 2)其中G(v)i=D(v)TiD(v)iRkk,式(1 2)变为二次规划问题,利用文献2 2 的方法求解。2.2.3 固定S、W(v),更新S(v)S(v)*=a r g m i nS(v)mv=1ni=1nj=1x(v)i-x(v)j22s(v)i j+1ni=1si-mv=1jNk(x(v)i)w(v)i js(v)j2F+2mwvH S I CS(v),S(w)s.t.S(v)T1n=1n,S(v)0(1 3)为了便于表示,忽略H S I C的比例因子(n-1)-2,式(1 3)可写为如下矩阵形式:S(v)*=a r g m i nS(v)mv=1t rB(v)TS(v)+1S-mv=1S(v)W(v)T22+2mv=1t rS(v)KvS(v)T (1 4)其中B(v)=b(v)i j Rnn,b(v)i j=x(v)i-x(v)j22.Kv=Hmw=1;wvK(w)H对于某一视图v,式(1 4)可写为S(v)*=a r g m i nS(v)t r-21W(v)TST+21W(v)T mwvW(w)S(w)T +B(v)T S(v)+T rS(v)1W(v)TW(v)+2Kv S(v)T =a r g m i n S(v)t rBTsS(v)+t rS(v)Q S(v)T (1 5)式中:Bs=-21S W(v)+21mwvS(w)W(w)T W(v)+B(v),Q=1W(v)TW(v)+2Kv将式(1 5)写为向量形式,即s(v)i*=m i ns(v)Ti1n=1B sTi+2njiQi js(v)Tj s(v)i+Qi is(v)Tis(v)i(1 6)式(1 6)进一步可写为式(1 7),并根据文献2 4 中算法1的方法求解:m i ns(v)is(v)i+B si+2njiQi js(v)j2Qi i22(1 7)87 纺 织 高 校 基 础 科 学 学 报 第3 6卷2.3 算法流程根据2.2模型求解,总结梳理k-L RMC算法流程如下。输输入入 数据集X=X(1);X(m),参数1、2与3,近邻个数k。初初始始化化 构造具有k个近邻的相似矩阵S(v),在k个近邻处取值1/k其余位置为0的自表示矩阵W(v):1)F o r t=1:最大迭代次数2)通过求解式(1 0)更新S3)F o r v=1m4)根据式(1 2)更新W(v)的每一列;5)E n d6)F o r v=1m7)通过求解式(1 7)更新S(v);8)E n d9)I f a b s(o b j_f c n(t)-o b j_f c n(t-1)1 e-5;/o b j_f c n表示目标函数值1 0)b r e a k;1 1)E n d1 2)E n d输输出出 各视角相似矩阵S(v),统一相似矩阵S,各视角自表示矩阵W(v)。3实验评估3.1 实验设置3.1.1 数据集描述为 了 验 证k-L RMC算 法 的 聚 类 效 果,选 取NU S-W I D E2 5,M S R C-v 12 6,p r o k a r y o t i c2 7,h a n d-w r i t t e n2 8 4个公开数据集进行实验。NU S-W I D E由8 1个目标的2 6 9 6 4 8个影像组成,从所有的8个类别中选择了1 6 0 0个样本,每幅图像由CH,CM 5 5,C O R R,E DH,WT,B o W 等6个不同的特征表示。M S R C-v 1数据集由属于8类的2 4 0张照片组成,每类有3 0张照片。背景类的图片被剔除,剩余的自行车、人脸、汽车、牛、树、建筑和飞机这7类图片组成数据集。P r o k a r y o t i c是一种可用于遗传分析的多视角数据集,包括4类5 5 1种原核生物。H a n d w r i t t e n 手写体包含2 0 0 0张从“0”到“9”的1 0个数字类的图像,用于手写体数字识别。包含P I X、F OU、F A C、Z E R、KA R和MO R等6个视角。3.1.2 对比方法为了证实本文算法的优越性,将k-L RMC与以下5种多视角算法进行比较,其中配置的参数根据相应文献中的建议选取。LM S C1 0:固定潜在表示维数K=1 0 0,参数:0.0 0 1,0.0 1,0.1,1,1 0,1 0 0,1 0 0 0。M S C-I A S1 1:模型的3个参数,完整潜在空间维数d1 0 0,3 0 0,5 0 0,7 0 0,1 0 0 0,近邻数k1,3,5,7,9,参 数20.0 0 1,0.0 0 5,0.0 1,0.0 5,0.1,0.5,1,5,1 0,3个参数通过网格搜索获得最佳实验结果。E CM S C1 5:对于参数1=1-t,2=和3=t-1。其中=1.2,0.2,0.4,0.6,0.8,1,t=1,2,T,T为迭代次数。D i M S C1 6:对于参数s0.0 1,0.0 3,0.0 5,0.0 7,0.0 9,24 0,8 0,1 2 0,1 6 0,2 0 0通过网格搜索获得最佳实验结果。S M S C2 9:该算法无参数。LM S C和M S C-I A S均通过原始多视角数据学习潜在空间并得到子空间或相似矩阵进行聚类。E CM S C和D i M S C均通过挖掘各视角子空间互补信息获得更精确的聚类结果。S M S C将非负嵌入和谱嵌入集成到一个统一的框架中,通过非负嵌入直接获得聚类结果。3.1.3 评估指标为了衡量聚类效果,实验使用4种聚类评价准则,分别为聚类精度(a c c u r a c y,A C C)3 0、标准化互信息(n o r m a l i z e d m u t u a l i n f o r m a t i o n,NM I)3 1、F值(F-s c o r e,F)3 2和R a n d指 数(r a n d i n d e x,R I)3 1。每个指标值越高,说明聚类结果越好。实验环境 为 M i c r o s o f t W i n d o w s 1 0系 统,处 理 器 为AMD R y z e n 7 4 8 0 0 H w i t h R a d e o n G r a p h i c s 2.9 0 GH z,内存为1 6.0 G i B(1 5.4 G i B可用),编程软件M a t l a b R 2 0 1 9 b。3.2 实验结果3.2.1 参数敏感性分析根据算法k-L RMC,需要确定相似矩阵融合参数1、多样性约束项参数2和自表示矩阵正则项参数33个参数。本节分析这3个参数在不同数据集中的敏感程度。首先考察模型中参数1、2对A C C的影响,设置参数3=1,1、20.0 0 1,0.0 1,0.1,1,1 0,1 0 0,1 0 0 0。其次考 察模型中参数3对A C C的影响,设置参数1=2=1,30,1,2,3,4,5,6,7,8,9,1 0。此外,近邻数k被指定为1 5。4个数据集上不同参数取值对聚类精度的影响如图1所示。97第3期 马盈仓,等:基于k-近邻局部线性邻域重建的多视角聚类算法 (a)NU S-W I D E (b)M S R C-v 1 (c)p r o k a r y o t i c (d)h a n d w r i t t e n图1 数据集的调节参数1和2的A C C值F i g.1 A C C v a l u e o f t h e p a r a m e t e r o f 1a n d2 d a t a s e t s 由图1可看出,在数据集NU S-W I D E上,当参数1、2分别取0.0 1、0.0 1时,A C C最高。在数据集M S R C-v 1上,A C C随参数1、2的改变有较大波动,随着1增大与2减小,A C C递减;当参数1、2分别 取0.0 0 1、0.0 0 1时,A C C取 到 最 高 值0.8 8。在数据集p r o k a r y o t i c上,当参数1、2分别取0.1、0.0 0 1时,A C C最高,A C C大多在0.40.5上下波动。在数据集h a n d w r i t t e n上,A C C随参数1、2的改变有较大波动,当参数1、2分别取0.0 1,0.1时,A C C取到最高值0.8 6。表1 各算法在4个公开数据集上聚类性能比较(平均值标准差)%T a b.1 C o m p a r i s o n o f c l u s t e r i n g p e r f o r m a n c e v a l u e o f d i f f e r e n t a l g o r i t h m s i n f o u r m u l t i p l e d a t a s e t s(m e a n s t a n d a r d)%数据集算法A C CNM IFR INU S-W I D ELM S C3 0.9 32.1 41 7.8 52.1 42 2.7 71.2 97 9.9 60.4 9M S C-I A S2 8.3 61.6 82 0.4 01.5 92 4.7 30.5 76 7.2 27.4 9E CM S C3 3.0 90.2 61 9.1 90.1 13 3.6 80.2 71 3.8 80.0 9S M S C3 3.7 50.0 01 9.7 20.0 02 6.1 20.0 01 3.6 70.0 0D i M S C1 7.2 80.2 72.0 90.0 61 3.1 90.0 37 8.1 70.0 4k-L RMC3 6.5 22.4 12 1.2 11.5 72 6.0 92.3 78 0.4 90.5 0M S R C-v 1LM S C7 9.0 51.5 67 0.4 41.9 36 9.4 72.4 29 1.1 70.5 9M S C-I A S3 0.1 91.5 61 9.9 42.9 92 0.6 01.7 27 6.6 80.5 9E CM S C7 8.5 70.0 07 3.7 80.0 08 0.9 50.0 06 6.3 80.0 0S M S C7 5.7 10.0 07 0.5 10.0 06 9.2 20.0 06 4.0 40.0 0D i M S C6 5.8 12.6 45 5.5 71.4 95 2.6 71.5 38 6.7 20.3 8k-L RMC7 9.5 23.1 67 4.6 32.0 97 1.1 42.8 49 1.6 50.9 3p r o k a r y o t i cLM S C5 0.3 94.3 42 3.6 62.2 84 0.7 80.7 96 0.6 72.3 0M S C-I A S5 6.6 90.3 81.5 40.6 95 6.1 10.2 54 0.4 10.4 5E CM S C5 1.9 10.0 01 9.8 40.0 06 0.9 80.0 01 3.3 80.0 0S M S C6 4.2 50.0 03 1.6 60.0 05 3.3 60.0 02 4.0 70.0 0D i M S C3 3.8 70.2 84.3 60.1 03 2.3 70.0 45 5.6 70.0 5k-L RMC7 7.2 52.7 34 8.0 74.4 96 7.7 95.1 37 6.3 11.7 508 纺 织 高 校 基 础 科 学 学 报 第3 6卷续表1C o n t i n u e d T a b.1数据集算法A C CNM IFR Ih a n d w r i t t e nLM S C8 2.4 09.1 58 0.8 63.1 57 6.6 76.9 59 5.0 71.7 6M S C-I A S2 0.7 52.4 41 0.1 73.1 21 4.2 11.6 38 2.5 60.2 9E CM S C8 4.9 00.0 08 3.5 80.0 08 4.9 00.0 07 9.5 10.0 0S M S C8 2.1 00.0 08 4.8 50.0 08 1.2 40.0 07 9.0 60.0 0D i M S C1 9.2 10.4 55.1 40.1 91 2.3 10.1 78 2.3 40.0 3k-L RMC8 8.6 95.3 78 9.9 31.9 88 6.5 94.6 69 7.1 31.0 63.2.2 聚类结果分析表1为各算法在4个公开数据集上聚类性能比较。从表1可以看出,在NU S-W I D E数据集上,与次优评价结果相比,本文算法在A C C、NM I和R I上分别提高了3%、1%和1%,但在评价指标F上有微小降低。在M S R C-v 1数据集上,与次优评价结果相比,本文算法在A C C、NM I和R I上分别提高了0.5%、1%和0.5%,但在评价指标F上降低了9%。本文算法k-L RMC在数据集p r o k a r y o t i c和数据集h a n d w r i t t e n上提供了完美的聚类性能。在数据集p r o k a r y o t i c上,本文算法在A C C、NM I、F和R I的评价指标相比于次优的分别提高了1 3%、1 7%、7%、1 6%。在数据集h a n d w r i t t e n上,本文算法在A C C、NM I、F和R I的评价指标比次优的算法提高了4%、5%、2%、2%。此外,从表1还可以看出,D i M S C的性能较差。这是因为,虽然D i M S C使用不同子空间来探索多个视图的互补信息,但这只能保证得到的子空间矩阵融合了每个视图数据的一致信息,而不能保证充分利用各子空间的个性化信息。为此本文算法k-L RMC对各视角图进行k-近邻局部线性重建提取各视角相似矩阵中的个性化信息。M S C-I A S性能也较差,该算法通过原始多视角数据学习潜在空间并得到相似矩阵进行聚类,但该算法没有挖掘各视角数据间的互补信息,可能导致学习出的潜在空间并不准确。3.3 实验分析3.3.1 收敛分析和算法复杂度计算为了求解目标函数(f),采用交替迭代优化算法求解每个变量,因此目标函数的收敛性非常重要。为了直观解释本文模型的收敛性,在4个数据集上目标函数值的对数值随迭代次数的变化如图2所示。可以看出,本文算法在数据集上仅需要不到1 0次就可以趋于收敛。(a)NU S-W I D E (b)M S R C-v 1 (c)p r o k a r y o t i c (d)h a n d w r i t t e n图2不同数据集的收敛图 F i g.2T h e c o n v e r g e n c e c u r v e o f d i f f e r e n t d a t a s e t s综上可知,本文算法包含3个子问题。更新相18第3期 马盈仓,等:基于k-近邻局部线性邻域重建的多视角聚类算法似矩阵S需要O(n(m n k+nl o g n)的时间复杂度,更新自表示矩阵W(v)的时间复杂度为O(m(n k2+k3),更新各视角相似矩阵S(v)的时间复杂度为O(m n(n2+nl o g n)。因此本模型的总时间复杂度为O(t(m n3),这里t是总迭代次数。3.3.2 可视化根据k-L R M C算法在数据集N U S-W I D E,M S R C-v 1,p r o k a r y o t i c,h a n d w r i t t e n上的相似矩阵,并利用(S+ST)/2绘制图像,如图3所示。其中,每一个数据集下方的图片为各数据集局部放大图。从图3可以看出,该方法可以很好地揭示底层的块对角结构(见图3所示的放大区域),这是基于谱聚类所需要的,并进一步验证了k-L R M C模型的优势。(a)NU S-W I D E (b)M S R C-v 1 (c)p r o k a r y o t i c (d)h a n d w r i t t e n 图3k-L RMC算法在4种数据集上的可视化相似矩阵 F i g.3 V i s u a l s i m i l a