k-平均演算法

-均值算法（英文：-means clustering）源于信号处理中的一种向量量化方法，现在则更多地作为一种聚类分析方法流行于数据挖掘领域。-均值聚类的目的是：把${\displaystyle n}$个聚类中，使得每个点都属于离他最近的均值（此即聚类中心）对应的聚类，以之作为聚类的标准。这个问题将归结为一个把数据空间划分为Voronoi cells的问题。

这个问题在计算上是NP困难的，不过存在高效的启发式算法。一般情况下，都使用效率比较高的启发式算法，它们能够快速收敛于一个局部最优解。这些算法通常类似于通过迭代优化方法处理高斯混合分布的最大期望算法（EM算法）。而且，它们都使用聚类中心来为数据建模；然而-均值聚类倾向于在可比较的空间范围内寻找聚类，期望-最大化技术却允许聚类有不同的形状。

-均值聚类与-近邻之间没有任何关系（后者是另一流行的机器学习技术）。

已知观测集${\displaystyle (x_1,x_2,...,x_n)}$-均值聚类要把这${\displaystyle n}$个集合中(k≤n),使得组内平方和（WCSS within-cluster sum of squares）最小。换句话说，它的目标是找到使得下式满足的聚类${\displaystyle S_i}$-均值”于1967年才被詹姆斯·麦昆（James MacQueen） 首次使用。标准算法则是在1957年被史都华·劳埃德（Stuart Lloyd）作为一种脉冲码调制的技术所提出，但直到1982年才被贝尔实验室公开出版 。在1965年，E·W·弗吉（E. W. Forgy）发表了本质上相同的方法，所以这一算法有时被称为劳埃德-弗吉方法。更高效的版本则被J·A·哈蒂根（J. A. Hartigan）和M·A·王（M. A. Wong）提出（1975/1979）。

最常用的算法使用了迭代优化的技术。它被称为-均值算法而广为使用，有时也被称为Lloyd算法（尤其在计算机科学领域）。已知初始的个均值点${\displaystyle m_1^{(t)},...,m_k^{(t)}}$-均值聚类的其他变体，如球体-均值算法和-中心点算法。

通常使用的初始化方法有Forgy和随机划分(Random Partition)方法。Forgy方法随机地从数据集中选择个观测作为初始的均值点；而随机划分方法则随机地为每一观测指定聚类，然后运行“更新(Update)”步骤,即计算随机分配的各聚类的图心，作为初始的均值点。Forgy方法易于使得初始均值点散开，随机划分方法则把均值点都放到靠近数据集中心的地方。参考Hamerly et al的文章，可知随机划分方法一般更适用于-调和均值和模糊-均值算法。对于期望-最大化(EM)算法和标准-均值算法，Forgy方法作为初始化方法的表现会更好一些。

这是一个启发式算法，无法保证收敛到全局最优解，并且聚类的结果会依赖于初始的聚类。又因为算法的运行速度通常很快，所以一般都以不同的起始状态运行多次来得到更好的结果。不过，在最差的情况下，-均值算法会收敛地特别慢：尤其是已经证明了存在这一的点集（甚至在2维空间中），使得-均值算法收敛的时间达到指数级（${\displaystyle 2^{\mathrm{\Omega <!--\; \Omega \; -->}(n)}}$-均值算法的平滑运行时间是多项式时间的。

注：把“分配”步骤视为“期望”步骤，把“更新”步骤视为“最大化步骤”，可以看到，这一算法实际上是广义期望-最大化算法（GEM）的一个变体。

在${\displaystyle d}$-均值聚类问题的最优解的计算复杂度：

相比之下，Lloyds算法的运行时间通常为${\displaystyle O(nkdi)}$和${\displaystyle d}$-均值算法效率很高的两个关键特征同时也被经常被视为它最大的缺陷：

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

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

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

-均值起源于信号处理领域，并且现在也能在这一领域找到应用。例如在计算机图形学中，色彩量化的任务，就是要把一张图像的色彩范围减少到一个固定的数目上来。-均值算法就能很容易地被用来处理这一任务，并得到不错的结果。其它得向量量化的例子有非随机抽样，在这里，为了进一步的分析，使用-均值算法能很容易的从大规模数据集中选出个合适的不同观测。

在聚类分析中，-均值算法被用来将输入数据划分到个部分(聚类)中。然而，纯粹的-均值算法并不是非常灵活，同样地，在使用上有一定局限（不过上面说到的向量量化，确实是一个理想的应用场景）。特别是，当没有额外的限制条件时，参数是很难选择的（正如上面讨论过的一样）。算法的另一个限制就是它不能和任意的距离函数一起使用、不能处理非数值数据。而正是为了满足这些使用条件，许多其他的算法才被发展起来。

在（半）监督学习或无监督学习中，-均值聚类被用来进行特征学习（或字典学习）步骤。基本方法是，首先使用输入数据训练出一个-均值聚类表示，然后把任意的输入数据投射到这一新的特征空间。-均值的这一应用能成功地与自然语言处理和计算机视觉中半监督学习的简单线性分类器结合起来。在对象识别任务中，它能展现出与其他复杂特征学习方法（如自动编码器、受限Boltzmann机等）相当的效果。然而，相比复杂方法，它需要更多的数据来达到相同的效果，因为每个数据点都只贡献了一个特征（而不是多重特征）。

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

基本的Mean Shift聚类要维护一个与输入数据集规模大小相同的数据点集。初始时，这一集合就是输入集的副本。然后对于每一个点，用一定距离范围内的所有点的均值来迭代地替换它。与之对比，-均值把这样的迭代更新限制在（通常比输入数据集小得多的）K个点上，而更新这些点时，则利用了输入集中与之相近的所有点的均值（亦即，在每个点的Voronoi划分内）。还有一种与-均值类似的Mean shift算法，即 似然Mean shift，对于迭代变化的集合，用一定距离内在输入集中所有点的均值来更新集合里的点。Mean Shift聚类与-均值聚类相比，有一个优点就是不用指定聚类数目，因为Mean shift倾向于找到尽可能少的聚类数目。然而，Mean shift会比-均值慢得多，并且同样需要选择一个“宽度”参数。和-均值一样，Mean shift算法有许多变体。

有一些研究表明，-均值的放松形式解（由聚类指示向量表示），可由主成分分析中的主成分给出，并且主成分分析由主方向张成的子空间与聚类图心空间是等价的。不过，主成分分析是-均值聚类的有效放松形式并不是一个新的结果(如，见)，并且还有的研究结果直接揭示了关于“聚类图心子空间是由主成分方向张成的”这一论述的反例。

有研究表明，在稀疏假设以及输入数据经过白化的预处理后，-均值得到的解就是独立成分分析的解。这一结果对于解释-均值在特征学习方面的成功应用很有帮助。

-均值算法隐含地假设输入数据的顺序不影响结果。双向过滤与-均值算法和Mean shift算法类似之处在于它同样维护着一个迭代更新的数据集（亦是被均值更新）。然而，双向过滤限制了均值的计算只包含了在输入数据中顺序相近的点，这使得双向过滤能够被应用在图像去噪等数据点的空间安排是非常重要的问题中。

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