#深入理解谱聚类（Spectral Clustering）：原理、对比与实战

在之前的文章里，我们介绍了比较传统的 [K-Means 聚类]、[Affinity Propagation (AP) 聚类]、比 K-Means 更快的 [Mini Batch K-Means] 聚类以及 [混合高斯模型 Gaussian Mixture Model (GMM)] 等聚类算法。今天，我们将介绍一个比较近代的一类算法—— Spectral Clustering ，中文通常称为 “谱聚类” 。

#什么是谱聚类？

Spectral Clustering（谱聚类，有时也简称 SC），其实是一类算法的统称。

它是一种基于图论的聚类方法（这点上跟 AP 类似，而 K-Means 是基于点与点的距离计算）。它能够识别任意形状的样本空间且收敛于全局最优解，其基本思想是利用样本数据的相似矩阵进行特征分解后得到的特征向量进行聚类。

为什么称谱聚类是“一类”算法？ 广义上来说，任何在演算法中用到 SVD（奇异值分解）或特征值分解的，都叫 Spectral Algorithm。从传统的 PCA/LDA，到比较近的 Spectral Embedding/Clustering，都属于这一类。

#谱聚类与 K-Means 的优势对比

谱聚类和传统的聚类方法（如 K-Means）相比，具有以下显著优点：

• 输入要求低：谱聚类只需要数据之间的相似度矩阵即可，而不必像 K-Means 那样要求数据必须是 N 维欧氏空间中的向量。
• 鲁棒性更强：由于抓住了主要矛盾，忽略了次要因素，谱聚类比传统的聚类算法更加健壮。它对于不规则的误差数据不那么敏感，聚类结果通常也更好。事实上，在各种现代聚类算法的比较中，K-Means 通常只是作为一个基准而存在。
• 理论复杂度低：计算复杂度比 K-Means 要小，特别是在处理像文本数据或平凡的图像数据这样维度非常高的数据时，理论上应该比 K-Means 更快速。（但实际情况真的是这样吗？下文的实验将给出解答。）

#实验验证：准确度与性能的较量

K-Means 一直以来都是距离算法中的经典，尤其通过 Mini Batch “改良”后的 K-Means 在大数据应用中的效率瓶颈也得到了极大改善。谱聚类这个相对的“晚生”是否真的如理论般优秀？我们来看具体的实验数据。

#实验一：关于准确度的较量

在此引用《Document clustering using locality preserving indexing》中关于 K-Means 和 Spectral Clustering 应用到 TDT2 和 Reuters-21578 这两组数据的准确率对比结果。

从准确率结果可以看出：在不同的类别数量下，谱聚类的准确率都要高于 K-Means。

#实验二：关于运行时间的较量

在此使用 Python 机器学习库 sklearn 中的 spectral_clustering 进行模拟实验。实验数据为随机生成的维度和样本量相同的矩阵，分别为 10 维、20 维、30 维、40 维、50 维、60 维（对应到图中就是从 0 到 5）。

实验发现，当尝试用更大的数据量（增加到 70 维）去测试时，spectral_clustering 已经由于内存错误而崩溃。由此可见，它对于大数据量的应用还是不适合的。

此外，虽然上文提到谱聚类的计算复杂度理论上低于 K-Means，运算时间应该更快，但实际的实验结果却未能证明这一点。

#谱聚类实战：基于 Python 的图像边缘提取

以下使用 Python 机器学习库 sklearn 中的 spectral_clustering 进行聚类，目标是从一个图片中区分出人为构造出的图像边缘。

#核心代码实现

pythonCopy
1import numpy as np   
2import matplotlib.pyplot as plt   
3from sklearn.feature_extraction import image   
4from sklearn.cluster import spectral_clustering   
5
6# 生成原始图片信息   
7x, y = np.indices((l, l))   
8
9center1 = (28, 24)   
10center2 = (40, 50)   
11center3 = (77, 58)   
12
13radius1, radius2, radius3 = 16, 14, 15   
14
15circle1 = (x - center1[0]) ** 2 + (y - center1[1]) ** 2 < radius1 ** 2   
16circle2 = (x - center2[0]) ** 2 + (y - center2[1]) ** 2 < radius2 ** 2   
17circle3 = (x - center3[0]) ** 2 + (y - center3[1]) ** 2 < radius3 ** 2   
18
19# 生成包括 3 个圆的图片   
20img = circle1 + circle2 + circle3   
21mask = img.astype(bool)   
22img = img.astype(float)   
23
24img += 1 + 0.2 * np.random.randn(*img.shape)   
25graph = image.img_to_graph(img, mask=mask)   
26graph.data = np.exp(-graph.data / graph.data.std())   
27
28# 聚类输出   
29labels = spectral_clustering(graph, n_clusters=3)   
30label_im = -np.ones(mask.shape)   
31label_im[mask] = labels   
32
33plt.matshow(img)   
34plt.matshow(label_im)   
35
36plt.show()   

以下是运行结果：左边的图形是人为生成的原始图片，右边是识别图形边缘后的处理图片。

#关键参数解析

spectral_clustering 可配置的参数如下，其中最主要的参数是 affinity（数据集）、n_clusters（聚类数）和 assign_labels（聚类方法，可选 kmeans [默认] 或 discretize）：

pythonCopy
1sklearn.cluster.spectral_clustering(affinity, n_clusters=8, n_components=None, eigen_solver=None, random_state=None, n_init=10, eigen_tol=0.0, assign_labels='kmeans')  

#应用场景与适用数据集

谱聚类在实际业务中主要有以下应用场景：

• 图像切割
• 数据聚类

总结：谱聚类适用数据集的特点

1. 不适合聚类类别数特别多的数据。
2. 对于特殊数据集具有比较好的适应性，例如环形数据、非凸数据、交叉数据等非正常或规则下的数据（如下图所示）。