深入谱聚类的拉普拉斯矩阵原理

可视化演示

展示图结构聚类、拉普拉斯矩阵特征值谱、以及特征向量嵌入空间中的聚类分离效果。

第一步：给路灯接线——图的构建

给小区路灯装电线之前，你得先回答一个问题：哪两盏灯该接一根线？在谱聚类里，这个动作叫“构建相似度图”。每个数据点是路灯，每根电线是两个点的相似关系。接线不能乱接，通常有三条规则：ε-邻域图（距离小于 ε 才接线）、K 近邻图（只连最近的 K 个邻居）、全连接高斯核图（所有灯都接线，但线越细阻抗越大，也就是权重越低）。

最常用的是高斯核：两盏灯离得越近，相似度越接近 1；离得越远，相似度指数衰减到 0。这就好比物业给路灯接线，近的用粗铜线（导电好），远得多的干脆不接。把所有相似度写进一张方方正正的表格，表格第 i 行第 j 列就是第 i 盏灯与第 j 盏灯的“电线的粗细”，这张表叫邻接矩阵 W。

邻居选好了、权重写好了，图的骨架就立起来了。下一节，我们要给每盏灯记录一个简单却重要的数字——它接了几根线。

度矩阵：数一数每盏灯的接线

接线图纸画好后，物业经理要统计每盏灯“接了多少根线、线加起来多粗”。对第 i 盏灯，把邻接矩阵第 i 行的所有元素加起来，得到的就是这盏灯的度。度大的灯是社区里的“交通枢纽”，度小的灯是偏僻角落的孤灯。

把所有灯的度依次放在一个对角矩阵的对角线上，其他位置全是 0，就得到度矩阵 D。它像一个“登记册”，每一页只记录一盏灯自己的接线总量，不掺和别人的事。这个登记册虽然简陋，却是后面构造拉普拉斯矩阵的左膀右臂。

度矩阵记住了每盏灯的重要程度。现在，我们要把这张“登记册”和“接线图纸”合并成一张更深的表——拉普拉斯矩阵。

拉普拉斯矩阵：电路的导电总表

把度矩阵 D 减去邻接矩阵 W，得到的矩阵就是拉普拉斯矩阵 L。它像电路里的“导纳总表”：对角线记录每盏灯的接线总量，非对角线上则记着“两灯之间连线”的负值。这张表有三条奇妙性质：第一，每一行的和都是 0；第二，它是半正定矩阵，所有特征值大于等于 0；第三，全 1 向量一定是它特征值 0 的特征向量。这三条性质让 L 成为图论里的“能量计”——任何一盏灯的亮度如果和邻居差得大，就会在 L 面前现出原形。

为什么 L 能测量“明暗差异”？因为对任意一组亮度 f（每个灯一个亮度值），二次型 $f^T L f$ 恰好等于“所有相邻灯亮度之差的平方和”再除以 2。这个公式是整个谱聚类的灵魂：找一种明暗模式，让所有电线两端的亮度差尽量小，本质上就是在最小化 $f^T L f$。

有了这张“导电总表”，我们还没考虑每盏灯自己的功率。下面要给它做一次“归一化手术”，让它更公平。

归一化拉普拉斯：把灯功率纳入计算

细心的物业经理会发现，只按“接线量”看问题有点不公平：一盏接了 100 根线的小区主灯，和一间只接了 2 根线的角落灯，根本不在一个量级上。为了让每一盏灯在“明暗模式”里享有平等话语权，我们引入归一化拉普拉斯矩阵。

最常用的有两种变体：对称归一化 $L_{\text{sym}} = I - D^{-1/2} W D^{-1/2}$ 和随机游走归一化 $L_{\text{rw}} = I - D^{-1} W$。前者在数学上保持对称美观，方便理论分析；后者对应“从某盏灯出发随机走到邻居”的概率过程，解释起来更直观。两条路殊途同归：它们的特征值谱非常接近，而且都能把“度大的枢纽灯”的数值影响压下来，让算法数值更稳定，对小簇也更敏感。

归一化做好了，接下来真正激动人心的时刻到了——对拉普拉斯矩阵做特征分解，把电路的“固有频率”一条条找出来。

特征分解：找出电路的固有频率

一栋楼的自来水管有它自己的“水锤频率”，一张电路图也有自己的“共振频率”。拉普拉斯矩阵的特征分解，就是把整张图的振动特性拆成一个个独立的“频率模式”：每个模式由一个特征值 λ 和一个特征向量 u 组成。把所有模式按特征值从小到大排列，就得到谱。

特征分解公式 $L = U \Lambda U^T$ 读起来很吓人，其实意思很简单：U 是“所有模式排列成的表”，Λ 是“每个模式对应频率的对角表”，$U^T$ 是“拆解回原先坐标”的逆操作。对谱聚类最关键的信息是：特征值 0 的个数，正好等于图中天然连通的块数。一张完全连成一片的图只有 1 个 0 特征值；若图分成两块互不相连的社区，就有 2 个 0 特征值。

谱揭示了图的“天然块数”，但真正把每个点划分到哪个社区，要看下一步：特征向量本身。

特征向量与分割：最平滑的明暗地图

现在，我们回到路灯明灭实验。物业经理想要一种“明暗模式”，让每根电线两端的亮度差尽量小。最没信息量的模式是所有灯一样亮——这就是全 1 向量，对应特征值 0。去掉这个“全亮”的平凡解后，下一个最平滑的模式就是次小特征向量（第二小特征值对应的特征向量）。

