谱聚类模拟器

参数设置

数据形状

非凸形状（半月形、同心圆）最能体现谱聚类优势

亲和函数 (Affinity)

如何构建图的边权重 W_ij

簇数 K

样本总数 N

亲和矩阵为 N×N → 内存与 N² 成正比

RBF 尺度 σ

W_ij = exp(-||x_i-x_j||²/(2σ²))

使用特征向量数 k

用最小 k 个特征向量进行低维嵌入

计算结果

—

簇数 K

—

特征向量数 k

—

聚类质量

—

k-means 改进 (%)

—

特征值间隙

—

内存占用 (MB)

—

图亲和视图 — 边与谱色映射

点：数据样本，灰线：k-NN 图边，色：谱聚类分割（与 k-means 不同，能分离非凸形状）。

对比散点图 — 原始数据 / k-means / 谱聚类

特征值谱 — 特征值间隙启发式

理论与主要公式

$$L = D^{-1/2}\,(D - W)\,D^{-1/2},\qquad y_k = \text{特征向量}(L,\,k) \to \text{k-means}$$

W：N×N 亲和矩阵（RBF、k-NN、余弦等），D：对角度矩阵 D_ii=Σ_j W_ij，L：对称正规化图拉普拉斯算子。将 L 的最小 k 个特征值对应的特征向量排列成 N×k 矩阵，按行正规化后用 k-means 聚类（Ng-Jordan-Weiss 2001）。

$$W_{ij}^{\text{RBF}} = \exp\!\left(-\frac{\|x_i-x_j\|^2}{2\sigma^2}\right),\qquad \text{特征值间隙} = \lambda_{K+1} - \lambda_K$$

RBF 亲和由 σ 控制带宽。特征值间隙（eigengap）是判断最优簇数 K 的指标，间隙最大处为谱上的自然分割点。

谱聚类 — 图拉普拉斯算子特征值分解

🙋

我用 k-means 聚类半月形数据时完全失败了…为什么谱聚类就能把它完美分开呢？

🎓

k-means 基于"到簇中心的欧氏距离"，只能创建凸形（大致球形）区域。半月形中，两个弯月的重心其实很近，但弯月的末端彼此很远，k-means 根本搞不定这种形状。谱聚类改变思路，在样本间定义"亲和度（相似性）"构建图。这个图的拉普拉斯算子的特征向量会把图上连通的点映射到低维空间的同一位置。只要两个点能通过相似点的链路相连，不管形状多弯曲，它们都会被识别为同一个簇。

🙋

那亲和度怎么构建呢？左边有 RBF、k-NN、余弦三种选择，我不知道用哪个…

🎓

最常用的是 RBF（高斯）亲和：W_ij = exp(-||x_i-x_j||²/(2σ²))，距离越近值越接近 1，越远越指数衰减到 0。连续平滑但需要仔细调 σ——太大会全部连在一起，太小会全是孤立点。k-NN 图就是"每个点只与 k 个最近邻相连"，简单粗糙但不需调参，适合大规模数据。余弦用于高维方向数据或文本。图像分割用 RBF，社交网络用 k-NN，NLP 用余弦，各有各的场景。

🙋

特征向量真的能看出簇吗？我想象不出来…

🎓

从直观角度说，拉普拉斯的特征值是图上的"振动频率"，特征向量是那种频率下的"振动形态"。如果数据是 K 个完全分离的连通块，L 最小的 K 个特征值都是 0，对应的特征向量在每块内是常数，块间为 0。真实数据虽然不完全分离，但特征向量仍然有这个性质——同簇点在特征向量空间中聚集一起。所以把特征向量当坐标一投，各簇就自动变成球形，k-means 一下就搞定。

🙋

使用的特征向量数 k 必须等于簇数 K 吗？

🎓

通常是的。标准的 Ng-Jordan-Weiss 算法就用最小 K 个特征向量。但实际应用有妙招——看"特征值谱图"，找特征值间隙（相邻两个特征值的最大跳跃），就能客观判断 K 是多少。比如特征值序列是 0.01、0.02、0.03、0.5、0.52…，第 4 个位置跳跃最大，说明 K=3 最合理。本工具右边那个谱图上，默认半月数据应该在 K=2 或 3 看到明显间隙。

🙋

最后，我看这里 N=200 时显示内存 0.3MB，但工程应用数据都成万上百万，不会爆炸吗？

🎓

这是古老的弱点。亲和矩阵 N×N，特征值分解 O(N³)，素朴实现 N=10000 时矩阵就 800MB、计算要几十分钟。有三条路走：(1) 用 k-NN 图让 W 变稀疏，配 Lanczos 等迭代求解器只求部分特征值，复杂度降到 O(N·k·iter)；(2) Nyström 近似用 m 个样本列（m≪N）近似整个矩阵；(3) 随机投影先降低数据维度再算亲和。scikit-learn 的 SpectralClustering 默认用 (1) 的思路，ARPACK 迭代求解，配合 k-NN，能搞定约 10 万规模数据。

常见问题

