K 均值聚类是什么？反复调整中心点，把数据分成 K 组

K 均值聚类（K-means Clustering）是最经典、使用最广泛的聚类算法。它的目标是把数据分成事先指定的 K 个组，也就是 K 个簇，让每个样本都属于离它最近的那个簇中心，同时让同一个簇内的样本尽可能紧密地聚在一起。这一方法的思想由 Stuart Lloyd 在 1957 年提出，“K-means”这个名称则由 James MacQueen 在 1967 年命名。

算法的步骤

K 均值聚类的过程非常直观，只有两个步骤反复进行。准备：先确定要分成几个簇，也就是 K 的值，然后随机地选择 K 个点作为初始的簇中心。第一步，分配：对每一个样本，计算它到 K 个簇中心的距离，通常是欧氏距离，把它分配给离它最近的那个簇中心。这样，所有的样本就被分成了 K 组。第二步，更新：对每一个簇，计算这个簇中所有样本的平均位置，把它作为这个簇新的中心。名字中的“均值”就来源于此。然后回到第一步，用新的中心重新分配样本，再更新中心……如此反复，直到簇中心几乎不再移动，或者样本的分配不再变化，算法就结束了。

可以想象这样一个场景：在一座城市里要开设 K 家快递网点，希望每个居民去最近的网点取件时走的路尽量短。先随便选 K 个位置开设网点，每个居民去最近的网点；然后把每个网点搬到它所服务的所有居民的中心位置；居民们再重新选择最近的网点，网点再搬家……反复几次之后，网点的位置就稳定下来了。

它优化的是什么

K 均值聚类实际上是在最小化所有样本到它所属簇中心的距离平方之和，这叫簇内平方误差。每一次分配和更新都会让这个值减小或保持不变，所以算法一定会收敛。但它收敛到的可能只是一个局部最优解，而不一定是全局最优的分组。

优点和缺点

K 均值聚类的优点是原理简单、容易实现，计算速度快，能处理大规模的数据。它的缺点也很明显：需要事先指定簇的数量 K，而在很多实际问题中，我们并不知道数据应该分成几类，常用“肘部法”或轮廓系数来帮助选择；结果对初始中心的选择很敏感，不同的初始中心可能得到不同的结果；它倾向于发现大小相近、大致呈圆球状的簇，对于形状不规则的簇，比如环形、月牙形，效果很差；它对异常值比较敏感，因为平均值容易被极端的值拉偏；而且需要先对数据进行标准化，否则取值范围大的特征会主导距离的计算。

改进的方法

k-means++：由 David Arthur 和 Sergei Vassilvitskii 在 2007 年提出，它改进了初始中心的选择方式，让初始的中心彼此尽量分散，从而得到更好、更稳定的结果，如今是大多数工具库的默认初始化方法。小批量 K 均值：每次只用一小批样本来更新中心，适合处理海量的数据。K 中心点算法：用簇中实际存在的某个样本作为中心，而不是平均值，对异常值更加稳健。此外，在需要处理复杂形状的簇时，可以选择 DBSCAN、谱聚类等其他的聚类方法。

应用

K 均值聚类被广泛用于客户细分、图像压缩（把图片中成千上万种颜色聚成少数几种代表色）、文档聚类、异常检测，以及作为其他算法的预处理步骤。在向量数据库中，它也常被用来对大量的向量进行分组，以加快相似向量的检索。