谱聚类算法及其研究进展

《谱聚类算法及其研究进展》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、谱聚类算法及其研究进展　　摘要：谱聚类具有良好的理论基础，被广泛应用于科学研究与工程应用的各个领域，成为聚类分析领域重要的新兴分支，受到越来越多的研究者的重视。然而，国内相关文献较少，该文从谱聚类算法的产生、研究进展、基础理论及代表算法等方面对谱聚类算法作简要综述，有望使读者对该领域形成初步认识。　　关键词：谱聚类；聚类；图划分　　中图分类号：TP311文献标识码：A文章编号：1009-3044（2016）19-0159-03　　SpectralClusteringanditsResearchProgress　　XINGJ

2、ie-qing，FUChuan-yi　　（DepartmentofModernEducationTechnology，QiongtaiNormalCollege，Haikou571100，China）　　Abstract：Spectralclusteringhasgoodtheoreticfoundation，andhasbeenappliedinvariousscienceresearchandengineeringfields.Itbecomesanimportantnewpopulartoolforclusterin

3、ganalysis.Withitsdevelopment，spectralclusteringattractsmuchmoreattentionfromresearchers.However，therearefewliteraturesonit.Thispapergivesabriefreviewaboutthecreation，development，theoreticanalysisandclassicalmethodsofspectral10clustering.　　Keywords：spectralclusteri

4、ng；clustering；graphpartition　　聚类作为无监督学习方法，广泛地应用于统计科学、计算机科学、生物学、社会学以及心理学等，成为应用最多的数据分析技术之一。其中，基于谱图划分理论的聚类方法――谱聚类，是目前研究较多、有深厚理论基础、应用广泛的聚类方法。与传统的方法（如k-means，EM等）相比，它不对样本空间的整体结构做任何假设，能够识别样本点在空间上的非凸分布。因此，谱聚类方法适用于具有任何分布形状的样本空间，从而求解到全局最优解。此外，谱聚类使得聚类算法的研究得到很大的拓展，适用于许多现实应用问

5、题，已成功地应用于文本分析、语音分析、图像分割、机器视觉、商业分析、市场营销、计算生物学等等[1-3]。目前，谱聚类方法的应用还扩展到医学诊断[6]、DNA和蛋白质等生物信息挖掘[5]、文本主题分析[4]等领域。对谱聚类算法的研究具有科学意义和现实意义。同时，谱聚类算法在实现上仅涉及标准的线性代数方法，易于实现。　　谱聚类算法是以图论当中的谱图理论为基础，重点在于设计合适的距离度量，计算待聚类的数据点之间的距离或相似性，构造邻接图，最后将聚类任务转化为邻接有向图的最优划分问题。本文旨在从基础理论、代表算法、比较分析等方面向

6、读者介绍这种新型的聚类算法。　　1谱聚类算法研究进展　　谱聚类的诞生可以追溯到1973年，Donath和Hoffman10首次基于邻接矩阵构造了图的划分[7]。在同一年，Fieldler发现图的二划分与Laplacian图的第二小特征向量有密切关系，并且建议使用该特征向量进行图的划分[8]。从此以后，许多研究者加入到谱聚类方法的研究队伍中，例如，Pothen，Simon，andLiou[9]、Bolla[10]、HagenandKahng[11]、HendricksonandLeland[12]、VanDriesschea

7、ndRoose[13]和GuatteryandMiller[14]等。　　谱聚类逐渐成为流行的聚类方法[1-6]。在算法扩展和理论分析方面涌现了大量的研究成果。Dhillon等人将谱聚类应用于联合聚类问题[14]，并分析了谱聚类与加权k-means的关系[19]。Bach等人利用谱聚类辅助学习相似性函数[9]。Kempe等人分析了再分布式环境下的谱聚类[21]。Perez等人提出了稀疏核谱聚类并应用于大尺度数据集[17]。Jia等人将集成学习方法应用于谱聚类[22]。Zhang等人设计了基于边界的多路谱聚类方法[14]。最

8、近，王春腾等分析了维数约简与谱聚类的关系，提出了基于维数约简的谱聚类方法：基于非负约束的谱聚类算法（NMFSC）[15]和基于独立成分分析的谱聚类（ICASC）[16]。　　特别地，聚类方法在图像分割任务的应用中，传统的做法提取各像素点的特征向量，利用k-means等聚类方法对像素点进行聚类。这类方法固