基于粗糙集的属性约简算法研究

论文摘要

粗糙集理论是一种新的处理模糊和不确定性知识的数学工具,其主要思想就是在保持分类能力不变的前提下,通过知识约简,导出问题的决策或分类规则。属性约简是粗糙集理论研究的核心内容之一,对于粗糙集理论的应用而言,设计有效地算法是非常重要的。本文基于布尔矩阵和属性重要性设计了两种不同的算法。目前,决策表中有关粗糙集理论中所有的概念与运算一般都是在代数形式下表示的,有关粗糙集的属性约简也都是在这种表示下来研究的。在代数表示下,粗糙集理论的很多概念与运算的直观性较差,且一些启发式算法计算量较大,而且大多是非完备算法。李龙星等教授证明了属性约简在布尔矩阵和代数两种不同表示下是等价的,布尔矩阵表示更加直观且可以减少存储空间。基于此理论本文提出了一种基于布尔矩阵的新的属性约简完备算法,为了保证算法的完备性,在此基础上加了一个反向删除过程,直到不能再删为止,保证了算法的完备性。最后通过实例分析证实了其有效性。在决策表中,属性并不是同等重要的,不同的属性具有不同的重要性,于是就有了研究属性重要性的必要。在目前已有的基于属性重要性的属性约简算法基础上,本文设计了一种基于限制正域和属性重要性的属性约简算法。本文首先将决策表上的属性约简转化到简化的决策表上进行,其次重新定义了限制正域的概念,并得到了限制正域的一些性质。根据限制正域,本文设计了一个以快速缩小搜索空间为目的的新的较合理的属性约简算法,即以属性核为起点,并向核不断添加重要性最大的属性,并用限制正域不断缩小搜索空间,从而降低算法的效率。最后实例分析验证了算法的有效性,并且该算法也满足不一致决策表。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 粗糙集理论的主要思想
• 1.2 国内外研究现状
• 1.3 问题的提出
• 1.4 论文的主要研究工作
• 1.5 论文的组织与结构
• 第二章 粗糙集理论的基础知识
• 2.1 知识与等价关系
• 2.2 上下近似集和正域
• 2.3 知识表达系统和决策表
• 2.4 属性约简和核
• 2.5 属性重要性
• 2.6 可辨识矩阵
• 2.7 小结
• 第三章 一种基于布尔矩阵的新的属性约简完备算法
• 3.1 引言
• 3.2 基于布尔矩阵的基本概念与定理
• 3.2.1 布尔矩阵的构造
• 3.2.2 基于布尔矩阵的基本定理
• 3.3 基于布尔矩阵的属性约简算法
• 3.3.1 算法的改进
• 3.3.2 算法的实现
• 3.3.3 算法复杂度分析
• 3.4 实例分析
• 3.5 结束语
• 3.6 结论
• 第四章 一种基于限制正域和重要性的属性约简算法
• 4.1 前言
• 4.2 限制正域的基本概念及定理
• 4.2.1 限制正域的基本概念
• 4.2.2 限制正域的定理
• 4.3 基于限制正域的属性约简算法
• 4.3.1 算法的分析
• 4.3.2 算法的实现
• 4.3.3 算法复杂度分析
• 4.4 实例分析
• 4.5 结束语
• 4.6 结论
• 第五章 总结与展望
• 5.1 工作总结
• 5.2 进一步的研究工作
• 参考文献
• 致谢
• 附录A （攻读硕士学位期间发表论文情况）