不完备信息系统中的规则提取【毕业论文】.doc

1、毕业论文 文客久久网 本科 毕业论文 (设计 ) 题 目： 不完备信息系统中的规则提取 学 院： 学生姓名： 专 业： 数学与应用数学 班 级： 指导教师： 起 止 日期： 毕业论文 文客久久网 摘 要 目前 , 在完备的信息系统中挖掘知识 , 人们已经有许多成熟的方法 , 但是 , 对于 如何将不完备信息系统中这些有用的规则挖掘出来 , 是广大学者研究的热点之一 , 挖掘 不完备信息系统 中 的规则是 一个 具有重要实际意义的研究问题 . 本文在回顾 信息系统中 , 一般二元关系的粗糙集理论的基础上 , 结合不完备信息系统中的完 备化方法 , 讨论粗糙集近似算子的性质 . 并通过建立论域的容

2、忍关系 , 将粗糙集方法用于不完备信息系统的规则提取问题研究 , 给出一种新的 规则提取的方法 , 讨论了决策规则的优化性质 . 并举例说明了方法的可行性 . 关键词 ： 粗糙集 ; 不完备信息系统 ; 决策规则 毕业论文 文客久久网 Abstract At present, there are many mature methods for data mining in the complete information systems. But how to mine useful rules in incomplete information systems is a researchin

3、g focus of majority of scholars, and it is also important work. In this thesis, rough set theory based on general binary relations is reviewed, combining the completing approach of incomplete information systems, the properties of rough sets are discussed in detail. By constructing the tolerance rel

4、ation on the universe of discourse, the method of rough sets is used for the rule extracting of incomplete information systems, and gives a new approach of rule extraction, discuss the properties of the optimization of decision rules, the feasibility of this method is illustrated by some examples. K

5、eywords: Rough sets; incomplete information system; incomplete decision rules 毕业论文 文客久久网 目 录 摘 要 . I ABSTRACT. II 目 录 . III 1 前言 . 1 2 粗糙集 . 3 2.1 粗糙集理论的基本知识 . 3 2.2 粗糙集的拓展模型 . 3 基于一般关系的粗糙集近似算子具有下列性质 . . 4 3 信息系统 . 6 3.1 完备与不完备信息系统 . 6 3.2 信息系统中的粗糙集模型 . 8 3.3 完备信息系统中的规则提取 . 9 4 不完备信息系统中的规则提取 . 13 4.

6、1 不完备信息系统的完备化 . 13 4.2 不完备信息系统中的决策规则 . 13 5 小结 . 16 参考文献 . 17 致谢 . 19 毕业论文 文客久久网 1 前言 由波兰科学家 Z. Pawlak 1 于 1982 年提出的经典粗糙集理论 , 作为一种有效处理不确定、不精确、不完备信息的新型数学工具 , 对完备信息系统的数据分析与处理起到了很大的促进作用 . Z. Pawlak 建议提供了一个正式处理不精确或不完整的信息 工具 . 这种做法似乎从根本上重要的人工智能和认知科学 . 经常有一些错误 , 不完整 , 不确定和模糊的数据在现实生活中的数据 . 一种形式的数据的不完备性 : 缺

7、少属性值 . 为了方便数据分析 , 数据通常是由两维表中的代表 . 此表将被称为知识表示系统 , 或信息系统 . 包含缺少属性值时 , 它被称为一个不完备信息系统 . J.W. Guan 2 和 M. Kryszkiewicz 3 发展了不完备信息系统粗糙集数据分析 算法 . 粗糙集数据分析的基本计算方法是不完备信息系统 , 他们的时间和空间复杂度进行了分析 . 其中建议的最小约简算法在数据库中发现知识是非常有用的 . R. Slowinski 和 D. Vanderpooten 4 调查了在粗糙集范围内的规则不完备系统的生成的问题 . 并探讨了三种不同的形式主义处理不完备信息表 : 宽容的关

