两条弯曲带在原空间难分，谱聚类怎样用图拉普拉斯把它们展开？

上一篇的层次聚类用 linkage 保存了多粒度合并树，但它仍直接在原特征空间比较距离。对同心圆、两条月牙或社区网络，“离中心近”没有意义，少数跨簇近邻还可能让 single linkage 链化。

谱聚类（Spectral Clustering）先把样本变成相似图，再寻找图上内部连接强、跨组连接弱的切分。它的关键不是最后调用 K 均值，而是中间的相似矩阵、图拉普拉斯（Graph Laplacian）与特征向量嵌入。

01 为什么换成图，弯曲结构会更容易？#

在原二维平面，两条月牙的质心可能接近；但若只连接局部邻居，每条月牙内部有连续路径，两条月牙之间只有很弱或没有边：

原空间                         相似图

   ●—●—●                          ●━━●━━●
 ●       ●                       ┃     ┃
          ○—○          ->        ●     ●     弱边  ···
        ○     ○                   ···
                                      ○━━○━━○

坐标看起来缠绕                   强连接留在各自子图

text

图的节点是样本，边权 $w_{ij}\ge 0$ 表示相似度。谱聚类希望切断的总边权很小，同时避免把一个孤立点当作“完美小簇”。

02 从数据到标签经历哪些张量？#

设 $X\in\mathbb R^{N\times D}$ ，目标簇数为 $K$ ：

X [N,D]
  │ RBF 或 k 近邻图
  ▼
W [N,N]  相似矩阵，Wᵢⱼ 越大越相似
  │ 行和
  ├──► degree d [N] ──► D=diag(d) [N,N]
  │
  ▼
L_sym = I - D^(-1/2) W D^(-1/2) [N,N]
  │ 最小 K 个特征向量
  ▼
U [N,K] ──逐行归一化──► Y [N,K]
  │ 在新坐标中聚类
  ▼
labels [N]

text

每个样本 $x_i$ 不再由原来的 $D$ 个特征直接分簇，而由矩阵 $Y$ 的第 $i$ 行——它在图上的低频坐标——表示。

03 相似矩阵不是距离矩阵#

常见的径向基函数（Radial Basis Function，RBF）相似度为：

w_{ij}=\exp(-\gamma\|x_i-x_j\|_2^2)

距离越小， $w_{ij}$ 越接近 1；距离越大，权重越接近 0。gamma 控制衰减速度：过大时图碎成许多近孤立节点，过小时几乎所有点都相似，簇边界消失。

另一种做法是建立 $k$ 近邻图，只保留局部边。它可得到稀疏 $W$ ，但必须决定邻居数与对称化方式： $i$ 把 $j$ 视为邻居，不保证反向也成立；谱分解通常需要对称图，可用并集、交集或对称加权。

04 图拉普拉斯为什么衡量“切边代价”？#

定义每个节点的度：

d_i=\sum_j w_{ij},\qquad D=\operatorname{diag}(d_1,\ldots,d_N)

非归一化图拉普拉斯为：

L=D-W

对任意节点信号 $f\in\mathbb R^N$ ：

f^\top Lf=\frac12\sum_{i,j}w_{ij}(f_i-f_j)^2

若强连接节点取值相近，右侧很小；若在强边两端给出不同值，代价很大。因此最小特征值对应的特征向量，是图上变化最平滑的坐标。常数向量满足 $L\mathbf1=0$ ；若图恰有 $K$ 个互不连通分量，0 特征值的重数就是 $K$ 。

为避免切出低度孤立点，实践常用对称归一化拉普拉斯：

L_{sym}=I-D^{-1/2}WD^{-1/2}

它把节点度纳入尺度，对应归一化切割（Normalized Cut）的连续松弛。

05 用四节点弱桥图手算一次切分#

设两个内部边权为 1 的点对，中间只有权重 0.1 的桥：

节点 0 ━1.0━ 节点 1 ··0.1·· 节点 2 ━1.0━ 节点 3

text

相似矩阵与度为：

W=\begin{bmatrix} 0&1&0&0\\ 1&0&0.1&0\\ 0&0.1&0&1\\ 0&0&1&0 \end{bmatrix},\qquad d=[1,1.1,1.1,1]

取候选分区信号 $f=[1,1,-1,-1]^\top$ 。内部强边两端取值相同，只在弱桥上变化。按无向边计一次：

f^\top Lf=0.1(1-(-1))^2=0.4

若错误地把节点 0 单独分开，强边 $(0,1)$ 被切断，单这一项就是 $1\times(1-(-1))^2=4$ 。因此低能量特征向量自然倾向在弱桥处改变符号。

原节点信号       第二个低频方向（示意）       嵌入后

0—1··2—3         +0.7 +0.6 | -0.6 -0.7       ● ●     ○ ○
                       弱桥处跳变             一条轴即可分开

text

这就是“谱”二字的来源：算法读取拉普拉斯的特征值与特征向量，而不是直接在原坐标画直线。

06 归一化切割如何变成特征向量问题？#

将节点分为 $A$ 与 $\bar A$ ，跨组边权为：

