基于简化差别矩阵的属性约简和求核算法研究

论文摘要

粗糙集理论是波兰科学家Palawk教授提出的一种能够对不精确和不完备信息系统进行处理的数学工具。由于粗糙集理论不需要先验知识,而是利用已有数据进行信息处理,因此体现了“用数据说话”的思想。因此作为一种信息处理工具被广泛应用在人工智能,认知科学等领域。属性约简是粗糙集理论的核心内容之一。属性约简是指在保持信息系统分类或决策能力不变的前提下,通过知识约简,导出问题的决策或分类规则。目前,很多学者提出了多种属性约简的算法,这其中有以完备信息系统作为研究对象,也有以不完备信息系统作为研究对象。因此,本文在分析目前多种属性约简算法的基础上,从事了如下研究工作：以完备信息系统作为研究对象。现在对粗糙集的研究主要是针对完备信息系统。所以,基于完备信息系统的粗糙集理论、概念和算法是相对成熟的。因此,首先以完备信息系统作为研究方向。本文研究了基于Skowron差别矩阵的属性约简和基于正区域的属性约简；根据简化决策表的定义和基于正区域的简化差别矩阵,设计一种基于正区域简化差别矩阵中非空元素个数作为启发信息的属性约简新算法；证明该属性约简与正区域属性约简的等价关系,给出计算启发信息的快速计算公式,并以此为基础设计一种基于正区域差别矩阵方法的属性约简算法。由于该属性约简算法以正区域差别矩阵中非空元素的个数作为启发信息,通过对U的划分就能简单得到,因此不必生成相应的差别矩阵,避免了差别矩阵方法计算费时且占用大量存储空间的缺点。粗糙集求解所有的属性约简是一个NP难问题。为研究完备的属性约简算法,设计了一种完备的基于正区域差别矩阵的属性约简算法。该算法利用差别矩阵的思想而又必备生成实际的差别矩阵,从而节约了计算时间和存储空间。因此,该算法的研究重点是启发信息,即属性重要度的定义。针对属性重要度的定义设计了相应的属性重要度计算公式,该计算公式只需要知道Upos和Uneg的划分,就能够计算出相应的启发信息,因此节省了计算时间和存储空间。该算法通过删除不支持决策属性D的条件属性以获得所有的属性约简,其时间复杂度为max{O(|C||U|),O(|C|3|U/C|}。粗糙集理论应用于人工智能的一种方式是基于粗糙集的有效算法研究。为研究粗糙集理论和遗传算法的集成运算,设计了一种快速的粗糙集属性约简遗传算法。该算法结合了粗糙集理论和遗传算法,遗传算法的特点是利用所求问题的适应度值大小确定下一步的搜索方向。由于适应度值是对适应度函数进行计算得到的,所以适应度函数的设计和计算效率直接影响遗传算法的性能。因此为了快速得到属性约简,研究的工作重点是适应度函数的设计和优化。利用区分对象对的性质,算法有效的减少了适应度函数的计算量,并根据启发信息加速算法收敛,得到属性约简。通过实验分析表明,粗糙集属性约简遗传算法是求解属性约简的有效算法,尤其是处理规模较大的决策表。核是指一个决策表中所有属性约简的交集,核主要应用于属性约简算法,通过求出决策表的核,然后再通过启发信息对这个核进行扩展从而得到最小属性约简,核的另一个应用在于多变量决策树的构造。因此,设计高效的求核算法也是我们的研究目标。目前设计的求核算法主要是差别矩阵方法。在该种方法中,是通过搜索差别矩阵的所有差别元素得到核。由于在所有的差别元素上搜索,故该方法比较耗时。为此,在简化决策表和简化差别矩阵的基础上,经研究发现了一种关于核的新现象,即如果将简化决策表中的对象根据它们的属性简化为一个数字时,这些对象是有序的。我们根据这个对象序的性质,只需判断简化差别矩阵中的少量差别元素就可以求出核属性集。在此基础上,设计了一个高效求核算法,其时间复杂度max{O(|C|2|U/C|),O(|C||U|)},其空间复杂度为O(|U|)。由于新算法只判断简化差别矩阵的少量差别元素就可以找到核算属性集,故新算法的效率得到了改善。

论文目录

• 摘要
• Abstract
• 引言
• 1.研究目的
• 2.研究意义
• 3.主要研究内容和创新点
• 4.文章组织
• 1.粗糙集理论概论
• 1.1 粗糙集理论的诞生
• 1.2 粗糙集理论研究和粗糙集应用研究
• 1.3 粗糙集理论的优点
• 1.4 现有的粗糙集软件
• 1.5 本章小节
• 2.粗糙集理论基础
• 2.1 粗糙集基本概念
• 2.1.1 基于正区域的属性约简定义和核定义
• 2.1.2 基于Skowron差别矩阵的属性约简定义和核定义
• 2.1.3 基于信息熵的属性约简定义和核定义
• 2.2 基于简化差别矩阵思想的快速属性约简算法
• 2.2.1 设计思想
• 2.2.2 基本概念及相关定理
• 2.2.3 求简化决策表算法
• 2.2.4 根据启发式信息求属性约简
• 2.2.5 实例分析
• 2.4 本章小结
• 3.完备的属性约简算法研究
• 3.1 设计思想
• 3.2 基本知识和相关工作
• 3.2.1 基本概念
• 3.2.2 相关定理与证明
• 3.3 基于启发信息的完备属性约简算法
• 3.3.1 简化决策表算法CalculBaseComp（U',P）
• ALL)'>3.3.2 启发信息算法CalculElicit(Sig（C）,R,U',R_ALL)
• 3.3.3 基于启发信息的完备属性约简算法SMReduce（U）
• 3.4 实例分析
• 3.5 本章小结
• 4.基于遗传算法的属性约简算法研究
• 4.1 设计思想
• 4.2 基本知识及相关工作
• 4.2.1 基本概念
• 4.2.2 相关定理与证明
• 4.3 属性约简遗传算法
• 4.3.1 求简化决策表
• 4.3.2 属性的编码方法
• 4.3.3 适应度函数的设计
• 4.3.4 修正算法
• 4.3.5 选择、交叉和变异运算
• 0,M,T）'>4.4 快速属性约简遗传算法SRGA（U,C,D,P₀,M,T）
• 4.5 实例分析和性能比较
• 4.5.1 实例分析
• 4.5.2 设计与实验
• 4.6 本章小结
• 5.用序关系求信息熵核的算法研究
• 5.1 设计思想
• 5.2 基本概念和相关工作
• 5.3 简化决策表算法
• 5.4 基于简化差别矩阵的核性质
• 5.5 高效求核算法
• 5.6 分析实例
• 5.7 本章小结
• 6.结论与展望
• 参考文献
• 在学研究成果
• 致谢