k-均值问题的理论与算法综述

• 作者: 张冬梅 李敏 徐大川 张真宁
• 来源期刊: 中国科学（数学）
• 关键词: k-均值 近似算法 线性规划
• 年，卷（期）: 2020,（9）
• 所属期刊栏目: 论文
• 页码范围: 1387-1404
• 页数: 18页
• 语种: 中文
• DOI: 10.1360/SSM-2019-0280

摘要

k-均值问题是理论计算机科学和组合优化领域的经典问题之一.相应的Lloyd算法是数据挖掘的十大经典算法之一,在各种领域被广泛研究和应用,特别是在图像处理和特征工程方面.随着数据多样性和数据量的爆炸性增长,在实际应用中遇到的k-均值聚类问题更加复杂多样,产生了各种亟需解决的具有挑战性的研究课题.k-均值问题在理论上是NP-难的.本文介绍经典k-均值问题及其变形的基于局部搜索、线性规划舍入、原始对偶、对偶拟合和Lagrange松弛等技术的有效算法.首先介绍经典k-均值问题的近似算法、加倍度量空间中的有效多项式时间近似方案及满足稳定性实例的多项式可解性,然后介绍k-均值问题的若干重要变形,包括k-中位、球面k-均值、鲁棒k-均值、带约束的k-均值和隐私保护k-均值等问题,最后列出k-均值领域中的若干公开问题.