K-平均算法

已知观测集${\displaystyle (x_{1},x_{2},...,x_{n})}$，其中每个观测都是一个${\displaystyle d}$-维实向量，k-平均聚类要把这${\displaystyle n}$个观测划分到k个集合中(k≤n),使得组内平方和（WCSS within-cluster sum of squares）最小。换句话说，它的目标是找到使得下式满足的聚类${\displaystyle S_{i}}$，

${\displaystyle {\underset {\mathbf {S} }{\operatorname {arg\,min} }}\sum _{i=1}^{k}\sum _{\mathbf {x} \in S_{i}}\left\|\mathbf {x} -{\boldsymbol {\mu }}_{i}\right\|^{2}}$

其中${\displaystyle \mu _{i}}$是${\displaystyle S_{i}}$中所有点的均值。

虽然其思想能够追溯到1957年的Hugo Steinhaus [1] ，术语“k-均值”于1967年才被James MacQueen [2] 首次使用。标准算法则是在1957年被Stuart Lloyd作为一种脉冲码调制的技术所提出，但直到1982年才被贝尔实验室公开出版 [3] 。在1965年，E.W.Forgy发表了本质上相同的方法，所以这一算法有时被称为Lloyd-Forgy方法。更高效的版本则被Hartigan and Wong提出（1975/1979） [4][5][6]。

在${\displaystyle d}$维空间中找到k-均值聚类问题的最优解的计算复杂度：

• NP-hard：一般欧式空间中，即使目标聚类数仅为2[12][13]
• NP困难：平面中，不对聚类数目k作限制[14]
• 如果k和${\displaystyle d}$都是固定的，时间复杂度为${\displaystyle O(n^{dk+1}logn)}$,其中${\displaystyle n}$为待聚类的观测点数目[15]

相比之下，Lloyds算法的运行时间通常为${\displaystyle O(nkdi)}$,k和${\displaystyle d}$定义如上，${\displaystyle i}$为直到收敛时的迭代次数。如果数据本身就有一定的聚类结构，那么收敛所需的迭代数目通常是很少的，并且进行少数迭代之后，再进行迭代的话，对于结果的改善效果很小。鉴于上述原因，Lloyds算法在实践中通常被认为几乎是线性复杂度的。

下面有几个关于这一算法复杂度的近期研究：

• Lloyd's k-均值算法具有多项式平滑运行时间。对于落在空间${\displaystyle [0,1]^{d}}$任意的${\displaystyle n}$点集合，如果每一个点都独立地受一个均值为${\displaystyle 0}$，标准差为${\displaystyle \sigma }$的正态分布所影响，那么k-均值算法的期望运行时间上界为${\displaystyle O(n^{34}k^{34}d^{8}log^{4}(n)/\sigma ^{6})}$，即对于${\displaystyle n,k,i,d}$和${\displaystyle 1/\sigma }$都是多项式时间的[11]。
• 在更简单的情况下，有更好的上界。例如[16]，在整数网格${\displaystyle \left\{1,...,M\right\}^{d}}$中，k-均值算法运行时间的上界为${\displaystyle O(dn^{4}M^{2})}$。

使得k-均值算法效率很高的两个关键特征同时也被经常被视为它最大的缺陷：

• 聚类数目k是一个输入参数。选择不恰当的k值可能会导致糟糕的聚类结果。这也是为什么要进行特征检查来决定数据集的聚类数目了。
• 收敛到局部最优解，可能导致“反直观”的错误结果。

k-均值算法的一个重要的局限性即在于它的聚类模型。这一模型的基本思想在于：得到相互分离的球状聚类，在这些聚类中，均值点趋向收敛于聚类中心。 一般会希望得到的聚类大小大致相当，这样把每个观测都分配到离它最近的聚类中心（即均值点）就是比较正确的分配方案。

k-均值聚类的结果也能理解为由均值点生成的Voronoi cells。

k-均值聚类（尤其是使用如Lloyd's算法的启发式方法的聚类）即使是在巨大的数据集上也非常容易部署实施。正因为如此，它在很多领域都得到的成功的应用，如市场划分、机器视觉、 地质统计学[17]、天文学和农业等。它经常作为其他算法的预处理步骤，比如要找到一个初始设置。

k-均值聚类，以及它与EM算法的联系，是高斯混合模型的一个特例。很容易能把k-均值问题一般化为高斯混合模型[19]。另一个k-均值算法的推广则是k-SVD算法，后者把数据点视为“编码本向量”的稀疏线性组合。而k-均值对应于使用单编码本向量的特殊情形（其权重为1）[20]。

目标函数是使得聚类平方误差最小化的算法还有k-中心点算法，该方法保持聚类的中心在一个真实数据点上，亦即使用中心而非图心作为均值点。

• Numerical Example of k-means clustering 页面存档备份，存于
• Application example which uses k-means clustering to reduce the number of colors in images 页面存档备份，存于
• Interactive demo of the k-means-algorithm(Applet) 页面存档备份，存于
• An example of multithreaded application which uses k-means in Java
• k-means application in php
• k-means application in image retrieval
• Another animation of the k-means-algorithm 页面存档备份，存于