李建元，周脚根，关佶红，周水庚

(1.同济大学 计算机科学与技术系，上海 201804;2.上海市农业科学院 数字农业与工程技术研究中心，上海 201106;3.复旦大学上海市智能信息处理重点实验室，上海 200433)

谱图聚类算法研究进展

李建元1，周脚根2，关佶红1，周水庚3

(1.同济大学 计算机科学与技术系，上海 201804;2.上海市农业科学院 数字农业与工程技术研究中心，上海 201106;3.复旦大学上海市智能信息处理重点实验室，上海 200433)

近10多年来，关于谱图聚类的研究成果非常丰富，为了总结和理清这些工作之间的脉络关系，揭示最新的研究趋势，回顾和比较了典型的图割目标函数，以及这些目标函数的谱宽松解决方法，总结了谱聚类算法的本质.另外，讨论了谱图聚类的几个关键问题:相似图的构建方法、复杂性与扩充性、簇数估计、半监督谱学习等.最后，展望了谱图聚类算法的主要研究趋势，如探寻其理论解释，构建更贴切的相似图，通过学习筛选特征，应用实例化等.

谱图聚类;图割目标函数;谱宽松方法;相似图构建;半监督学习

聚类技术是探测数据分析的关键步骤，具有非常重要的科学地位和应用价值.传统的聚类算法如K－means［1］和 EM［2］等，它们虽然简单，但缺乏处理复杂簇结构的能力，并可能陷入局部解.近10余年来，谱聚类算法作为一种有竞争力的技术，成为一个新的研究热点，与之相关的研究成果也颇为丰富.

谱聚类是一类基于图论的聚类算法，其算法框架一般包括两大步:首先构造一个……