谱聚类

一、直观理解：先把数据织成一张“相似图”，再在图上切分

有些簇在欧氏空间里不是球，甚至缠绕成月牙：K-means 会失败。谱聚类先构建样本相似图（近邻连边、权重大表示像），再把图切割问题松弛成拉普拉斯矩阵的特征向量子空间，最后在这个新坐标里用 K-means 切开。

像社交网络：不按地理坐标分群，而按“谁和谁联系紧密”分社群。特征向量提供了一种让连通团块变得线性可分的嵌入。

二、适用场景与优缺点

类型	说明
适用场景	非凸簇；流形结构；有自然的相似图；中等 $n$。
核心优点	能分离复杂形状；理论与图割、随机游走联系深；核/相似可定制。
局限与缺点	相似图与尺度参数敏感；特征分解 $O(n^3)$ 量级（大图需近似）；$K$ 仍要选；噪声图边难设。

三、核心原理

1. 相似矩阵 $W$

例如 RBF：$W_{ij}=\exp(-\|x_i-x_j\|^2/(2\sigma^2))$，或 $k$ 近邻二值/热核权重；通常 $W_{ii}=0$。

2. 拉普拉斯

度 $D_{ii}=\sum_j W_{ij}$。

• 非规范化：$L=D-W$
• 规范化（常用）：$L_{\mathrm{sym}}=I-D^{-1/2}WD^{-1/2}$ 或随机游走 $L_{\mathrm{rw}}=I-D^{-1}W$

3. 特征嵌入

取 $L$ 最小的 $K$ 个特征向量构成 $n\times K$ 矩阵 $U$，有时按行归一化，再对行向量做 K-means。

图割目标（RatioCut / Ncut）的谱松弛正对应这些特征向量。

四、关键决策

决策点	建议
构图	$k$NN 图常比全连接稳；$\sigma$ 用中位数距离启发式
规范化	优先尝试规范化拉普拉斯
$K$	特征值间隙（eigengap）+ 轮廓
规模	$n$ 大用 Nyström/landmark 近似
标准化特征	构图前建议

五、MATLAB 示例

% 两个月牙（演示非凸）
rng(4);
n = 60;
t = linspace(0, pi, n)';
X1 = [cos(t), sin(t)] + 0.05*randn(n,2);
X2 = [1-cos(t), 1-sin(t)-0.5] + 0.05*randn(n,2);
X = [X1; X2];
Xz = zscore(X);

K = 2;
% 工具箱谱聚类
idx = spectralcluster(Xz, K, ...
    "Distance", "euclidean", ...
    "SimilarityGraph", "knn", ...
    "NumNeighbors", 8, ...
    "LaplacianNormalization", "symmetric");

figure; gscatter(X(:,1), X(:,2), idx);
title("谱聚类：月牙数据");

% 对比 K-means
idxKM = kmeans(Xz, K, "Replicates", 10);
figure; gscatter(X(:,1), X(:,2), idxKM);
title("K-means 对照（常失败）");

% 手写规范化谱聚类骨架
function idx = mySpectral(X, K, knn)
    n = size(X,1);
    Dists = pdist2(X, X);
    W = zeros(n);
    for i = 1:n
        [~, ord] = sort(Dists(i,:));
        nn = ord(2:knn+1);
        W(i, nn) = exp(-Dists(i,nn).^2 / (2*median(Dists(:))^2));
    end
    W = max(W, W');  % 对称化
    d = sum(W, 2);
    DinvHalf = diag(1./sqrt(d+eps));
    Lsym = eye(n) - DinvHalf * W * DinvHalf;
    [V, E] = eig(Lsym);
    [~, ii] = sort(diag(E), "ascend");
    U = V(:, ii(1:K));
    % 行归一
    U = U ./ (sqrt(sum(U.^2, 2)) + eps);
    idx = kmeans(U, K, "Replicates", 10);
end

idx2 = mySpectral(Xz, 2, 8);
figure; gscatter(X(:,1), X(:,2), idx2);
title("手写谱聚类");

六、如何解释结果

1. 相似图参数：邻居数/核宽如何选；
2. 特征值间隙：第 $K$ 与 $K+1$ 之间是否有跳；
3. 嵌入散点：前 2–3 个特征向量空间中是否可分；
4. 与密度方法对照：复杂形状是否一致；
5. 报告：构图方式、拉普拉斯类型、$K$、图示。

七、常见误区

1. $\sigma$ 拍脑袋

过大图几乎全连，过小图破碎。

2. 把谱聚类当黑箱 PCA

嵌入来自图拉普拉斯，不是协方差主成分。

3. $n$ 很大仍稠密特征分解

需稀疏 $k$NN + 迭代特征求解。

4. 忽略对称化与孤立点

度的为 0 会导致数值问题。

5. 以为一定优于 K-means

球状易分数据上 K-means 更简单稳定。

附：建模论文中的写法要点

1. 问题对应：用一两句话说明为何该方法匹配题目数据结构与目标（分类/分群/排序/效率）。
2. 符号与步骤：按“输入 → 预处理 → 核心计算 → 输出指标”列出编号步骤，公式与代码变量名一致。
3. 参数表：列出全部可调参数、取值、选取依据（CV、信息准则、业务约束或灵敏度）。
4. 结果呈现：主结果用表格；辅以 1–2 张图（边界、树状图、得分条形图、效率分解等）。
5. 稳健性：至少做一种扰动——删点、换权重、换距离、换初值或换阈值，观察结论是否保持。
6. 局限：主动写明假设（球状簇、线性可分、CRS、完全补偿等）及适用边界，避免被质询时被动。

若主方法结论与合理基线（如 K-means 对 GMM、加权和对 TOPSIS、CCR 对 BCC）严重冲突，应回到数据质量与指标方向检查，而不是只报告“更好看”的一种结果。

八、小结

谱聚类把聚类转化为图的最优切割，并用拉普拉斯特征向量完成松弛与嵌入，擅长非凸与流形结构。

关键在构图与 $K$；参数稳健性要在论文中用多组邻居数/核宽验证。