基于 KRUSKAL 算法进行初值选取的改进的

基于 KRUSKAL 算法进行初值选取的改进的 中国科技论文在线 基于 Kruskal 算法进行初值选取的改进的 K-means 算法 任倩，卓新建 ,北京邮电大学理学院～北京 100876, 5 摘要:K-means 算法是聚类算法中最经典的划分算法之一～它对初值的依赖性很强～聚类结 果随初始聚类中心选择的不同而波动很大。本文基于图论中著名的 Kruskal 算法提出了一种 改进的 K-means 算法～该算法首先运用 Kruskal 算法生成聚类对象的最小生成树,MST,～ 然后按权值从大到小删去 K-1 条边～将得到的 K 个连通子图中对象的均值作为初始聚类中心 进行聚类。仿真实验明～该算法较传统 k-means 算法有更好的聚类效果和准确性。 10 关键词:聚类,K-means 算法,Kruskal 算法,MST 中图分类号:TP301 Improved K-means Algorithm of Choosing the Clustering Center Based on Kruskal Algorithm 15 REN Qian, ZHUO Xinjian (School of Science,Beijing University of Post and Communication, Beijing 100876) Abstract: K-means algorithm is one of the most classic partition algorithms in clustering algorithms. The result obtained by K-means algorithm varies with the choice of the initial 20 clustering center. Motivated by this, an improved K-means algorithm is proposed based on the Kruskal algorithm, which is famous in graph theory. The procedure of this algorithm is shown as follows: Firstly, the minimum spanning tree (MST) of the clustered objects is obtained by using Kruskal algorithm. Then K-1 edges are deleted based on weights in a descending order. At last, the average value of the objects contained by the k-connected graph resulting from last two steps is regarded as the initial clustering center to cluster. Simulation exeriment shows that the improved 25 K-means algorithm has a better clustering effect and higher efficiency than the traditional one. Keywords:Clustering; K-means Algorithm; Kruskal Algorithm; MST 0 引言 随着数据挖掘技术研究的不断成熟，作为其主要算法之一的聚类算法也越来越得到人们 30 的关注，有关聚类算法的研究也已经取得了丰硕的成果。根据对象间的相似性度量和聚类评 价准则等的不同，聚类一般包括:(1)基于划分的方法;(2)基于层次的方法;(3)基于密 度的方法;(4)基于网格的方法;(5)基于模型的方法。此外还有模糊聚类方法，核聚类方法， 谱聚类方法等新发展的聚类方法[1]。K-均值(K-means)聚类法是典型的划分方法,具有简单、 快速的优点。然而这种算法对初始聚类中心的选择很敏感, 初值选取的不同往往导致聚类结 35 果差异很大，当初始聚类中心选择不当时，算法极易陷入局部极小点。近几年来人们提出了 多种改进和优化的方法，例如 PaulS.Bradley 等提出的基于采样的初始类簇中心算法[2]， Moh’dB.Al-Daoud 和 Stuart A.Roberts 提出的基于划分的密度估计法[3]，Kaufman 提出的通过 数据点的局部密度来估算初始类簇中心[4]，周海岩等提出的基于图论的连通分支来进行初始 聚类中心选取的 K-means 算法[5]，步媛媛提出的基于欧几里德距离确定相隔最远的两个数据 40 点之间的距离，将数据集均分为 k 个段，进而寻求聚类中心的方法[6]，李卫平提出的基于贪 心算法对初始聚类中心进行选取的 k-means 算法[7], 苏锦旗等提出的基于划分的 K-均值初始 作者简介:任倩，(1986-)，女，硕士研究生，数据挖掘 通信联系人:卓新建，(1971-)，男，副教授，网络编码，数据挖掘. E-mail: zhuoxj@163.com -1- 中国科技论文在线 聚类中心优化算法[8]。本文基于图论中的 Kruskal 算法对聚类中心的选取进行了改进, 提出 了一种改进的 K-means 算法，并通过仿真实验，证实该算法改善了传统 K-means 算法对初 45 值选取的依赖性, 提高了聚类结果的稳定性和准确性。 1 K-means 算法 1.1 K-means 算法的基本原理 假定需要聚类的对象共有 n 个，样本集为 X = {x1,x 2 ,..., x n }，K-means 算法的目的是 把 n 个样本对象分为 K 个簇，使得簇内的样本对象有较高的相似度，而簇间的样本对象相 似度很低。具体思想如下: 50 1)随机选取 K 个对象作为初始的聚类中心 c1,c2 ,...,cK 。 2)将数据样本集中的每一个样本对象按照最小距离原则 ---式 1.1.1 Dj =min X-cj ,X={x1,x2,...,xn} j =1,2,...K , 分配到 K 个聚类中的某一个。 55 3)以每个聚类中所有样本对象的均值 n 1 j ---式 1.1.2 为 第 j类 中样 本 对 象 个 数 , j =1,2,..., c j = å xi nj i=1 jn,K 作为新的聚类中心。 4)如果聚类中心有变化则重复 2)，3)步，直到聚类中心不再变化为止，即使得聚类 准则函数 60 ---式 1.1.3 其中c j是聚类S j的聚类中心 收敛。 1.2 K-means 算法的流程图 图 1 K-means 算法流程图 Fig. 1 Flow of K-means algorithm 65 -2- 中国科技论文在线 1.3 K-means 算法的缺点 K-means 算法有两个缺点: (1) 对于不同初始聚类中心的选取可能导致不同的聚类结果; 70 (2) 该算法是基于目标函数的寻优算法,通常采用梯度法求解极值,算法很容易陷入局部 [9] 极值 。 本文针对第一个缺点对 K-menas 算法进行改进，提出一种基于图论中 Kruskal 算法寻找 初始聚类中心的算法。 2 基于 Kruskal 算法进行初值选取的改进的 K-means 算法 2.1 Kruskal 算法介绍 75 Æ， 设无向连通图 G=(V,E)，令 G 的最小生成树为 T=(U,H)，其初始状态为 U=V，H= 这样 T 中各顶点各自构成一个连通分支，然后按照边的权值由小到大的顺序，依次选择边 集 E 中的各条边，若被选择的边的两个顶点属于 T 的两个不同的连通分支，则将此边加入 到 H 中去，同时把两个连通分支连接成一个连通分支;若被选择的两个节点属于同一个连 通分支，则舍去此边，以免造成回路，如此下去，当 T 中的连通分支个数为 1 时，此连通 80 分支为 G 的一棵最小生成树(MST)。 2.2 改进 K-means 算法的思想 对于给定的数据集 X = {x1, x 2 ,..., x n },我们的任务是对 X 中的数据对象进行聚类。首先 定义数据对象之间的距离，本文采用欧几里德距离，将 X 中任意两个对象之间的距离作为 权值赋予连接这两个对象的边，于是得到一个无向赋权图 G(X)。 85 利用 Kruskal 算法求出此无向赋权图 G(X)的最小生成树(MST)，按权值从大到小删除最 小生成树中的 K-1 条边，得到 K 个连通子图，计算这 K 个连通子图中数据对象的平均值作 为初始的聚类中心，然后用原始的 K-means 算法做聚类。 2.3 改进 K-means 算法的流程图 90 -3- 中国科技论文在线 图 2 改进 K-means 算法流程图 Fig. 2 Flow of K-means algorithm 3 仿真实验及结果分析 95 3.1 实验环境 Windows XP 操作系统，MATLAB7.1 编程语言 实验数据 3.2 随机生成 50 个二维数据对象，其数据分布如图 3 所示。 K 为聚类数目，进行聚类分析前输入。 100 图 3 50 个随机二维数据对象分布图 Fig. 3 Distribution of 50 random two-dimensional data objects -4- 中国科技论文在线 3.3 结果分析 算法聚类后(K=4)，结果分布如图 4 所示。 经传统 K-means 105 图 4 传统 K-means 算法的聚类结果图 Fig.4 Clustering distribution based on traditional K-means algorithm 经改进 K-means 算法聚类后(K=4)，结果分布如图 5 所示。 110 图 5 改进 K-means 算法的聚类结果图 Fig.5 Clustering distribution based on improved K-means algorithm 将随机生成的 50 个二维数据对象根据分类数的不同分别用传统 K-means 算法，本文提 115 出的改进算法及文献[7]中提出的算法进行 5 次聚类实验，目标函数值如表 1 所示。 120 -5- 中国科技论文在线 表 1 50 个随机二维数据对象聚类数分别为 2,3,4,5 的目标函数值 125 Tab. 1 Function values of 50 random two-dimensional data objects based on k is 2,3,4,5 respectively 目标 K=2 K=3 K=4 K=5 [7] [7] [7] [7] K-m 改 进 K-mea 改 进 K-mea 改 进 K-mea 改 进 函数值 文献 文献 文献 文献 eans ns ns ns 算 法 中 的 算 法 中 的 算 法 中 的 算 法 中 的 试验 算法 算 法 算 法 算 法 算 法 算 法 算 法 算 法 次数 1 5361 47887 47840 28156 28877 28521 18300 18165 64258 13703 14780 73264 6 2 4784 47887 47840 28337 28877 28521 25320 18165 64258 18506 14780 73264 0 3 4900 47887 47840 29867 28877 28521 45592 18165 64258 20435 14780 73264 1 4 5970 47887 47840 53029 28877 28521 25698 18165 64258 58335 14780 73264 6 5 7703 47887 47840 36598 28877 28521 30624 18165 64258 20468 14780 73264 0 由图 4 和图 5 可知，改进的 K-means 算法改善了聚类分析的效果，整体分布比较均匀。 由表 1 可知， K-means 算法随机选取初值，每次试验得到的目标函数值都不一样，结 果波动很大。而改进的 K-means 算法利用 Kruskal 算法已经确定初始中心，聚类结果稳定， 130 实验证明该算法有效解决了传统 K-means 算法对初始聚类中心敏感的缺点。同时改进算法 得到的目标函数值比传统 K-means 算法的平均目标函数值小，符合聚类算法使聚类准则函 数收敛到最小的要求。表 1 中还运用文献 7 中提出的算法对此二维数据进行了聚类对比实验， 数据显示当 K 值较小时，聚类结果和本文改进算法的结果差别很小，当 K 值较大时，聚类 结果与本文改进算法的结果差别较大。 135 4 结论 传统 K-means 聚类算法的聚类结果取决于初始聚类中心的选择，本文基于此，利用图 论中的 Kruskal 算法寻找最小树(MST)取得初始聚类中心，对 K-means 算法进行改进(通过 仿真实验，分析得出该算法成功解决了传统 K-means 算法对初始聚类中心敏感的问题，并 且改进后的算法在聚类准确性和稳定性方面优于传统的 K-means 算法。 140 [参考文献] (References) [1] Jiawei Han,Mieheline Kamber.数据挖掘概念与技术[M].范明、孟小峰,等译.北京:机械工业出版社,2001. [2] Bradley P S, Fayyad U M.Refining initial points for K-Means clustering [C]//Proc. of the 15th International Conf. on Machine Learning. San Francisco, CA: MorganKaufmann, 1998: 91-99. 145 [3] Moh'd B Al-Daoud, Stuart A Roberts. New methods for the initialization of clusters [J]. Pattern Recognition Letters, 2001 (17) : 451- 455. [4] Kaufman L,Rousseeuw P J. Finding groups in data:an introduction to cluster analysis[M]. NY:John Wiley &Sons , 1990. [5] 周海岩, 白晓林. 基于图的 K-均值聚类法中初始聚类中心选择[J]. 计算机测量与控制, 2010, 18 150 (9):2167-2169. [6] 步媛媛, 关中仁. 基于 K-Means 聚类算法的研究[J].广西南民族大学学报 2009:35(1). [7] 李卫平. 对 k-means 聚类算法的改进研究[J]. 中国西部科技, 2010, 9(24):49-50. [8] 苏锦旗, 薛惠锋, 詹海亮( 基于划分的 K-均值初始聚类中心优化算法[J]. 微电子学与计算机, 2009, 26(1):8-11( 155 [9] 黄光球, 王西邓. 基于网格划分策略的改进人工鱼群算法[J]微电子学与计机,2007 ,24 (7) :83 - 86. -6-