基于并行遗传算法的K-means聚类研究  

Research of K-means Clustering Method Based on Parallel Genetic Algorithm

作　　者：戴文华[1] 焦翠珍[1] 何婷婷[2] 

机构地区：[1]咸宁学院计算机系,湖北咸宁437100 [2]华中师范大学计算机科学系,武汉430079

出　　处：《计算机科学》2008年第6期171-174,共4页Computer Science

基　　金：国家自然科学基金(No60442005,No60673040);国家社会科学基金(No06BYY029);教育部重点研究项目(No105117);湖北省教育厅科(NoD200728002)

摘　　要：针对传统K-means聚类算法对初始聚类中心的选择敏感,以及聚类数K难以确定的问题,提出一种基于并行遗传算法的K-means聚类方法。该方法采用一种新型的可变长染色体编码方案,随机选择样本点作为初始聚类中心形成染色体,然后结合K-means算法的高效性和并行遗传算法的全局优化能力,通过种群内的遗传、变异和种群间的并行进化、联姻,有效地避免了局部最优解的出现,同时得到了优化的聚类数目和聚类结果。实验表明该方法是一种精确高效的聚类方法。As K-means Clustering Algorithm is sensitive to the choice of the initial cluster centers and it＇s difficult to determine the cluster number, we propose a K-means Clustering Method Based on Parallel Genetic Algorithm. In the method, we adopt a new strategy of Variable-Length Chromosome Encoding and randomly chose initial clustering centers to form chromosomes among samples. Combining the efficiency of K-means Algorithm with the global optimization ability of Parallel Genetic Algorithm, the local optimal solution is avoided and the optimum number and optimum result of cluster are obtained by means of heredity, mutation in the community, and parallel evolution, intermarriage among communities. Experiments indicated that this algorithm is efficient and accurate.

关 键 词：并行遗传算法 可变长染色体编码 K-MEANS算法 聚类 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] O242.23[自动化与计算机技术—计算机科学与技术]