K-means聚类算法研究综述.docx

《K-means聚类算法研究综述.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、量和距离矩阵ReviewofK-meansclusteringalgorithmAbstract:K-meansclusteringalgorithmisreviewed.K-meansclusteringalgorithmisaNPhardoptimalproblemandglobaloptimalresultcannotbereached.Thegoal，mainstepsandexampleofK-meansclusteringalgorithmareintroduced.K-meansal

3、gorithmrequiresthreeuser-specifiedparameters:numberofclustersK，clusterinitialization，anddistancemetric.ProblemsandimprovementofK-meansclusteringalgorithmaresummarizedthen.FurtherstudydirectionsofK-meansclusteringalgorithmarepointedatlast.Keywords:K-me

4、ansclusteringalgorithm;NPhardoptimalproblem;numberofclustersK;clusterinitialization;distancemetricK-means聚类算法是由Steinhaus1955年、Lloyed1957年、Ball&Hall1965年、McQueen1967年分别在各自的不同的科学研究领域独立的提出。K-means聚类算法被提出来后，在不同的学科领域被广泛研究和应用，并发展出大量不同的改进算法。虽然K-means聚类算法被提出已

5、经超过50年了，但目前仍然是应用最广泛的划分聚类算法之一[1]。容易实施、简单、高效、成功的应用案例和经验是其仍然流行的主要原因。文中总结评述了K-means聚类算法的研究现状，指出K-means聚类算法是一个NP难优化问题，无法获得全局最优。介绍了K-means聚类算法的目标函数、算法流程，并列举了一个实例，指出了数据子集的数目K、初始聚类中心选取、相似性度量和距离矩阵为K-means聚类算法的3个基本参数。总结了K-means聚类算法存在的问题及其改进算法，指出了K-means聚类的进一步研究

6、方向。1经典K-means聚类算法简介1.1K-means聚类算法的目标函数对于给定的一个包含n个d维数据点的数据集，其中，以及要生成的数据子集的数目K，K-means聚类算法将数据对象组织为K个划分。每个划分代表一个类，每个类有一个类别中心。选取欧氏距离作为相似性和距离判断准则，计算该类内各点到聚类中心的距离平方和（1）聚类目标是使各类总的距离平方和最小。（2）其中，，显然，根据最小二乘法和拉格朗日原理，聚类中心应该取为类别类各数据点的平均值。K-means聚类算法从一个初始的K类别划分开始，然

7、后将各数据点指派到各个类别中，以减小总的距离平方和。因为K-means聚类算法中总的距离平方和随着类别个数K的增加而趋向于减小（当时，）。因此，总的距离平方和只能在某个确定的类别个数K下，取得最小值。1.2K-means算法的算法流程K-means算法是一个反复迭代过程,目的是使聚类域中所有的样品到聚类中心距离的平方和最小，算法流程包括4个步骤[1]，具体流程图如图1所示。1)选定数据空间中K个对象作为初始聚类中心，每个对象代表一个类别的中心2)对于样品中的数据对象，则根据它们与这些聚类中心的欧氏

8、距离，按距离最近的准则分别将它们分配给与其最相似的聚类中心所代表的类3)计算每个类别中所有对象的均值作为该类别的新聚类中心，计算所有样本到其所在类别聚类中心的距离平方和，即值4)聚类中心和值发生改变？聚类结束是否图1K-means聚类算法流程图Fig.1StepsofK-meansclusteringalgorithm1.3K-means聚类算法实例图2显示的是K-means算法将一个2维数据集聚成3类的过程示意图。2K-means聚类算法是一个NP难优化问题K-means聚类算法