谱聚类的扰动分析

中国科学E辑:信息科学2007年第37卷第4期:527~543收稿日期:2006-07-20;接受日期:2006-08-29国家自然科学基金(批准号:60375003)和航空科学基金(批准号:03I53059)资助项目*联系人,E-mail:[e-mail];[e-mail]1)WeissY.Segmentationusingeigenvectors:aunifyingview.In:ProceedingsoftheSeventhIEEEInternationalConferenceonComputerVision.LosAlamitos:IEEEComputerSociety,1999.975—982SCIENCEINCHINAPRESS谱聚类的扰动分析田铮1,2李小斌1*句彦伟1(1.西北工业大学应用数学系,西安710072;2.模式识别国家重点实验室,中国科学院自动化研究所,北京100080)摘要以矩阵的扰动理论为工具对谱聚类(spectralclustering)进行了分析,通过引入图的权矩阵并对权矩阵的谱和特征向量进行分析,得到了权矩阵的谱与聚类的类数、权矩阵特征值的大小与每一类所含点的个数、以及权矩阵的特征向量与聚类之间的关系.据此,设计了一个基于权矩阵的无监督谱聚类算法(unsupervisedspectralclusteringalgorithmbasedonweightmatrix,简记为USCAWM),并在模拟点集和实际的数据集上进行了实验,实验结果肯定了理论分析的正确性.关键词谱聚类权矩阵权矩阵的谱聚类的类数基于权矩阵的无监督谱聚类算法聚类分析是多元统计分析和模式识别研究的一个重要内容,多年来已经提出了许多聚类方法,如K均值聚类和模糊C均值聚类等,但是这些方法大都需要假定待聚类的对象具有某些特征,且多数情形下难以得到全局最优解.近年来所提出的谱聚类是一种较为实用的聚类方法[1,2].由于源于图的谱分割[3,4],谱聚类在进行聚类时首先以待聚类的对象集为顶点集构造赋权图,然后通过分析一个与图相关的矩阵的特征向量和特征值来得到聚类结果.由于图的边权可以结合待聚类对象的各种特征,所以谱聚类方法简单,可以处理复杂的数据类型,目前已经出现了许多谱聚类模型和算法,如Ratio-cut[5,6],Normalized-cut[7,8]及Max-mincut[9,10]等.但是应注意制约谱聚类方法发展的难题是该方法缺乏理论基础,虽然已经有了多种谱聚类算法,但是其区别仅在于所处理的矩阵不同,矩阵的谱和特征向量与聚类之间的关系并不清楚.鉴于此,Weiss1)对几种谱聚类方法进行了实验比较,文献[11]研究了谱聚类方法与K均值聚类之间的关系,文献[12]为了对谱聚类方法进行评价,提出了双标准评价策略,文献[13,14]从矩阵扰动的角度对谱聚类算法进行了初步的分析,但是它们似乎并未给出一个明确的答案.本文的目的是给出上述问题的比较理想的解答.本文首先定义了图的权矩阵的概念;其次以矩阵的扰动理论为工具,研究了权矩阵的谱和特征向量与聚类之间的关系,得到了权矩528中国科学E辑信息科学第37卷阵的谱和聚类类数之间的关系,权矩阵的特征值和每一类所含顶点数之间的关系,以及权矩阵的特征向量和聚类之间的关系;最后设计了一个基于权矩阵的无监督谱聚类算法,通过模拟点集和实际数据集上的实验,验证了理论分析的正确性,与Normalized-cut方法和k-means方法的比较说明该方法是有效的.1相关定义设123{,,,,}nVvvvv=是待聚类的对象集,其中iv为待聚类的对象.以V为顶点集构造赋权图(,)GVE,其中EVV=×表示顶点之间的边集,为方便起见用ije表示顶点ijvv和之间的边(,)ijvv,即(,)ijijevv=,边(,)ijvv上的权[0,1]ijw∈,表示ijvv和之间的相似程度,ijvv和之间越相似,即ijvv和越有可能属于同一类,ijw越大;反之ijw越大,表明ijvv和越有可能属于同一类,特别有1,1,2,,iiwin==.定义1(相似度函数)[1,7]定义二元函数:[0,1]RVV×→,若R满足(,),,1,2,,,ijijRvvwijn==则称R为V的相似度函数,而称(,)ijRvv为ijvv和之间的相似度(,1,2,,ijn=).定义2(权矩阵)称矩阵()ijnnWw×=为图G的权矩阵.显然有()((,))ijnnijnnWwRvv××==,简记为()WRVV=×.注1(ⅰ)集合V中的元素与其下标是一一对应的,文中标号i对应的集合V中的元素是指iv(1,2,,in=).(ⅱ)将对象集V进行聚类,即按照某一规则将集合V分成不相交子集的并,满足1,,,,1,2,,,kiijiVVVVijijk===∅≠=∩∪其中k是分类数,iV是聚类结果的第i个类,1,2,,ik=.设矩阵nnA×∈,12knλλλλ≥≥≥≥≥是矩阵A的特征值,12,,,,,knxxxx是相应的特征向量,则称12kλλλ≥≥≥为矩阵A的前k个特征值,12,,,kxxx是矩阵A的前k个特征向量.本文用()Aλ表示矩阵nnA×∈的特征值的全体组成的集合,用nE表示元素均为1的nn×方阵.2主要结论设对象集123{,,,,}nVvvvv=有k个类,即1,,,,1,2,,,kiijiVVVVijijk===∅≠=∩∪其中1112111212112212{,,,},{,,,},,{,,,}kkkiiiiiinknnnvvvVvvvVvvvV−−++++∈∈∈,第4期田铮等:谱聚类的扰动分析529即顶点按顺序属于每一类.于是111212122212()()...()()()...()()()...()kkkkkkRVVRVVRVVRVVRVVRVVWRVVRVVRVV×××⎛⎞⎜⎟×××⎜⎟=⎜⎟⎜⎟×××⎝⎠.(1)以下就W的3种不同情形分别给出权矩阵的谱和特征向量与聚类之间的关系.2.1理想情形设相似度函数R满足条件1,,(,),1,2,,,0,,ijvvijRvvijnvvij⎧⎪==⎨⎪⎩属于同一类,不属于同一类,则权矩阵12diag(,,,)knnnWEEE=.引理1设12nλλλ≥≥≥是nE的特征值,则1,0,2,,,ininλλ===且若T(1,1,,1)=en∈⊕,则1λ的特征子空间1()VLλ=e.证明经简单计算即可得结论.□引理2设12diag(,,,)knnnAAAΛ=,(1,2,,)iiinnnAik×∈=为实对称矩阵,则1()()ikniAλλ=Λ=∪,且若in∈x是矩阵inA对应于特征值λ的特征向量,则12kTT0,,0,0,,0,,,,0,,0nnn()x也是矩阵Λ对应于特征值λ的特征向量.证明经简单计算即可得结论.□定理1设12nλλλ≥≥≥是W的特征值,12,,,kxxx是W的前k个正交单位特征向量,令矩阵1212(,,,)(,,,)XΤΤΤ==αααknxxx,其中iα是X的第i个行向量,1,2,,in=,则(1)分类数{}max|1,1,2,,ikiinλ==;(2)T221,,cos(,),1,2,,0,,ijijvvijnvvθ⎧⎪===⎨⎪⎩属于同一类,不属于同一类,ijijijαααααα.证明由引理1和2可知结论(1)成立.`下面以3k=的情形对结论(2)进行证明,其余情形方法类同.设530中国科学E辑信息科学第37卷123T111(1,,1,0,,0,0,,0)nnnn=e,213T221(0,,0,1,,1,0,,0)nnnn=e,312T331(0,,0,0,,0,1,,1)nnnn=e.若112233,,===xexexe,则结论(2)是显然的.现考虑一般情形,根据引理1和2可知,123123(,,)(,,)LL=xxxeee,于是存在正交阵33()ijQq×=,使得123123(,,)(,,)Q=xxxeee=312T111121213131121222223232131323233333,,,,,,,,,,,,,,,,,,nnnqqqqqqqqqqqqqqqqqq⎛⎞⎜⎟⎜⎟⎜⎟⎜⎟⎜⎟⎜⎟⎝⎠,根据Q的正交性立知结论(2)成立.□应注意理想情形下的结论需要以下两个条件成立,即(i)(),1,2,,,(ii)(),,,1,2,,,iiinijRVVEinRVVOijijn×==×=≠=这并不现实(上式中O表示零矩阵).下一小节考虑仅在条件(ii)成立的情形下建立权矩阵的谱和特征向量与聚类之间的关系.2.2分块情形设相似度函数R满足条件,,(,)01,,1,2,,;0,,ijijijrvvijRvvrijnvvij⎧⎪==⎨⎪⎩属于同一类,≤≤不属于同一类,则权矩阵12diag(,,,)knnn=,其中(),1,2,,.iniiWRVVik=×=定理2设,1max1,ijijrσ−||≤12nλλλ≥≥≥是W的特征值.如果1(1,2,,)inik=,则当1σ充分小时,分类数{}max|1,1,2,,ikiinλ==.证明由引理2可知1()()ikinWWλλ==∪.现考虑矩阵inW(1,2,,)ik=的特征值.不失一般性,任取其中一个进行考虑,无妨记为mmmW×∈.第4期田铮等:谱聚类的扰动分析531将mW表示为1212121201110111,0111mmmmmmWEεεεεεεε−−⎛⎞⎛⎞⎜⎟⎜⎟−−⎜⎟⎜⎟=+=+⎜⎟⎜⎟⎜⎟⎜⎟−−⎝⎠⎝⎠若设mW的特征值是12mηηη≥≥≥,则有12||||,mηε−≤2||||,2,3,,iimηε=≤.又由Gerschgorin定理可知ε的特征值都在圆域(0,||||)oε∞中,且根据定理的条件可知1||||mεσ∞≤,于是有11,mmησ−≤1,2,3,,imimησ=≤.由mW的任意性可得1,1,2,,iiinnikλσ−=≤,11max,1,2,,iiiknikknλσ=++≤≤≤.由此不难看到,当1σ充分小时,如11/2nσ≤,则有11,1,2,,22iiinnikλ−+=≤≤,11,1,2,,22iikknλ−=++≤≤.故结论成立.□在定理2的证明过程中,若记()1iσ为矩阵()(1,2,,)iniiERVVik−×=的最大元素,则有()111maxiikσσ≤≤≥.显然()1iσ越小,类iV中的元素就越相似,因此本文称()1iσ为类iV的离散度,称1σ为集合V的类内离散度.定理3设,1max(1)ijijrσ−≤,1,1,2,,inik=,12,,,kλλλ是W的前k个特征值,12,,,kxxx是相应的正交单位特征向量,TTTT1212(,,,)(,,,)nX==kxxxααα,则当1σ充分小时有T221,,;cos(,)0,,.vvijvvijθ⎧⎪==⎨⎪⎩属于同一类不属于同一类ijijijαααααα证明仅对3k=的情形进行证明,其余情形的证明方法与此类同.根据引理2和定理2,若T12(,,,)(1,2,3)iiiniyyyi==iy满足2,1,1,2,3,iniWiλ===iiiyyy则TT11(,0,0)y=β,TT22(0,,0)y=β和TT33(0,0,)y=β是矩阵W对应于123,,λλλ的特征向量,由于123123(,,)(,,)LL=xxxβββ,故存在正交矩阵33()ijQq×=,满足532中国科学E辑信息科学第37卷123123(,,)(,,)Q=xxxβββ=312123123123T111111112212211331331111211212222221332332111311312232231333333,,,,,,,,,,,,,,,,,,nnnnnnnnnnnnyqyqyqyqyqyqyqyqyqyqyqyqyqyqyqyqyqyq⎛⎞⎜⎟⎜⎟⎜⎟⎜⎟⎜⎟⎜⎟⎝⎠,由Q的正交性立得结论成立.□注2由定理3的证明过程可知,如果1min1ikin≤≤,那么即使集合V的类内离散度较大,即1σ