谱聚类算法及其应用综述

李玲俐

摘要：由于性能优越，谱聚类成为近年来聚类算法研究的热点。谱聚类算法可以在任意形状的样本空间上聚类，并能获得全局最优解。介绍了谱图的基本理论及其划分准则，探讨了谱聚类算法，并针对当前谱聚类应用展望了未来研究方向。

关键词关键词：谱聚类；谱图理论；图划分；应用研究

DOIDOI：10.11907/rjdk.161229

中图分类号：TP312文献标识码：A文章编号文章编号：16727800（2016）007005403

0引言

聚类就是按照事物的某些特征，把事物分成若干类或簇，使得在同一个类内的对象之间最大程度相似，而不同类之间的对象最大程度不同。聚类分析在数据挖掘、空间数据处理、金融数据分类和入侵检测技术等领域中都得到了广泛应用。传统的聚类算法，如Kmeans和模糊C均值算法（Fuzzy CMeans，FCM）等大都建立在凸球形样本空间上，如果样本空间不为凸，算法就会陷入局部最优。因此，学者们开始研究一种新的聚类方法——谱聚类（Spectral Clustering，SC）算法。该算法由给定的样本数据集定义一个描述数据点之间相似度的亲和矩阵，并计算矩阵的特征值和特征向量，再选择合适的特征向量聚类不同的数据点。谱聚类算法是一个判别式算法，其思想相对简单易于实现，具有识别非凸分布的聚类能力，适合处理许多实际应用问题。本文着重介绍谱聚类的基本理论、算法描述、当前应用及未来研究方向。

1谱聚类基本理论与算法描述

1.1图划分原理

谱聚类是一种基于图论的聚类方法。谱图理论是将数据聚类问题转化成图的多路划分问题，通过分割子图来聚类数据点。谱聚类能对任意形状的样本空间聚类，并能获得全局最优解，其基本思想是通过对样本数据的Laplacian（拉普拉斯）矩阵进行特征分解而得到的特征向量进行聚类。

4结语

针对kmeans算法易受初始聚类中心影响的问题，首先用人工鱼群算法的全局寻优能力搜索初始聚类中心。

为了处理大规模数据，本文提出基于Mapreduce的afsa_km算法。实验结果表明，并行化的afsa_km算法比kmeans算法有更高的准确率，基于Mapreduce实现的afsa_km算法具有良好的加速比和扩展性，效率也有很大提高。 假定将每个数据样本看作图中的顶点V，且样本中的数据对之间都有一定的相似性，由样本间的相似度，将顶点间的边E赋权重值W，得到一个无向加权图G=（V，E），V={v1，v2，...vn}表示点集。图G中，可将聚类问题转化为在图G上的图划分问题。图论中的划分准则一般有Minimum Cut、Average Cut、Normalized Cut、Minmax Cut、Ratio Cut、MN Cut等，划分准则的好坏对聚类结果的优劣产生很大影响。

1.1.1最小割集准则（Minimum Cut）

谱图分割过程中，图的边值代表顶点之间的相关性大小，假设G被划分为A、B两个子图，最小割集的代价函数为：Cut（A，B）=∑i∈A，j∈BWij其中，A∩B=φ，A∪B=V，权重Wij表示Vi与Vj之间的关系。属于子图A的顶点和属于子图B的顶点之间的所有边的和最小化，表示两个子图之间的相关性越小。Wu和Leahy[2]提出最小化上述Cut值来划分图G，即最小割集准则，是最常见也是最简单的评价方法。用该准则对一些图像进行分割也能产生不错的效果。该准则的缺点是分割图像时容易出现偏向小区域的情况。

1.1.2规范割集准则（Normalized Cut）

根据谱图理论，Shi和Malik[3]提出新的目标代价函数NCut为：NCut（A，B）=Cut（A，B）Vol（A，V）+Cut（A，B）Vol（B，V）其中，Vol（A，V）

