遗传算法及其在分类规则挖掘中的应用研究

摘要

随着互联网技术的快速发展,信息的增长速度呈指数上升,传统的分析方法已远远不能满足现实的需求。面对海量数据,如何从中发现有价值的信息,数据挖掘技术为满足这一需求而产生。分类规则挖掘是数据挖掘的一个重要分支,许多研究人员将基本遗传算法应用于分类规则挖掘中,总存在着早熟收敛的问题。因此,如何改善遗传算法的早熟收敛现象,提高分类规则挖掘的效率,是一个具有重要价值的研究课题。
　　 要解决早熟收敛问题,关键是保持种群的多样性。为了有效地解决上述问题,提高分类规则挖掘的效率和准确性,本文对基本遗传算法做了改进,并提出一种双种群和双变异的改进遗传算法,将它们应用到分类规则挖掘中。本文的主要工作如下:
　　 首先,对遗传算法的三大算子进行改进。改进的选择算子将个体按适应值大小升序排列,将排在前面三分之二的个体进行等概率选择,排在后面三分之一的个体进行比例选择,可保持种群的多样性。改进的交叉算子根据个体相似度与设定阈值的比较结果,按一定的概率执行单点交叉或均匀交叉,可提高算法的搜索能力。改进的变异算子使群体中个体变异概率自适应调节,且保证群体中表现优良性状的个体变异概率不为零,保持群体不断进化,加速算法的收敛。实验结果表明,改进的算法保持了种群的多样性,明显改善了早熟现象,挖掘出质量更好的分类规则。
　　 其次,提出了一种双种群和双变异的改进遗传算法。该算法的初始群体有两个,初始群体产生时,对初始群体按适应值大小排序,将其中一半优秀的个体放入群体2中,另一半放入群体1中。然后,对群体1中的个体实行双变异操作,对群体2中的个体实行单变异操作。执行完一轮遗传操作后,若群体1中的个体比群体2中的个体优秀,则将其替换群体2中的个体。实验结果表明,该算法消除了基本遗传算法在分类规则挖掘中收敛于局部最优的局限性,能快速地获得更准确的分类规则。

目录

文摘

英文文摘

论文说明:图表目录

第1章 绪论

1.1 课题研究背景及意义

1.2 国内外研究现状

1.3 本文研究内容

1.4 本文组织结构

第2章 数据挖掘和遗传算法概述

2.1 引言

2.2 数据挖掘的相关理论

2.2.1 数据挖掘的概念

2.2.2 数据挖掘的基本过程

2.2.3 数据挖掘的分类

2.3 分类数据挖掘

2.3.1 分类数据挖掘简介

2.3.2 分类数据挖掘的常用方法

2.4 遗传算法的相关理论

2.4.1 遗传算法的概念

2.4.2 遗传算法的特点

2.4.3 基本遗传算法描述

2.4.4 遗传算法操作设计

2.5 本章小结

第3章 基本遗传算法的改进及应用

3.1 引言

3.2 遗传算法在分类规则挖掘中存在的问题及解决方法

3.2.1 存在问题

3.2.2 早熟现象的原因

3.2.3 早熟现象的解决方法

3.3 遗传算法的改进

3.3.1 选择算子的改进

3.3.2 交叉算子的改进

3.3.3 变异算子的改进

3.4 遗传算法应用于分类规则挖掘的步骤

3.5 改进算法应用于分类规则挖掘

3.5.1 编码方式

3.5.2 适应度函数设计

3.5.3 算法提取分类规则的流程

3.6 实验

3.6.1 实验数据和测试环境

3.6.2 算法参数设置

3.6.3 实验结果分析和比较

3.7 本章小结

第4章 双种群和双变异遗传算法的改进及应用

4.1 引言

4.2 双种群和双变异的改进遗传算法简介

4.3 双种群和双变异的改进遗传算法的具体实现

4.3.1 改进算法的基本思想

4.3.2 改进算法流程

4.4 双种群和双变异的改进遗传算法应用于分类规则挖掘

4.4.1 编码方式

4.4.2 适应度函数设计

4.4.3 算法提取分类规则的流程

4.5 实验

4.5.1 实验数据和测试环境

4.5.2 算法参数设置

4.5.3 实验结果分析和比较

4.6 本章小结

结论

参考文献

致谢

附录A 攻读硕士学位期间发表的论文目录