基于粗糙集的约简优化计算方法研究

论文摘要

粗糙集理论是一种处理含糊和不确定性信息的新型数学工具,其理论提出以来得到迅速的发展和广泛的应用。知识约简是粗糙集理论重要研究内容之一,它的主要目的在于去除数据中的冗余信息,同时保持原决策信息系统的分类能力不变。针对大量或海量数据,原有约简方法效率低,须对粗糙集约简计算理论进行优化,发展完善相关计算算法,以提高知识约简的效率。本文基于粗糙集理论,针对知识约简优化计算问题进行了较为深入的研究。对粗糙集理论三种知识约简方法进行比较,分析各类方法的优缺点以及它们之间的相互关系。通过改进原有差别矩阵,在对象比较过程中一次性提取核与用于求约简的所有分辨信息,并保证分辨信息之间不存在包含关系。在此分辨信息基础上以属性频度为启发式信息给出了一种基于改进差别矩阵的启发式约简及增量式更新方法。理论分析与实验仿真表明,新启发式算法产生约简与分辨函数思想产生的最优约简一致,说明算法的有效性。深入研究约简算法完备性理论,指出现有知识约简算法的不完备性,对本文的新启发式约简算法的完备性给出的了充分的证明。其次,在Pawlak知识约简定义下,证明了任意决策信息系统约简个数是条件属性的组合函数。利用已证明的重要性质提出一种非指数级的所有约简计算方法,低于所有相关文献算法的时间复杂度。该结论有助于改进知识约简的效率,进一步提高粗糙集数据分析能力。

论文目录

• 摘要
• ABSTRACT
• 目录
• 第一章 绪论
• 1.1 引言
• 1.2 国内外研究现状
• 1.3 本文主要研究内容
• 1.4 本文结构组织
• 1.5 本章小结
• 第二章 粗糙集理论
• 2.1 集合与关系
• 2.2 知识与分类
• 2.3 信息系统和上、下近似
• 2.4 知识约简
• 2.4.1 代数观约简
• 2.4.2 信息观约简
• 2.4.3 差别矩阵约简
• 2.5 知识约简比较分析
• 2.5.1 代数观点和信息论观点比较分析
• 2.5.2 代数观点和差别矩阵观点比较分析
• 2.6 本章小结
• 第三章 基于差别矩阵的知识约简
• 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.3.4 实例分析
• 3.4 改进差别矩阵增量式约简
• 3.4.1 增量式更新基本概念
• 3.4.2 分辨信息集更新
• 3.4.3 约简增量式更新
• 3.5 实验仿真分析
• 3.6 本章小结
• 第四章 约简完备性分析
• 4.1 约简完备性定义
• 4.2 已有知识约简算法不完备性分析
• 4.3 基于改进差别矩阵的所有约简分析
• 4.3.1 基于改进差别矩阵的所有约简算法
• 4.3.2 算法复杂性分析
• 4.3.3 实例分析
• 4.4 算法ARIDM与AARIDM完备性分析
• 4.5 实验仿真分析
• 4.5.1 理论分析对比
• 4.5.2 实验分析对比
• 4.6 本章小结
• 第五章 研究工作总结与展望
• 5.1 研究工作总结
• 5.2 研究工作展望
• 参考文献
• 致谢
• 攻读学位期间主要研究成果目录