规范割集准则即最小化NCut函数。与Minimum Cut相比，该准则能平衡类内样本间的相似度，也能平衡类间样本间的相异度，即可以避免偏向小区域分割。一般的聚类算法中，采用NCut准则的情况比较多。

1.1.3比例割集准则（Ratio Cut）

为兼顾孤立点和均衡化问题，Hagen和Kahng[4]提出了比例割集准则，其目标代价函数RCut为：RCut（A，B）=Cut（A，B）min（|A|，|B|）其中，|A|、|B|分别表示子图A、B中顶点的个数，Cut（A，B）是最小割集准则的代价函数。最小化RCut函数引入了一个规模参数作为分母，加大了类间相似性，减低了过分分割的可能性，这是优于最小割集准则的方面，但该准则会使运行速度降低。

1.1.4平均割集准则（Average Cut）

Sarkar和Soundararajan[5]提出平均割集准则，其目标函数AvCut为：AvCut=Cut（A，B）|A|+Cut（A，B）|B|AvCut同NCut函数一样，最小化目标函数都能产生较准确的划分，两个都考虑了边界损失与分割区域之间的相关性比例。而AvCut准则更容易导致欠分割或易分割出只包含几个少数顶点的极小子图的缺点。

1.1.5最小最大割集准则（MinMax Cut）

最大最小割集准则[6]是为了能够使类内顶点的连接度强，类间的连续强度能够最小化，其目标函数MCut为：MCut=Cut（A，B）Vol（A，A）+Cut（A，B）Vol（B，B）可以看出，最小化MCut函数不仅要最小化Cut（A，B），还需要最大化Vol（A，A）和Vol（B，B）。该函数不易出现分割出只包含几个顶点的较小子图，倾向于产生平衡割集，可以有效避免孤立点的出现，但实现速度较慢。

1.1.6多路规范割集准则（Multiway Normalized Cut）

Meila和Xu[7]在NCut割集函数的基础上，将图G分割成k个子图，将规范割集准则扩展到k类，这就是多路规范割集准则。其目标函数为：MNCut=Cut（A1，V-A1）Vol（A1，V）+Cut（A2，V-A2）Vol（A2，V）+...

+Cut（Ak，V-Ak）Vol（Ak，V）可以看出，当k值为2，即分割成2个子图，聚类成两类时，MNCut函数和NCut函数是相同的。多路规范割集准则在实际应用中更有效、合理，只是优化问题和最小化问题比较难于解决。

1.2谱聚类算法描述

谱聚类算法大多处理两类问题，多类聚类一般通过两路划分方法来实现。假定k是最终分类个数。谱聚类算法不是直接对数据点集的亲密度矩阵S进行分析而得出分类结果，而是要先计算k个最大的特征值和特征向量，没有充分利用包含有用划分信息的其它特征向量，其计算量较大，计算效率低，并且需要由用户事先给出聚类个数k。然后，用这些特征向量构造一个对称矩阵Q，最后对Q进行亲密度分析才得到数据集的最终聚类。因此，谱聚类算法得到的矩阵Q只是原始亲密度矩阵S的一个近似，近似的程度与k值相关，k越大，Q和S的误差越小。Q对比S的优势主要体现在对Q进行亲密度分析，比对S直接进行分析以实现的分类要容易。

目前，已经出现了许多谱聚类模型和算法，如PF算法、SM算法、SLH算法、KVV算法、MCut算法等几种迭代谱聚类算法；还有多路谱聚类算法，包括MS算法和NJW算法等。

2当前研究和应用

2.1图像分割应用

谱聚类算法最初应用在图像分割中。Shi和Malik采用2way NCut的谱聚类算法对图进行迭代分割，得到满意的聚类效果。但传统谱聚类算法易受到彩色图像大小和相似性测度的影响，会导致计算量大和分割精度低的问题。文献提出了一种谱聚类分割算法，该算法基于超像素集测地线特征。先对彩色图像进行预分割得到超像素集，以超像素集为基础构造加权图，利用测地线距离特征和颜色特征构造权值矩阵，再应用NJW算法得到最终的分割结果，实验表明该算法在分割精度和计算复杂度上都有较大改善。