8、系 , 非对称相似关系和有价值的耐受性关系 . 基于非对称相似关系的一个方法 , 他们取得了一些成果 , 即非对称相似的方法提炼使用容差关系的方法得出的结果 . 规则的获取是数据研究领域中的一个非常重要的研究课题 . 目前 , 有许多基于机器学习、模式识别及统计学的规则的获取算法 , 如决策树方法、贝叶斯方法、聚类分析、遗传算法、神经网络等 . 规则提取是数据挖掘研 究的主要内容之一 , 其中未知值问题有待解决 . 被认为是从不完备信息系统中发现知识的问题 . 通过一个完整的系统 , 我们命名一个丢失数据的系统（空值） . 我们不考虑意味着不适合值的空值 . 通过加入一个特殊的符号 , 表示不

9、适用值的属性域 , 这个问题可能得到解决 . R. Slowinski 与 J. Stefanowski 5 讨论未知值的外观造成的模糊集模型的不确定性 , 处理未知值的问题 . 在人工智能（ AI）领域产生决策树的训练集合的未知值的例子的问题的几种解决方案已经提出 . 其中最简单的由未知值的例子 中取出或用最常用的值更换未知值 . 更 复杂的方法是在 I. Kononenko 6 与 J.R. Quinlan 7 提 出 . Bayes 形式主义是用确定的未知值超过域的可能值的概率分布 , 这种方法可以选择最可能的值 , 或分成小数对象的对象 , 每一个可能的值按加权确定的概率 . J.R.

10、 Quinlan 7 建议预测对象的其他属性值和类的信息为基础的属性毕业论文 文客久久网 值 . P. Clark 8 提出了另一种简单的一种是最 常见的价值 , 以取代未知值 . 其他更 复杂的方法 J. W. Grzymala-Busse 9 与 J. Jelonek, K. Krawiec 与 R. Slowinski 10. 除了删除有缺失值的例 子的方法 , 所有上述方法替换丢失的值 , 根据属性值的决策表中的其他例子分布 . 目前 , 基于完备信息系统的规则提取方法比较成熟 . 如何将不完备信息系统中这些有用的规则挖掘出来 , 是广大学者研究的热点之一 . 目前 , 很多学者对它进

11、行了研究并提出了不同的规则提取算法 . M.R. Chmielewski 与 J.W. Grzymala-Busse 11 等人 , 提出了一种方法 : 由一个不完备系统 改造成一个完备的系统 , 不完备信息系统中描述的每个对象是一个可能的子对象在目标系统的设置取代 . 这种方法是很难在实践中应用，因为大尺寸的一个新的表 . 其中另一种方法是 AI 简单的方法 , 前面提到的减少与未知的值删除的对象的原始表的大小 . M. Kryszkiewicz 12 提出的方法可以产生直接从原来的不完备决策表的广义规则 . 然而对于某些决策表提取出的确定规则并不是最优的 . 不完备信息系统的规则是具有重要

12、实际意义的研究问题 . 本文在回顾已有不完备信息系统中粗糙集模型以及规则提取问题的基础上 , 给出一种新的规则提取方法 , 讨论规则最优化性质 . 毕业论文 文客久久网 2 粗糙集 2.1 粗糙集理论的基本知识 定义 2.11 设 U 是论域 , R 是 U 上的一个等价关系 , 即 R U U. /UR表示 R 的所有等价类构成的集合 , 即 / :RU R x x U , 其中 Rx 表示包含 x 的 R 等价类 , : ( , )Rx y U x y R . 也就是 Rx 满足以下三个性质 : (1) , Rx U x x （自反性） ; (2) , , RRx y U y x x y

