Kmea
s聚类算法研究综述
摘要总结评述了Kmea
s聚类算法的研究现状，指出Kmea
s聚类算法是一个NP难优化问题，无法获得全局最优。介绍了Kmea
s聚类算法的目标函数，算法流程，并列举了一个实例，指出了数据子集的数目K，初始聚类中心选取，相似性度量和距离矩阵为Kmea
s聚类算法的3个基本参数。总结了Kmea
s聚类算法存在的问题及其改进算法，指出了Kmea
s聚类的进一步研究方向。关键词：Kmea
s聚类算法；NP难优化问题；数据子集的数目K；初始聚类中心选取；相似性度量和距离矩阵
ReviewofKmea
sclusteri
galgorithm
AbstractKmea
sclusteri
galgorithmisreviewedKmea
sclusteri
galgorithmisaNPhardoptimalproblema
dglobaloptimalresultca
otbereachedThegoal，mai
stepsa
dexampleofKmea
sclusteri
galgorithmarei
troducedKmea
s
algorithmrequiresthreeuserspecifiedparameters
umberofclustersK，clusteri
itializatio
，a
ddista
cemetric
Problemsa
dimproveme
tofKmea
sclusteri
galgorithmaresummarizedthe
Furtherstudydirectio
sofKmea
s
clusteri
galgorithmarepoi
tedatlastKeywordsKmea
sclusteri
galgorithmNPhardoptimalproblem
umberofclustersKclusteri
itializatio
dista
cemetric
Kmea
s聚类算法是由Stei
haus1955年、Lloyed1957
距离判断准则，计算该类内各点到聚类中心i的距离平方
年、BallHall1965年、McQuee
1967年分别在各自的不同的科学研究领域独立的提出。Kmea
s聚类算法被提出来后，在不同的学科领域被广泛研究和应用，并发展出大量不同的改进算法。虽然Kmea
s聚类算法被提出已经超过50年了，但目前仍然是应用最广泛的划分聚类算法之一1。容易实施、简单、高效、成功的应用案例和经验是其仍然流行的主要原因。
文中总结评述了Kmea
s聚类算法的研究现状，指出Kmea
s聚类算法是一个NP难优化问题，无法获得全局最优。介绍了Kmea
s聚类算法的目标函数、算法流程，并列举了一个实例，指出了数据子集的数目K、初始聚类中
和
Jck
xik2
xiCi
（1）
K
聚类目标是使各类总的距离平方和JCJck最k1
小。
K
K
2K

2
JCJck
xik
dkixik
k1
k1xiCi
k1i1
（2）
其中，
dki

10
若xici若xici
，显然，根据最小二乘
法和拉格朗日原理，聚类中心k应该取为类别ck类各数
心选取、相似性度量和距离矩阵为Kmea
s聚类算法的3
据点的平均值。
个基本参数。总结了Kmea
s聚类算法存在的问题及其改
Kmea
s聚类算法从一个初始的K类别划分开始，然
进算法，指出了Kmea
s聚类的进一步研究方向。
后将各数据点指派到各个类别中，以减小总的距离平方r