粗糙近似算子的性质与公理化刻画【毕业论文】.doc

1、毕业论文 文客久久 本科 毕业设计 (论文 ) 题 目： 粗糙近似算子的性质与公理化刻画 学 院： 学生姓名： 专 业： 信息与计算科学 班 级： 指导教师： 起 止 日期： 毕 业论文 文客久久 摘要 粗糙集理论是一种研究不完整、不确定知识处理的数学工具 , 近几年来在机器学习、知识发现、算法研究、工程应用、决策支持系统以及模式识别等应用中取得了较好的成果 . 在Pswlsk 粗糙集理论中 , 下近似和上近似并非最基本的概念 , 粗糙集理论中所产生的代数系统是最主要的研究 , 利用一个公理化来刻画上、下近似 算子 , 表示公理集和这个条件下所产生的代数系统之间的联系的粗糙集理论研究方法被称为

2、公理化方法 . 本文主要研究粗糙近似算子的性质与公理化刻画 . 在粗糙集理论中有两种方法来推广定义近似算子 : 构造性方法和公理化方法 . 给出了在一般模糊环境下各种粗糙近似算子的定义 , 得到了这些近似算子的表示 . 关键词 : 粗糙集 ; 近似算子 ; 近似空间 ; 公理化刻画 毕 业论文 文客久久 Rough approximation operator properties and axiomatic characterization Abstract Rough Set Theory is a kind of mathematical tool to deal with the in

3、complete and indefinite knowledge processing, which has borne fruit recently in the application to machine learning, knowledge discovery, algorithm research, engineering application, decision supporting system and pattern recognition. Lower approximation and upper approximation are not the most basi

4、c concepts in Pawlaks Rough Set Theory while algebra system induced by that theory is the main idea which uses axiomatization to depict upper and lower approximation operators. The research method of Rough Set Theory that represents the relationship between axiom set and algebra system is called axi

5、omatic approach. This thesis mainly makes a study of the nature of rough approximation operators and the depiction of axiomatization. There are two approaches to the generalization of defining approximation operators, namely, constructive method and axiomatic approach and the latter provides the def

6、inition of different kinds of rough approximation operators under the fuzzy circumstances, and then gets the expressions of those approximation operators. Keywords: Rough set; Approximation operators; Approximation space; Axiomatic depiction 毕 业论文 文客久久 目录 摘要 . 0 Abstract. II 1 前言 . 1 1.1 粗糙集的简介 . 1

7、1.2 公理化方法 的应用 . 1 1.3 论文的组织结构 . 2 2 粗糙近似算子及其性质 . 3 2.1 广义粗糙近似算子的定义 . 3 2.2 粗糙近似算子与二元关系的等价刻画 . 6 3 粗糙近似算子的公理化刻画 . 10 3.1 近似算子的公理化刻画 . 10 3.2 粗糙集理论的公理化刻画 . 11 4 小结 . 17 参考文献 . 18 致谢 . 19 毕 业论文 文客久久 1 前言 1.1 粗糙集的简介 1982 年 , 波兰数学家 Pawlak Z1 发表了经典论文 Rough Sets, 粗糙集理论于此诞生 . 在这之后 , 许多数学家 , 计算机研究人员和逻辑学家对粗糙集

8、产生了很大的兴趣 , 并在粗糙集的理论和应用方面做了大量的研究 . 1991年 Pawlak Z2 的专著 出版 , 使得粗糙集在各个领域中的应用向前推进 . 此后也召开了一些粗糙集的会议 , 第一届关于粗糙集理论国 际学术会议在波兰召开 . 1995 年 , ACM Communication 将其列为新浮现的计算机科学的研究课题 . 1998年 , 国际信息科学杂志 (Information Sciences)还为粗糙集理论的研究出了一期专辑 . 这些大大地促进了粗糙集的发展 . 粗糙集的实用性很强 , 粗糙集从产生到现在虽然只有短暂的十几年的时间 , 但是已经取得了很多的成果 . 它在机

