一、换个问法：不问坐标，只问连边

K 均值问的是「你离哪个中心近」。 这个问题在月牙上没法回答——月牙没有中心，它的两端弯向相反方向，任何一点都可以当中心。 谱聚类换一个问法：「你和谁连着」。 在月牙上这个问题很好回答：同一个弯月上的点，沿着弯月走一小段就能连上； 不同弯月之间，得「跨过空隙」才能连——而空隙里没有点。 所以关键的一步是建图：每个点连它最近的 nn 个邻居，边权用高斯核衰减。 这张图把「形状」编码进去了——同一个弯月内部的路径，沿着图能走通； 跨过空隙的路径，图上根本没有边。 这就是为什么谱聚类看得见形状：它根本不用直线距离做判断，用的是图上能不能走过去。 注意建图仍然要用欧氏距离找近邻——但它只用来「连边」，不用来「划分」。 这一字之差，就是能不能处理非凸数据的分水岭。

二、三步流程

第一步：建图。每个点连最近的 nn 个邻居，边权 exp(负距离平方除以 2)。 记得对称化——「i 是 j 的邻居」和「j 是 i 的邻居」不一定同时成立。 第二步：算归一化拉普拉斯，取前 K 个特征向量，把每一行归一化成单位长度。 归一化拉普拉斯是单位阵减去「度矩阵负二分之一次方 乘 边权矩阵 乘 度矩阵负二分之一次方」。 第一个特征值恒为 0（对应常向量），所以真正有用的是第 2 到第 K 加 1 个。 第三步：把每个点的这 K 个特征向量拼成一个 K 维向量，对它做 K 均值。 注意这一步跑的 K 均值是在「特征向量空间」里，不是在原始空间里。 这里几乎不会失败——因为前 K 个特征向量已经把簇分得很开了，K 均值只需要收个尾。 为什么这样就能分对？ 直觉是：图上能被切开的地方，在拉普拉斯的前几个特征向量里会表现出明显的「台阶」。 同一块内部的点，特征向量值几乎一样；跨过切口，值突然跳。 所以把这些值当坐标看，两块自然分成两坨——第三方的 K 均值只是把这两坨标上号。 行归一化那一步不能省。 它的作用是让每个点的「尺度」一致，避免某些度特别大的点把 K 均值带偏。 这一步在原论文里叫 Ng-Jordan-Weiss，是谱聚类最常用的版本。

三、实测：月牙上打满

300 个点、两个交错的月牙。K 均值的 ARI 是 0.3741。 谱聚类换不同的邻居数：

四、多出来的一层信息：谱

这一节比前两节多拿到一样东西：谱本身。 K 均值要先知道 K 才能跑；谱聚类可以先用特征值的「跳」来猜 K。 在月牙上（nn=8），前三个特征值是 0、0.00118、0.00358。 第一个 0 是常向量；第二个 0.00118 明显小于第三个 0.00358，中间有三倍的跳。 这个跳说的是：图可以切成两块，而且切开的代价很小；切成三块就要付三倍的代价。 换成三个高斯团，前四个特征值是 0、0.00197、0.00270、0.02656。 第四个比第三个大了将近十倍——这个跳就对应「三块」。 换句话说，看谱就能数出簇数，不用先猜。 不过这个办法不是万能的：数据本身没有明显分块时，谱是一条平滑下降的曲线，没有跳可看。 更麻烦的是「跳多大才算跳」要靠人判断，所以它只是「多一层信息」，不是「自动给出 K」。 真要自动定 K，还得看 14.4 节那些带惩罚的判据。 但请注意谱聚类在这一点上确实比 K 均值强：K 均值给你的只有一个数（目标函数值）， 而且它对 K 单调；谱给你一整条曲线，形状本身就有信息。

五、代价与边界

谱聚类不是免费的。 三步里最贵的是第二步：对一个 n 乘 n 的矩阵做特征分解，复杂度大约 n 的三次方。 加上建图要算两两距离（n 的平方），整体比 K 均值贵得多。 所以它常见于「n 在几千以内、形状复杂」的场合； n 上十万就不合适了，得改用采样、稀疏特征求解器（比如 Lanczos）这类办法。 第二个代价是它只在有标签时才能评估好坏。 它给出的划分和 K 均值一样，没有「置信度」这种东西。 要判断分得对不对，还是得回到「这个簇在业务上有没有意义」。 第三个边界是：谱聚类假设「簇之间连接少、簇内部连接多」。 如果两份数据的密度差很多（一个稠密小簇紧贴一个稀疏大簇），建图时稠密区的边会远多于稀疏区， 谱就会被稠密区主导。 这时候归一化能缓解一部分，但缓解不了根本。 顺带对照一下核 K 均值在月牙上的表现：

六、动手 Demo：两个月牙：K 均值 0.374，谱聚类 1.000

