K-means 聚类与 k-means++

一句话定义

K-means 把 n 个样本分到 k 个簇，目标是最小化簇内平方和 ∑_j ∑_{x ∈ Cj} ‖ x - μ_j ‖²，用「分配点→更新中心」交替迭代求解，k-means++ 通过概率化的初始中心选择大幅改善解质量。

为什么重要

它是无监督学习的 hello world：目标函数、EM 结构、初始化敏感性、评估难题等无监督核心议题全部在一个算法里出齐；工程上是最常用的用户分群、向量量化、文本粗分工具，也是高维向量检索（ANN 索引）的常用构件。

前置知识

梯度下降与凸优化基础 的迭代优化直觉；欧氏距离与均值。

核心概念

• 簇（cluster）：算法划分出的样本组，无标签语义。
• 质心：簇内样本均值 μ_j。
• WCSS/inertia：簇内平方和，K-means 的优化目标（非凸，只保证局部最优）。
• Lloyd 迭代：固定中心分配样本（E 步）→ 固定分配更新中心（M 步）。
• k-means++ 初始化：第一个中心随机，之后以正比于 D(x)² 的概率选下一个中心，理论期望逼近比 O(log k)。
• 肘部法 / 轮廓系数：选 k 与评估聚类质量的常用启发式。

直观类比

在广场上摆 k 个摊位（质心）：每个人先去离自己最近的摊位（分配），摊主统计客流后把摊位挪到客流中心（更新），反复几轮趋于稳定。摊位初始位置很关键——全挤在一角会导致永远服务不好另一头的居民，这就是初始化敏感与 k-means++ 的意义。

原理与机制

目标 J = ∑_j=1^k∑_{xi ∈ Cj}‖ x_i - μ_j ‖² 对 (C, μ) 联合非凸，但固定一方另一方有解析最优：固定 μ 时最优分配是「最近质心」；固定分配时最优 μ_j 是簇内均值（对平方和求导置零）。两步交替使 J 单调不增，故必收敛到局部最优（分配不再变化的稳定点）。它与 EM 的关系：K-means 是高斯混合（kp-020）在「各向同性、方差趋零、均匀先验」极限下的硬分配 EM——这一视角解释了它的隐含假设：簇是球形、等方差、大小相近。

k-means++ 的选点概率 p(x) ∝ D(x)²（D(x) 为到已有最近中心的距离）使初始中心彼此远离，从根源上避开劣质局部最优；MiniBatchKMeans 用小批量近似两步，把百万级样本的聚类时间降一个量级。

公式与推导

更新步的最优性：固定分配 C_j，min_μj ∑_{x ∈ Cj} ‖ x - μ_j ‖²，梯度 -2∑_{x ∈ Cj}(x - μ_j) = 0 得 μ_j = 1|C_j|∑_{x ∈ Cj} x——均值。单调性：分配步取每个样本的最近质心，等价于对固定 μ 逐点最小化 J；更新步同理，故每步 J 下降，且有下界，迭代收敛。K-means 因此可严格表述为：对隐变量「簇指派」做硬 EM。

图示

 ●●●         ○○○
●●●●  ✚      ○○○○    ✚=质心
 ●● ●   ╱  ╲  ○○
      ╱ ╲   ╲
 ←初始化差：两个质心落入同一群，
   一群被强行劈开、两群被错误合并
 k-means++：初始质心按 D(x)² 散开

实例或案例

用肘部法与轮廓系数选 k 并聚类：

from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_score
import numpy as np

X, _ = make_blobs(n_samples=900, centers=4, cluster_std=1.1, random_state=0)
for k in range(2, 8):
    km = KMeans(n_clusters=k, n_init="auto", random_state=0).fit(X)
    print(f"k={k} inertia={km.inertia_:.0f} 轮廓={silhouette_score(X, km.labels_):.3f}")
km = KMeans(n_clusters=4, n_init="auto", random_state=0).fit(X)
print("各簇规模:", np.bincount(km.labels_))

inertia 拐点与轮廓峰值都指向 k = 4；真实数据上两指标可能不一致，需结合业务可解释性定夺。

常见误区

• 把簇名当真类：聚类只保证「球形分组」，与业务类别可以对不上；簇解释是事后行为。
• 特征尺度不统一直接聚类：欧氏距离被大量纲特征统治，先标准化（对照 kp-027）。
• 对非凸/长条形/密度悬殊的簇用 K-means：目标函数决定它只能切「球形」，此类数据应转 DBSCAN（kp-019）或谱聚类。
• 用 inertia 跨不同 k/不同数据比较质量：inertia 随 k 单调下降、随尺度变化，没有可比性。

与其他知识点的关系

高斯混合模型与 EM 算法 把硬分配软化成 EM 的概率版；DBSCAN 与层次聚类 处理 K-means 搞不定的任意形状与噪声；核技巧与常用核函数 的核 K-means 把相似度升级；交叉验证与数据划分策略 提醒：无监督评估没有「真标签」，不能用有监督那套 CV 直接照搬。

自测题

1. K-means 的两步各在优化什么？为什么收敛？

- 要点：E 步固定质心做最优分配、M 步固定分配取均值；每步 J 单调不增且有下界，分配状态有限故收敛。

1. k-means++ 如何降低坏初始化概率？

- 要点：按正比于到已有中心距离平方的概率选新中心，强制初始质心分散，理论期望解 O(log k) 逼近最优。

1. K-means 隐含了什么簇形状假设？如何从 EM 视角解释？

- 要点：球形、等方差、等先验——它是 GMM 在协方差趋各向同性单位阵、硬分配极限下的特例。

延伸阅读

Lloyd, Least squares quantization in PCM（1982）；Arthur & Vassilvitskii, k-means++（SODA, 2007）。