9、器学习、知识发现 2 与数据挖掘 3 、模式识别、决策分析 4 、本体近似等领域广泛应用 , 粗糙集理论的研究逐渐趋于热化 . 1.2 公理化方法的应用 在 Pawlak粗糙集模型中 , 等价关系在论域上有着至关重要的作用 . 划分在等价关系上 的形成 , 构造了论域上的上、下近似算子 . 用来刻画不精确的概念 , 并且进一步的研究相应的知识来获取问题 . 但在很多实际的问题中 , 很难构造对象之间的等价关系 , 或者对象之间在本质上并不存在等价关系 . 为了推广粗糙集理论的应用范围 , 根据具体的问题 , 人们对Pawlak粗糙集模型进行了许 多形式的推广 . 通常研究粗糙集近似算子有两种方

10、法 : 构造性方法与公理化方法 . 构造性方法 的 主要思路是从给定的近似空间出发去研究粗糙集和近似算子 , 然后导出粗糙集代数系统 6,7. 公理化方法的基本要素是满足某些公里集的近似算子 , 即事先给定粗糙集代数系统 , 然后再去找通过构造性方法定义的近似算子以及由它导出的粗糙集的二元关系 , 这个 就是事先就给定的一个近似算子和粗糙集代数系统 . 最早研究粗糙集用公理化方法的是我国的刘清及其国际合作者 Lin8, 因为他们得出的的公理集是不独立的 , 祝峰与何华灿 9就对公理化方法又进行了改进 . Thieie10与 Yao11分别对于一般关系下的经典粗糙近似算子与公理化作了比较完整的刻

11、画 . 研究粗糙集结构主要有构造性方法和公理化方法 . 研究粗糙集理论的大部分前期的工毕 业论文 文客久久 作都是构造性方法 , 这种方法具有较强的应用背景 , 因为一些实际例子的需要 , 也常常产生一些 问题 , 它的缺点是不易比较深入了解粗糙集的代数结构 . 与构造性不同 , 用公理化方法研究粗糙集就少了很多工作 , 公理化方法所显示的形式的简洁性、条理性和结构的和谐性确实符合美学上的要求 , 因而为数学活动中贯彻审 美原则提供了范例 1.3 论文的组织结构 本文 用构造性方法和公理化研究粗糙集 , 由一个一般二元经典关系出发构造性定义一对对偶粗糙近似算子 , 讨论了粗糙近似算子的性质 ,

12、 并且由各种类型的二元关系通过构造得到各种类型的粗糙集代数 , 用公理形式定义粗糙近似算子 . 对于各种粗糙近似算子的公理化刻画做了总结 , 在有限论域中给出了经典粗糙近似算子的构造性定义并获得刻画这些近似算子的独立公理集 . 阐明了近似算子的公理集可以保证找到相应的二元经典关系 , 使得由关系通过构造性方法定义的粗糙近似算子恰好就是用公理化定义的近 似算子 . 毕 业论文 文客久久 2 广义粗糙近似算子及其性质 2.1 广义粗糙近似算子的定义 定义 2.1 设 U 和 W 是两个非空有限论域 . 称子集 ()R P U W( ()PX 表示 X 的幂集 ) 是从 U 到 W 上的一个经典二元

13、关系 . 称关系 R 是串行的 (serial), 若对于任意 xU 存在 yW 使得 ,x y R ; 若 UW , 称 ()R P U U是 U 上的一个二元关系 . 称 R 是自反的 , 若对于任意 xU 有 ( , )x x R ; 称 R 对称的 , 若对于任意 ,xy U , ,x y R 蕴含 ( , )y x R ; 称 R 是传递的 , 若对于任意 ,x y z U , ,x y R 和 ( , )y z R 蕴含( , )x z R ; 称 R 是欧几里得的 (Euclidean), 若对于任意 ,x y z U , ,x y R 和( , )x z R 蕴含 ( , )y

