K 均值聚类

是什么

K 均值聚类（k-means clustering）是一种聚类方法，更准确地说是一种矢量量化（vector quantisation）方法：它把 n 个观测分成 k 组，每个观测被划到均值离它最近的那一组^[1]。名字里的 k 就是使用者要给出的组数，算法本身不决定它。因为每个簇只用一个均值来代表，方法需要的只是「距离」和「平均」两件事，最常用的是平方欧氏距离（squared Euclidean distance）^[1]。这样得到的划分，等于把整个空间切成若干维诺图区域（Voronoi cells），而算法想要最小化的量是簇内平方和（within-cluster sum of squares）^[1]。scikit-learn 文档换了一种说法：把样本分成 n 个方差相近的组，同时最小化一个叫 inertia 的指标，而这个指标就是簇内平方和^[2]。

怎么工作

算法在两步之间来回交替^[1]。第一步是分配：按平方欧氏距离，把每个观测送到离它最近的中心点（centroid）。第二步是更新：把每个中心点重新算成当前归属于它的那些观测的均值。这两步反复执行。

举一个具体的小例子。假设平面上有一批点，要分成 3 组：先取 3 个起始中心点，每个点归到离自己最近的那一个；然后每个中心点挪到自己那一组点的平均位置。因为平均位置变了，下一轮可能有些点改换门庭，接着再算均值、再分配，直到各点的归属不再变化。整个过程里用到的只有距离和平均值。

收敛的保证来自目标函数：随着迭代进行，簇内平方和单调下降^[1]。此外，样本量很大时这种方法也能用^[2]。

从哪来

Hugo Steinhaus 在 1956 年提出了这个想法^[1]。Stuart Lloyd 在贝尔实验室（Bell Labs）做出了标准算法，时间是 1957 年，但直到 1982 年才发表，所以这个版本被称为 Lloyd 算法^[1]。James MacQueen 在 1967 年第一次使用了「k-means」这个名称^[1]。

今天用在哪里

scikit-learn 里的 KMeans 是常见实现之一，文档把方法描述为把样本分成方差相近的组并最小化 inertia，同时指出两点：簇的数目必须事先指定，算法能较好地扩展到大量样本^[2]。也就是说，k 要由使用者自己拿主意，换来的好处是数据量变大时仍然跑得动^[2]。

局限

首先是 k。它必须事先选定，选得不合适，结果就差^[1]。其次是起点：结果对初始中心点敏感，常常收敛到局部最优而不是全局最优^[1]——同一批数据，换一组初始中心，可能就得到另一种划分。再次是形状：方法假定簇大致是球形的、大小相近，不适合任意的距离度量，也不适合非数值数据^[1]。针对起点问题，k-means++ 通过让初始中心彼此分散来改进初始化，并带有 O(log k) 的近似保证^[1]。