1、 本科毕业论文 （ 20 届） 不完备信息系统中基于证据理论的知识约简 所在学院 专业班级 数学与应用数学 学生姓名 学号 指导教师 职称 完成日期 年 月 I 摘要 知识约简是知识表示和数据挖掘中的一个基本问题 . 本文我们研究在不完备信息系统和不完备决策系统中基于证据理论的属性约 简 . 首先 , 介绍了完备信息系统和不完备信息系统的概念 , 回顾了信任函数与似然函数的定义和基本性质 . 其次 , 给出了不完备系统中的约简、相对约简、信任约简和似然约简的定义 , 并讨论了这些概念之间 的关系 . 最后 , 讨论了不完备决策表中基于证据理论的属性约简问题 , 证明了 在一个 协调的不完备决策
2、系统中相对约简、相对似然约简和相对信任 约简 这些概念都 是等价的 ; 而 在一个不协调的不完备 决策 系统中 , 一个 属性集是相对似然约简当且仅当它是相对约简 , 一个似然协调集必 定 是一个信任协调集 , 但 一个信任协调集一般不 会 是一个似然协 调集 . 关键词： 不完备信息系统 ; 粗糙集 ; 信任函数 ; 知识约简 II Knowledge Reduction in Incomplete Information Systems Based on Dempster-Shafer Theory of Evidence Abstract Attribute reduction is a
3、 basic issue in knowledge representation and data mining. In this thesis, we mainly focus on the study of attribute reduction in incomplete information systems and incomplete decision systems based on evidence theory. The concepts of complete information systems and incomplete information systems ar
4、e first introduced. Definitions of belief functions and plausibility functions as well as their properties are also reviewed. The concepts of reduct, belief reduct and plausibility reduct in incomplete information systems are then defined, and their relationships are discussed. Finally, we investiga
5、te the issue of attribute reduction in incomplete decision systems. It is proved that in a consistent incomplete decision system, the concepts of relative reduct, relative plausibility reduct and relative belief reduct are all equivalent. In an inconsistent incomplete decision system, an attribute s
6、et is a relative plausibility reduct if and only if it is a relative reduct, and a plausibility consistent set must be a belief consistent set. However, a belief consistent set may not be a plausibility consistent set. Keywords: Incomplete information systems; Rough sets; Belief functions; Knowledge
7、 reduction III 目 录 摘要 . I Abstract . II 1 前言 .1 1.1 信息系统知识约简的研究背景 . 1 1.2 论文的组织结构 . 1 2 信息系统 .3 2.1 完备信息系统 . 3 2.2 不完备信息系统 . 3 3 不完备信息系统基于证据 理论的属性约简 .8 3.1 信任结构和信任函数 . 8 3.2 不完备信息系统的属性约简 . 9 4 不完备决策系统的属性约简 .13 4.1 协调的不完备决策系统的属性约简 . 13 4.2 不协调的不完备决策系统的属性约简 . 16 5 小结 .21 参考文献 .22 致谢 . 错误 !未定义书签。 1 1 前
8、 言 1.1 信息系统知识约简的研究背景 随着信息的不断快速增长 , 我们在生活中遇到完整的、确定的、不完整的、不确定的信息 ,从数据中获取知识的理论越来越重要了 , 对数据分析方法的要求也越来越高 . 目前 , 在处 理完备信息系统和不完备信息系统时 , 我们运用了粗糙集理论 , 成功地对信息系统进行知识约简 , 本文将运用证据理论中的知识对不完备信息系统中的知识约简进行研究 . 粗糙集理论 21 最初是 由 Pawlak 3 提出 , 是为了研究不完整的智能信息系统而从经典集合论中延伸出来的 , 经过 20 多年的发展 , 粗糙集理论在智能系统中取得了显著的成果 . 在粗糙集理论中 , 信
9、息系统是一个重要的概念 . 大多数的粗糙集理论的应用是建立在信息系统模型上的 . 根 据信息系统 的属性值是否确定 , 我们可将其分为 : 完 备 信息系统和不完 备信息系统 . 一个完 备 信息系统是一个所有属性值都是确定已知的系统 . 不完 备 信息系统是指一些属性 值是 未知 , 或者被丢失了 , 或者是部分已知的信息系统 . 粗糙集理论的主要特点是 数据 直接从给定问题的分类知识出发 , 通过不可分辨关系来确定给定问题的知识约简 , 导出问题的决策或分类规则 , 为 信息系统或决策系统提供潜在知识和决策的支持 . 知识约简是粗糙集理论的核心问题 , Kryszkiewicz 提出了可能
10、约简 4 , 张文修5 等 提出了分布约简、分配约简和近似约简 , 米据生 6 等提出了 可变精度粗集模型 , 管涛 7和冯博琴 7 在模糊目标信息系统种推广了文献中的几种知识约简 , 王国胤 8 等 提出了信息熵约简 , Dominik 9 定义了近似熵约简 . 由于现实生活中广泛存在的信息 系统是不完备的 , 因此也 有学者将知识约简在不完备系统中进行了推广 . 如 Kryszkiewicz 提出了广义决策约简 10 , 周献中 11 和黄兵 11 将分布（分配）约简引入不完备决策系统 , 管延勇 12 等 使用最大连续块技术获取不完备信息系统的可信规则 , 吴伟志 13 等 研究了不完备
11、模糊信息系统中的知识约简 . 粗 糙集理 论与证据理论之间有很大的关系 . 事实证明 , 各种信任结构中的信任函数和似然函数与粗糙集理论中的上下近似有很大的对应关系 . 证据理论可以在信息系统的知识约简方面发挥很大的用处 . 1.2 论文的组织结构 本文强调了粗糙集理论在数据挖掘和数据处理方面所做出的贡献 , 然后介绍了证据理论2 在处理不完备信息系统中的应用 . 在文章的第二部分 , 我们将信息系统分为 : 完 备 信息系统和不完 备 信息系统 , 对它们的概念进行具体介绍 , 详细介绍了粗糙集理论中的完 备 信息系统知识以及不完 备 信息系统的性质 . 文章的第三部分着重介绍了证据理 论在
12、不完 备 信息系统的知识约简方面的应用 , 提出了信任函数和似然函数的概念 . 文章的第四部分 介绍了协调 的 不完全决策系统 和不 协调 的 不完全决策协调系统的知识约简 . 本文以证据理论解决不完 备 信息系统中的知识约简问题 , 提出新的一种知识约简的方法 , 丰富不完 备 信息系统知识约简的内涵 . 3 2 信息系统 2.1 完 备 信息系统 一个信息系统 S 是一个 二元组 ),( ATU , 其中 nxxxU , 21 是有限非空集 , 称 为论域或对象空间 , U 中的元素称为对象 ; maaaAT , 21 也是一个有限非空集 , AT 中的元素称为属性 ; 对于每个 ATa
13、有一个映射 aVUa : , 即 aVxa )( , aV 称为属性 a 的值域 . 在一个完 备 信息系统 S 中 , 任意非空集合 ATB , 定义一个不可分辨关系 BayaxaUUyxI B ),()(:, ）（ . (2.1) 因此 , BI 是在 U 上的一个等价关系 , 从而有 U 的划分 UxxIU BB : , 其中 Bx 是 x关于 B 的等价类 , 即 BB IyxUyx ),(: . 2.2 不完 备信息系统 我们看到在完 备 信息系统中 , 任何对象的所有属性值都是唯一确定的 , 即 Ux 以及ATa , 总是存在唯一的 aVv , 使得 vxa )( . 然而 , 我
14、们的知识库可能是不完整的 , 我们不能 确定被给的对象在属性 a 下的确定值 , 即属性的精确值无法得知 , 或者被丢失了 , 或者只是部分知道 . 在这种情况下 , 我们只能表示对象的可能值 , 丢失的值 )(xa 可被所有可能值表示 , 即 aVxa )( , 我们称 这样的系统 为不完 备 信息系统 . 一个决策系统是一个 二元组 ),( dCUS , 其中 ),( CU 是一个信息系统 , Cd , 并且 d 作为完整的属性称为决策 . 在这种情况下 , C 是条件属性 , d 是一个从论域 U 到集合 aV的映射 dVUd : , rVd ,2,1 . 定义 )()(:),( ydx
15、dUUyxR d . 从而 , 我们 得到划分 U 的一个划分 rd DDDRU , 21 , 其中 jxdUxD j )(: , rj . 如果 ),( CU 是一个完 备 信息系统 , 那么 S 是一个完 备 决策系统 ; 如果 ),( CU 是一个不完 备 信息系统 , 那么 S 是一个不完 备 决策系统 . 利 用条 关于 件属性子集的决策集合的上下近似 , 我们可以从一个决策系统中得到一个 确定 的决策规则和 不确定的 决策规则 . 4 在一个不完 备 信息系统 ),( ATUS 中 , 任意一个非空子集 ATA 决定了一个 相似 关系 AayaxaUUyxR A ,)()(:, ）
16、（ . (2.1) 令 AA RyxUyxS ),(:)( , )xSA 称为在 S 上 x 关于 A 的 相似 类 , 而 A 中所有 相似 类的全体用 ARU 来表示 , 即 UxxSRU AA :)( . 如果不完 备 信息系统 S 中存在 缺 省值 , 相似 关系 AR 可定义为 ,)(,)(),()(:),( AayaxayaxaUUyxR A 或或. 例 2.1 表 2.1 表示一个不完 备无决策的 信息 系统 , 对象集 821 , xxxU , 表示不同的汽车 , 属性集 XSMPAT , . P 代表价格 , M 代表里程 , S 代表尺寸 , X 代表最大速度 ,并且 PV
17、 = SV = XV =低，高，中 , SV =大，小 , “ ”表示属性值是未知的 . 表 2.1 不完备信息系统表 Car P M S X 1x 高 低 大 低 2x 低 大 低 3x 小 低 4x 高 大 高 5x 大 高 6x 低 高 大 7x 中 不低 大 不低 8x 不高 不高 小 不高 若按式 (2.1)的定义，则表格 2.1 转化为表 2.2 表 2.2 不完备信息系统表 5 Car P M S X 1x 高 低 大 低 2x 低 高 , 中 , 低 大 低 3x 高 , 中 , 低 高 , 中 , 低 小 低 4x 高 高 , 中 , 低 大 高 5x 高 , 中 , 低 高
18、 , 中 , 低 大 高 6x 低 高 大 高 , 中 , 低 7x 中 中 , 高 大 中 , 高 8x 低 , 中 低 , 中 小 低 , 中 在一个不完 备 信息系统 ),( ATUS 中 , ATA , UX , X 关于 A 的上 近似和下 近似 定义 如下 XxSUxXA A )(:)( , XxSUxXA A )(:)( . )(XA 和 )(XA 分别是 X 关于 A 的属性约简的上 近似和 下近似 . )(XA 就是那些根据已有知识判断肯定属于 X 的对象所组成的最大集合 , )(XA 就是那些根据已有知识判断可能属于 X 的对 象所组成的最小集合 . )(),( XAXA
19、称为 X 关于 A 的粗糙集 . 例 2.2 在例 2.1 中 , 令属 性集 , SMPB , 那么 ,)( 5411 xxxxS B , ,)( 6522 xxxxS B , ,)( 833 xxxSB , ,)( 5414 xxxxS B , ,)( 76525 xxxxxS B , ,)( 6526 xxxxS B , ,)( 757 xxxSB , ,)( 838 xxxSB . 若我们令 , 652 xxxX ，则可得 ,)( 765421 xxxxxxXB , ,)( 62 xxXB . 性质 2.1 设二元组 ATUS , 是不完备信息系统 , ATBA , , 那么 )(,
20、UYX , 6 其中 )(U = : UXX . (1) )(XA X )(XA , (2) )(XA = )( XA , (3) )(UA = )(UA =U , )(A = )(A = . (4) )( YXA = )(XA )(YA , )()()( YAXAYXA . (5) YX )(XA )(YA , )(XA )(YA . (6) )()( XBXAATBA , )()( XAXB . 其中 XUX 是 X 在 U 上的补集 . 证明 (1)设 )(XAx , 有 XxSA )( ; 因为 )(xSx A , 所以 Xx , 从而 , )(XA X . 设 Xx , 有 XxSA
21、 )( , 所以 , )(XAx , 因此 , )(XAX . (2)因为 )()()()( XAxXxSXxSXAx AA )( XAx , 所以 )()( XAXA . (3)由 (1)知 , )(A , 而 )( A , 因此 , )(A . 假设 )(A , 则存在 x 使得 )(Ax , 即 )(xSA . 而 )(xSA , 与假设矛盾 . 因此 , )(A . 由 (1)知 , UUA )( . 又因为当 Ux , 有 UxSA )( , 所以 )(UAx , 即 )(UAU ,因此 , UUA )( . (4) )( YXAx YXxS A )( YxSXxS AA )()( )()( YAXAx , 因此 )()()( YAXAYXA .