\operatorname{cut}(A,\bar A)=\sum_{i\in A,j\in\bar A}w_{ij}

只最小化 cut 会偏爱孤立单点。归一化切割再除以各组总度：

\operatorname{Ncut}(A,\bar A)= \frac{\operatorname{cut}(A,\bar A)}{\operatorname{vol}(A)}+ \frac{\operatorname{cut}(A,\bar A)}{\operatorname{vol}(\bar A)}

其中 $\operatorname{vol}(A)=\sum_{i\in A}d_i$ 。离散分区求解是困难的组合优化；放松节点只能取两个离散值的约束后，可转化为拉普拉斯特征向量问题。多簇时取 $K$ 个低频方向形成 $U\in\mathbb R^{N\times K}$ ，再把每一行当作新样本聚类。

谱松弛不是原离散目标的魔法精确解。最后从连续嵌入恢复离散标签仍可能受 K 均值初始化、特征值接近和图构造影响。

07 不依赖聚类器，写出最小谱嵌入#

下面从手算图直接构造 $L_{sym}$ ，取两个最小特征向量，再对行归一化。为保持透明，最后按第二个特征向量符号二分：

import numpy as np

W = np.array([
    [0.0, 1.0, 0.0, 0.0],
    [1.0, 0.0, 0.1, 0.0],
    [0.0, 0.1, 0.0, 1.0],
    [0.0, 0.0, 1.0, 0.0],
])                                                  # [N=4,N=4]

degree = W.sum(axis=1)                              # [N]
inv_sqrt = 1.0 / np.sqrt(degree)
L_sym = np.eye(4) - inv_sqrt[:, None] * W * inv_sqrt[None, :]

eigenvalues, eigenvectors = np.linalg.eigh(L_sym)   # 升序；列为特征向量
U = eigenvectors[:, :2]                             # [N,K=2]
Y = U / np.linalg.norm(U, axis=1, keepdims=True)    # [N,K]
labels = (U[:, 1] > 0).astype(int)                  # 仅适合这个二分示例

assert np.allclose(L_sym, L_sym.T)
assert eigenvalues[0] < 1e-12
assert labels[0] == labels[1]
assert labels[2] == labels[3]
assert labels[0] != labels[2]

python

特征向量整体乘以 $-1$ 仍是同一个解，所以标签 0/1 可能交换。一般 $K>2$ 时不要按符号逐列切分，应在归一化后的 $Y$ 中使用 K 均值、离散化或 cluster_qr。

08 用 scikit-learn 1.9 正确落地#

当前官方 SpectralClustering API ↗ 可自行构造 RBF 或近邻 affinity：

import numpy as np
from sklearn.cluster import SpectralClustering
from sklearn.preprocessing import StandardScaler

X_scaled = StandardScaler().fit_transform(X_train)  # [N,D]

model = SpectralClustering(
    n_clusters=2,
    affinity='nearest_neighbors',
    n_neighbors=12,
    n_components=2,
    eigen_solver='arpack',
    eigen_tol='auto',
    assign_labels='cluster_qr',
    random_state=42,
    n_jobs=-1,
)
labels = model.fit_predict(X_scaled)                 # [N]

assert model.affinity_matrix_.shape == (
    X_scaled.shape[0], X_scaled.shape[0]
)
assert model.labels_.shape == (X_scaled.shape[0],)

python

assign_labels='cluster_qr' 直接从特征向量提取簇，不需要 K 均值迭代；'kmeans' 则使用 n_init 和随机初始化。若用 RBF：

rbf_model = SpectralClustering(
    n_clusters=2,
    affinity='rbf',
    gamma=3.0,
    assign_labels='kmeans',
    n_init=20,
    random_state=42,
).fit(X_scaled)

python

gamma 对 nearest_neighbors、precomputed 和 precomputed_nearest_neighbors 会被忽略。n_jobs 主要用于近邻图构造，不会让所有特征分解自动线性扩展。

09 使用业务图时怎样传入预计算 affinity？#

当边来自网页链接、交易关系或图像邻接，而不是特征欧氏距离，可直接传对称非负矩阵：

from scipy import sparse
from sklearn.cluster import SpectralClustering

# row、col、weight 描述无向边；同时放入两个方向
rows = np.array([0, 1, 1, 2, 2, 3])
cols = np.array([1, 0, 2, 1, 3, 2])
weights = np.array([1.0, 1.0, 0.1, 0.1, 1.0, 1.0])
W_sparse = sparse.csr_matrix((weights, (rows, cols)), shape=(4, 4))

labels = SpectralClustering(
    n_clusters=2,
    affinity='precomputed',
    assign_labels='cluster_qr',
    random_state=42,
).fit_predict(W_sparse)

python

传入前至少断言 W.shape == (N,N)、非负、近似对称，并检查零度节点。负权相似度需要专门的 signed graph 方法，不能假设当前实现会替你验证并修复。

10 怎样选择图、K 与求解器？#

图构造通常比最后的标签器更关键：

