谱聚类是什么？把数据看成图，再按图的结构来分组

谱聚类（Spectral Clustering）是一种基于图论的聚类方法。它把所有的数据点看作一张图上的节点，把点与点之间的相似程度看作连接它们的边的权重，然后利用图的“谱”，也就是图拉普拉斯矩阵的特征值和特征向量，把数据划分成若干个簇。“谱”这个名字就来源于矩阵的特征值集合。

为什么需要谱聚类

最常用的聚类方法 K 均值，是把每个点分配给离它最近的簇中心。这种方法隐含地假设每个簇都是一个大致呈圆球状的团。但现实中的数据可能具有各种各样的形状，比如两个嵌套在一起的同心圆环，或者两个相互交错的月牙形。对于这样的数据，K 均值会失败：它会把圆环从中间一切两半，而不是把内圈和外圈分开。谱聚类不看点到中心的距离，而是看点与点之间是否“连通”：同一个圆环上的点通过相邻的点一个接一个地连在一起，即使圆环上相对两侧的点距离很远，它们也属于同一个簇。

谱聚类的步骤

第一步，构建相似度图：计算每一对数据点之间的相似度，常用高斯核函数，距离越近相似度越高；也可以只把每个点和它最近的若干个邻居连起来，构成 K 近邻图。第二步，计算图拉普拉斯矩阵：它等于度矩阵减去相似度矩阵，度矩阵是一个对角矩阵，对角线上是每个点与其他所有点的相似度之和。实践中常使用归一化的拉普拉斯矩阵。第三步，计算特征向量：求出拉普拉斯矩阵最小的 k 个特征值所对应的特征向量，k 是想要得到的簇的数量。把这 k 个特征向量排成矩阵，每一行就代表一个数据点在新的低维空间中的坐标。第四步，在新的空间中聚类：在这个低维空间中，原本形状复杂的簇往往变得容易分开，再用 K 均值进行聚类，就得到了最终的结果。

背后的原理：图的切分

谱聚类可以从“图切分”的角度来理解：我们希望把图分成几个部分，使得不同部分之间的连边权重之和尽量小，也就是切断的联系尽量少，同时每一部分又不能太小。直接求解这个问题是非常困难的，但通过一定的数学放松，它可以转化为求拉普拉斯矩阵的特征向量的问题，这就是谱聚类的理论基础。经典的方法包括 Jianbo Shi 和 Jitendra Malik 在 2000 年提出的归一化切分方法，它被用于图像分割；以及 Andrew Ng、Michael Jordan 和 Yair Weiss 在 2001 年提出的算法。Ulrike von Luxburg 在 2007 年发表的谱聚类教程被广泛引用。

优缺点

谱聚类的优点是能够识别任意形状的簇，对数据分布的假设较少，并且有扎实的数学基础。它的缺点是：需要计算所有点之间的相似度并求解特征向量，当数据量很大时，计算和存储的开销都很高；结果对相似度的计算方式和参数，比如高斯核的宽度、近邻的数量，比较敏感；而且仍然需要事先指定簇的数量。它被用于图像分割、社交网络中的社区发现、文本聚类等领域。