基于浓缩差别矩阵的不完备信息系统的规则获取算法研究

发布时间：2017-09-15 08:44

  本文关键词：基于浓缩差别矩阵的不完备信息系统的规则获取算法研究

  更多相关文章： 属性约简 规则获取 浓缩差别矩阵 二叉树 布尔冲突矩阵

【摘要】：随着科学技术的发展、网络的普及,大量的信息都得以保存,人们想要快速的搜索到自己需要的信息变得更加困难。粗糙集理论作为一种较新的软计算方法,目前在国际上仍然是人工智能理论及其应用领域中的研究热点之一,由于它是在模糊集、概率论及证据理论之后出现的又一个处理不确定性的数学工具,且其能够有效的在许多科学与工程领域中得以应用,所以,越来越受到人们的重视。粗糙集理论起初主要研究对象是针对完备信息系统的,然而现实生活中的数据可能是遗漏型或缺省型的,传统的粗糙集理论就不能够再像原来一样处理这类信息系统了。怎样利用粗糙集理论来处理这类信息系统成为了国内外学者和专家的研究热点,他们最先想到两种办法来解决这类问题,一种是将完备信息系统中的等价关系理论延伸到不完备信息系统中去,因而产生了容差关系和相似关系等扩展模型；另一种则是通过将不完备信息系统的空缺值补充起来,使它成为完备的信息系统,然后再来处理。规则获取是粗糙集理论的一项重要研究内容,它主要包含属性约简及属性值约简。属性约简的目的是为了尽量化简原始数据,且不会改变原始数据背后的隐藏规则及数据之问的关系。且属性约简的结果也是为了能够更好的进行属性值约简,达到规则获取的目的。因而,研究粗糙集理论的多种扩展模型和知识获取方法在不完备信息系统中有着极其重要的理论与现实意义。本文在前人研究的基础之上对粗糙集理论中的属性约简以及规则获取方面进行了研究学习,主要进行了下面三个方面的研究：(1)差别矩阵方法因简单方便,被许多学者使用。然而,对于现实中所面对的海量数据,传统的差别矩阵方法不仅费时且占用空间大而使得效率不高。有学者使用元素之间相互比较的方法来构造浓缩差别矩阵的算法,其算法时间复杂度达到O(|C‖U|4),因此,并不适合用来处理大数据。也有研究者将差别元素压缩存储到FP树上,减少了存储的空间,但却并没能够去掉那些无用的元素,为此,我们设计一种改进算法,引入二叉树的思想,循环采用短差别元素建立二义树,长差别元素依次查找比较的方法,然后在此基础之上,引入了扩展的二进制差别矩阵,并直接从矩阵中提取规则,使得新算法的时间复杂度降到了max{O(|C‖U|2),O(|C|2|Upos‖U|)}。实验证明,设计的浓缩差别矩阵的规则获取算法是高效可行的。(2)由于大型决策表求解差别矩阵时费时且需要用到大量的存储空间,使得属性约简算法的效率不高。为了不仅能降低差别矩阵的存储空间，还能运用到差别矩阵的思想,引入了区分对象对集的思想,以知识粒度为启发信息,引入分布计数排序法求容差类,并结合冲突域的思想,使得算法时空复杂度分别降到了max{O(|C‖U|),O(|C‖U|α|2}(a∈C)及max{O(|U|),O(|U|α|2)}(a∈C)。最后实验证明该算法是一种高效可行的属性约简算法。(3)为了降低属性约简算法的复杂度,在布尔冲突矩阵的基础上,定义了一个启发函数,该函数能求出决策表中条件属性导致的冲突个数,同时给出了计算该启发函数的快速算法。然后用该启发函数设计了一个有效的关于不完备决策表的改进的布尔冲突矩阵的高效属性约简算法,该算法将时间复杂度降到了D(|K‖C‖U|)(|K|=,max{|Tp(xi)‖xi∈U})。最后实验结果说明了新算法的有效性。
【关键词】：属性约简 规则获取 浓缩差别矩阵 二叉树 布尔冲突矩阵
【学位授予单位】：广西师范大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP18
【目录】：

• 摘要3-5
• Abstract5-9
• 第1章 绪论9-14
• 1.1 论文研究背景9-10
• 1.2 粗糙集理论概述10-12
• 1.2.1 粗糙集理论的产生与发展10-11
• 1.2.2 粗糙集理论应用研究现状11-12
• 1.3 论文的研究意义和目的12
• 1.4 论文的主要创新点12-13
• 1.5 论文的构造情况13-14
• 第2章 粗糙集理论的基本概念14-22
• 2.1 知识的分类和表示14-15
• 2.2 决策表相关的概念15-17
• 2.2.1 完备决策表的相关定义15-16
• 2.2.2 不完备决策表的相关定义16-17
• 2.3 完备决策表的属性约简的相关定义17-19
• 2.3.1 基于正区域模型的相关定义17-18
• 2.3.2 基于差别矩阵模型的相关定义18
• 2.3.3 基于信息熵模型的相关定义18-19
• 2.3.4 基于知识粒度模型的相关定义19
• 2.4 不完备决策系统属性约简相关定义19-21
• 2.4.1 基于正区域模型的相关定义19
• 2.4.2 基于差别矩阵模型的相关定义19-20
• 2.4.3 基于广义决策函数的相关定义20
• 2.4.4 基于知识粒度模型的相关定义20-21
• 2.5 本章小结21-22
• 第3章 基于浓缩差别矩阵的规则获取算法22-36
• 3.1 算法的设计思路22
• 3.2 浓缩差别矩阵属性约简及规则获取的相关定义22-24
• 3.3 基于浓缩差别矩阵的规则获取算法24-29
• 3.4 算法的复杂度分析29
• 3.5 实例验证29-33
• 3.6 实验验证33-35
• 3.7 本章小结35-36
• 第4章 基于冲突域的区分对象对的属性约简算法36-41
• 4.1 算法的设计思路36
• 4.2 基于区分对象对的属性约简相关定义36-37
• 4.3 基于冲突域的区分对象对的属性约简算法37-39
• 4.4 算法的复杂度分析39
• 4.5 实例验证39-40
• 4.6 实验验证40
• 4.7 本章小结40-41
• 第5章 布尔冲突矩阵的高效属性约简算法41-48
• 5.1 算法的设计思路41
• 5.2 布尔冲突矩阵的高效属性约简算法的相关定义41-43
• 5.3 布尔冲突矩阵的高效属性约简算法43-44
• 5.4 算法的复杂度分析44
• 5.5 实例验证44-45
• 5.6 实验验证45-47
• 5.7 本章小结47-48
• 第6章 总结与展望48-50
• 6.1 全文总结48
• 6.2 问题和展望48-50
• 参考文献50-55
• 攻读硕士学位期间科研成果55-56
• 致谢56-57

，

本文编号：855504