《k-means聚类算法簇的个数的研究》由会员分享，可在线阅读，更多相关《k-means聚类算法簇的个数的研究（7页珍藏版）》请在金锄头文库上搜索。
1、K-means 聚类算法聚类个数的方法研究摘要：在数据挖掘算法中，K 均值聚类算法是一种比较常见的无监督学习方法，簇间数据对象越相异，簇内数据对象越相似，说明该聚类效果越好。然而，簇个数的选取通常是由有经验的用户预先进行设定的参数。本文提出了一种能够自动确定聚类个数，采用 SSE 和簇的个数进行度量，提出了一种聚类个数自适应的聚类方法(SKKM) 。通过 UCI 数据集的实验，验证了 SKKM 可以快速的找到数据集中聚类个数。关键字：K-means 算法; 聚类个数; 初始聚类中心;近年来，随着信息技术的发展，特别是云计算、物联网、社交网络等新兴应用的产生，我们的社会正从信息时代步入数据时代。
2、数据挖掘就是从大量的、不完整的、有噪声的、模糊的数据中通过数据清洗、数据集成、数据选择、数据变换、数据挖掘、数据评估、知识表示等过程挖掘出隐含信息的过程。目前，数据挖掘已经广泛的应在电信、银行、零售、公共服务、气象等多个行业与领域。聚类是数据挖掘中一项重要的技术指标，也受到人们的重视，并且广泛的应用在多个领域中1。K 均值算法是一种基于划分的聚类算法。通常是由有经验的用户对簇个数 K 进行预先设定，一般用户很难确定 K 的值，K 值设定的不正确将会导致聚类算法结果的错误，因此，本文提出了一种 SKKM 的方法对 K值进行确认。传统的 K 均值聚类算法中的另外一个缺点就是初始中心点的选取问题，随
3、机选取初始中心点将会导致局部最优解， 而不是全局最优解，因此，初始中心点的研究也是聚类算法比较热门的话题。文献2 提出了基于划分的聚类算法，该方法对簇的个数并不是自动的获取，而是通过有经验的用户进行设定。现有的自动确定簇的个数的聚类方法通常需要给出一些参数，然后再确定簇的个数。如：Iterative Self organizing Data Analysis Techniques Algorithm，该方法在实践中需要过多的对参数进行设定，并且很难应用在高维数据中3。为了更方便的确定簇的个数，我们提出了一种可以自动确定聚类个数的聚类方法。簇类个数通常是由某一指标来自动确定，指标的好坏将直接影响
4、聚类的效果。评价聚类算法准则通常是与簇内对象相似成正比，以簇间相似成反比。4 根据 SSE 度量的性质，我们提出了基于 SSE 的 K 乘 SSE 的 K 均值聚类方法。该方法通过划分算法来分配数据点的结果，在最终的结果中利用 SK 来确定最佳聚类个数。从而可以自动确定聚类个数。本文提出的 SKKM 算法，不仅能够有效的自动确定簇的个数，而且适用于多维的数据。与其他的自动确定簇的个数聚类算法相比，我们的算法参数设置更少，在实践中更容易使用，并且在对 UCI 中的数据集和仿真数据的实验中证明了 SKKM 算法的有效性。1. 改进的 k-Means 算法SKKM 算法是本文提出的一种自动确定聚类个
5、数的方法，为了使读者可以更好的了解 SKKM 算法，我们首先介绍划分聚类方法和 SK 指标。1.1 划分聚类方法K-means 算法是将数据集划分为 K 个簇的方法。簇的个数 K 是用户自己预先设定，并且簇的中心点是通过簇的质心来进行描述。算法在调用的过程中会用到欧式距离和质心的概念5，现在我们先来看下欧式距离和质心的定义。定义如下：定义 1 设向量 和 分别表示两个数据向量，12(,.)iiimaa12(,.)jjjmbb那么本文说的欧式距离定义为： 21(,)() (1)ijinjdb其中 n 代表该数据集的维数。定义 2 对于同一个簇中，该簇的质心定义如下： () (2)jiijpTim
6、其中 是该簇的数据个数， 为该簇的数据对象。|Ti jK-means 聚类算法是以 K 为参数，对数据集 N 个对象划分为 K 个数据簇，并且保证簇内数据对象相似度高，簇间数据对象相似度低。首先随机选择 K 个对象，每个对象代表着一个簇的中心。然后对数据集中的剩余数据对象分别计算到 K 个数据对象的距离，并且将其赋给最近的簇中。然后从新计算簇的质心，直到准则函数收敛6算法描述如下：Step1：从数据集中随机取 K 个点作为起始质心Step2：分别计算数据集各个点到 K 个簇的欧式距离，并且将这些数据点划分到各个簇中Step3: 依据聚类结果，通过簇内数据重新计算质心Step4: 重复第二步，直
7、到质心位置不再变化Step5: 输出结果1.2 SK 指标SSE 算法是一种用于度量聚类效果的指标。误差平方和越小，表示越接近与它们的质心，聚类效果相应的也就越好。由于 SSE 是对误差去了平方，因此更加注重远离质心的点。其实有一种有效的方法可以降低 SSE 的值，但这种方法是增加簇的个数来降低 SSE 的值，而聚类算法的目标是保持聚类数目不变的情况下，来提高簇的个数，故该方法并不能有效的保证簇内对象相似，簇间对象相异7。而本文提出的 SK 指标，是将 SSE 的值和 K 值相结合，从而取出最佳 K 值，来达到聚类的目的。定义 3 SSE 的公式定义如式(3)所示：21(,) (3)ikiix
8、CSEdstc其中 表示第 类数据对象的集合。 是簇 的质心，K 表示该数据集可以划iCiiC分为 K 个簇的集合,dist 是欧几里德空间里 2 个空间对象之间的欧式距离。由于 SSE 值越小，说明数据点越接近于它们的质心，簇类效果也就越好。随着 K 的个数的增加，SSE 的值也就越来越小，但是这种方法违背了聚类的初衷。故本文提出了 SK 指标，通过 SSE 值和 K 值来共同找出最佳的 K 值。定义 4 SK 的公式定义如式(4)所示： min(*) (4)SE通过计算 SK 的大小，来反推出最佳簇类个数的选取，SK 越小，说明聚类效果越好，并且对应的 K 值即为最佳的簇类个数，而不用用户
9、自行的设定 K 值大小。1.3 1.3 改进的 K-means 算法SKKM 算法可以对任意维数的数据对象进行聚类，并且能够自动的确定聚类个数，而不是由有经验的用户进行预先定义。前面已经详细的介绍了划分算法和 SK 指标的定义，在划分算法的基础上，寻找 SK 指标的最小值，来确定最佳 K 值的大小，而不是人为的去设定 K 值的大小。该算法具体描述如下：Step1 从样本中随机的选择 K 个数据为初始簇类中心点。并且 K 在 2n的范围内取整数值，并且 K 从 2 开始取值。Step2 通过划分算法对数据对象进行聚类，直到质心大小不再变化。Step3 计算 SK 的取值。先计算误差平方和，再通过
10、 K 值的大小来计算 SK 值。Step4 重复 1-3 的步骤，直到 K 值计算完成。Step5 1-4 步骤进行 100 次，求平均 SK 值Step6 选取最小的 SK 值，其对应的 K 值即为最佳的聚类个数Step7 输出结果2. 实验结果与分析为了验证 SKKM 聚类算法的性能，本实验使用的是 UCI 机器学习数据库的IRIS 和 GLASS 数据8，UCI 数据库是专门用来支持数据挖掘算法和机器学习的常用数据库。因此，K 值的选取是衡量该算法优劣的一项重要指标，并且通过 UCI 的数据来验证该算法的有效性。图 1 仿真数据分布图图 1 是某数据集二维的分布图，通过 k-means
11、算法将其进行聚类，并得出结果如有图所示，从图 1 中我们可以看出该数据集可以划分为 4 个簇。接下来我们用本文提出的 SK 来计算出最佳 K 值得情况，通过对 SSE 的计算，我们可以得出 SK 的分布图，找到 SK 的最佳值，从图中可以看出 4 为该数据集的最佳簇点个数，所以本算法有效。其中图 2 的左边为 SSE 分布图，随着 K 值的逐渐增加，相对应的 SSE 值逐渐趋向于某一常量，但并不是最佳 K 值的选取，并且通过图 2 的右图选取最佳簇点个数。图 2 SSE 和 SK 分布图IRIS 数据集：簇的个数 维数 数据量IRIS 3 4 150图 3 算法在 IRIS 上的应用GLASS
12、 数据集：簇的个数 维数 数据量Glass 6 9 214 图 4 算法在 GlASS 上的应用从图 2-4 中可以看出，SKKM 算法通过对 SK 值的选取，可以找到聚类算法的最佳中心点个数，而不用人为的对 K 值进行设定，与传统的划分 K-means 算法相比，优化了预先设定 K 值的缺点，并且通过实验证明了 SKKM 算法对 K 值确认的有效性。由此可见，SKKM 算法可以有效的解决了聚类算法中心点个数选题的问题。3. 结束语在传统的 K-means 算法中，聚类个数通常是由有经验的用户进行设定，该算法特有的缺点对聚类的性能也会造成一定的影响。因此，该算法并不能行之有效的在实践中进行应用
13、。实验表明，本文提出的基于 SSE 的 SKKM 算法可以准确的确认聚类个数 K 的值，而不是认为的进行设定。参考文献：1. 逄玉俊， 柳 明， 李 元 . K 均值聚类分析在过程改进中的应用 J . 华中科技大学学报： 自然科学版， 2009， 37 （SI ） ： 245-247 .2. 郝洪星， 朱玉全， 陈耿， 李米娜 基于划分和层次的混合动态聚类算法 J 计算机应用研究， 2011( 1) : 51 533. MA Cai-rong, DAI Qin,LIU Shi-bin. A hybrid PSOISODATA algorithm for remote sensing image
14、 segmentation /Proceeding of the 2012 International Conference on Industrial Control and Electronics Engineering(ICICEE). Xian,Chian:IEEE,2012:1371-1375 4. 孙吉贵,刘杰,赵连宇. 聚类算法研究J. Journal of SoftWare,2008,19(1)：48-615. LEE S S ,Lin J C. An accelerated K-means clustering algorithm selection and erasure
15、rulesJ. Zhejiang University-SCIENCE :Computers Electronics,2012,13(10):761-7686. 潘盛辉. 移动终端百度地图偏移修正方法的研究. 信息通信， 2014，(10)：40-42.7.Krista Rizman Zalik,Borut Zalik. Validity index for clusters of different sizes and densities J. Pattern Recognition Letters,2011,32(2):221-2348. 韩凌波， 王 强， 蒋正锋， 等. 一种改进的 K-means 初始聚类中心选取算法 J . 计算机工程与应用， 2010， 46 （17） ： 150-152.
