K均值聚类 · aiwiki.page

K均值聚类是一种聚类分析方法，将数值观测划分为 $k$ 个簇，每个簇以其算术平均值（即质心）作为代表。它无需预先定义的类别标签就能识别数据中的分组，因此广泛用于无监督学习。其目标是最小化各观测值与其所属簇质心之间的距离平方和。这个名称也常用来指求解该优化问题近似解的迭代算法，通常是劳埃德算法。(scikit-learn.org)

数学表述

设 $x_1,\ldots,x_n$ 是实向量空间 $\mathbb{R}^d$ 中的观测值，每个坐标代表一项数值特征。给定整数 $k$ ，目标是找到非空簇 $C_1,\ldots,C_k$ 及其对应的质心 $\mu_1,\ldots,\mu_k$ ，使下式最小：

J=\sum_{j=1}^{k}\sum_{x_i\in C_j} \lVert x_i-\mu_j\rVert_2^2, \qquad \mu_j=\frac{1}{|C_j|}\sum_{x_i\in C_j}x_i.

式中的范数表示欧氏距离。这一损失函数称为簇内平方和，也称惯性。各观测值的簇归属固定时，算术平均值能使每个簇对距离平方和的贡献最小；质心不一定与任何观测点重合。(cs.columbia.edu)

该问题属于数学优化。虽然在簇归属固定时求质心很简单，但同时确定簇归属和质心并不是一个凸优化问题。一般情况下，求全局最优解是 NP 难的，因此实际实现通常采用迭代式启发算法，而不是精确搜索。(cs.columbia.edu)

劳埃德算法

标准流程从 $k$ 个初始质心出发，交替执行两项操作：

**分配：**将每个观测值分配给距离最近的质心。
**更新：**将每个质心替换为分配给它的观测值的均值。

当簇归属不再变化、质心的移动量低于容差，或达到最大迭代次数时，迭代停止。若出现空簇，需要按具体实现的规则处理，例如重新放置该簇的质心。每个常规的分配或更新步骤都不会使目标函数值增大。在距离相等的情况得到一致处理且各簇均非空的条件下，精确执行这一流程会在有限次变化后得到稳定的划分。但这并不意味着该划分是全局最优的。(cs.columbia.edu)

质心固定时，按最近中心分配观测值，会将周围空间划分成一个沃罗诺伊图。任意两个不同中心之间的分界位于超平面上，这解释了为什么标准 K均值算法产生的是凸的判定区域，而不能沿着任意弯曲的簇形状划分。劳埃德的这项工作源于量化研究，并于 1982 年发表。(cs.columbia.edu)

初始化与计算成本

不同的初始质心可能产生不同的最终划分。一种常见策略是使用不同的初始化多次运行算法，并保留惯性最小的结果。固定随机种子可以使某次随机化计算的结果可复现，但不能保证结果最优。(scikit-learn.org)

K均值++由戴维·阿瑟和谢尔盖·瓦西尔维茨基于 2007 年提出，通过让初始中心分散在数据中来改进初始化。首先以均匀随机方式选择第一个中心，随后抽取其他中心，各点被抽中的概率与其到最近已选中心的距离平方成正比。对于原始流程，初始目标函数值的期望值不超过最优值的 $8(\ln k+2)$ 倍；后续的劳埃德迭代不会使其增大。这是期望意义上的近似保证，并不保证每次运行都能找到最佳划分。(theory.stanford.edu)

直接实现的劳埃德算法每次迭代的计算成本约为 $O(nkd)$ ，因此 $T$ 次迭代的总成本为 $O(nkdT)$ 。虽然在实际应用中往往收敛很快，但最坏情况下的迭代次数可能呈超多项式增长。小批量K均值算法处理随机选取的小批量数据，并增量更新中心，从而减少计算量，但代价可能是最终目标函数值更高。(scikit-learn.org)

选择簇的数量

簇数 $k$ 是拟合前指定的超参数。随着 $k$ 增大，全局最优的惯性不会增大，因此仅靠最小化惯性无法确定有用的簇数。肘部图比较不同候选簇数下的惯性，寻找改善幅度开始减小的位置，不过并不一定存在明显的“肘部”。(cs.columbia.edu)

轮廓系数将每个观测值到自身所属簇的平均距离，与其到最近的其他簇的平均距离进行比较。接近 $1$ 的值表示簇之间分离明显，接近 $0$ 的值表示存在重叠，负值则提示该观测值的簇归属可能不合适。轮廓分析评估的是某种特定的几何分离程度；它本身不能证明所选分组代表有意义的类别。(scikit-learn.org)

假设与局限

K均值算法最适合紧凑、近似各向同性且离散程度相近的簇。当簇呈细长形或非凸形、离散程度不均，或大小相差很大时，它可能产生误导性的划分。距离的平方也使目标函数对距离异常远的观测值敏感。每个观测值都会被分配到某个簇：标准 K均值算法没有单独的噪声类别。(scikit-learn.org)

特征缩放很重要，因为数值范围较大的坐标可能主导距离计算。因此，特征工程会改变聚类所依据的几何结构。在高维数据中，距离所提供的信息可能减少；包括主成分分析在内的降维方法可以降低计算量并缓解部分困难，但也会改变被聚类的数据表示。(scikit-learn.org)

应用与相关方法

K均值算法可用于向量量化，即用由有限个质心构成的码本来表示观测值。在图像减色中，按像素的颜色坐标进行聚类，再用所属簇的质心替换每个原始颜色。得到的各个中心构成一个颜色数量更少的调色板。(cs.columbia.edu)

与 K均值算法不同，高斯混合模型能够表示具有不同协方差结构的簇，并以概率形式给出簇归属。其期望最大化算法采用软分配，而普通 K均值算法将每个观测值恰好分配到一个簇。K中心点算法则用实际观测值来代表簇，并能适应更一般的相异度，因此它采用的是不同的目标函数，而不只是 K均值算法的另一种初始化方式。(cs.columbia.edu)