谱聚类算法及其研究进展.doc

谱聚类算法及其研究进展 　　摘要：谱聚类具有良好的理论基础，被广泛应用于科学研究与工程应用的各个领域，成为聚类分析领域重要的新兴分支，受到越来越多的研究者的重视。然而，国内相关文献较少，该文从谱聚类算法的产生、研究进展、基础理论及代表算法等方面对谱聚类算法作简要综述，有望使读者对该领域形成初步认识。 　　关键词：谱聚类；聚类；图划分 　　中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2016）19-0159-03 　　Spectral Clustering and its Research Progress 　　XING Jie-qing， FU Chuan-yi 　　（Department of Modern Education Technology， Qiongtai Normal College， Haikou 571100， China） 　　Abstract：Spectral clustering has good theoretic foundation， and has been applied in various science research and engineering fields. It becomes an important new popular tool for clustering analysis. With its development， spectral clustering attracts much more attention from researchers. However， there are few literatures on it. This paper gives a brief review about the creation， development， theoretic analysis and classical methods of spectral clustering. 　　Key words： spectral clustering； clustering； graph partition 　　聚类作为无监督学习方法，广泛地应用于统计科学、计算机科学、生物学、社会学以及心理学等，成为应用最多的数据分析技术之一。其中，基于谱图划分理论的聚类方法――谱聚类，是目前研究较多、有深厚理论基础、应用广泛的聚类方法。与传统的方法（如k-means，EM等）相比，它不对样本空间的整体结构做任何假设，能够识别样本点在空间上的非凸分布。因此，谱聚类方法适用于具有任何分布形状的样本空间，从而求解到全局最优解。此外，谱聚类使得聚类算法的研究得到很大的拓展，适用于许多现实应用问题，已成功地应用于文本分析、语音分析、图像分割、机器视觉、商业分析、市场营销、计算生物学等等[1-3]。目前，谱聚类方法的应用还扩展到医学诊断[6]、DNA和蛋白质等生物信息挖掘[5]、文本主题分析[4]等领域。对谱聚类算法的研究具有科学意义和现实意义。同时，谱聚类算法在实现上仅涉及标准的线性代数方法，易于实现。 　　谱聚类算法是以图论当中的谱图理论为基础，重点在于设计合适的距离度量，计算待聚类的数据点之间的距离或相似性，构造邻接图，最后将聚类任务转化为邻接有向图的最优划分问题。本文旨在从基础理论、代表算法、比较分析等方面向读者介绍这种新型的聚类算法。 　　1 谱聚类算法研究进展 　　谱聚类的诞生可以追溯到1973年，Donath和Hoffman 首次基于邻接矩阵构造了图的划分[7]。在同一年，Fieldler发现图的二划分与Laplacian图的第二小特征向量有密切关系，并且建议使用该特征向量进行图的划分[8]。从此以后，许多研究者加入到谱聚类方法的研究队伍中，例如，Pothen， Simon， and Liou [9]、Bolla [10]、Hagen and Kahng [11]、Hendrickson and Leland [12]、Van Driessche and Roose[13]和Guattery and Miller[14]等。 　　谱聚类逐渐成为流行的聚类方法[1-6]。在算法扩展和理论分析方面涌现了大量的研究成果。Dhillon等人将谱聚类应用于联合聚类问题[14]，并分析了谱聚类与加权k-means的关系[19]。Bach等人利用谱聚类辅助学习相似性函数[9]。Kempe等人分析了再分布式环境下的谱聚类[21]。Perez等人提出了稀疏核谱聚类并应用于大尺度数据集[17]。Jia等人将集成学习方法应用于谱聚类[22]。Zhang等人设计了基于边界的多路谱聚类方法[14]。最近，王春腾等分析了维数约简与谱聚类的关系