k均值聚类算法是原型聚类（prototype-based clustering）和划分聚类算法（Partitional Algorithms）中最常见的算法。k均值算法的目标是最小化聚类所得簇划分的平方差：
E=\sum_{i=1}^{k}\sum_{x\in C_{i}}^{ } \left \| x-\mu _{i} \right \| _{2}^{2}
其中x是给定样本集中的样本，（\mu）i 是聚类簇Ci的均值向量，直观的说 k 均值算法就是使得每一个聚类簇中的数据样本和其所在簇样本均值相似度最高。
经典的 k 均值算法可以描述为以下几步：
- 从样本集中随机选择k个样本作为初始的样本均值；
- 对于其他的每一个样本数据，计算其与各个样本均值的距离，并将其划分入与其最近均值所在的簇；
- 对于每一个簇，重新计算样本均值
- 重复2和3，直到所有的样本均值都不再更新
作为最常见的聚类算法，k 均值算法有很多变异算法，他们中的一些算法试图通过选择更好的初始样本均值从而更容易收敛例如 k-medoids。另外一些变异算法允许簇于簇的合并与分裂，合并的通常依据是两个簇样本均值之间的距离：若两个样本均值之间的距离小于预设的阀值，则将两个聚类簇合并；而当单个聚类簇的平方差大于某一个阀值的时候，则将它分裂为两个不同的簇，这类算法代表是ISODATA。
ISODATA通过动态的分裂和聚类簇从而预估较为合适的K值。
上图是 K-means 算法的演示：a表示输入数据；b中花圈表示最初选择的三个代表样本均值的样本点，并且对所有样本点进行划分；c-e表示多次迭代的过程：样本均值（圆圈位置）和数据划分（不同颜色）的状态。
【描述来源：周志华. (2016). 机器学习: = Machine learning.清华大学出版社.】
【描述来源：Jain, A. K., Murty, M. N., & Flynn, P. J. (1999). Data clustering: a review. *ACM computing surveys (CSUR)*, *31*(3), 264-323.描述来源URL：http://eprints.library.iisc.ernet.in/273/1/p264-jain.pdf .】
【描述来源：Xu, R., & Wunsch, D. (2005). Survey of clustering algorithms. IEEE Transactions on neural networks, 16(3), 645-678.描述来源URL：http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.334.9507&rep=rep1&type=pdf .】
【描述来源：Jain, A. K. (2010). Data clustering: 50 years beyond K-means. Pattern recognition letters, 31(8), 651-666.描述来源URL：https://pdfs.semanticscholar.org/a80c/3c251bd9253dd70b9370bc05259468475a03.pdf .】
发展历史
K-means 算法最初在1955年由提出，被众多不同的科学邻域所发现。尽管他已经被提出超过60年，之后又有上千种聚类算法被提出，但时至今日，K-means 仍然是最受欢迎和最简单的划分聚类算法之一而被广泛使用。K-means 算法的两个最著名变异算法分别是由斯坦福大学的 Ball 和 Hall 在1965年提出的 ISODATA 算法和以生物学家 Forgy 命名的 FORGY 算法。在传统的 K-means 算法中，一个样本只会被划分入一个聚类簇，而在另一个变异算法模糊c均值聚类最初由 Dunn 在1973年提出并被Bezdek 在1981年优化, 这个算法允许一个样本数据可以被划分到多个簇中。Steinbach 等人在2000年提出了一种基于层次划分 K-means 算法，称作 bisecting K-means。这个算法在每一步都把都把数据划分开称两个簇。Pelleg 和 Moore 在1999年提出了一种针对全部样本数据识别最短距离的簇中心的算法，而这也是 K-means 算法中的关键一步。Bradley 等人在1998年提出了一种快速可伸缩单通的 K-means 算法，不需要一次性把所有的数据全部放入到内存。X-means 也是由 Pelleg 和 Moore 在2000年提出的基于 Akaike Information Criterion (AIC) 或者 Bayesian Information Criterion (BIC) 自动优化从而来寻找K值。Kaufman 和 Rousseeuw 提出的 K-medoid 算法中使用样本的中位数所替代样本均值。Kernel K-means 是 Scholkopf 等人在1998提出的算法通过选择合适的相似度核函数可以来处理不同形状的簇。
主要事件
| 年份 | 事件 | 相关论文 |
| 1955 | K-means 算法的雏形由Steinhaus被提出 | Steinhaus, H. (1956). Sur la division des corps matériels en parties. Bull.acad.polon.sci.cl.iii, 801-804. |
| 1965 | Ball 和 Hall 提出的 ISODATA 算法 | Ball, G. H., & Hall, D. J. (1965). ISODATA, a novel method of data analysis and pattern classification. Stanford research inst Menlo Park CA. |
| 1965 | Forgy 提出 FORGY 算法 | Forgy, E. W. (1965). Cluster analysis of multivariate data : efficiency versus interpretability of classifications. Biometrics, 21(3), 41-52. |
| 1973 | Dunn 提出模糊c均值聚类算法 | Dunn, J. C. (1973). A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters. |
| 1981 | Bezdek 优化模糊c均值聚类算法 | Bezdek, J. C. (2013). Pattern recognition with fuzzy objective function algorithms. Springer Science & Business Media. |
| 1987 | Kaufman 和Rousseeuw 提出 K-medoid 算法 | Kaufman, L., & Rousseeuw, P. J. (2005). Finding groups in data: an introduction to cluster analysis. |
| 1998 | Scholkopf 等人 提出 Kernel K-means 算法 | Schölkopf, B., Smola, A., & Müller, K. R. (1998). Nonlinear component analysis as a kernel eigenvalue problem. Neural computation, 10(5), 1299-1319. |
| 1998 | Bradley 等人提出快速可伸缩单通的 K-means 算法 | Bradley, P. S., Fayyad, U. M., & Reina, C. (1998, August). Scaling Clustering Algorithms to Large Databases. In KDD(pp. 9-15). |
| 1999 | Pelleg 和 Moore 提出了针对全部样本数据识别最短距离的簇中心的算法 | Pelleg, D., & Moore, A. (1999, August). Accelerating exact k-means algorithms with geometric reasoning. In Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 277-281). ACM. |
| 2000 | Pelleg 和 Moore 提出 X-means 算法 | Pelleg, D., & Moore, A. W. (2000, June). X-means: Extending K-means with Efficient Estimation of the Number of Clusters. In ICML (Vol. 1, pp. 727-734). |
| 2000 | Steinbach 等人提出 bisecting K-means 算法 | Steinbach, M., Karypis, G., & Kumar, V. (2000, August). A comparison of document clustering techniques. In KDD workshop on text mining (Vol. 400, No. 1, pp. 525-526). |
发展分析
瓶颈
K值的选取一直以来是 K-means 算法的一个重要的研究问题，因为不同的 K 值可能会导致不同的收敛结果。寻找全局最小化平方差函数的解是一个NP难问题，所以作为一种贪婪算法 K-means 只能收敛到一个局部最小值。同时基于欧式距离的 K-means 算法的复杂度依旧很高。最后，K-means 算法对噪声和异常点较为敏感，即使一个噪声样本数据距离任意簇的样本均值都很远，K-means 依旧会把他归入到一个相对较近的簇中，从而导致该簇整体数据的发生偏差从而导致最终聚类质量的下降。
未来发展方向
在未来，K-means 甚至聚类算法可能更多的用于对于没有固定结构的数据，比如图像，文字，声音，视频或者维度不统一的异质数据等等。同时采用多个 K 值的 K-means 算法的集成学习算法也是未来的研究方向之一。
Contributor: Chao Yang