k-means 和层次聚类基于"簇内样本距离较小"的假设，只能有效分离凸形（大致球形）的簇。对于半月形、同心圆、螺旋形数据，即使距离很近也可能属于不同簇，距离很远也可能属于同一簇。谱聚类将样本间的"亲和矩阵 W"视为图，使用正规化图拉普拉斯算子 L=D^-1/2(D-W)D^-1/2 的最小 k 个特征值和特征向量在低维空间中进行 k-means。因为它在图上"切断连通分量"，所以即使数据形状非凸也能完美分离。

RBF 亲和 W_ij = exp(-||x_i-x_j||²/(2σ²)) 中，σ 决定了聚类质量。σ 过大会强烈连接远点，所有数据压成一团；σ 过小会导致邻域外几乎为零，孤立点增多且 k-means 失败。实际应用中，通常以"邻域点距离中位数"或"k-NN 图中第 k 近邻距离平均值"作为初始 σ，然后调整使特征值间隙（第 k 与第 k+1 特征值之差）最大。本工具在 σ≈0.3 时对半月形数据达到 0.95 的质量得分。

亲和矩阵为 N×N，特征值分解素朴实现为 O(N³)，内存为 O(N²)。N=10000 时约需 800MB，N=100000 时需 80GB，成为瓶颈。回避策略有三：(1) 用 k-最近邻图将 W 稀疏化，配合 Lanczos 等迭代特征值法（O(N·k·iter)）；(2) Nyström 近似用 m 个样本列近似 N×N 矩阵（m≪N）；(3) 随机投影压缩数据维度后再构亲和矩阵。scikit-learn 的 SpectralClustering 默认使用 ARPACK 迭代求解器，结合 k-NN 图可处理约 10 万规模数据。

谱聚类有独特的最优 K 判定法——特征值间隙启发式（eigengap heuristic）。将拉普拉斯算子特征值升序排列，选择 λ_K 与 λ_{K+1} 差值最大的 K。理论上，若数据由 K 个完全分离的连通分量组成，L 有 K 个零特征值，λ_{K+1}>0，形成明显间隙。实际数据因噪声略微连通，间隙温和但仍可见肘形飞跃。这种从特征值谱客观确定 K 的方法，相比需要人工指定簇数的层次聚类是重大优势。

实世界应用

图像分割（Shi-Malik 2000）：这是谱聚类的首次重大突破。将图像像素作为节点，根据颜色、纹理相似度和空间距离定义亲和度，通过最小化 Normalized Cut 能干净地分离物体和背景。Berkeley 分割数据集至今仍以此为标准。最近的做法是结合 CNN 深层特征与谱聚类进行医学图像器官分割和卫星遥感土地利用分类。

社交网络社区检测：SNS 关注关系、学术共著网络、邮件往来网络中，"社区=稠密子图"是关键概念。以邻接矩阵为 W 计算正规化拉普拉斯的特征向量，能自然分离 Twitter 粉丝圈、维基百科话题等。与模块度最大化算法结合使用，效果更佳。

单细胞 RNA-seq 分析：以细胞为节点，基因表达谱的余弦相似度为 W，谱聚类能分离组织内不同细胞类型。Seurat 和 Scanpy 等主流生物信息工具中已是标配，与 UMAP 结合进行细胞图谱绘制。

CAE 有限元网格分割：将网格作为图并行计算时，Fiedler 向量（第二小特征向量）的符号二分割是经典方法，迭代细分大规模并行领域分解。MeTiS 和 Scotch 等库已在 ANSYS、OpenFOAM 等工业求解器中广泛应用。

常见误区与注意事项

最大陷阱是认为"σ 一旦确定就永远适用"。实际上 σ 是聚类质量的关键参数，数据缩放改变时最优 σ 也随之变化。例如归一化到 0–1 的数据用 σ=0.3 最优，但原始值 0–100 时需要 σ=30。这说明前处理（标准化、归一化）会改变 σ 的含义。实务中应以"邻域点距离中位数"初始化 σ，或干脆用 k-NN 图完全绕过 σ 调参。

次大陷阱是"每次都做完整特征值分解"。SpectralClustering 的 eigen_solver='arpack'（默认）只求最小 K 个特征值，用迭代法 O(N·K) 搞定；而 eigen_solver='dense' 用 LAPACK 解所有特征值 O(N³)。N=10000 时前者秒级，后者几十分钟。即便库函数默认改了也要查文档，N=1000 以上务必启用迭代求解器。同时如果用 k-NN 图，要确保 W 保持稀疏矩阵格式，防止被转成稠密矩阵。

最后是忽视聚类结果的稳定性。k-means 最后一步对初始值敏感，需要 n_init=10 多次试验。ARPACK 也依赖随机初始，改变随机种子会有微妙变化。论文和实务报告应该用多个种子测试 Adjusted Rand Index（ARI），证实稳定性 >0.95，否则"特定种子下的漂亮结果"容易被当成最终成果。

谱聚类 — 图拉普拉斯算子特征值分解

常见问题

实世界应用

常见误区与注意事项

使用指南

具体计算例

工程实施要点