一、为什么 K 均值在同心圆上必败

先把失败的原因说透，因为它决定了后面所有补救的方向。 K 均值给每个点分配簇，靠的是「到哪个中心更近」。两个中心的势力范围分界， 是一条直线（三维里是平面，高维里是超平面）——这是欧氏距离的性质，不是实现细节。 所以 K 均值能画的边界，本质上是一条直线。而同心圆需要的是一个圆。 一条直线穿过圆心，切出来的两半里，每一半都同时含有内圈和外圈的点。 不管你怎么初始化、跑多少次，结果都一样——这不是优化问题，是表达能力问题。 实测 ARI 0.0047。ARI 为 0 意味着「和随机划分一样好」，0.0047 基本就是噪声。 注意这和 14.1 节那种「初始化不好所以掉到 0.432」是两种失败：那个能靠多跑几次救回来， 这个救不回来。 区分这两种失败很重要。 优化失败：目标函数还能更低，只是没找到——多跑、换初始化、换更好的求解器。 表达失败：目标函数的全局最优本身就不对——换模型、换空间、换目标函数。 分不清这两者，就会在一个根本不可能work的模型上反复调参。

二、把「距离」换成核

核 K 均值的推导只有一步：把 K 均值里的「点到中心的距离平方」换成核空间里的版本。 原始空间：||x 减 c_k||²，其中 c_k 是第 k 簇的平均。 核空间：||φ(x) 减 m_k||²，其中 m_k 是第 k 簇在特征空间里的平均。 展开之后，它变成三项：K(x,x) 减去 2 除以簇大小乘以「x 与簇内所有点的核值之和」， 再加上「簇内所有点两两核值之和」除以簇大小的平方。 三项全都只用到核矩阵，一个高维坐标都不用算。 代码上就是三层循环：对每个点、对每个簇，算那两个和。 复杂度是每轮 n²K，比普通 K 均值（每轮 nK）贵 n 倍，但换来的是能弯曲的边界。 这里有一个必须提前说清的取舍：核 K 均值没有「中心」的显式坐标。 普通 K 均值可以打印出三个中心点，核 K 均值打印不出来——中心只存在于那个看不见的特征空间里。 要判断一个新点属于哪簇，只能拿它和所有训练点算核值。 这和第 13.3 节 LPP 有显式投影矩阵、13.4 节核 PCA 没有，是同一类区别。

三、带宽：这一次真的决定生死

核 K 均值只有一个参数：带宽 h。它决定「多远算远」。 每种带宽跑十个种子，再跑一次「十次取最优」：

四、目标函数降低，划分反而更错

这一节最反直觉的一段。 同样取十次最优，换带宽看两个数：核目标函数值，以及真标签本身的核目标函数值。

五、初始化：同一个病，只是更重

h 取 1.0，随机初始化 vs 特征空间里的 ++ 初始化：

六、动手 Demo：同心圆：K 均值 0.005，核 K 均值 1.000

这段代码在同心圆上跑两件事：先看普通 K 均值怎么败，再扫带宽、统计每个带宽的成功率、 并对照「求得的目标值」和「真标签的目标值」。 重点看两张表。第一张的「成功次数」说明单次运行不可靠； 第二张说明带宽太大时，目标函数会主动选择更错的划分。

import numpy as np

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

def circles(n=200, seed=5, r2=3.0):
    rg = np.random.default_rng(seed)
    a1 = rg.uniform(0.0, 2 * np.pi, n)
    a2 = rg.uniform(0.0, 2 * np.pi, n)
    X = np.vstack([np.column_stack([np.cos(a1), np.sin(a1)]),
                   np.column_stack([r2 * np.cos(a2), r2 * np.sin(a2)])])
    return X, np.r_[np.zeros(n), np.ones(n)]

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))

def kgauss(A, B, h):
    return np.exp(-d2(A, B) / (2.0 * h * h))

def kk_val(Km, lab, K):     # 核空间里的簇内平方和
    tot = 0.0
    for k in range(K):
        m = lab == k
        blk = Km[np.ix_(m, m)]
        tot += float(np.diag(blk).sum() - blk.sum() / m.sum())
    return tot

def kk_core(Km, K, lab, iters=60):
    n = len(Km)
    dg = np.diag(Km).copy()
    for _ in range(iters):
        cnt, s, q = np.zeros(K), np.zeros((n, K)), np.zeros(K)
        for k in range(K):
            m = lab == k
            cnt[k] = max(m.sum(), 1)
            s[:, k] = Km[:, m].sum(axis=1)
            q[k] = Km[np.ix_(m, m)].sum() / cnt[k] ** 2
        new = np.argmin(dg[:, None] - 2.0 * s / cnt[None, :] + q[None, :], axis=1)
        if np.array_equal(new, lab):
            break
        lab = new
    return lab

