（计算机软件与理论专业论文）rough集中若干问题的研究.pdf

摘要 摘要 r o u g h 集理论是一种处理含糊和不精确性问题的新型数学工具。z p a m a k 建 立的r o u g h 集理论有3 个部分：( 1 ) 使用上近似和下近似表示知识的不确定性； ( 2 ) 对数据的约简；( 3 ) 基于r o u g h n e s s 的推理。他把那些无法确定的个体都 归属于边界线区域，而这种边界线区域被定义为上近似集和下近似集之差集，由 于上近似集和下近似集都可以通过等价关系给出确定的数学公式描述，所以含糊 元素数目可以被计算出来，从而实现了g f r e g e 的边界线思想。 r o u g h 集理论在人工智能和认知科学研究领域有十分重要的应用；尤其为机 器学习、知识获取、决策分析、数据库的知识发现、专家系统和模式识别等领域 提供了一种很有效的新的数学方法。 本文主要研究内容如下： _ r o u g h 集中近似质量的新认识在r o u g h 集近似空间中提供了对一个列象 集近似的准确性因子啦和属性集问依赖程度因子y 。对于因子a 可以给出精确 性因子兀与之比较；通过基于集合的距离度量公式，可以给出近似差错率来 解释c t ，和y 。如果把数据空间从1 维拓广到k 维，可以得到k 维近似空f 白j 和 相应的近似因子。 基于带状划分数据库的发现函数依赖集的方法这种方法基于一致集的概 念。根据一致集导出最大集及其补集，然后生成最小非平凡函数依赖集。通 过使用带状划分数据库减少求一致集的运算次数，使用逐层求精的算法来计 算最小非平凡函数依赖集的左部；并从时间复杂度上与其它方法进行了比 较。 _ 基于r o u g h 集的数据约简讨论用r o u g h 集知识，对信息系统进行数据约 简。给出用分明矩阵和分明函数的属性约简方法，对决策表的属性约简和属 性值约简，以及晟小决策化算法。 一 r o u g h 集与其它数据推理讨论r o u g h 集与概率逻辑，贝叶塞规则，证据理 论和模态逻辑的关系，指出它们之间存在的一致性。 一基于r o u g h 集的形式化概念分析形式化概念分析有助于数据的表达和分 析。本文讨论用r o u g h 集分别对一个对象集、一个特征集和由对象集与特征 摘要 集形成的对的近似来形成各自的可定义的形式化概念。 r o u g h 包含度统一r o u g h 集中各种度量方式r o u g h 集中提供了各种度量 方式，可以用r o u g h 包含度的概念来统一这些度量，这有助于人们理解r o u g h 集的实质。 关键词：r o u g h 集；近似质量：最小函数依赖集；数据约简：数据推理：形式化 概念；r o u g h 包含度。 中图分类号：t p l 8 r o u g h 集中若千问题的研究 2 溥士学位论文 a b s t r a c t a b s t r a c t r o u g h s e tt h e o r yi san e wm a t h e m a t i c a lt o o lf o ru s ei nc o m p u t e ra p p l i c a t i o n si n c i r c u m s t a n c e sw h i c ha r ec h a r a c t e r i z e d b yv a g u e n e s sa n du n c e r t a i n t y r o u g h s e t t h e o r yb yz p a w l a kh a st h r e ep a r t s ：( 1 ) t h er e p r e s e n t a t i o no fu n c e r t a i nk n o w l e d g eb y u s i n gu p p e ra p p r o x i m a t i o na n dl o w e ra p p r o x i m a t i o n ( 2 ) d a t ar e d u c t i o n ( 3 ) r e a s o n i n g w i t hv a g u ea n d o ri m p r e c i s ek n o w l e d g e i nt h et h e o r y , a no b j e c t ，i m p o s s i b l et ob e d e t e r m i n e do nt h eb a s i so fk n o w n k n o w l e d g e ，b e l o n g st ot h eb o u n d a r yr e g i o nw h i c h i s t h em i n u so fu p p e ra p p r o x i m a t i o na n dl o w e ra p p r o x i m a t i o n t h en u m b e ro fv a g u e e l e m e n t si nt h eb o u n d a r yr e g i o nc a nb ec a l c u l a t e do nt h eb a s i so ft h em a t h e m a t i c a l d e s c r i p t i o n o fu p p e ra n dl o w e ra p p r o x i m a t i o n s b y t h e e q u i v a l e n c er e l a t i o n ，t h i s r e a l i z e st h ei d e ao f t h eb o u n d a r y r e g i o nb yg f r e g e r o u g hs e tt h e o r yh a sm a n yi m p o r t a n ta p p l i c a t i o n si na r t i f i c i a li n t e l l i g e n c ea n d c o g n i t i v es c i e n c e ，e s p e c i a l l y i nt h er e p r e s e n t a t i o no fa n dr e a s o n i n gw i t hv a g u eo r i m p r e c i s ek n o w l e d g e ，m a c h i n el e a r n i n g ，k n o w l e d g ea c q u i s i t i o n ，d e c i s i o na n a l y s i s ， k n o w l e d g ed i s c o v e r yf r o md a t a b a s e s ，p a t t e r nr e c o g n i t i o na n de x p e r ts y s t e m s t h em a i nw o r ko ft h i sp a p e ri sa sf o l l o w s ： _ r e c o g n i t i o no fa p p r o x i m a t i o nq u a i l t yi nr o u g hs e t sr o u g ha p p r o x i m a t i o n s p a c ep r o v i d e s t h ea c c u r a c yf a c t o r o fa l l o b j e c t s e t a p p r o x i m a t i o na n dt h e d e g r e ef a c t o rvo fd e p e n d e n c yf o rs e t so fa t t r i b u t e s t h ep r e c i s i o nf a c t o r 兀o f a p p r o x i m a t i o nc a nb ei n t r o d u c e dt oc o m p a r ew i mo 【b ya p p r o x i m a t i o ne r r o r r a t e sb a s e do nt h ed i s t a n c em e a s u r eo fs e t s ，t h ef a c t o r s o 【，y a n d7 cc a nb e r e i n t e r p r e t e d b yd e v e l o p i n go n ed i m e n s i o nd a t as p a c et okd i m e n s i o ns p a c e ，k d i m e n s i o n a p p r o x i m a t i o ns p a c ea n d i t sa p p r o x i m a t ef a c t o r sc a nb eo b t a i n e d 一am e t h o df o rd i s c o v e r i n gf u n c t i o n a l d e p e n d e n c i e sb a s e do nt h es t r i p p e d p a r t i t i o nd a t a b a s e t h i se f f i c i e n tm e t h o di sb a s e do nt h ec o n c e p to f a g r e es e t s f r o ma g r e e es e t s ，m a x i m a ls e t sa n di t sc o m p l e m e n t sa r ed e r i v e d ，a n da l lm i n i m a l n o n - t r i v a lf u n c t i o n a ld e p e n d e n c i e sc a b h eg e n e r a t e d t h ec o m p u t a t i o no fa g r e e s e t sc a nb ed e c r e a s e d b yu s i n gt h es t r i p p e dp a r t i t i o nd a t a b a s e al e v e l w i s e a l g o r i t h m i su s e df o r c o m p u t i n gt h e l e f th a n ds i d e so fm i n i m a ln o n t r i v a l r o u g h 集中若干问蹶的研究 3 博士学位论文 a b s t r a c t f u n c t i o n a l d e p e n d e n c i e s t h i s m e t h o di sb e t t e rt h a no t h e rm e t h o d sf o r d i s c o v e r i n gf u n c t i o n a ld e p e n d e n c i e so nt i m ec o m p m x _ d a t ar e d u c t i o nb a s e do nr o u g hs e t s r o u g h s e t sa l l o w p e o p l et od e t e r m i n ef o r ag i v e ni n f o r m a t i o ns y s t e mt h em o s ti m p o r t a n ta t t r i b u t e sf r o ma c l a s s i f i c a t o r y p o i n to fv i e w t h ed i s c e r n i b i l i t ym a t r i xa n dt h ed i s c e r n i b i l i t yf u n c t i o nc a nh e l p p e o p l et oc o n s t r u c te f f i c i e n ta l g o r i t l m a sr e l a t e dt ot h eg e n e r a t i o no fr e d u c t s t h e r e d u c t i o no nd e c i s i o nt a b l e si n c l u d e sa t t r i b u t er e d u c t i o n ，a t t r i b u t ev a l u er e d u c t i o n a n dm i n i m a ld e c i s i o n a l g o r i t h m s r o u g h s e t sa n do t h e rd a t ar e a s o n i n gi nt h i sp a p e r , t h er e l a t i o n s h i p sb e t w e e n r o u g h s e t sa n d p r o b a b i l i t y l o g i c ，b a y e s r u l e ，d e m p s t e r - s h a f e r e v i d e n c e t h e o r y , m o d a ll o g i ca r ed i s c u s s e dr e s p e c t i v e l y 一f o r m a lc o n c e p ta n a l y s i sb a s e do nr o u t hs e t sf o r m a l c o n c e p ta n a l y s i s i s u s e f u lf o rr e p r e s e n t a t i o na n d a n a l y s i so f d a t a t h i sp a p e r p r e s e n t saa p p r o a c hf o r f o r m a lc o n c e p t st or e s p e c t i v e l ya p p r o x i m a t ea g i v e no b j e ds e t ，ag i v e nf e a t u r es e t a n da p a i ro f ag i v e no b j e c ts e ta n da g i v e nf e a t u r es e t t h i sa p p r o a c hi sb a s e do n r o u g h s e t _a p e r s p e c t i v e o nm e a s u r e sf o r r o u g h s e td a t a a n a l y s i s b a s e do n r o u g h i n c l u s i o nd e g r e ei nt h i sp a p e r ，t h e r e l a t i o n s h i p sb e t w e e ni n c l u s i o nd e g r e ea n d e a c ho fv a r i o u sm e a s u r e si nr o u g hs e tt h e o r ya r ed i s c u s s e d t h ef a c tt h a tv a r i o u s m e a s u r e si nr o u g hs e tc a nb er e d e f i n e db yu s i n gt h ec o n c e p to fi n c l u s i o nd e g r e e w i l lb eh e l p f u lf o rp e o p l et ou n d e r s t a n dt h ee s s e n c eo f r o u g h s e t k e yw o r d s ：r o u g hs e t ；a p p r o x i m a t i o nq u a l i t y ；m i n i m a lf u n c t i o n a ld e p e n d e n c y ；d a t a r e d u c t i o n ；d a t ar e a s o n i n g ；f o r m a lc o n c e p t ；r o u g hi n c l u s i o nd e g r e e r o u g h 集中若干闷题的研究 4 博士学位论文 第一章前言 1 1 研究背景与意义 第一章前言 r o u g h 集理论由波兰数学家z p a w l a k 在1 9 8 2 年提出，它是一种处理含糊和 不确定性问题的新型数学工具。起初，由于这个理论建立在商集理论之上，较为 复杂的数学使得这个理论并未引起人工智能研究者的注意，直到2 0 世纪8 0 年代 末，特别是在1 9 9 5 年，在a c mc o m m u n i c a t i o n 上，以计算机科学新进展发表了 p a w l a k 对这个理论的通俗解释之后 p a w 9 5 】，这个理论才被计算机科学家认识。 p a w l a k 建立的r o u g h 集理论有3 个部分：( 1 ) 使用上近似和下近似表示知 识的不确定性：( 2 ) 对数据的约简；( 3 ) 基于r o u g h n e s s 的推理。他把那些无法 确定的个体都归属于边界线区域，而这种边界线区域被定义为上近似集和下近似 集之差集，由于上近似集和下近似集都可以通过等价关系给出确定的数学公式描 述，所以含糊( v a g u e ) 元素数目可以被计算出来，即在真假二值之间的含糊程 度可以计算，从而实现了g f r e g e 的边界线思想。r o u g h 集理论的主要贡献在于 它恰好反映人们用r o u g h 集方法处理不分明问题的常规性，即以不完全信息或 知识去处理一些不分明现象的能力，或依据观察、度量到的某些不精确的结果而 进行分类数据的能力。 r o u g h 集理论在人工智能和认知科学研究领域有着十分重要的应用；尤其为 机器学习、知识获取、决策分析、数据库的知识发现、专家系统和模式识别等领 域提供了一种很有效的新的数学方法。 1 2 研究现状 目前，对r o u g h 集和基于r o u g h 集的数据处理的研究大致可分为两个方面。 一方面是对r o u g h 集理论的研究，如r o u g h 集拓广、r o u g h 集代数、r o u g h 集 拓扑、r o u g h 逻辑及处理近似推理的逻辑工具等。另一方面是对r o u g h 集应用的 研究，利用r o u g h 集处理的主要问题包括数据库中的数据约简、数据相关性的 发现、数据意义的评估、由数据产生决策控制算法、数据的近似分类、数据中范 式的发现以及因果关系的发现等。r o u g hm e r e o l o g y 方法是对r o u g h 集理论的扩 r o u g h 集中若币褥蕊媳研究 博士学位论文 第一章前言 充，它提供了智能a g e n t 在分布式环境下对个体进行综合和分析的一种方法学 已经被用作研究信息g r a n u l e 计算的基础，朝着用词计算的公式化方向发展。 1 3 本文工作 本文主要研究内容如下： 一r o u g h 集中近似质量的新认识在r o u g h 集近似空间中提供了对一个对象 集近似的准确性因子d 和属性集问依赖程度因子v 。对于因子d 可以给出精确 性因子n 与之比较；通过基于集合的距离度量公式，可以给出近似差错率来 解释a ，兀和y 。如果把数据空间从l 维拓广到k 维，可以得到k 维近似空间和 相应的近似因子。 _ 基于带状划分数据库的发现函数依赖集的方法这种方法基于一致集的概 念。根据一致集导出最大集及其补集，然后生成最小非平凡函数依赖集。通 过使用带状划分数据库减少求一致集的运算次数使用逐层求精的算法来计 算最小非平凡函数依赖集的左部；并从时间复杂度上与其它方法进行了比 较。 _ 基于r o u g h 集的数据约简讨论用r o u g h 集知识。对信息系统进行数据约 简。给出用分明矩阵和分明函数的属性约简方法，对决策表的属性约简和属 性值约简，以及最小决策化算法。 一r o u g h 集与其它数据推理讨论r o u g h 集与概率逻辑，贝叶塞规则，证据理 论和模态逻辑的关系，指出它们之删存在的一致性。 _ 基于r o u g h 集的形式化概念分析形式化概念分析有助于数据的表达和分 析。本文讨论用r o u g h 集分别对一个对象集、一个特征集和由对象集与特征 集形成的对的近似来形成各自的可定义的形式化概念。 一 r o u g h 包含度统一r o u g h 集中各种度量方式r o u g h 集中提供了各种度量 方式，可以用r o u g h 包含度的概念来统这些度量，这有助于人们理解r o u g h 集的实质。 1 4 本文结构 本文共分八章，文章结构及备章内容简介如下： r o u g h 集中若千鹤题的研究 6 博士学位论文 第一章前言 第章为前言，简单介绍r o u g h 集理论的背景、研究现状和研究意义， 最后综述本文的工作及结果。 第二章首先从介绍等价关系、等价类和划分入手，介绍r o u g h 集的基本 概念。指出信息系统与分明矩阵和分明函数的关系：对z ，p a w l a k 的近似空间中 提供的一个对象集近似的准确性因子和一个属性集对另一个属性集的依赖程度 因子给出新的认识；并把数据空问从l 维扩展到k 维，可以得到k 维近似空间和 相应的近似因子。 第三章首先对己知的发现函数依赖集的方法进行总结，指出这些方法都使 用了根据属性集的知识来定义等价类，形成划分，这与r o u g h 集定义中的知识是 相通的。然后给出一种基于带状划分的发现函数依赖集的方法，这种方法减少了 运算的次数，其结果较优。同时对方法中的结论给出了严格的证明并指出这 种方法可用到对一致决策表的属性约简上。 第四章讨论基于r o u g h 集的数据约简。首先介绍基于r o u g h 集的约简的 概念，给出基于分明矩阵和分明函数的属性约简的算法，然后用r o u g h 集的方 法对决策表进行属性约简和属性值约简，给出最小化决策算法。 第五章讨论r o u g h 集与概率逻辑，贝叶塞规则，证据理论和模态逻辑的 关系，指出它们之间存在的一致性。 第六章讨论用r o u g h 集分别对一个对象集、一个特征集和由对象集与特 征集形成的对的近似来形成各自的可定义的形式化概念。 第七章在r o u g h 集中提供了各种度量方式，如对一集合近似的准确性因 子，r o u g h 隶属函数，对一个划分近似的准确性因子和近似质量，以及属性i 目的 依赖程度因子和属性重要程度因子等，可以通过r o u g h 集中的包含度( i n c l u s i o n d e g r e e ) 概念来统一这些度量，这有助于人们理解r o u g h 集的实质。 第八章总结全文指出本文研究成果及后续工作。 r o u g h 集中若干阔题的研究 7搏士学位论文 第二章r o u g h 集和r o u g h 近似质量 第二章r o u g h 集和r o u g h 近似质量 本章从介绍等价关系、等价类和划分入手，介绍r o u g h 集的基本概念。指 出信息系统与分明矩阵和分明函数的关系；对z p a w l a k 的近似空间中提供的一 个对象集近似的准确性因子和一个属性集对另一个属性集的依赖程度因子给出 新的认识；并把数据空间从1 维扩展到k 维，可以得到k 维近似空问和相应的近 似因子。 2 1 等价关系、等价类和划分 关系的某些性质是指自反性、对称性和传递性。 定义2 1 设r 是集合a 上的二元关系，如果对v a a ，有( a ，口) r ，则称 r 是a 上的自反关系。 定义2 2 设r 是集合a 上的二元关系，对 c a ，6 e a ，如果有( d ，6 ) r ，则 必有( 6 ，) r ，则称r 是a 上的对称关系。 定义2 3 设r 是集合a 上的二元关系，对v a ，b ，c a ，如果有( 日，b ) r 和 ( 6 ，c ) r ，必有( d ，c ) r ，则称r 是a 上的传递关系。 定义2 4 设r 是集合a 上的二元关系，如果它是自反、对称和传递的，则 它是a 上的等价关系。 例如，同余模关系。设m 是大于1 的正整数，可以证明 r = ( n ，b ) a = b ( m o d 脚) ) 是整数集z 上的等价关系。 定义2 5 设r 是集合a 上的一个等价关系，与a 中的一个元素a 相关的所 有元素的集合被称做a 的一个等价类，记为 日 。形式地，【口】。= b ( d ，6 ) r ) 。 同余模m 关系的等价类被称做同余类模m 。个整数a 模m 的等价类可以 表示成 口】。= 一，一2 m ，a m ，口+ m ，a + 2 m ，) 性质2 1 设r 是集合a 上的一个等价关系，下面的陈述是等价的，其中 r o u g h 集中若干偶殛瓣研究博士学位论文 第二章r o u g h 集和r o u g h 近似质量 a b a ( 1 ) a r b ： ( 2 ) 口】= b 】；( 当仅考虑一个关系时，可略去等价类表示中的下标) ( 3 ) a n 【b 】中。 现在说明一个等价关系如何划分一个集合。集合s 的一个划分是s 中不相交 的非空子集的聚合，使得s 作为它们的并。换句话说，子集丘，f ，( 自然数集) 形成的一个划分，当且仅当： ( 1 ) 对i i ，a 中； ( 2 ) 当f j 时，a 。n a ，= ( i s ； ( 3 ) u 。a ，= s 。 设r 是集合a 上的一个等价关系，因为口 口 ，所以u 。【8 】- a ，即a 等 价类的并是a 的全体元素。根据性质2 1 ，这些等价类或者相等或者分离，所以 有当 a 】【b 时陋 n b = 巾。 由此可见，等价类形成a 的一个划分。 性质2 2 设r 是集合s 的一个等价关系，那么r 的等价类形成s 的一个划 分；给定集合s 的一个划分( a 。i i i ) ，存在一个等价关系r 使得每个a i , i ，作 为它的等价类。 在同余模m 关系中，存在m 个不同的同余类模m ，记成【o 】。，【1 】一，【m 一1 】， 形成整数集的一个划分。 等价关系可用来划分等价类。全集中的任意子集按等价关系被分类，有日_ j 在 给定的全域u 的子集中能全被分成类，有时不能被分成类，我们称能全被分成 类的子集u 是可定义的；而不能全被分成类的子集是不可定义的。如果有 些子集在某一等价关系下不能全被分成类，那么它可用r o u g h 集方法近似地分 类。 r o u g h 集中若干闯鼹的研究 9 博士学位论文 第二章r o u g h 集和r o u g h 近似质量 2 2 信息系统与分明矩阵和分明函数 2 2 1 信息系统 定义2 6 一个信息系统s = ，q ，v ，f ) ，其中u 是有限菲空对象的集合 称为封闭世界：q 是有限非空属性的集合；v = u 删，是属性q 的域；f 是 u x q _ 矿的一个完全确定函数，称为信息函数。 设u ，且x 中，称x 为s 的一个概念，一个概念可能具有某种含义。 设a q 工，y u ，x a y 9 v a af ( x ，口) = f ( y ，口) 。若x a y ，则根据a 的 知识，x 和y 是不可分明的( i n d i s c e m i b l e ) 。 定义2 7 设x q ，i n d ( a ) = ( x ，j ，) e ，u f x a y ) 。称i n d ( a ) 为u 上关于 a 的不可分明关系，它是一个等价关系。 x q ，s 中根据a 的等价关系i n d ( a ) 的一个等价类i x 。可描述成 【z 。= 抄u f ( x ，y ) i n d ( a ) ，j u 。这样，根据a 对u 的划分只可定义为： 只= i x 。i j u 设x u ，令只0 ) = 扛1 。如果i n d ( a ) ，d ( 曰) ，则称划分乓比划分细 小，表示为只s 匕。若对v x u ，巴( x ) = x ，则称只是恒等划分，它是任何非 空集的最细小的划分。 r o u g h 集数据分析( r s d a ) p a w 9 1 是根据某信息粒度( 属性子集的知识) 来 获取u 的知识。 设x 只，x 是根据a 的一个等价类，也称x 为s 中一个a _ e l e m e n t a r y 集， 我们用d e s 。( x ) 来描述x ： d e s 月( x ) = ( o ，b ) jf ( x ，a ) = 6 ，v x z ，a a 由于x 中任何两个对象在a 中的同一属性上的值一样，我们用其属性与属 性值对来描述x 。 r o u g h 集中若干问题的研究 博士学位论文 第二章r o u g h 集和r o u g h 近似质量 例2 1 考虑一个简单的m e d i c a l 数掘集。这个信息系统s = u ，q ，v ，_ 厂) 其中u = 。l ，- 一，芏l o ，每个z ，( 1 i l o ) 代表个病人：q = b ，c 2 ，d ，c 。，岛代 表医学的测试或诊断，d 代表专家的决断； 屹= o ，l ，2 ) ，= ( l ，h ) 似= l o w ，h = h i g h ) ，= o ，1 ) 。s 可用表2 1 来表示，f 也反映在其中了，如f ( x 。，c ) = 0 。 设a = “，c ： q ，则s 中根据a 形成的等价类有： 【x l 】。= 葺) x ：l = k 】。= ，x 3 ) x 4 = x s = x 4 ，b x 6 = 【一 = ( x 6 ，x 7 ) 】= 【b 。= x b ，x 9 ) 工i o 】= o s 中关于a 的不分明关系( 等价关系) i n d ( a ) 由等价类中任两个对象形成的 对组成，如i n d ( a ) 中包含( 屯，x ：) ，( x ：，x ，) ，( x ，z ：) ，( z ，z ，) 元素，这些是由【x ：】。中 的元素形成的。 表2 1一个医学数据集m e d i c a l o b j e c t a t t r i b u t e s u c 1c 2 d x i ol0 x 2 oh0 x 3 0ho llo x 5 1ll x 6 1h1 x 7 lh1 x 8 2lo x 9 2li x 1 0 2hl r o u g h 集中若干阀题的研究 1 1 博士学位论文 第二章r o u g h 集和r o u g h 近似质量 而由i n d ( a ) 揪u 的个划分只为 只= x ， ，缸：，墨 ， x 4 ，黾 ， ，而 ， ，岛) ， 。 只中的一个a _ e l e m e n t a r y 集( 等价类) x 2 】。可描述为 d e s 。( x 2 】。) = ( q ，o ) ，( c 2 ，日) ) 每个a _ e l e m e n t a r y 集代表了a b a s i c 知识，表达一个最小的可分明的对象组， 称为c e l l 。在近似空间a s = ( u ，i n d ( a ) ) 中，任何有限个a _ e l e m e n t a r y 集的并集 都是可定义的( d e f i n a b l e ) ，如 z 2 ，x 3 u ( x 。，x 5 ) = x 2 ，x 3 ，- ，z 5 ) 是一个可定义集。 我们考虑q _ e l e m e n t a r y 集，它是由i n d ( q ) 形成的等价类，这样的等价类称 为原子( a t o m ) ；在这个例中，q e l e m e n t a r y 集为： x i ) ，( 工2 ，x 3 ) ， 工4 ) ， x 5 ，f x 6 ，x 7 ，( 毛 ， x 9 ) ，( x i o ) 任何这些原予的并集都是a s = ( u ，i n d ( q ) ) 中的个可定义集。 2 2 2 分明矩阵和分明函数 常常我们要关心对象的分明性或可区分性，在这种情形下，我们可把信息系 统表示成分明矩阵或分明函数 s r 9 2 1 ；它们含比信息系统少的数据，但含有用属 性集来描述概念所需的信息。 设s = u ，q ，y ，f 是一个信息系统，u = “，h ，q = a l ，一，a 。) ，s 的分 明矩阵m ( q ) 是一个n x n 的方阵，设x ，x ，u ，m ( 囝的元素m 。为：若x i ，x j 属于 i n d ( q ) 的n - - 个等价类，则m i j = 0 ；否则，m i j = a q f ( x ，口) f ( x ，口) ) 。显然， 肌f = 2 ，r m 。= 0 ，即m ( q ) 是对称的。所以只需计算m ( q ) 的下三角元素即 m “，1 j f s n l 。 信息系统s 的分明函数磊是关于n 个布尔变量q ，盘：，吒的一个布尔函数， 口l ，a 2 ，a 。分别对应于属性a ，a 2 ，口。： 兀( 口i ，日2 ，d 。) = v ( 棚f ) l l ， i n 一1 ，m 口巾) r o u g h 集中瞢干拇磊瓣研究 1 2博士学位论文 第二章r o u g h 集和r o u g h 近似质量 其中v ( ) 是所有口m 口对应的口的变量的析取。 例2 。2 考虑一个数据集b i n a r y ，这个信息系统s = ，q ，v ，厂) 可表示为表 2 2 。 它的分明矩阵m ( q ) 可用表2 3 表示，其中的空格代表0 ，它的分明函数为： 兀( 口，c ，d ，e ，o ) = c e o a v d ) a p vp ) a ( c v o ) a o vo ) ( a v c v d ) ( 日v d v o ) ( c ve v o ) ( a v c v d v o ) a ( 口v c v d v e v o ) 其中a s c ，d ，e ，o 都表示布尔变量。 表2 2信息系统b i n a r y uacdeo x i o11l1 x 2 11o1o x 3 lo0ll x 4 l0ol0 x 5 lo0oo x 6 l101l 表2 3 分明矩阵m ( q ) l23456 1 2a d o 3a c dc 0 4 a c d oco 5a c d e oc ee oe 6a docc oc e o r o u g h 集中若干闯联的研究 1 3 博士学位论文 第二章r o u g h 集和r o u g h 近似质嚣 2 3 r o u g h 集 r o u g h 集理论是一种处理含糊和不精确性问题的新型数学工具，在机器学习、 知识获取、决策分析和数据库的知识发现等方面有重要的应用。z p a w l a k 提出的 r o u g h 集 p a w 8 2 是建立在由等价关系对全域进行划分的基础上，每个等价类是 一个基本的信息粒度。一个等价关系是按信息系统中的某个属性的知识来形成 的，全域的一个划分代表了全域的一种信息粒度化的观点。在信息系统中一些对 象的集合不能根据己知的属性集或等价类的知识来分明，但可以近似的描述它 们。一个对象集合的近似由这个集合下近似和上近似组成的粗糙集来描述，一个 集合的下近似是包含在这个集合内的等价类的并，它的上近似是与这个集合相交 的等价类的并。 定义2 8 设一个信息系统s = u ，q ，v ，f ) ，a q 是一个已知的属性集，由 它形成了s 中的一个近似空间a s = ( u ，i n d ( a ) ) ；对于x u ，则x 在a s 中的 下近似( 1 0 w e ra p p r o x i m a t i o n ) a x 和上近 以( u p p e ra p p r o x i m a t i o n ) a 一定义为： a x = 扛u | x 】j z ) = u y 只j ， a x = x u 1 b 】n z 中) = u r 只i y n x 巾 ( a x ，a x ) 称为r o u g h 集。 y 是u 上按等价关系i n d ( a ) 作成的等价类。下近似被解释为所有那些被 包含在x 里面的等价类的并集：上近似被解释为所有那些与x 有交的等价类的 并集。显然a a x 。上近似和下近似之间的差被称做x 的a 边界线集，记 为b n ( x ) ： b n ( x ) = a x a x 它是那些通过等价关系i n d ( a ) 即不能在x 上被分类，也不能在一z 上被分类 的元素的集合。以上说明如果通过已掌握的信息看这个集合x ，只能观察到x 的下近似和上近似，而不能观察到x 的全貌。边界线集为空集，则通过等价关 系可以恰当地观察x ；相反，b n 。( x ) o ，只能r o u g h 地观察集合x 。前者是 分明的，而后者是r o u g h 的。形式上，集合x 是a - 分明的当且仅当b n 。( x ) = o ， r o u g h 集中若干问惩的研究 1 4博士学位论文 第二章r o u g h 集和r o u g h 近似质量 否则x 是a _ r o u g h 的。 定义2 9 0 ) x 是a j j 丁定义的，当且仅当4 x = a x ：( 2 ) x 关于a 或1 n d ( a ) 是r o u g h 的，当且仅当a x a x 。 事实上，a x 是包含于x 中的最大a 可定义集，类似于点拓扑中的内点：a x 是包含x 的最小a 可定义集，类似于点集拓扑中的闭包。近似概念能使我们精 确地讨论关于不精确的东西。 x 的a 一正区域( a a p o s i t i o nr e g i o n ) 被记成p o s 月( ) = a x ，它是如此一些 个体元素的集合，这些元素完全属于x 的成员。 x 的a 负区域( a n e g a t i v er e g i o n ) 被记成n e g ( x ) = u a 戈；它是如此 一些个体元素的集合，这些元素不是任意模糊用等价关系i n d ( a ) 确定的，它 们不属于x ，而是属于x 的补集。 例2 3 考察例2 1 中的表2 1 x = x 5 ，z6 ，x7 ，x ”x i o 是u 中的一个子集，根据属性集爿= 弛，c ： 的 知识，有： a x = x 6 ，x 7 u 工i o ) = x 6x 1 ，x l o ) a x = x 4 ，x 5 ) u x 6x 7 ) u ( x 8 ，x 9 u x l o = x 4 ，z 5 ，x 6 , x 7 ，x 8 ，x 9 ，x i o b n h ( 彳) = a x a x 2 ( x 4 ，x 5 ，x 6 ，x 9 从表2 1 中可显示地看出x 代表有病人的集合( d 一1 ) ；a x 中的病人肯定有病； a 中的病人可能有病；b n 。( x ) 中的病人不能分到x 上，也不能分到上。 2 4 r o u g h 集的性质 直接从上近似集和下近似集的定义，可以得到它们的一些性质 性质2 3 ( 1 ) a x x ( 一2 2 a x ( 2 ) 4 由= a m = m r o u g h 集中若干阔题的研究博士学位论文 第二章r o u g h 集和r o u g h 近似质量 ( 3 1 a u = 一u 2 u ( 4 ) a 一( x w y ) 2 a x u 墨y ( 5 ) a ( x u y ) = a u a y ( 6 ) 粤( xny ) = a xna y ( 7 ) a ( x n y ) a x n a y ( 8 ) x y 。a x 垂y ( 9 ) x y j a x a y 0 0 ) 4 ( z ) = 爿 ( 1 1 ) 爿( ) 2 a x ( 1 2 ) a a x ：a a x = a x ( 1 3 a a x ：a a x ：d x 证明：在不引起混淆时，我们省略了下角标，如【x 】简写为【x 】。 ( 1 ) a ) 若x g 爿，t j j x _ c x ，又x x ，所以x x ：故g x b ) 若x z ，则【x 】n x 巾( 因为x 【x 】n x ) ，所以z a x ；放 xe a xa ( 2 ) a ) 由( 1 ) 可知a q b o ，并且空集包含于任意集合中：所以a d o = 中 b ) 假设a d o m ，则存在x ，使得x 彳o ，因此【x n 中中，但 【x 】n 中