RBF 图：画距离分位数与权重分布；避免几乎全 0 或几乎全 1。
kNN 图：检查连通分量、节点度分布和互为近邻比例；在相邻 n_neighbors 上比较稳定性。
簇数 $K$ ：查看最小特征值序列中的 eigengap 只能提供候选，还要结合稳定性、簇大小和领域需求。
arpack：默认常用；大而稀疏的问题可评估 lobpcg。amg 需要额外安装 pyamg，官方也提示可能不稳定。
eigen_tol='auto'：让求解器选择容差；对 lobpcg/amg 强行设小于 $10^{-5}$ 的容差可能导致收敛问题。

若图实际有很多连通分量，却只要求两个簇，特征空间会退化且答案不唯一。先检查图，再调最后的 assign_labels。

11 为什么它也没有自然的新样本预测？#

谱坐标来自当前整张图的特征分解。加入一个新样本会增加一行一列并改变全局特征向量，所以 scikit-learn 的 SpectralClustering 提供训练标签，没有原生 predict(X_new)；它是传导式学习（Transductive Learning）方法。

需要外推时可选择：

冻结训练图，用 Nyström 延拓近似新点的谱坐标；
在训练谱嵌入与标签上训练一个监督分类器；
定期重建图与重聚类，并处理簇身份匹配；
若持续在线预测是核心需求，改用有显式映射的表示学习或聚类方法。

每种方案都改变了原算法语义，必须单独验证训练外样本。

12 复杂度、失败场景与最短调试路径#

稠密 $W$ 占 $O(N^2)$ 内存，完整特征分解更昂贵；谱聚类通常适合中等样本量、较少簇。排查顺序应沿数据流：

尺度错误：检查标准化与距离样本，确认相似图表达了真正关系。
图过稀：连通分量暴增、零度节点出现；增加邻居或修正数据覆盖。
图过密：权重近似常数，边界被抹平；减小邻居数或增大 RBF gamma。
误传距离矩阵：打印近点和远点的矩阵值，确认近点值更大。
标签随机变化：先区分编号置换，再固定 random_state、增大 n_init 或使用 cluster_qr。
特征值扎堆：不存在清晰 eigengap，簇可能不稳定；做重采样和图参数扰动。
内存爆炸：使用稀疏近邻图与稀疏求解器，先估计边数；不要无意识创建稠密 RBF 矩阵。
把簇当真类别：图由人为相似度定义，结果只能说明“按这张图容易切”。

线上或批处理至少记录：图边数、连通分量、度分位数、前若干特征值、eigengap、簇大小、参数扰动稳定性、求解器耗时与峰值内存。

13 与相近方法的边界#

方法	关键表示	非凸结构	主要限制
K 均值	原空间中心	弱	偏好球形；可原生预测
DBSCAN	半径近邻与密度连通	强	单一密度阈值；可标噪声
层次聚类	linkage 合并树	视准则而定	保存多粒度；可能链化
谱聚类	图拉普拉斯低频嵌入	强	需簇数；图与特征分解昂贵、难外推
核 K 均值	核诱导特征空间的中心	强	与谱方法关系紧密，但目标与归一化不同

谱聚类适合“局部相似关系可信、全局中心不可信”的问题；它不是所有非凸数据的默认答案。

14 今天真正需要记住什么？#

谱聚类把样本变成非负相似图，用 $L$ 或 $L_{sym}$ 的低频特征向量寻找强连接内部几乎不变、弱连接处发生变化的坐标，再在谱嵌入中离散化标签。结果依赖相似图、归一化、簇数与数值求解；可靠实践必须检查图连通性、度分布、特征值、稳定性和平方级资源风险，并承认它通常不能直接预测新样本。

15 思考题与小练习#

把弱桥权重从 0.1 改为 0、0.5 和 1，分别计算 $f=[1,1,-1,-1]^\top$ 的 $f^\top Lf$ ，并解释图从两个分量走向均匀链时切分证据怎样变化。
在同心圆数据上扫描 n_neighbors，记录连通分量数、度分位数、前五个特征值与 ARI（仅用于有模拟真值的实验）。找到图碎裂、合理和过密三个区域。
构造同一数据的距离矩阵与 RBF 相似矩阵，分别传给 affinity='precomputed'。错误输入产生什么警告或异常结果？写断言在训练前阻止它。

16 下一篇预告#

谱嵌入已经把“图上的邻近关系”转成新坐标，但它主要服务于分簇。下一篇将继续无监督表示学习，研究流形学习：如何在不要求离散簇的情况下保留局部邻域，把高维弯曲流形展开为可视化或下游建模坐标。

01 为什么换成图，弯曲结构会更容易？#

02 从数据到标签经历哪些张量？#

03 相似矩阵不是距离矩阵#

04 图拉普拉斯为什么衡量“切边代价”？#

05 用四节点弱桥图手算一次切分#

06 归一化切割如何变成特征向量问题？#

07 不依赖聚类器，写出最小谱嵌入#

08 用 scikit-learn 1.9 正确落地#

09 使用业务图时怎样传入预计算 affinity？#

10 怎样选择图、K 与求解器？#

11 为什么它也没有自然的新样本预测？#

12 复杂度、失败场景与最短调试路径#

13 与相近方法的边界#

14 今天真正需要记住什么？#

15 思考题与小练习#

相关工作#

16 下一篇预告#