第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),难以扩展 其他基准算法进行子空间上的聚类， 其处理大规模的问题.拟合图是一种最新的研究成
.410 智能系统学报 第6卷 果，此类图能更自然地表达数据间的关系，且能从理 力，但其算法是应用在网络社区发现问题中的，在点 论上保证图的稀疏性，其缺点依然是构图的时间耗 集聚类问题上，尚需推广和验证， 费太大 4.3复杂性与扩充性问题 总的来看，尽管新的构图方法具有一些好的特 快速求解稀疏矩阵的特征值和特征向量的主要 性，但考虑到其时间耗费巨大，不及近邻图或者互 算法是Arnoldi或者Lanczos算法，其他快速方法几 为k近邻图经济实用.近来的一些理论研究已经着 乎都是它们的变体，关于特征空间求解方法的总结 眼于讨论k的界，即k大于多少时可以保证k近邻 可参看文献72]. 图的连通性.例如，针对包含足够多数据点的平面泊 以非归一化谱聚类为例，即求解Lx=入x,采用 松分布数据，Xue和Kumer6]证明了当k≥ Lanczos算法求解的时间复杂性分析如下，设图的总 5.1774×logn时k近邻图连通的概率为1.Balister 边数为m,考虑典型的稀疏矩阵（即满足m与节点 等人[]进一步证明了更紧的界，即当≥ 数n成线性关系)，特征方程左边需要O(m)次操 0.5139×logn时，k近邻图连通的概率为1，Brito等 作，右边需要O(n)次操作，共O(m+n)次操作.再 人[利用蒙特卡罗仿真得出了一些实证的参数，这 考虑上Lanczos算法的迭代次数O(n),求解一个二 些结果为参数k的选取提供了一定的依据， 分问题的时间约为O(n2).于是，重复二分谱聚类问 σ是高斯核参数，许多研究者都将其设为一个 题的时间复杂性约为O(n'log n),解决k路谱聚类 全局值31，其取值范围一般满足‖x-‖>σ> 问题约为O(m),空间复杂性为O(n2),只有采用 0,通过加入参数σ，将原始的相似关系映射到其他 优化方法存储稀疏矩阵，才能降低其空间复杂性和 空间.考虑到机器的计算精度，过小的σ会导致相 时间复杂性 似图不连通，然而，全局设定σ的值实际上在一些 些改进的谱算法试图更快速实现该类算法， 情况下并不是理想的方法.文献[19]探讨了自适应 如Fowlkes等人[]运用Nystrom近似方法避免计算 设定局部参数的方式，能够更加恰当地描述节点间 整个相似矩阵，Dhillon等人[741提出了一种不使用特 的邻域关系，其表达式如下： 征向量的方法，Yan等人[51基于局部K-means聚类 0g=exp(-‖x:-x‖2/(o0)). 或者随机投影树来快速近似谱聚类.这些方法虽然 式中：σ：取点i与其第K个邻近点之间的距离，σ 改善了扩充性问题，但是损失了精度，而且没有讨论 类似.K是一个独立的参数，从几何意义上讲，它是 空间复杂性方面的瓶颈问题然而不论采取何种特 嵌入空间的数据维数的函数，K的选取较σ更容易. 征求解方法，当面对大规模的数据集时，都可能会遭 该方法对于常用的人工数据（如环形嵌套的簇结 遇空间上的瓶颈。考虑最坏的情况，也即非稀疏矩 构、簇间密度不同的问题等)的处理效果较好. 阵，设数据规模n=10,采用邻接矩阵表示法或者 4.2簇数估计问题 拉氏矩阵表示法，由于每个浮点型实数需要占据 自动估计簇数的研究大体上可以分为2类.一种 4Byte,则大约需要占用40GB的存储空间. 方法是通过分析特征值.文献[3]分析了在理想状况 文献[24]提出了一种并行谱聚类算法，既考虑 下（簇与簇之间的距离为无穷远）的簇数估计方法：对 了存储空间的并行使用问题，也考虑到了并行分布 于归一化相似矩阵，特征值为1的个数严格地对应着 式计算的问题.他们首先将n个数据实例分配到p 簇数.然而实际的情况没有这么简单，一种可选的方 个机器节点上，然后用最小磁盘/0方法在每个机 法是分析特征值缺口(eigen-gap)m,在部分应用中， 器节点上计算本地数据实例与所有数据实例之间的 此方法是有效的，但是其缺乏理论根据，而且缺口往 相似度.这2步与分布式特征求解和分布式参数调 往可大可小，难以取舍.文献[71]提出将相似矩阵的 整结合起来，大大加速了聚类速度，其快速求解的算 特征值大于1的个数作为簇数的方法，实质上就是一 法采用的是较流行的ARPACK及其并行版本PAR 种特征值缺口法.另一种更好的方法是分析特征向 PACK6].通过十万数量级上的文本分类和图像分 量，如文献[19]通过引入旋转矩阵和一个优化目标来 类的实证研究，表明了提出的算法有效地改善了谱 发现最佳簇数.实验表明，该方法在一些复杂的合成 聚类算法难以扩充到大规模数据集的问题。可见，若 数据集和图像分割应用上是有效的 要解决大规模数量级的谱聚类问题，需要借助于并 值得注意的是，以上这些方法要么是基于谱来 行算法。 估计簇数，要么是基于新的优化目标来估计簇数.而 4.4半监督谱学习 直接基于图割优化目标来确定簇数的研究尚少.虽 通常，与分类问题本身无关的特征会使得大多 然Newman[]提出的重复二分谱算法具有这种能 数的谱聚类算法的性能大打折扣.几乎所有谱聚类
第5期 李建元，等：谱图聚类算法研究进展 。411 的应用都是在某种相似性度量假设基础之上进行 图割优化目标的指导下发现簇数是值得思考的： 的，这些算法的成功依赖于度量方式的选择，而已有 5)探讨基于其他矩阵的谱聚类算法.如文中提 的大多数谱聚类算法对于不相关的特征具有较差的 及的模块度矩阵，它与拉氏矩阵的特性相似但又有 鲁棒性].这种情况需要结合先验知识来解决，在 很大区别，该算法在处理真实网络时表现出很好的 许多情况下，某些先验知识是可以获得的，如文献 性能，但是推广其用于谱聚类，依然有许多问题值得 [78]提及的空间一致性先验信息，文献[79]在相似 探讨 性度量时依靠结合知识来减轻不相关特征造成的影 6)如何在构建相似图的过程中进行自动特征 响，文献[77,80]提出了从数据中自动学习的方式 筛选.例如：针对高维数据，L1图的构建可以有效地 来确定恰当的核或者相似性度量方法，文献[77]提 捕捉最稀疏的特征，从而得到非常高的聚类和分类 供了一个基于实例的相似矩阵学习的总体框架，文 准确性[82] 献[78]提出了一种从数据中学习先验知识的密度 7)如何快速解决大规模或超大规模的谱聚类 敏感的半监督聚类算法等，均取得了较好的效果 问题.随着经济和社会的发展，在许多行业中，需要 处理的数据规模与日俱增，虽然现有的研究已经能 5 结论与展望 够解决10万数量级的问题，但是解决更大规模的问 图分割的本质可以归结为矩阵的迹最小化或最 题仍然具有挑战性. 大化问题，而完成该最小化或最大化的任务需要依 8)应用实例化.与各学科或应用领域相结合，通 靠谱聚类算法.在绝大多数情况下，归一化谱聚类的 过改进典型的谱聚类算法切实解决实际问题。例如， 性能超过非归一化谱聚类的性能，所以归一化谱聚 在网络文档分类中，如何恰当地利用全局一致性信 类的应用更为广泛.它之所以吸引了大批研究者，最 息，如何增量地聚类动态更新的博客社区等 主要的原因有3点：1)它具有坚实的理论基础 参考文献： 代数图论；2)对于较复杂的簇结构，它能得到全局 宽松解；3)它能在多项式时间内解决问题.近年来， [1]LLOYD S P.Least squares quantization in PCM[J].IEEE 在与图和网络相关的领域中，个性化的改进算法层 Transactions on Information Theory,1982,28(2):129- 137. 出不穷，在某种程度上，谱聚类已经成为现代最流行 [2]DEMPSTER A P,LAIRD N M,RUBIN D B.Maximum 的聚类算法之一 likelihood from incomplete data via the EM algorithm[J]. 以下提出今后依然需要探讨的几点问题 Joural of the Royal Statistical Society-Series B:Statistical 1)谱聚类的理论解释.例如，在谱聚类中，采用 Methodology,1977,39(1):1-38. 哪些特征向量最好？应该采用多少个特征向量最 [3]NG A Y,JORDAN M I,WEISS Y.On spectral clustering: 好？为什么？采用部分特征向量张成的子空间，保 analysis and an algorithm[C]//PIETTERICH T G,BECK- 留了什么信息？损失了什么信息？ ER S,GHAHRAMANI Z.Advances in Neural Information 2)如何更恰当地构建相似图，相似图构建的好 Processing Systems.Cambridge,USA:MIT Press,2001: 坏决定着谱聚类性能.近来提出的b-匹配图和拟合 849-856. [4]RAHIMI A,RECHT B.Clustering with normalized cuts is 图就是非常有趣和有用的方法，尽管已有的构建方 法已经不少，但关于该问题依然需要推陈出新，最核 clustering with a hyperplane[C]//Statistical Learning in Computer Vision Workshop in ECCV 2004.Prague,Czech 心的一点是如何本质地描述数据之间的关系， Republic,2004:1-12 3)加权方式或者参数选择.虽然构图的同时已 [5]SHI J B,MALIK J.Normalized cuts and image segmenta- 经加权，但也可以考虑重新加权的问题.例如，流形 tion[J].IEEE Transactions on Pattern Analysis and Ma- 学习领域的一个重要概念“局部线性重构”[川就是 chine Intelligence,2000,22(8):888-905. 一种有效的重加权方式.再比如，高斯核参数是谱聚 [6]MALIK J,BELONGIE S,LEUNG T,et al.Contour and 类中的一个非常敏感的参数，该参数选择的恰当与 texture analysis for image segmentation[J].International 否直接影响着聚类的效果，关于自动选取该参数的 Joumal of Computer Vision,2001,43(1):7-27. [7]ZHANG X R,JIAO L C,LIU F.Spectral clustering ensem- 研究是另一个难题： ble applied to SAR image segmentation[J].IEEE Transac- 4)如何将优化目标与簇数估计相结合，已有的绝 tions on Geoscience and Remote Sensing,2008,46(7): 大多数谱算法并不能根据其图割优化目标来决定簇 2126-2136. 数，也就是说在算法运行之前簇数是给定的.然而，在 [8]陶文兵，金海.一种新的基于图谱理论的图像阈值分割 许多应用场合中，事先知道簇数是不现实的，如何在 方法[J].计算机学报，2007,30(1)：110-119
·412. 智能系统学报 第6卷 TAO Wenbing,JIN Hai.A new image thresholding method [21]ALZATE C,SUYKENS J A K.Multiway spectral cluste- based on graph spectral theory[J].Journal of Computers, ring with out-of-sample extensions through weighted kernel 2007,30(1):110-119. PCA[J].IEEE Transactions on Pattern Analysis and Ma- [9]ALPERT C J,KAHNG A B.Multi-way partitioning via geo- chine Intelligence,2010,32(2):335-347. metric embeddings,orderings and dynamic programming [22]YU S X,SHI J B.Grouping with bias[C]//The Fifteenth [J].IEEE Transactions on Computer-Aaided Design of In- Annual Conference on Neural Information Processing Sys- tegrated Circuits and Systems,1995,14(11):1342-1358. tems.Vancouver,Canada,2001:1327-1334. [10]DRIESSCHE R V,ROOSE D.An improved spectral bi- [23]KANNAN R,VEMPALA S,VETTA A.On clusterings: section algorithm and its application to dynamic load balan- good,bad,and spectral[J].Journal of the ACM,2004, cing[J].Parallel Computing,1995,21(1):29-48. 51(3):497-515. [11]HENDRICKSON B,LELAND R.An improved spectral [24]SONG Yangqiu,CHEN Wenyen,BAI Hongjie,et al.Par- graph partitioning algorithm for mapping parallel computa- allel spectral clustering[C]//European Conference on Ma- tions[J].SIAM Journal on Scientific Computing,1995, chine Learning and Principles and Practice of Knowledge 16(2):452459. Discovery in Databases.Antwerp,Belgium,2008:374- [12]CRISTIANINI N,SHAWE-TAYLOR J,KANDOLA J. 389. Spectral kemel methods for clustering[C]//Proceedings [25]VERMA D,MEILA M.A comparison of spectral cluste- of the Neural Information Processing Systems.Vancouver, ring algorithms,Technical Report UW-CSE-03-05-01[R]. Canada,2001:649655. Seattle,USA:Department of CSE,University of Washing- [13]KLUGER Y,BASRI R,CHANG J T,et al.Spectral bi- ton,2003. clustering of microarray data:coclustering genes and con- [26]LUXBURG U,BELKIN M,BOUSQUET O.Consisteney ditions[J].Genome Research,2003,13(4)703-716. of spectral clustering[J].Annals of Statistics,2008,36 [14]KULIS B,BASU S,DHILLON IS,et al.Semi-supervised (2):555586. graph clustering:a kemel approach[C]//International [27]FILIPPONE M,CAMASTRA F,MASULLI F,et al.A Conference on Machine Learning.New York,USA:ACM survey of kemel and spectral methods for clustering[J]. Pre8s,2005:457464. Pattern Recognition,2008,41(1):176-190. [15]PACCANARO A,CHENNUBHOTLA C,CASBON J A. [28]蔡晓妍，戴冠中，杨黎斌.谱聚类算法综述[J].计算机 Spectral clustering of protein sequences[].Nucleic Acids 科学，2008,35(7)：14-17. Research,2006,34(5):1571-1580. CAI Xiaoyan,DAI Guanzhong,YANG Libin.Survey on [16]DHILLON I S.Co-clustering documents and words using spectral clustering algorithms [J].Computer Science, bipartite spectral graph partitioning[C]//Proceedings of 2008,35(7):14-17. the Seventh ACM SIGKDD International Conference on [29]DIESTEL R.Graph theory[M].4th ed.Heidelberg,Ger- Knowledge Discovery and Data Mining.New York,USA: many:Springer-Verlag,2010. ACM Press,2001:269-274. [30]FIEDLER M.Algebraic connectivity of graphs[J].Czech- [17]谢永康，周雅倩，黄萱菁.一种基于谱聚类的共指消解 oslovak Mathematical Joural,1973,23(98):298-305. 方法[J].中文信息学报，2009,23(3)：10-16 [31]DONATH W E,HOFFMAN A J.Lower bounds for the XIE Yongkang,ZHOU Yagian,HUANG Xuanjing.A partitioning of graphs[J].IBM Joumal of Research and spectral clustering based coreference resolution method Development,1973,17(5):420-425. [J].Journal of Chinese Information Processing,2009,23 [32]BAMES E R.An algorithm for partitioning the nodes of a (3):10-16. graph[].SIAM Joumal on Algebraic and Discrete Meth- [18]ALPERT C J,YAO S Z.Spectral partitioning:the more 0ds,1982,17(5):541-550. eigenvectors,the better[C]//Proceedings of the 32nd An- [33 DONATH W E.Logic partitioning M]//PREAS B T, nual ACM/IEEE Design Automation Conference.New LORENZETTI M J.Physical Design Automation of VLSI Yok,USA:ACM,1995:195-200. Systems.S.1.]Benjamin/Cummings Pub Co,1988: [19 ZELNIK-MANOR L,PERONA P.Self-tuning spectral 65-86. clustering[C]//Neural Information Processing Systems. [34]BIGGS N L.Algebraic graph theory M].Cambridge, Vancouver,Canada,2004,2:1601-1608. USA:Cambridge University Press,1974. [20]NING Huazhong,XU Wei,CHI Yun,et al.Incremental [35]BROUWER A E,HAEMERS W H.Spectra of graphs spectral clustering with application to monitoring of evol- [EB/OL].[2010-10-05].http://homepages.cwi.nl/~ ving blog communities[C]//Proceedings of the SIAM In- aeb/math/ipm.pdf. ternational Conference on Data Mining.Minneapolis, [36]CHUNG F.Speetral graph theory EB/OL].[2010-10- USA,2007:261-272. 05].http://www.ams.org/mathscinet-getitem?mr
第5期 李建元，等：谱图聚类算法研究进展 ·413· 1421568. [53]WU Z,LEAHY R.An optimal graph theoretic approach to [37]MOHAR B.The Laplacian spectrum of graphs M]// data clustering:theory and its application to image seg- ALAVI Y,CHARTRAND G,OELLERMANN O R,et al. mentation[J].IEEE Transactions on Pattern Analysis and Graph Theory,Combinatorics,and Applications.[S. Machine Intelligence,1993,15(11):1101-1113. 1.]:Wiey,1991,2:871-898. [54]CHAN P K,SCHLAG M D F,ZIEN J Y.Spectral k-way [38]MOHAR B.Some applications of Laplace eigenvalues of ratio-cut partitioning and clustering[J].IEEE Transactions graphs[J].Graph Symmetry:Algebraic Methods and Ap- on Computer-Aided Design of Integrated Circuits and Sys- plications,1997,497(22):227-275. tems,1994,13(9):1088-1096. [39]LUXBURG U.A tutorial on spectral clustering[J].Statis- [55]WEI Y C,CHENG C K.A two-level two-way partitioning tics and Computing,2007,17(4):395-416. algorithm[C]//IEEE International Conference on CAD. [40]WEI Y C,CHENG C K.Toward efficient hierarchical de- Santa Clara.USA,1990:516-519. signs by ratio cut partitioning [C]//IEEE International [56]HAGEN L,ANDREW B K.New spectral methods for ratio Conference on CAD.New York,USA,1989:298-301. cut partitioning and clustering[J].IEEE Transactions on [41]BARNARD S,POTHEN A,SIMON H.A spectral algo- Computer-Aided Design of Intergrated Circuits and Sys- rithm for envelope reduction of sparse matrices[J].Nu- tems,1992,11(9):1074-1085. merical Linear Algebra with Applications,1995,2(4): [57]YU S,SHI J B.Multiclass spectral clustering[C]//Pro- 317-334. ceedings of the Ninth IEEE International Conference on [42]GUATTERY S,MILLER G L.On the quality of spectral Computer Vision.Nice,France,2003,2:313-319. separators[J].SIAM Joumal on Matrix Analysis and Ap- [58]DING C,HE X,ZHA H,et al.A min-max cut algorithm plications,1998,19(3):701-719. for graph partitioning and data clustering[C]//Proceedings [43]WEISS Y.Segmentation using eigenvectors:a unifying of the 2001 IEEE International Conference on Data Min- view[C]//Proceedings of the Seventh IEEE International ing.Washington,DC,USA:IEEE Computer Society, Conference on Computer Vision.Washington,DC,USA: 2001:107-114. IEEE Computer Society,1999:975-982. [59]SARKAR S,SOUNDARARAJAN P.Supervised learning [44]HIGHAM D,KIBBLE M.A unified view of spectral clustering of large perceptual organization:graph spectral partitioning [EB/OL].[2010-10-05].http://meyer.math.ncsu.edu/Mey- and learning automata[J].IEEE Transactions on Pattern er/Courses/Selee591RPresentation.pdf,2007. Analysis and Machine Intelligence,2000,22 (5):504- 45]MEILA M,SHI J B.Learing segmentation by random 525. walks[C]//LEEN T K,DIETTERICH T G,TRESP V. [60]ZHA Hongyuan,HE Xiaofeng,DING C H Q,et al.Spec- Advances in Neural Information Processing Systems.Cam- tral relaxation for k-means clustering[C]//DIETTERICH bridge,USA:MIT Press,2001:873-879. T G,BECKER S,GHAHRAMANI Z.Advances in Neural [46]NEWMAN M E J.Finding community structure in net- Information Processing Systems.Cambridge,USA:MIT works using the eigenvectors of matrices[J].Physical Re- Pres8,2002,14:1057-1064. view E,2006,74(3):036104. [61]WU Z,LEAHY R.Tissue classification in MR images u- [47]NEWMAN M E J.Modularity and community structure in sing hierarchical segmentation [C]//1990 IEEE Nuclear networks[J].Proceedings of the National Academy of Sci- Science Symposium Conference Record,Including Sessions ences of the United States,2006,103(23):8577-8582. on Nuclear Power Systems and Medical Imaging Confer- [48 NEWMAN M E J.Analysis of weighted networks [J]. ence.Piscataway,USA:IEEE Service Center,1990: Physical Review E,2004,70(5):056131. 1410-1414. [49]LEICHT E A,NEWMAN M E J.Community structure in [62]FORD L R,FULKERSON D R.Flows in networks[M]. directed networks J].Physical Review Letters,2008, Princeton,USA:Princeton University Press,1962. 100(11):118703. [63]DHILLON I S,KULIS Y B.A unified view of kemel k- 50]ZAHN C T.Graph-theoretic methods for detecting and de- means,spectral clustering and graph partitioning,UTCS scribing gestalt clusters[J].IEEE Transactions on Com- Technical Report #TR-04-25[R].Austin,USA:Depart- puters,1971,20(1):68-86. ment of Computer Science,The University of Texas at Aus- [51]URQUHART R.Graph theoretical clustering based on lim- tin,2005. ited neighborhood sets[J].Pattern Recognition,1982,15 [64 DHILLON I S,GUAN Y,KULIS B.Kemel k-means: (3):173-187. spectral clustering and normalized cuts[C]//ACM SIGK- 52]WAGNER D,WAGNER F.Between mincut and graph bi- DD International Conference on Knowledge Discovery and section[J].Lecture Notes in Computer Science,1993, Data Mining.New York,USA:ACM Press,2004:551- 711:744-750 556
·414 智能系统学报 第6卷 [65]JEBARA T,WANG J,CHANG S.Graph construction and 2003. b-matching for semi-supervised learing[C]//Proceedings [78]王玲，薄列峰，焦李成.密度敏感的半监督谱聚类[J] of the 26th Annual International Conference on Machine 软件学报，2007,18(10)：2412-2422. Learing.New York,USA:ACM,2009:441448. WANG Ling,BO Liefeng,JIAO Licheng.Density-sensi- [66]DAITCH S I,KELNER J A,SPIELMAN D A.Fitting a tive semi-supervised spectral clustering[J].Journal of graph to vector data[C]//Proceedings of the 26th Annual Software,2007,18(10):2412-2422 Intemational Conference on Machine Learning.New York, [79]KAMVAR S D,KLEIN D,MANNING C D.Spectral USA:ACM,2009:201-208. learing[C]//Proceedings of the Eighteenth Interational [67]XUE F,KUMAR P R.The number of neighbors needed Joint Conference on Artificial Intelligence.Acapulco, for connectivity of wireless networks J].Wireless Net- Mexico,2003:561-566. work8,2004,10(2):169-181. [80]FISCHER I,POLAND I.New methods for spectral cluste- 68]BALISTER P,BOLLOBAS B,SARKAR A,et al.Con- ring,Technical Report No.IDSIA-12-04 [R].Manno, nectivity of random k-nearest-neighbour graphs[J].Ad- Switzerland:Dalle Molle Institute for Artificial Intelli- vances in Applied Probability,2005,37(1):1-24. gence,2004. 69]BRITO M R,CHFIVEZ E L,QUIROZ A J,et al.Con- [81]ROWEIS S,SAUL L.Nonlinear dimensionality reduction nectivity of the mutual k-nearest-neighbor graph in cluste- by locally linear embedding [J].Science,2000,290 ring and outlier detection[J].Statistics Probability Let- (5550):2323-2326. es,1997,35(1):3342. [82]CHENG B,YANG J,YAN S,et al.Learning with L1- [70]POLITO M,PERONA P.Grouping and dimensionality re- graph for image analysis[J].IEEE Transactions on Image duction by locally linear embedding[C]//DIETTERICH T Proce99ing,2010,19(4):858866. G,BECKER S,GHAHRAMANI Z.Advances in Neural 作者简介： Information Processing Systems.Cambridge,USA:MIT 李建元，男，1979年生，讲师，博士 Press,2001:1255-1262. 研究生，CCF及ACM学生会员，主要研 [71]田铮，李小斌，句彦伟.谱聚类的扰动分析[J].中国科 究方向为数据挖掘、机器学习、遥感与 学E辑：信息科学，2007,37(4)：527543 GIS等. TIAN Zheng,LI Xiaobin,JU Yanwei.Perturbation analy- sis of spectral clustering[J].Science in China Series E: Technological Sciences,2007,37(4):527-543. [72]HERNANDEZ V,ROMAN J,TOMAS A,et al.A survey 周脚根，男，1978年生，副研究员， of software for sparse eigenvalue problems EB/OL]. 博士，主要研究方向为空间数据挖掘和 [2010-10-05].http://www.grycap.upv.es/slepc/docu- 空间统计等。 mentation/reports/str6.pdf. [73]FOWLKES C,BELONGIE S,CHUNG F,et al.Spectral grouping using the Nystrom method[J].IEEE Transactions on Pattem Analysis and Machine Intelligence,2004,26 (2):214-225. 关佶红，女，1969年生，教授，博士 [74]DHILLON IS,GUAN Y,KULIS B.Weighted graph cuts 生导师，博士，主要研究方向为分布计 without eigenvectors:a multi-level approach[J].IEEE 算、数据库、数据挖掘、生物信息学等。 Transactions on Pattem Analysis and Machine Intelligence, 2007,29(11):1944-1957. [75]YAN D H,HUANG L,JORDAN M I.Fast approximate spectral clustering[C]//ACM SIGKDD Interational Con- ference on Knowledge Discovery and Data Mining.New 周水庚，男，1966年生，教授，博士 York,USA:ACM Press,2009:907-915. 生导师，博士，主要研究方向为网络数 [76]MASCHHOFF K J,SORENSEN D C.A portable imple- 据管理与搜索、海量数据挖掘与学习、 mentation of ARPACK for distributed memory parallel ar- 生物信息学等。 chitectures[EB/OL].[2010-10-05].http://www.caam. rice.edu/_kristyn/parpack home.html. [77]BACH F R,JORDAN M I.Leaming spectral clustering, Technical Report No.UCB/CSD-03-1249[R].Berkeley, USA:Computer Science Division,University of Califoria