这段代码在两个月牙上跑三组对比：K 均值、不同邻居数下的谱聚类、以及谱聚类换到球状数据上还灵不灵。 重点看两张表：ARI 从 0.3741 跳到 1.0000； 以及前三个特征值里第二个和第三个之间的那个跳——那是「图能被切成两块」的信号。

import numpy as np

def dmat(A, B):
    return np.sqrt(np.maximum(((A[:, None, :] - B[None, :, :]) ** 2).sum(-1), 0.0))

def moons(n=300, seed=4, noise=0.08):
    rg = np.random.default_rng(seed)
    m = n // 2
    t1 = rg.uniform(0.0, np.pi, m)
    t2 = rg.uniform(0.0, np.pi, m)
    A = np.column_stack([np.cos(t1), np.sin(t1)])
    B = np.column_stack([1.0 - np.cos(t2), 0.5 - np.sin(t2)])
    X = np.vstack([A, B]) + rg.normal(0.0, noise, (2 * m, 2))
    return X, np.r_[np.zeros(m), np.ones(m)]

def d2(A, B):
    return np.maximum(((A[:, None, :] - B[None, :, :]) ** 2).sum(-1), 0.0)

def kmeans(X, K, seed=0, iters=100):
    rg = np.random.default_rng(seed)
    C = X[rg.choice(len(X), K, replace=False)].astype(float)
    for _ in range(iters):
        lab = np.argmin(d2(X, C), axis=1)
        newC = np.array([X[lab == k].mean(0) if (lab == k).any() else C[k]
                         for k in range(K)])
        if np.allclose(newC, C):
            return lab
        C = newC
    return np.argmin(d2(X, C), axis=1)

def graph(X, nn=10, sig=1.0):
    D = dmat(X, X)
    np.fill_diagonal(D, np.inf)
    W = np.zeros((len(X), len(X)))
    for i in range(len(X)):
        idx = np.argsort(D[i])[:nn]
        W[i, idx] = np.exp(-D[i, idx] ** 2 / (2.0 * sig * sig))
    return np.maximum(W, W.T)

def spectral(X, K, nn=10, sig=1.0, seed=0):
    W = graph(X, nn, sig)
    d = W.sum(axis=1)
    dm = 1.0 / np.sqrt(np.maximum(d, 1e-12))
    L = np.eye(len(X)) - (W * dm[:, None]) * dm[None, :]
    val, vec = np.linalg.eigh((L + L.T) / 2.0)
    o = np.argsort(val)
    U = vec[:, o][:, :K]
    U = U / np.maximum(np.sqrt((U ** 2).sum(1))[:, None], 1e-12)
    return kmeans(U, K, seed=seed), val[o]

def ari(a, b):
    ua, ub = np.unique(a), np.unique(b)
    tab = np.zeros((len(ua), len(ub)))
    for i, x in enumerate(ua):
        for j, y in enumerate(ub):
            tab[i, j] = np.sum((a == x) & (b == y))
    c2 = lambda z: z * (z - 1.0) / 2.0
    sij, sa, sb = c2(tab).sum(), c2(tab.sum(1)).sum(), c2(tab.sum(0)).sum()
    exp, mx = sa * sb / c2(float(len(a))), 0.5 * (sa + sb)
    return float((sij - exp) / (mx - exp))

X, y = moons(300, 4)
print('K 均值 ARI %.4f' % ari(kmeans(X, 2), y))
for nn in (6, 8, 10, 15, 20):
    lab, val = spectral(X, 2, nn=nn)
    print('nn=%d ARI %.4f 特征值 %.5f %.5f %.5f'
          % (nn, ari(lab, y), val[0], val[1], val[2]))

实跑输出：