def kernel_kmeans(X, K, h=1.0, seed=0, n_init=1):
    Km = kgauss(X, X, h)
    best, bv = None, None
    for r in range(n_init):
        rg = np.random.default_rng(seed + r)
        lab = kk_core(Km, K, rg.integers(K, size=len(X)))
        v = kk_val(Km, lab, K)
        if bv is None or v < bv:
            best, bv = lab, v
    return best

def plain_kmeans(X, K, seed=0):    rg = np.random.default_rng(seed)    C = X[rg.choice(len(X), K, replace=False)].astype(float)    for _ in range(100):        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):            break        C = newC    return np.argmin(d2(X, C), axis=1)
X, y = circles(200, 5)
print('K 均值 ARI %.4f' % ari(plain_kmeans(X, 2), y))

for h in (0.5, 0.8, 1.0, 1.4, 2.0, 3.0):
    a = [ari(kernel_kmeans(X, 2, h, seed=s), y) for s in range(10)]
    bb = ari(kernel_kmeans(X, 2, h, seed=0, n_init=10), y)
    ok = sum(1 for v in a if v > 0.999)
    print('h=%.1f 单次最小 %.3f 中位 %.3f 最大 %.3f 成功 %d/10 取优 %.3f'
          % (h, min(a), np.median(a), max(a), ok, bb))

for h in (1.0, 2.0, 3.0):
    Km = kgauss(X, X, h)
    lab = kernel_kmeans(X, 2, h, seed=0, n_init=10)
    print('h=%.1f 求得 %.2f 真标签 %.2f ARI %.3f'
          % (h, kk_val(Km, lab, 2), kk_val(Km, y.astype(int), 2), ari(lab, y)))

实跑输出：

--------------------------------------------------------------------
同心圆：K 均值 ARI 0.005，核 K 均值换对带宽就 1.000
--------------------------------------------------------------------
  数据                     400 个二维点：内圈半径 1 共 200 点，外圈半径 3 共 200 点
  任务                     分成两簇，看分得对不对（ARI：1 完全一致，0 等于瞎猜）

  K 均值的结果             ARI 0.0047
  **K 均值在同心圆上必败，而且不是参数没调好——它一定能找到一条直线把平面切成两半。**
  **两半里，每一半都同时含有内圈和外圈的点。ARI 0.005 说的就是「跟瞎猜一样」。**

  核 K 均值换一个空间做同一件事：先算核矩阵，再在核空间里算「点到簇中心」的距离。
  **注意代码里从头到尾没有真的算出任何一个高维坐标，只有 n×n 的核矩阵。**
  带宽 h 从 0.5 扫到 3.0。每种带宽跑 10 个随机种子，再跑一次「十次取最优」：
  带宽 h   单次最小   单次中位   单次最大   成功次数   十次取优
  ------------------------------------------------------------
     0.5     -0.002      0.070      0.175       0/10      0.000
     0.8     -0.002      0.101      1.000       4/10      1.000
     1.0     -0.001      0.526      1.000       5/10      1.000
     1.4     -0.002      1.000      1.000       6/10      1.000
     2.0     -0.002      0.165      0.249       0/10     -0.002
     3.0     -0.002      0.151      0.197       0/10     -0.002
  **先看「成功次数」这一列：没有一种带宽能做到十次全对，最好的 1.4 也只有 6 次。**
  **这就是这一节最该记住的一句：核 K 均值很容易卡在局部最优，所以工程上一定要多跑几次、按核目标取最好。**
  **做这个动作之后，h 在 0.8 到 1.4 之间都能稳定拿到 1.000。**
  两头都救不回来，但原因不一样：
  h 太小（0.5）时核值只在自己身上还算大，核矩阵接近单位阵，
  **这时「簇内平方和」几乎和怎么分无关——一行代码都不报错，跑一百次也没用。**
  h 太大（2.0 以上）时核矩阵被拉平，退回到线性那套，怎么切都切不开。

  这里有一个必须看清楚的现象。同样取十次最优，换带宽看目标值：
  h=1.0 求得 / 真标签      核目标 278.90 / 278.90   ARI 1.000
  h=2.0 求得 / 真标签      核目标 178.28 / 183.45   ARI -0.002
  h=3.0 求得 / 真标签      核目标 105.79 / 126.59   ARI -0.002
  **h 等于 1.0 时，求得的目标值 278.90 和真标签的一模一样——它找到的就是全局最优。**
  **h 等于 3.0 时，求得的目标值比真标签的 126.59 还低，可 ARI 只有 -0.002。**
  **这句话很反直觉但必须接受：目标函数降低了，划分反而更错。**
  **带宽一旦不合适，目标函数衡量的就不是你想要的东西了——它自己变成了一个错误的标准，而且优化得越好，错得越离谱。**

  最后对照一下初始化。h 取 1.0，随机初始化 vs 特征空间里的 ++ 初始化：
  随机 初始化              ARI 最小 0.000 中位 0.400 最大 1.000
  ++ 初始化                ARI 最小 -0.001 中位 0.526 最大 1.000
  **++ 比随机略好，但都好不到哪去——单次运行的正确率只有一半上下。**
  **所以别指望换个聪明的初始化就一劳永逸，真正管用的还是「多跑几次、按目标函数挑最好」这个笨办法。**
  **这也顺便说明了核方法的普遍毛病：核空间里代价地形比原始空间崎岖，局部最优多得多，所以「目标函数最小」这件事本身变得更难做对。**

