K-means 聚类

1957 年，Bell Labs 的 Stuart Lloyd 开发了一种信号量化算法，用于将连续信号压缩为有限个离散值——他将类似的点"聚合"到同一个"中心"附近。这个方法在 Bell Labs 内部流传了二十多年，直到 1982 年才正式发表。与此同时，James MacQueen 在 1967 年的论文中命名了"k-means"，Hugo Steinhaus 在 1956 年的波兰语论文中也独立描述了相似方法。

如今，K-means 是最广为人知的无监督机器学习算法，也是数据分析工具箱中的标配工具。它的成功有一个悖论：极其简单，却被证明在理论上是 NP-hard 的。

什么是聚类？#

无监督学习（Unsupervised Learning）不提供标签，让算法自己从数据中发现结构；聚类（Clustering）则是把数据点分组，使同一组内的点彼此相似，不同组间的点差异较大。

聚类没有"正确答案"——因为没有标签，无法验证。不同的距离度量、不同的 $k$ 值会给出不同的聚类结果，这些结果都可能在不同的问题框架下"有意义"。

K-means 是基于质心（Centroid-based）的聚类方法，假设每个簇由一个代表点（质心）描述，每个点属于距其质心最近的簇。

算法：Lloyd 迭代#

目标：将 $n$ 个数据点 $x_1, \ldots, x_n \in \mathbb{R}^d$ 分成 $k$ 个簇，使得簇内平方和（Within-Cluster Sum of Squares，WCSS）最小：

$$\text{最小化} \sum_{j=1}^{k} \sum_{x_i \in C_j} \|x_i - \mu_j\|^2$$

其中 $\mu_j$ 是第 $j$ 个簇的质心（均值），$C_j$ 是第 $j$ 个簇的点集。

Lloyd 算法（"标准 K-means"）：

1. 随机初始化 k 个质心 μ₁, ..., μₖ
2. 重复直到收敛：
   a. 分配步骤（Assignment）：每个点分配给最近的质心
      对每个 xᵢ：Cⱼ ← 使 ‖xᵢ - μⱼ‖ 最小的 j
   b. 更新步骤（Update）：重新计算每个簇的质心
      μⱼ ← 簇 Cⱼ 内所有点的均值
