基于差分演化算法的粗糙集离散化及属性约简的研究

论文摘要

当前,数据挖掘已广泛应用于金融、制造和医疗等领域。但随着知识库的信息量急剧增加,人类迫切需要一类工具能从数据量大、冗余多,且存在噪声数据干扰的知识库中提取潜在有价值的规则。由于粗糙集在这些方面具有优良性能,其已越来越多地应用于数据挖掘。实际应用的知识库存在大量连续数据,而以等价关系为核心的粗糙集只能处理离散数据。因此,在利用粗糙集方法（如属性约简）处理连续数据之前必须将其离散化。本文分析比较了各无监督离散化方法和有监督离散化方法的优缺点,针对最优离散化是一个NP-hard问题的性质,提出了一种启发式离散化方法——基于差分演化算法的离散化算法。该算法采用实数串表示个体,增强了对局部最优点的搜索能力,并在此基础上给出了二值个体和一种适应值函数的定义形式,其中二值个体的定义形式上因条件属性而异设置不同的阈值,适应值函数考虑到了粗糙集理论的特殊性。最后通过Iris数据集的测试实验,验证了该算法是有效的。知识库的各属性的重要性并不是等同的,在确保不改变知识库的分类能力的前提下,可以删除其中冗余的或者重要性较低的属性。本文探讨了属性约简的启发式算法,缘于最小属性约简的求解是一个NP-hard问题,并提出了一种基于差分演化算法的属性约简算法,分别讨论了其在相容决策表和不相容决策表中的约简情况,进而引出了一种新的适应值函数定义形式和一种新的差分操作使变异向最小属性约简相应的个体进化。最后通过两组实验证明该算法是有效的,它的计算复杂度与基于遗传算法的属性约简的计算复杂度相当,但它的收敛速度是基于遗传算法的4倍。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 引言
• 1.2 国内外研究现状
• 1.2.1 粗糙集理论及算法的研究
• 1.2.2 基于粗糙集的应用
• 1.3 论文组织结构
• 第二章 粗糙集、离散化及差分演化算法的基本理论
• 2.1 粗糙集的基本理论
• 2.1.1 粗糙集的基本定义
• 2.1.2 属性约简
• 2.2 离散化的基本概念
• 2.3 差分演化算法
• 2.4 本章小结
• 第三章 粗糙集的离散化方法
• 3.1 连续属性离散化方法
• 3.1.1 无监督离散化方法
• 3.1.2 有监督离散化方法
• 3.2 基于差分演化算法的连续属性离散化算法
• 3.2.1 DBODE 算法的基本操作过程
• 3.2.2 DBODE 算法的流程
• 3.3 实验与结果
• 3.4 本章小结
• 第四章 一种基于差分演化算法的属性约简
• 4.1 基于差分演化算法的属性约简算法
• 4.1.1 改进的差分演化算法操作过程
• 4.1.2 算法的执行过程
• 4.2 相容决策表的属性约简
• 4.2.1 实验与结果
• 4.2.2 小结
• 4.3 不相容决策表的属性约简
• 4.3.1 引言
• 4.3.2 进一步改进差分演化算法的操作过程
• 4.4 算法可行性及计算复杂度分析
• 4.5 本章小结
• 第五章 结论与展望
• 参考文献
• 致谢
• 附录（攻读硕士学位期间发表录用论文）
• 中英文摘要