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

K-means聚类算法研究综述摘要:总结评述了K-means聚类算法的研究现状，指出K-means聚类算法是一个NP难优化问题，无法获得全局最优。介绍了K-means聚类算法的目标函数，算法流程，并列举了一个实例，指出了数据子集的数目K，初始聚类中心选取，相似性度量和距离矩阵为K-means聚类算法的3个基本参数。总结了K-means聚类算法存在的问题及其改进算法，指出了K-means聚类的进一步研究方向。关键词：K-means聚类算法；NP难优化问题；数据子集的数目K；初始聚类中心选取；相似性度量和距离矩阵ReviewofK-meansclusteringalgorithmAbstract:K-meansclusteringalgorithmisreviewed.K-meansclusteringalgorithmisaNPhardoptimalproblemandglobaloptimalresultcannotbereached.Thegoal，mainstepsandexampleofK-meansclusteringalgorithmareintroduced.K-meansalgorithmrequiresthreeuser-specifiedparameters:numberofclustersK，clusterinitialization，anddistancemetric.ProblemsandimprovementofK-meansclusteringalgorithmaresummarizedthen.FurtherstudydirectionsofK-meansclusteringalgorithmarepointedatlast.Keywords:K-meansclusteringalgorithm;NPhardoptimalproblem;numberofclustersK;clusterinitialization;distancemetricK-means聚类算法是由Steinhaus1955年、Lloyed1957年、Ball&Hall1965年、McQueen1967年分别在各自的不同的科学研究领域独立的提出。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.1K-means聚类算法的目标函数对于给定的一个包含n个d维数据点的数据集12{x,x,,x,,x}inX，其中dixR，以及要生成的数据子集的数目K，K-means聚类算法将数据对象组织为K个划分{c,i1,2,}kCK。每个划分代表一个类ck，每个类ck有一个类别中心i。选取欧氏距离作为相似性和距离判断准则，计算该类内各点到聚类中心i的距离平方和2(c)iikikxCJx（1）聚类目标是使各类总的距离平方和1(C)(c)KkkJJ最小。221111(C)(c)iiKKKnkikkiikkkxCkiJJxdx（2）其中，10iikiiixcdxc若若，显然，根据最小二乘法和拉格朗日原理，聚类中心k应该取为类别kc类各数据点的平均值。K-means聚类算法从一个初始的K类别划分开始，然后将各数据点指派到各个类别中，以减小总的距离平方和。因为K-means聚类算法中总的距离平方和随着类别个数K的增加而趋向于减小（当Kn时，(C)0J）。因此，总的距离平方和只能在某个确定的类别个数K下，取得最小值。1.2K-means算法的算法流程K-means算法是一个反复迭代过程,目的是使聚类域中所有的样品到聚类中心距离的平方和(C)J最小，算法流程包括4个步骤[1]，具体流程图如图1所示。图1K-means聚类算法流程图Fig.1StepsofK-meansclusteringalgorithm1.3K-means聚类算法实例图2显示的是K-means算法将一个2维数据集聚成3类的过程示意图。2K-means聚类算法是一个NP难优化问题K-means聚类算法是一个NP难优化问题吗？在某个确定的类别个数K下，在多项式时间内，最小的总距离平方和(C)J值和对应的聚类划分能否得到？目前，不同的学者有不同的答案。AristidisLikas等人[2]认为在多项式时间内最小的值和对应的聚类划分能够得到，并于2002年提出了全局最优的K-means聚类算法。但给出的“TheglobalK-meansclusteringalgorithm”只有初始聚类中心选取的算法步骤，而缺乏理论证明。很快，pierreHansen等人[3]就提出“TheglobalK-meansclusteringalgorithm”不过是一个启发式增量算法，并不能保证得到全局最优，文章最后还给出了反例。很多学者指出，如果数据点的维数1d，最小的总距离平方和(C)J值和对应的聚类划分能够在2(Kn)O时间内使用动态规划获得，例如BellmanandDreyfus[4]。PierreHansen等人[3]认为,K-means聚类算法时间复杂度未知。但是，更多的学者认为，对于一般的数据维数d和类别个数K，K-means聚类算法是一个NP难优化问题[5]。SanjoyDasgupta等人认为即使在类别个数K=2的情况下，K-means聚类算法也是一个NP难优化问题。MeenaMahajan等人[6]认为即使在数据点的维数2d下，对于平面的K-means聚类问题，也是NP难的。本研究也认为，对于一般的数据维数d和类别个数K，K-means聚类算法是一个NP难优化问题。K-means聚类算法是一个贪心算法，在多项式时间内，仅能获得局部最优，而不可能获得全局最优。(a)将被分成3类的2维原始输入数据(b)选择3个种子数据点作为3个类的初始聚类中心(a)two-dimensionalinputdatawiththreeclusters(b)Threeseedpointsselectedasclustercentersandinitialassignmentofthedatapointstoclusters1)选定数据空间中K个对象作为初始聚类中心，每个对象代表一个类别的中心2)对于样品中的数据对象，则根据它们与这些聚类中心的欧氏距离，按距离最近的准则分别将它们分配给与其最相似的聚类中心所代表的类3)计算每个类别中所有对象的均值作为该类别的新聚类中心，计算所有样本到其所在类别聚类中心的距离平方和，即(C)J值4)聚类中心和(C)J值发生改变？聚类结束是否(c)更新聚类类别和类别中心的第二次迭代过程(d)更新聚类类别和类别中心的第3次的迭代过程(e)K-means聚类算法收敛所获得的最终聚类结果(c)steptwoofintermediateliterationsupdating(d)Stepthreeofintermediateiterationsupdating(e)finalclusteringobtainedbyK-meansalgorithmclusterlabelsandtheircentersclusterlabelsandtheircentersatconvergence图2K-means算法示意图Fig.2IllustrationofK-meansalgorithm3K-means聚类算法的参数及其改进K-means聚类算法需要用户指定3个参数：类别个数K，初始聚类中心、相似性和距离度量。针对这3个参数，K-means聚类算法出现了不同的改进和变种。3.1类别个数KK-means聚类算法最被人所诟病的是类别个数K的选择。因为缺少严格的数学准则，学者们提出了大量的启发式和贪婪准则来选择类别个数K。最有代表性的是，令K逐渐增加，如1,2,K，因为K-means聚类算法中总的距离平方和J随着类别个数K的增加而单调减少。最初由于K较小，类型的分裂（增加）会使J值迅速减小，但当K增加到一定数值时，J值减小速度会减慢，直到当K等于总样本数N时，0J，这时意味着每类样本自成一类，每个样本就是聚类中心。如图3所示，曲线的拐点A对应着接近最优的K值，最优K值是对J值减小量、计算量以及分类效果等进行权衡得出的结果。而在实际应用中，经常对同一数据集，取不同的K值，独立运行K-means聚类算法，然后由领域专家选取最有意义的聚类划分结果。图3J-K关系曲线Fig.3RelationshipcurvebetweenJandK并非所有的情况都容易找到J-K关系曲线的拐点，此时K值将无法确定。对类别个数K的选择改进的算法是Ball&Hall[7]于1965年提出的迭代自组织的数据分析算法（IterativeSelf-organizingDataAnalysisTechniqueAlgorithm,ISODATA），该算法在运算的过程中聚类中心的数目不是固定不变的，而是反复进行修改，以得到较合理的类别数K，这种修改通过模式类的合并和分裂来实现，合并与分裂在一组预先选定的参数指导下进行。3.2初始聚类中心的选取越来越多的学者倾向于认为最小化总距离平方和(C)J值和对应的聚类划分是一个ＮＰ难优化问题。因此，K-means聚类算法是一个贪心算法，在多项式时间内，仅能获得局部最优。而不同的初始聚类中心选取方法得到的最终局部最优结果不同。因此，大量的初始聚类中心选取方案被提出。经典的K-means聚类算法的初始聚类中心是随机选取的。SelimSZ,Al-SultanKS于1991年提出的随机重启动K-means聚类算法是目前工程中应用最广泛的初始聚类中心选取方法，其过程如图4所示。王成等人提出使用最大最小原则来选取初始聚类中心[8]，与其它方法不同的是，该过程是一个确定性过程。模拟退火、生物遗传等优化搜索算法也被用于K-means聚类算法初始聚类中心的选取。四种初始聚类中心选取方法的比较可见文献[9]。自从AristidisLikas等人[2]提出“TheglobalK-meansclusteringalgorithm”，对其的批评[3]、讨论和改进就没有停止过[10]。图4多次重启动K-means聚类算法流程图Fig.4StepsofmultiplerestartsK-meansclusteringalgorithm3.3相似性度量和距离矩阵K-means聚类算法使用欧式距离作为相似性度量和距离矩阵，计算各数据点到其类别中心的距离平方和。因此，K-means聚类算法划分出来的类别店铺是类球形的。实际上，欧式距离是Minkowski距离在2m时的特例，即2L距离。在采用mL距离进行K-means聚类时，最终类中心应是每一类的m中心向量。Kashima等人于2008年使用1L距离，最终聚类中心使每一类的中位向量。对于一维数据12,{x,x,x,,x}inX而言，中位数M比均值x对异常数据有较强的抗干扰性，聚类结果受数据中异常值的影响较小。Mao&Jain[11]于1996年提出使用Mahalanobis距离，但计算代价太大。在应用中，Linde等。于1980年提出使用Itakura-Saito距离。Banerjee等人2004年提出，如果使用Bregman差异作为距离度量，有许多突