粗糙集与Bayes决策规则【毕业论文】.doc

1、 本科毕业论文 （ 20 届） 粗糙集与 Bayes决策规则 所在学院 专业班级 数学与应用数学 学生姓名 学号 指导教师 职称 完成日期 年 月 I 摘要 粗糙集理论是一种研究不完整、不确定知识处理的数学工具 , 近几年来在机器学习、知识发现、算法研究、工程应用、决策支持系统以及模 式识别等应用中取得了较好的成果 . 本文主要研究粗糙集与 Bayes决策规则 , Byes概率理论在完备决策系统中决策规则提取的应用 . 首先 , 回顾 了 粗糙集理论的基本概念 . 其次 , 介绍了条件概率的定义及其性质 . 最后研究了粗糙集与 Bayes 决策规则 . 研究了决策表基于 Bayes 概率的决策

2、规则获取方法 . 在粗糙集的理论中 , 每个决策规则都对应信任因子和覆盖因子 , 这两个因子可以表示为两个条件概率 . 此外 , 研究结果表明这两个因子满足 Bayes 定理 . 这就意味着我们可以用数据分析研究Bayes 推理规则且不需要涉及 Bayes 定理中的先验和后验概率 . 关键词 : Bayes 规 则 ; 粗糙集 ; 决策规则 ; 信息系统 II Rough Sets with Bayes Decision Rule Abstract Rough set theory is a mathematical tool to study incomplete and uncertain

3、 knowledge processing. In recent years, it has been successfully applied in many research fields such as machine learning, knowledge discovery, algorithm research, engineering application, decision support systems, and pattern recognition etc. In this thesis, we mainly focus on the study of rough se

4、ts with Bayes decision rules. Basic notions related to rough sets, information systems, and decision tables are first reviewed. The definition of conditional probability and its properties are then introduced. Finally, we investigate the approach of rule acquisition in complete decision tables based

5、 on the Bayes probability theory. In the rough set theory, with every decision rule, two conditional probabilities, called certainty factor and coverage factor, are associated. Besides, it is revealed that the two factors satisfy the Bayesian theorem. That means that we can use the two factors to an

6、alyze the Bayes rules in decision tables without referring to the prior and posterior probabilities of the Bayesian theorem. Keywords: Bayes rule; Rough sets; Decision rules; Information system III 目录 摘要 .I Abstract. II 1 前言 . 1 1.1 粗糙集的由来和发展 . 1 1.2 Bayes理论的由来和发展 . 1 1.3 论文的组织结构 . 2 2 粗糙集理论的基本概念 .

7、3 2.1 知识与知识库 . 3 2.2 不确定范畴 , 近似与粗糙集 . 3 2.3 知识约简 . 4 2.4 知识表达系统 . 4 2.5 决策表 . 6 3 条件概率 . 7 3.1 条件概率的定义 . 7 3.2 全概率公式 . 8 3.3 Bayes公式 . 8 4 粗糙集与 Bayes决策规则 . 9 4.1 决策规则 . 9 4.2 决策算法及其性质 . 10 4.3 决策规则和粗糙集的近似 . 11 4.4 决策规则和 Bayes决策 规则 . 13 4.5 对决策规则的信任因子和覆盖因子决策规则的解释 . 15 5 小结 . 25 参考文献 . 26 致谢 . 27 1 1

8、前言 1.1 粗糙集的由来和发展 粗糙集理论是波兰数学家 Pawlak Z1 于 1982 年提出的一种数据分析理论 . 在这之后 , 许多数学家 , 计算机研究人员和逻辑学家对粗糙集产生了很大的兴趣 , 并且在粗糙集的理论和应用方面做了大量的研究 . 1991 年 , Pawlak Z2 的专著 问世 , 标志着粗糙集理论及其应用的研究进入了活跃时期 . 1992 年 , 在波兰召开了关于粗糙集理论的第一届国际学术会议 . 1995 年 , ACM Communication 将其列为新浮现的计算机科学的研究课题 . 1998 年 , 国际信息科学杂志 (Infomation Science

9、s)还为粗糙集理论的研究出了一期专辑 . 这些都促进了粗糙集的发展 . 粗 糙集理论是一种 用来 刻 画 不完整性和不确定性的数学工具 , 能有效地分析不精确 , 不一致 , 不完整等各种不完备的信息 . 粗糙集理论将知识理解为使用等价关系集对有限非空论域进行划分 , 它的主要思想是将不确定或不精确的知识用已知的知 识库中的知识来近似刻画 , 在不损失信息的前提下 , 约简信息属性及属性值 , 获得相应的决策规则 3 . 粗糙集的实用性很强 , 粗糙集从产生到现在虽然只有短短的十几年时间 , 但是它在机器学习与知识发现 2 , 数据挖掘 4 , 决策支持与分析 5 等方面已经取得了很多的成果

