非负拉格朗日松弛优化的子空间聚类算法.pdf

收稿日期:网络出版时间:基金项目:国家自然科学青年基金(,);江苏省自然科学青年基金(B K ,B K );中国博士后科学基金(T ,M );江苏省博士后科学基金(K C)作者简介:朱东霞(),女,江苏大学硕士研究生,E m a i l:q q c o m黄龙霞(),女,副教授,E m a i l:h l x i a u j s e d u c n通信作者:贾洪杰(),男,副教授,E m a i l:j i a h j u j s e d u c n网络出版地址:h t t p s:d o i o r g/j i s s n d o i 敭 j 敭i s s n 敭 非负拉格朗日松弛优化的子空间聚类算法朱 东 霞,贾 洪 杰,黄 龙 霞(江苏大学 计算机科学与通信工程学院,江苏 镇江 )摘要:传统的子空间聚类和谱聚类中普遍使用谱松弛方法聚类,需要先计算拉普拉斯矩阵的特征向量.特征向量中包含负数,根据元素的正负可以直接得到二类聚类的结果.对于多类聚类问题,需要递归地进行二划分,或在特征向量空间中使用k m e a n s算法聚类,分配类簇标签是间接的,这种后处理的聚类方式会增加聚类结果的不稳定性.针对谱松弛的问题,提出了一种非负拉格朗日松弛优化的子空间聚类算法,在目标函数中集成了自表示学习和秩约束.通过非负拉格朗日松弛来求解相似性矩阵和隶属矩阵,并保持隶属矩阵的非负性.在这种情况下,原来的隶属矩阵就变成了类簇的后验概率,当算法收敛时,只需将数据点分配给具有最大后验概率的类簇,即可得到聚类结果.与已有的子空间聚类和谱聚类方法相比,所提出的算法设计了新的优化规则,可以实现类簇标签的直接分配,不需要额外的聚类步骤.最后,给出了算法的收敛性证明.在个基准聚类数据集上的大量实验表明,所提算法的聚类性能优于近几年来的子空间聚类方法.关键词:聚类算法;自表示;优化;非负拉格朗日松弛;子空间聚类中图分类号:T N 文献标识码:A文章编号:()S u b s p a c e c l u s t e r i n ga l g o r i t h mo p t i m i z e db yn o n n e g a t i v eL a g r a n g i a nr e l a x a t i o nZHUD o n g x i a J I A H o n g j i e HU ANGL o n g x i a S c h o o l o fC o m p u t e rS c i e n c ea n dC o mm u n i c a t i o nE n g i n e e r i n g J i a n g s uU n i v e r s i t y Z h e n j i a n g C h i n a A b s t r a c t S p e c t r a l r e l a x a t i o n i sw i d e l yu s e d i n t r a d i t i o n a l s u b s p a c e c l u s t e r i n ga n ds p e c t r a l c l u s t e r i n g 敭 F i r s t t h ee i g e n v e c t o ro ft h eL a p l a c i a nm a t r i xi sc a l c u l a t e d 敭 T h ee i g e n v e c t o rc o n t a i n sn e g a t i v en u m b e r s a n dt h er e s u l to f t h e w a yc l u s t e r i n gc a nb e o b t a i n e dd i r e c t l ya c c o r d i n g t o t h ep o s i t i v e a n dn e g a t i v e o f t h e e l e m e n t s 敭F o rm u l t i w a yc l u s t e r i n gp r o b l e m s w a yg r a p hp a r t i t i o ni sa p p l i e dr e c u r s i v e l yo rt h ek m e a n si su s e di ne i g e n v e c t o r s p a c e 敭 T h ea s s i g n m e n to ft h ec l u s t e rl a b e l i si n d i r e c t 敭 T h ei n s t a b i l i t yo fc l u s t e r i n gr e s u l t sw i l li n c r e a s eb yt h i sp o s t p r o c e s s i n gc l u s t e r i n g m e t h o d 敭 F o rt h el i m i t a t i o no fs p e c t r a lr e l a x a t i o n as u b s p a c ec l u s t e r i n ga l g o r i t h m o p t i m i z e db yn o n n e g a t i v eL a g r a n g i a nr e l a x a t i o ni sp r o p o s e d w h i c hi n t e g r a t e ss e l f r e p r e s e n t a t i o nl e a r n i n ga n dr a n kc o n s t r a i n t s i nt h eo b j e c t i v e f u n c t i o n 敭 T h e s i m i l a r i t ym a t r i xa n dm e m b e r s h i pm a t r i xa r es o l v e db yn o n n e g a t i v eL a g r a n g i a nr e l a x a t i o na n dt h en o n n e g a t i v i t yo f t h em e m b e r s h i pm a t r i xi sm a i n t a i n e d 敭 I nt h i s w a y t h e m e m b e r s h i p m a t r i x b e c o m e st h ec l u s t e rp o s t e r i o rp r o b a b i l i t y 敭W h e nt h ea l g o r i t h mc o n v e r g e s t h ec l u s t e r i n g r e s u l t s c a nb eo b t a i n e dd i r e c t l yb ya s s i g n i n g t h ed a t ao b j e c t t o t h e c l u s t e rw i t ht h e l a r g e s t p o s t e r i o rp r o b a b i l i t y 敭 C o m p a r e dw i t ht h e e x i s t i n gs u b s p a c e c l u s t e r i n ga n ds p e c t r a l c l u s t e r i n gm e t h o d s t h ep r o p o s e da l g o r i t h md e s i g n san e wo p t i m i z a t i o nr u l e w h i c hc a nr e a l i z et h ed i r e c ta l l o c a t i o no f 年月第 卷第期西安电子科技大学学报J OURNA LO FX I D I ANUN I V ER S I TYF e b V o l N o c l u s t e r l a b e l s w i t h o u ta d d i t i o n a lc l u s t e r i n gs t e p s 敭 F i n a l l y t h ec o n v e r g e n c eo ft h ep r o p o s e da l g o r i t h mi sa n a l y z e dt h e o r e t i c a l l y 敭 G e n e r o u se x p e r i m e n t so nf i v eb e n c h m a r kc l u s t e r i n gd a t a s e t ss h o wt h a t t h ec l u s t e r i n gp e r f o r m a n c eo f t h ep r o p o s e dm e t h o d i sb e t t e r t h a nt h a to f t h er e c e n t s u b s p a c ec l u s t e r i n gm e t h o d s 敭K e yW o r d s c l u s t e r i n ga l g o r i t h m s s e l f e x p r e s s i o n o p t i m i z a t i o n n o n n e g a t i v eL a g r a n g i a nr e l a x a t i o n s u b s p a c ec l u s t e r i n g引言聚类作为一种无监督技术,目前已被广泛应用于机器学习、计算机视觉、数据分析和统计研究等领域.过去几十年中,已经开发出了大量的聚类算法,例如k m e a n s、谱聚类、层次聚类、D B S C AN、深度聚类等等,聚类在各种应用中得到了广泛的研究.然而,在处理高维数据时,标准聚类算法的性能会受到不利影响,并且在处理大规模数据集时,它们的时间复杂度会显著增加.为了解决维数灾难,文献 首次提出了子空间聚类的概念.子空间聚类受到了越来越多的关注,它假设数据点来自多个低维子空间,在聚类的过程中能够为每个类簇找到相应的特征子空间 .基于子空间学习方法的直观解释,子空间聚类因其良好的性能而得到了广泛的探索.因此,开发了许多子空间聚类算法,包括基于迭代、代数、统计和谱聚类的方法.在这些方法中,谱聚类方法是研究的热点,因为谱聚类是从谱图划分发展而来的,具有良好的聚类目标函数.代表性工作有低秩表示(L o w R a n kR e p r e s e n t a t i o n,L R R)和稀疏子空间聚类(S p a r s eS u b s p a c eC l u s t e r i n g,S S C).其中,L R R发现子空间的低秩结构,而S S C发现数据点的稀疏表示.在此基础上,研究者们开展了大量的工作来加速子空间聚类.例如,A B HA D I OMHE N等提出了一种基于耦合低秩表示的方法,通过构建一个流形恢复结构来纠正数据的低秩表示的不足,然后得到一个服从k块对角性质的聚类投影矩阵来学习理想的相似性矩阵.在这些聚类方法中,相似性度量和数据聚类通常分成两个独立的步骤,因此学习到的数据相似性可能不是数据聚类的最佳相似性,并导致次优结果.另一方面,在谱松弛中,离散簇指示符的连续近似可以由相似图的拉普拉斯矩阵的特征向量获得.由于特征向量项有正负号,因此谱聚类最适合用于使用单个特征向量的二类聚类问题.当应用于多类聚类时,分配聚类成员成为间接的.通常的解决方法有两种:第种方法是递归地应用二类谱聚类;第种方法首先对特征向量所跨越的空间进行嵌入,然后借助额外的聚类方法(例如k m e a n s)来完成聚类.这种后处理的不确定性会增加原始性能的不稳定性.谱松弛存在的问题是理想的聚类指标是非负的,但特征向量的解包含许多负项.在这种情况下,很难识别集群成员.如果隶属矩阵H的元素是非负的,那么这个类簇分配问题就会变得容易.为了解决这个问题,文中在子空间聚类中引入了非负拉格朗日松弛方法,以保持隶属矩阵的非负性.此时,计算的隶属矩阵成为聚类后验概率.在收敛时,只需将数据对象分配给具有最大后验概率的类簇,直接得到聚类结果.这是相对于谱松弛的一个主要优势,除了解决类簇分配问题外,这种附加的可解释性在理论上也很有吸引力.在此基础上,文中提出了一种非负拉格朗日松弛优化的子空间聚类算法(N o n n e g a t i v eL a g r a n g i a nR e l a x a t i o nS u b s p a c eC l u s t e r i n g,N L R S C),它可以在一个统一的框架中学习数据的相似性和类簇标签.首先利用子空间聚类的自表达特性,即每个示例相对于整体数据的线性表示来捕获数据的全局结构;然后加入拉普拉斯矩阵来保持数据之间的块连通性,加强了数据的类内相似性;最后,使用非负拉格朗日松弛优化方法求解非负的隶属矩阵,直接分配类簇成员,避免传统谱聚类算法后处理带来的不确定性.与近几年先进的技术相比,该方法在有效性方面获得了很大的提高.总之,文中的主要贡献如下:()提出了一种非负拉格朗日松弛优化的子空间聚类算法,引入非负拉格朗日松弛,处理多类聚类问题.()学习相似性和聚类可以在迭代优化过程中相互促进,直接获得聚类结果,不需要额外的步骤来进行聚类,避免后处理带来的不确定性.第期朱东霞等:非负拉格朗日松弛优化的子空间聚类算法()构造了有效的乘法更新规则求解该模型,并进行了全面的理论分析,保证了算法的收敛性.()大量的实验结果证明了该方法的有效性.相关工作子空间聚类是探索数据潜在特征结构的一种非常有用的方法.它的目的是寻找数据点的最优子空间,其中每个数据可以表示为其他点的线性组合,并最小化重建损失以获得组合系数.该系数被视为对应点之间的相似性,它可以捕捉数据的全局结构.过去的几年中,子空间聚类领域提出了许多方法.比如一些方法选择观测数据矩阵X作为独立和不相交子空间的字典,如最小二乘回归(L e a s tS q u a r e sR e g r e s s i o n,L S R)、S S C 和L R R.此外,一些文献还提出了许多改进的方法,如单纯形稀疏表示(S i m p l e xS p a r s eR e p r e s e n t a t i o n,S S R),提出可以使用具有适当约束的稀疏表示来计算样本对之间的亲和力,通过自动生成拉普拉斯图来显著降低计算成本,并对异常值和噪声具有鲁棒性.基于干净字典的低秩稀疏子空间聚类(L o w R a n ka n dS p a r s eS u b s p a c eC l u s t e r i n gw i t haC l e a nd i c t i o n a r y,L R S C),通过结合S S C和L R R,将子空间的并集拟合到一个包含从子空间中提取并被噪声破坏的数据点的集合,目标是将破坏的数据矩阵分解为干净且自表示的字典和一个噪声矩阵.在子空间的多种方法中,基于谱图的子空间聚类通常具有良好的性能.因此,谱聚类方法是近年来研究的热点,应用最为广泛.谱聚类在执行k m e a n s聚类之前对数据的相似性矩阵进行低维嵌入.每对数据点之间的相似性利用了数据中的流形信息,因此谱聚类方法通常比k m e a n s算法表现出更好的性能.然而,这种方法的性能在很大程度上取决于相似性矩阵.许多基于相似度的聚类方法分为两个独立的步骤,包括相似性矩阵计算和后续的谱聚类.然而,相似性度量具有挑战性,因为它通常受到许多因素的影响,例如度量、邻域大小和数据规模,都可能导致性能不理想.大多数研究人员将重点放在相似性矩阵的优化和改进上,以获得更好的聚类性能 .例如,CHE N等 提出了一种自适应低秩表示的方法,将采用正交约束的自适应词典学习策略集成到低秩表示模型中来同时获得投影矩阵和低秩特征.然而,这些方法的最后一步,通常需要将一种简单的聚类方法应用于学习的指标矩阵,如k m e a n s.但是这种后处理操作的不确定性将增加聚类结果的不稳定性.为了解决该问题,N I E等 提出了一种基于拉普拉斯矩阵秩约束的聚类方法.该方法结合了F r o b e n i u s范数,通过最小距离获得仅具有连通分量的邻接矩阵,因此邻接矩阵可以直接用于完成聚类任务.它可以避免进一步后处理带来的不确定性.但是,F r o b e n i u s范数对许多实际情况中存在的异常值和噪声非常敏感,如何减少这些负面影响也是一个待解决的问题.最近,自表达已成功地应用于子空间恢复 和低秩表示,它以其他点的线性组合表示每个数据点,通过求解优化问题,自动从数据中学习相似性信息.这种方法不仅可以揭示低维结构,而且对噪声和数据规模具有鲁棒性.受此启发,KANG等 提出了一个学习全局结构和秩约束的模型.该模型在核空间中同时学习隶属矩阵和相似性信息.Z HU等 提出了一种低秩稀疏子空间(L o w r a n kS p a r s eS u b s p a c e,L S S)聚类方法.该方法首先通过在样本自表示框架中进行特征选择和子空间学习,将原始数据投影到它们的低维空间,然后利用秩约束和直接从原始数据中获得的亲和矩阵构造一个动态的内在亲和矩阵.通过自表示并对数据施加稀疏约束;由于两个点仅在它们来自同一子空间时才连接,稀疏子空间聚类可以保证同一子空间内的数据亲和力.然而,另一方面,来自同一子空间的数据点可能连接不好,导致过度分割的问题.CHE N等 引入了D r o p o u t来解决过度分割的问题,提出了一种随机稀疏子空间聚类方法,它可以有效地处理大规模数据集.上述方法在整合全局数据结构方面已被证明是有效的.另外,非负矩阵分解(N o n n e g a t i v eM a t r i xF a c t o r i z a t i o n,NMF)是一种重要的降维技术,在机器学习和数据挖掘中得到了广泛的应用.研究人员通过探索矩阵分解和聚类之间的关系,为NMF技术开辟了多种其他潜在应用.已经证明,具有平方误差代价函数的NMF等价于最广泛使用的无监督学习算法 松弛k m e a n s聚类.NMF的核心概念是将原始非负数据矩阵分解为非负基矩阵和非负系数矩阵,使其乘积最可能接近原始非负数据矩阵.由于NMF学习的数据表示具有良好的可解释性,使用NMF来完成聚类任务也被证明是一项有效的技术.例如,KUANG等 将NMF和谱聚类联系起来,提出了对称NMF西安电子科技大学学报第 卷(S y mm e t r i cN o n n e g a t i v eM a t r i xF a c t o r i z a t i o n,S y mNMF)图聚类方法.S y mNMF继承了NMF的良好解释性,其成功的关键在于隶属矩阵的非负性性质(H),通过在H的每一行中选取最大条目,可以直接将H解释为聚类结果.受S y mNMF的启发,文中提出了非负拉格朗日松弛优化的子空间聚类方法N L S R C.通过在子空间聚类中加入非负拉格朗日约束,可以在一个统一的优化框架中学习数据的相似性和隶属矩阵;学习的隶属矩阵直接揭示了一致的聚类结果,不需要额外的聚类步骤,从而避免了后处理带来的不确定性.文中提出的方法首先介绍N L R S C的总体框架.如图所示,在该框架中,首先通过核子空间自表示学习全局结构;然后转换成相似性矩阵,将相似性矩阵S和初始化的隶属矩阵H输入到目标函数中,如果结果不收敛,相似性矩阵S和隶属矩阵H会返回,继续进行迭代改进;再后继续输入到目标函数中,进行优化,直到结果收敛;最后,根据H来分配数据点标签,直接得到聚类结果.图N L R S C的整体框架图文中使用的相关符号和解释如表所示.表使用的符号和解释符号解释X Rdn数据矩阵S Rnn相似性矩阵H Rnc隶属矩阵单位向量I单位矩阵t r()矩阵的迹d i a g()对角矩阵r a n k()矩阵的秩FF范数 自表示性一个子空间中的一个样本可以表示为相同子空间中其他样本的线性组合,称为自表示性.自表示特性已被应用于许多应用程序,并证明了其捕获数据全局结构的能力.子空间聚类是建立在这个特性上的,用来学习邻接矩阵.它假设每个数据点可以从所有其他数据点的加权组合中线性重构,即得到其直接邻域和可到达的间接邻域.因此,基于图的聚类方法可以依赖于自表示性来构建可靠的亲和图.数学定义如下:第期朱东霞等:非负拉格朗日松弛优化的子空间聚类算法m i nSXX SFR(S),s t S,S,()其中,XRdn是给定的数据样本矩阵,SRnn是学习到的相似性矩阵,是平衡参数,第项是重构误差,第项R(S)是S上的正则化项.现有的方法之间的差异主要取决于R(S)的选择,例如:S、S或者SF.是长度为n的单位向量,S 意味着每行S加起来等于.因此,式()将通过跟踪数据点的分布来学习相似性矩阵,这将反映全局关系.目标函数为了避免二次规划的优化问题,这里放松了全局相似性矩阵S的约束,即m i nSXX SFSF,s t S,d i a g(S),()其中,d i a g(S),表示数据点不能由数据点本身表示.问题式()中的S没有明确的类簇结构,因此它可能不会产生最佳聚类结果.理想的聚类应该使来自不同类别的数据样本之间的连接尽可能弱,而同一类中的数据点之间的联系则尽可能紧密.理想情况下,c个类簇的亲和图应该具有c个连通分量,即S是块对角的(具有适当的排列),其中每个块是连通的,并且对应于来自同一类的数据样本.为了解决这个问题,需要根据定理引入秩约束.定理相似性矩阵S的拉普拉斯矩阵L的特征值的重数c等于S中连通分量的个数.定理表明如果相似性矩阵S由c个完全连通的分量组成,则r a n k(L)nc.因此问题式()可以重新表述为m i nSXX SFSF,s t S,d i a g(S),r a n k(L)nc.()问题式()也不好解决.因为拉普拉斯矩阵LID/S D/,其中D是相似性矩阵S的度矩阵,L也依赖于S.令(L)表示L的第i个最小特征值,因为L是半正定的,可以得到(L),根据文献 ,r a n k(L)nc,相当于cii(L);另外,具有秩约束的优化问题具有组合复杂性.为了解决这一问题,建议将秩约束作为正则化项纳入目标函数,问题式()可以被改写为m i nSXX SFSFcii(L),s t S,d i a g(S).()尽管如此,等式()中的优化问题仍然具有挑战性.为了缓解这个问题,接下来引入凯凡定理:cii(L)m i nHTHIHTL H,()其中,HRnc是隶属矩阵,拉普拉斯矩阵L可以用于合并来自数据的全局结构信息.因此,问题式()可以被描述为m i nSXX SFSF(HTL H),s t S,d i a g(S),HTHI,H.()但是式()是一个线性模型,不能有效地处理非线性数据.为了解决这个问题,可以通过核技巧将非线性数据映射到高维特征空间中.因此,通过核函数Ki j(Xi),(Xj)将问题式()扩展到核表示,得到m i nSt r(KK SSTK S)t r(S ST)t r(HTL H),s t S,d i a g(S),HTHI,H,()西安电子科技大学学报第 卷其中,和都是平衡参数,在实验中便于调整模型以适用不同的数据集.式()的最后一项是保证相似性矩阵满足秩约束.式()将学习相似性和聚类融合为统一的框架,通过迭代优化过程相互促进,求得隶属矩阵H后,可以直接得到聚类结果.模型求解 非负拉格朗日优化为了求解问题式(),使用非负拉格朗日松弛方法推导迭代更新规则,相似性矩阵S和隶属矩阵H的更新公式可表示为Si kSi kKi k(D/H HTD/)i k(K S)i kSi k/,()Hi kHi k(D/S D/H)i k(H)i k/,()其中,HTD/S D/H.式()的正确性和收敛性证明用迭代法求解矩阵S和H,即固定其中一个,求解另一个.定理固定H,式()中的更新规则极限解满足KK T条件.证明:固定H,求解S的子问题就是m i nSt r(K SSTK S)t r(S ST)t r(HTD/S D/H).()引入拉格朗日乘数i j和拉格朗日函数:LSt r(K SSTK S)t r(S ST)t r(HTD/S D/H)t r(ST)t r(K S)t r(STK S)t r(S ST)t r(HTD/S D/H)t r(ST).()其一阶导函数为LSSKK SSD/H HTD/.()在互补松弛条件下,可以得到(KK SSD/H HTD/)i kSi ki kSi k.()注意,式()提供了极限解应满足的不动点条件.另外,式()的极限解满足式(),如下所述,在收敛时,式()给出:Si kSi kKi k(D/H HTD/)i k(K S)i k Si k/.()通过简单代数可以得到(KK SSD/H HTD/)i kSi k.()此式即式(),其中,(KK SSD/H HTD/)i k或者Si k.定理对于固定H,式()和式()在式()的更新规则下单调递减.在这里使用辅助函数方法 来证明上述定理,相关定义和命题证明如下:定义对于任何Y和Y,若满足以下条件,则称J(Y,Y)为L(Y)的辅助函数.J(Y,Y)L(Y),J(Y,Y)L(Y).()命题对于任何矩阵A Rnn,B Rkk,C Rnk和C Rnk,由于A和B是对称的,以下不等式成立:niks(A C B)i sCi sC i st r(CTA C B).()命题给定一个函数L(Y)和它的辅助函数J(Y,Y),可以定义一个可变系列Y(t)如下:第期朱东霞等:非负拉格朗日松弛优化的子空间聚类算法Y(t)a r gm i nYJ(Y,Y(t).()由于以下不等式链,值序列L(Y(t)在变小:L(Y(t)J(Y(t),Y(t)J(Y(t),Y(t)L(Y(t).借助定义和命题,接下来证明定理.证明:对于式(),可以重写为f(S)t r(K SSTK S)t r(S ST)t r(HTD/S D/H).()首先找到f(S)的正项和负项的上界和下界,对于正项,使用命题和不等式aabb,a,b来获取以下上界:t r(STK S)i k(K S)i kSi kS i k,t r(STS)i kS i kSi kS i k.()对于负项,使用不等式al o ga,a来获取以下下界:t r(K S)t r(STK)i kKi kSi ki kKi kS i kl o gSi kS i k,t r(HTD/S D/H)t r(D/H HTD/S)i k(D/H HTD/)i kSi ki k(D/H HTD/)i kS i kl o gSi kS i k.()结合这些界,可以得到函数f(S)的辅助函数P(S,S)如下:P(S,S)i kKi kS i kl o gSi kS i ki k(K S)i kSi kS i ki kS i kSi kS i ki k(D/H HTD/)i kS i kl o gSi kS i k.()接下来,将展示式()的更新本质上遵循式().为了说明这一点,剩下的问题是找到式()的全局最小值.为此,首先证明式()是凸的.P(S,S)的一阶导数:P(S,S)Si k Ki kS i kSi k(K S)i kSi kS i kS i kSi kS i k(D/H HTD/)i kS i kSi kKi k(D/H HTD/)i kS i kSi k(K S)i kS i kSi kS i k,()P(S,S)的二阶导数:P(S,S)Si jSk li jk lKi k(D/H HTD/)i kS i kSi k(K S)i kS i kS i k,()其中,i j是指示函数,如果ij则返回,否则返回.可以得到,P(S,S)的H e s s i a n矩阵非对角元素为,对角元素为非负,因此矩阵是正定的,所以P(S,S)是凸的.通过其一阶最优性条件,即令式()等于,可以得到:(K S)i kS i kSi kS i kKi k(D/H HTD/)i kS i kSi k.()式()进一步简化为Si kSi kKi k(D/H HTD/)i k(K S)i kS i k/.()定义S(t)S,S(t)S,可以得到式().式()的正确性和收敛性证明定理固定S,式()中的更新规则极限解满足KK T条件.西安电子科技大学学报第 卷证明:固定S,求解H的子问题就是m i nHt r(HTL H)t r(HTD/S D/H).()引入拉格朗日乘子 Rkk,构造拉格朗日函数:LHt r(HTD/S D/H)t r(HTHI)t r(HTD/S D/H)t r(HT H)t r().()其一阶导函数为LHH D/S D/H(D/S D/)THH H TD/S D/HH.()然后根据KK T互补条件,得到:(D/S D/HH)i kHi k.()式()中,对矩阵的行向量求和,可以得到(HTD/S D/H)i i(HTH)i i()i i,这给出了的对角线元素.为了找到的非对角元素,暂时忽略H H的非负性要求.等式(D/S D/HH)i k左乘以HT,得到HTD/S D/H.式()提供了极限解应满足不动点的条件,遵循上一小节得到Hi kHi k(D/S D/H)i k(H)i k/.()从式()可以得到,在收敛时,解满足以下条件:(D/S D/HH)i kHi k.()这是式()中的不动点条件,其中,(D/S D/HH)i k或者Hi k.接下来证明收敛性.定理对于固定S,式()和式()在式()的更新规则下单调递减.证明:根据LH,得到:f(H)t r(HTD/S D/H)t r(HTH).()根据 节的命题和不等式,得到以下上下界:t r(HT H)t r(HTI H)i k(H )i kHi kH i k,t r(HTD/S D/H)k i j(D/S D/)i jHi kHj k k i j(D/S D/)i jH i kH j kl o gHi kHj kH i kH j k.()结合这些界,得到f(H)的辅助函数J(H,H)如下:J(H,H)k i j(D/S D/)i jH i kH j kl o gHi kHj kH i kH j ki k(H )i kHi kH i k.()接下来证明J(H,H)是凸的,其一阶导函数为J(H,H)Hi k(D/S D/H)i kH i kHi k(H )i kHi kH i k.()J(H,H)的二阶导函数为J(H,H)Hi jHk li jk l(D/S D/H)i kH i kHi k(H )i kH i k.()遵循上一小节,很容易验证J(H,H)的H e s s i a n矩阵是否有非对角的零元素和对角的非负值.因此,J(H,H)是凸的.通过其一阶最优性条件,即令式()等于,可以得到(H )i kHi kH i k(D/S D/H)i kH i kHi k.()式()进一步化简为第期朱东霞等:非负拉格朗日松弛优化的子空间聚类算法Hi kHi k(D/S D/H)i k(H)i k/.()定义H(t)H,H(t)H,可以得到式().文中提出的非负拉格朗日松弛优化的子空间聚类算法的完整过程如算法所示.算法非负拉格朗日松弛优化的子空间聚类算法N L R S C.给定核矩阵K,度矩阵D,参数和,初始化相似性矩阵S和隶属矩阵H当收敛条件不满足时执行根据式()更新S根据式()更新H退出循环得到最优的S和H根据H来分配数据点的类标签:Hi k,ka r gm a xk,cHi k,其他输出聚类结果.实验本节进行了大量实验,以验证所提出的N L R S C的有效性.数据集实验在个基准数据集上进行了评估,包括个著名的人脸数据集(即YA L E、A R、O R L 和J A F F E)和一个文本语料库T R .表列出了这些数据集的基本信息,其详细信息如下.()YA L E:包含 张 人的G I F格式灰度图像.每人有 个图像,每个图像的大小为 像素.()A R:该数据集有 张图片,包含 个人,每个人张照片,图片以正面视图的人脸为特征,具有不同的面部表情、不同光照.()O R L:一共包含 个不同人的 张照片,每个人 张人脸图像.每个图像的大小为 像素.()J A F F E:收集了 张 位日本女性模特的照片,展示了种面部表情.这些图片由 名日本人根据个动作形容词进行评分.每个图像的大小为 像素.()T R :用于验证文本文档聚类的结果,这些数据集是文本文档聚类首选的标准数据集.表所用数据集的基本信息数据集类型类别样本特征YA L E人脸 A R人脸 O R L人脸 J A F F E人脸 T R 文本 比较方法为了充分研究所提方法在聚类方面的性能,本节选择了一组近年来具有代表性的方法进行比较.()谱聚类(S p e c t r a lC l u s t e r i n g,S C):一种广泛使用的聚类技术.它具有探索内在数据结构的优势.然而,如何构造一个好的相似图是一个悬而未决的问题.这里,直接使用核矩阵作为输入.()鲁棒核k 均值(R o b u s tK e r n e lk m e a n s,R KkM):作为经典k m e a n s聚类方法的扩展,R KkM能够处理数据中的非线性结构、噪声和异常值,因为L 范数用于衡量k m e a n s的损失.西安电子科技大学学报第 卷()低秩表示(L R R):基于自表示特性,得到一个低秩图.()单纯形稀疏表示(S S R):基于自表示特性,得到一个稀疏图.S S R在大量数据集上取得了令人满意的性能.()全局结构学习方法(G l o b a l):基于自表示特性,该方法结合了全局结构和秩约束.()结构化图学习(S t r u c t u r e dG r a p hL e a r n i n g,S G L):基于自表示特性,该方法结合全局结构和二部图的约束来发现潜在的簇结构.()文中提出的N L R S C:所提方法不仅基于自表示特性结合了全局结构信息,还利用非负拉格朗日松弛方法优化隶属矩阵,直接得到聚类结果.评估指标在实验中,一共使用了个评估指标,即准确度(A C C u r a c y,A C C)、归一化互信息(N o r m a l i z e dM u t u a lI n f o r m a t i o n,NM I)和纯度(P u r i t y),来验证所提方法的有效性.A C C衡量每个类簇中同一类数据点所占的比例.NM I测量类簇的质量.P u r i t y衡量每个类簇包含主要来自同一类别的样本的程度.这些指标的值越高,表明聚类的质量越好.实验结果为了公平起见,所有比较方法的参数都根据相应论文描述的实验设置进行了调整.此外,针对提出的方法,所有数据集的参数初始化都是 ,然后根据不同数据集的特点在实验中进行调整.表、表和表中给出了不同方法的实验结果,该结果是 次独立实验的平均聚类结果.各表中的最后一行分别是每种方法在每个数据集上的平均A C C、平均NM I和平均P u r i t y.对于每个数据集和指标,最好的结果以黑体字突出显示.可以看到,文中提出的方法取得了令人满意的结果,其次是S G L、G l o b a l、S S R、L R R、R KKM和S C.与S C和R KKM相比,N L R S C可以显著提高性能.例如,就平均准确度,N L R S C比S C和RMMK分别提高约 和 .基于自