不完备信息系统的增量式知识约简算法研究

发布时间：2017-07-28 08:16

第一章 绪论

1.1 研究背景与意义

全球每天几十亿人使用计算机、GPS 设备、电话和医疗设备，产生海量的数据信息。为了长远发展，企业纷纷建立自身独有的数据库，以期为自身长远发展提供决策支持，如何从这些海量数据中挖掘出对企业长远发展有益的信息成为当前重要的研究课题。然而，数据中往往存在着大量毫无价值的信息，且难于通过主观的经验去甄别，这不仅会造成资源的浪费，最重要的是会干扰企业的发展决策。研究还发现：绝大多数拥有海量数据库的企业，数据和信息的有效利用率仅为 7%，大量的知识资源得不到有效利用。与此同时，由于各种原因，经常会出现数据缺损的情况，例如：数据输入时人为疏漏、数据传输堵塞、机器故障等，都会造成数据不完整。如此庞大、复杂、不完整的数据面前，人工分析已经无能无力，宝贵的信息无法得到充分的利用，知识发现技术应运而生。知识发现[1-2]是挖掘数据库中数据或属性间一个代数关系，通过存在的关系建立数学模型以提取有用的信息提供给用户，方便用户在信息正确的情况下处理“缩减”后的数据信息。因此如何应对数据缺失、提取海量数据中有效的数据已经成为数据分析的热点课题。

...............

1.2 粗糙集在完备信息系统中的研究现状

粗糙集理论提出至今，经过 30 多年的研究发展，已经成为非常有效的数据分析与处理工具。粗糙集在发表之初并未受到太多关注，直到 1990 年前后才逐渐受到广泛的重视。尤其进入 21 世纪以来，该理论在机器学习、数据挖掘、决策支持等方面的广泛、成功的应用使它成为诸多领域的研究热点之一。作为粗糙集理论核心研究内容之一的属性约简，约简结果通常并不唯一。 Wang 等人[6]在研究的过程中已经证实求解所有属性约简和最小约简是 NP-hard 问题。据此，在属性约简中启发式的方法被广泛应用。常用的启发式算法有基于信息熵的方法[7-9]、基于差别矩阵[10,11]的方法和基于正区域[12,13]的方法。

...............

第二章 信息系统中的基本概念

2.1 知识与分类

知识是人类通过实践认识到的客观世界的规律性的东西，是人类实践经验的总结和升华，具有抽象性和普遍性。定义 2.1[39]（知识） 设 U 是非空的有限实例的集合，称为论域。论域中任何一个子集 X   U，称为论域 U 的一个概念。论域 U 中任何子类族称为关于 U的知识。在粗糙集理论中通常用不可分辨关系来表示分类及知识。而从数学和数据在计算机中的表示形式的角度来看，关系在计算机中的表示和处理比分类的表示和处理更容易、简单，所以，我们就用等价关系或关系来表示知识及分类。在实际生活中，我们处理的数据在论域 U 上并不仅仅只是单一的划分，而是论域 U 上的多个或一族划分。从而，我们就有了信息库的相关概念。

...............

2.2 上、下近似集及正区域

定义 2.5[39]（上、下近似集）给定信息库 S   (U ,A,V,f)，U 为论域，集合 X U和 U 论域上的一个不可分辨关系 R  IND(S)，定义两个子集：R( X){x|(xU)([x]X)}{Y|(YU/R)(YX)}R 2.2）R( X)  {x|( x U) ([x]X  )} {Y|( Y U/R) (YX  )}R （2.3）分别称之为 X 关于 R 的下近似集、上近似集。 R (X)称为 X 关于知识 R的下近似，表示U 中确定划分到集合 X 的对象组成的集合，，等价关系中属于集合 X 的所有子集Yi的并集。R  (X)称为 X 关于知识R 的上近似，表示论域U 中有确定和可能被划分到集合 X 的实例组成的集合，关系中与集合 X 的交集不为空的所有子集 Yi的并集。

...............

第三章 不完备决策表的数据补齐................13

3.1 引言................13

3.2 模糊加权相似性度量.................13

第四章 基于数据补齐的不完备决策表增量式属性约简................20

4.1 引言...............20

4.2 补齐后的决策表化简算法.................20

第五章 基于限制容差关系的不完备决策表增量式属性约简................29

5.1 引言...............29

5.2 扩展模型分析................30

第五章 基于限制容差关系的不完备决策表增量式属性约简

5.1 引言

当前数据普遍存在数据不完备、动态增长这两个特性，针对数据不完备性，解决的办法多集中在数据补齐和拓展粗糙集模型上，这两种思路是当前不完备数据的研究基础。同时，数据动态增长的特性导致建立的原信息系统的结论可能不再有效，需要对这些结论动态更新。据此，针对不完备增量式数据的知识发现，之前的章节提出了一种基于模糊加权的粗糙集数据补齐方法，补齐后的数据可以较方便的利用现有的针对完备数据所取得的研究成果，在此基础上，分析研究现有的针对补齐后决策表的增量式属性约简算法，在简化决策表的基础上提出一种综合差别矩阵和正区域两种思想的增量式属性约简算法，在原决策表约简结果的基础上，该算法能快速更新数据动态变化后的决策表属性约简结果，同时保证约简结果不再包含冗余属性。

...............

5.2 扩展模型分析

经典粗糙集理论通过等价关系对对象进行分类和处理，然而实际数据中大量存在着不完备现象，当利用经典粗糙集理论对这些数据进行处理时，将会出现由于不完备数据无法满足等价关系致使经典粗糙集束手无策的现象。为解决等价关系划分不完备信息系统过于苛刻的问题，目前已提出多种粗糙扩展集模型，本节分析比较基于容差关系、非对称相似关系、量化相

本文编号：582943