K-Means聚类是一种向量量化方法，最初源自信号处理领域，它将一组观测数据划分为k个簇，其中每个观测数据归属于具有最近均值（即簇中心）的簇。这导致数据空间被划分为Voronoi单元。该算法广泛应用于Machine learning中的客户细分、图像压缩和模式识别等任务，并且是Artificial intelligence和数据分析中的基础技术。
K-means的目标是最小化簇内平方和（WCSS），即每个数据点与其簇中心之间欧氏距离的平方和。这等价于最小化同一簇内数据点之间的成对平方偏差。然而，k-means最小化的是欧氏距离的平方，而非普通欧氏距离；后者需要解决更困难的Weber问题。对于欧氏距离最小化，k-medians或k-medoids等替代方法更为合适。
寻找最优k-means聚类在计算上是困难的（NP难问题），但高效的启发式算法能够快速收敛到局部最优解。最常用的方法是Lloyd算法，它迭代执行以下两步：将每个数据点分配给最近的簇中心，然后更新簇中心为其所分配数据点的均值。这种迭代细化过程类似于高斯混合模型所用的期望最大化算法，但k-means倾向于找到空间范围相当的簇，而高斯混合模型则允许不同形状的簇。
标准k-means算法从一组初始簇中心开始，这些中心可以随机选择，或使用k-means++等方法以改善收敛性。算法重复两个步骤直至收敛：分配步骤，即将每个观测数据分配给最近的簇中心；更新步骤，即重新计算每个簇中心为其所有数据点的均值。当分配不再变化或WCSS改进低于阈值时，通常认为算法已收敛。
存在多种变体，包括用于大数据集的mini-batch k-means和用于文本数据的球形k-means。k值的选择通常通过肘部法则、轮廓系数或间隙统计量来确定。算法的时间复杂度约为O(nkd*i)，其中n是观测数据数量，d是维度，i是迭代次数。
K-means是一种无监督算法，意味着它不需要标注数据。它与k近邻分类器（一种监督技术）有松散的联系。将k-means得到的簇中心应用于1-最近邻分类器，可以将新数据分类到现有簇中；这被称为最近质心分类器或Rocchio算法。这种联系凸显了无监督聚类如何支持监督任务。
K-means也与高斯混合模型相关。两者都使用簇中心来建模数据，但高斯混合模型允许簇具有不同的形状和大小，而k-means假设簇是球形的且方差相似。因此，k-means更简单、更快，但灵活性较低。
K-means广泛应用于众多领域。在Amazon Web Services和Google Cloud中，它是分析用户行为和优化资源分配的常用工具。在Computer vision中，它用于图像分割和颜色量化。在市场营销中，它根据购买模式对客户进行细分。该算法也是更复杂方法（如Deep learning特征提取和Generative AI数据预处理）的构建模块。
然而，k-means也有局限性。它需要预先指定簇的数量k，而这并不总是已知的。它对初始簇中心的选择敏感，尽管k-means++可以缓解这一问题。它假设簇是凸形的且各向同性，这在实际数据中可能不成立。离群点会扭曲簇中心，且算法可能收敛到局部最优解。尽管存在这些问题，其简单性和效率使其成为流行的选择。
K-means算法由Hugo Steinhaus于1956年首次提出，Stuart Lloyd于1957年在贝尔实验室对其进行了改进（但直到1982年才发表）。"k-means"这一名称由James MacQueen于1967年创造。此后，人们开发了许多改进方法，包括用于更好初始化的k-means++和用于可扩展性的mini-batch变体。该算法至今仍是Machine learning课程中的核心内容，并在scikit-learn和TensorFlow等主要库中得以实现。