1、 本科毕业论文 （ 20 届） 无限论域上粗糙集的公理化刻画 所在学院 专业班级 信息与计算科学 学生姓名 学号 指导教师 职称 完成日期 年 月 I 摘要 粗糙集理论中的基本结构是由论域及其定义在论域上的二元关系所生成的近似空间 , 由近似空间可以导出下近似算子和上近似算子 . 在 经典的 Pawlak 粗糙模型中 , 等价关系在近似空间的构造中起着重要的作用 , 但近似空间中的等价关系是一个过于苛刻的条件 , 因此会限制 Pawlak 粗糙集模型的应用 . 粗糙集理论研究的一个重要方向是 Pawlak 粗糙集模型的推广 . 本文研究无限论域中粗糙集近似算子的特征 . 首先 , 回顾了无限论
2、域中的二元关系及其基本性质 . 其次 , 定义了无限论域中集合关于近似空间的下近似和上近似的概念 , 研究了下近似算子和上近似算子的基本性质 , 讨论了近似算子的性质与一些特殊二元关系性质之间的等价刻画 . 最后 , 用公理化方法研究粗 糙集近似算子的一些特征 . 证明了无限论域中 各种类型的粗糙集代数可以被各种不同的公理集所刻划 . 阐明了近似算子的公理集可以保证找到相应的二元关系 , 使得由关系通过构造性方法定义的粗糙近似算子恰好就是用公理化定义的近似算子 . 关键词 : 近似算子 ; 粗糙集 ; 二元关系 II Abstract The basic structure of the ro
3、ugh set theory is an approximation space consisting of a universe of discourse and a binary relation imposed on it. Based on the approximation space, the key notions of lower and upper approximation operators can be constructed. In the classical Pawlaks rough set model, an equivalence relation is a
4、primitive notion in the construction of an approximation space. This equivalence relation is a very restrictive condition that may limit the application domain of the rough set model. One of the main directions in the research of rough set theory is naturally the generalization of concepts of Pawlak
5、 rough set approximation operators. In this thesis, we mainly focus on the study of rough set approximation operators in infinite universes. Binary relations in infinite universes with their properties are first reviewed. Lower and upper approximations of a set with respect to an infinite approximat
6、ion space are then defined, and their properties are examined. Equivalent characterizations of properties of approximation operators and properties of binary relations are further presented. Finally, axiomatic chararerizations of rough set approximation operators in infinite universes are discussed.
7、 Different axiom sets of lower and upper set-theoretic operators guarantee the existence of different types of binary relations which produce the same operators. Key Words: Approximation operators; Approximation spaces; Rough sets; Binary relations III 目 录 摘要 .I 1 前言 . 1 2 无限论域上的粗糙近似算子 . 3 2.1 无限论域上
8、的粗糙近似算子的构造性定义 . 3 2.2 无限论域上的粗糙近似算子的性质 . 4 3 无限论域上的粗糙近似算子的公理化刻画 . 10 3.1 无限论域上的粗糙近似算子的公理化方法 . 10 3.2 无限论域上的粗糙近似算子构造性方法与公理化方法的关系 . 13 4 小结 . 15 参考文献 . 16 致谢 .错误 !未定义书签。 1 1 前言 粗糙集理论作为一种数据分析处理理论 , 在 1982 年由波兰科学家 Z. Pawlak 1 创立 . 最开始由于语言的问题 , 该理论创立之初只有东欧国家的一些学者研究和应用它 ,后来才受到国际上数学界和计算机界的重视 . 1991 年 , Pawl
9、ak 出版了粗糙集 关于数据推理的理论这本专著 , 从此粗糙集理论及其应用的研究进入了一个新的阶段 , 1992 年关于粗糙集理论的第一届国际学术会议在波兰召开 . 1995 年 ACM 将粗糙集理论列为新兴的计算机科学的研究课题 . 粗糙集理论作为一种处理不精确 (imprec ise)、不一致 (inc onsistent)、不完整(incomplete)等各种不完备的信息有效的工具 , 一方面得益于他的数学基础成熟、不需要先验知识； 另一方面在于它的易用性 . 粗糙集理论创建的目的和研究的出发点就是直接对数据进行分析和推理 , 从中发现隐含的知识 , 揭示潜在的规律 , 因此是一种天然的
10、数据挖掘或者知识发现方法 , 它与基于概率论的数据挖掘方法、基于模糊理论的数据挖掘方法和基于证据理论的数据挖掘方法等其他处理不确定性问题理论的方法相比较 , 最显著的区别是它不需要提供问题所需处理的数据集合之外的任何先验知识 , 而且与处理其他不确定性 问题的理论有很强的互补性 (特别是模糊理论 ). 对粗糙集理论的研究主要集中在 : 粗糙集模型的推广 , 问题的不确定性研究 , 与其他处理不确定性和模糊性问题的属性理论的关系与互补 , 纯粹的数学理论方面的研究 , 粗糙集的算法研究以及与人工智能其他方向关系的研究等 . 构造性方法和公理化方法是研究粗糙集理论的两种主要方法 . 构造性方法 是
11、对原始的 Pawlak 粗糙集模型的一般推广 , 也是最为自然的方法 , 其主要思路是从给定的近似空间出发去研究粗糙集和近似算子 . 他是以论域上的二元关系作为基本要素的 , 导出近似算子 , 然后导 出粗糙集代数系统 ( ( ), , , , , )P U R R. 其次 有很强的应用背景 , 所研究的间题也往往应实际的需要而产生 , 在知识的表示与获取方面的研究有重要的应用 . 用构造性方法定义的近似算子 , 用来描述知识的不精确性 ,导出各种类型的粗糙集代数 , 但粗糙集的代数结构不易深刻了解 . 而公理化方法的最大特点是可以深刻地理解各类近似算子的结构特征 . 在有限论域上以二元关系为
12、基础的粗糙集的构造性方法和公理化方法的研究比较成熟 , 本文将无限论域上的粗糙集的构造性方法和公理化方法进行讨论 , 进一步完善了 粗糙集近似算子的理论研究 . 在这些研究结果的基础上 , 我们2 将回顾和讨论粗糙集近似算子的性质， 并显示与其他数学系统的连接 . 公理化方法也称为算子方法与构造性方法思想相反，这种方法不是以二元关系作为基本要素，它的基本要素是一对满足某些公理的一元算子 , : 2 2UULH , 即粗糙集代数系统 (2 , , , , , )U RR中近似算子恰好就是事先给定由公理定义近似算子 . 这种研究方法的最明显的优点是能够深刻地了解近似算在的数学结构 , 其缺点是应用
13、性不够强 . 公 理化方法的研究最初是有 Lin 和Liu 提出的一开始只局限于 Pawlak 代数系统 3 , 即由公理定义的近似算子与二元等价关系相对应的情形 , 后逐渐发展到各种具体的二元关系与一般关系下的粗糙集代数系统 , Yao 10对于近似算子与一般关系对应的公理化刻画进行了比较完整的讨论 . 3 2 无限论域上的粗糙近似算子 2.1 无限论域上的粗糙近似算子的构造性定义 定义 2.1 设 U 是无限集 , 常称为论域 , R 是 U 上的 二元关系 , 称 ( , )UR 为广义无限近似空间 . Ux , 记 yRxUyxR s )( , 称 )(xRs 为 x 的后继邻域 .
14、UX , 记 ( ) ( )sR X x R x X, ( ) ( )sR X x R x X . )(XR 和 )(XR 分别称为 X 关于 ( , )UR 的下近似和上近似 . 当 XR = XR 时 , 称 X 关于广义无限近似空间 ( , )UR是可定义的 , 否则称 X 是粗糙的 . 定理 2.1 设 R 是 U 上的一个任意的二元关系 , U 是一个无限论域 , UX 有 ( )RX R X , ( )RX R X . 证明 因为 )()()()( XRxXxRXxRXRx ss , 所以 )( XRXR . 用 X 代替 )( XRXR 中的 X 即得 )( XRXR . 定理
15、2.1 称为近似算子的对偶性质 . 定理 2.2 设 R 是 U 上的一个任意的二元关系 , U 是一个无限论域 , 则 UUR , R . 证明 若 R , 则 Rx , 由定义得 )( xRs , 矛盾 . 所以 R . 由 ( )R X R X 得 R , 即 )( UR , 从而 UUR . 定理 2.3 设 R 是 U 上的一个任意的二元关系 , U 是一个无限论域 , 其中 I 是任意指标集 , IiUXi , 有 iIiiIi XRXR )(, iIiiIi XRXR )(. 证明 因为 ( ) ( )i s ii I i Ix R X R x X 4 ( ) ( ) ( )s
16、i iR x X i I x R X i I iIi XRx , 所以 iIiiIi XRXR )(. 同理 )( iIi XRx 0)(,)()( 0 isiIis XxRIiXxR iIii XRxXRxIi 0,0, 所以 iIiiIi XRXR )(. 定理 2.4 设 R 是 U 上的一个任意的二元关系 , U 是一个无限论域 , UYX , 有 YRXRYRXRYX ,. 证明 XRx , 由定义 XxRs )( , 而 YX , 于是 YxRs )( , 从而 YRx , 所以 , YRXR . 由对偶性质和 YRXR 易推得 YRXR . 定理 2.5 设 R 是 U 上的一个
17、任意的二元关系 , U 是一个无限论域 , 其中 I 是任意指标集 , IiUXi , 有iIiiIiiIiiIi XRXRXRXR )(,)(. 证明 由iIii XX 和定理 2.4 知 )(iIii XRXR ，从而 )(iIiiIi XRXR . 同理可得iIiiIi XRXR )(. 定理 2.6 设 R 是 U 上二元关系 , U 是无限论域 , 则 Ux , 则 )()()(1 yRxUyxRxRxR sps . 证明 因为对于任意 Uy , )()()( xRyyRxxyRxRy pss , 所以 )()()(1 yRxUyxRxRxR sps . 2.2 无限论域上的粗糙近似
18、算子的性质 5 定义 2.2 U 是无限论域 , R 是 U 上的一个二元关系 , 我们定义 U 上的特殊关系 R 如下 (1)串行性 x y xRy ()sx y y R x ()sx R x . (2)自反性 x xRx ()sx x R x . (3)对称性 x , y xRy yRx ( ) ( )ssy y R x x R y . (4)传递性 x , y , ( , )z xRy xRz xRz x , ( ) ( ) ( )s s sy y R x R y R x . (5)欧几里得性 x , y , ( , )z xRy xRz yRz x , ( ) ( ) ( )s s s
19、y y R x R x R y . 定理 2.7 设 R 是 U 上二元关系 , U 是无限论域 , 则以下等价 (1) R 是自反的 ; (2) UXXXR , ; (3) UXXRX , . 证明 “ (1) (2)” 设 XRx , 由下近似的定义得 XxRs )( . 又因为 R 是自反的 , 所以 x )(xRs , 从而 Xx , 因此 XXR . “ (2) (3)” UX , 由 (2)得 XXR )( , 从而由对偶性质得 XRXRXX )()( . “ (3) (1)” xU , 由 (3)得 xRx , 可得 ()px R x , 从而 ()sx R x , 所以 R 是
20、自反的 . 6 定理 2.8 设 R 是 U 上二元关系 , U 是无限论域 , 则以下等价 (1) R 是串行的 ; (2) RX RX ; (3) R ; (4) UUR . 证 明 “ (1) (2)” XRx , 由下近似的定义知 XxRs )( . 因为 R 是串行的 , 即)(xRs , 因此 XxRs )( , 于是由上近似的定义知 XRx , 故 XR XR . “ (2) (1) ” 反证 , 若 Ux , 使 )(xRs , 由 XxRUX s )(, , 即XRx , 但 XxRs )( , 因此 XRx , 这与 (2)矛盾 , 所以 R 是串行的 . “ (2) (3
21、)” 利用近似算子的对偶性质有 )()( XRXRXRXRXRXR )( XX , 即 (2) (3). “ (3) (4)” 利用近似算子的对偶性质有 UURURRR )( . 所以 以上等价关系成立 . 定理 2.9 设 R 是 U 上任意一个二元关系 , 则对于 xU , 有 1 ( ) ( ) | ( ) s p sa p r x R x R x y U x R y . 证明 对于 y apr x , 由 ( ) sR y x , 即 ()sx R y , 也就是说 ()py R x , 从而 | ( ) sa p r x y U x R y . 定理 2.10 设 R 是 U 上二元关系 , U 是无限论域 , 则以下等价 (1) R 是逆串行的 ; (2) UxxR , ; (3) UURs )( . 证明 由定理 2.9 得