10、. 粗糙集理论的研究逐渐趋于热化 . 但是 , 针对 粗糙集在数据处理方法的方法上 , 缺乏一些关键数据和信息的支持 , 并且 , 当关键的信息缺省比较多的时候 , 将影响其在实际应用中的决策效率 , 而且有可能会做出错误的判断 . 如果把 Bayes理论引入到粗糙集中 , 可以显著提高决策能力 . Bayes决策理论既可以一次处理整个的数据集 , 也可以一次只处理某一个数据 . 利用 Bayes 原理中的先验概率来分析引发该结果的主要因素以及该因素所起作用的大小 . 该方法不但避免了单纯 Bayes理论的计算的繁琐性 , 而且也克服了粗糙集刚性推理的弱点 . 1.2 Bayes 理论的由来和

11、 发展 自从 20 世纪 50-60 年代 , Bayes 学派形成之后 , 关于 Bayes 的研究日趋火热 . 20 世纪 80年代后 , Bayes 网络就成功地应用于专家系统 , 成为表示不确定性专家知识和推理的一种重要的方法 . Bayes决策理论是主观 Bayes派归纳理论的重要组成部分 . 有三位学者对 Bayes决策理论的建立作出了重要贡献 , 他们是 Ramsey E P, Savage L J, Jeffrey R L. Savage J 系统地研究了决策理论 . Bayes 理论提供了一种计算假设概率的方法 , 它基于先验概率 , 在给定 假2 设下观察到不同数据的概率以

12、及观察到数据本身 . Bayes 推理为衡量多个假设的信任度提供了定量的方法 . Bayes决策是通过 Bayes先验概率分析思想构造的决策方法 , 其核心是利用事件发生的先验概率计算后验概率 , 获得最优决策方案 6 . Bayes 推理在过去近 30 年中得到了较为广泛的研究 , 特别 的是 自 Kahneman 和 Tversky发现人们直觉的概率判断忽略基础概率现象以来 , 出现了许多理论和研究方法的更新 , 这些都深化了对这一问题的研究 . Bayes 决策 方法作为 一种风险型决策方法 , 在实际中的应用较广泛 . 它在会计决策 7 , 房地产风险决策 8 , 企业重要的经营决策等

13、方面的应用都有研究 . 1.3 论文的组织结构 本文主要 研究了粗糙集与 Bayes决策规则 . 本文是对 9 的扩展的构想 . 本文第一部分回顾了粗糙集与 Bayes 理论的由来和发展 . 第二部分 回顾了 粗糙集理论的基本概念 . 第三部分介绍了条件概率的基本概念 . 第四部分是本文的核心 , 介绍了粗糙集与 Bayes 决策规则 . 说明利用数据分析证明 Bayes 推理规则不需要涉及 Bayes 定理的先验和后验概率 . 3 2 粗糙集理论的基本概念 粗糙集理论是一种处理模糊和不确定性知识的数学工具 . 主要思想是将不确定或不精确的知识用已知的知识库中的知识来近似刻画 , 在不损失信息

14、的前提下 , 约简信息属性及属性值 , 获得相应的决策规则 . 目前 , 粗糙集理论已被成功地应用于就机器学习与知识发现 , 数据挖掘 , 决策支持与分析 . 2.1 知识与知识库 设 U 是我们感兴趣的对象组成的有限集合 , 称为论域 . 任何子集 XU , 称为 U中的一个概念或范畴 . 我们认为空集也是一个概念 . U 中任何概念族称为关于 U 的抽象知识 , 简称知识 . 本文主要是对在 U 上能形成划分的那些知识感兴趣 . 一个划分 12, , , nX X X ; iXU , iX , 对于 ij , ijXX , , 1, 2, ,i j n ; 1n ii XU . U 上的一

15、族划分称为关于 U 的一个知识库 . 设 B 是 U 上的一个等价关系 , /UB表示 B 的所有等价类构成的集合 , ()Bx表示包含元素 xU 的 B 等价类 . 一个知识库就是一个系 统 ( ,B)KU , 其中 U 为非空有限集 , 称为论域 , B 是 U 上的一族等价关系 . 2.2 不确定范畴 , 近似与粗糙集 令 XU , B 是 U 上的一个等价关系 . 当 X 能表达成某些 B 基本范畴的并时 , 称为X 是 B 可定义的 ; 否则称为 X 为 B 不可定义的 . B 可定义集是论域的子集 , 它在知识库 K 中精确地定义 , 而 B 不可定义集不能在这个知识库中定义 .

