K-Means 聚类

监督学习有标签——每一份数据都告诉你"答案是什么"。但现实中，绝大多数数据是没有标注的：用户的浏览记录、传感器的时序信号、社交网络中的行为日志。面对一堆没有标签的点，我们能做什么？

聚类（Clustering）的回答是：物以类聚。如果某些数据点在特征空间中彼此靠近，它们很可能属于同一类。我们不需要标签，只需要一个"距离"的概念。

K-Means 是最经典、最直觉的聚类算法。它的核心思想只有一句话：把数据分成 K 组，让每组内的点尽可能靠近它们的中心。

K-Means 的优雅之处在于，它把一个 NP-hard 的联合优化问题，拆成了两个极其简单的交替步骤：

用流程图来直观展示整个迭代过程：

graph TD
  A["随机初始化 K 个中心"] --> B["分配：每个点归入最近中心"]
  B --> C["更新：每个中心取簇内均值"]
  C --> D{"中心是否变化？"}
  D -->|"是"| B
  D -->|"否"| E["输出最终聚类结果"]

  style A fill:#3498db,color:#fff
  style B fill:#e74c3c,color:#fff
  style C fill:#27ae60,color:#fff
  style E fill:#f39c12,color:#fff

形式化地，设第 $t$ 轮迭代时，簇中心为 $\mu_1^{(t)}, \ldots, \mu_K^{(t)}$：

分配步骤：对每个数据点 $x_i$，找到最近的中心：

更新步骤：重新计算每个簇的均值：

其中 $C_j^{(t)} = \{i : c_i^{(t)} = j\}$ 是第 $j$ 个簇的数据点集合。

import numpy as np

def kmeans(X, K, max_iters=100):
    n, d = X.shape

    # 随机初始化：从数据中随机选 K 个点作为初始中心
    idx = np.random.choice(n, K, replace=False)
    centroids = X[idx].copy()

    for _ in range(max_iters):
        # Step 1: 分配 — 每个点归入最近的中心
        # distances[i][j] = ||x_i - mu_j||^2
        distances = np.sum((X[:, None, :] - centroids[None, :, :]) ** 2, axis=2)
        labels = np.argmin(distances, axis=1)

        # Step 2: 更新 — 每个中心取簇内均值
        new_centroids = np.zeros_like(centroids)
        for j in range(K):
            members = X[labels == j]
            if len(members) > 0:
                new_centroids[j] = members.mean(axis=0)
            else:
                new_centroids[j] = centroids[j]  # 空簇保留原中心

        # 收敛判断
        if np.allclose(centroids, new_centroids):
            break
        centroids = new_centroids

    return labels, centroids

K-Means 的收敛性可以从一个优雅的不等式链得出。定义失真函数（Distortion Function）：

也就是所有数据点到其所属簇中心的距离平方和。K-Means 的目标就是最小化 $J$。

每一轮迭代中，两个步骤分别做了什么？

更新步骤为什么能降低 $J$？这是一个经典的结论：对于固定的簇 $C_j$，使得 $\sum_{i \in C_j} \|x_i - \mu\|^2$ 最小的 $\mu$ 恰好就是算术平均值。可以通过对 $\mu$ 求导令其为零直接验证。

由于每步都不增，且 $J$ 有下界（$\geq 0$），所以 $J$ 必然收敛。又因为可能的分配方案只有有限种（$K^n$ 种），所以经过有限步后分配不再变化，算法终止。

既然 K-Means 对初始中心敏感，一个自然的想法是：能不能让初始中心"均匀铺开"，而不是随机扎堆？

K-Means++（Arthur & Vassilvitskii, 2007）用一种贪心策略实现了这一点：

直觉上，这就像撒种子——第一颗随机撒，后续的种子倾向于落在离已有种子最远的地方，确保初始中心"覆盖"整个数据分布。

def kmeans_plus_plus_init(X, K):
    n, d = X.shape
    centroids = np.zeros((K, d))

    # 第一个中心随机选
    centroids[0] = X[np.random.randint(n)]

    for k in range(1, K):
        # 计算每个点到已有中心的最短距离平方
        dists = np.min(
            np.sum((X[:, None, :] - centroids[:k][None, :, :]) ** 2, axis=2),
            axis=1
        )
        # 按距离平方的概率分布采样
        probs = dists / dists.sum()
        centroids[k] = X[np.random.choice(n, p=probs)]

    return centroids

K-Means 有一个无法回避的超参数：簇数 $K$。如何选择合适的 $K$？

from sklearn.metrics import silhouette_score

# 对不同的 K 计算轮廓系数
silhouette_scores = []
K_range = range(2, 11)  # K 至少为 2 才有意义

for K in K_range:
    labels, _ = kmeans(X, K)
    score = silhouette_score(X, labels)
    silhouette_scores.append(score)

# 选择轮廓系数最高的 K
best_K = K_range[np.argmax(silhouette_scores)]

K-Means 的简洁背后隐藏了几个强假设，了解它们才能避免误用：

一个经典的失效案例：两个同心圆环。K-Means 无论如何也无法正确分离它们，因为它只能切出"饼状"的区域。

针对 K-Means 的各种局限，研究者提出了多种变体：

def mini_batch_kmeans(X, K, batch_size=100, max_iters=100):
    n, d = X.shape
    centroids = kmeans_plus_plus_init(X, K)
    counts = np.zeros(K)  # 每个簇累计分配的点数

    for _ in range(max_iters):
        # 随机采样一个小批
        batch_idx = np.random.choice(n, batch_size, replace=False)
        batch = X[batch_idx]

        # 分配：小批内每个点归入最近中心
        dists = np.sum((batch[:, None, :] - centroids[None, :, :]) ** 2, axis=2)
        labels = np.argmin(dists, axis=1)

        # 增量更新中心
        for i, label in enumerate(labels):
            counts[label] += 1
            eta = 1.0 / counts[label]  # 学习率递减
            centroids[label] = (1 - eta) * centroids[label] + eta * batch[i]

    return centroids

K-Means 看起来和概率模型没什么关系，但它实际上是高斯混合模型（GMM）的一个特例，对应 EM 算法的一种极端退化。

在高斯混合模型中，假设数据由 $K$ 个高斯分布混合生成：

EM 算法同样有两步：

当 GMM 的协方差矩阵趋于 $\sigma^2 I$ 且 $\sigma^2 \to 0$ 时，软分配退化为硬分配——每个点以概率 1 属于最近的簇。这就是 K-Means。

graph TD
  GMM["高斯混合模型
(GMM)"] -->|"Σ→σ²I, σ→0"| KM["K-Means
(硬分配)"]
  GMM -->|"一般情况"| EM["EM 算法
(软分配)"]
  KM --> INIT["K-Means++
(智能初始化)"]
  KM --> MB["Mini-Batch
(大规模)"]
  KM --> MED["K-Medoids
(鲁棒)"]
  EM --> FB["Fuzzy C-Means
(模糊聚类)"]
  EM --> VAR["变分推断
(变分 EM)"]

  style GMM fill:#3498db,color:#fff
  style KM fill:#e74c3c,color:#fff
  style EM fill:#27ae60,color:#fff