1、 本科毕业论文 （ 20 届） 信息系统中基于证据理论的属性约简 所在学院 专业班级 信息与计算科学 学生姓名 学号 指导教师 职称 完成日期 年 月 I 摘要 属性约简是粗糙集理论研究的一个主要问题 . 本文主要研究完备信息系统中基于证据理论的属性约简 . 首先 , 介绍完备信息系统 和完备决策表的概念 , 回顾经典粗糙集、信任函数、似然函数的定义和基本性质 . 其次 , 给出了信息系统的经典属性约简、信任约简与似然约简的概念 . 并证明了在完备信息系统中信任约简、似然约简和经典约简都是等价的 . 最后 , 在协调的完备决策系统和不协调的完备决策系统中定义了相对信任约简和相对似然约简的概念
2、. 并将新定义的约简概念与已有相对约简和广义决策约简概念进行了比较 , 建立了约简之间的相互关系 . 关键词 : 信任函数 ; 协调集合 ; 决策系统 ; 信息系统 ; 约简 ; 粗糙集 II Abstract Attribute reduction is one of the main problems in the study of rough set theory. In this thesis, we mainly focus on the study of knowledge reduction in complete informati- on systems based on e
3、vidence theory. The concepts of complete information systems a- nd complete decision tables are first introduced. Definitions and and some basic proper- ties related to classical rough sets, belief functions, and plausibility functions are also r- eviewed. The concepts of belief reducts and plausibi
4、lity reducts in complete informatio- n systems are then defined. It is proved that both of belief reduct and plausibility redu- ct are equivalent to classical reduct in complete information systems. Finally, the relati- ve belief reducts and relative plausibility reducts in consistent and inconsiste
5、nt decision systems are respectively defined and are compared to the relative reducts, and relation- ships between the new reducts and relative reducts as well as generalized decision redu- cts are examined. Keywords: Belief function; Consistent sets; Decision systems; Information systems; Reducts;
6、Rough sets III 目录 摘要 . I Abstract . II 1 前言 . 1 1.1 粗糙集与属性约简的由来 . 1 1.2 证据理论的由来 . 1 1.3 论文组织结构 . 1 2 信息系统、粗糙集与证据理论的基本概念 . 3 2.1 信息系统和粗糙集 . 3 2.2 证据理论 . 5 3 随机信息系统中的知识约简 . 7 4 随机决策系统的知识约简 .11 4.1 协调随机决策系统下的知识约简 .11 4.2 不协调随机决策系统下的知识约简 . 17 5 小结 . 21 参考文献 . 22 致谢 . 错误 !未定义书签。 1 1 前言 1.1 粗糙集与属性约简的由来 粗糙
7、集理论 14是波兰数学家 Pawlak 于 1982 年提出的用于数据分析的理论 , 常用于处理模糊和不精确的问题 . 利用粗糙集理论中的上、下近似 5的概念 , 可以很好地把信息系统中的知识用决策规则 6,7的形式表达出来 . 目前 , 粗糙集理论已在机器学习、知识发现、过程控制、数据挖掘、决策分析、模式识别等领域得到广泛应用 , 成为一个新的学术热点 . 经典粗糙集理论的主要思想是以等价关 系（自反性 、 对称性 、 传递性）为基础 , 通过定义上 、 下近似来描述知识的不确定性 . 在完备信息系统中 , 这种模型被成功地运用在知识约简 , 导出问题的分类或决策规则等方面 . 知识约简是粗
8、糙集理论的核心内容之一 . 对一个信息系统来说 , 知识库中属性并不是同等重要的 , 甚至其中某些属性是冗余的 . 所谓知识约简就是在知识库分类能力不变的条件下 , 删除其中不重要或不相关的属性特别是 , 当信息系统中的数据是随机采集时 , 其冗余性更为普遍 . 属性约简是数据挖掘中的一种粗糙集方法 , 它决定了能代表整个信息系统的重要属性的集合 . 一般地讲 , 一个信息系统的 属性约简 不是唯一的 , 人们希望找到具有最少属性的约简 , 即最小约简 . 然而 , 要找到一个信息系统的最小约简是一个 NP-hard 问题 . 不过 , 在实际应用中 , 要求得到 某些 属性约简就可以了 .
9、许多研究人员己提出了属性约简算法 . 利用可辨识属性矩阵 , 确定了信息系统的核心属性和去掉绝对不必要属性 , 并给出一个由可辨识属性矩阵求信息系统的一个约简的简便算法 . 1.2 证据理论的由来 D-S 证据理论是由 Dempster 于 1967 年提出 , 他首先提出了上、下概率 8的定义 , 后由Shafer9于 1976 年使之系统化、理论化 , 形成了一种不确定性推理的理论 , 即 D-S 理论 . 该理论的基本代表结构是一个信任结构 . 由信任结构导出的数量测度是一对信任函数和似然函数 . 证据理论是一种重要的不确定推理方法 , 近年来该理论有了很大发展 , 正受到不同领域的学者
10、越来越多的关注 . 粗糙集理论与证据理论之间有着密切的关系 . 结合信任结构和粗糙集近似空间 , 从而可以用粗糙集近似空间中的上、下近似算子来说明对应的信任结构中的信任函数和似然函数 . 1.3 论文组织结构 本文在前言部分介绍了有关粗糙集、属性 约简和证据理论的背景 , 并提出了基于经典粗2 糙集数据分析的约简 , 该约简只使用了内部知识 , 没有依靠先验模型假设 . 且可用的数据库可以通过随机分组方法得到 . 在这个基础上 , 本文将研究随机信息系统中的知识约简问题 . 由于证据理论与粗糙集理论之间有着密切的关系 , 所以我们主要研究信息系统中基于证据理论的属性约简 . 在第二部分 , 给
11、出了信息系统、粗糙集和证据理论的基本概念 . 在第三部分 , 介绍了随机信息系统中的信任约简和似然约简 . 而在第四部分 , 研究了协调决策系统和不协调决策系统中的相对信任约简和似然约简 , 并 讨论了信息系统和决策表中的约简、相对约简、广义决策约简与信任约简和似然约简之间的关系 . 3 2 信息系统、粗糙集与证据理论的基本概念 2.1 信息系统和粗糙集 一个信息系统是一个二元组 ( , )UA, 其中 12, ,., nU x x x 是非空有限集合 , 称为论域 . 12, ,. , mA a a a 是一个非空的有限属性集 , 对任意的 aA , 有 : aa U V , 其中 aV是
12、a 的值域 . 每个非空子集 BA 决定了一个不可辨别关系如下 ( , ) : ( ) ( ) ,BR x y U U a x a y a B . BR 是 U 上 的一个等价关系 , 产生了 U 中的一个划分 :B BU R x x U， 其中 Bx 表示为由 x 关于 B 决定的等价类 , 即 : ( , ) BBx y U x y R . 例 2.1 表 2.1给出了 一个信息系统 ( , )UA, 其中 1 2 10, ,. ,U x x x , 1 2 3,A a a a . 可以计算出 1 2 5, , .,AU R C C C ， 其中 1 1 3 9= , ,C x x x ,
13、 2 2 7 10= , ,C x x x , 34=Cx, 4 5 8=,C x x , 56=Cx. 设 ( , )UA是一个信息系统 , 对任意的 XU , BA , 定义 :B BR X x U x X , :B BR X x U x X . ()BRX和 ()BRX分别表示 X 关于 BR 的下近似和上近似 . 若 ( ) ( )BBR X R X , 则称 X 为可定义集 . 若 ( ) ( )BBR X R X, 则称 X 为粗糙集 . 一个决策系统（通常也叫决策表） ,S U C d , 其中 ( , )UC 是一个信息系统 , dC 是一个决策属性 , 在这种情况下 , C
14、称为条件属性集 , d 是论域 U 到值集 dV 的一个映射 , 即 : dd U V , 一般地 , 假设 1, 2,.,dVr . 对任意的 BC , 定义 ( ) ( ) :B Bx d y y x , xU . 4 表 2.1 信息系统 U 1a 2a 3a 1x 2 1 3 2x 3 2 1 3x 2 1 3 4x 2 2 3 5x 1 1 4 6x 1 1 2 7x 3 2 1 8x 1 1 4 9x 2 1 3 10x 3 2 1 称 ()Bx 为 S 中的 x 关于 B 的广义决策值 , 且 B 是 S 中关于 B 的决策函数 10. 对任何xU （ X 表示集合 X 的基数）
15、 , 若 ( ) 1C x, 则决策系统 ,U C d 是协调的 , 否则 , 称这个系统是不协调的 . 定义 ( , ) : ( ) ( )dR x y U U d x d y . 我们得到决策类 U 中的一个划分 12, , . ,drU R D D D , 其中 : ( )j x U d x j , jr . 因此 , 可以得到决策系统 ,U C d 是协调的当且仅当 CdRR . 我们可以从协调决策系统中获得确定性决策规则 , 从不协调决策系统中获得不确定性决策规则 . 事实上 , 若 ( ) 1C x, 则相对于类 Cx 的决策规则是确定的 , 若 ( ) 2C x, 则相对于类 C
16、x 的决策规则是不确定的 . 如果 P 是 U 上正则概率测度 , 即对任意的 xU , 有 ( ) 0Px 且 ( ) 1xUPx , 那么称 ( , , )UPA 是一个随机信息系统 . 同样地 , 称 ,U P C d 是一个随机 决策系统 , 其中 ,U C d 是一个决策系统 . 在对任何的 xU , 特殊概率 ( ) 1P x U 的情况下 , 可称经典信息系统为一个随机信息系统 . 5 2.2 证据理论 定义 2.19 设 U 是一个非空有限集合 , P( )U 是 U 中所有子集的全体 , 0,1I 是单位区间 , 称一个集合函数 m ： ()UI为 mass函数 , 若满足以
17、下公理 (M1) ( ) 0m ; (M2) ( ) 1XUmX . 若 ( ) 0mX , 则称 X 为一个焦元 . 我们用 M 表示 m 中的所有焦元素 . 一组 ( , )Mm是一个信任结构 . 根据每个信任结构 , 可以导出一组信任函数和似然函数 . 定义 2.211 令 ( , )Mm是一个信任结构 , 称集合函数 : ( )Bel U I为 U 上的信任函数 , 当 ( ) ( )MXBel X m M , ()XU . 称集合函数 : ( )Pl U I为 U 上的一个似然函数 , 当 ( ) ( )MXPl X m M , ()XU . 基于同一个信任结构的信任函数和似然函数具
18、有对偶性 ( ) 1 ( )Pl X Bel X 此外 , 对所有的 ()XU , ( ) ( )Bel X Pl X . 粗糙集理论与 D-S证据理论之间有着很强的联系 , 接下来的定理说明了经典的信任函数和似然函数可以通过 Pawlak的集合下近似和上近似来表示 . 定理 2.111 设 ( , , )UPA 是一个随机信息系统 , BA , 对任意的 XU , 记 ( ) ( )BBBel X P R X , ( ) ( )BBPl X P R X . 则 BBel 和 BPl 分别是 U 上的信任函数和似然函数 , 相应的 mass函数为 ( ) , ,() 0 , BBP Y Y U
19、 RmY 若其 它 .在这种情况下 , 这些焦元素互不相交 . 6 推论 2.1 设三元组 ( , , )UPA 是一个随机信息系统 , B B A , 对任意的 XU ( ) ( ) ( ) ( )B B B BB e l X B e l X P X P l X P l X . 证明 因为 B B A, 所以由上、下近似的定义可知 ( ) ( )BBR X R X , ( ) ( )BBR X R X , ( ) ( )BBR X X R X . 则可得 ( ) ( )BBP R X P R X , ( ) ( )BBP R X P R X , ( ) ( ) ( )P R X P X P R X. 因此 ( ) ( ) ( ) ( ) ( )B B B BP R X P R X P X P R X P R X . 由定理 2.1知 ()BBBel X P R X , ( ) ( )BBBel X P R X , ( ) ( )BBPl X P R X , ( ) ( )BBPl X P R X . 所以 , ( ) ( ) ( ) ( )B B B BB e l X B e l X P X P l X P l X .
