（计算机软件与理论专业论文）基于泛系的上下近似求解和决策表属性约简.pdf

摘要 在粗糙集理论及粗糙模糊集理论中，上下近似及边界的求解与决策表属性 约筒是它们的核心内容。将这两个方面与泛系的形影关系相结合，得出了一些 结论，将其总结如下： 1 从形影关系的角度给出求解粗糙集与粗糙模糊集上下近似与边界的统一 公式，得出粗糙集是粗糙模糊集的泛极端，粗糙模糊集是模糊粗糙集的泛极端； 同时还提出了粗糙模糊二元关系和模糊粗糙二元关系的概念，分别求解了它们 的上下近似及边界，并且得出了粗糙二元关系是粗糙模糊二元关系的泛极端， 粗糙模糊二元关系是模糊粗糙二元关系的泛极端，进一步拓宽了粗糙集理论。 2 根据泛化的集合包含关系，提出了决策规则确定度的概念，在此基础上 进一步定义了b 相容决策表，指出1 3 相容决策表就是决策表相容度大于给定置 信水平0 的决策表，传统的相容决策表指b = 1 的决策表，b 相容决策表的提 出为人们做出更符合实际的决策提供了理论依据。 3 对b 相容决策表属性约简与求核。将冗余属性的定义进一步拓宽：去掉 该属性后决策表相容度不小于原来的，称该属性是冗余的。结合修改后的基于 包含度的分布属性约简算法，进行属性约简与求核。 关键词：形影关系，特征函数，广义包含，决策规则确定度，决策表相容度，b 相容决策表 a b s t r a c t i nt h er o u g hs e tt h e o r ya n dr o u g h f u z z ys e tt h e o r y , c o m p u t a t i o no fa p p r o x i m a t i o n s a n de d g ea n da t t r i b u t e sr e d u c t i o no fd e c i s i o nt a b l ei si m p o r tp a r to ft h e m a n ys e ta n d b i n a r yr e l a t i o nc a nb ep r e s e n t e db yam a p p i n gf r o mt h ep o i n to fb o d y - s h a d o wr e l a t i o n o fp a n s y s t e m s ，w ei n t r o d u c et h e b o d y s h a d o wr e l a t i o no fp a n s y s t e m s t ot h e c o m p t u t i o na n dd r a ws o m ec o n c l u s i o n s a n dn o wl i s tt h e ma sf o l l o w s ： i t h i sp a p e rp r e s e n t sau n i f l e df o r m u l ao fs o l v i n gt h ei o w e ra p p r o x i m a t ea n dt h e u p p e ra p p r o x i m a t eo fr o u g hs e ta n dr o u g h f u z z ys e t ，a n dp r o v e st h a tt h ef o r m u l ai s e q u i v a l e n tt ot l l et r a d i t i o n a io n e w ec o n c l u d et h a tt h eu p p e ra n dl o w e ra p p r o x i m a t i o n a n dt h ee d g eo fr o u g hs e t sa r ec o n s i s t e n tw i t ht h a to fr o u g hf u z z ys e t s ，t h a to fr o u g h f u z z ys e t sa r ec o n s i s t e n tw i t ht h a to ff u z z yr o u g hs e t s t h a ti st os a y , t h ef o f i l l e ri st h e e x t r e m eo fp a n s y s t e m so ft h el a t t e r a tt h es a m et i m e ，ip r e s e n tt h er o u g h f u z z yb i n a r y r e l a t i o na n dt h ef u z z y r o u g hb i n a r yr e l a t i o n t h er o u g hs e tt h e o r yi se x t e n d e db yt h e c o n c l u s i o n 2 ip r e s e n tt h ea s c e r t a i n m e n td e g r e eo fd e c i s i o nr u l e sb a s e do i lt h eg e n e r a l i z e d i n c l u s i o no fs e t f u r t h e r m o r e 3 - c o m p a t i b l ed e c i s i o nt a b l ei sp u tf o r w a r d a l lt h e a s c e r t a i n m e n td e g r e eo fd e c i s i o nr u l e so fw h i c ha r eg r e a t e rt h a nb h e r ebi sc a l l e d c o n f i d e n c el e v e lb yp e o p l e t h et r a d i t i o n a lc o n c e p to fd e c i s i o nt a b l ei se x t e n d e df o r c o m p a t i b l ed e c i s i o nt a b l ei st h ed e c i s i o nt a b l ew h o s ebi sl ，s ot h er o u g hs e tt h e o r yi s e x t e n d e d t h ec o n c e p to f3 - c o m p a t i b l ed e c i s i o nt a b l ec a nb et h et h e o r e t i c a lb a s e so n w h i c hp e o p l ec a r lb eb a s e dw h e nt h e yp u tf o r w a r ds o m et r u t h f u la r i t h m e t i c 3 t or e d u c et h ea t t r i b u t e sa n dc o m p u t et h ek e r n e lo f3 - c o m p a t i b l ed e c i s i o nt a b l e ，i e x p a n dt h et r a d i t i o n a ld e f i n i t i o no fr e d u n d a n ta t t r i b u t e s i nt h i sp a p e r ，w h e na na t t r i b u t eo f a3 - c o m p a t i b l ed e c i s i o nt a b l ei sr e m o v e d ，b u tt h ed e g r e eo fc o m p a t i b i l i t yo fi td o s en o t c h a n g es m a l l e r w ec a l lt h ea r r i b u t ear e d u n d a n to n e ir e d u c et h ea t t r i b u t e sa n dc o m p u t e t h ek e r n e lo fb c o m p a t i b l ed e c i s i o nt a b l et h r o u g ht h em o d i f i e da t t r i b u t e sr e d u c t i o n a l g o r i t h mw h i c hb a s e do nt h ed e g r e eo fi n c l u s i o n k e y w o r d s ：b o d y s h a d o wr e l a t i o n ；c h a r a c t e r i s t i cf u n c t i o n ；g e n e r a l i z e di n c l u s i o n o fs e t ；t h ea s c e r t a i nd e g r e eo fd e c i s i o nr u l e ；t h et o l e r a n td e g r e eo fd e c i s i o nt a b l e ； 3 - c o m p a t i b l ed e c i s i o nt a b l e 符号注释 表示r 上的不可分辨关系 表示r 的核集 蕴含( 当则) p 的井集 ，的交集 经典集合的r 上近似 经典集合x 的r 下近似 模糊x 的r 上近似 模糊集合的rr 近似 取y 的最小值 取z ，y 的最大值 p 上的不可分辨关系构成u 中的所有等价类 经典集合爿的特征函数 模糊集合t 的隶属函数 经典二元关系r 的特征函数 模糊二元关系r 的隶属函数 求决策规则的确定度 v 一一，m砑些：邑一一一厶厶矗一 原仓性声明 本人郑重声明：本人所望交的学位论文，是在导师的指导下独立进行研究 所取得的成果。学位论文中凡引用他人已经发表或未发表的成果、数据、观点 等，均已明确注明出处。除文中已经注明引用的内容外，不包含任何其他个人 或集体已经发表或撰写过的科研成果。对本文的研究成果做出重要贡献的个人 和集体，均已在文中以明确方式标明。 本声明的法律责任由本人承担。 论文作者签名：磊垂凄与 日 期：迎：妻：之i 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权 归属兰州大学。本人完全了解兰州大学有关保存、使箱学位论文的 规定，同意学校保存或向国家有关部f 1 或机构送交论文的纸质版和 电子版，允许论文被查阅和借阅；本人授权兰州大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，可以采用任何复 制手段保存和汇镳本学位论文。本人离校后发表、使用学位论文或 与该论文直接相关的学术论文或成果时，第一署名单位仍然为兰州 大学。 保密论文在鳃密后应遵守此爝定。 论文作者签名：雄导师签名： 真毛 e t 期：心c 矸 批于泛系的上下近似求解和决策表属性约简 1 1 论文背景 l 绪论 1 9 8 2 年，波兰学者z p a w l a k 教授提出了“粗糙集理论( r o u g hs e t s ) ”， 用来研究不完整数据、不精确知识的表达、学习、归纳等方法。粗糙集理论认 为人类的知识是一种分类的能力，它的特点是：无需提供除问题所需处理的数 据之外的任何先验信息；其主要思想就是在保持分类能力不变的前提下，通过 知识约简，导出问题的决策或分类规则。决策表的化简及决策规则的提取在粗 糙集理论中占有重要的位置。 粗糙集理论是基于经典集合的，由于不能有效地描述模糊事物，经典集合 论难以处理复杂系统问题。这里的所谓模糊乃指并非由于随机性而是由于缺乏 从一类成员到另一类成员的明晰过渡所引起的不确定性。诸如“高个子人”、“下 棋的好策略”、“两个数近似相等”、“系统大致是线性的”等晓法都是模糊的。 为了克服经典数学解决这种问题的局限性，美国加州大学伯克利分校l o t f i az a d e h 教授于1 9 6 5 年在i n f o r a m t i o na n dc o n t r o l 上发表论文( ) ， 标志着“模糊数学理论”的正式诞生，为数学的发展开辟了一个崭新的研究方 向。在模糊数学中，元素与集合的关系不再是经典集合中简单的“属于”或“不 属于”，而是通过一个隶属度的值来描述元素与集合的归属关系。模糊数学承认 由于客观事物的差异所引起的“不分明性”，体现了“亦此亦彼”的现象。 模糊集研究的是同类中属于不同集合l 司对象的不可分辨关系，它的计算 方法主要是连续特征函数的产生，主要着眼于集合的模糊性，而粗糙集理论研 究的是不同类中的对象组成的集合之间的关系，重在分类，它的计算方法是知 识的表达与简化，主要着眼于集合的粗糙程度。 泛系理论是关于跨学科的研究，它的基础是数学化的语言、数学化的逻辑。 它以集合理沦为基砖模型构建。泛系以广义系统为研究对象，重在研究系统关 系，研究元素之间、集合之间、基础系统内部、基础系统之蚓、复杂系统内部、 复杂系统之问的广义关系，研究关系之问的关系，研究关系的转化、转化中的 不变性( 泛对称) 、优化转化等等。深刻理解运用泛系中的些基础关系( 局整 关系、形影关系、异同关系、模拟关系等等) 对研究事物机理有很大的帮助。 兰州入学坝一 学位论文 泛系是以集合为基础来研究关系、系统等之间的内在联系及相互转化的， 粗糙集和模糊集是研究模糊、不确定知识的新型工具，将三者有机地结合起来， 用泛系的形影关系等基本概念来重新求解粗糙集和粗糙模糊集的上下近似及决 策表的简化和规则提取等，发掘出它们内在的联系，为人们对粗糙集和模糊集 的研究提供了新的研究方向。 1 2 论文研究的意义 本论文将泛系与粗糙集相结合，x , t j i h 糙集和粗糙模糊集的上下近似及边界 的求解公式做了统一，从给出的统一求解公式能看出它们的内在联系，为人们 研究粗糙集和粗糙模糊集的联系提供了明确的思路。 随后本文提出了1 3 相容决策表的概念，它是为了克服传统相容决策表的弊 端而提出的。传统的相容决策表做出的决策规则过于理想化，在实际应用中比 较少见，而1 3 相容决策表做出的决策规则虽然有一定的误差，但是它更符合实 际，为人们做出贴近生活的决策规则提供了理论依据。 1 3 论文的创新点 本文将泛系与粗糙集和粗糙模糊集上下近似、边界的求解以及决策表属性 约简相结合，在结合过程中做了一些创新，简述如下： 1 统一了粗糙集和粗糙模糊集上下近似及边界的求解公式，提出了粗糙模 糊二元关系和模糊粗糙二元关系的概念，并将它们的上下近似及边界的求解公 式与粗糙集和粗糙模糊集的求解公式统一起来，找到了粗糙集、粗糙模糊集、 粗糙二元关系和粗糙模糊二元关系之问的泛系关系，最后用程序实现了一l 下近 似及边界的统一求解。 2 拓展了传统的集合包含关系，基于此并结合泛系提出了决策规则确定度 的概念，进一步提出了决策表相容度的概念，指出了传统相容决策表的缺点， 为克服此缺点而提出了1 3 相容决策表，并对它进行了属性约简与求核。 基于泛系的卜下近似求斛和决荒表属性约简 1 4 论文组织 本论文共分五章，以泛系的形影关系为引线，以上下近似的求解和决策表 属性约简为研究对象，通过对上下近似求解公式的重新定义，找到了它们内在 的规律；通过相容决策表的提出，拓展了相容决策表的概念，为人们提取切 合实际的决策规则提出供了理论依据。 第二章主要是本论文涉及的到一些概念的简单介绍。在粗糙集理论中介绍 了粗糙集上下近似及边界的传统的求解和及其意义，找出下近似是指由那些根 据现有知识判断出肯定属于观察对象所组成的最大集合，上近似是指由那些根 据有现有知识判断出可能属于观察对象所组成的最小集合，负域是由那些根据 现有知识判断出肯定不属于观察对象所组成的集合，边界是由那些根掘现有知 识判断出可能属于观察对象但不能完全肯定是否一定属于观察对象所组成的集 合，对决策表的属性约简和决策规则的概念进行了阐述；本章还介绍了模糊集 的概念，对模糊数学提出的原因做了详细的分析，指出了经典( 传统) 数学的 不足，简单的说明了模糊集的表示法和合运算；对粗糙集和模糊集在处理不确 定信息方面做了比较，指出模糊集是通过对象关于集合的隶属程度来近似描述 知识的，而粗糙集是通过集合关于已知可利用信息的一对上、下近似来描述的， 二者的互补性还是存在的；最后介绍了泛系的形影关系，由于其比较抽象难以 理解，列举了现实生活中人们日常生活的例子加以阐述。 第三章将泛系的形影关系引入上下近似及边界的求解，提出了统一的求解 公式，找出了它们的内在联系：粗糙集合的上下近似是粗糙模糊集合上下近似 的泛极端，粗糙模糊集合上下近似是模糊粗糙集上下近似的泛极端。在此基础 上，将观察对象进一步拓展，分别拓展为经典二元关系和模糊二元关系，提出 了粗糙二元关系、粗糙模糊二元关系及模糊粗糙二元关系的概念，并给出了它 们的上下近似及边界的求解公式，对它们的性质做了讨论，最后用程序实现了 上下近似及边界的统一求解。 第四章首先指出了传统相容决策表分类的弊端，而后基于泛化的集合包含 关系并结合泛系提出了决策规则确定度的概念，并对其性质进行了探讨；进一 步提出口相容决策表的概念，拓展了传统的相容决策表，对人们做出更贴近实 兰州大学顶：卜学位论文 际问题的决策算法提出供了理论依据。最后用基于包含度的分布约简对口相容 决策表进行属性约简与求核并且举例说明。 第五章对全文做了总结，对未来的工作做了展望。粗糙集、模糊集及泛系 三者的结合方面还有很多方面去探讨，去深究。 基于泛系的上下近似求解和决策表属性约简 2 基础知识介绍 本沦文涉及到粗糙集、模糊集以及泛系等学科，本章简单介绍一下粗糙集、 模糊集及二者的比较和结合。 2 1 粗糙集 2 1 1 上下近似及边界 粗糙集理论是波兰数学家p a w l a k 于1 9 8 2 年提出的1 2 1 ，它在决策支持和分 析得到了广泛的应用m “，它是- ：9 1 较新的处理不精确、不确定与不完全数据 的数学工具。在机器学习与知识发现、数据挖掘、模式识别等领域得到了广泛 的应用。 上下近似及边界的求解构成了粗糙集的核心内容，f 面我们用图来阐述一 下： 幽21 飘l 糙榘上f 近似及边界教刁 下近似是指由那些根据现有知识判断出肯定属于观察对象所组成的最大集 合，上近似是指由那些根据有现有知识判断出可能属于观察对象所组成的最小 集合，负域是由那些根据现有知识判断出肯定不属于观察对象所组成的集合， 边界是由那些根据现有知识判断出可能属于观察对象但不能完全肯定是否一定 属于观察对象所组成的集合。 兰州大学颂十学位论文 2 1 2 数据约简和决策规则 信息系统约简主要是是信息量减少，它将一些无关或多余的信息丢掉了， 而不影响其原有功能。 下面给出几个定义简单介绍一下数据约简1 6 1 。 定义2 1 设r 是一个等价关系族，sr ，如果m o ( r ) = 1 n o ( r 一) ，则称，在 r 中是可被约去的知识；如果p = r 一是独立的，则p 是r 中一个约简。 定义2 2 如果任一rer 是r 中不可约去的，则等价关系族r 是独立的：否 则r 是相关的。 定义2 3r 中所有不可约去的关系称为核，由它构成的集合称为r 的核集， 记为c o r e ( r ) 。 决策规则的定义在文献中给出： 定义2 4 对于决策表r = ( u ，a ，c ，d ) c ，d a 分别是条件属性和决策属性。函 数d 。：a - v ，使得出( a ) = a ( x ) ，其中a ，x u ，x u ，称以是7 上的一条决策规 则。若。e c ca ，则记叱i c ，是决策规则的条件部分：若口d ca ，则记d 。i d ， 是决策规则的结论部分。 定义2 5 定义2 4 中的。( r ) 是这样定义的，a ：u - ，其中as ，是属性。 的值集。 定义2 6 如果对任一个体y x ，以i c = d ，i c _ d 。l d = 4 l d ，则称乩是相容 的，否则d 、是不相容的。 2 2 模糊数学 2 2 1 模糊数学的提出 i 1 9 6 5 年美国加利福尼亚大学控制论专家扎德( z a d e hla ) 教授在 i n f o r m a t i o na n dc o n t r o 杂志上发表了一篇丌创性论文 f u z z ys e t s ) ， 这标志着模糊数学的诞生。 接干泛系的1 下近似求解和决策表届性约彻 和其它学科一样，模糊数学也是由于实践的需要而产生的。模糊概念( 或 现象) 处处存在，例如，在日常生活中的厚、薄、快、漫、大、小，长、短、 胖、瘦；白天、黑夜、暴雨、大暴雨、晴天、夕阳等。当代科技发展的趋势之 ，就是各个学科领域都要求定量化、数学化。当然也迫切要求将模糊概念( 或 现象) 定量化、数学化，这就促使人们必须寻找一种研究和处理模糊概念( 或 现象) 的数学方法。 众所周知，经典数学是以精确性为特征的。然而，与精确性相悖的模糊性 并不完全是消极的、没有价值的。甚至可以这样浣，有时模糊性比精确性还有 好。例如，要你在某日上午1 0 时到校门口去迎接一个“大胡子高个子长头发戴 宽边墨色眼镜的中年男人”，尽管这里只提供了一个精确信息男人，而其他 信息大胡子、高个子、长头发、戴宽边墨色眼镜、中年等都是模糊概念， 但是，你将这些模糊概念经过头脑的综合分析判断，就可以接到这个人。如果 这个问题要利用计算机精确地来处理，那么就要求将此人的准确年龄与身高， 胡子、头发的准确长度与根数，眼镜的边宽厘米数，黑色的程度等一一输入计 算机，才可以找到此人。如果这个人的头发中途掉了一根的话，计算机就可能 找不到这个人。由此可见，有时太精确了未必一定是好事。 模糊数学决不是把数学变成模模糊糊的东西，它也是具有数学的共性：条 理分明、一丝不苟。即使描述模糊概念( 或现象) ，也会描述得清清楚楚。由扎 德教授创立的模糊数学是继经典数学、统计数学之后数学的一个新发展。统计 数学把数学的应用范围从必然现象领域扩大到偶然现象的领域，模糊数学则把 数学的应用范围从精确现象扩大到模糊现象的领域。 2 2 2 模糊集的基础知识7 1 定义 定义2 7 特征函数设u 是由些确定的可识别的对象构成的集合称为论 域，对于u 中任意集合，我们可以引进个函数4 ( x ) ，即 船，= 妊：三 该函数称为集合的特征函数。 兰卅i 大学顺：| 二学位论文 u 中特征函数是从u 到 0 ，l 的一个映射，u 中任何一个特征函数也完全 确定了u 中的一个经典子集合，即 a = f x u ：月( ) = l 定义2 8 隶属函数论域u 上的一个模糊集合( f u z z ys e t ) a 是由u 上的一 个函数 a ：u 【0 ，】 来表示，其中月( z ) ( 有时用，( x ) 表示) 表示元素r 隶属于模糊集合a 的程度。 对于论域u 的一个对象x 和u 上的一个模糊集合a ，我们不能简单地说z 是 “绝对”属于还是不属于，而是x 在多大程度上属于a 。隶属度( z ) 币是x 属 于a 的程度的数量指标。 2 模糊集表示法 论域u 是有限集，u = “，_ ， ，u 上的任一模糊集a ，其隶属函数为 ( t ) ( = 1 ，2 ，n ) ( 1 ) z a d e h 表示法 ：型+ 盟。+ 盟 x ix 2 z l | 这旱丛盟不是分数，“+ ，也不是表示求和，只有符号意义，它表示变量t 对模糊集的隶属度是a ( x ，) ，本论文采用的就是此表示法。 ( 2 ) 序偶表示法 a = ( x 。，a ( x ) ) ，( x 2 ，( 墨) ) ，( ，a ( x ) ) ) ( 3 ) 向量表示法 a = ( ( 。) ，a ( x ! ) ，( ) ) 论域u 是无限集时，此时u 上的模糊集a 表示为 一= f 一( x ) ，x e ， 这里的叶- 不是积分符号，a ( x ) x 也不是分数。 3 模糊集的运算 定义2 9 设4 ，be f ( ，f ( 是论域u 上模糊集的全体，则有 举于泛系的i ：下近似求解和决策表属性约简 包含： a b 一( ) 口( ) ，v x u 相等：a ；b ( x ) = 口( x ) ，v x u 交：( a n b ) t x ) = 4 ( x ) 8 ( x ) ，v x u 并：( a u 口) 0 ) = a ( x ) v b ( x ) ，v x u 2 3 粗糙集和模糊集的关系 2 3 1 粗糙集和模糊集的比较 粗糙集与模糊集在处理不确定与不精确问题方面都推广了经典集合论，它 们都可以用来描述知识的不精确性和不完全性，然而侧重面有所不同。模糊集 是通过对象关于集合的隶属程度来近似描述知识的，与元素和集合的关系相联 系是经典集合论中属于和不属于关系的推广；而粗糙集是通过集合关于己知 可利用信息的一对上、下近似来描述的w 。 传统的不确定信息处理方法，有模糊集理论、证据理论和概率统计理论等， 而粗糙集与这些理论相比，有以下优势t 9 l ： 粗糙集优势在于仅依赖于原始数据，而不需要任何外部信息：约简冗余的 属性，且约简算法较为简单，由粗糙集模型导出的决策规则集给出了最小的知 识表示：由粗糙集方法导出的结果易于理解。 粗糙集涉及的概念都是清晰的，对模糊信息( 或知识概念) 无能为力：粗糙 集处理的对象是不连续的，对连续的对象要先离散化，这样容易造成信息的丢 失。 模糊集也有自身的不足，比如模糊集的隶属函数确定有很多方法”，但是在 结合具体实际问题寻找合适的方法时往往会带有一定的主观性，而单纯地使用 粗糙集理沦不一定能完全有效地描述不精确或不确定问题，二者有很强的互补 性。在粗糙集与模糊集融合方面，d d u b o i s 和h ，e r a d e 提出了粗糙模糊集和模 糊粗糙集的概念w ，。 兰州人学坝“l j 学位论文 2 3 2 粗糙集和模糊集的结合 从2 - 1l 小节可知，粗糙集和模糊集在处理不确定信息方面各有优缺点，它 们有很强的互补性，因此，有很多学者做了这方面的工作。 从泛系的观点，我们可以从p a w l a k 的粗糙集模型中分离出知识库( u ，脚、 被观察对象片u 和观察结果下近似印r 。( ) 、上近似；万。( ) 三个因子2 】。很多 学者刺附两个因子进行改变，以此来扩充粗糙集模型。从d u b o i s 和p r a d e ( 1 9 9 0 ) 提出模糊粗糙集理论i l l l ，到后来的各种广义模糊粗糙集理论、公理化的模糊粗 糙集理论i l ，其中g r e c o ，m a t a r a z z o 和s l o w i n s k i ( 1 9 9 8 ) 提出的模型、特 别是r a d z i k o w s k a ( 2 0 0 2 ) 的模型，可以说在一个论域的框架下，已经使该理 论的发展达到了一个相对完善的状态。另一方面，w u 等( 2 0 0 3 ) 和m i 等( 2 0 0 4 ) 在两个论域的范畴下进行了探索。 箨于泛系的1 1 ：近似求解和扶策表属性约简 3 形影关系与上下近似及边界的求解 实际生活当中，由于人们处理的知识往往是模糊的，有学者提出了粗糙模 糊集理论及模糊粗糙集理论”l 。无论是粗糙集模型、粗糙模糊集模型还是模糊 粗糙集模型，上下近似及边界构成了它们的核心内容，文献l ls i 给出了它们各自 的求解公式。但从给出的求解公式中，看不出三者的统一性。本章从泛系的形 影关系出发，重新给出了上下近似及边界的求解公式，并分析了三者在本质上 是统一的：租糙集合的上下近似是粗糙模糊集合上下近似的泛极端，粗糙模糊 集合上下近似是模糊粗糙集上下近似的泛极端。在此基础上，将观察对象进一 步拓展，分别拓展为经典二元关系和模糊二元关系，提出了粗糙二元关系、粗 糙模糊二元关系及模糊粗糙二元关系的概念，并给出了它们的上下近似及边界 的统一求解公式。最后用程序实现了统一公式的求解。 3 1 预备知识 3 1 - l 泛系的形影关系 集论意义的形影关系包括函数、投影、映射、反函数、赋形( 投影之逆) 、 直集、商化( 转化为商集子集的某些集合) 、积化( 商化之逆) 有时也包括 缩影及其逆扩形以及泛积，并把形影关系的复合也看成形影关系。复合是 直积再约化的结果，所以广义的形影关系也包括复合及数学关系，后者可定义 为直积的缩影而与泛积概念实质上相同。所有这些集论意义的形影关系均被泛 系数学推广于类集泛系，并且还用多种公理形式推广于一般泛系。它与局整关 系形成泛系的形式关系的两大基砖，它们可生成种种的泛关系、泛转与泛模拟， 为百科理法建构形式模型提供工具m ，。 理论上的说明比较抽象，我们举个简单的例子来说明一下什么是形影关系。 现在有a ，b ，c ，d 四个盒子，它们的颜色分别为红色，红色，半红半蓝， 蓝色，形状规格分别是大，中，中，小。 兰州大学坝：卜学位论文 形 固田田圈田霉 幺- 卜一、：一 ，。j 、 ，。一_ 、，一一、，一一- 、 兰兰，j ( ! ，八! 一，h 、竺，j 一 、一，、一 幽3 1 饭舰巴共 ：! ；幽32 接形状规格共彬 在图3 i 中，a ，b ，c ，d 是形，“红色”、“蓝色”、“大”、“中”、“小”是 它们的影，a ，b 从颜色上来说是全共影，由于c 的特殊性，a ，b 与c 是半共影， 同样，c 和d 是半共影，从形状规格上来看，a 、d 各与自己全共影，b 和c 全 共影。 从上面的例子可以看出，要想看两个事物是否共影，必须是从事物的某个 属性谈起的，比如就盒子a ，b 来况，从颜色上来说，a ，b 是全共影，而从形状 规格上来说，a ，b 是不共影的。 形影关系在现实生活中也有很多体现及应用，比如，在计算机领域，在l i n u x 文件系统为了要兼容各种操作系统下的文件系统，提出了“虚拟文件系 统”v f s ( v i r t u a lf i l e s y s t e ms w i t c h ) 的概念。为了能做到兼容各种文件系统， l i n u x 对各种文件系统作了极其美妙的抽象，在各个操作系统的文件系统上面 又做了一层，这一层就是虚拟文件系统层。这个虚拟文件系统层就是“影”，而 各个不同的文件系统是“形” 1 0 l 。 操作系统中的逻辑i o 与物理i o 也体现了形影关系的思想i 。 形影关系在人们的日常生活中也到处体现，人们一般关心“影”，而不是 “形”。比如，我们平时坐公共汽车，我们说l 路车是指车体上写有1 路标志的 公共汽车，假如这样的车共有i o 辆，那么这1 0 辆车就是“形”，而1 路车就是 它们共同的“影”。人们坐车关心的是第几路车，而不是具体哪一辆车。 3 1 2 泛极端 泛极端是泛系理论中比较重要的一个概念，它是指某一序关系下的最小元 和最大元f l g l 。 例如，给定集合 0 1 ，在“大于”这个序关系下，0 是最小元，l 是最大 元，它们都是此序关系下的泛极端。 基于泛系【1 勺| ：_ 下近似求斛和决策表属性约简 再比如，剥于集合u ，p ( u ) 是集合u 所有的子集的集合，p ( 在”序关 系下，中是最小元，u 是最大元，它们是此序关系下的泛极端。 3 1 3 观察对象 在解释观察对象这个概念之前，首先解释一下什么是论域，什么是知识， 因为观察对象是相对于知识来况的。 设u ；巾是我们感兴趣的剥象的有限集合，称为论域。任何子集x u ，称 为u 中的一个概念或范畴。u 中的任何概念族称为关于u 的抽象知识，简称知 识。本论文的知识如果没有特别说明是指能在u 上形成划分的那些知识。 观察对象是u 中的一个概念，用u 中的知识来度量该观察对象，可以得到 观察对象关于此知识的上下近似及边界。我们也可以这样解释，知识就是我们 已经学到的、掌握的、对我们日后认识事物有用的理论，而观察对象就是我们 待认识的、还没有完全掌握的概念。用我们已经掌握的知识来观察没有掌握的 概念，难免会出现误差，这就是上下近似及边界。下近似是对观察对象肯定的 部分，上近似是对观察对象以外可以肯定否定的部分，边界就是模棱两可的部 分。 3 1 4 传统的上下近似的求解公式 1 粗糙集 粗糙集理沦中的上下近似的求解公式如下： 给定知识库，对于每个子集x u 和一个等价关系re i n d ( k ) ，定义两个子集： r x = u y u r l y n z ) ( 3 1 一1 ) 一r x = u y u r l y e x ) ( 3 一l 一2 ) 分别称它们为v 的r 上近似集和r 下近似集。 2 粗糙模糊集 在z p a w l a k 粗糙集模型中，论域u 上任意一个经典集合x 都可用关于 ( u ，r ) 的一对上下近似来描述，但在实际生活中，人们涉及到的知识或概念往往 兰卅人学顾士学位论文 是模糊不确定的，即牙是u 上的一个模糊集合，那么牙也可用一对模糊集合表 示，定义如下： 设( u ，尺) 是z p a w l a k 近似空间，即r 是论域u 上的一个等价关系，若戈是 u 上的一个模糊集合，则牙关于( u ，r ) 的一对上近似牙。和下近似薹。定义为u 上的一对模糊集合，其隶属函数分别定义为： 雪”( z ) = s u p 量( y ) ly 州。 ，x u ( 3 1 3 ) 星。( z ) = i n f 2 7 ( y ) j y 【z 】。) ，j u ( 3 - 1 4 ) 其中， x 。为元素x 在关系r 下的等价类。 3 2 特征函数和隶属函数的拓展 本章从形影关系的角度来求解粗糙集和粗糙模糊集上下近似及边界，从前 面的形影关系的概念介绍我们可知，经典集台的特征函数和模糊集合的隶属函 数都是形影关系，它们的形是论域u ，它们的影分别是 o ，1 ) 和 0 1 。我们对 形进行拓展就得到经典二元关系的特征函数函数和模糊二元关系的隶属函数。 3 2 1 经典二元关系的特征函数 在前面的章节中我们介绍了经典集合的特征函数，将经典集合特征函数的 论域u 由经典集合推广为序偶集合( 集合的元素是由序偶对组成) ，我们就得到 经典二元关系的特征函数。因为论域u 上的一个二元关系可以用一个序偶集合 表示，而序偶集合和经典二元关系的特征函数是一对应关系，所以二元关系 和经典二元关系的特征函数之间是一一对应关系。 举例况明：论域u ：z ：，_ ，x 4 上的u 上的一个二元关系r 可用序偶集合 = ， ， ， ) 表示，陇芋偶集合说明元素工l 和工f ，工2 和x ，b 和x ，x 。和x ，之间有关系，其他元素之间没有关系。那么该经典二元 关系的特征函数一。( z ，y ) 表示如下 摧十泛系的一1 2 下近似求解和决策表属性约简 3 2 2 模糊二元关系的隶属函数 将经典二元关系特征函数的值域由 0 ，1 ) 泛化成 0 1 所得的函数就是模 糊二元关系的隶属函数，我们用厶( x ，) 表示，在此不再举例。 3 2 3 经典等价关系的特征函数 对于经典二元关系的特征函数厶( 五y ) ，当 ( 1 ) 若 ( z ，z ) = l ，( v x ，则称f i e ( x ，y ) 为自反的： ( 2 ) 若l ( x ，y ) = 兀( j ，x ) ，( v x ，y ，则称l ( x ，y ) 为对称的； ( 3 ) 若l ( x ，：) i n f f 。( x ，y ) ，l ( y ，：) ，( v x ，y ，z ，则称厶( x ，y ) 为传递的。 若 ( x ，y ) 是自反、对称和传递的，则称l ( x ，y ) 为等价的。 下面我们说明一下，上面的定义和传统二元关系是一致的。 五( ，) ：1 ，v x u ，根据前面经典二元关系特征函数的定义，说明关系对 。_ x ，“属于关系r ，这证明了关系r 是自反的；当j z ，儿使得 ( 。) ：厶( 儿x ) = 1 时，说明关系对 y ，c 弘z ，l y e u 同时属于关系r ，符合了 若 r ，则 r 的条件，说明关系r 是对称的；当厶( t ，) = o 或l ( y ，= ) = o 时，公式i n ! 一。( x ，y ) ，f a ( y ，z ) f a x ，z ) ，v x ，y ，：u 成立，关系r 可以是传递的， 当 ( x ，y ) = l ( y ，：) = l 是，根据公式i d n f ，i f , e ( z ，y ) ，厶( y ，：) ) 厶( x ，z ) ，y ，= 5 u 可 以推导出厶( 平) ：i ，换句话说，关系对 y ，c y ，= ，v x ，y ，= u 属于关系r ，则推出 一 兰! ! ：! ! 查兰塑：l ! 堂些堡皇 c l 二，属于关系r ，也就是晚关系r 是传递的。 3 2 4 模糊等价关系的隶属函数 对于模糊二元关系的隶属函数厶( x ，y ) ，当 ( 1 ) 若厶( z ，y ) = l ，( v x e ，则称厶( z ，y ) 为自反的； 1 2 1 若，t 虹，力= ，i ( y ，幻，( v x ，力，则称，i ( x ，y ) 为对称的： ( 3 ) 若厶( x ，z ) i n f f v ( x ，y ) ，瓜( y ，z ) ，( v x ，y ，z ，则称厶( z ，y ) 为传递 的。 若厶( x ，y ) 是自反、对称和传递的，则称厶( z ，) 为等价的。 3 3 基于形影关系的上下近似及边界的统一求解公式 下面我们给出在形影关系下，集合( 经典集合和模糊集合) 及二元等价关 系( 经典二元关系及模糊关二元系) 上下近似及边界的求解公式，并汪明这些 公式与传统的求解公式是等价的。 1 是经典集合，r 是经典二元关系给定知识库( u ，r ) 及论域c ，的一子集 ，将二元关系及子集分别用经典二元关系的特征函数 ( x ，y ) 及经典集合的 特征函数厂( x ) 表示，那么，我们可以从以下公式求得x 的r 上、下近似及边 界： ( ) = s u p in f ( f 、( y ) ，厶( ，y ) j 】x u ( 3 3 一1 ) l f 位( 一) = i n f f su p ( f ( y ) ( 1 _ 几( ，y ) ) ) xeu ( 3 - 3 2 ) 】( z ) 2i 1 1 f ，万( z ) ，1 一五( x ) j u ( 3 3 3 ) 2 牙是模糊集合，r 是经典二元关系给定论域u 及u 上的二元关系r 和 u 上的模糊子集戈，将r 和霄分别用经典二元关系的特征函数一。( x ，y ) 及模糊 集合的隶属函数厂，( x ) 表示，模糊子集戈的r 上、下近似及边界求解如下： 拱于泛系的一卜下近似求觯和决策表属性约简 岛( x ) 一u p i n f f f ( y ) ，g ( x ，y ) z u ( 3 3 4 ) 么( x ) i 。n f ， s u p 厶( y ) ，( 1 一g ( x ，y ) ) x u ( 3 3 5 ) 厶帆( x ) = i n f 岛( x ) ，1 名( x ) x u ( 3 3 6 ) 3 戈是模糊集合，膏是模糊二元关系知识库( ，夏) 是模糊知识库，戈是r 上的一个模糊子集，那么它的上下近似及边界可以用如下公式求得： ，雨( z ) 一u p i n f 厂f ( j ，) ，月( x ，川 x u ( 3 3 7 ) 奄( x ) 2 嘴n f s u p ( 凡( y ) ，( 1 一厶( x ，y ) ) ) x u ( 3 3 8 ) 如( 时1 ( x ) = i n f 岛( x ) ，l 一继( x ) ) x 己， ( 3 3 9 ) 从( 3 - 3 4 ) 、( 3 - 3 7 ) 两个求解公式中可以