基于不完备决策表的属性约简及规则获取算法的研究

摘要

随着高科技的飞速发展，全世界每天都有几十亿的人在使用手机、电脑和其他电子产品，产生了大量的海量数据。大数据从互联网向其他领域急速蔓延，各行各业都已经被数据给渗透，对于海量数据的有效处理成为目前研究的热点之一。在2015年的两会期间，李总理签订了国务院有关推进“互联网+”行动的指导意见，给互联网与传统行业之间的有效结合提供了政策依据。数据挖掘的发展优势越来越突出，占据了互联网的广阔天地。所谓数据挖掘就是对数据库中的数据，利用一些数据处理的方法，查找出在信息之间存在的内在关系的过程。包含数理统计、模式识别、神经网络等技术，广泛应用于电信、航空公司、政府和科学领域中。
　　粗糙集是数据挖掘的方法之一，是一种用于处理不准确、含有缺省值的工具。相较于模糊集，它最突出的特点是不需要其他先验的信息，或附加的知识，就可以直接处理信息，找出海量数据中的隐含知识，应用于实际生活中。在数据挖掘的过程中，属性约简可以被看做为一个预处理的步骤，同时在粗糙集理论中占据了举足轻重的地位。属性约简可以定义为在保证知识库能够有效的区别库中含有的对象的前提下，将其中不能起到决定作用的属性消去。因此，在操作之后可以有效地减少知识库中的属性表示，同样也保证了对象基本信息的完整性。在将知识库中的冗余属性消去之后，在很大程度上降低了知识所占用的空间，有效的减少了成本支出。
　　在目前的研究进程中，将粗糙集的属性约简分成了两种不同的类型，一种是包含全部的信息，叫做完备知识表，另一种中含有不确定的或者空缺的信息，命名为不完备知识表。完备知识表指的是在知识系统中所有的对象信息都是准确并且全面的，现在对于完备知识系统的属性约简探索相对来讲是比较全面也比较成熟的，在现实的应用中也施展出来了很大的引导作用。但是，实际生活中由于数据搜集设备的不可避免的误差，或者是搜集过程中环境的影响等情况，导致知识系统中会有一些信息缺失的情况存在，原有完备知识系统的算法已经不能适用于这种情况。对含有缺失信息的决策表的研究是未来科学家和学者们重点关注的地方。
　　此外，规则获取是粗糙集理论中的一个比较实用的领域。随着信息爆炸式的增长，企业和各种组织积累了海量的数据，但是这些数据本身并不是有用的信息，在数据中的规则才是对企业做出有效决策提供帮助的信息，可以使企业在处理数据信息时有可靠的依据。因此获取决策知识库中的规则同样具有实用性。
　　本文对当前学者在粗糙集中属性约简和规则获取中取得的研究成果进行了学习，在结合他们的基础上，进行了以下创新:
　　(1)在不完备知识系统中，引入了基于粒度的差别矩阵，利用条件属性在区别对象时出现频率的属性约简思想，在粒度差别矩阵的基础上，构造了计算属性频率的启发函数。以知识粒度为启发信息，提出了新的约简算法，使得算法的时空复杂度都得到了很大幅度的降低，分别降为O(K|C‖U|)（其中K=max{|T(xi)|，xi∈U}和O(|U|)，最后通过数据集进行仿真实验，证明了算法相较于同类算法有较高的时间效率。
　　(2)介绍了LEM2规则获取算法总有属性-值对是在反复的被纳入候选属性-值对，然后又在程序的后面进行反向消除的缺陷，及一系列改进算法的不足之处，本文引入广义决策函数，在程序执行之前就先删除存在的冗余属性-值对，使它们无法参与后面的一系列操作，减少了属性-值对的样本空间，提高了求取属性-值对的效率。

目录

摘要

1 绪论

1．1 选题背景和目的

1．2 粗糙集理论相关概述

1．2．1 粗糙集理论的产生与发展

1．2．2 粗糙集理论的研究现状

1．3 论文的主要创新点

1．4 论文的组织与安排

2 粗糙集理论相关概述

2．1 知识与分类

2．2 决策表的基本概念

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

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

2．3 完备决策表属性约简及求核

2．3．1 基于正区域模型的属性约简和核属性定义

2．3．2 基于Skowron差别矩阵模型的属性约简和核属性定义

2．3．3 基于信息熵的约简及求核定义

2．3．4 知识粒度的属性约简定义

2．3．5 基于分布、最大分布和分配的约简定义

2．4 在不完备决策系统中的属性约简及核定义

2．4．1 在正区域上的属性约简与求核定义

2．4．2 差别矩阵的属性约简及求核

2．4．3 在知识粒度上的约简及求核定义

2．4．4 广义决策的约简定义

2．5 本章小结

3 基于知识粒度的快速属性约简算法

3．1 设计思想

3．2 基本定义及性质

3．2 粒度差别矩阵相关概念

3．3 构造启发函数

3．4 属性约简算法

3．5 实例分析

3．6 仿真实验对比

3．7 本章小结

4 基于快速缩小样本空间的改进的LEM2算法

4．1 设计思想

4．2 相关概念

4．3 LEM2及其改进算法的局限性分析

4．4 快速缩小样本空间的改进算法

4．5 实验分析

4．6 小结

5 展望

5．1 论文总结与不足

5．2 展望

参考文献

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

致谢

声明