K-means聚类算法簇的个数的研究

K-means聚类算法聚类个数的方法研究摘要：在数据挖掘算法中，K均值聚类算法是一种比较常见的无监督学习方法，簇间数据对象越相异，簇内数据对象越相似，说明该聚类效果越好。然而，簇个数的选取通常是由有经验的用户预先进行设定的参数。本文提出了一种能够自动确定聚类个数，采用SSE和簇的个数进行度量，提出了一种聚类个数自适应的聚类方法(SKKM)。通过UCI数据集的实验，验证了SKKM可以快速的找到数据集中聚类个数。关键字：K-means算法;聚类个数;初始聚类中心;近年来，随着信息技术的发展，特别是云计算、物联网、社交网络等新兴应用的产生，我们的社会正从信息时代步入数据时代。数据挖掘就是从大量的、不完整的、有噪声的、模糊的数据中通过数据清洗、数据集成、数据选择、数据变换、数据挖掘、数据评估、知识表示等过程挖掘出隐含信息的过程。目前，数据挖掘已经广泛的应在电信、银行、零售、公共服务、气象等多个行业与领域。聚类是数据挖掘中一项重要的技术指标，也受到人们的重视，并且广泛的应用在多个领域中[1]。K均值算法是一种基于划分的聚类算法。通常是由有经验的用户对簇个数K进行预先设定，一般用户很难确定K的值，K值设定的不正确将会导致聚类算法结果的错误，因此，本文提出了一种SKKM的方法对K值进行确认。传统的K均值聚类算法中的另外一个缺点就是初始中心点的选取问题，随机选取初始中心点将会导致局部最优解，而不是全局最优解，因此，初始中心点的研究也是聚类算法比较热门的话题。文献[2]提出了基于划分的聚类算法，该方法对簇的个数并不是自动的获取，而是通过有经验的用户进行设定。现有的自动确定簇的个数的聚类方法通常需要给出一些参数，然后再确定簇的个数。如：IterativeSelforganizingDataAnalysisTechniquesAlgorithm，该方法在实践中需要过多的对参数进行设定，并且很难应用在高维数据中[3]。为了更方便的确定簇的个数，我们提出了一种可以自动确定聚类个数的聚类方法。簇类个数通常是由某一指标来自动确定，指标的好坏将直接影响聚类的效果。评价聚类算法准则通常是与簇内对象相似成正比，以簇间相似成反比。[4]根据SSE度量的性质，我们提出了基于SSE的K乘SSE的K均值聚类方法。该方法通过划分算法来分配数据点的结果，在最终的结果中利用SK来确定最佳聚类个数。从而可以自动确定聚类个数。本文提出的SKKM算法，不仅能够有效的自动确定簇的个数，而且适用于多维的数据。与其他的自动确定簇的个数聚类算法相比，我们的算法参数设置更少，在实践中更容易使用，并且在对UCI中的数据集和仿真数据的实验中证明了SKKM算法的有效性。1.改进的k-Means算法SKKM算法是本文提出的一种自动确定聚类个数的方法，为了使读者可以更好的了解SKKM算法，我们首先介绍划分聚类方法和SK指标。1.1划分聚类方法K-means算法是将数据集划分为K个簇的方法。簇的个数K是用户自己预先设定，并且簇的中心点是通过簇的质心来进行描述。算法在调用的过程中会用到欧式距离和质心的概念[5]，现在我们先来看下欧式距离和质心的定义。定义如下：定义1设向量12(,,...,)iiiimaaaa和12(,,...,)jjjjmbbbb分别表示两个数据向量，那么本文说的欧式距离定义为：21(,)()(1)mijinjnndabab其中n代表该数据集的维数。定义2对于同一个簇中，该簇的质心定义如下：1()(2)jiijpTimTpT其中||Ti是该簇的数据个数，jp为该簇的数据对象。K-means聚类算法是以K为参数，对数据集N个对象划分为K个数据簇，并且保证簇内数据对象相似度高，簇间数据对象相似度低。首先随机选择K个对象，每个对象代表着一个簇的中心。然后对数据集中的剩余数据对象分别计算到K个数据对象的距离，并且将其赋给最近的簇中。然后从新计算簇的质心，直到准则函数收敛[6]算法描述如下：Step1：从数据集中随机取K个点作为起始质心Step2：分别计算数据集各个点到K个簇的欧式距离，并且将这些数据点划分到各个簇中Step3:依据聚类结果，通过簇内数据重新计算质心Step4:重复第二步，直到质心位置不再变化Step5:输出结果1.2SK指标SSE算法是一种用于度量聚类效果的指标。误差平方和越小，表示越接近与它们的质心，聚类效果相应的也就越好。由于SSE是对误差去了平方，因此更加注重远离质心的点。其实有一种有效的方法可以降低SSE的值，但这种方法是增加簇的个数来降低SSE的值，而聚类算法的目标是保持聚类数目不变的情况下，来提高簇的个数，故该方法并不能有效的保证簇内对象相似，簇间对象相异[7]。而本文提出的SK指标，是将SSE的值和K值相结合，从而取出最佳K值，来达到聚类的目的。定义3SSE的公式定义如式(3)所示：21(,)(3)ikiixCSSEdistcx其中iC表示第i类数据对象的集合。ic是簇iC的质心，K表示该数据集可以划分为K个簇的集合,dist是欧几里德空间里2个空间对象之间的欧式距离。由于SSE值越小，说明数据点越接近于它们的质心，簇类效果也就越好。随着K的个数的增加，SSE的值也就越来越小，但是这种方法违背了聚类的初衷。故本文提出了SK指标，通过SSE值和K值来共同找出最佳的K值。定义4SK的公式定义如式(4)所示：min(*)(4)SKSSEK通过计算SK的大小，来反推出最佳簇类个数的选取，SK越小，说明聚类效果越好，并且对应的K值即为最佳的簇类个数，而不用用户自行的设定K值大小。1.31.3改进的K-means算法SKKM算法可以对任意维数的数据对象进行聚类，并且能够自动的确定聚类个数，而不是由有经验的用户进行预先定义。前面已经详细的介绍了划分算法和SK指标的定义，在划分算法的基础上，寻找SK指标的最小值，来确定最佳K值的大小，而不是人为的去设定K值的大小。该算法具体描述如下：Step1从样本中随机的选择K个数据为初始簇类中心点。并且K在2Kn的范围内取整数值，并且K从2开始取值。Step2通过划分算法对数据对象进行聚类，直到质心大小不再变化。Step3计算SK的取值。先计算误差平方和，再通过K值的大小来计算SK值。Step4重复1-3的步骤，直到K值计算完成。Step51-4步骤进行100次，求平均SK值Step6选取最小的SK值，其对应的K值即为最佳的聚类个数Step7输出结果2.实验结果与分析为了验证SKKM聚类算法的性能，本实验使用的是UCI机器学习数据库的IRIS和GLASS数据[8]，UCI数据库是专门用来支持数据挖掘算法和机器学习的常用数据库。因此，K值的选取是衡量该算法优劣的一项重要指标，并且通过UCI的数据来验证该算法的有效性。图1仿真数据分布图图1是某数据集二维的分布图，通过k-means算法将其进行聚类，并得出结果如有图所示，从图1中我们可以看出该数据集可以划分为4个簇。接下来我们用本文提出的SK来计算出最佳K值得情况，通过对SSE的计算，我们可以得出SK的分布图，找到SK的最佳值，从图中可以看出4为该数据集的最佳簇点个数，所以本算法有效。其中图2的左边为SSE分布图，随着K值的逐渐增加，相对应的SSE值逐渐趋向于某一常量，但并不是最佳K值的选取，并且通过图2的右图选取最佳簇点个数。图2SSE和SK分布图IRIS数据集：簇的个数维数数据量IRIS34150图3算法在IRIS上的应用GLASS数据集：簇的个数维数数据量Glass69214图4算法在GlASS上的应用从图2-4中可以看出，SKKM算法通过对SK值的选取，可以找到聚类算法的最佳中心点个数，而不用人为的对K值进行设定，与传统的划分K-means算法相比，优化了预先设定K值的缺点，并且通过实验证明了SKKM算法对K值确认的有效性。由此可见，SKKM算法可以有效的解决了聚类算法中心点个数选题的问题。3.结束语在传统的K-means算法中，聚类个数通常是由有经验的用户进行设定，该算法特有的缺点对聚类的性能也会造成一定的影响。因此，该算法并不能行之有效的在实践中进行应用。实验表明，本文提出的基于SSE的SKKM算法可以准确的确认聚类个数K的值，而不是认为的进行设定。参考文献：[1].逄玉俊，柳明，李元.K均值聚类分析在过程改进中的应用［J］.华中科技大学学报：自然科学版，2009，37（SI）：245-247.[2].郝洪星，朱玉全，陈耿，李米娜．基于划分和层次的混合动态聚类算法［J］．计算机应用研究，2011(1):51－53．[3].MACai-rong,DAIQin,LIUShi-bin.AhybridPSOISODATAalgorithmforremotesensingimagesegmentation//Proceedingofthe2012InternationalConferenceonIndustrialControlandElectronicsEngineering(ICICEE).Xi’an,Chian:IEEE,2012:1371-1375[4].孙吉贵,刘杰,赵连宇.聚类算法研究[J].JournalofSoftWare,2008,19(1)：48-61[5].LEESS,LinJC.AnacceleratedK-meansclusteringalgorithmselectionanderasurerules[J].ZhejiangUniversity-SCIENCE:ComputersElectronics,2012,13(10):761-768[6].潘盛辉.移动终端百度地图偏移修正方法的研究.信息通信，2014，(10)：40-42.[7].KristaRizmanZalik,BorutZalik.Validityindexforclustersofdifferentsizesanddensities[J].PatternRecognitionLetters,2011,32(2):221-234[8].韩凌波，王强，蒋正锋，等.一种改进的K-means初始聚类中心选取算法［J］.计算机工程与应用，2010，46（17）：150-152.