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

Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date谱聚类算法及其研究进展谱聚类算法及其研究进展摘要：谱聚类具有良好的理论基础，被广泛应用于科学研究与工程应用的各个领域，成为聚类分析领域重要的新兴分支，受到越来越多的研究者的重视。然而，国内相关文献较少，该文从谱聚类算法的产生、研究进展、基础理论及代表算法等方面对谱聚类算法作简要综述，有望使读者对该领域形成初步认识。关键词：谱聚类；聚类；图划分中图分类号：tp311 文献标识码：a 文章编号：1009-3044（2016）19-0159-03spectral clustering and its research progressxing jie-qing， fu chuan-yi（department of modern education technology， qiongtai normal college， haikou 571100， china）聚类作为无监督学习方法，广泛地应用于统计科学、计算机科学、生物学、社会学以及心理学等，成为应用最多的数据分析技术之一。其中，基于谱图划分理论的聚类方法谱聚类，是目前研究较多、有深厚理论基础、应用广泛的聚类方法。与传统的方法（如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 roose13和guattery and miller14等。谱聚类逐渐成为流行的聚类方法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 相似图为说明谱聚类的基本理论，本节首先引入有关的基本记号和相似图概念。已知一个给定的数据集，根据已设计的距离公式可计算出样本点两两之间相似度，构造出相似性矩阵。以每个数据点为顶点，顶点与连通，给其连接边赋予非负权值，即数据点与之间的相似性。此时，基于相似性矩阵构造出无向图，其中，是顶点集合，是边集合。聚类的直接目标是将相似的点尽量放在同一簇中，而不相似的点尽量归入到不同簇中。至此，聚类问题可以转化为该无向图上的划分问题，找到图的某个分割，使得同一簇中点点间的边权值之和最大，而不同簇之间的点点间边权值之和最小。 无向图称为给定数据集的相似图，其中，顶点集，边集。在边上赋予权值，构成无向加权图，顶点与之间赋予非负权值，则有加权邻接矩阵，。特别地，当，表示两顶点间不连通。2.2 谱图划分理论谱聚类算法的思想来源于谱图划分理论19。无向加权图构造完成后，就可以寻找图的最优划分，需要建立图的最优划分准则。图论中常用的划分准则有m-cut， mbmax-cut， n-cut， average-cut，ratio-cut等。限于篇幅，本文仅对常用的划分准则规范割集准则（normalized-cut或n-cut）作简要介绍。n-cut是由shi和malik提出的，其目标函数的公式如下：其中。以ncut函数作为最小化目标函数，称为规范割集准则。从该准则的目标函数可以看出，不仅可以度量同簇样本间的相似性，还可以度量不同簇间样本的相异性。shi和malik对上述目标函数进行了拓展，提出规范关联目标函数（nassoc）：其中，与分别是在子图，内各自所有顶点间连接权值的总和。该准则衡量了同一簇内的样本间的紧凑程度。进一步的推导，可以得出ncut函数与nassoc函数之间的线性关系：。所以，最小化ncut函数与最大化nassoc函数是等价的，两个目标函数可以任选其一。在实际应用中，ncut函数更常用。3 谱聚类算法选用不同的划分准则，可以构造出不同的谱聚类算法，大致可以将谱聚类算法分为两类：迭代谱聚类和多路谱聚类。就迭代谱聚类而言，peron与freeman合作提出pf算法，其主要思想是构造样本集的相似图，计算相似性矩阵的最大特征值及其对应的特征向量，以特征向量中零元素对应的数据点为中心生成一个簇类，其余点生成另外一个类，由此迭代，得到最终聚类结果25。其他具有代表性的迭代谱聚类算法有sm算法1、slh算法6和kvv26算法等。不管是上述哪一类方法，谱聚类算法的步骤大致可以归纳为如下三步：step1：构造无向图，其中，顶点集，边集。根据样本点与之间的相似性，赋予边权值，得到加权邻接矩阵，。此时，将聚类问题转化为图的最优划分问题。最优划分准则的选取直接影响谱聚类算法的效果，也是谱聚类算法研究的集中关注点。谱聚类算法改进大多集中在相似性度量函数和最优划分目标函数的设计上。step2：计算相似性矩阵的前k个特征值及其对应的特征向量，构造新的k维特征空间，将原始样本点投影到新的k维空间中。step3：在新的k维特征空间中实施传统的聚类算法，例如k-means等。4 结论谱聚类在理论和应用上都具有突出优势，近年来在学术界得到越来越多的重视，使聚类分析的研究得到延伸，适应更多的现实应用问题，已成为聚类分析中一个重要的新兴分支。本文从谱聚类的产生、发展、基本理论和代表算法等方面比较系统的总结了谱聚类算法及其研究进展，可望使读者对谱聚类形成基本的初步认识，由此将该方法应用到科学研究与工程应用的各种实际问题中。-