王 千， 王 成， 冯振元，叶金凤

（1.69026部队 新疆 乌鲁木齐 830002；2.西安交通大学 航天航空学院，陕西 西安 710049；3.中国建设银行 苏州常熟支行，江苏 常熟 215500）

K-means聚类算法是由Steinhaus 1955年、Lloyd 1957年、Ball&Hall 1965年、McQueen 1967年分别在各自的不同的科学研究领域独立的提出。K-means聚类算法被提出来后，在不同的学科领域被广泛研究和应用，并发展出大量不同的改进算法。虽然K-means聚类算法被提出已经超过50年了，但目前仍然是应用最广泛的划分聚类算法之一[1]。容易实施、简单、高效、成功的应用案例和经验是其仍然流行的主要原因。

文中总结评述了K-means聚类算法的研究现状，指出K-means聚类算法是一个NP难优化问题，无法获得全局最优。介绍了K-means聚类算法的目标函数、算法流程，并列举了一个实例，指出了数据子集的数目K、初始聚类中心选取、相似性度量和距离矩阵为K-means聚类算法的3个基本参数。总结了K-means聚类算法存在的问题及其改进算法，指出了K-means聚类的进一步研究方向。

1 经典K-means 聚类算法简介

1.1 K-Means聚类算法的目标函数

对于给定的一个包含 n个d维数据点的数据集X={x1，x2，…，xi，…，xn}，其中 xi∈Rd，以及要生成的数据子集的数目K，K-Means聚类算法将数据对象组织为K个划分C={ck，i=1，2，…K}。每个划分代表一个类ck，每个类ck有一个类别中心μi。选取欧氏距离作为相似性和距离判断准则，计算该类内各点到聚类中心μi的距离平方和

显然，根据最小二乘法和拉格朗日原理，聚类中心μk应该取为类别ck类各数据点的平均值。

K-means聚类算法从一个初始的K类别划分开始，然后将各数据点指派到各个类别中，以减小总的距离平方和。……