一种改进的基于遗传算法的K均值聚类算法

文章编号: 1004- 5422( 2011) 02- 0162- 03 一种改进的基于遗传算法的 K 均值聚类算法 唐朝霞 (淮阴工学院 计算机工程学院, 江苏 淮安 � 223003) 摘 � 要: 结合遗传算法和 K 均值聚类算法的优点, 提出一种改进的基于遗传算法的 K 均值聚类算法. 将遗传 算法的编码方法、初始化、适应度 函 关于工期滞后的函关于工程严重滞后的函关于工程进度滞后的回复函关于征求同志党风廉政意见的函关于征求廉洁自律情况的复函 数、选择、交叉和变异等较好地应用于聚类问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 ,不仅解决了 K 均值聚类算 法中 K值难以确定、对初始值敏感以及遗传算法存在收敛性差和容易早熟的缺点,而且实现了聚类中心的优 化选择、K 值的自动学习和基因的自适应变异等. 仿真实验表明,改进后的算法效率有较大的提高. 关键词: 聚类分析;遗传算法; K 均值 中图分类号: TP301�6� � � � � � � � � � 文献标识码: A 0 � 引 � 言 聚类是一种无监督的分类方法, 是按照某个特 定标准把一个数据集分割成不同的类或簇, 使得在 同一个簇内的数据相似性尽可能的大, 而不在同一 个簇中的数据差异性也尽可能的大. 聚类作为一种 重要的数据分析技术, 可以大大提高算法的运行效 率. 目前, 聚类已经成为数据挖掘领域中一个非常 重要的研究课题 [ 1] , 聚类算法主要有: K 均值聚类 算法, 基于网格的聚类算法, 基于神经网络的聚类 算法, 模糊 c均值( FCM ) 聚类算法等 [2] . 在聚类算 法中, 每种聚类算法都有各自的缺点, 比如易陷入 局部最优、对初始聚类中心敏感和复杂度过高 等[ 3- 4] . 遗传算法作为一种高效的全局优化搜索算 法, 广泛应用于各种优化问题中, 该算法以适应度 函数为依据, 通过对个体施加遗传操作, 实现个体 一代代地优化并逐渐逼近最优解[ 5, 6] . 鉴于 K 均值 聚类算法具有简单易于改进, 且执行效率相对较高 等优点, 本文综合遗传算法和K 均值聚类算法的优 点, 提出一种改进的基于遗传算法的K 均值聚类算 法. 1 � 改进的基于遗传算法的聚类算法 1�1 � 编 � 码 遗传算法的编码方法主要分为二进制编码、浮 点数编码和符号编码 3类. 由于聚类的数据集数目 一般远大于其聚类中心的数目, 故本文采用基于聚 类中心的浮点数编码,将各个聚类中心编码为个体. 例如,一个类别为3的聚类问题,假设数据集为2维, 初始的 3个聚类中心为( 3, 2)、( 1, 4) 和( 8, 6) , 则个 体编码为( 3, 2, 1, 4, 8, 6) .这种基于聚类中心的编码 方式可以缩短个体的长度,从而提高算法的效率. 1�2 � 随机产生初始种群 初始确定种群大小 m,一般取 20 ~ 100;交叉概 率 Pc ,一般取0. 25 ~ 0. 75;变异概率 Pm ,一般取0. 01 ~ 0. 2.由于初始 K 值选择具有不确定性,存在较 大变数, 所以初始变异概率可以选取大些; 对于聚类 中心数K 值,可在[ 2, n ] ( n为数据集的大小) 内选 取随机产生的整数;最大遗传代数 T , 一般取 100 ~ 500. 1�3 � 采用 K 均值聚类算法对数据进行分类 设大小为 n 的数据集为, { x 1 , x 2 , �, x n} , i = 1,选取K个初始聚类中心Cj ( i ) ,每个聚类中心的数 据大小为 nj , j = 1, 2, �, K .计算每个数据对象与聚 类中心的距离 D ( x i , Cj ( i ) ) , 如果满足 D ( x i , Ck ( i ) ) = min{ D ( x i , Cj ( i ) ) , i = 1, 2, �, n, j = 1, 2, �, K } ,则 x i � Ck ( i ) .同时,计算 k个新的聚类中 心, � Cj ( i + 1) = 1 nj � n j i= 1 x i ( 1) 1�4 � 评价个体适应度值 适应度函数是对个体进行优胜劣汰的主要依 据, 其关系到下一代种群的优良性及数量. 设大小为 收稿日期: 2011 - 04 - 11. 基金项目: 江苏省教育厅高校自然科学研究项目( 08KJB520001) 资助项目. 作者简介: 唐朝霞( 1978 � ) , 女, 硕士, 讲师, 从事计算机算法与程序设计研究. n 的数据集分为K 类,其适应度函数为, f = min�c i - cj � 2 1 k �kj= 1 ( � n i i= 1 �xj - ci �2�nj ) ( 2) 式中, 分子为最小聚类中心间距, 应尽可能大; 分母 为平均聚类中心内距,应尽可能小.适应度函数体现 了聚类中心间距应尽可能松散, 而聚类中心内距应 尽可能紧凑. 1�5 � K 值的自动学习 由于初始的聚类数 K 值并非最佳聚类数, 因此 将种群中具有最大适应度值的个体作为最佳聚类数 的样本,其他个体的长度(即 K 值) 向其学习. 假设 K 值呈增长趋势,可选取数据集中离目前个体中最 大聚类中心距离最远的点加入; 假设 K 值呈减少趋 势,如果种群中任一个体中 2 个聚类中心的间距为 所有聚类中心间距的最小值, 则合并这两个聚类中 心.合并后新的聚类中心为这 2个聚类中心的平均 值.以此根据个体的适应度值实现聚类数 K 值的自 动学习,以显著提高真实聚类结果的可能性. 1�6 � 选 � 择 选择是为了提高算法的全局收敛性和计算效 率,而简单地采用遗传算法容易造成算法的收敛性 较差[ 7] .本文引入差异度的概念, 通过计算聚类中心 之间的差异度值以限制适应度差的个体产生, 即子 个体差异度必须大于原个体的差异度才可以选择进 行遗传操作,从而优化了并提高了算法的效率. 设个体 C j ( i ) = { C1 i , C2 i , �, Cki } ,则个体的 差异度为, � d(Cj ( i)) = a k(k- 1) �kx= 1 � k y= 1 �cxi - cyi�, 0< a < 1 ( 3) 如果个体是一个优质个体, 则其聚类中心之间 的距离较远,其差异度值则较大. 1�7 � 交 � 叉 交叉操作是遗传算法区别于其他算法的重要特 征.交叉是产生新个体的主要方法,并直接影响算法 的全局搜索能力[ 5] . 为保证聚类中心各分量不被分 割,并产生有意义的新个体,本文采用如下算法, 设交叉的两个体为: C1 ( t ) = C11 , C11 �C1K 1 和 C2 ( t ) = C 2 1 , C 2 2 �C2K2 ,在[ 1, K 1- 1] 和[ 1, K 2- 1] 中随机选取整数X 和Y分别作为两父代个体的交叉 位,从而得到两个子个体: C1� ( t ) = C11 , C12 , �, C1X , C 2 X+ 1 �C 2K2 和 C2� ( t ) = C21 , C22 , �, C2Y, C1Y+ 1 , �, C 1 K 1 .通过这种交叉策略, 不仅种群中个体所包含的 聚类中心数目得到动态调整, 而且聚类中心也得到 了重新组合. 1�8 � 基因的自适应变异 变异操作可以增加种群的多样性, 防止�早熟� 现象的发生, 进而增加算法的局部搜索能力[ 8] . 据 此, 本文设计了一种新的变异算法,可进行自适应变 异. 设变异个体的基因 C ij 表示第i个聚类中心第j 维 的值,则变异后个体的基因 Cij� 为, Cij � = Cij + m( C ij ,max � C ij ) , m � 0 Cij + m( C ij � Cij , min) , m < 0 ( 4) 式中, C ij , max 和 C ij , min分别为第 i个聚类中心第j 维的 最 大 和 最 小 值; m 在 [ �( f�f min )�( f max�f min ) , ( f �f min )�( f max�f min ) ] 内均匀分布产生, f 为变异个体 的适应度值, f min和 f max 分别表示当代种群最优和最 差个体的适应度值.这样,最差个体的基因变异值较 大, 最优个体的基因不参与变异, 实现了基因的自适 应变异, 进而加快了算法的收敛速度. 1�9 � 循环终止条件 若连续几代个体平均适应度的差异小于某一极 小的阈值(一个较小的正常数 �) 或遗传代数 ( t = Gmax) ,本算法停止. 2 � 仿真实验结果 为验证本文提出算法的有效性, 下面以数据集 data1(图 1) 为例, 将 K 均值聚类算法、基本遗传聚 类算法和改进的遗传聚类算法分别用Matlab编程进 行仿真实现[ 9] . 3种算法分别运行 100次, 其结果如 图 2(其中 * 表示聚类中心) 和表 1所示. 图 1� data1数据集 图 2 � data1 聚类结果 �163�第 2期 � � � � � � 唐朝霞: 一种改进的基于遗传算法的 K 均值聚类算法 表 1� 3种聚类算法仿真结果 算 � 法 平均迭代次数 聚类正确率 K 均值聚类算法 42 54% 基本遗传聚类算法 39 92% 改进的遗传聚类算法 18 98% 3 � 结 � 语 本文提出的改进的基于遗传算法的 K 均值聚 类算法对基本遗传算法存在收敛性差和容易�早熟� 的缺点进行了改进, 克服了 K 均值聚类算法对初始 聚类中心敏感和容易陷入局部极值的缺点. 仿真实 验表明,在聚类正确率和平均运行时间方面, 改进的 遗传聚类算法明显优于 K 均值聚类算法和基本遗 传聚类算法. 参考文献: [ 1] Bagheri E, Deldari H. Dejong Function Optimization by Means of a Parallel Approach to Fuzzif ied Genetic Algorithm [ C]��11th IEEE Symposium on Computers and Communications ( ISCC � 06) . Cagliari, Italy: IEEE Press, 2006: 675- 680. [ 2]丁泽进, 于剑. 聚类分析技术 [ M ] . 北京: 清华大学出版 社, 2006. [ 3]傅景广,许刚, 王裕国. 基于遗传算法的聚类分析[ J] . 计 算机工程, 2004, 30( 4) : 122- 125. [ 4]陆林花,王波. 一种改进的遗传聚类算法[ J] .计算机工程 与应用, 2007, 43( 21) : 170- 172. [ 5]周洪伟,原锦辉,张来顺. 遗传算法� 早熟�现象的改进策 略[ J] .计算机工程, 2007, 33( 19) : 201- 205. [ 6] Bezdek J C. Pattern Recognition with Fuzzy Objective Funcion Al� gorithms [ M] . New York: Plenum Press, 1981. [ 7]张伟,廖晓峰 ,吴中福.一种基于遗传算法的聚类新方法 [ J] . 计算机科学, 2002, 29( 6) : 114- 116. [ 8] Hall L O, Ozyurt I B, Bezdek J C. Clustering with a Genetically Optimized Approach[ J] . IEEE Transactions on Evolutionary Com� putation, 1999, 3( 2) : 103- 112. [ 9]雷英杰,张善文, 李继武. Matlab 遗传算法工具箱及应用 [ M] . 西安:西安电子科技大学出版社, 2005. K�means Clustering Algorithm Based on Improved Genetic Algorithm TANG Zhaoxia (School of Computer Engineering, Huaiyin Inst itute of Technology, Huaan 223003, China) Abstract: Based on advantages of K�means clustering algorithm and genetic algorithm, an improved genet ic clustering algorithm was proposed. Encoding method, initialization, fitness function, selection, crossover and mutation of genet ic algorithms were better applied to the clustering problem, which not only can solve the problems that K value is difficult to determine, sensitive to init ial value in K�means clustering algorithm and that genetic algorithm has poor convergence and is easy to be precocious and other shortcomings in ge� netic algorithm, but also can achieve the optimal choice of clustering centers, automatic learning of K value and adaptive variation of genes. Simulated experiments� results show that clustering algorithm efficiency has great improvement. Key words: clustering analysis; genetic algorithm; K�means �164� � � � � � � � � � � � � � � � 成都大学学报(自然科学版) � � � � � � � � � � � � 第 30卷