14、 z R ; 称 R 是等价的 , 若 R 是自反、对称和传递的二元关系 . 设 R 是从 U 到 W 上的一个二元关系 . 我们定 义一个集值函数 : ( )sR U P W 如下 : ( ) ,sR x y U x y R , xU . ()sRx称为 x 关于 R 的后继领域 . 显然 , 任意一个从 U 到 W 的集值函数 F 都可以定义一个二元关系 ,R x y U W y F x . 由集值函数 : ( )F U P W , 我们可以定义一个基本集分配（又称为关系划分函数） :j P W P U , j A u U F u A , A P W . 易证 j 满足性质 : (J1)

15、AUj A U , (J2) A B j A j B . 定义 2.2 设 R 是从 U 到 W 上的一个经典二元关系 , 称三元组 ,UW R 是一个广义经典近似空间 . 对于任意 AW , A 关于 ,UW R 的下似 RA和上似 RA分别定义如下 : ()sR A x U R x A , 毕 业论文 文客久久 ()sR A x U R x A . 称 ,R A R A 是 A 关于 ,UW R 的（广义）粗糙集 , 分别称 R 和 :R F W F U 为下近似算子和上近似算子 . 显然 , 如果 UW , R 是 U 上的等价关系 , 那么对于 A PU 有 , R R RR A x

16、U x A x x A , R R RR A x U x A x x A . 故广义近似算子是 Pawlak 经典近似算子的推广形式 . 定理 2.1 12-14 设 R 和 S 是从 U 到 W 上的二元经典关系 , 那么广义粗糙近似算子满 足以下性质 : 对于 , ( )A B PW , (LP) R S S A R A , (UP) R S R A S A ; (L1) R A R A , (U1) R A R A ; (L2) R W U , (U2) R ; (L3) R A B R A R B , (U3) R A B R A R B ; (L4) A B R A R B , (U

17、4) A B R A R B ; (L5) R A B R A R B , (U5) R A B R A R B . 定理 2.2 设 U 是有限非空论域 , R 是 U 上的二 元关系 , 则 : (1) ,RX R X RX R X , XU ; 毕 业论文 文客久久 (2) RU U , R ; (3) iii I i IR X RX, iii I i IR X RX; iXU, iI ; (4) X Y RX RY , RX RY , iXU; (5) iii I i IR X RX, iii I i IR X RX, iXU, iI ; 其中 I 是任意指标集 , 性质 (1)称为近

18、似算子的对偶性质 . 证明 (1) 设 xU , 因为 x RX sR x X sR x X x R X , 所以 RX R X . 用 X 代替 RX R X 中的 X 即得 RX R X . (2) 若 R , 则存在 xR, 由定义得 sRx , 矛盾！所以 R . 由 RX R X 得 R , 即 RU, 从而 RU U . (3) 因为 iiIx R X siiIR x X siR x X iI iiIx RX, 所以iii I i IR X RX. 同理 , iiIx R X siiIR x X 0iI, 0siR x X 0ix RX 毕 业论文 文客久久 iiIx RX, 所以

19、iii I i IR X RX. (4) x RX , 由定义 sR x X , 而 XY ,于是 sR x Y , 从而 x RY , 所以 , RX RY . 由对偶性质和 RX RY 易推得 RX RY . (5) 由iiiIXX和性质 (4)得到iiiIRX R X , 从而iii I i IRX R X . 同理可得iii I i IR X RX. 引理 2.1 设 U 是有限非空论域 , R 是 U 上的二元关系 , 则 xU , 有 1s p sR x R x R x Ry U x y . 证明 因为对于任意 yU , sy R x R y x sx R y py Rx 所以 , 1s p sR x R x R x Ry U x y . 2.2 粗糙近似算子与二元关系的等价刻画 定理 2.3 设 U 是有限 非空论域 , R 是 U 上的二元关系 , 则以下等价 : (1) R 是串行的 ; (2) RX RX ; (3) R ; (4) RU U . 证明 “(1) (2)” x RX , 通过定义知 sR x X . 因为 R 是串行的 , 即 sRx , 因此 sR x X , 即 x RX , 故 RX RX .