2.2半监督学习应用

文献提出了一种有约束的半监督谱聚类特征向量选择算法。该算法通过大量的监督信息寻找能体现数据结构特征的向量组合，来获得优于传统谱聚类算法的聚类性能，采用MNIST手写体数据集和UCI标准数据集进行仿真实验，结果验证了该算法的有效性和鲁棒性。

2.3大数据分析应用

李斌等提出了一种新的聚类算法NGKCA。首先利用谱聚类NJW算法对大数据集进行列降维和数据归一化处理，其次引入对初始值不敏感的粒子群算法对数据集进行行降维从而选出临时的聚类中心集，接着通过全局kmeans算法获取聚类中心点，最后使用粒子群算法调整聚类中心点获取最终的聚类划分。实验结果表明，该算法具有更好的稳定性和更高的检测率、更优的时间复杂度，适用于解决大数据环境下的聚类问题。

2.4其它应用

朱正伟提出基于谱聚类的入侵检测技术，采用KDD CUP99数据集实验，结果表明谱聚类的检测率和误报率普遍优于Kmeans和层次聚类算法。周林等提出基于谱聚类的聚类集成算法。先利用谱聚类的内在特性构造多样性的聚类成员，然后用连接三元组算法计算相似度矩阵，再对该矩阵使用谱聚类算法以得到集成结果。最后，用Nystrom采样算法有效降低了算法的计算复杂度，使得算法能扩展到大规模应用。实验结果表明，较之其它常见的聚类集成算法，该算法更优越、更有效，能较好地解决数据聚类、图像分割等问题。

3研究展望

谱聚类算法是应用矩阵谱分析理论得到聚类数据的新特征，利用新的数据特征对原数据进行聚类。从国内外研究现状来看，谱聚类算法已被广泛运用于各个领域，并取得很好的效果。但是，谱聚类算法仍然存在一些亟待深入研究的问题：

（1）如何智能地确定需要聚类的个数。这不仅仅是谱聚类，也是其它很多聚类算法所面临的困难和挑战。目前已有的谱聚类算法中，如RCut、NLDR（Nonlinear Dimensionality Reduction，非线性降维）算法能够自适应确定聚类个数，但是聚类效果并不是很理想，亟需改进。

（2）如何解决模糊聚类问题。谱聚类算法来源于谱图分割领域，图分割后一般子图与子图之间是不重叠的。谱聚类算法在面对这种情况时往往聚类效果不佳。

（3）如何运用到海量数据中。谱聚类算法涉及到求解大型矩阵的特征值分解问题，其计算复杂度高、计算量和存储量太大，不利于在大规模数据中计算和扩展，这对谱聚类的应用前景非常不利。虽然己经有研究者提出优化这一问题的方法，但仍然是未来研究的方向。

（4）如何与深度学习相融合。近年来深度学习发展迅猛，文献介绍了谱算法中算子谱刻画映射的能力，学者们开始思考将谱聚类算法与深度学习相结合并帮助提高算法效率。

参考文献：

蔡晓妍，戴冠中，杨黎斌.谱聚类算法综述[J].计算机科学，2008，35（7）：1418.

WU Z，LEAHY R.An optimal graph theoretic approach to data clustering：theory and its application to image segmentation[J].IEEE Trans on PAMI，1993，15（11）：11011113.

SHI J，MALIK J.Normalized cuts and image segmentation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2000，22（8）：888905.

HAGEN L，KAHNG A B.New spectral methods for ratio cut partitioning and clustering[J].ComputerAided Design，1992，11（9）：10741085.

SARKAR S，SOUNDARARAJAN P.Supervised learning of large perceptual organization：Graph spectral partitioning and learning automata[J].IEEE Transaction on Pattern Analysis and Machine Intelligence，2000，22（5）：504525.