基于浓缩差别矩阵的不完备信息系统的属性约简算法研究

摘要

如何从海量数据中提取最有用的信息，对当今的网络架构和数据处理能力来说是一个大的挑战。Rough Sets理论作为当今数据处理中比较新颖的软计算方法，有效性在众多科学与工程领域得到证实之后，继概率论、模糊集及证据理论之后的又一个处理不确定性的数学工具，越来越受世人重视。
　　属性约简是Rough Sets理论的核心问题之一，它是在不影响信息系统分类能力的情况基础上，消除冗余数据，提取知识库中未知的、隐含的简洁的知识，即用最少的属性组合揭示其潜在的有价值的信息。属性的组合爆炸是使属性约简的求解成为一个NP难问题得最主要原因。随着大数据时代的到来及数据库技术的迅速发展，科研机构、政府单位、企业等各大领域数据呈指数递增且这些大数据杂乱无章，也存在很多的强干扰的数据。如此的海量数据对人类处理数据、分析数据能力是一个大挑战，至今属性约简的求解仍然没有一个高效可行的方法，因此求解高效的属性约简算法仍是Rough Sets理论的研究热点。
　　在很多现实情况下，因人类思维的局限性对外界环境不能做出完整、准确的判断、数据采集技术有限、传输媒体故障、及时间因素的影响（比如，医院的诊断系统，对于病员对象集合，病人的一些临床检验结果属性值，在给定的时间里是不可能拿到所有的检验结果的），数据采集过程中数据丢失或数据的可信度降低，不完整的数据信息会造成数据失真，得到的知识规则也不可靠，不可靠的只是规则干扰人们做出正确的决策。基于传统的不分明关系的Rough Sets理论只能处理所有属性值已知且确定的完备信息系统，不能处理一些数据缺失的不完备信息系统。因此在不完备信息系统中研究各种Rough集理论的扩展模型及其知识获取方法有着极其重要的理论与现实意义。
　　本文基于Rough Sets理论及差别矩阵的方法研究不完备信息系统属性约简方法，主要研究工作有以下几个方面:
　　(1)以不完备决策表为研究对象，引入浓缩差别矩阵的概念，采用布尔与思想，给出了不完备信息系统下基于布尔与的浓缩差别矩阵属性约简算法。最后通过一个实例验证了浓缩差别矩阵在属性约简算法中的优越性，且通过UCI实验证明了浓缩差别矩阵的使用价值。
　　(2)差别矩阵方法易懂，易设计被广大学者接受并使用。然而，对于大型数据而言，计算差别矩阵时不仅费时，而且会占用大量的存储空间，使得算法的效率不高。有学者利用差别元素间两两比较的方法构造浓缩差别矩阵的算法，设计的算法时间复杂度为O(|C‖U|4)，由于时间复杂度过高，不适用大数据的处理。还有一些学者将差别元素压缩存储在一棵FP树上，虽然减少了存储空间，但并没有去掉那些无用的元素，为此，我们设计了一种改进的基于二叉树的不完备浓缩差别矩阵属性约简算法算法，采用短差别集插入长差别集依次比较查找的方法，使得新算法的时间复杂度降为O(|C|2|U|2)。
　　(3)在对区分对象对集进一步研究中，区分对象对集算法时空复杂度还是不够理想，为此，在区分对象对集基础上，设计一个能计算区分对象对集的个数的函数，并用该函数设计了一个启发函数，同时给出该启发函数的快速算法，利用启发函数设计了一个高效的不完备决策系统属性约简算法，新算法时间复杂度及空间复杂度分别降为O(K|C‖U|)(其中K=max{|TC(xi)|，x∈U}和O(|U|)。通过实例仿真说明该算法是一高效可行的属性约简算法。

目录

摘要

1．绪论

1．1 课题研究背景

1．2 Rough Sets理论概述

1．2．1 Rough Sets理论国内外研究现状

1．2．2 Rough Sets理论应用研究

1．3 论文的主要创新点

1．4 论文的组织结构

2．Rough Sets理论

2．1 知识与分类

2．2 决策表相关的基本概念

2．2．1 完备决策表的基本概念

2．2．2 不完备决策表的基本概念

2．3 完备决策系统属性约简定义

2．3．1 完备决策表属性约简的J下区域表示

2．3．2 完备决策表属性约简的HU差别矩阵表示

2．3．3 完备决策表属性约简的信息熵表示

2．3．4 完备决策表属性约简的知识粒度表示

2．4 不完备决策系统属性约简定义

2．4．1 不完备决策表属性约简的正区域表示

2．4．2 不完备决策表属性约简的HU差别矩阵表示

2．4．3 不完备决策表属性约简的知识粒度表示

2．5 本章小结

3．基于布尔与的浓缩差别矩阵属性约简属性约简算法

3．1 新算法的设计思想

3．2 基于布尔与的浓缩差别矩阵属性约简相关定义

3．3 基于布尔与的浓缩差别矩阵的属性约简算法

3．4 算法复杂度分析

3．5 实例说明

3．6 实验对比

3．7 小结

4．改进的基于正区域的浓缩差别矩阵属性约简算法

4．1 新的属性约简算法的设计思想

4．2 基于正区域的浓缩差别矩阵属性约简相关定义

4．3 改进的基于正区域的浓缩差别矩阵的属性约简算法

4．4 算法复杂度分析

4．5 实验对比

4．6 小结

5．高效的不完备决策系统属性约简算法

5．1 新属性约简算法的设计思想

5．2 新属性约简算法的相关定义

5．2．1 基于区分对象对集的相关性质

5．2．2 计算区分对象对集的启发函数

5．3 高效的属性约简算法

5．4 算法复杂度分析

5．5 实例说明

5．6 实验对比

5．7 小结

6 总结与展望

6．1 论文总结

6．2 问题与展望

参考文献

攻读硕士学位期间科研成果

致谢

声明