K-means聚类是一种向量量化方法，最初源于信号处理，它将n个观测值划分为k个簇，其中每个观测值属于具有最近均值（簇中心或质心）的簇。这导致数据空间被划分为Voronoi单元。该算法广泛用于机器学习中的无监督数据分析，例如客户细分、图像压缩和模式识别。
K-means最小化簇内方差，以平方欧氏距离衡量，而非普通欧氏距离，后者是更困难的Weber问题。均值优化平方误差，而只有几何中位数能最小化欧氏距离。例如，使用k-medians和k-medoids可以找到更好的欧氏解。
该问题在计算上是困难的（NP-hard）；然而，高效的启发式算法能快速收敛到局部最优。这些算法通常类似于高斯混合分布的期望最大化算法，通过k-means和高斯混合建模都采用的迭代细化方法。两者都使用簇中心来建模数据；然而，k-means聚类倾向于找到空间范围相当的簇，而高斯混合模型允许簇具有不同形状。
无监督的k-means算法与k近邻分类器有松散关系，后者是一种流行的监督机器学习分类技术，常因名称而与k-means混淆。将1近邻分类器应用于k-means获得的簇中心，可将新数据分类到现有簇中，这称为最近质心分类器或Rocchio算法。
正式定义
给定一组观测值（x1, x2, ..., xn），其中每个观测值是一个d维实向量，k-means聚类旨在将n个观测值划分为k（≤ n）个集合S = {S1, S2, ..., Sk}，以最小化簇内平方和（WCSS），即方差。形式上，目标是找到：
在S上最小化，对i=1到k求和，对Si中的x求和，||x - μi||^2，
其中μi是Si中点的均值（也称为质心），||·||是通常的L2范数。这等价于最小化同一簇中点对的平方偏差，如以下恒等式所示：到均值的平方距离之和等于平均成对平方距离。
算法
最常见的算法，通常称为Lloyd算法，采用迭代细化方法。它从一组初始的k个质心开始，然后在两个步骤之间交替：分配和更新。在分配步骤中，每个观测值被分配给质心最近的簇，通常使用欧氏距离。在更新步骤中，每个簇的质心被重新计算为分配点的均值。这些步骤重复，直到分配不再变化，表明收敛到局部最优。
初始化至关重要；k-means++方法，它分散初始质心，是一种流行的启发式方法，用于提高最终聚类的质量。该算法对k的选择敏感，使用肘部法或轮廓分析等方法估计合适的簇数。
性质与局限性
K-means假设簇是球形的且大小相似，这限制了其对复杂簇形状数据的适用性。它也对异常值敏感，因为均值受极端值影响。算法收敛到局部最优，不一定是全局最优，不同的初始化可能产生不同结果。尽管有这些局限性，其简单性和可扩展性使其成为大型数据集的热门选择，尤其是在数据增强和预处理流程中。
应用
K-means用于各种领域。在人工智能中，它作为聚类任务的基线。在计算机视觉中，用于图像分割和颜色量化。在市场营销中，帮助根据购买行为细分客户。在自然语言处理中，可以聚类文档或词嵌入。该算法也是更高级技术的基础，例如深度学习特征学习和Generative AI模型。
与其他方法的关系
K-means与高斯混合模型（GMM）相关，因为两者都使用迭代细化和簇中心。然而，GMM允许簇具有不同形状和协方差，而k-means假设各向同性簇。从k-means导出的最近质心分类器是一种简单的监督分类方法。K-means常与k近邻（k-NN）混淆，但它们是不同的：k-means是无监督的，而k-NN是监督的。
历史与发展
K-means的概念最早由Hugo Steinhaus于1956年提出，术语“k-means”由James MacQueen于1967年创造。Lloyd算法发表于1957年，但直到1982年才广为人知，是标准实现。多年来，开发了许多变体，例如用于大规模数据的mini-batch k-means和用于软聚类的模糊c-means。