评价网 > 科教论文 > 工学毕业论文 > 计算机应用论文 > 正文

基于聚类K-means算法的初值依赖性研究(1)

2015-01-08 02:13 摘 要 聚类分析是数据挖掘中的一个重要研究领域。K-means 算法对随机选取K个初始点作为初始值是很敏感的，聚类的质量依赖于初始值。在分析聚类结果对初值依赖性的基础上，对初值选取方法进行了分析和研究，并提出了一种有效的改进方法，通过试验证明了改进算法的有效性。 关键词 数据挖掘；聚类；K-means；初值1 引言 数据挖掘(Data Mining)，又称为数据库中的知识发现(简称 KDD)，是从大量数据中提取可信的、新颖的、有效的并能被人们理解的模式的处理过程。它是一门新兴的交叉学科，汇集了来自机器学习、模式识别、数据库、统计学、人工智能等各领域的研究成果。聚类是数据挖掘中的一种主要技术，是把一组个体按照相似性归成若干类别即“物以类聚”。它的目的是使得属于同一类别的个体之间的距离尽可能的小而不同类别上的个体间的距离尽可能大。2 聚类K-means算法简介 K-means 算法属于数据挖掘聚类分析方法中一种基本的且应用最广泛的划分算法，它是一种已知聚类类别数的聚类算法。指定类别数为K，对样本集合进行聚类，聚类的结果由K 个聚类中心来表达，基于给定的聚类目标函数(或者说是聚类效果判别准则)，算法采用迭代更新的方法，每一次迭代过程都是向目标函数值减小的方向进行，最终的聚类结果使目标函数值取得极小值，达到较优的聚类效果。根据聚类结果的表达方式又可以分为硬 K-means(HCM)算法、模糊 K-means 算法(FCM)和概率 K-means 算法(PCM)。该算法的基本框架如下： (1) 给定大小为 N 的数据集，令 I =1，选取 k 个初始聚类中心 Z j(I)，j =1，2，3，...，k。 (2)计算每个数据对象与聚类中心的距离D(Xi，Zj(I))。 其中 i=1，2，3，…，n，j=1，2，3，…，k，如果满足(1)式： 则Xi∈Wk； (3)计算K个新的聚类中心 (4)判断：若Zj(I 1)≠Zj(I)，j=1，2，3，…，K，则I=I 1，返回(2)，否则该算法结束。从上面的算法思想和算法框架，我们不难看出，K个初始聚类中心点的选取对聚类结果具有较大的影响，因为在该算法中是随机地选取任意K个点作为初始聚类中心。如果有先验知识，可以选取具有代表性的点作为初始中心点。3 聚类K-means算法的初值依赖性3.1 初值依赖性分析 无论是原始K-means算法还是使用了聚类准则函数的K-means算法，都具有一个共同的特点：在算法的初始阶段都要选取K个点作为初始聚类中心，然后在此基础上进行反复迭代。选取的点不同，聚类结果可能就有所不同，所以这个算法的聚类结果对初值的依赖性很强，这样的依赖性导致聚类结果的不稳定。当然也有可能碰到最极端的初值选取情况，这种情况使得算法运行时间加长，聚类准则函数难以收敛，聚类结果更加难以预测。3.2 实验结论 为了证明初值选取对聚类结果的影响，制作了一个测试模块。运用算法测试模块得到的结果分别如图1和2所示，图中圆圈代表的是初始的聚类中心即初值，zi(i=1，2，3，4，5)表示聚类完成后的聚类中心，wi(i=1，2，3，4，5)表示每个簇。每一个数据对象被分配给离它最近的聚类中心所在的类。我们可以很清楚地看到初始值的选取对聚类结果的影响，反过来也可以说是聚类结果对初始聚类中心的依赖。 显然，图2中由于初始聚类中心点的选择比较好，因此最后的聚类结果较为理想。因此，随机选择初始聚类中心使得聚类很难得到一个稳定的聚类结果。针对聚类初值选择这一问题，有文献考虑了冗余类中心初始化方法，该方法扩大了解空间的搜索范围，减少了某些极值点附近无初值的机会，初始聚类中心在数据空间中分布较广，具有多样性。具体方法为采用适当准则逐步减小类的个数，直到指定达到指定的k 的数目，这样得到的聚类结果受随机选择初始聚类中心的影响较小。初始的聚类中心选的越多，聚类结果受初值的影响就越小。但在这个算法中，需要确定一个合并参数d，即对类间距小于d的类就进行合并。实际上，对这个合并参数d很难确定，而这个参数的选择又直接影响着聚类结果。该改进算法使得在增加聚类中心的同时也增加了算法中的计算量和聚类结果的不确定性。