基于遗传编程的数据挖掘分类和聚类算法的研究与实践

论文摘要

随着人们生产和搜集数据的能力大幅度提高,迫切需要找到从现有数据库系统/广域网的大量数据中提取知识的手段。然而,目前人们分析数据、获取知识的能力还不能与现有的组织、存储和操作数据的技术相媲美。为了解决这个问题,产生了基于数据库与数据仓库系统的数据挖掘方法与技术。数据挖掘可以看作是信息技术自然演化的结果,从数据收集和数据库的创建,到数据管理,再到高级数据分析。分类和聚类是数据挖掘的两个重要过程,针对这两个过程,人们已经提出了许多算法,如:贝叶斯分类、基于规则的分类、关联分类、k均值聚类、层次聚类等。这些传统的方法中普遍对用户的相关领域知识有一定的要求,用户对参数的输入很大程度上影响了算法的结果。为了改进这个问题,使数据挖掘任务能够自动的进行,人们提出了基于进化算法的数据挖掘算法。遗传编程是进化算法的一个分支,其主要思想来源于生物的进化。NilsAall Baricelli在1954年首先提出了遗传编程。1980年,Stephen F.Smith发表了关于遗传编程的实验结果。Nichael L.Cramer和Jurgen Schmidhuber分别于1985年和1987年发表论文提出了现代进化编程。John R.Koza对遗传编程作出了重要的拓展,并在1992年发表论文指出,遗传编程应该被视为遗传算法的一个分支而不是特例,John R.Koza被认为是遗传编程的先驱。文中介绍了数据挖掘中分类和聚类的相关算法,并针对这些算法作了系统的分析,指出了这些算法的优势和不足。同时,文中对遗传编程进行了讨论,详细地阐述了遗传编程的相关理论、方法以及技术。在此基础上提出了基于遗传编程的分类与聚类算法。在分类算法中,一个簇用一个逻辑公式表示,这个逻辑公式则由谓词构成。每一个遗传编程个体则将该逻辑公式编码为树形结构。本文提出的聚类算法基于层次聚类的思想,首先将数据集划分为若干个簇,然后对簇进行合并。但是层次聚类的一个缺点是一旦某一部做出决定,那么以后就不能更改。这导致了聚类结果有很大的偶然性。同时,一开始划分的若干个簇并不一定合适。因此,引入遗传变程。将一种聚类方案表示为一个个体,对若干个个体进行评估后,进行一系列遗传操作,产生下一代个体。经过数代,最终得出聚类方案。同时,文中对数据进行了实验,将实验结果与传统的聚类算法相比较,验证了基于遗传编程的数据分类和聚类算法在结果上相对于传统算法有较大的提升。最后,文中提出了该思想存在的不足和进一步改进的方向。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景和立项意义
• 1.2 国内外研究现状
• 1.3 论文主要研究内容
• 1.4 论文框架与组织结构
• 第2章 相关的理论、方法与技术
• 2.1 数据挖掘技术概述
• 2.2 数据挖掘技术中分类/聚类过程的经典算法
• 2.2.1 数据挖掘分类算法
• 2.2.2 数据聚类算法
• 2.3 遗传编程方法
• 2.3.1 遗传编程的概述
• 2.3.2 标准遗传编程方法
• 2.4 本章小结
• 第3章 基于遗传编程的数据挖掘技术
• 3.1 基于遗传编程的数据挖掘技术的研讨
• 3.2 本文所研究的基于遗传编程的数据挖掘技术
• 3.2.1 基于遗传编程的数据分类算法
• 3.2.2 基于遗传编程的数据聚类算法
• 3.3 本章小结
• 第4章 基于遗传编程的数据挖掘技术的数据分类和聚类算法的实现过程
• 4.1 该实现平台的类层次结构
• 4.2 该实现平台的实现过程
• 4.3 数据分类算法的实现与评估
• 4.3.1 数据分类算法的实现
• 4.3.2 实验结果评估
• 4.4 聚类算法的实现与评估
• 4.4.1 聚类算法的实现
• 4.4.2 实验结果评估
• 4.5 本章小结
• 第5章 总结与展望
• 5.1 本文总结
• 5.2 工作展望
• 参考文献
• 附录1 主要代码
• 附录2 作者攻读硕士学位期间发表的论文
• 致谢