用图论切分聚类的谱聚类入门

可视化演示

展示谱聚类四步流程：构建相似度图、拉普拉斯矩阵特征分解、谱嵌入低维空间、K-Means聚类，动态对比原始空间与嵌入空间的聚类效果。

聚类任务背景：K-means 为何切不动月牙

故事从“笨办法”开始。若只按“离哪桌中心最近就坐哪桌”来分，面对两条交错的亲戚阵营（月牙形），座位图怎么画都有一条“误伤线”横穿其中。K-means 就是一把“圆规”：它只会画圆形的势力范围，碰到环形、月牙这类非凸形状就抓瞎。

在机器学习里，K-means 把每个数据点硬性划给最近的质心，相当于在特征空间里画 k 个圆。问题恰恰出在“画圆”这个几何假设上——当簇的形状是月牙、圆环时，任何一个圆都不可能完整包住一族，硬切必然误伤。它的目标函数长这样：

$$\displaystyle J=\sum_{i=1}^{k}\sum_{x\in C_i}\lVert x-\mu_i\rVert^2$$

1. 点与质心：x 是一个数据点（宾客），μi 是第 i 个簇的质心（这桌的虚拟中心），差的范数平方就是“离桌中心有多远”。

$$\lVert x-\mu_i\rVert^2$$

2. 簇内求和：把第 i 个簇里所有点到质心的距离平方相加，衡量这桌排得服不服帖。

$$\sum_{x\in C_i}\lVert x-\mu_i\rVert^2$$

3. 所有簇求和：把 k 桌的“别扭程度”全部累加，K-means 的训练就是在最小化这个总代价。

$$J=\sum_{i=1}^{k}\sum_{x\in C_i}\lVert x-\mu_i\rVert^2$$

所以问题的关键不是“客人不好排”，而是“排桌的依据”选错了。与其在平面上画圆，不如拿起新人给的那张“人际网”，沿着网上的裂缝下刀——这正是谱聚类的出场方式。

图论核心概念：把数据画成关系网

婚礼筹备中，新人偷偷塞给你一张手绘的“人际关系网”：每个宾客是一个点，只要两人有交情就画一条线，交情越深线越粗。这，就是图论视角下的数据。数据点是顶点，点与点之间的相似关系是边，边的粗细就是权重。

所有边权排成一个方阵，叫邻接矩阵 W；每个顶点的“关系总量”叫度 d。有了网，就能定义“下刀的代价”——把宾客分成 A、B 两堆时，所有“一边站一个”的连线权重之和：

$$\displaystyle \mathrm{cut}(A,B)=\sum_{i\in A,\,j\in B} W_{ij}$$

1. 两个阵营：一次切分把顶点分成 A、B 两堆，i 属于 A 堆，j 属于 B 堆。

$$i\in A,\ j\in B$$

2. 跨堆边权累加：凡是交集 A 里的点和集合 B 里的点之间的边，权重全部加总。

$$\sum_{i\in A,\,j\in B}W_{ij}$$

3. 最优切分目标：谱聚类要找的是 cut 尽量小、且两边不太失衡的切法。

$$\min_{A,B}\ \mathrm{cut}(A,B)$$

现在，“排桌”被翻译成一个数学问题：在一张人际网上找到一组“裂缝”，切开后每块内部关系紧密、块与块之间纽带稀薄。剩下的事情，就是怎么高效地找到这条裂缝——答案藏在拉普拉斯矩阵里。

相似度图构建：亲密度怎样量化

问题来了：新人只给了你宾客名单，没说谁跟谁熟。你得自己从“座位距离”推断关系——物理上坐得近的人，大概率聊得来；隔了半个宴会厅，多半是点头之交。机器学习里同样如此：原始数据只有坐标，没有边，第一步就是“根据距离猜测关系”。

最常用的猜测工具是高斯核：距离越近，亲密度越接近 1；距离越远，亲密度断崖式下跌。公式如下：

$$\displaystyle w_{ij}=\exp\left(-\frac{\lVert x_i-x_j\rVert^2}{2\sigma^2}\right)$$

1. 距离平方：x_i 与 x_j 是两个点的坐标向量，差向量的范数平方是欧氏距离的平方。

$$\lVert x_i-x_j\rVert^2$$

2. 尺度参数：分母 2σ² 决定“多远算远”，σ 是亲疏尺子的宽度。

$$2\sigma^2$$

3. 指数衰减：exp 把距离压到 0 到 1 之间，距离越近权重越接近 1。

$$\exp(-t)\in(0,1]$$

除了高斯核，还可以用 K 近邻图（只连最近的 K 个点）或 ε 邻域图（半径内才连）来让网络“稀疏化”。关系图画得准不准，直接决定后面所有步骤——地基歪了，房子必歪。

拉普拉斯矩阵：切图压力账本

