摘要:谱聚类具有良好的理论基础,被广泛应用于科学研究与工程应用的各个领域,成为聚类分析领域重要的新兴分支,受到越来越多的研究者的重视。然而,国内相关文献较少,该文从谱聚类算法的产生、研究进展、基础理论及代表算法等方面对谱聚类算法作简要综述,有望使读者对该领域形成初步认识。聚类作为无监督学习方法,广泛地应用于统计科学、计算机科学、生物学、社会学以及心理学等,成为应用最多的数据分析技术之一。其中,基于谱图划分理论的聚类方法――谱聚类,是目前研究较多、有深厚理论基础、应用广泛的聚类方法。与传统的方法(如k-means,em等)相比,它不对样本空间的整体结构做任何假设,能够识别样本点在空间上的非凸分布。因此,谱聚类方法适用于具有任何分布形状的样本空间,从而求解到全局最优解。此外,谱聚类使得聚类算法的研究得到很大的拓展,适用于许多现实应用问题,已成功地应用于文本分析、语音分析、图像分割、机器视觉、商业分析、市场营销、计算生物学等等[1-3]。目前,谱聚类方法的应用还扩展到医学诊断[6]、dna和蛋白质等生物信息挖掘[5]、文本主题分析[4]等领域。对谱聚类算法的研究具有科学意义和现实意义。同时,谱聚类算法在实现上仅涉及标准的线性代数方法,易于实现。谱聚类算法是以图论当中的谱图理论为基础,重点在于设计合适的距离度量,计算待聚类的数据点之间的距离或相似性,构造邻接图,最后将聚类任务转化为邻接有向图的最优划分问题。本文旨在从基础理论、代表算法、比较分析等方面向读者介绍这种新型的聚类算法。1谱聚类算法研究进展谱聚类的诞生可以追溯到1973年,donath和hoffman首次基于邻接矩阵构造了图的划分[7]。在同一年,fieldler发现图的二划分与laplacian图的第二小特征向量有密切关系,并且建议使用该特征向量进行图的划分[8]。从此以后,许多研究者加入到谱聚类方法的研究队伍中,例如,pothen,simon,andliou[9]、bolla[10]、hagenandkahng[11]、hendricksonandleland[12]、vandriesscheandroose[13]和guatteryandmiller[14]等。谱聚类逐渐成为流行的聚类方法[1-6]。在算法扩展和理论分析方面涌现了大量的研究成果。dhillon等人将谱聚类应用于联合聚类问题[14],并分析了谱聚类与加权k-means的关系[19]。bach等人利用谱聚类辅助学习相似性函数[9]。kempe等人分析了再分布式环境下的谱聚类[21]。perez等人提出了稀疏核谱聚类并应用于大尺度数据集[17]。jia等人将集成学习方法应用于谱聚类[22]。zhang等人设计了基于边界的多路谱聚类方法[14]。最近,王春腾等分析了维数约简与谱聚类的关系,提出了基于维数约简的谱聚类方法:基于非负约束的谱聚类算法(nmfsc)[15]和基于独立成分分析的谱聚类(icasc)[16]。特别地,聚类方法在图像分割任务的应用中,传统的做法提取各像素点的特征向量,利用k-means等聚类方法对像素点进行聚类。这类方法固有的缺陷是对样本点的分布假设,例如k-means方法假定样本点的分布服从高斯分布。然而,在现实应用中该假设未必成立。谱聚类方法的优势在于不需要事先假定样本服从某种特定的分布,计算像素点样本之间的相似性,构造相似性矩阵,通过对相似性矩阵的谱图划分达到划分样本空间的目的,从而避免了对样本空间分布假设的依赖,使得谱聚类方法在理论上能够适应任意分布形状的样本空间。2理论基础2.1相似图为说明谱聚类的基本理论,本节首先引入有关的基本记号和相似图概念。已知一个给定的数据集,根据已设计的距离公式可计算出样本点两两之间相似度,构造出相似性矩阵。以每个数据点为顶点,顶点与连通,给其连接边赋予非负权值,即数据点与之间的相似性。此时,基于相似性矩阵构造出无向图,其中,是顶点集合,是边集合。聚类的直接目标是将相似的点尽量放在同一簇中,而不相似的点尽量归入到不同簇中。至此,聚类问题可以转化为该无向图上的划分问题,找到图的某个分割,使得同一簇中点点间的边权值之和最大,而不同簇之间的点点间边权值之和最小。无向图称为给定数据集的相似图,其中,顶点集,边集。在边上赋予权值,构成无向加权图,顶点与之间赋予非负权值,则有加权邻接矩阵,...