谱聚类

谱聚类通过聆听一张图的低频来在数据中找出分组。先构造一张相似项相连的图，再用它拉普拉斯矩阵的少数几个特征向量，把每个项放到一条线上或低维空间里，使分得开的组变得易见也易于切分。

方法是：构造相似度图及其拉普拉斯矩阵 L，计算最小的若干个特征值对应的特征向量（跳过平凡的全一向量），把它们列堆叠起来，将每个节点嵌入为一个短向量，然后对这些向量跑普通的 k-means。最小的特征向量是最平滑的标号，即沿边变化最小者，故尊重图的自然接缝。

其奏效之由是拉普拉斯矩阵的二次型 x^T L x = 对所有边求和 (x_i - x_j)^2。在正交约束下最小化它，是 NP 难的平衡最小割问题的松弛；特征向量是连续解，对它们取整即可还原近最优的割。第二个特征向量，即费德勒向量，给出第一次的二分划分。

为何重要：谱聚类能捕捉原始空间里普通 k-means 无法处理的非凸、缠绕的形状，并适用于任何你能转化为相似度图的数据。警示：结果高度依赖你如何构造图（相似度核及其尺度），而对极大的图，若无稀疏或近似方法，特征分解代价高昂。