并行遗传算法在K-中心数据挖掘的应用研究

摘要

数据挖掘是随着信息技术不断发展而形成的一门新学科.它帮助人们在信息海洋中发现有用的知识和信息.数据挖掘按照其任务主要可以分为4种:聚类、分类、关联规则、序列-模式.其中聚类是最重要的一种.在数据挖掘中,效率和准确性一直是人们所关注的问题.为了提高数据挖掘的准确性和效率,人们将许多的算法应用到数据挖掘当中来.这些算法包括:遗传算法,神经网络,模糊理论,粗糙集理论等等.本论文将并行遗传算法应用到K-中心聚类数据挖掘中,从而来提高K-中心数据挖掘的效率和聚类的准确性.本论文用PVM将PC机组织在一起,构成了一个并行计算环境,所用的操作系统为Linux.并行计算时所选用的模型为粗粒度的主/从模型.在计算过程中,将初始个体分别分配得各台slave机器上,然后slave机就开始计算,在slave机计算到一定的时间以后,依据一定的迁移策略,向master迁移个体,然后再从master机上取回其它机器的个体继续运算,直到满足中止条件为止.最后,对实验得到的数据进行了比较,分析,并得出了相应的加速比.

目录

文摘

英文文摘

1绪论

1.1论文的研究背景及选题的意义

1.2国内外现状综述

1.3论文研究的内容及组织

2数据挖掘与遗传算法技术

2.1数据挖掘技术简介

2.1.1数据挖掘的定义

2.1.2数据挖掘的任务

2.1.3数据挖掘的常用方法

2.1.4数据挖掘的应用

2.2遗传算法与K-中心聚类

2.2.1遗传算法的定义

2.2.2自然进化与遗传算法

2.2.3遗传算法的描述

2.2.4遗传算法的特点

2.2.5遗传算法的基本原理

2.2.6 K-中心聚类数据挖掘

3将并行遗传算法应用于K-中心聚类

3.1引入并行遗传算法的理由

3.1.1引入遗传算法是由遗传算法所固有的并行特性所决定的

3.1.2并行遗传算法有利解决传统遗传算法的早熟现象

3.1.3效率低也是遗传算法的一个缺点

3.2并行遗传算法的模型

3.2.1主从式并行遗传算法

3.2.2细粒度并行遗传算法

3.2.3粗粒度并行遗传算法

3.3将并行遗传算法应用到K-中心数据挖掘中

3.3.1并行遗传算法应用到K-Means中

3.3.2将并行遗传算法应用到K-中心聚类中

3.3.3对K-中心进行编码

3.3.4适度函数的选择

3.3.5遗传操作

3.3.6并行模型

3.3.7迁移策略

4算法的实现及实验结果的分析

4.1 PVM的组成

4.2 PVM的特点

4.3 PVM的编程基础

4.3.1 PVM的编程模型

4.3.2 PVM在两台计算机之间传送数据的过程

4.3.3主要的PVM库函数

4.4算法描述

4.5关于本试验的说明

4.6实验结果分析

4.6.1实验步骤

4.6.2实验结果分析

4.6.3加速比分析

4.6.4实验小结

5论文的总结

5.1论文的主要工作

5.2进一步努力的方向

致 谢

参考文献

附录 作者在攻读硕士学位期间发表的论文

独创性声明及学位论文版权使用授权书