--------------------------------------------------------------------
两个月牙：K 均值 ARI 0.374，谱聚类 1.000
--------------------------------------------------------------------
  数据                     300 个二维点，两个交错的月牙
  任务                     分成两簇

  K 均值                   ARI 0.3741
  **两个月牙交错在一起，任何一条直线都会同时切到两个月牙。**
  **K 均值只能画直线（准确说是直线的正交分割面），所以它注定失败。**

  谱聚类的做法分三步：建邻接图、算归一化拉普拉斯的前 K 个特征向量、再对它们做 K 均值。
  **关键在于第三步之前：图上的「距离」是沿着弯月走的，不是直线——这才是它看得见形状的原因。**
  邻居数 nn      ARI    特征值1   特征值2   特征值3
  ------------------------------------------------
          6   1.0000    0.00000   0.00000   0.00176
          8   0.9734    0.00000   0.00118   0.00358
         10   0.9867    0.00000   0.00145   0.00448
         15   0.9734    0.00000   0.00238   0.00723
         20   0.8336   -0.00000   0.00424   0.01124
  **邻居数从 6 到 15，ARI 都在 0.97 以上；nn=6 直接打满，nn=8 是 0.9734，nn=20 掉到 0.8336。**
  **注意前三个特征值：第一个是 0（常向量），第二个 0.00118 和第三个 0.00358 之间有一个明显的跳。**
  **这个跳就是「图能被切成两块」的信号：前 K 个特征值都很小，第 K+1 个突然变大。**
  **所以谱聚类其实是先看谱，再决定 K，而不是先定 K 再分——这比 K 均值多了一层信息。**

  但别以为它只对非凸数据好。换回三个高斯团：
  三团上的谱聚类           ARI 0.9850
  三团上的 K 均值          ARI 0.9850
  前四个特征值             0.00000  0.00197  0.00270  0.02656
  **凸数据上两者几乎打平，谱聚类没有明显优势，也没有明显劣势。**
  **它多花的是：建图 O(n²)、特征分解 O(n³)。n 大了这笔账很贵。**

  顺便对照一下核 K 均值在月牙上的表现：
  核 K 均值 h=0.3          中位 0.297 最大 0.693
  核 K 均值 h=0.5          中位 0.586 最大 0.586
  核 K 均值 h=1.0          中位 0.404 最大 0.461
  **同一个核思想，核 K 均值明显不如谱聚类。差别在目标函数。**
  **核 K 均值在核空间里还是「找中心、拉距离」，容易卡在局部解；谱聚类解的是一个松弛过的全局特征值问题，跳出了「找中心」这个框。**
  **这也是这一章最该带走的一句：方法之间的差别，往往不在用了什么核、什么距离，而在「把问题化成什么形式去解」。**

第一行 0.3741：K 均值在月牙上也不算完全瞎猜， 它至少把「上半个」和「下半个」大致分对了——但月牙是交错弯的，所以错得很多。 谱聚类那一列从 1.0000 到 0.8336，中间四个都在 0.97 以上。 这个稳定性值得注意：核 K 均值要卡带宽卡到 1.0 到 1.4 才行， 谱聚类邻居数从 6 到 15 随便取都行。 特征值那三列是这一节多出来的信息。 第一个恒为 0，第二个和第三个之间的差距随着 nn 增大而缩小。 nn=6 时第二个特征值是 0.00000（几乎为零）， 说明图几乎断成两块——这正是「两个弯月之间没有边」的量化表现。 所以谱不只是一个中间产物，它可以拿来判断「这个图能不能干净地切开」。 第二个特征值越接近 0，切口越干净。 注意 nn=20 时 ARI 掉到 0.8336，同时第二个特征值涨到 0.00424（比 nn=6 大得多）。 这两个现象是同一件事的两面：邻居太多，图上出现了跨月牙的边，图变得「切不开」， 谱聚类就开始出错。

30 秒实验

1. 把 moons 的 noise 从 0.08 改成 0.25，两个月牙会糊在一起。 谱聚类的 ARI 会掉，而且最优邻居数会变小——噪点让「近邻」变得不可靠。
2. 把 spectral 里的行归一化那一步（U / sqrt(...)）删掉，用未归一化的特征向量。 月牙上可能还凑合，换到密度不均的数据上会明显变差。想清楚这一步在防什么。
3. 把 moons 换成 circles（同心圆），再跑一遍。 谱聚类在同心圆上也应该能打满——因为它同样只看连通性。 这比核 K 均值那个「带宽必须卡准」宽容得多。

常见误区

1. 「谱聚类就是核 K 均值换了个核」。 两者都用到「相似度」，但解的问题完全不同：核 K 均值是反复硬分配、容易卡局部解； 谱聚类是一次特征分解、解的是松弛后的全局问题。 实测月牙上核 K 均值最好 0.693，谱聚类 1.0000。
2. 「谱聚类不需要调参数」。 它有两个：邻居数 nn 和边权的带宽。 只是它比核 K 均值宽容（6 到 15 都行），不是「不用调」。 nn 太大会让图连通过渡、切口消失，实测 nn=20 就掉到 0.8336。
3. 「特征值第一个是 0 所以要扔掉，取前 K 个」。 正确的是取第 2 到第 K 加 1 个。 第一个对应常向量，所有点数值相同，没有任何区分力。这和 13.5 节拉普拉斯特征映射是同一个坑。
4. 「谱聚类能自动决定簇数」。 谱里确实有「跳」这个信号，但「跳多大才算跳」要靠人判断。 数据没有明显分块时，谱是一条平滑下降的曲线，没有跳可看。

前三节都在解决「怎么分」，但有一件事一直悬着：K 到底取几。没有标签的时候， 凭什么说三个比四个好？下一节专门处理这个问题，并且会看到：判据再精细，也救不了选错的模型。

• ☐ （本节完，下一节 14.4 14.4）

相关笔记

• K 均值聚类
• 核 K 均值聚类
• 拉普拉斯特征映射
• 🤖 图解机器学习 · 索引