1、 本科毕业论文 （ 20 届） 粗糙集与证据理论的关系研究 所在学院 专业班级 信息与计算科学 学生姓名 学号 指导教师 职称 完成日期 年 月 摘要 本文主要研究粗糙集近似与证据理论之间的关系 . 首先 , 介绍粗糙集的基本概念 . 粗糙集理论是一种处理不精确、不确定和不完备信息 的数据分析方法 . 其次 , 回顾证据结构及其导出的信任函数与似然函数的定义 , 给出信任函数和似然函数的一些基本性质 . 证据理论是处理不确定性问题的有力工具 , 作为一种常用的信息融合方法 , 对解决信息融合中不确定性问题具有显著的优势 . 最后研究粗糙集理论中的下近似和上近似与证据理论中信任函数与似然函数之间
2、的联系 . 关键词： 粗糙集理论 ; 证据理论 ; 信任函数 ; 似然函数 II Abstract Rough set theory and evidence theory are two important tools in data analysis dealing with imprecise, inconsistent and incomplete information. In rough set theory there exists a pair of approximation operators, the upper and lower approximations, whe
3、reas in evidence theory there exists a dual pair of uncertainty measures, the plausibility and belief functions. In this thesis, we mainly focus on the study of relationships between rough set and evidence theory. Some basic notions related to rough sets are first reviewed. Belief structures with th
4、eir induced belief functions and plausibility functions are then defined, and some basic properties of belief functions and plausilibility functions are presented. Finally, relationships between lower approximations and upper approximations of rough set theory and belief functions and plausibility f
5、unctions of evidence theory are discussed. It is demonstrated that various belief structures are associated with various rough approximation spaces such that different dual pairs of upper and lower approximation operators induced by the rough approximation spaces may be used to interpret the corresp
6、onding dual pairs of plausibility and belief functions induced by the belief structures. Keywords: Rough sets; Approximation operators; Evidence theory; Belief functions; Plausibility functions III 目录 摘要 .I Abstract . II 1 前 言 . 1 2 粗糙集 . 3 3 随机集 . 5 4 证据理论 . 9 4.1 证据理论与信 任测度 . 9 4.2 证据理论与可能性测度 . 10
7、 5 粗糙集与证据理论的关系 . 14 5.1 Pawlak 粗糙集代数 . 14 5.2 串行粗糙集代数 . 14 5.3 区间粗糙集代数 . 15 5.4 随机粗糙集代数 . 16 5.5 随机粗糙模糊集代数 . 17 5.6 随机模糊粗糙集代数 . 18 5.7 定理的证明 . 21 6 小结 . 25 参考文献 . 26 致谢 .错误 !未定义书签。 东海科学技术学院本科毕业论文 1 1 前 言 在计算机与网络信息技术飞速发展的今天 , 各个领域的信息与数据急速增加 (信息爆炸 ), 并且由于人类的参与使数据与信息中 的不确定性更加显著 , 信息与数据中的关系更加复杂 (复杂系统 ).
8、 如何从大量的、杂乱无章的、强干扰的数据 (海量数据 )中挖掘潜在的、新颖的、正确的、有利用价值知识 (有用知识 ), 这给智能信息处理提出了严峻的挑战 , 由此产生了人工智能研究的一个崭新领域 数据挖掘 (Data Mining, DM)和数据库知识发现(KDD). 同样是基于数据库的知识发现 , 有着完全不同的方法 , 使用着完全不同的数学工具 . 比如基于网络结构的神经网络算法 , 基于训练选优的遗传算法 , 基于统计理论的数据挖掘与支持向量机方法 , 基于归纳 学习的机器学习方法 , 基于范例的推理方法 , 基于生物信息的知识发现方法等 . 粗糙集 13 (Rough Set, RS)
9、理论与方法对于处理复杂信息系统不失为一种有效的方法 . 粗糙集作为处理不精确 , 不确定与不完全数据的理论是由波兰数学家 Pawlak 于 1982 年提出的 . 该理论是经典集合论的又一推广形式 . 其主要思想就是在保持分类能力不变的前提下 , 通过知识约简 , 导出问题的决策或分类规则 . 在 20 世纪 80 年代初 , 粗糙集理论的研究人员主要局限在东欧各国 , 因此 当时没有引起国际学术界的重视 . 到了 20 世纪 90 年代 , 由于该理论在人工智能领域的成功应用 , 特别是 1991 年 Pawlak 出版粗糙集的第一本专著以来 , 这个理论引起了世界各国学者的广泛注意 . 从
10、 1992 年至今 , 每年都召开以 Rough Set 为主题的国际会议 , 国际上成立了粗糙集学术研究会 , 并在 Internet 上定期发布电子公告 , 加速了粗糙集理论的发展与交流 . 由于粗糙集理论能够分析处理不精确 , 不协调和不完备信息 , 因此作为一种具有极大潜力和有效的知识获取工具受到了人工智能工作者的广泛关注 . 目前 , 粗糙集理论已被成功地应用在机器学习与知识发现 , 数据挖掘 , 决策支持与分析 , 过程控制 , 模式识别等计算机领域 . 基于随机集的信任结构可以产生一对数值型的测度 : 信任测度与似然测度 . 而由于粗糙集理论的核心算子是从近似空间导出的一对非数值
11、型算子 : 上近似算子与下近似算子 . 这两者之间是否有某些必然的联系 ? 事实上 , 粗糙集理论问世不久这个问题就引起了人们的关注 . 人们很快发现一个集合关于 Pawlak 近似空间的上、下近似的概率 (或上、下近似质量 )2 就是一对对偶的似然测度与信任测度 . 后来进一步研究表明各类推广 的 (经典 )粗糙集模型中的上、下近似概率 (或上、下近似质量 )也是一对对偶的似然测度与信任测度 . 反之对于一对给定的 (经典 )似然测度与信任测度 , 必能找到一个近似空间 , 使由这个近似空间导出的上、下近似质量恰好就是给定的似然测度与信任测度 . 于是粗糙集理论成了 D-S 证据理论的基础
12、, 而 D-S 证据理论又为粗糙集的不确定分析提供了一个很好的也非常合理的工具与解释 ,比如在粗糙集理论用于决策过程中可以抽取带有一定的信任度与似然度的决策规则 . 粗糙集和证据理论在处理不确定性和不精确性问题方面都推广了经典集合论 , 它们都可以用来描述知识的不精确性和不完全性 , 然而它们的侧重面不同 , 从知识描述的方法上来看 , 模糊集是通过对象关于集合的隶属程度来近似描述的 , 而粗糙集是通过一个集合关于某个已知的可利用的信息库 (近似空间 )的一对上、下近似来描述的 ; 从集合的对象间的关系来看 , 模糊集强调的是集合边界的病态定义 , 即边界的不分明性 , 而粗糙集强调的是集合对
13、象间的不可分辨 ; 从研究对象的角度来看 , 模糊集研究的是属于同一类的不同对象的隶属关系 , 重在隶属程度 , 而粗糙集研究的是不同类中的对象组成的集合之间的关系 , 重在分类 . 正 因为这两个理论的特点不同 , 它们有很强的互动性 . 在模糊环境中得到了粗糙模糊集与模糊粗糙集 . 而随机集所反映的问题主要是由随机原因引起的不确定性 . 在模糊集理论中要得到模糊概念的隶属函数有时是很困难的，而其中较好的方法是用集值统计的方法通过某个随机集及其伴随的概率测度得到 , 而基于粗糙集的粗糙隶属函数却是很容易得到的 . 对粗糙集理论的研究主要集中在 : 粗糙集模型的推广 , 问题的不确定性研究 ,
14、 与其他处理不确定性和模糊性问题的属性理论的关系与互补 , 纯粹的数学理论方面的研究 , 粗糙集的算法研究以及与人工智能其 他方向关系的研究等 . 本文主要研究粗糙集近似与证据理论之间的关系 . 首先 , 介绍粗糙集的基本概念 . 粗糙集理论是一种处理不精确、不确定和不完备信息的数据分析方法 . 其次 , 回顾证据结构及其导出的信任函数与似然函数的定义 , 给出信任函数和似然函数的一些基本性质 . 证据理论是处理不确定性问题的有力工具 , 作为一种常用的信息融合方法 , 对解决信息融合中不确定性问题具有显著的优势 . 最后研究粗糙集理论中的下近似和上近似与证据理论中信任函数与似然函数之间的联系
15、 . 3 2 粗糙集 粗糙集理论作为一种处理不精确、不确定与不完 全 数据 的 新的 数 学理 论最初是由波兰数学家 1Pawlak 于 1982 年 提 出的 该 理论 将 知识 理 解 为对 数 据的划分 , 每 一被 划 分的 集 合称 为 概念 ； 该 理 论的 主 要思 想 是利 用 已知 的 知识 库 , 将不 精 确或 不 确定 的 知识 用 知识 库 中的 知 识来 近 似 刻画 ； 该理 论 与其 他处理不确性问题的理论的最显著的区别 , 是它无需提供问题所需处理的数据集合之外的任何先验信息 , 对问题的不确性描述和处理比较客观 . 目前 , 该理论及其应用已成为信息科学研究
16、的一个热点 , 并且已在医学 、生物学、化学、材料学、地理学、管理科学等其他学科得到了成功的应用 . 定义 2.1 设 U 是非空有限论域 , R U U是 U 上的二元等价关系 , 对 ( , )A U R称为 Pawlak近似空间 , 商集 /UR中的集合称为基本集 . XU, X 关于近似空间( , )A U R 的一对下近似 RX 和上近似 RX 定义为 R X x U x X , R X x U x X . 其中 x 是 x 所在的 R 等价类 , 下近似 RX 也称为 X 关于 A 的正域 , 记为 ()POS X , 它可以解释为由那些根据现有知识 A 判断 出肯定属于 X 的对
17、象所组成的最大集合 , 上近似RX 可以解释为根据现有知识 A 判断可能属于 X 的对象所组成的最小集合 . 当 RX RX时 , 称 X 关于近似空间 A 是可定义的 , 否则称 X 关于 A 是粗糙的 , 简称是粗糙集 . 定义 2.2 设 UW和 是两个有限非空集合 , ( ,2 , )UUP为概率空间 , 若 集值函数:2WFU 是关于 2 (2 )UW 可测的 , 则称 F 为 随 机 集 , 称 四 元 有 序 组( , , , )A U W F P 为随机集近似空间 , 2WX , 定义 X 关于近似空间 A 的下近似 AX 和上近似 AX 为 ( ) , ( ) .A X u
18、U F u XA X u U F u X 4 当 AX AX 时称 X 关于近似空间是可定义的 , 否则称 X 关于近似空间 A 是不可定义的或粗糙的 . 注 2.1 基于随机集的粗糙集 A 和 A 的定义可以说是相当一般化 , 它一方面适用于知识库的获得很可能是随机的 , 另一方面直接从信号的接收或根据属性的值得到了对象的分类 ，应用更加广泛 . 又当 WU 时 ,RU为 上等价关系且 ( ) F u u 时 , 就退化为 Pawlak粗糙集 . 由定义 2.2, 容易证明下述定理 定理 2.1 设 :2WFU 是随机集 , 且 ()Fu , uU , 则 AA和 满足下列性质 (1) (
19、) , ( ) , ,A X A X A X A X X W 其中 指取集合补 ; (2) ,;A A A W A W U (3) ( ) , ( ) , ,A X Y A X A Y A X Y A X A Y X Y W ; (4) ,X Y W A X A Y A X A Y ; (5) ( ) , ( ) , ,A X Y A X A Y A X Y A X A Y X Y W . 定义 2.3 对于随机集 :2WFU , 记 ( ) ( ) ,j X u U F u X X W 若 ( ) ,jX 则称 Xj为 的焦点集 ，记全体焦点集为 J ， 即 2 ( ) WJ X j X 证
20、明方法类似于文献 6. 定理 2.2 设 :2WFU 为随机集 , 则下列性质成立 （ 1） ()AWj A U ; （ 2） , , ( ) ( )A B A B W j A j B ; （ 3） ( ) ,YXA X j Y X W; （ 4） ( ) ,YXA X j Y X W; （ 5） ( ) , ,YXj X A X A X X W 指取真子集 . 5 3 随 机集 定理 3.1 设 0: ( , , ) ( )F U P P W是随机集 , 则近似算子 F 和 F 满足下列性质 , , ( )X Y P W , 有 (1) ( ) ( )F X F X , (1 ) ( ) (
21、 )F X F X ; (2 ) ()F W U , ( 2 ) ()F ; (3 ) ( ) ( ) ( )F X Y F X F Y , (3 ) 22( ) ( ) ( )F X Y F X F Y a b; (4 ) ( ) ( )X Y F X F Y , ( 4 ) ( ) ( )X Y F X F Y ; (5 ) ( ) ( ) ( )F X Y F X F Y , (5 ) ( ) ( ) ( )F X Y F X F Y ; (6 ) ()F , (6 ) ()F W U ; (7 ) ( ) ( ).F X F X 证明 由定义 2.2 直接可得 . 性质 (1)与 (1
22、 )称为随机近似算子的对偶性质 , 有时具有相同数字标号的性质也可以看成是对偶性质 . 特别需要指出的是 , 其中三个性质 (6)、 (6 )和 (7 )是等价的 , 它们刻画了随机集6 这个集值函数取值必须为非空的特性 , 即有 定理 3.27 若 : ( )F U P W 是一个集值函数 , FF和 是以（ 3.1）式给出的近似算子 , 则以下等价 (1) 对于任意 uU , 有 ()Fu ; (2) 对任意 XW , ( ) ( )F X F X ; (3) ()F ; (4) ()F W U . 证明 “(1) (2) ”由定理 3.1 得 . “(2) (1) ”反证 ,若 uU 使
23、 ()Fu , 则对于任意 XW , 有 ()F u X , 即()u F X , 但是 ()F u X , 于是 ()F u X , 于是 ()u F X , 这与（ 2）成立矛盾 . “(2) (3)” 事 实 上 ， 由 定 理 3.1 的 对 偶 性 质 (1),(1) 和 性 质 (3) 可得( ) ( ) ( ) ( ( ) )( ) ( )( ( ) )( ) .F X F X F X F XF X F XF X XF “(3) (4) ”由定理 3.1 的对偶性质 (1) (1)与 可得 ( ) ( ) ( ) ( )F F F W F W U . 定义 3.1 设 0: ( , , ) ( )F U P P U是随机集 , 对于 uU , 若 ()u Fu , 则称 u 是 F的不动点 . 定理 3.3 设 0: ( , , ) ( )F U P P U是随机集 , 则以下等价 （ 1）任意的 uU 都是 F 的不动点 ;
