基于改进启发式遗传算法的属性约简方法

论文摘要

粗糙集理论是在上世纪八十年代由波兰数学家Pawlak提出的一种处理模糊和不确定问题的数学理论。它能够分析出隐藏在数据中的事实,而且不需要提供任何关于数据的附加信息。粗糙集理论已经在许多领域获得了成功的应用,例如知识发现、模式识别、决策分析、机器学习等领域。信息系统的属性约简是粗糙集理论的核心内容之一。寻找信息系统的最优约简或全部约简是NP-Hard问题,而基于属性重要性的启发式算法能够相对快速地计算出信息系统的约简。为了获得决策系统中属性的极小相对约简,本文将决策表中相对于每个条件属性的集合和划分的粗糙逼近精度作为衡量属性重要程度的准则,并以此作为启发式信息引入遗传算法,提出了一种在优化初始种群的基础上提高算法性能的启发式遗传算法。通过构造一个修正算子并将其引入启发式信息,以保证被选择的属性子集的分类能力不变。该算子利用启发式信息的局部搜索技术,使得算法既保持了整体的优化特性,又具有较快的收敛速度。最后的实例证明,该算法能有效地对决策系统进行约简。

论文目录

• 摘要
• Abstract
• 绪论
• 第一章 粗糙集理论
• 1.1 集合与等价关系
• 1.2 粗糙集的基本理论
• 1.3 粗糙集模型的扩展
• 1.3.1 可变精度模型
• 1.3.2 相容关系模型
• 1.3.3 概率粗糙集模型
• 1.3.4 模糊粗糙集模型
• 1.4 粗糙集与其他方法的关系
• 本章小结
• 第二章 信息系统及其属性约简
• 2.1 知识与知识库
• 2.1.1 知识的定义
• 2.1.2 不可分辨关系
• 2.2 信息系统和决策表
• 2.3 信息系统的属性约简概念
• 2.3.1 约简与核
• 2.3.2 相对约简与相对核
• 2.4 信息系统的属性约简算法
• 2.4.1 基本约简算法
• 2.4.2 基于区分矩阵的一般算法
• 2.4.3 基于信息熵的约简算法
• 2.4.4 基于遗传算法的约简算法
• 本章小结
• 第三章 遗传算法理论
• 3.1 遗传算法的发展和研究现状
• 3.2 遗传算法的基本概念
• 3.3 遗传算法的编码方式
• 3.4 基本遗传算法
• 3.4.1 基本遗传算法的构成要素
• 3.4.2 基本遗传算法流程
• 3.4.3 基本遗传算法的实现
• 本章小结
• 第四章 基于改进启发式遗传算法的属性约简方法
• 4.1 问题提出
• 4.2 基于粗糙逼近精度的属性重要性
• 4.2.1 粗糙逼近精度
• 4.2.2 属性重要程度
• 4.3 基于改进启发式遗传算法的属性约简算法描述
• 4.3.1 理论基础
• 4.3.2 算法框架描述
• 4.4 算法实现技术分析
• 4.4.1 初始群体设置
• 4.4.2 编码
• 4.4.3 适应度函数的确定
• 4.4.4 选择算子
• 4.4.5 交叉变异
• 4.4.6 修正算子
• 4.4.7 算法终止规则
• 4.5 算法分析
• 4.6 算法实现与应用实例
• 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间发表的学术论文
• 致谢