16、B 可定义集也称作 B 精确集 , 而 B 不可定义集称为 B 非精确集或 B 粗糙集 . 用粗糙集的上下近似精确集 , 近似地定义粗糙集 . 定义 2.1 10 给定知识库 ( ,B)KU , 对于每个子集 XU 和一个等价关系()B ind K , 有两个子集 * ( ) ( ) : ( )xUB X B x B x X, * ( ) ( ) : ( )xUB X B x B x X . 分别称他们为 X 的 B 下近似集和 B 上近似集 ; 4 * *( ) ( ) ( )BB N X B X B X 称为 X 的 B 边界域 ; *( ) ( )Bpos X B X 称为 X 的 B

17、正域 ; *( ) ( )Bneg X U B X 称为 X 的 B 负域 . 显然 * ( ) ( ) ( )BBB X p o s X B N X . 2.3 知识约简 粗糙集理论的核心内容之一是知识约简 . 知识库中的知识 (属性 )不是同等重要的 , 可能某些知识是冗余的 . 知识约简 , 就是在保持知识库的分类能力不变的条件之下 , 删除不重要的知识 . 约简和核是知识约简中的两个基本概念 . 定义 2.210 令 B 为一族等价关系 , BB , 如果 ( B ) ( B )ind ind B, 那么称 B 为 B 中不必要的 ; 否则称 B 为 B 中必要的 . 如果每一个 BB

18、 都为 B 中必要的 , 那么称 B 为独立的 ; 否则称 B 为依赖的 . 定义 2.310 如果 B 是独立的 , PB , 那么 P 也是独立的 . 定义 2.410 核的定义如下 (P ) (P )core red , 其中 (P)red 表示 P 的所有约简 . 定义 2.510 相对核与相对约简的关系 , 有 (P ) (P )QQcore red , (P)Qred 表示 P 的所有约简构成的集合 . 2.4 知识表达系统 形式上 , 四元组 ( , , , )S U A V f 称为一个知识表达系统 , 其中 5 U 是非空有限对象集合 , 称为论域 ; A 是非空有限属性集合

19、 ; aaAVV, aV 是属性 a 的值域 ; f : U A V是一个信息函数 , 为每个对象的每个属性赋予一个信息值 , 即 aA , xU , ( , ) af x a V . 知识表达系统也称信息系统 , 通常也是用 ( , )S U A 来代替 ( , , , )S U A V f . 关系表可以表示知识表达系统 . 关系表的行对应研究的对象 , 列 对应对象的属性 , 指定对象的各属性值表达对象的信息 . 例 2.1 表 2.1是一个关于某些病人的知识表达系统 , 其中 表 2.1病人的知识表达系统 病人 头痛 肌肉痛 体温 1e 是 是 正常 2e 是 是 高 3e 是 是 很

20、高 4e 否 是 正常 5e 否 否 高 6e 否 是 很高 1 2 3 4 5 6e , e e , e , e eU , A 头痛 , 肌肉痛 , 体温 . 令 PA , 定义属性集 P 的不可区分关系 ()indP 为 ( ) ( , ) | , ( , ) ( , )in d P x y U U a P f x a f y a . 如果 ( , ) ( )x y ind P , 称 x 和 y 是 P 不可区分的 . 易证明 PA , 不可区分关系()indP 是 U 上的等价关系 , 符号 / ( )U ind P (简记为 /UP)表示不可区分关系 ()indP 在U 上导出的划分

21、 , ()indP 中的等价类称为 P 基本集 . Px 表示包含 xU 的 P 等价类 . 在上面这个例子中 , 如果取属 性集 P 头痛 , 肌肉痛 , 2 4 6e e ,eX , , 则有 1 2 3 4 6 5/ e , e e e , e eUP , ， ，. P 基本集为 1 2 3e ,e e, , 46e,e , 5e . 6 * 4 6( ) ( ) ,BB X p o s X e e, * 1 2 3 4 6( ) e , e e , e eBX , * 5( ) ( ) eBn eg X U B X , * * 1 2 3( ) ( ) ( ) e , e eBB N

22、X B X B X ,. 属性集 头痛 , 肌肉痛 , 体温 有一个约简 头痛 , 体温 , 头痛 , 体温 是核 . 2.5 决策表 决策表是一类特殊的知识表达系统 , 决策表可以表达多数决策问题 , 在决策应用中这一工具起着重要的作用 . 设 ( , , , )S U A V f 为一知识表达系统 , A C D , CD , C 为条件属性集 , D 为决策属性集 . 决策表是具有条件属性和决策属性的知识表达系统 . 例 2.2 表 2.2 是一个决策信息系统 (一个决策表 )的例子 . 表 2.2 决策信息系统 汽车 F P S M 1x 中 中 中 差 2x 高 中 大 差 3x 中 低 大 差 4x 低 中 中 好 5x 高 低 小 差 6x 中 低 大 好 表格包含的数据大约有六辆汽车 , F , P , S , M 分别表示燃油消耗 , 销售价格 , 尺寸和市场性 . 属性 F , P 与 S 是条件属性 , 而 M 是决策属性 . 表 2.2 中的每一行可以导出一个决策规则 .