13、（对称性） ; (3) , , , , R R Rx y z U y x z y z x （传递性） . 定义 2.2 设 R 是论域 U 上的一个等价关系 , 称 ( , )UR 为 Pawlak 近似空间 ; 对于任意XU , 称 ( ) : RR X x U x X : RRx x X, 为 X 关于近似空间 ( , )UR 的下近似 , 称 ( ) : RR X x U x X : RRx x X , 为 X 关于近似空间 ( , )UR 的上近似 . 称 ( ) ( ( ), ( )R X R X R X 为 X 关于近 似空间 ( , )UR 的粗糙集 . 称幂集 ()PU 上的

14、集合算子 R 与 R 分别 为下近似算子与上近似算子 . 2.2 粗糙集的拓展模型 在 Pawlak 粗糙集模型中 , 论域上的等价关系是最基本的概念 ,.但在很多实际问题中 , 论毕业论文 文客久久网 域上的二元关系不是等价的 , 这时 Pawlak 粗糙集模型的应用受到了限制 , 因此扩展基于等价关系的粗糙集为基于 一般二元关系的粗糙集显得非常重要 . 定义 2.3 2,3 设 U 是有限非空的论域 , R U U 为 U 上的任意的二元关系 , 称 ,A U R 为广义近似空间 . 对于任意 XU , X 关于近似空间 ,A U R 的下近似AaprX和上近似 Aapr X 分别定义为

15、sAa p r X x U R x X sAap r X x U R x X 其中 : 当 XaprA= XaprA 时 , 称 X 关于近似空 间 A 是可定义的 , 否则称 X 关于近似空间A 是粗糙的 . 注 . 如果 R 是等价关系 , 则 sRx就是对象 x 所在的 R 等价类 Rx , 也就是 说 x 所在的等价类可以看成 x 的邻域 , 这时所得到的下近似Aapr X和上近似 XaprA 就是 Pawlak 意义下的下近似 RX 和上近似 RX . 显然 , 近似算子 apr 和 apr 是 P U P U 的算子 , 我们称系统 , , , , ,P U a p r a p r

16、为广义粗糙集代数 . 基于一般关系的粗糙集近似算子具有下列性质 . 命题 2.1 设 R 是论域 U 上的一个任意的二元关系 , 则 （ 1） )( XaprXapr , )( XaprXapr . （ 2） UUapr , apr . （ 3） Ya p rXa p rYXa p r )( , Ya p rXa p rXa p r )( . （ 4） YX YaprXapr , YaprXapr . （ 5） Ya p rXa p rYXa p r )( , YaprXaprYXapr )( . 例 2.1 设 4,3,2,1U , )4,3(),2,3(),1,2(),2,1(),1,1(

17、R , 41X , 4,3,2Y , 可以得 : 2,1)1( sR , 1)2( sR , 4,2)3( sR , (4)sR 毕业论文 文客久久网 所以 4,2Xapr , 4,3Yapr , 4,3,2YaprXapr , 4,3,2,1)( YXapr . 并且 3,2,1Xapr , 3,2,1Yapr , 3,2,1aprYXapr , 3)( YXapr . 毕业论文 文客久久网 3 信息系统 3.1 完备与不完备信息系统 定义 3.13 四 元组 ( , , , )S U A V f 是一个信息系统 , 其中 U 表示对象的非空有限集合 , 称为论域 ; A 表示属性的非空有限

18、集合 ;aaAVV, aV 是属性 a 的值域 ; f 表示U A V是一个信息函数 , 它为每个对象的每个属性赋予一个信息值 , 即 aA , xU , ( , ) af x a V . 信息系统在智能数据处理中占有十分重要的地位 . 信息系统的数据以关系表的形式表示 . 关系表的行对应要研究的对象 , 列对应对象的属性 , 对象的信息是通过指定对象的各属性值来表达 . 容易看出 , 一个属性对应一个等价关系 ,一个表可以看作是定义的一族等价关系 , 即知识库 . 设 ( , , , )U AV f 是一个信息系统 , 若对于任意 aA ,xU , 都有 ( , )f xa 是 aV 中一个

19、确定数值 , 则称 ( , , , )U AV f 一个完备的信息系统 . 如果存在某个 aA 和某个 xU , 对应的 ( , )f xa 不是 aV 中一个确定数值 , 也称 此属性值是不确定的 , 则称 ( , , , )U AV f 为不完备的信息系统 . 设 ( , , , )U AV f 是一个完备信息系统 , 对于任何 BA , Pawlak 在其上定义了一个等价关系 : ( ) ( , ) | , ( , ) ( , )I N D B x y U U a B f x a f y a . 则 ()INDB 是 U 上的一个等价关系 . 表 3.1 一个信息系统 U 1a 2a 3a 4a 5a 1x 2 1 3 1 2 2x 1 2 2 2 3 3x 2 1 3 2 3 4x 2 3 4 4 2 5x 1 2 2 1 1