基于遗传算法的聚类分析及编程实现

论文编号:XXLW036论文字数:11814,页数:27

摘 要

聚类分析目前应用广泛，已经成为数据挖掘中的主要研究领域。通过聚类，人们可以识别密集的和稀疏的区域，从而发现数据的整体分布模式，还能找到数据间有趣的相关联系。本文主要讨论的是一种基于遗传算法的K均值聚类。该算法采用自然数编码方式，取聚类中的欧氏距离的平方为目标函数，对初始群体进行遗传操作。分别应用SAS及VC编程来实现传统的K均值聚类算法和遗传K均值聚类算法，最后通过数据结果的对比可以得出：遗传K均值聚类算法具有较强的全局收敛能力和全局寻优能力。该算法兼顾了局部收敛和全局收敛性能，在兼顾局部收敛速度的同时寻找到的聚类中心保持了良好的全局分布特性。

关键词：遗传算法 K均值聚类 遗传K均值算法

At present,Wider application of cluster analysis has become the main research areas in data mining.Through clustering,people can identify intensive and sparse region,thus can found the overall pattern of data, can also find an interesting correlation between the data link.This paper proposes a K-Meams clustering method based on genetic algorithm. The inital groups is operated by the algorithm which is using natural number coding,and the objective function is got from the square of Euclidean distance. The traditional K-Means method and the K-Meams clustering method based on genetic algorithm will be realized by using the tools:SAS and VC. Finally,based on the results of the comparison of data,we proves that this new method achieves a better result than a K-Meams.The spatial clustering algorithm can give attention to local constringency and the whole constringency.By the local constringency,the cluster center which wo find can maintained the good overall situation distributed characteristic.

Keywords:Genetic algorithm K-Means clustering Genetic K-Means algorithm

目录

中文摘要i

Abstract．ii

目录iii

第一章 前言．1

第二章 遗传算法．2

2.1遗传算法的基本思想．2

2.2染色体编码方法．2

2.2.1自然数编码2

2.3适应度函数．2

2.4遗传算子．3

2.4.1选择算子3

2.4.2交叉算子4

2.4.3变异算子5

2.5控制参数的选择．5

第三章 K均值算法6

3.1算法计算步骤．6

3.2实例应用．7

第四章 利用遗传算法实现聚类．9

4.1问题的描述9

4.2编码与适应度函数．9

4.3初始群体的生成9

4.4遗传算子10

4.5算法实现步骤11

4.6算法的收敛性11

4.7实例应用12

第五章 结论14

致谢15

参考文献．16

附录17