关系网画好了，但一眼望去全是线，看不出该从哪里下刀。这时需要一本“压力账本”：把每个人的关系总量记在对角线上，把两两关系记在角落，两下一减，就得到拉普拉斯矩阵 L。记度矩阵 D 为对角阵（第 i 个对角元是顶点 i 的度 d_i），邻接矩阵 W 已知，那么：

$$\displaystyle L=D-W$$

1. 度矩阵 D：对角线上是每个顶点的边权总和，表示这位宾客在网里的“人情总量”。

$$D_{ii}=\sum_{j}W_{ij}$$

2. 减去邻接矩阵：对角线变成“人情总量减自己”（无自环时不变），非对角线变成负边权。

$$L_{ij}=D_{ij}-W_{ij}$$

3. 二次型意义：对任意标签向量 f，fᵀLf 等于所有边上“标签差”的加权平方和，标签突变得越剧烈数值越大。

$$f^{\top}Lf=\tfrac12\sum_{i,j}W_{ij}(f_i-f_j)^2$$

直观理解：如果给每位宾客标一个数（比如 0 或 1 表示阵营），拉普拉斯会狠狠惩罚“好友之间标号不一样”的情况。切图要找的，正是让这种惩罚最小的标号方式——它藏在特征分解里。（归一化版本 L_sym = I − D^{-1/2} W D^{-1/2} 只是把账本按人情量标准化，思路相同，到应用章节再展开。）

特征分解降维：抖开关系网

有了压力账本，怎么读出“裂缝”？想象把人际网拎起来一抖——网会顺着最松散的缝隙自动摊开。拉普拉斯的特征分解，做的就是“找到网最容易裂开的方向”。数学上，解方程 Lv=λv 得到若干“特征对”。

把特征值从小到大排列，最小的那批特征值对应的特征向量，恰好编码了“最便宜”的切图方向。取前 k 个拼成一个矩阵：

$$\displaystyle U=[v_1,v_2,\dots,v_k]\in\mathbb{R}^{n\times k}$$

1. 特征方程：v 是特征向量，λ 是特征值，表示矩阵作用在 v 上等价于把 v 拉伸缩 λ 倍。

$$Lv=\lambda v$$

2. 取最小 k 个：特征值从小到大排，取前 k 小对应的特征向量，数值越小表示切得越省力。

$$\lambda_1\le\lambda_2\le\cdots\le\lambda_k$$

3. 拼成新坐标：矩阵的第 i 行就是第 i 个点的新坐标，维度从原始维度降到 k 维。

$$U_{i:}=[v_1(i),v_2(i),\dots,v_k(i)]$$

特别地，第二个特征向量（λ₂ 对应，叫 Fiedler 向量）就能把一张连通图切成两个自然社区——这正是婚宴“一分为二”的关键。原始空间里纠缠的月牙，在新坐标上彻底分开。

算法五步走：从建图到开席

现在把这场婚宴的完整流程写成操作手册，一共五步，谁都能照着执行。第一步建相似度图 W；第二步算拉普拉斯 L=D−W；第三步特征分解，取前 k 个小特征值对应的特征向量拼成 U；第四步做行归一化，把每位宾客的新坐标长度都拉到 1：

$$\displaystyle Y_{ij}=\frac{U_{ij}}{\sqrt{\sum_{r=1}^{k}U_{ir}^2}}$$

1. 行长度：对第 i 行所有分量平方和再开根号，得到该点新坐标的模长。

$$\sqrt{\sum_{r=1}^{k}U_{ir}^2}$$

2. 逐分量归一：每个分量都除以模长，得到单位向量，只保留方向、抹掉远近。

$$Y_{ij}=\frac{U_{ij}}{\lVert U_{i:}\rVert}$$

3. K 均值收尾：对 Y 的行做普通 K-means 得到簇标签，再映射回原始数据点。

$$\text{labels}=\mathrm{KMeans}(Y)$$

第五步就是在 Y 上跑普通 K-means。整套流程下来，原始空间里奇形怪状的簇，在新坐标里都是一团团“标准圆球”，K-means 终于派上用场——收尾切分，开席！

实战应用场景：图像与社区

婚宴策划师出师了，业务开始扩张：酒店要你把宴会厅的照片切成“舞台区、宾客区、蛋糕区”；粉丝后援会要你把五千名会员按兴趣分成小组。谱聚类在这些场景里大显身手：图像分割中，每个像素是顶点，颜色相近、位置相邻的像素连边，切出来的就是语义区域；社区发现中，每个用户是顶点，关注关系是边，找出来的就是“抱团”的圈子。

真实网络里更容易出现“孤点被单独切开”的问题，于是用归一化割来同时约束“切得省力”和“两边均衡”：

$$\displaystyle \mathrm{Ncut}(A,B)=\mathrm{cut}(A,B)\left(\frac{1}{\mathrm{vol}(A)}+\frac{1}{\mathrm{vol}(B)}\right)$$

