（计算机应用技术专业论文）粗糙集理论约简算法的研究.pdf

川i i iiii i1 1 1 1 1i ii ii i iiiil ：。y 18 8 0 6 0 1 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得武汉理工大学或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示了谢意。 、 签名：日期：兰笙：3 学位论文使用授权书 本人完全了解武汉理工大学有关保留、使用学位论文的规定， 即学校有权保留并向国家有关部门或机构送交论文的复印件和电 子版，允许论文被查阅和借阅。本人授权武汉理工大学可以将本 学位论文的全部内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存或汇编本学位论文。同时授权经武汉理 工大学认可的国家有关机构或论文数据库使用或收录本学位论 文，并向社会公众提供信息服务。 ( 保密的论文在解密后应遵守此规定) 研究生( 签名) ：忑芗幺导师( 签名) 掰日粉l l , m 。婶 摘要 粗糙集理论是由z p a w l a k 于1 9 8 2 年提出的，它是一种处理信息的工具，可 以有效地对不精确、不一致、不完整信息进行分析。有关粗糙集理论的研究现 已成为热点，该理论的应用也非常广泛，如入侵检测、数据挖掘、知识发现等。 粗糙集理论中的一个重要内容是属性约简，属性约简的目的是在保持决策 表分类能力不变的情况下删除冗余的属性，得到一个精简的决策表，以便于以 后的计算。 属性约简算法有很多，文中主要介绍基于差别矩阵的约简算法。首先介绍 了几种经典的属性约简算法，给出了它们的定义，对求解过程加以分析，指出 了它们的优缺点，对于它们的缺点，给出了相关的解决方法，并给出实例。 其次，介绍了_ 种新的属性约简模型，该模型与传统模型是等价的。在文 中给出了该模型的相关定义和求解属性约简的算法，并通过实例对算法的求解 过程加以演示。 再次，介绍一种基于差别矩阵的最小约简算法，该算法通过u ( e 划分来计 算最小约简，并指出其不足，如存在重复计算、结果错误等。分析了算法的不 足后，本文给出了一种改进算法，该算法首先对决策表中的数据进行压缩，删 除冗余数据，降低了时间复杂度和空间复杂度，然后用基于属性核的思想求解 最小约简。 最后，对改进算法进行分析。在决策表中冗余数据较多的情况下，改进算法 才能充分发挥其优势。该算法还有待进一步完善，如将该算法与智能计算相结 合以提高计算效率。 关键字：粗糙集，差别矩阵，属性约简，最小约简 a b s t r a c t r o u g hs e t st h e o r y , p r e s e n t e db yp a w l a ki n 19 8 2 ，i sa l lt o o lt oh a n d l e i n f o r m a t i o n ，i t c a l l e f f e c t i v e l y d e a l 诵li m p r e c i s e ，i n c o n s i s t e n t , i n c o m p l e t e i n f o r m a t i o n , e t c 1 1 1 er e s e a r c ho nr o u g hs e tt h e o r yh a sb e c o m eah o ts p o t ，t h et h e o r yi s w i d e l ya p p l i e di ni n s t r u s i o nd e t e c t i o n ，d a t am i n i n g , k n o w l e d g ed i s c o v e r ya n ds oo n a t t r i b u t er e d u c t i o ni sa ni m p o r t a n tp a r to fr o u g hs e t st h e o r y , t h ep u r p o s eo f a t t r i b u t er e d u c t i o ni st od e l e t et h er e d u n d a n ta t t r i b u t e su n d e rt h ec o n d i t i o no f m a i n t a i n i n gt h ec l a s s i f i c a t i o n ，g e ta c o n c i s ed e c i s i o nt a b l et op r o v i d ec o n v e n i e n c ef o r t h el a t e rc a l c u l a t i o n t h e r ea r em a n ya l g o r i t h m so na t t r i b u t er e d u c t i o n ，b u tt h i s p a p e rm a i n l y i n t r o d u c e st h ea l g o r i t h m sb a s e do nd i s c e r n i b i l i t ym a t r i x f i r s t l y , t h i sp a p e ri n t r o d u c e s s e v e r a lt y p i c a l r e d u c t i o na l g o r i t h m s ，g i v e st h ed e f i n i t i o n so ft h ea l g o r i t h m s ，a n a l y z e s t h es o l v i n gp r o c e s s e so ft h ea l g o r i t h m s ，p o i n t so u tt h ea d v a n t a g e sa n dd i s a d v a n t a g e s o ft h e m ，g i v e sr e l e v a n ts o l u t i o n sf o rt h ef a u l t s ，g i v e se x a m p l e sa tl a s t s e c o n d l y ，an e wm o d e lo fa t t r i b u t e r e d u c t i o ni si n t r o d u c e d ，t h i sm o d e li s e q u i v a l e n tt o t h et r a d i t i o n a lm o d e l s o m er e l a t e dd e f i n i t i o n so ft h i sm o d e la n d a t t r i b u t er e d u c t i o na l g o r i t h mb a s e do nt h i sm o d e la r ep r e s e n t e di n t h i sp a p e r ，a n da n e x a m p l ei sg i v e nt od e m o n s t r a t et h ea t t r i b u t er e d u c t i o np r o c e s so f t h ea l g o r i t h m t h i r d l y , a na l g o r i t h mb a s e do nd i s c e r n i b i l i t ym a t r i xi si n t r o d u c e d ，i tc a l c u l a t e s t h em i n i m u mr e d u c t i o nb yu c p a r t i r i o n ，t h i sp a p e rp o i n t so u t t h e a l g o r i t h m s d i s a d v a n t a g e s ：t h e r ea r er e p e a t e dc o m p u t a t i o na n dt h ea l g o r i t h mm a y b eg e tw r o n g r e s u l t s a f t e rt h ed i s a d v a n t a g e so ft h ea l g o r i t h mi sa n a l y z e d ，a ni m p r o v e da l g o r i t h mi s p r e s e n t e d ，f i r s t l y , t h ea l g o r i t h mc o m p r e s s e s t h ed a t ao fd e c i s i o n t a b l e ，d e l e t et h e r e d u n d a n td a t a , t h i sr e d u c e st h et i m ec o m p l e x i t ya n dt h es p a c ec o m p l e x i t y , t h e na m i n i m u ma t t r i b u t er e d u c t i o nb a s e do nc o r eo fa t t r i b u t e sa r eu s e dt oc o m p u t et h e m i n i m u mr e d u c t i o n f i n a l l y ，t h ei m p r o v e da l g o r i t h mi sa n a l y z e d ，o n l yi ft h e r ea r em a n yr e d u n d a n t d a t a si nt h ed e c i s i o nt a b l e ，t h ei m p r o v e da l g o r i t h mc a nw o r ke f f e c t i v e l y ，t h ea l g o r i t h m n e e d sf u r t h e ri m p r o v e m e n t ，s u c ha sc o m b i n i n gw i t hi n t e l l i g e n tc o m p u t a t i o n k e yw o r d s ：r o u g hs e t s ，d i s c e m i b i l i t ym a t r i x ，a t t r i b u t er e d u c t i o n , m i n i m u m r e d u c t i o n ： i i 目录 第1 章引言。l 1 1粗糙集理论的背景和特点1 1 2粗糙集理论的研究与应用2 1 3粗糙集理论存在的问题3 1 4本文的具体工作和结构安排4 第2 章粗糙集理论基础知识介绍5 2 1 知识库和决策表5 2 2 等价类与上、下近似7 2 3 粗糙集属性约简1 2 2 3 1 绝对约简1 2 2 3 2 相对约简1 4 2 4 小结1 6 第3 章基于差别矩阵的约简算法1 7 3 1s k o w r o n 差别矩阵1 8 3 1 1 算法介绍1 8 3 1 2 算法复杂度分析及不足19 3 2h u 差别矩阵1 9 3 2 1 算法介绍1 9 3 2 2 算法复杂度分析及不足2 0 3 3y e 差别矩阵2 0 3 3 1 算法介绍2 0 3 3 2 算法复杂度分析及不足2 l 3 4 基于差别矩阵的启发式约简算法2 2 3 4 1 差别矩阵的定义2 2 3 4 2 差别矩阵的性质2 6 3 4 3 算法设计3 6 3 4 4 算法复杂度分析3 8 i i i 3 4 5 实验结果3 9 3 5 小结一4 1 第4 章最小属性约简算法4 2 4 1 基于条件属性划分的最小属性约简算法4 3 4 0 ! 1 属性约简的相关定义4 3 4 1 2 子系统的生成与约简的定义4 5 4 1 3 算法分析及实例4 8 4 2 基于决策表分解的约简算法5 0 4 2 1 问题的引入5 0 4 2 2 差别矩阵的定义5 2 4 2 3 算法设计5 2 4 2 4 实例分析5 4 4 3 一种改进的基于属性核的约简算法5 5 4 3 1 问题的引入5 5 4 3 2 基于等价类的决策表压缩方法5 7 4 3 3 基于核的改进算法及其完备性证明：6 0 4 3 4 实验仿真6 2 4 3 5 小结6 2 第5 章结论与展望6 4 0 1 论文总结6 4 5 2 工作展望6 4 致 射6 6 参考文献6 7 攻读硕士学位期间发表的学术论文7 0 攻读硕士学位期间参研的科研项目7 0 i v 武汉理工大学硕士学位论文 第1 章引言 1 1 粗糙集理论的背景和特点 g f r e g e 于1 9 0 4 年提出了含糊边界线问题，该问题可解释为如何计算边界上 含糊元素的数量。对该问题，许多人进行了研究，其中包括不少数学家和计算 机科学家。1 9 6 5 年，l a z a d e h 提出t f u z z y 集t ，他试图用该理论解决含糊概念， 很遗憾的是他没有成功，因为他在模糊集中没有给出精确的数学公式，无法通 过运算确定有多少元素符合要求。此后，人们进一步进行研究，试图解决含糊 边界线问题。1 9 8 2 年，z p a w l a k 提出t r o u g h 多t t 2 1 。在该理论中，他提出了 一上近似和下近似的概念，上、下近似都可以通过确定的数学公式计算出来。z p a w l a k 提出采用上、下近似求解含糊边界线问题的方法，将边界线区域定义为上、 下近似集的的差。由于上、下近似可根据公式具体求出，故可以得到含糊边界 线上含糊元素的具体数目，从而解决了g f r e g e 提出了含糊边界线问题。 粗糙集理论是一种新型的处理模糊性和不确定性问题的数学工具，它通过 将知识和分类相结合，采用等价类来表示分类，这样，我们可以将知识理解为： 知识是使用等价关系的集合对离散空间划分的结果。在处理实际问题时，人们 最感兴趣的是粗糙集理论处理不完全信息或知识的能力，以及通过对比、观察 某些不精确的数据信息从而进行数据分类和提取决策信息的能力。 在与概率统计、模糊集等处理不确定信息的方法比较之后，我们会发现粗 糙集理论具有如下特点： ( 1 ) 除了实际问题所提供的需要处理的数据集合之外，粗糙集理论不需要 任何其它信息。这是粗糙集理论最突出的优点，也是它与证据理论、模糊集理 论最重要的区别。在使用概率统计求解问题时，我们需要计算出概率分布，有 时概率分布是不容易求的，在对复杂问题求解时容易出现误差，这往往会影响 后面的求解结果，甚至会使最终的求解结果远远偏离实际情况。但是在使用粗 糙集理论解决问题的时候，我们并不用担心这些问题，因为我们只需要处理实 际问题所提供的数据集合，不需要另外的信息，所以它对实际问题的处理更加 客观。 ( 2 ) 粗糙集理论具有强大的数据分析能力。在保持分类能力不变的情况下， 武汉理工大学硕士学位论文 它既可以处理完备和不完备的数据信息，又可以处理离散的和连续的数据信息。 对于连续的数据信息，粗糙集相关软件可以直接对这些信息进行离散化，然后 对它们进行消除冗余的操作，进而进行数据约简，从中提取出想要的规则知识。 ( 3 ) 粗糙集与模糊集分别刻画了不完备信息的两个方面【3 1 。粗糙集侧重于 分类，它是以等价关系，即不可分辨关系为基础的。而模糊集则注重于强调集 合的含混性，它主要是基于元素对集合隶属程度的不同。由于粗糙集缺乏足够 的论域知识，所以不能清晰定义粗糙集合，但是可以用一对清晰集合逼近。粗 糙集和模糊集之间即存在差别又存在联系，在实际问题求解中，它们可以相互 补充，有一定的互补性【4 5 ，6 】。 ( 4 ) 粗糙集理论可以获得最小的约简，从而得到有关知识的简单表达和规 则。 自该理论提出以来，越来越多的研究人员对该理论进行了研究，相关的国 际会议也越来越多，从而推动了该理论的发展与完善。该理论具有实用性强的 特点，目前，其已被应用于许多领域，如故障检测、数据挖掘、模式识别、过 程控制等。 1 2 粗糙集理论的研究与应用 早在2 0 世纪7 0 年代，波兰的p a w l a k 和其他一些逻辑学家就在对信息系统 逻辑特性研究的基础上，提出了粗糙集理论的思想。但遗憾的是，当时并未引 起世界各地的科学家的注意，仅有东欧各国对此进行研究。主要是因为当时有 关粗糙集理论的论文大多用波兰文发表的。这种状况一直持续到1 9 8 2 年，p a w l a k 于该年发表了( ( r o u g hs e t s ) ) ，引起了国际计算机界的重视，从而标志着粗糙集理 论的正式诞生。 早期对粗糙集理论的发展起到推动作用的专家有p a w l a k 教授和 r s l o w i n s k i ，他们分别于1 9 9 1 年和1 9 9 2 年出版了各自的专著。在文献 1 9 中， p a w l a k 教授对粗糙集理论进行了系统的介绍。文献 4 9 】是一本由r s l o w i n s k i 主 编的论文集，主要是一些早期有关粗糙集研究应用的论文。随着粗糙集理论得 到国际计算机界的肯定，有关该理论的研究与活动被迅速发展起来，最早的有 关粗糙集的国际会议是于1 9 9 2 年举办的，从此每年召开一次以粗糙集理论为主 题的国际研讨会。1 9 9 3 年和1 9 9 4 年，第二届和第三届有关粗糙集理论的国际研 讨会分别在加拿大和美国召开。此时，该理论虽已得到认可，但因影响力还不 2 武汉理工大学硕士学位论文 大。1 9 9 5 年，p a w l a k 等人在a c mc o m m u n i c a t i o n s ) ) 上发表了“r o u g hs e t s ”， 从而把该理论的国际影响力推上新的高度。此后有关该理论的国际研讨会分别 在日本、美国、加拿大举行。 国内从事该理论的研究相对较晚，但发展较快。目前，我们已连续举办了 1 0 届“中国r o u g h 集与软计算学术会议”。由中国人工智能学会粗糙集与软计算 专业委员会和中国计算机学会人工智能与模式识别专业委员会联合主办的“第九 届中国r o u g h 集和软计算学术研讨会( c r s s c 2 0 0 9 ) 于2 0 0 9 年8 月2 2 日至8 月2 4 日在河北师范大学召开。由中国人工智能学会r o u g h 集与软计算专业委员 会和中国计算机学会人工智能与模式识别专业委员会主办、重庆邮电大学承办 的“第十届中国r o u g h 集与软计算、第四届中国w e b 智能及第四届中国粒计算 联合会议”于2 0 1 0 年1 0 月1 1 日至l o 月1 4 日在重庆召开。 经过多年的研究与发展，粗糙集理论日趋完善，此外，实践证明其在处理 实际问题中具有非常大的应用价值。现已广泛应用于故障检测、知识发现、过 程控制、决策系统等诸多领域。由于粗糙集理论在处理问题时，除了问题所提 供的数据外，其并不需要其它的额外信息，在保持分类能力不变的情况下，该 理论仅通过等价类划分，数据约简以及其它操作来获得所需信息，因此该理论 相对于其它处理不确定信息的方法来说，获得的规则信息是客观的。 1 3 粗糙集理论存在的问题 每一种方法和理论都有其优缺点，都有其提出的背景，有的只是针对某一 问题或者某些问题提出的，所以，没有万能的方法和理论。粗糙集理论存在的 问题可分为以下几方面【7 】： ( 1 ) 目前的连续属性离散化方法均有其各自的应用背景和规则限制，还没 有一种可满足各种应用限制的离散化方法。在对连续属性进行约简、提取规则 之前，我们需要对各属性进行离散化。因粗糙集理论操作的主要对象就是离散 的数据，所以如果离散方法选取不当的话，后面约简的效果和提取的规则有可 能不是最优的，甚至可能是错误的。所以，寻求高效的离散化方法一直是制约 着粗糙集理论发展的问题。 ( 2 ) 现有的粗糙集理论处理的数据大多是静态的。而在处理实际问题的时 候，事先提供的数据肯定不能满足实际需求，我们需要根据问题的需求添加新 的数据，进而进行反复的约简，从而得出规则。但是，现有的方法大多是针对 3 武汉理工大学硕士学位论文 静态数据的信息系统，所以在处理动态的数据信息时，现有的方法就不能够对 数据进行有效的约简。 ( 3 ) 从模型中得到的结论仅适用于这些模型中的对象。现在并没有哪一种 模型是通用的，不同的模型均有自己的规则。所以从模型中得到的结论很难进 行推广。 ( 4 ) 粗糙集理论在处理不确定性问题时虽然存在其优势，但也只是相对而 言，在处理实际问题时，为了更好的解决问题，往往会需要结合其它处理不确 定性问题的工具，通过彼此之间的互补性，取长补短。 ( 5 ) 约简过程中的去除冗余的操作会在一定程度上降低容错性和数据推广 能力。 ( 6 ) 粗糙集理论只考虑具有明确的“包含”与“不包含”关系的分类，不会考 虑哪些相互之间存在交集的分类。 1 4 本文的具体工作和结构安排 本文由五部分组成，具体内容如下： 第l 章概括地介绍粗糙集理论的研究背景、实际应用、存在的问题，在第l 章最后给出了全文的结构安排。 第2 章简要地介绍粗糙集理论的基本概念，包括知识库、决策表、上下近 似、约简等概念，为后面的内容提供理论基础。 第3 章分析一些传统的基于差别矩阵的约简算法并介绍一种改进的差别矩 阵。主要对传统矩阵概念、性质加以介绍，分析其不足；给出改进差比矩阵的 定义、性质，对传统差别矩阵的算法与改进差别矩阵的算法进行对比，并给出 实验数据。 第4 章重点介绍最小属性约简算法。首先具体介绍一种基于叫 c l 划分的约 简算法，分析其不足；接着以前述算法的不足为切入点，介绍了一种基于决策 表分解的约简算法，对算法进行分析，并给出实例；最后对基于决策表分解的 约简算法进行分析，指出其不足，给出实例加以证明，并以此算法为基础，提 出一种基于属性核的约简算法，对算法的有效性加以证明，并给出实验数据。 第5 章总结论文的整体工作，对后续工作加以介绍。 4 武汉理工大学硕士学位论文 第2 章粗糙集理论基础知识介绍 粗糙集理论是一种数学工具，我们主要用它来解决一些不完备和不确定性 问题。在仅提供问题所需处理的数据的情况下，我们可利用粗糙集理论的相关 操作对待处理数据进行等价类划分、上、下近似求解、正区域求解等操作，进 而对数据进行约简并提取相应的规则和获得隐含的知识，揭示潜在的规律。因 在处理数据的时候没有添加额外的信息，所以粗糙集理论对问题的处理是比较 客观的。在本章，将对粗糙集理论处理实际问题时所涉及的一些基本定义和定 理做详细的介绍，以便于对粗糙集理论进行系统的了解。 2 1 知识库和决策表 粗糙集理论对知识做了如下定义：人类以及其他生物所与生俱来的分类能 力。在粗糙集理论中，人们将研究对象所组成的非空有限集合称为论域。若 x 量u ，则称x 为u 的一个概念。u 的一切概念所组成的集合称为u 的抽象知 识，也可以简称为知识。我们将从u 上得到的相应的一族划分称为u 的一个知 识库。 定义2 1 t 8 】：知识库可以表示为k = ( u ，r 1 ，其中u 是非空的论域，尺是与 论域u 相对应的一个等价关系。 知识的正确合理的表达在处理数据的过程中是十分重要的。在粗糙集理论 中，我们对知识表达系统做了如下定义： 定义2 2 【9 1 ：一个知识表达系统s 是一个四元组，即s = ( u ，r ，v ，f ) ，其中 阢研究对象的全体所组成的有限集合，该集合非空( 即u a ) ，我们称它 为论域( u n i v e r s e ) ； r ：论域中的所有元素所对应的属性，这些属性值组成一个集合，该集合非 空( 即r a ) ； 玑与对象相对应的属性值所组成的集合，即y = u 攻，此处我们称圪是x j 哐月 的值域； 斥是一个函数，该函数可表示为厂：u x r 专矿，由此函数可知，每个研究 5 武汉理工大学硕士学位论文 对象所对应的所有属性均与一个值相对应，即v r r ，u u ，f ( r ，”) k ： 定义2 3 【9 】：在一个知识表达系统中，若有r = c u d ，且有c n d = a ，其 中c 是条件属性集合，d 是决策属性集合。我们称这种具有条件属性和决策属 性的知识表达系统为决策表。 例2 1 ：对于决策表s = ( u ，r ，v ，f ) ，c = 口，b ，c ，d ，d = d ，论域中个对象 所对应的属性值如下表所示： 表2 1 决策表 在表中我们可以看到，对于论域中的某些元素，虽然它们的条件属性值完 全相同，但它们的决策属性值却不同( 如奶与踢，有 厂( 确，口) = f ( u 2 ，口) ，厂( 撕，b ) = f ( u 2 ，6 ) ，( 明，c ) = 厂( 耽，c ) 但厂( 加，d ) 厂( 眈，d ) ) ，有 些对象彼此的条件属性值和决策属性值完全相同( 如坼与阮，有 厂( 聊，a ) = 厂( 地，口) ，厂( 聊，b ) = f ( u s ，6 ) ，f ( u 7 ，c ) = 厂( z 坛，c ) ，厂( 聊，d ) = ( 确，d ) ) 。在 粗糙集里，把在条件属性值完全相同时，决策属性值也相同的决策表叫做相容 决策表，否则叫做不相容决策表。由相容决策表和不相容决策表的定义，我们 可知表2 1 是不相容的，同时我们可以将表2 1 进行划分，将其分为两个表，表 2 2 是相容的，表2 3 是不相容的。 6 武汉理工大学硕士学位论文 表2 2 相容决策表 2 2 等价类与上、下近似 定义2 4 9 1 ：设s = ( u ，r ，矿，f ) ，对于每个属性集p c _ r ，定义集合尸的不可 区分关系i n d ( p ) = ( 石，j ，) u 2iv r p , f ( x ，) = i ( y ，) ，如果( 五y ) i n d ( p ) ， 则称x 与y 是p 不可区分的，不可区分关系也可称为等价关系。u i n d ( p ) ( 也 可以简写为u p ) 是由i n d ( p ) 得出的论域u 上的一个划分，u p 中的任意元素 【z 】p = yi 比p , f ( x ，口) = 厂( y ，口) ) 称为等价类，其中【x 】p 为包含x 的等价类。 粗糙集是基于等价类的划分来获取知识的，下面介绍一个知识获取的例子。 例2 2 ：在知识表达系统s = ( u ，r ，v ，厂) 中，论域包含8 个元素，属性集中 包含3 个属性，各属性及它们所对应的属性值如下： c o l o r ：r e d 、y e l l o w 、b l u e ；s h a p e ：s q u a r e ，t r i a n g l e 、c i r c l e ；s i z e ：s m a l l 、b i g 。 7 武汉理工大学硕士学位论文 对于咋( 1 f 8 ) 所对应的具体属性值，在表2 - 4 中给出。 表2 4 关于图形的决策表 由上表我们可以得到三个划分，u c o l o r ) 、w s h a p e ) 、u s i z e 。对于 u c o l o r ，由于u i ，u 3 ，u 7 ，在属性c o l o r 上的值是相等的，均为r e d ，因此 u l ，u 3 ， u 7 ) 在属性c o l o r 上就构成了一个等价类， u 2 ，以) 、 u 5 ，u 6 , u s ) 也在属性c o l o r 上构成一个等价类，由此可得u c o l o r = u l ，u 3 ，u 7 ) 、 埸，以) 、 阮，玩，) ) 。 同理可得有属性s h a p e 、s i z e 所构成的划分分别为：u s h a p e = u i ，u 5 ) 、 奶，阮) 、 u 3 ，砺，u 7 ，) ) ，u s i z e = u 2 ，u 7 ，u s ) 、 u l ，u 3 ，以，以，玩) ) 。 由上面划分中的等价类我们可以得到如下信息： u l ，u 3 ，u 7 n u 3 ，阢，u 7 ，现) = u 3 ，u t ， 叻，以) n u 2 ，) = u 2 ) ， 协，玩，玩) r 、 u 3 ，以，u 7 ，) = u s ) 。 上述等价类属于u c o l o r , s h a p e ) ，其中u c o l o r , s h a p e = u 1 ) 、 协) 、 u s ，u 7 、 u ) 、 u s 、 0 6 、 u 8 ) ) 。 u s ，u 7 表示红色的三角形， 踢) 表示 绿色的正方形， u s ) 表示黄色的三角形。 按照上面的方法，我们可知下列结果属于u c o l o r , s h a p e ，s i z e ) ，运算如下： u ，u s ，u 7 n u s ，u 4 ，u 7 ，u 8 ) n ，u 7 u ) = u 7 ， 踢，u ，n u 2 ，u 6 n ，u 7 ，u 占) = u 2 ) ， u s ，u 6 ，u s n u s ，u 4 ，u 7 , u s n 踢，u 7 u 8 ) = u 8 ， u e o l o r , s h a p e ，c i r c l e = u j ) 、 协) 、 u s 、 u 4 、 u ) 、 u 6 、 u 7 、 u 8 ) 。 武汉理工大学硕士学位论文 踢) 表示绿颜色的大的平方形、 v z 表示红颜色的大的三角形、 u s 表示 黄颜色的大的三角形 对于各等价类的并运算则可以获得如下知识： ( u j ，u j ，u t u 巩，u 4 ) = u t ，u 2 ，u 3 ，u 4 ，u z ， 踢，u ) u u j ，u 6 ，u 艿) ) = 奶，u 4 ，u j ，u 6 ，u s ， u j ，u 3 ，u 7 ) ) u u s ，u 6 ，u 8 ) = u i ，u j ，u 5 ，u 6 ，u z , u s 。 上述等价类可有u c o l o r 获得， u j ，踢，u ，u 4 ，u t 表示红颜色或者蓝颜色 的， 沈，u ，u ，u 6 ，u s 表示蓝颜色或者黄颜色的、 u ，u ，协，u 幻u 7 u s 表示红 颜色或者黄颜色的。但是有些知识我们无法有给定的知识系统获得，如： 巩，u 4 ) 厂、 u t ，u j ) = a ， u i ，u 3 ，u t n 踢，u 6 ) = a 。 计算表明，在给定的知识系统中，得不到蓝颜色的圆形和红颜色的正方形。 由实例我们可以了解到，粗糙集理论中的不可分辨关系在获取知识的过程 的有着举足轻重的作用，通过不可分辨关系的计算和等价类的比较，我们可以 获取相关知识，同时不可分辨关系也表明了在知识中存在颗粒状结构【2 , 1 1 , 1 2 】。 定义2 5 t 9 1 ：u c u ，p 是u 上的等价关系，如果能将u 表示成p 的某些元 素的并，则称u 是p 可定义集，否则称u 是p 不可定义集。 如果u 是p 可定义集，则其必为p 的某些元素的并，故u 必是论域的子集， 可以在知识系统中对它进行详细的定义；如果u 是p 不可定义集，则说明不能 将其表示成等价关系的某些元素的并的形式，该知识在这个知识系统中不存在， 即不能通过该知识系统中的知识对u 进行定义。对于可定义集，我们也将其称 为精确集；不可定义集，我们将其称为非精确集合或者粗糙集。 例2 3 - ：以表2 4 中的数据为基础，对可定义集和粗糙集的求解进行详细介 绍，具体求解过程如下： u c o l o r = u l ，u 3 ，u 7 、 踢，以) 、 ，) ) ， u s h a p e = u i ，u 5 ) 、 踢，玩) 、 u 3 ，以，u 7 ，) ) ， u s i z e = 踢，u 7 ，翰) 、 u l ，u 3 ，以，协，玩) ) 。 判定们= u l ，u 3 ，协，u 7 ) 、【， u ，踢，u 3 ，u t 是可定义集还是不可定义集。 因u c o l o r 与u s h a p e 联合构成的等价关系是它们的并，u c o l o r ) u u s h a p e = u l u 3 ，u 7 、 仍，砜) 、 协，玩，) ) u u l ，砺 、 协，玩) 、 u 3 ， 砺，u 7 ，) ) ，u 1 可表示成 u l ，u 3 ，u 7 u 巩) ，可由u c o l o r uu s h a p e 中 的元素 u l ，u 3 ，u t 、 协) 取并得到，故u 1 _ u l ，u 3 ，u 5 ，u 7 是u c o l o r u 9 武汉理工大学硕士学位论文 u s h a p c 日- 定义的；而对于u 2 = u ，协，u 3 ，u t ，我们无法将其表示成某些集合 并的形式，所以它是不可定义的。 定义2 6 【9 】：设s = ( u ，r ，v ，f ) ，对于每个子集xc _ u 和一个等价关系p cr ， 则有如下定义： x 的p 下近似集：出= y u 尸i 】r 互x ， x 的p 上近似集：蹦= 】，u p 】，n x f 2 j ) ， x 的p 边界域：6 脚( x ) ：斟一出， x 的p 正域：p o s e ( x ) = ( ) ， x 的p 负域：，z e g p ( x ) ：u 一斟。 对于x 的p 下近似集和x 的p 上近似集也可做如下定义： 猷= k u l z 】pcx ) 、两= x u 州pn x g 。 廖和e o s p ( x ) 都是由那些通过判定得出肯定属于x 的论域u 中的元素组成； 以是由那些通过判定得出可能属于x 的论域u 中的元素组成；b n p ( x ) 是由那 些既不能通过判定得出肯定属于x 的论域u 中的元素又不能通过判定得出肯定 属于u x 的论域u 中的元素组成；n e g p ( x ) 是由判定得到的肯定不属于x 的论 域u 中的元素组成。前面的判定都是由知识p 得到的。图2 - 1 给出了集合x 、p x 、 厨、b n e ( x ) 、n e g 尸( x ) 之间的关系，关系如下： 一a d x ) b n a ( x ) + 一a ( ) 0 o r g h 融x 口n 1 e g ( x ) 图2 1 各定义之间关系示意图 1 0 武汉理工大学硕士学位论文 例2 4 ：设有一个知识表达系统s - - ( v ，r ，y ，f ) ，其中u = u l ，1 1 2 ，u 3 ，u 4 ，u 5 ，u s ， u 7 ，u s ) ，r = r l , r 2 ，r 3 且等价关系u r l 、u r 2 、u r 3 的具体值如下： u r l = u l ，u 4 ，u s ， u 2 ，u s ) ， u 3 ) ， 1 1 6 ，u 7 ) ) ， u r 2 = u l ，u 3 ，u s ) ， u s ) ， u 2 ，1 1 4 ，1 1 7 ，u 8 ) ) ， u r 3 = u l ，u s ) ， 1 1 6 ) ， u 2 ，u 7 ，u s ， u 3 ，1 1 4 ) ) ， u i n d ( r ) = u l ，u s ) ， u 2 ，u s ) ， u 3 ) ， u d ， u s ， u 7 ) ) 。 对于x _ u l ，1 1 4 ，u 7 ) ，可得到蟹= 1 1 4 ，u 7 ) ； r x = u l ，u d u u 4 ) u u 7 ) = u l ，1 1 4 ，u 5 ，u t ) ； b n p ( x ) = 厨一r x = u l ，u 5 ) ； p o s r ( x ) = u 4 ，u t n e g r ( x ) = u 一肘= 1 1 2 ，u 3 ，u s ，u 8 ) 。 定义2 7 3 7 1 ：设s = ( u ，c u d ，v ，f ) ，pc _ c ，对划分 x l ，x 2 ，x n ) 的p 下近 似精度可表示为r p = l 甄i l u i o 定义2 8 3 刀：设s = ( u ，r ，矿，f ) ，若p c ，2 5 , = ，且没有r c p ，满足= 斥， 则称p 是c 的一个相对属性约简。 定理 2 1 1 3 1： 在决策表 s = ( u ，c u d ，矿，厂) 中， p o s 1 d l = ux 、7 x e v c r v x ，y e x = f ( x ，o ) - f ( y ，d ) 该定义说明p o s c ( d ) 是由不可分辨关系中决策属性值完全相同的等价类组 成，也就是说如果圳c 中某一等价类中的元素在决策属性上取了一个以上的不 同值，那么这个等价类就不在正区域中。 按照定理2 1 计算正区域时比较方便，在计算出不可分辨关系后，直接判断 不可分辨关系中的等价类，看等价类中的决策属性值是否唯一，也即等价类中 所有元素的决策属性是否一致，一致的话，该等价类就在正区域中，否则，就 不在。这样就省略了判断等价类是否包含在原集合中的操作。 武汉理工大学硕士学位论文 定义2 9 1 3 1 ：设决策表s 7 = ( u ，c u d ，矿，f ) 由决策表s = ( u ，c u d ，矿，厂) 简化 后得到，对s c 定义酬( d ) 2 石毫u ，卧工乩阱d 卜。x 。 2 3 粗糙集属性约简 粗糙集理论主要用于对决策表进行属性约简或者提取决策表中的规则，从 而获得某些知识。对于给定的决策表s = ( u ，c w d ，y ，f ) ，并非所有的属性都是 必须的，在不影响决策表分类能力的前提下，我们可以删除某些条件属性或者 决策属性，进而得到一个相对简洁的决策表。通过对决策表的约简我们可以了 解到属性的重要性，删除后会改变决策表分类能力的属性肯定是最重要的，是 必不可少的；删除后并不影响决策表分类能力的属性，肯定是不必要的。在以 后的计算中，我们可以用约简后的决策表代替原决策表，虽然分类能力是相同