第6卷第5期 智能系统学报 Vol.6 No.5 2011年10月 CAAI Transactions on Intelligent Systems 0ct.2011 doi:10.3969/i.i8sn.1673-4785.2011.05.004 谱图聚类算法研究进展 李建元1，周脚根2，关估红1，周水庚3 (1.同济大学计算机科学与技术系，上海201804；2.上海市农业科学院数字农业与工程技术研究中心，上海 201106:3.复旦大学上海市智能信息处理重，点实验室，上海200433) 摘要：近10多年来，关于谱图聚类的研究成果非常丰富，为了总结和理清这些工作之间的脉络关系，揭示最新的研 究趋势，回顾和比较了典型的图割目标函数，以及这些目标函数的谱宽松解决方法，总结了谱聚类算法的本质.另 外，讨论了谱图聚类的几个关键问题：相似图的构建方法、复杂性与扩充性、簇数估计、半监督谱学习等.最后，展望 了谱图聚类算法的主要研究趋势，如探寻其理论解释，构建更贴切的相似图，通过学习筛选特征，应用实例化等」 关键词：谱图聚类：图割目标函数：谐宽松方法：相似图构建；半监督学习 中图分类号：TP301.6文献标志码：A文章编号：16734785(2011)050405-10 A survey of clustering algorithms based on spectra of graphs LI Jianyuan',ZHOU Jiaogen2,GUAN Jihong',ZHOU Shuigeng' (1.Department of Computer Science Technology,Tongji University,Shanghai 201804,China;2.Center of Information Technology in Agriculture,Shanghai Academy of Agricultural Sciences,Shanghai 201106,China;3.Shanghai Key Lab of Intelligent Information Processing,Fudan University,Shanghai 200433,China) Abstract:Over the past decade,a huge amount of research has covered the clustering algorithms that are based on the spectra of graphs.It is essential to analyze the relationships among those works so as to reveal the research tend- encies.In this paper,the typical works on topics ranging from cost functions to spectral relaxation solutions were investigated and compared in an effort to clearly reveal the essence of these algorithms.Furthermore,the focus was concentrated on several crucial technical issues,including the construction of similarity graphs,the estimation of the clusters'number,the complexity and scalability,and semi-supervised spectral learning.Finally,some open issues were highlighted for future studies,e.g.,finding more theoretical interpretations of spectral clustering,con- structing better similarity graphs,selecting features via learning,and the instantiations of concrete fields. Keywords:spectral clustering;graph-cut objectives;method of spectral relaxation;construction of similarity graphs;semi-supervised learning 聚类技术是探测数据分析的关键步骤，具有非 图分割为若干不连通的子图.子图中包含的点集被 常重要的科学地位和应用价值.传统的聚类算法如 视为簇.以聚类为目的的图割优化目标通常均为NP K-means和EM21等，它们虽然简单，但缺乏处理 离散最优化问题，谱聚类的提出使得问题可以在多 复杂簇结构的能力，并可能陷入局部解.近10余年 项式时间内求解.较之K-means等传统算法，谱聚类 来，谱聚类算法作为一种有竞争力的技术，成为一个 还具有另一优势：它可以处理更为复杂的簇结构 新的研究热点，与之相关的研究成果也颇为丰富. (如非凸数据341)，并找到全局宽松解.故而，谱聚 谱聚类是一类基于图论的聚类算法，其算法框 类已被推广应用到许多领域，如计算机视觉5]、集 架一般包括两大步：首先构造一个相似图用以描述 成电路设计9、负载均衡o山、生物信息51、文本 数据点之间的相似关系；然后根据某个优化目标将 分类167等. 谱聚类技术可以从以下几个角度进行分类：1) 收稿日期：2010-10-12. 基金项目：国家自然科学基金资助项目(60873040). 从是否考虑样本外扩展的角度，可以将其分为离线 通信作者：李建元.E-mail:jy79@gmail.com
·406 智能系统学报 第6卷 谱聚类（如文献[3,5,18-19]等）和增量谱聚类（如 0.关于图论的基本知识，可参考最新版图论教 文献[20-21]等)：2)从是否具有约束条件或者先验 程21 知识的角度，可以将其分为无监督谱聚类和约束谱 I B C 聚类（如文献[22]等）；3)按优化目标的个数可以将 其分为单目标优化（绝大多数）和双目标优化（如文 献[23]等)；4)从运行环境上，可将其分为串行谱聚 (a)无向无权图 b)无向加权图 类和并行谱聚类（如文献[24]等）. 迄今为止，谱聚类技术已经得到长足的发展，总 A B C A「010 结和理清已有研究之间的关系，揭示未来的研究方 B001 -89 向是十分有必要的.已出现的综述文章各有侧重 cCL100 2●CCL30 Vema等人[s]主要从实验的角度比较了几种典型 c)有向无权图 d有向加权图 的谱聚类算法的性能，并提出若干改进算法.Lx 图1图及其邻接矩阵 burg等人[2w]从统计学习的理论高度比较了典型的 Fig.I Examples of graphs and adjacent matrices 归一化和非归一化谱聚类算法，并总结了相似图构 代数图论是图论、线性代数以及矩阵计算理论 建方法和簇数估计等问题.Maurizio等人[21调查了 相结合的交叉领域，其研究较早始于19世纪50年 基于核的聚类方法和谱方法，并得出这2种方法的 代.它是图论的分支之一，旨在利用代数方法来研究 共同本质是迹最优化问题.国内方面，关于该领域较 图，将图的特性转化为代数特性，然后利用代数特性 好的综述如文献[28]，其从算法层面上较为全面地 和代数方法推导关于图的定理.事实上，代数图论的 进行了比较 主要内容是图的谱，粗略地说，谱指的是矩阵的特征 本文尽管与上述综述文献在内容上有一些重叠 值连同其多重解(multiplicites).最早的关于代数图 之处，但却包含了一些新的内容.一方面，涉及的内 论的研究如：Fiedler3oj得出了图的连通性的代数判 容更全面、脉络关系更清楚，如从图论到代数分割特 据，即根据拉氏矩阵的第二小特征值是否为零可以 性的发展、从图割目标函数到谱图聚类算法的演变、 判断图是否连通，与第二小特征值对应的特征向量 谱图聚类算法的本质等.另一方面，讨论的问题更深 后来被命名为Fiedler向量，它包含了二分一个图所 入，如图的构建、边权的度量、簇数的估计、复杂性与 需要的指示信息.另外，Donath和Hoffman31] 扩充性、半监督谱学习.最后，总结了有待澄清的一 Bamest21和Donath3]等的理论工作建立了图的谱 些的理论和实际问题，指出了谱图聚类算法的研究 和图割之间的另一些关联.关于代数图论较全面的 趋势， 介绍可参考文献[34-36]. 1基本理论 1.2矩阵与谱 大多数的谱聚类算法是基于拉普拉斯矩阵（以 1.1图论与代数图论 下简称“拉氏矩阵”)的谱来进行的.拉氏矩阵分为 图论是数学的一个重要分支，是以1736年大数 非归一化的(L)和归一化的2种.归一化的又包括 学家欧拉关于Konigsberg七桥问题的论文为里程碑 对称方式（记作L。)和随机游走方式（记作L,),表 开始发展的.它研究的是关于图(aph)的理论和方 达式分别如下： 法.简单来说，图是点集和边集或弧集构成的图形 L.D-LD-1 其中边或弧用来表示一对节点间存在某种关系，边 L.=D-L. 或弧可以赋予权值，权值用来量化节点之间的关系， 文献[37-38]给出了非归一化拉氏矩阵的部分 根据是否加权，图可分为无权图和加权图；根据边是 特性，文献[36]进一步给出了归一化拉氏矩阵的部 否具有方向，可将图分为有向图和无向图. 分特性.拉氏矩阵的谱对于图的分割提供了极为有 常用的图的表示方法有邻接矩阵（记作A)和 用的信息，例如，基于Fiedler向量o可直接进行图 拉普拉斯矩阵（记作L).无权图的邻接矩阵表示法 的二分，基于多个主要特征向量可以进行图的k分 如图1(a)、(c)所示，用0表示一对顶点间无边，用 关于拉氏矩阵的特性，Luxburg391对其进行了较全 1表示一对顶点间存在一条边.加权图是用某个实 面的概括，在此不再赘述.关于到底应该采用非归一 数来反映顶点之间关系之不同，如图1(b)、(d)所 化拉氏矩阵还是归一化拉氏矩阵的问题上目前存在 示.拉普拉斯矩阵L=D-A,其中D为对角阵，对角 着较大的分歧.采用归一化拉氏矩阵的如文献[5， 线上的数值等于A的行和的绝对值，非对角元素为 23,40],非归一化拉氏矩阵的如文献[4142].从实
第5期 李建元，等：谱图聚类算法研究进展 ·407· 证的角度上，文献[3,5,43]提供了归一化拉氏矩阵 最小生成树(MST)聚类法是Zahn(]提出的， 更适用于谱聚类的证据，即意味着归一化谱聚类性 该算法首先由图的邻接矩阵得到最小生成树，然后 能比非归一化谱聚类好.文献[44]指出在某种特定 从最小生成树中去除掉若干权值较大的边从而产生 的条件下采用非归一化谱聚类较好.而文献[26]从 一个连通分量集，以此达到聚类的目的.该方法在探 统计一致性的理论高度，证明了归一化拉氏矩阵优 测明显分离的簇时是成功的，但若改变节点密度，其 于非归一化拉氏矩阵的事实 性能会变差.另一个缺点是，Zahn的研究是在事先 另一种可选的矩阵是概率转移矩阵（记作P), 知道簇结构（如分离簇、接触簇、密度簇等）的前提 概率转移矩阵实质上就是相似矩阵的归一化形式， 下进行的. 其表达式如下： 图的割是指去除一定的边将一个图分割为多个 P=DA 连通分量，其中被去除的边权的总和称为割（如式 由于归一化后的相似矩阵的行和为1，因此P (1)所示).Bames32]最早提出了最小割聚类准则， 中的元素可以理解为马尔可夫转移概率，2个节点 即在把一个图分割成k个连通子图时，寻求割的最 间的转移概率越大，则同簇的可能性也越大.概率转 小化.Alpert和YaoI8]较早提出了基于谱方法来解 移矩阵的谱也包含了分割图所需的必要信息，只不 决最小割准则的方法，为后来的谱聚类的发展奠定 过与拉氏矩阵谱稍有区别，例如，次大特征值的特征 了重要基础.Wu和Leahy(s6将最小割运用到图像 向量可以指示图的二分，多个主特征值的特征向量 分割领域，并基于网络最大流理论「2]来求解最小 可以指示图的k分割.有趣的是，如果入是Px=入x 割.该准则在图像分割方面有些许成功的应用，但其 的解，则1-入是方程Lx=Dx的解. 最大的问题是可能会导致分割的严重不均衡，如分 值得一提的另一种新颖矩阵是模块度矩阵（记 割出“孤点”及“小簇”.能够产生较均衡的分割的研 作B).其相关研究主要出自复杂网络社区649，它 究有Wei和Cheng提出的比率割、Shi和Malik[sI 具有明显物理意义，其表达式如下： 提出的规范割、Dig等人]提出的最小最大割和 B=A-dd Sarkar等人[s9]提出的平均割，其目标函数分别为 2m 式(2)~(5).这些优化目标能够较好地避免最小割 式中：d代表列向量，其元素为节点的度；m表示图 造成的分割严重不均衡的问题， 的总边权；B中的元素表示的是成对节点间实际的 以图的二分割为例，令V为一个给定的点集，N 边数与期望的边数之差，或者说是实际的边数超出 表示V的一个子集，用M代表八N,w(·,·)表示 期望边数的程度.因此，此类矩阵也直接促成了一个 2个点集之间边的总边权，则有： 目标函数，即最优分割应使得各社区中（与“簇”相 C (N,M)w(N,M), (1) 对应)边的稠密程度尽量超出预期。就矩阵特性而 C (N,M) 言，模块度矩阵与拉氏矩阵具有相似之处，例如：行 R(N.M)=I NII MT' (2) 和（列和）为0,0是其特征值；但又具有明显区别， N(N,M) C.(N,M)C(N,M) (3) 模块度矩阵不是一个半正定矩阵，也就是说其部分 w(N,) (M,, 特征值可能为负，就分割图方面，基于其最大特征值 Mon(N,M)= C(N,M)C(N,M) w(N,N) +(M,M)' (4) 的特征向量可以进行网络二分，基于多个主特征向 C(N,M)C(N,M) 量可以进行网络飞分， A(N.M)=NIM (5) 2主要的图割目标函数 近l0年来复杂网络的研究快速崛起，Newman 系统地研究了无权网络、加权网络乃至有向网络中 图割聚类的雏形是最小生成树方法(minimum 的网络社团结构谱算法，运用了模块度(modularity) spanning tree,,MST)0s).之后出现的目标函数有 函数进行社团发现[649]，模块度准则的思想较为新 最小割(minimum cut,Mincut)[32,s2s3)、比率割(ratio 颖：以无权图为例，当各社团中的边的比例尽可能地 cut,Rcut)[o,4s6、规范割(normalized cut, 超出“期望”的边的比例时，才认为是合理的分割. Ncut)5,]、最小最大割（max flow/min cut, 其中“期望”的边数指的是根据配置模型得到的一 MMCut)[s1和平均割(average cut,.Acut)9等.除此 种随机图模型.这显然与传统的图割聚类方法的出 以外，还有一些其他的优化目标，如用谱宽松来解决 发点不同，其目标函数为 K-means目标函数的方法I6oj,以及文献[23]提出的 (6) 双准则方法， 0=(4,-2
·408 智能系统学报 第6卷 式中：Q表示模块度；m表示图中包含的边数；k:表 xLx=Am(A,A)·n 示编号为i的节点的度(k类似)；：和巴只可取-1 另存在： 或1，当：≠巴是表示将节点i和j划分到不同社区， 反之则属于同一社区. 名=NI-M MI7INT- 1M1·√个NI/1MT=0, 3谱宽松方法解决图割问题 最小化比率割、规范割、平均割以及最大化模块 x好=N1(IM1/IN1)+ 度等，均为P离散最优化问题.幸运的是，谱方法 IM1·(INI/1MI)=n. 可以为该最优化问题提供一种多项式时间内的宽松 于是最小化平均割的问题与比率割的解决方法相 解.这里的“宽松”指的是将离散最优化问题宽松到 似，需求解Lx=x,x的离散化方法也与之类似 实数域，然后利用某种启发式方法将其重新转换为 3.1.3规范割 离散解.下面简要介绍从目标函数到谱方法的演 令指示向量x满足： 变39,46,56】 vol(M) 3.1图的二分割问题 Vvol(N),ie N; 3.1.1比率割 /vol(N) 设比率割为c,考虑一个最小化式(2)的图的二 Vvol(M),i M. 分割问题，令IN1=pm,IMI=gm,其中p,q≥0且满 则有 足p+q=1,簇指示向量x的元素满足： x"Lx =N (N,M).vol(V). =9,eN; 又因为x'Dx=vol(,故可得 L-p,ViE M. xLx =N (N,M). 令E表示一个包含n个元素的常向量，其每个元素 xDx 均设为1.因为拉氏矩阵L的各特征向量正交，而E 令g=DPx,代人上式得 又是L的一个特征向量，故可得x·E=0.若eg是连 g'L. 接N和M2个点集的边，则有x-=q-（-p)= 1g1 :=N(N.M). 1;相反，若eg不是连接N和M2个点集的边，则有 因此最小化规范割相当于求解Lx=入x或者Lx= x:-为=0.从而可得 入Dx,找到归一化拉氏矩阵的第二小特征值对应的 特征向量，然后将其离散化。 一)。 3.1.4模块度 又因为 对于任意无向加权图，令和表示整个图的总权 I x12=q'pn +p'gn (I NII MI )/n,(8) 值，d:代表节点i与其他节点之间的总权值.令B:= 合并式(7)、(8)，根据瑞利商定理可得 Ag-d,d/20,p为指示向量且仅可取1或-1，当m:= 脚器 时表示节点i与j属于同一个簇，反之属于不同的 簇.用于聚类的模块度函数可表达为 也即c≥入2/n,这将意味着图的二分割的实数域解x 由第二小特征值对应的特征向量给出，即求解方程 Lx=入x,找到入2及其特征向量.由于聚类问题是 式中：w可写作w=ol(V)/2=∑Ag,i>j；d可写作 “离散”最优化问题，故而需要将实数域解离散化， d:=vol(V)/=∑A因为∑：d:=2w=∑4，故存在 最简单的离散化方法是阈值法，即： 「V:∈N,x:≥0； B=(4-2)=d-器Σ4)=0， LV:E M,x:<0. 于是可得 3.1.2平均割 与上同理，令指示向量x的分量满足： Q=品豆uu=豆c 即矩阵的所有项之和等于0.进一步有 「TMI/INI,ieN; -√NI/IMT,i∈M. 中)=4-器g 可以得出，在非归一化拉氏矩阵L与平均割之间存 在如下关系： B
第5期 李建元，等：谱图聚类算法研究进展 ·409· 设v是矩阵B的特征向量4：的线性组合，即 可以验证，比率割下的k分割问题与平均割的 v=∑1a:4,则有a=u·y,于是有 情况类似，规范割的分割问题需要将式(9)中的 Q=ΣauBa4 拉氏矩阵L替换为归一化拉氏矩阵L,模块度的 分割问题需要将式(9)中的拉氏矩阵L替换为模块 另存在关系By=Av,故可得 度矩阵B. Q=又amya两 可见，这些最优化问题，均可运用谱方法来解 决.不同的是，比率割、最小最大割、平均割派生出非 又因为当ij时有4·4=0，而4·4：=1，故进一 归一化的谱聚类算法，而规范割派生出归一化的谱 步得到 聚类算法，模块度派生出一种新的谱分割算法，然 =2c世4=宫x, 而，它们共同的本质是约束条件下的迹最优化问 题[6]，只不过针对的矩阵不同。 若将'的取值宽松到实数域，则可得当入：取最 大特征值且ⅴ平行于其对应的特征向量时，Q取最 4谱图聚类中的几个关键问题 大值.但是网络社区分割问题仍为离散最优化问题， 4.1构图与加权 故依然需要离散化步骤.Newman的方法是使得v 令0g为点i和点j之间的边权，一种最典型的 的各分量与：的各分量符号一致，也就是使二者尽 加权方式是利用高斯衰减公式，即0= 量平行 ex即(（-I-x‖2/σ2).在给定的一个点集上建立 3.2图的k分割 相似图是谱聚类中最基本的问题，主要的方法如下， 以平均割目标函数为例，来说明图的k分割问 题的谱宽松解决方法39] 1)e图（即阈值图）：当‖：-x‖2<e时，相似 度取0，否则取w,其中e为正实数. 假定点集V可以分割为k个子集A1,A2,…,Ak, 2)k近邻图：当点i(或点)是点（或点）的k 定义指示向量h=(h,h2i,…,h)T,其中： 个邻近点之一时，相似度取0，否则取0. r1/1A:l,i∈A 3)互为k近邻图：当i点和j点互相落在对方的 0, 其他. k邻域时，相似度取0，否则设为0. 然后，令H是一个n行k列的矩阵，其列即为不同 4)b-匹配图[6s1:在度约束的前提下最小化图的 的指示向量.因为矩阵丑的各列向量是相互正交 总权值得到的一类图，可利用信任扩散方法求解其 的，即满足HH=L.于是有 权矩阵。 hZh,=2C.(4,a,) 5)拟合图]：以重构误差为优化目标，节点加 权度不小于1为约束条件，利用二次规划求得的矩 并存在 阵和图. k:Lh;=(HLH) 阈值图能够确保节点间的相邻关系几何对称， 综上可得 但阈值的选取比较困难.在一些情况下，甚至难以设 定一个恰当的阈值得到一个既连通又稀疏的图.相 对较好的选择应该是k近邻图，k容易选取也容易 2t(HLH). 1 保证得到的是一个稀疏图，但是k近邻图一般是不 故最小化平均割的问题可以等价为在约束条件 对称的，即有向图.为了使得邻近关系对称，通常的 H'H=I下求解，min,tr(HLH).若允许H中的 做法是简单地消除方向.但是这样将导致连接度的 1,2“k 不均衡性，即存在若干hub节点，从而可能对聚类问 项取任意实数，该问题可以宽松为在HH=I约束 题产生一定的负面干扰，另外，互为近邻图，虽然 下求解 能保证几何对称，可以用于捕捉那些最“重要”的 min tr(HLH), (9) 簇，但其缺点是不容易得到稀疏连通图（当参数k 即迹最小化问题.取拉氏矩阵的前k个特征向量作 较小时).b-匹配图就拓扑结构而言是规则的，在部 为列便可得到矩阵丑.然而此处H中的项在实数域 分场合下是优于：近邻图的，主要原因是其不存在 中，需要离散化才能达到分类的目的.最简单的离散 hub节点，不会造成簇间的边过分稠密的问题；其缺 化方法是在实数域解H上采用K-means算法或者 点是构建一个b-匹配图时间约为O(bn),难以扩展 其他基准算法进行子空间上的聚类， 其处理大规模的问题.拟合图是一种最新的研究成