1. cut 与 vol：cut 是跨堆边权和，vol 是堆内所有边的权重总和，衡量这桌的“总人脉”。

$$\mathrm{vol}(A)=\sum_{i\in A}d_i$$

2. 倒数相加：两堆人脉越不均衡，两项倒数之和越大，相当于加了一笔“失衡罚金”。

$$\frac{1}{\mathrm{vol}(A)}+\frac{1}{\mathrm{vol}(B)}$$

3. 最小化目标：谱聚类求使 Ncut 最小的分割，它等价于对归一化拉普拉斯做特征分解取前 k 小特征向量。

$$\min_{A,B}\ \mathrm{Ncut}(A,B)$$

凡是“对象之间的关系比坐标更重要”的任务——社交网络、图像像素、蛋白质交互——都可以借用这套“关系网 + 压力账本”的组合拳。这也是谱聚类成为无监督学习常备武器的原因。

局限与调参：翻车现场与对策

但谱聚类不是万能神药，婚宴排桌也可能翻车：宾客上万时，关系账本写到手抖；σ 尺子没选好，要么全场宾客都“似熟非熟”成一锅粥，要么关系网碎成一地孤岛。最大的痛点是计算与存储：邻接矩阵是 n×n 的，n 一大内存就爆炸，特征分解更是 O(n³)。

对策是“稀疏化”——只保留少数重要边，比如 K 近邻图：

$$\displaystyle A_{ij}=\begin{cases}1,& j\in\mathrm{KNN}(i)\ \text{或}\ i\in\mathrm{KNN}(j)\\0,& \text{否则}\end{cases}$$

1. KNN 邻居：对每个点 i，找出特征空间中距离最近的 K 个点，记入集合 KNN(i)。

$$j\in\mathrm{KNN}(i)$$

2. 对称处理：只要 i 是 j 的近邻或 j 是 i 的近邻，都算有边，保证矩阵对称。

$$j\in\mathrm{KNN}(i)\ \text{或}\ i\in\mathrm{KNN}(j)$$

3. 稀疏邻接矩阵：大部分位置是 0，只有邻居位置是 1，内存和计算量大幅下降。

$$A_{ij}\in\{0,1\}$$

其他调参要点：簇数 k 可以看特征值“间隙”（eigengap，相邻特征值差突然变大处往往就是真正的簇数）；σ 用网格搜索或设为距离分布的分位数；数据量巨大时用 Nyström 近似加速。记住一句话：谱聚类成也图，败也图——关系图画得准，它能切出任何形状的月亮；图画得糙，再好的拉普拉斯也救不回来。

AI 应用场景

Python 演示

import numpy as npfrom sklearn.datasets import make_moonsfrom sklearn.cluster import KMeansfrom sklearn.metrics import adjusted_rand_score def spectral_cluster(X, k=2, sigma=0.45):    n = len(X)    # 1. 相似度图(高斯核全连接)    diff = X[:, None, :] - X[None, :, :]    D2 = np.sum(diff ** 2, axis=2)    W = np.exp(-D2 / (2 * sigma ** 2))    np.fill_diagonal(W, 0.0)    # 2. 拉普拉斯矩阵 L = D - W    deg = W.sum(axis=1)    L = np.diag(deg) - W    # 3. 特征分解, 取前 k 小特征值对应的特征向量    vals, vecs = np.linalg.eigh(L)    U = vecs[:, :k]    # 4. 行归一化, 抹平模长差异    U = U / np.linalg.norm(U, axis=1, keepdims=True)    # 5. K 均值收尾    return KMeans(n_clusters=k, n_init=10, random_state=0).fit_predict(U) X, y_true = make_moons(n_samples=240, noise=0.06, random_state=42)y_spec = spectral_cluster(X, k=2, sigma=0.45)y_km = KMeans(n_clusters=2, n_init=10, random_state=0).fit_predict(X)print("谱聚类 ARI:", round(adjusted_rand_score(y_true, y_spec), 3))print("K-means ARI:", round(adjusted_rand_score(y_true, y_km), 3))

1. diff = X[:, None, :] - X[None, :, :]把 240 个点两两配对做差，得到所有点对的距离向量。
2. W = np.exp(-D2 / (2 * sigma ** 2))高斯核：把距离翻译成 0 到 1 的亲密度。
3. np.fill_diagonal(W, 0.0)自己不跟自己连，去掉自环避免干扰。
4. L = np.diag(deg) - W压力账本：度矩阵减邻接矩阵得到拉普拉斯。
5. vals, vecs = np.linalg.eigh(L)对对称矩阵做特征分解，特征值自动升序排列。
6. U = vecs[:, :k]取最小的 k 个特征值对应的特征向量构成新坐标。
7. U = U / np.linalg.norm(U, axis=1, keepdims=True)行归一化，防止长坐标主导 K-means。
8. return KMeans(...).fit_predict(U)在新坐标上做普通 K-means，返回簇标签。

常见误区

面试题