谱聚类算法及其研究进展分析研究 物理学专业VIP专享VIP免费

摘要：谱聚类具有良好的理论基础，被广泛应用于科学研究与工程应用的各个领域，成为聚类分析领域重要的新兴分支，受到越来越多的研究者的重视。然而，国内相关文献较少，该文从谱聚类算法的产生、研究进展、基础理论及代表算法等方面对谱聚类算法作简要综述，有望使读者对该领域形成初步认识。聚类作为无监督学习方法，广泛地应用于统计科学、计算机科学、生物学、社会学以及心理学等，成为应用最多的数据分析技术之一。其中，基于谱图划分理论的聚类方法――谱聚类，是目前研究较多、有深厚理论基础、应用广泛的聚类方法。与传统的方法（如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相似图为说明谱聚类的基本理论，本节首先引入有关的基本记号和相似图概念。已知一个给定的数据集，根据已设计的距离公式可计算出样本点两两之间相似度，构造出相似性矩阵。以每个数据点为顶点，顶点与连通，给其连接边赋予非负权值，即数据点与之间的相似性。此时，基于相似性矩阵构造出无向图，其中，是顶点集合，是边集合。聚类的直接目标是将相似的点尽量放在同一簇中，而不相似的点尽量归入到不同簇中。至此，聚类问题可以转化为该无向图上的划分问题，找到图的某个分割，使得同一簇中点点间的边权值之和最大，而不同簇之间的点点间边权值之和最小。无向图称为给定数据集的相似图，其中，顶点集，边集。在边上赋予权值，构成无向加权图，顶点与之间赋予非负权值，则有加权邻接矩阵，...