第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