```

收敛性：算法为什么必然收敛，拆开两步看就清楚了。

• 分配步不重算质心，只把每个点挪到最近的质心——这一步不会增加任何点的平方距离，WCSS 不增。
• 更新步固定分配、重算质心。均值恰好是"使簇内平方距离之和最小"的点（对 $\sum_i \|x_i - \mu\|^2$ 求导，极小点在 $\mu = \frac{1}{|C|}\sum_i x_i$），所以这一步同样不增 WCSS。

两步交替，WCSS 单调不增又有下界 0，必然收敛。更进一步，$n$ 个点分成 $k$ 簇的分法总数有限（不超过 $k^n$ 种），单调下降意味着不会绕回旧分配，所以算法在有限步内终止。

但为什么只保证局部最优？因为 Lloyd 迭代是一种贪心坐标下降：固定一边优化另一边，每一步都取当下最好的局部动作，没有任何机制让算法"暂时变差"以跳出当前的盆地。从不同的初始质心出发，就像从山的不同侧面往下走，停在哪个山谷完全由起点决定——这就是为什么初始化几乎决定结果的质量。

时间复杂度（每次迭代）：$O(nkd)$——$n$ 个点，各自计算到 $k$ 个质心的 $d$ 维欧氏距离。

初始化的关键：K-means++#

标准 Lloyd 算法的主要缺陷是对初始化极为敏感——不同的随机初始质心可能收敛到差异极大的局部最优解。

K-means++（David Arthur 和 Sergei Vassilvitskii，2007 年提出）：

1. 均匀随机选第一个质心 $\mu_1$
2. 对每个点 $x$，计算其到最近已选质心的距离平方 $D(x)^2$
3. 按概率 $D(x)^2 / \sum D(x_i)^2$ 随机选下一个质心（距离越远被选中概率越大）
4. 重复步骤 2-3 直到选出 $k$ 个质心
5. 用 Lloyd 迭代优化

理论保证：K-means++ 初始化后，Lloyd 算法收敛的期望 WCSS 不超过最优 WCSS 的 $O(\log k)$ 倍。实践上，K-means++ 显著提高结果质量和收敛速度，是现代实现的标准初始化方法（scikit-learn 默认使用 K-means++）。

为什么"散开"就有效？直觉来自随机初始化的典型失败模式：两个初始质心落进同一个真实簇，而另一个真实簇无人问津——Lloyd 迭代没有能力让质心跨越盆地搬家，这个错误会一直保持到最后。K-means++ 用 $D(x)^2$ 加权，让"离所有已选质心都远"的点最可能成为下一个质心，系统性地避开扎堆。$O(\log k)$ 的期望保证意味着：哪怕之后一步 Lloyd 迭代都不跑，光凭初始化就已离最优解不远；而纯随机初始化的误差没有任何上界，运气差时可以任意糟。

即便如此，工程实践还有最后一道保险：多次重启。用不同的随机种子跑若干次完整的"K-means++ 初始化 + Lloyd 迭代"（scikit-learn 默认 10 次），保留 WCSS 最小的一次。因为单次运行陷入差局部最优的概率并不为零，而独立重启让失败概率随次数指数下降——这是用可预期的算力换结果稳定性的标准做法。需要注意，重启之间只能用 WCSS 比较，而 WCSS 随 $k$ 单调下降，所以这种比较只在同一个 $k$ 内有效，不能跨 $k$ 使用。

选择 $k$：肘部法则与轮廓系数#

K-means 需要预先指定 $k$——这是它最大的实践困难之一。

肘部法则（Elbow Method）：对不同的 $k$ 值绘制 WCSS 曲线，寻找曲线下降明显放缓的"肘部"点，对应合理的 $k$。局限是肘部往往不清晰，不同数据集之间差异很大。

轮廓系数（Silhouette Coefficient，Rousseeuw 1987）：衡量每个点与其所在簇的契合程度。对点 $i$，定义：

$$s(i) = \frac{b(i) - a(i)}{\max(a(i), b(i))}$$

• $a(i)$：$i$ 到同簇其他点的平均距离（凝聚度）
• $b(i)$：$i$ 到最近邻簇点的平均距离（分离度）
• $s(i) \in [-1, 1]$，越接近 1 越好

平均轮廓系数最大时对应的 $k$ 通常是较好的选择。

间隙统计量（Gap Statistic，Tibshirani、Walther 与 Hastie，2001）：换一个思路，问"这份数据比'完全没有簇结构'好多少"。在数据的取值范围内生成均匀分布的参照数据（按构造无簇），比较真实数据与参照数据的 $\log \text{WCSS}$ 曲线差距，差距最大的 $k$ 当选。它比肘部法则客观——不依赖目测折角；代价是要对参照数据反复跑聚类，计算量大得多。

贝叶斯信息准则（BIC）和赤池信息准则（AIC）：用信息论方法平衡模型复杂度与拟合质量，适用于高斯混合模型等概率聚类框架。

K-means 的局限#

只能发现凸形簇：K-means 基于欧氏距离，本质上假设每个簇是球形（凸形）。对于"环形"或"月牙形"等非凸形状的簇，K-means 彻底失效。

对噪声和异常值敏感：质心是均值，被极端点显著拉偏。K-medoids（用实际点作为簇代表，而非均值）对异常值更鲁棒。

假设等方差（球形）：若各簇大小或密度差异很大，K-means 效果变差。高斯混合模型（Gaussian Mixture Model，GMM）用 EM 算法，允许椭球形簇，是 K-means 的概率版本推广。

全局 NP-hard：即使在二维平面上，找 $k$ 个簇的全局最优分配也是 NP-hard 的（首个严格证明由 Dasgupta 2008 和 Aloise et al. 2009 独立给出；更早的 Drineas et al. 2004 证明后被发现存在漏洞）。K-means++ 提供近似保证。

距离度量：一个经常被忽略的假设#

K-means 的每一步都内置了一个选择：欧氏距离。这不是中立的决定，它隐含了两条假设。

第一，质心必须是均值。Lloyd 更新步之所以取均值，是因为均值恰好最小化平方欧氏距离之和。换成别的距离，"中心"就不一定是均值——Banerjee 等人（2005）证明，均值性质对一整类Bregman 散度（包括平方欧氏距离、KL 散度等）都成立，因此 K-means 的框架可以原样推广：文本聚类用 KL 散度通常比欧氏距离合理，算法骨架一行不用改。

第二，各方向等权、各簇等方差。欧氏距离把所有维度当作同样重要、同样尺度的坐标轴，后果是对量纲极度敏感：把身高从米改成厘米，它在平方距离里的贡献放大一万倍，聚类结果会被这个特征完全主导。这就是实践中必须先做标准化（Z-score）的原因——但标准化本身也是一个假设：它宣称"每个特征的波动都同样重要"，而这个宣称未必符合业务事实。

归根结底，换距离度量不是换实现细节，而是换"什么叫相似"的定义——而"相似"恰恰是聚类的全部。

变种与替代#

Mini-Batch K-means：每次迭代只用随机抽取的一个小批量（Mini-Batch）而非全部数据更新质心，适合大规模数据集。收敛速度大幅提升，代价是略微降低精度。

DBSCAN（Density-Based Spatial Clustering of Applications with Noise，1996）：不需要指定 $k$，基于密度自动发现任意形状的簇，并将低密度区域的点标记为噪声。对非凸形簇效果极好。

谱聚类（Spectral Clustering）：利用图的 Laplacian 矩阵的特征向量，在低维嵌入中运行 K-means，能发现非凸结构。

层次聚类（Hierarchical Clustering）：自底向上（凝聚型，Agglomerative）或自顶向下（分裂型，Divisive），输出树状图（Dendrogram），不需要预先指定 $k$。

实际应用#

图像压缩（向量量化）：将图像的像素颜色用 $k$ 个代表色替换（Lloyd 的原始应用），可以用 $\log_2 k$ 位而非 24 位表示每个像素颜色。JPEG 的色度子采样用了类似思想。

用户分群（Customer Segmentation）：按购买行为、地理位置等对用户聚类，用于精准营销。

文档聚类：将新闻文章按话题自动聚类（TF-IDF 向量 + K-means），是信息检索和话题模型的基础工具。

基因表达分析：将基因按表达模式聚类，发现功能相关的基因群——20 世纪 90 年代末微阵列技术兴起时，K-means 是标准分析工具。

推荐系统：协同过滤的早期实现用 K-means 对用户行为聚类，对同一簇内的用户进行统一推荐。

跨域连接#

• 统计学：它是高斯混合模型在等方差球形假设下取硬分配的极限，也是交替最小化的一个实例——固定质心求分配、固定分配求质心，目标单调不增因而必然收敛，但只收敛到局部最优。这解释了初始化为何决定成败：算法本身没有跨越盆地的能力，全部依赖起点足够分散。
• 主成分分析：两者共享同一条隐含假设——重要的结构在方差大的方向。后果也是共同的：对量纲极其敏感。把身高从米换成厘米，它在欧氏距离里的权重涨一万倍，聚类结果随之改变。先降维再聚类因此是双刃剑：能压掉噪声方向，也可能抹掉方差小却区分度高的方向，而后者往往正是要找的稀有类别。
• 相变与临界现象：把硬分配换成带温度的软分配、再让温度缓慢下降，簇的数目不是平滑增加，而是在一系列临界温度上分岔出现。这给"该取几个簇"提供了一个物理化判据：在较宽温度区间内稳定存在的划分更可信，一降温就分裂的是过拟合。它同时解释了肘部常常不清晰的原因——分岔点密集时曲线上就没有明显折角。
• 单细胞与人类细胞图谱：把"细胞类型"定义成聚类结果，就把类型数量变成了一个超参数。"发现新细胞类型"很多时候只是把分辨率调高了，而无监督方法没有金标准能判定哪个分辨率是对的。可检验的补救是要求新类型具备独立证据——特有标记基因、空间位置或功能实验，而不是只在某个参数下能被分开。
• 社会分层：把收入、教育、职业等连续指标聚成"阶层"，簇的数量与边界同样由分析者选定。同一份数据取不同的簇数，可以支撑互相冲突的政策叙事，而聚类本身给不出哪个更真。这不是方法缺陷，而是无监督方法的定义性质：它输出的是一种划分方案，不是数据里现成存在的类别。

参考文献#

• Lloyd, S. "Least Squares Quantization in PCM." IEEE Transactions on Information Theory 28(2), 1982. （论文写于 1957 年，发表于 1982 年）
• MacQueen, J. "Some Methods for Classification and Analysis of Multivariate Observations." 5th Berkeley Symposium, 1967.
• Arthur, D. & Vassilvitskii, S. "k-means++: The Advantages of Careful Seeding." SODA, 2007.
• Banerjee, A., Merugu, S., Dhillon, I. S. & Ghosh, J. "Clustering with Bregman Divergences." Journal of Machine Learning Research 6, 1705–1749, 2005.
• Tibshirani, R., Walther, G. & Hastie, T. "Estimating the Number of Clusters in a Data Set via the Gap Statistic." Journal of the Royal Statistical Society: Series B 63(2), 411–423, 2001.

延伸阅读#

• Bishop, C. Pattern Recognition and Machine Learning. Springer, 2006. （第9章 Mixture Models and EM）