第一行 0.0047 就是普通 K 均值的判决。 这个数意味着「和随机划分一样好」——不是差，是完全没有信息。 带宽表里最该看的是「成功」那一列：0/10、4/10、5/10、6/10、0/10、0/10。 最强的带宽也只有六成把握，这说明核 K 均值不能「跑一次看结果」，必须多跑几次按目标函数挑。 做完这一步，0.8 到 1.4 都能稳定拿到 1.000。 注意 h=0.5 那一行：单次中位 0.070，取优还是 0.000。 多跑救不回来，因为目标函数本身已经失去区分能力（核矩阵接近单位阵）。 这类失败要认出来，否则会误以为「再多跑几次就好了」。 最后三行是这一节的重头戏：h=1.0 时求得 278.90 与真标签 278.90 完全一致； h=3.0 时求得 105.79，比真标签的 126.59 还低，可 ARI 是负的。 目标函数说「我找到更好的解了」，而真相说「你错得更彻底了」。 所以核方法里「挑带宽」这件事，不能靠看目标函数——它一定会挑那个让它自己变小的值。 得靠外部信息：有标签就用交叉验证，没标签就只能靠对数据尺度的判断。

30 秒实验

1. 把 circles 的 r2 从 3.0 改成 1.5（两圈挨得很近）。 最优带宽会明显变小，而且成功率整体下降——两圈在核空间里也不容易分开了。
2. 把 kernel_kmeans 的 n_init 从 10 改成 1，跑一遍 h=1.0 的十个种子。 看「成功次数」变成多少次，体会「单次运行」为什么不可靠。
3. 把 kk_core 里的 iters 改成 2，只迭代两步。 ARI 会崩。这和 14.1 节「迭代次数要够」是同一件事，只是核空间收敛更慢。

常见误区

1. 「核 K 均值是 K 均值的升级版，效果更好」。它换的是空间，代价是：每轮贵 n 倍、 多一个必须调对的带宽、而且局部最优更多（最强带宽也只有 6/10 次成功）。 数据本来就是球状时，用它纯属浪费。
2. 「目标函数更小说明聚类更好」。 实测 h=3.0 时求得的目标值 105.79 比真标签的 126.59 还低，ARI 却是负的。 带宽错了，目标函数衡量的就不是你想要的东西，优化得越好错得越离谱。
3. 「带宽随便试几个，取最好的」。「最好」按什么算？按目标函数算一定选错（见上一条）。 h 必须和数据尺度对上：这里两环间距是 2，最优在 1.0 到 1.4。换数据就得重新定，不能沿用。
4. 「核 K 均值能给出簇中心，可以拿来解释」。 它没有显式中心——中心只存在于看不见的特征空间里。 能拿到的只有「每个点属于哪簇」。要解释，得回到原始空间算每簇的均值或中位数，那是另一回事。

核 K 均值放宽了「球」的形状，但没放宽「中心」这个东西——它仍然要求每簇有个代表。 下一节把「中心」整个扔掉，只在图上说「谁和谁连着」，于是连月牙这种没有中心的形状也能分。

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

相关笔记

• K 均值聚类
• 谱聚类
• 核函数主成分分析
• 核模型
• 🤖 图解机器学习 · 索引