1、 本科毕业论文 （ 20 届） 粗糙集与集分配函数 所在学院 专业班级 数学与应用数学 学生姓名 学号 指导教师 职称 完成日期 年 月 I 摘 要 粗糙集理论是一种新的处理模糊和不确定性知识的数学工具 , 也是一种新的软计算和数据分析方法 . 粗糙集理论收到广大人工智能工作者的高度 重视 . 本文首先回顾了粗糙集理论的基本知识 , 研究三种基于二元关系的粗糙集扩展模型的性质 , 并对它们进行了比较 . 重点研究了集分配函数 , 给出二元关系与集分配函数之间的一一对应关系 , 利用集分配函数刻画了各种类型的二元关系 . 建立了基于集分配函数的粗糙集近似算子 , 研究了近似算子的性质 , 然后给
2、出了集分配函数的粗糙近似算子刻画 . 关键词 : 粗糙集 ; 集分配函数 ; 二元关系 ; 算子刻画 II Rough Sets and Set Distribution Functions Abstract Rough Set Theory is a new mathematical tool dealing with ambiguous and uncertain knowledge, it is also a kind of new method of soft computing and data analysis. Rough set theory was paid high att
3、ention by researchers of artificial intelligence. In this thesis, the basic knowledge of the theory of rough sets is first reviewed, properties of three kinds of extended rough set models are investigated, and comparison is done subsequently. The focus of the thesis is on the set distribution functi
4、ons. The relationships between binary relations and set distribution functions are given, various types of binary relations are characterized by set distribution functions. The rough set approximation operators based on set distribution functions are constructed, the properties of the new operators
5、are discussed, and the characterizations of set distribution functions are given by means of the rough approximation operators. Keywords: Binary relations; Operator characterization; Set distribution functions; Rough set III 目 录 中文摘要 .I 英文摘要 . II 1 前言 . 1 2 粗糙 集理论基本概念 . 3 3 粗糙集模型的扩展与比较 . 6 3.1 两类基于后
6、继邻域的扩展模型 . 6 3.2 几类粗糙近似算子的关系 . 8 4 基于 集分配算子的粗糙集 . 9 4.1 二元关系与集分配函数 . 9 4.2 集分配算子与粗糙集 . 11 小结 . 14 参考文献 . 15 致谢 .错误 !未定义书签。 1 1 前言 智能信息处理是当前信息科学理论和应用研究中的一个热点领域 . 由于计算机科学 与技术的发展 , 特别是计算机网络的发展 , 每日每时为人们提供了大量的信息 . 信息量的不断增长 , 对信息分析工具的要求也越来越高 , 人们希望自动地从数据中获取其潜在的知识 . 特别是近 20 年间 , 知识发现（规则提取、数据挖掘、机器学习）受到人工智能
7、学界的广泛重视 , 知识发现的各种不同方法应运而生 . 粗糙集（ Rough Set 也称 Rough 集或粗集）理论 1是 Pawlak 教授于 1982 年提出的一种能够定量分析处理不精确、不一致、不完整信息与知识的数学工具 2. 粗糙集理论最初的原型来源于比较简单的信息模型 , 它的基本思想是通过关系数据库分类归纳形成概念和规则 3, 通过等价关系的分类以及分类对于目标的近似实现知识发现 . 由于粗糙集理论思想新颖、方法独特 , 粗糙集理论 4已成为一种重要的智能信息处理技术 , 该理论已经在机器学习与知识发现、数据挖掘、决策支持与分析等方面得到广泛应用 . 目前 , 有个有关粗糙集的系
8、列国际会议 , 即 RSCTC、 RSFDGrC 和 RSKT. 中国学者在这方面也取得了很大的成果 , 从 2001 年开始每年召开中国粗糙集与软计算学术会议 ; RSFDGRC2003、 IEEE GrC2005、 RSKT2006、 IFKT2008、 RSKT2008、 IEEEGrC2008 等 5一系列 国际 学术会议在中国召开 . 粗糙集理论与应用的核心基础是从近似空间导出的一对近似算子 , 即上近似算子和下近似算子（又称上、下近似集） . 经典 Pawlak 模型中的不分明关系是一种等价关系 , 要求很高 , 限制了粗糙集模型的应用 6. 因此 , 如何推广定义近似算子成为了粗
9、糙集理论研究的一个重点 . 目前 , 常见的关于推广粗糙集理论的研究方法有两种 , 即构造化方法和公理化方法 . 构造化方法是以论域上的二元关系、划分、覆盖、邻 域系统、布尔子代数等作为基本要素 7, 8, 进而定义粗糙近似算子 , 从而导出粗糙集代数系统 . 公理化方法的基本要素是一对满足某些公理的一元集合算子 , 近似算子的某些公理能保证有一些特殊类型的二元关系的存在 . 反过来 , 由二元关系通过构造性方法导出的近似算子一定满足某些公理 . 目前 , 对粗糙集的研究主要是集中在 : 粗糙集的模型推广、问题的不确定性研究、与其他处理不确定性和模糊性问题的数学理论的关系与互补、纯粹的数学理论
10、方面的研究、粗糙集的算法研究和与人工智能其他方向关系的研究等 .文 9-11分别介绍了Rough 集的研究现状和发展趋势、 Rough 集的基本概念及其理论基础、数据约简的各种方法、数据推理原理和各种推理模式 , firaitule 软计算、 Rough 逻辑及其推理系统等。文 12从算子2 的观点来解释粗糙集 , 在面向算子的观点中 , 上下近似被看作是论域幂集空间 U2 上的一对一元算子 L 和 H, 也就是说，粗糙集理论中研究的系统 U 2 , , , , L, HU 是标准集合系统 2 , , ,U 附加了两个近似算子的扩展 . 粗糙集理论是建立在分类机制的基础上的 , 它将分类理解为
11、在特定空间上的等价关系 , 而等价关系构成了对该空间的划分 . 粗糙集理论 是基于论域上的 划分 来展开的 . 但是实际问题中的知识大多时候不是对应论域上的一个等价关系 , 而是一个其他类型的二元关系或一般二元关系 . 因此研究基于一般关系的粗糙集非常必要 . 集分配函数的粗糙集的刻画是粗糙集理论研究的另一课题 , 在这 方面有许多问题有待深入研究 . 本文对粗糙集与集分配函数进行研究 , 研究有利于搞清楚各种粗糙集近似算子之间的关系 , 同时也有利于新算子在解决实际问题中的应用 . 本文旨在研究粗糙集与集分配函数 , 研究二元关系与集分配函数之间的关系 . 讨论粗糙集近似算子的基本性质 ,
12、给出集分配函数的粗糙集刻画 . 本文的第二部分首先回顾粗糙集理论中的基本概念 ; 第三部分介绍粗糙集模型的扩展 ; 第四部分二元关系与集分配函数之间的关系 ; 第五部分得出集分配算子与粗糙集之间的关系 , 给出集分配函数的粗糙集刻画 . 3 2 粗糙集理论基本概念 定义 2.1 1 设 U 是一个有限非空集合 , 称为论域 . UUR 是一个二元关系 . ( , )x y R 又记为 xRy , 称为 x 与 y 有关系 . 若对于任意的 Ux , 都有 xRx , 则称 R 是自反的 . 若对于任意 ,xy U , 都有 xRy 蕴含着 yRx , 则称 R 是对称的 . 若 对于任意 ,x
13、 y z U , xRy , yRz 蕴含着 xRz , 则 称 R 是传递的 . 如果 UUR 是自反的、对称的、传递的 , 则称 R 是等价关系 . 对于二元关系 R U U, xU , 令 ( ) | R x y U xRy , 称 ()Rx是元素 x 的后继邻域 . 令 ( ) | qR x y U yRx , 称 ()qRx是元素 x 的后前继 l邻域 . 定义 2.2 设 R 是 U 上的一个二元关系 , 称 ( , )UR 是一个一般近似空间 . 对于任意XU , 定义 X 在 ( , )UR 的上、下近似为 : ( ) | ( ) R A x U R x X , ) | ( )
14、 R A x U R x X . 近似算子 , : ( ) ( )R R P U P U 满足以下性质 : 命题 2.1 设 RU, 是一个一般近似空间 , 对于任意 ,XY U 有 0( ) ( ) ( )L R x R X ; 0( ) ( ) ( )U R X R X ; 1( ) ( )L R U U , 1()UR ; 2( ) ( ) ( )L X Y R X R Y , 2( ) ( ) ( )U X Y R X R Y ; 3( ) ( ) ( ) ( )L R X Y R X R Y, 3( ) ( ) ( ) ( )U R X Y R X R Y. 特别地 , 若 R 是
15、U 上的一个等价关系 , 记 ()Rx为 Rx , / | RU R x x U是 U 的一个划分 , 即 RRxx, ,x y U, 且 RxUxU . 此时 , 称 Rx 为包含 x 的等价类 . 例 2.1 设 ( , , | , | )aaU A V a A I a A t是一个 信息系统 , 其中 U 是有限非空集合 ,4 称为论域 , A 是非空有限集 , 其中的元素称为属性 , 对于属性 aA , aV 表示属性 a 的值域 , :aaI U V 为关系函数 , 称 xIa 是对象 x 的 a 属性值，又记为 ()ax . 对于表 1, 1 2 3 4 5 6 7 8 , , ,
16、 , , , , U x x x x x x x x , , , A ht hr ey , , htV st , , , hrV b r d , , eyV bl br . 这里 ht , hr , ey 分别表示“身高”、“发色”和“眼睛” . 属性值 s 和 t 分别表 示“矮”和“高” . 属性值 b 、 r 和 d 分别表示“金色”、“红色”和“黑色” . 属性值 bl 和 br 分别表示“蓝色”和“褐色” . 令 表 1 U ht hr ey 1xs b bl 2xs b br 3xt r bl 4xt d bl 5xt d bl 6xt b bl 7xt d bl 8xs b br
17、 ( , ) | , ( ) ( ) AR x y U U a A a x a y , 则 AR 是 U 上的一个等价关系 , 且 11 ARxx , 2 8 2 8 , AARRx x x x, 33 ARxx , 4 5 4 5 , AARRx x x x, 66 ARxx , 77 ARxx . 则 1 2 8 4 5 7/ , , , , , AU R x x x x x x . 若取 , B ht hr A, 令 2( , ) , ( ) ( ) BR x y U a B a x a y , 5 则 1 2 8 4 5 6 7/ , , , , , , BU R x x x x x
18、x x . 若 UUR 是一个等价关系 , 则称 RU, 是一个 Pawlak近似空间 . XU , 下 、上近似又可以定义为 : ( ) / | RRR X x U R x X , ( ) / | RRR X x U R x X . Pawlak粗糙集近似算子除满足命题 2.1中的性质外还满足以下性质 : 4( ) ( )L R X X , 4( ) ( )U X R X ; 5( ) ( ( )L X R R X , 5( ) ( ( )U R R X X; 6( ) ( ) ( ( )L R X R R X , 6( ) ( ( ) ( )U R R X R X. 关于特殊类型的二元关系
19、 , 可以用粗糙近似算子刻画如下 : 定理 2.2 3 设 R 是 U 上的任意一个二元关系 , 则以下命题等价： (1) R 是自反的 . (2) ()R X X , UX . (3) ()X R X , UX . 定理 2.3 3 设 R 是 U 上的任意一个二元关系 , R 是自反的 , 则 : ( ) ( )R X R X , UX . 定理 2.4 3 设 R 是 U 上的任意一个二元关系 , 则以下命题等价： (1) R 是传递的 . (2) ( ) ( ( )R X R R X , UX . (3) ( ( ) ( )R R X R X , UX . 定理 2.5 3 设 R 是
20、 U 上的任意一个二元关系 , 则以下命题等 价： (1) R 是对称的 . (2) ( ( )X R R X , UX . (3) ( ( )R R X X , UX . 6 3 粗糙集模型的扩展与比较 3.1 两类基于后继邻域的扩展模型 Pawlak 粗糙集的近似算子的定义有两种形式 : 设 ( , )UR 是一个 Pawlak 近似空间 , 对于任意 XU , 下近似 ()RX 和上近似 ()RX可以写成如下两种形式 : ( ) | ( ) R X x U R x X , (1) ( ) | ( ) R X x U R X X ; (2) ( ) ( ) / | ( ) R X R x
21、U R R x X , (3) ( ) ( ) / | ( ) R X R x U R R X X . (4) 在一般近似空间 ( , )UR 中 , 利用等式 (1)和 (2), 在定义 2.2 中已经对上下近似算子进行了扩展 . 同样地 , 利用等式 (3)和 (4), 我们可以得到另一种形式的扩展 . 但是直接利用等式 (3)和 (4)扩展上下近似的定义 , 得到的算子不是对偶的 , 因此 , 有的作者给出两种形式的扩展 . 即先用一个等式扩展上近似算子或下近似算子 , 然后再利用对偶性扩展另一个算子 . 这样就会得到两对上下近似算子 : ( ) ( ) | ( ) , R X R x R x X x U ( ) , ( ) x U y x R y R y X , ( ) ( )R X R X ( ) , ( ) x U y x R y R y X ( ) ( ) x U y x R y R y X . ( ) ( ) ( ) R X R x R x X ( ) , ( ) x U y x R y R y X , ( ) ( )R X R X ( ) , ( ) x U y x R y R y X