数学上，最小的那个非零“能量/能量”比值由瑞利商刻画：在跟全 1 向量正交的所有向量里，谁让 $f^T L f / f^T f$ 最小，谁就是第二小特征向量。这个向量里的每个分量，可以看作每盏灯在“从左边社区到右边社区”这条主路上的“水平坐标”。符号为正的灯大概在社区的一侧，为负的在另一侧——于是，一个向量就把图切成了两半。想切更多块，就再取第二三四个特征向量，把它们拼成一张低维“地图”，每个数据点在这张地图上有了新坐标，最后用 KMeans 就能轻松圈出社区。

有了最平滑的明暗地图，最后一个小问题：要拿几盏灯的分组信号当坐标？答案藏在特征值谱的“悬崖”上。

特征向量个数：看谱悬崖选数字

小区分成几个社区，有时候一眼看不出。但把特征值从小到大排成一条“山脉”，你会发现一个神奇现象：前几个特征值平缓低矮，某个位置之后突然拔高，形成一道“悬崖”。这道悬崖的位置，就是谱间隙——相邻两个特征值之差最大处。悬崖之前的特征值个数，就是要选的特征向量个数 k。

直觉上讲，前 k 个“低频率模式”对应的是图里大尺度的结构分块，而高频率模式对应的是小区内部的细枝末节。挑 k 就是问：“图的大尺度结构里，有几条明显的分界线？” 用公式说，就是在所有相邻特征值间隙里找最大值。

选好了特征向量的个数 k，谱聚类的最后一步就水到渠成了——把前面所有零件拼成一台完整的机器。

谱聚类流程：从电路图到社区分组

现在把整个“夜间巡逻”流程串起来。谱聚类算法由四个动作组成，每一步都对应我们前面的准备：

1. 构建相似图：算出所有点的高斯相似度，用 K 近邻或 ε-邻域整理成邻接矩阵 W——这是给路灯接线的施工图。

2. 计算拉普拉斯矩阵：根据 W 算出度矩阵 D，再算归一化拉普拉斯矩阵——这是电路的导电总表。

3. 取前 k 个特征向量：对拉普拉斯矩阵做特征分解，取前 k 个（对应最小 k 个特征值）特征向量拼成矩阵 Z，每行是一个点的“新坐标”——这是把每盏灯在明暗地图上的坐标抄下来。

4. KMeans 聚类标注：把 Z 的每一行当作一个数据点，用 KMeans 聚成 k 组，得到最终标签——这是按地图坐标把小区圈成 k 个社区。

这套流程的精妙在于：原始数据可能形状复杂（比如两个交错的月牙），KMeans 直接上手根本分不开；但经过拉普拉斯特征向量这张“地图”的重新投影，原本缠绕的数据被拉成了紧致的小簇，KMeans 一下就能切开。这也是谱聚类被称为“聚类算法之王”的原因。

AI 应用场景

Python 演示

import numpy as npfrom sklearn.cluster import KMeansfrom sklearn.datasets import make_moons  def gaussian_similarity(X, sigma=0.5):    sq = np.sum(X ** 2, axis=1, keepdims=True)    d2 = sq + sq.T - 2 * np.dot(X, X.T)    return np.exp(-d2 / (2 * sigma ** 2))  def knn_graph(W, k=4):    A = np.zeros_like(W)    for i in range(W.shape[0]):        idx = np.argsort(W[i])[-k:]        A[i, idx] = W[i, idx]    return (A + A.T) / 2  def spectral_cluster(X, k=2, sigma=0.5, knn=4):    W = gaussian_similarity(X, sigma)    A = knn_graph(W, knn)    D = np.diag(A.sum(axis=1))    L = D - A    d_inv_sqrt = np.diag(1.0 / np.sqrt(np.maximum(A.sum(axis=1), 1e-10)))    L_sym = np.eye(X.shape[0]) - d_inv_sqrt @ A @ d_inv_sqrt    eigvals, eigvecs = np.linalg.eigh(L_sym)    Z = eigvecs[:, :k]    return KMeans(n_clusters=k, n_init=10).fit_predict(Z)  if __name__ == "__main__":    X, y = make_moons(n_samples=200, noise=0.05, random_state=42)    pred = spectral_cluster(X, k=2)    print("聚类完成，前10个标签:", pred[:10])

1. sq = np.sum(X ** 2, axis=1, keepdims=True)先算每个点的模长平方，为下一步距离矩阵铺路。
2. d2 = sq + sq.T - 2 * np.dot(X, X.T)用平方展开式一次性算出所有点对距离，避免笨重的双重循环。
3. idx = np.argsort(W[i])[-k:]对第 i 行按相似度排序，取最大的 k 个索引作为“最近邻居”。
4. A = (A + A.T) / 2把 K 近邻图强制对称化，保证“你连我、我也连你”，避免有向边破坏矩阵性质。
5. L = D - A构造非归一化拉普拉斯矩阵，这是“导电总表”的起点。
6. d_inv_sqrt @ A @ d_inv_sqrt左乘右乘 $D^{-1/2}$，实现对称归一化，压制高度数节点的主导地位。
7. eigvals, eigvecs = np.linalg.eigh(L_sym)对称矩阵用 eigh 特征分解，输出从小到大排列的特征值。
8. Z = eigvecs[:, :k]截取前 k 个特征向量作为每个样本的新坐标，这就把图“投影”到了低维空间。
9. KMeans(n_clusters=k, n_init=10)最后用经典 KMeans 在新坐标上圈出社区。

常见误区

面试题