（毕业设计论文）《基于K-均值遗传算法的聚类程序》 (2).doc

本科毕业设计（论文） 题目：基于K-均值遗传算法的聚类程序 学 院 软件学院 专 业 软件工程 学生姓名 学生学号 指导教师 提交日期 2012 年 月 日  摘 要 在这篇论文里，我们先介绍遗传算法的原理以及特点，然后介绍遗传算法的现今的发展状况。之后我们介绍在数据挖掘方面的发展和前景，最后，介绍遗传算法在数据挖掘方面的应用。 我们提出一个能够把一个给定的数据整体上理想的划分成指定数目的簇的新颖的混合遗传算法。在聚类方面，GA早期要么用于从父染色体中生成子染色体的昂贵的交叉算子，要么用于昂贵的适应度函数 之后我们会介绍这个混合算法的C++实现，介绍程序用到的类和类内部的成员参数和成员函数。介绍一下世界各国物价水平数据，最后我们用程序对世界各国物价水平 进行聚类分析，检查程序的实用性和性能，最后根据结果得出结论。 关键词：数据挖掘，聚类，遗传算法， K均值算法，整体最优解。 Abstract We firstly introduced?the principle and feature?of?genetic algorithm,?and then describe?the?present state of development?of?the?genetic algorithm. We introduce?the?data mining?developments and?prospects, and finally?to introduce the application of the genetic?algorithm in data mining. We propose a novel hybrid genetic algorithm that finds a globally optimal partition of a given data into a specified number of clusters. GA’s used earlier in clustering employ either an expensive crossover operator to generate valid child chromosomes from parent chromosomes or a costly fitness function or both. To circumvent these expensive operations, we hybridize GA with a classical gradient descent algorithm used in clustering viz., K-means algorithm. Hence, the name is genetic K-means algorithm (GKA). We define K-means operator, one-step of K-means algorithm, and use it in GKA as a search operator instead of crossover. We also define a biased mutation operator specific to clustering which base on distance. Using finite Markov chain theory, we prove that the GKA converges to the global optimum. Then we will introduce the implementation of this hybrid algorithm in C++ and the class of parameter members and member functions in this program. And then we will introduce the data of the world price level data. Finally we use this program on the data to clustering analysis. Check the usability and performance of the program, and