谱聚类算法及其研究进展

邢洁清　符传谊

摘要：谱聚类具有良好的理论基础，被广泛应用于科学研究与工程应用的各个领域，成为聚类分析领域重要的新兴分支，受到越来越多的研究者的重视。然而，国内相关文献较少，该文从谱聚类算法的产生、研究进展、基础理论及代表算法等方面对谱聚类算法作简要综述，有望使读者对该领域形成初步认识。

关键词：谱聚类；聚类；图划分

中图分类号：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]。最近，王春腾等分析了维数约简与谱聚类的关系，提出了基于维数约简的谱聚类方法：基于非负约束的谱聚类算法（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]和KVV[26]算法等。

就多路谱聚类而言，Ng和Jordan等人提出NJW算法，其基本思想是计算相似性矩阵的拉普拉斯矩阵，寻找该矩阵的前k个最大特征值及其对应的特征向量，将原数据点投影到k个特征向量构造的新的特征空间中，最后在新的k维空间中实施k-means，得到最终聚类结果[2]。Meila对NJW算法进行的拓展，将NJW中的k维特征空间再实施了一个线性旋转，构造出新的投影空间，然后在该空间中实施聚类[28]。

不管是上述哪一类方法，谱聚类算法的步骤大致可以归纳为如下三步：

Step1：构造无向图，其中，顶点集，边集。根据样本点与之间的相似性，赋予边权值，得到加权邻接矩阵，。此时，将聚类问题转化为图的最优划分问题。最优划分准则的选取直接影响谱聚类算法的效果，也是谱聚类算法研究的集中关注点。谱聚类算法改进大多集中在相似性度量函数和最优划分目标函数的设计上。

Step2：计算相似性矩阵的前k个特征值及其对应的特征向量，构造新的k维特征空间，将原始样本点投影到新的k维空间中。

Step3：在新的k维特征空间中实施传统的聚类算法，例如k-means等。

4 结论

谱聚类在理论和应用上都具有突出优势，近年来在学术界得到越来越多的重视，使聚类分析的研究得到延伸，适应更多的现实应用问题，已成为聚类分析中一个重要的新兴分支。本文从谱聚类的产生、发展、基本理论和代表算法等方面比较系统的总结了谱聚类算法及其研究进展，可望使读者对谱聚类形成基本的初步认识，由此将该方法应用到科学研究与工程应用的各种实际问题中。

参考文献：

[1] Ahn I， Kim C. Face and Hair Region Labeling Using Semi-Supervised Spectral Clustering Based Multiple Segmentations[J]. IEEE Transactions on Multimedia， 2016：1-1.

[2] Petkos G， Schinas M， Papadopoulos S， et al. Graph-based multimodal clustering for social multimedia[J]. Multimedia Tools & Applications， 2016：1-23.

[3] 崔丽，陈睿，李华. 拓扑图格独立分量分析和谱聚类支持的纹理探测[J]. 计算机辅助设计与图形学学报，2005，17（5）：，935-940.

[4] Hou H X， Yuan M M， Liu C X. Indirect spectral clustering towards large text datasets[J]. Journal of Computer Applications， 2013， 32（12）：3274-3277.

[5] Huang L， Liao L， Wu C H. Inference of protein-protein interaction networks from multiple heterogeneous data[J]. Eurasip Journal on Bioinformatics & Systems Biology， 2016， 2016（1）：1-9.

[6] Wang D， Gu J. Integrative clustering methods of multi-omics data for molecule-based cancer classifications[J]. Quantitative Biology， 2016：1-10.

[7] Donath W E， Hoffman A J. Lower bounds for the partitioning of graphs. IBM J. Res. Develop. 1973（17）：420-425.

[8] Fiedler M. Algebraic connectivity of graphs. Czech， Math. J.， 1973（23）：298-305.

[9] Pothen A， Simon H D， Liou K P. Partitioning sparse matrices with eigenvectors of graphs. SIAM Journal of Matrix Anal. Appl.， 1990（11）：430-452.

[10] Simon， H. Partitioning of unstructured problems for parallel processing. Computing Systems Engineering， 1991（2）：135-148.

[11] Hagen L， Kahng A B. New spectral methods for ratio cut partitioning and clustering. IEEE Transactions on Computer-aided Design， 1992（9）：1074-1085.

[12] Hendrickson， B. and Leland， R. An improved spectral graph partitioning algorithm for mapping parallel computations. SIAM J. on Scientic Computing， 1995（16）：452-469.

[13] Van Driessche， R. and Roose， D. An improved spectral bisection algorithm and its application to dynamic load balancing. Parallel Comput.， 1995，21（1）：29-48.

[14] Dhillon， I. Co-clustering documents and words using bipartite spectral graph partitioning. In Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining， New York： ACM Press， 2001， pp.269–274.

[15] 王春腾，符传谊.基于非负约束的谱聚类算法[J].电脑知识与技术，2011，17（41）：65.

[16] 王春腾，符传谊.基于独立成分分析的谱聚类方法[J].安徽电子职业技术学院学报2011，6（42）：51.

[17] Perez A， Andres C， and Johan S. Sparse Kernel spectral clustering models for large-scale data analysis， Neurocomputing， 2011， v74（9）， p1382-1390

[18] Zhang Z and Jordan M. I.， Multiway Spectral Clustering： A Margin-Based Perspective， V23（3）， 2008， p383-403

[19] Dhillon， I.， Guan， Y.， and Kulis， B. A unied view of kernel k-means， spectral clustering， and graph partitioning. University of Texas at Austin， 2005

[20] Bach， F. and Jordan， M. Learning spectral clustering. In S. Thrun， L. Saul， and B. Sch?lkopf （Eds.）， Advances in Neural Information Processing Systems. Cambridge， MA： MIT Press， 2004.

[21] Kempe， D. and McSherry， F. A decentralized algorithm for spectral analysis. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing . New York， NY， USA： ACM Press， 2004， pp. 561–568.

[22] Jia J， Xiao X， Liu B and Jiao L， Bagging-based spectral clustering ensemble selection， Pattern Recognition Letter， v32（10）， 2011.

[23] Ding C， He X， Zha H， et al. A min-max cut algorithm for graph partitioning and data clustering. In Proceedings of therst IEEE International Conference on Data Mining， Washington， DC， USA： IEEE Computer Society， 2001：107-114

[24] Guattery S， Miller G L. On the quality of spectral separators. SIAM Journal of Matrix Anal. Appl.， 1998，19（3）：701-719.

[25] Perona P，Freeman W T.A factorization approach to grouping， Proc. ECCV，1998：655-670.

[26] Kannan R， Vempala S， Vetta A. On clusterings good， bad and spectral. In FOCS， 2000：367-377.

[27] Meila M， Shi J. Learning segmentation by random walks. In NIPS， 2000：873-879.