k-均值是理论计算机科学和组合优化领域的经典问题之一,亦是数据挖掘的十大经典算法之一,在各种领域被广泛研究和应用,特别是在图像处理和特征工程方面。随着数据多样性和数据量的爆炸性增长,k-均值聚类在实际应用中遇到的问题更加复杂多样化,产生了各种亟需解决的具有挑战性的研究课题。k-均值问题可描述为: 给定n个元素的观测集,其中每个观测点都是d维实向量,目标是把这n个观测点划分到k个集合中,使得所有集合中的点到对应的聚类中心的距离的平方和最小,其中一个集合的聚类中心指的是该集合中所有观测点的均值。k-均值问题在理论上是NP-难的。本报告首先介绍经典k-均值问题的近似算法,然后介绍k-均值问题的若干重要变形,包括球面k-均值、鲁棒k-均值和带约束的k-均值等,并总结k-均值中尚待研究的若干问题。