（运筹学与控制论专业论文）粗糙集方法及应用研究.pdf

摘要 摘要 粗糙集( r o u 曲s e t ) 理论是2 0 世纪发展起来的一种新的处理含糊性和不确定 性问题的数学工具，求取高效、快捷的属性约简算法是当前该理论研究的主要 课题之一。约简算法是信息系统分析、数据挖掘等领域的一种主要方法，有广 泛的应用前景，对它的研究具有重要的理论意义和实用价值。 本文简明地介绍了粗糙集理论的研究现状，主要特点和应用领域；全面、 系统地介绍了粗糙集理论的基本概念、基本知识和基本方法；重点讨论了连续 属性的离散化、对象的聚类处理、粗糙集的约简和规则发现算法等租糙集理论 的一些主要方法和关键技术。在深入分析、研究的基础上，提出了一类新的基 于m a h a l a b i s 距离的最近邻中心聚类算法，该算法不仅解决了各属性间的彼此 依赖关系和量纲不同对聚类和离散化带来的干扰，而且聚类过程不需要预先设 定阈值和聚类数目而自动完成，减少了人的主观因素影响，具有较高的智能性； 同时，在对现行粗糙集约简算法进行系统分析和比较的基础上，提出了一种基 于属性频率函数的h o ra f a b 算法该算法对每个属性建立自己的区分矩阵， 用属性频率函数作为约简条件，直接对区分能力矩阵进行处理，并充分利用属 性的有关信息，有效地避免了具有重复信息属性的再选择问题，不仅使h o r a f a 算法能够找到最优约简，同时直接使用矩阵运算，较大地提高了运行效率。最 后，在粗糙集理论应用于证券分析系统、建立规则库等方面进行了一些探索， 为粗糙集理论用于实际积累了一些经验。 关键词：粗糙集聚类约简区分矩阵m a h a l a b i s 距离 a b s t r a c t a b s t 仡l c t r c m 曲s e tn r yi sat o o lt od e a l 谢t ht l l ei m p c i i n c o 璐i s t e 鸲i 嗍l e t e i n f 0 肋a t i s y s 把m t o d a y ，l e 瞄龇h e s r o u g hs e tt h 。o r yf o c u s e s t h e 删b u t e sr e d u c ta l g 面t l l | 璐，锄di t sa p p l i c a t i o n i n ：f 0 珊a t i o na n a l y s i ss ) r s t c m 锄d d a 协m m i n gb e c 伽m o r c 锄dm o r cp o p u l 孔 1 1 1 i sp 印e ri n n d d u c c sr o u g hs e tt h e o f yt l l 。o m t i c a l l y 觚d 蹦l p l l a s i s s o m e s i 刨f i c a mm e m o d s 舭dk c y 佃幽o i o 西髂如c h 鹤d i s p c r s i o no fr c a i 训u 鹤a l 仃i b i l t e s ， d 珊：i c r i n ga l g o r i m 塔a n df e d u c ta l 酬t l l m so f r o u g hs c l 1 1 l ep a p e rd c v e l 叩san e wc e n t c rc l u s t e l i i l ga 1 9 0 r l l l n lb 觚e do nm a l l a l 锄o b i s d i s t 锄c c t 1 把a i g 耐t l i m t l ye l i l n i n a t e st l l e i m e r f b r e n c c sw h e nc l u s t e r i i 培a r l d d i s p e 塔i n gb yt l l ec o r r e l a t i o 璐o f 髓c h 删b u t c s 锄dd i 彘m l c c so f m e 鹊u r e l n e n t s ，b u t a l p r o c 髂s e st h ec l u s t a 血喀a m 咖a t i c a l l y1 ) i ，i t h o u t t t i l 培t l l et l l r e s h o l d 锄df h c n 啪b e ro fc l l l s t e 血gi l la d v 锄c e 1 ka 1 鲥t 蚰i si l i g h l yi n t c l l i g e mf o rd i i n i i l i s h i 】呜t l 坨 i n n u e n c eb yh u m 卸s 跚b j e c t i v e j u d g e m 椭d l i l e ，t l 嵋p a p c rd e v c l o p sah o i 凇a - b a l g 耐t l 皿岫i 唱锄a d j l j s t 删b u i 髂舶q u e n c y 如c 如m1 ka l g 硎t l 瑚c o 咖c bd i s r n i b i l 姆 m a t r i xf b r c ha t 啪b m e n s i d e r sm ea 螂u s t 删b 懒白e q 唧yf i l c n o n 舔n d u c t 训砸咀 锄dc 伽p i l t e sn 圯d i s c e 】c n i b i n t y 曲i l 时m 捌xd i r e c t l y f o re l i i i 血龇i n gt h e 呻b l 鼬o f c s i d e r i i l gc o m l a t i v ea 佃b u i e sr e l ) c t 硒v e l y ，h 0 蝴- ba l g o d t l 皿啪6 n dt h eb e s t r c d u c to ft l 坨k n o w l e d g cs y s t e m a tt h es a n l et i n 坤，h o r 趾a ba l g o 舳mf a i 螂岫 e 伍c i c yo f i e d u c tb y 啦锄斓，i l t e sm s o 咖i b i l i t ym a 埘】【 a t l 吼t 1 1 e p a p 盯积p l o r 鹳m ea p p n c a l i 蚀so fr l m 曲s e t s t o c k 删y s i ss y s t e m 卸d 邝1 e $ e b 柚dg e | ss o m e 麟p e r i e n o f 砥a p p l i c 撕0 n 1 盯w o r 山：风曲鳅，c l t i 眠l e d i 咄d i s r n i b i l 姆m 删x ，m a l l a l 锄o b i s i i 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：士名贯 6 年r 月沙日 经指导教师同意，本学位论文属于保密，在年解密后适用本 授权书。 指导教师签学位论文作者签 名： 名： 解密时年 月日 间： 各密级的最长保密年限及书写格式规定如下； ”t ”一1 。1p 1 。1 “、7 1 o ：一内部_ 5 年+ ( 最长5 年，可少于5 年) ，i ；+ r 。：5 ，；秘密l o 年( 最长1 0 年，可少于1 0 年，：i ，；。i 一 一 “ ；。叶机奄专2o ，年( 最长2 0 年，缈于* 2 0 年) ；掌i ；， 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名：扣碰导 跏“年厂月秒日 第一章绪论 第一章绪论 第一节前言 近十几年，随着科学技术飞速的发展，经济和社会都取得了极大的进步， 与此同时，在各个领域产生了大量的数据，如企业的现金流记录，公司的客户 资料和销售记录，金融证券市场的交易记录等等显然这些数据包含了丰富的 信息，如何处理这些数据得到有益的信息，人们进行了有益的探索计算机技 术的迅速发展使得处理数据成为可能，这就推动了数据库技术的极大发展，但 是面对不断增加如潮水般的数据，人们不再满足于数据库的查询功能，提出了 更深层次问题：能不能从数据中提取信息或者知识为决策服务。就数据库技术 而言已经显得无能为力了，同样，传统的统计技术也面临了极大的挑战。这就 急需有新的方法来处理这些海量般的数据。在这种背景下，一些新的智能数据 处理技术，如；数据库知识发现a 陋国) ，数据挖掘p a t am i i l i l l g ) 等应运而生，并 在理论和应用上都有一定的成果因此，知识发现和数据挖掘是应用需求推动 下跨学科发展的产物。 在知识发现和数据挖掘诸多方法中，粗糙集u 曲s e t ) 理论与方法对于处 理复杂系统不失为一种较为有效的方法，它与概率论方法、模糊集理论方法、 证据理论方法等处理不确定性问题理论的最显著的区别是它不需要提供问题所 需处理的数据集合之外的任何附加的信息或先验知识，就能有效地分析和处理 不精确、不完整和不一致的数据，并从中发现隐含的知识，揭示潜在的规律 粗糙集方法已被广泛地应用于数据挖掘、机器学习、模式识别、决策分析等许 多领域，并在经济、金融、医学、化学、材料学、管理科学等领域得到了成功 的应用。现已经成为信息科学最为活跃的研究领域之一 第二节粗糙集理论简介 1 2 1 租糙集理论的产生 在自然科学、社会科学和工程技术的很多领域中，都不同程度地涉及到对 一1 一 第一章绪论 不确定因素和对不完备( i m p e 疵哟信息的处理从实际系统中采集到的数据常常 包含着噪声，不够精确甚至不完整采用纯数学上的假设来消除或回避这种不 确定性，效果往往不理想，反之，如果正视它，对这些信息进行合适的处理， 常常有助于相关实际系统问题的解决多年来，研究人员一直在努力寻找不完 整性和不确定性的有效途径模糊集和基于概率的证据理论都是处理不确定信 息的方法，已应用于实际领域。但这些方法有时需要一些数据的附加信息或先 验知识，如模糊隶属函数，基本概率分配函数( b 勰i cp f o b a b i l 时a s s i 鲫me 1 】_ i ，b p a ) 和有关统计概率分布等，而这些信息有时并不容易得到。 在这种背景下，波兰学者z p a w l a l 【于1 9 8 2 年提出了粗糙集理论【1 1 它也是 一种刻画不完整和不确定性的数学工具，但它不需要数据集以外的任何先验信 息就能有效的分析不精确( i m p r e c i s e ) 、不一致( i n c 帆s i s l c n t ) 、不完整( i n m p l e i e ) 等各种不完备信息，还可以对数据进行分析和推理，从中发现隐含的知识，揭 示潜在的规律。1 9 9 1 年，p a w l a l 【发表了专著r 伽曲s 眈1 1 l c o r e t i c a la s p c c t so f r c 嘲晌ga b o u td a 协【2 】奠定了粗糙集理论的基础。从而掀起了粗糙集的研究高 潮。1 9 9 2 年，在波兰召开了第一届国际粗糙集研讨会，在以后的各届的研讨会 上，都有力地推动了粗糙集理论的发展。近几年来，粗糙集合理论已经广泛地 应用于机器学习、知识发现、决策支持与分析、过程控制、专家系统、智能控 制、模式识别等领域【3 1 。 1 2 2 租糙集理论的特点 粗糙集理论是种新的处理模糊和不确定性知识的数学工具其主要思想 就是在保持分类能力不变的前提下，通过知识约简，导出问题的决策或分类规 则。 粗糙集理论与其他处理不确定性问题的最显著的区别是它无需提供问题所 需要处理的数据集合之外的任何先验信息，如统计中要求的先验概率和模糊集 中要求的隶属度。同时这也是粗糙集与其他处理不确定性问题的方法相比最大 的优点。 具体地说，在证据理论中的对属性、数据或知识等局部的信息及计算全局 信息的函数，及在模糊集理论中对隶属度与隶属度函数，均需要凭借系统设计 者的经验事先给定，即这些不确定性的描述带有强烈的主观色彩，受到系统设 一2 一 第一章绪论 计者的知识结构、经验组成以及心理因素等多方面的影响。而粗糙集理论则无 需这些先验的信息，它的基本思想是：利用定义在论域u 上的等价关系对c ，的 划分作为知识，而对知识不确定程度的测量，则是在对被分析数据整体的处理 之后自然获得。这样，租糙集理论不需要事先对知识或数据的局部给予主观评 价，换言之，r s 理论对不确定性的描述相对客观。 但是，粗糙集理论与模糊集理论又有着天然的联系。粗糙集理论使用确定 的数学公式对含糊度进行计算是以不可分辨关系为基础，侧重分类；模糊集基 于元素对集合隶属程度的不同，强调集合本身的含混性。从粗糙集的观点看， 粗糙集合不能清晰定义的原因是缺乏足够的论域知识，但可以用一对清晰集合 逼近因此在粗糙集的研究过程中，学者们就很自然地将粗糙集和模糊集联合 起来。在1 9 9 5 年召开的第四届模糊理论与技术国际研讨会，主要针对粗糙集与 模糊集之间的关系进行了讨论，进一步促进了租糙集的发展。 1 2 - 3 粗糙集理论的发展现状 粗糙集理论作为一种处理含糊和不精确性问题的新型数学工具，它自问世 以来，无论是在理论或应用上都是一种新的最重要的并且是迅速发展的一门既 有理论又有应用的研究领域。在机器学习、知识获取、决策分析、数据库的知 识发现、专家系统、归纳推理、矛盾归结、模式识别、决策支持系统、模糊控 制及其他各个方面的应用，粗糙集理论都提供了一种很有效的新的数学方法。 同时，粗糙集理论处理的主要问题包括数据库中的数据约简、数据相关性的发 现、数据意义的评估、由数据产生决策控制算法、数据的近似分类、数据中的 相似性或差异性的发现、数据中范式的分析以及因果关系的发现特别地，粗 糙集方法在医学、药学、银行、商业、金融、市场研究、工程设计、气象学、 振动分析、开关函数，冲突分析、图像处理、声音识别、并发系统分析、决策 分析、字符识别及其他领域都有重要的应用。 目前，国内对粗糙集理论的研究和应用还处于探索阶段，但是我国在这个 领域的发展速度很快，目前中科院、清华大学等研究所和高校己经加入到这个 领域中，并取得了一定的成果相比之下，国外己建立了不少的数据库领域知 识发现d d ) 系统，它们一般都由数据预处理、基于粗糙集或其扩展理论的数据 约简、决策算法等部分组成其大概思想是先进行必要的数据预处理，为数据 一3 一 第一章绪论 约简做准备，并在此基础上根据值约简等减少属性和个体数目，最终提取规则 并将之应用于新对象的分类比较有代表性的有美国m s 舔大学开发的基于粗 糙集的实例学习系统l e r s 函跚i l l g 缸吼e x 锄p l c s b a s c d o n r s ) 系统1 4 】，这个系 统的知识获取项对于用不完全信息工作的专家系统建立知识库是一个十分恰当 的规则归纳法的应用实例。在n a s a sj o b n s 空间中心多年的应用，充分显示 了它在开发专家系统进行全球气候变化的研究中起的作用，它是作为一种开发 专家系统的工具被引用的。r e 西舱大学利用粗糙集理论开发的知识发现系统 圈d d - r 【5 l ，该系统目前被广泛的应用于医疗诊断、电信业等领域 在研究过程中，粗糙集理论除了朝着逻辑及其近似推理方向发展以外，近 些年来出现了大量的r 伽曲数及r o u g h 函数的研究【6 l ，发表了一系列关于 r d u g h 函数方面的论文，如r o u 曲函数的各种近似运算、r o u 曲函数的基本性 质。关于它的r 傩曲连接、r o u 曲极限、r o u g h 可导、r o u 曲积分和r o u g h 稳 定性、r d u 曲函数控制及建立由r o u g h 实函数控制的离散动态系统都是典型的 问题，这些问题都要求在r ( m g h 函数理论的模型下给予公式化。这些问题的研 究将有助于定性推理方法的研究。这种研究实质上是使连续数学离散化，从而 使连续数学也能被现代计算机所接受。 目前，对r s 理论研究集中在数学性质、r s 拓广、与其它方面不确定方法 的关系和互补及有效算法等方面【6 1 。 第三节本文的主要内容和结构安捧 1 3 。1 主要内容及创新点 本文在粗糙集理论和应用方面做了一些探讨，主要研究了连续属性的离散 化、对象的聚类处理、租糙集的约简和规则发现算法等粗糙集理论的一些主要 方法和关键技术，同时，在将粗糙集理论用于证券分析系统、建立规则库等方 面也进行了一些探索 主要创新点为： 一v ， 在粗糙集数据预处理技术中，对连续属性离散化和聚类进行了深入的研究， 针对现行算法存在距离计算忽略属性影响、存在人为因素干扰等缺点，提出了 一类新的基于m a l l a l 肌o b i s 距离的最近邻中心聚类算法。该算法不仅在计算距离 一4 一 第一章绪论 时考虑了对象不同属性之间的关系，而且聚类数日无需由经验或专家事先规定， 在计算对象之间距离的过程中自动完成聚类与传统的聚类算法相比，不仅距 离的计算更为合理，而且减少了人的主观影响，从而提高了分类质量 在对现行粗糙集约简算法进行系统分析和比较的基础上，提出了一种基于 属性频率函数的h o r a f a - b 算法该算法充分利用属性的有关信息，使用属性 频率函数作为约简的条件，建立了新的基于属性的区分矩阵，使h o r a e a 算法 能够找到最优约简，而且提高了运行效率。 在将粗糙集理论应用于证券分析系统、建立规则库等方面进行了一些初步 探索，取得了一些有益的结果，为粗糙集理论用于实际积累了一些检验。 1 3 。2 文章主要结构 第一章绪论 本章介绍了粗糙集理论产生发展的脉络和粗糙集的研究现状，并且简明地 论述了粗糙集理论的一些主要特点。 第二章粗糙集理论基础知识简介 本章对粗糙集理论的基本知识进行了阐述其中包括知识、不可分辨关系、 粗糙集的基本概念、以及知识库，决策表和属性约简。 第三章数据预处理 本章的重点集中在两个方面，一个是连续属性的离散化，另外一个是对论 域中对象的聚类处理。在分析了现有的各类方法之后，提出了一类新的基于 m a l l a l 粕o b i s 距离的最近邻中心聚类算法 第四章粗糙集约简算法的研究 本章以粗糙集属性约简为重点，介绍如何使用粗糙集理论对决策表和知识 系统进行属性约简和规则发现。首先介绍、分析了现行的一些算法：如h o r 觚a 算法、m m 越算法和归纳属性算法等，在对这些算法深入研究的基础上，提 出了一类基于h o r a f a 算法的改进算法h o r a f a b 算法 第五章粗糙集理论的应用 本章主要介绍了本人在硕士研究生期间运用粗糙集理论完成的一些实际应 用项目主要包括：基于粗糙集理论的证券分析系统，应用粗糙集建立规则库， 建立投资者仿真模型的复杂系统证券市场仿真平台 一5 一 第一章绪论 第六章结论与展望 本章对本文的整体工作做出了一个结论，同时指出了本文存在的一些不足， 并提出了一些今后可以继续的研究方向 一6 一 t l 毒 e 第= 章相糙集理论的基本知识简介 第二章粗糙集理论的基本知识简介 第一节知识与知识库 2 1 1 粗糙集理论的一些基础知识简介 在信患系统中，人们首先碰到的就是对知识的理解和表达，一般认为，知 识是人类实践经验的总结和提炼，具有抽象和普遍的特性，是属于认识论范畴 的概念任何知识都是对事物运动状态及变化规律的概括性描述。这个定义不 能算是一个完全的、精确的表达，因为知识具有多种意义，特别是在不同的领 域中进行讨论更是如此。 在粗糙集理论中，。知识”被认为是一种分类能力。人们的行为是基于分辨 现实的或抽象对象的能力，如医生给病人诊断，必须辨别出患者得的是哪一种 病：人在生活中必须判断哪些事情是合法的，哪些又是非法的。这些根据事物 的特征差别将其分门别类的能力均可以看作是某种“知识”。 下面我们给出粗糙集理论中一些概念的严格数学定义。 设u 薯中是我们感兴趣的对象组成的有限集合，称为论域闭。 任何子集z 【，称为，中的一个概念或范畴。为规范化起见，我们认为 空集也是一个概念u 中的任何概念族称为关于u 的抽象知识，简称知识。 一个划分，定义为= 隅，置，以) ；置c 【，五m ，置n z ，m x 于j ，= l ，2 ， ；【j 蜀= 【，- 面 c ，上的一族划分称为关于【，的一个知识库o ( n a w i e d g eb a s e ) 设置是c ，上的一个等价关系，u ，置表示置所有等价类( 或者u 上的分类) 构成的集合，防k 表示包含元素zec ，的五等价类一个知识库就是一个关系 系统置= ，置) ，其中u 为非空有限集称为论域，孟是【厂上的一族等价关系。 等价关系和划分的关系：由划分的定义可知，由u 上的等价关系盅所生成 的等价类作为元素所构成的集合，就是【，上的一个划分，即由等价关系可以得 到一个划分也就是说，等价关系与划分的概念是一一对应的：一个等价关系 一7 一 第二章粗糙集理论的基本知识简介 可以导出一个划分，一个划分也可以导出一个等价关系 一个由等价关系r 的所有等价类u ，丑构成的集合是u 上的一个划分形成 了一个知识，我们称为足初等知识。足的等价类为知识的r 初等范畴 2 1 2 不可分辨关系与知识 不可分辨关系：在知识库茁= ( u ，且) 中，置且尸m ，则n ，妒中所 有等价关系的交集) 也是一个等价关系，称为，上的不可分辨关系翻，记为 i ，讲( 即，且有 【x 】w 一。胁x k 由这个定义可知，不可分辨关系也是等价关系，它是由等价关系族的交集 构成的一个等价关系。 知识库置= ( 以册中，把加巩目定义为置中所有等价关系的族，记作 f ，甜( 足) = 加d ( ，) i p r ，且p m ) 下面我们用一个简单的例子来说明这些概念。 例2 1 给定一个玩具积木的集合，；“，屯，h ) ，在这些积木中有不同的 颜色( 红、黄、蓝) ，形状( 方、圆、三角) ，体积( 小、大) 。因此，这些积木都可 以用颜色、形状、体积这些知识来描述。例如一块积木可以是红色、小而圆的， 或黄色、大而方的等。如果我们根据某一属性描述这些积木的情况，就可以按 颜色、形状、体积分类。 按颜色分类： 红：t ，毛，耳 蓝：屯，而 黄；而，黾 按形状分类： 圆：而，氟 方：墨，毛 三角：焉， ，而， 按体积分类： 一8 一 第二章粗糙集理论的基本知识简介 大：屯，而， 小：而，而，毛，氏 换言之，我们定义三个等价关系：颜色置，形状r ：和体积墨，通过这些等 价关系，可以得到下面三个等价类： ( 厂，蜀= “西，而，而 ， 而，) ， 毛，砘，气) ， 【，马= 而，毛) ， 屯， ， 而，而，黾) ) ， ，玛= “屯，南，) ， 毛，而，黾， 这些等价类是由知识库k = ( u ， 蜀，r ，马) ) 中的初等概念( 初等范畴) 构成 的。 基本范畴是初等范畴的交集构成的，例如下列集合： 而，矗，而 n 为，而，黾) = 屯，而 ， 而，扎，n x 2 ，x 6 ) = x 2 ， 毛，黾) n 屯，h ，而，黾) = ) 它们分别为( 马，五：) 的基本范畴，即：红色三角形，蓝色方形，黄色三角形。 同时有些范畴在这个知识库中是无法得到的，例如集合： 恐， n 而，) = o ， 而，b ，而 n x 2 ， = o 。 这表明在我们的知识库中不存在蓝色圆形和红色方形的范畴，即为空范畴。 设，= 墨，恐 ，q = 墨，玛) ，丑= 如，玛) ，则有： u p = “而 ， 而，坼) ， 屯) ， ) ， 而) ， ， 黾) ) ， u q = 毛，毛 ， 而) ， 屯) ， ，n ， ， 黾，) ， 【，盖= 毛，如) ， 而 ， k ， 码， ， ，黾) ) ， 【厂 墨，局，玛 = “而 ， 屯 ， 南) ， ) ， 而 ， ) ， x ， ， h 那些画下划线的就是等价类中的元素个数大于l 的，所以对这些元素中的 对象，根据我们现有的知识，无法分辨那么对于画有下划线的等价类中元素 而言，该关系就是它们的一个不可分辨关系这就形成了知识的粒度性。从上 面的例子也看到，随着知识的增加，例如，从知识p 增加到 置，恐，玛 ，知识的 一9 一 第二章粗糙集理论的基本知识简介 粒度有一个缩小的过程。当我们能够分辨所有的对象时，这个知识就是完全清 楚的了 下面讨论两个知识库之间的关系 令蜀= ( u ，p ) 和岛= ，9 为两个知识库 若删= 删，即u ，= u ，q ，则称蜀和( p 和是等价的，记作 蜀：岛( 巴j 。因此当墨和岛有同样的基本范畴时，知识库墨和局中的知识 都能使我们确切地表达关于论域的完全相同的事实。 若加d ( d s 矗耐( 9 时，我们称知识p ( 知识库墨) 比知识q ( 知识库局) 更精 细，或者说知识q 比知识p 更粗糙。当知识p 比知识q 更精细时，我们也称知 识，为知识q 的特化，知识q 为知识p 的推广这意味着，推广是将某些范畴 组合在一起，而特化是将范畴分割成更小的单元。 第二节租糙集理论的基本概念 2 2 1 粗糙集的定义 令x u ，r 为u 上的一个等价关系。当x 能表达成某些r 基本范畴的并 时，称x 是r 可定义的；否则称x 为r 不可定义的。 r 可定义集是论域的子集，它可在知识库r 中精确地定义，而r 不可定义 集则不能在这个知识库且定义。五可定义集也称作胄精确集而胄不可定义集 也称为r 非精确集或胄粗糙集( r o u 曲s c t ) 当存在等价关系胄加d ( 足) 且x 为r 精确集时，集合z u 称为足中的精 确集；当对于任何盖f ，甜( k ) ，工都为r 粗糙集，则工称为r 中的粗糙集 对于粗糙集可以近似地定义，用两个精确集，即粗糙集的上近似( u p p e r a p p r o x i m a t i o n ) 和下近似o o w 口印弘o x i n l a l i ) 来描述。 给定知识库置= ( 矾妁，对于每个子集z u 和一个等价关系矗加d ( k ) 定义两个子集： 星x = u 】，e u ，盂l l ，三盖】， 冠z = u y u ，且i 】，n r m 分别称它们是x 的r 下近似集和矗上近似集。 下近似和上近似也可用下面的等式表达： 一1 0 第二章粗糙集理论的基本知识简介 星y = u 扛u r i 【明 r x = u 缸e u ，r i 【明rn x 西 我们可以把下近似理解为所有那些被包含在z 里面的等价类的并集，而上 近似被理解为所有那些与x 有交集的等价类的并集。 显然有下面的性质： x 为r 精确集当且仅当丛；肼 。 工为定粗糙集当且仅当丛# 肘 一个集合的下近似集和上近似集将论域u 划分为了三个互不相交的区域：j 的r 正域p = 丛，z 的r 负域，昭r ( d = u 一心，x 的胄边界域 b n r = r x 一丛 由上面的定义，堡或p 甜r ( | r ) 是由那些根据知识胄判断肯定属于石的u 中元素组成的集合；尼r 是那些根据知识置判断可能属于石的u 中元素组成的 集合；是那些根据知识矗既不能判断肯定属于z 又不能判断肯定不属于 z 的u 中元素组成的集合；，理乳( z ) 是那些根据知识胄判断肯定不属于x 的u 中元素组成的集合。 粗糙集的表示只是由两个精确集近似地表示，这种近似的大小程度是可以 刻画的集合( 范畴) 的不精确性是由于边界域的存在而引起的，集合的边界域越 大，其精确性则越低为了更准确地表达这一点，我们引入精度的概念。由等 价关系且定义的集合的近似精度为： ( 柳；阻r i l 冗捌 其中x 西，冈表示集合x 的基数 精度用来反映我们对于了解集合z 的知识的完全程度。显然，对每 一个r 和z ( ，有o s 1 。当= 1 时，z 的置边界域为空集，集合 z 为置可定义的；当( 柳 ，且r 有下列等价类： 墨= 粕，而 ， 局= ，而 ， ” 8 ”44 马= 而，而 ， 。 巨= 瓴，黾 ， 易= 为，而o ) ； 集合五= 粕，而，x 。 为震可定义集，因为 一1 2 第二章粗糙集理论的基本知识简介 甄= 蠲= 五u 且； 集合砭= ，屯，毛， 为r 粗糙集，五的粗糙表示如下： 星如= 马u 巨= 协，毛，黾 ， 兄邑= 墨u 毛u 日u 历= ，黾，而，以，黾，而， ， 6 行。( ) = j j 一星如= ，黾，而，o ， p 。( 五) = 堡2 ，2 = 协，而，毛o ) ， 力曙月( 爿：) = u 一r 五= x 2 ，x 6 ， 隅) = 瓯 匦l - 4 ，8 = 1 2 ， m ( 五) = l 一( 五) = 1 2 ； 集合j ，3 = ，而，而) 是r 内不可定义 星瓦= m ， j 瓯= 巨u 易u 历= ，而，屯，而，如，而 u ， 6 ( 邑) = 冗邑一 蜀= ，毛，屯，玛，黾，而) ， 眇。( 墨) = 甄= m ， 行e g r ( 墨) = u 一足玛= ，x 7 ，黾，而o ) ， ( 墨) = 瞄i ，陋卜o 7 = o ， m ( 玛) = 1 一( 五) = l ； 集合j ，4 = 而，而，屯，而，- ，而 为盖外不可定义。 星= 晶u 置= ，毛) o ， r x l u - 6 ( 蜀) = r 邑一墨= 而，而， ，屯，毛，而，南，而o ) ， p 哪。( 蜀) = 鱼，= ，毛 ， 嘲r ) = u 一魁= o ， ( 五) = i 甄l i 甄f - 2 ，1 0 = l 5 ， c 邑) = l 一口r ( 五) = 4 ，5 ； 集合五= ，而，而，南 为且全不可定义 丛s = q ， 欢5 = u ， 。 伐) = 瓯一甄= u ， p o s r q 0 = 擎s = 中t 嘲r 隔) = u 一瓯= 西， 一1 3 第= 章粗糙集理论的基本知识简介 ) = i 甄i i 磁l - o ，l o = o ， 风) = l 一( 五) = l ； 粗糙集理论是经典集合理论的扩展。粗糙集导致了新的成员关系、集合相 等关系和包含关系： 成员关系眶r 石当且仅当x 星y ；难r x 当且仅当苫e 尼r 。虱表示根据知 识r ，x 肯定地属于蜀r 表示根据r ，工可能属于z 分别称自和品为下成员 关系和上成员关系 相等关系：令x = ( u ，五) 是一个知识库，x ，y e u 且r 蒯( 的。 ( 1 ) 若鱼= 墅7 ，则称集合x 和1 7 为五下粗相等，记作j ，= 。y 。 ( 2 ) 若瓦r = j 口，则称集合z 和】，为足上粗相等，记作。y = 。y 。 ( 3 ) 若z r 】，且比r y ，则称集合z 和y 为r 粗相等，记作x * r 】，。 易知，对任何不可分辨关系五，一r 、= r 和a r 为等价关系。 包含关系：令k = ，胄) 是一个知识库，爿，j ，u 且r 打耐( k ) 。 ( 1 ) 若墨r 星r ，则称集合工为r 下包含于l 记作彳c y 。 ( 2 ) 若见r j 彤，则称集合z 为胄上包含于y ，记作z c r l ，。 ( 3 ) 若x cj 7 且z c y ，则称集合z 为矗包含于y ，记作x cy 。 一卫一置 将粗糙集的概念与普通集合论相比较，可以看出粗糙集的基本性质，如元 素的成员关系，集合的等价和包含，都与不可区分关系所表示的论域的知识有 关。因此，一个元素是否属于某一集合，不是该元素的客观的性质，而是取决 于我们对它的了解程度。同样，集合的相等和包含没有绝对的意义，即取决于 我们对所研究问题中的集合的了解程度。 2 2 2 知识的约简 2 2 2 1 知识的绝对约简 知识约简是粗糙集理论的核心内容之一众所周知，知识库中知识( 属性) 并不是同等重要的，甚至其中某些知识是冗余的所谓知识约简，就是在保持 知识库分类能力不变的条件下，删除其中不相关或不重要的知识。 设r 为一族等价关系，胄r ，如果 一1 4 一 第二章粗糙集理论的基本知识简介 加d 限) = 加d - 似 ) ， 则称r 为r 中不必要的；否则称盂为r 中必要的 如果r 为r 中不必要的，则r 和俾 ) 能够表达相同的知识，表明且在r 。中的作用不大，并不能给知识库带来更精细的分类关系，删除它不影响对原来 系统的表达。 如果每一个矗r 都为r 中必要的，则称r 为独立的；否则称r 为依赖的。 如果r 为独立的，则说明r 中的每个等价关系震都是必要的，都不可省略，即 r 具有最小性。 显然，我们马上可以得到如下结论： 如果r 是独立的，r ，则p 也是独立的。 下面我们给出关于知识约简的严格数学定义。 约简：设q p ，如果q 是独立的，并且加烈旦户加成功，则称q 为p 的一 个约简 根据这个定义可知，约简有两个方面的性质：首先，约简所表达的对系统 的划分与原来的知识库所形成的划分是完全一致的，即约简所表达的知识和原 来的知识具有相同的表达能力；其次，就是独立性，郎最小性，约简是能够表 达原来的知识库的最小集合，约简里边不可再进行约简 核：p 中所有必要关系组成的集合，称为户的核。记为c o 陀( n 。 核与约简有如下关系：c d 憎( d = n 耐( p ) ，其中撂成乃表示p 的所有约简。 核这个概念的用处有两个方面：首先它可以作为所有约简的计算基础，因 为核包含在所有的约简之中，并且计算可以直接进行；其次可解释为在知识约 简时，它是不能消去的知识特征集合。 例2 3 设置= ，r ) 是一个知识库，其中u = “，屯，屯 ，盂= 置，岛，马 ， 等价关系墨，是，玛有下列等价类： u ，墨= “而，如， 屯，黾 ， b ) ， ，而) ， u 如； 瓴，而，屯) ， ， 而，而，黾) ) ， u 玛= 而，毛) ， 气) ， 屯，吻，黾) ， 黾，毛 ) 关系加故固有下列等价类； u ，加d ( r ) = “毛，毛) ， 屯，黾 ， 而) ， ) ， ，臼，) 由于 u ，加d ( r 一 蜀) ) = “而，而) ， 而，而，黾 ， 玛) ， ， ) 【，加d 僻) ， 一1 5 第二章粗糙集理论的基本知识简介 所以关系置为置中必要的。 由于 u 加d ( r 一 r 2 = ，黾) ，0 2 ，黾 ， 南) ， ) ， ，) = u ，矗耐( 固， 关系岛为五中不必要的 由于 u ，删( r 一 马 ) 。“而，而) ， ，黾 ， b ， ， 氏 ， 而 ) = u 胁d ( r ) 关系皿为a 中不必要的。 这表明通过等价关系r = 墨，且：，玛) 的集合定义的分类与根据 马，恐) 或 置，马) 定义的分类相同，即表明该系统的知识可以通过u ，枷( 蜀，r ： ) 或 u 涮( 置，马) 来表达 为了得到五= 墨，马，墨) 的约简，我们检验 蜀，马 和 置，马 是否为独立的。 因为 u 折d ( 胄l ，r 2 ) u 胁d ( 蜀) 且u ，涮( r i ，恐 ) u 加d ( r 2 ) ， 所以 墨，r 2 是独立的，即 马，矗： 为r 的一个约简； 又因为 u 蒯( 强，玛 ) u ，砌( 墨) 且u ，砌( 眠，马 ) u 蒯( 玛) ， 所以 局，甩 是独立的，即 马，玛为足的一个约简； 盖有两个约简 蜀，胄： 和 墨，玛 ，r 的核彤( r ) = 蜀，垦 n 马，玛) = 置) 。 2 2 2 2 知识的相对约简 在应用中，一个分类( 不可分辨关系) 相对于另一个分类( 不可分辨关系) 的关 系十分重要，因此我们将介绍知识的相对约简( 1 d a t i v cr e d u c t ) 和相对核( r e l a t i v e c o r e ) 的概念首先我们定义一个分类相对于另一个分类的正域： 令尸和q 为u 中的等价关系。q 的p 正域记为朋p ( q ) ，即 p 嘶( q ) = u ( 蹦i 石e 【，q q 的尸正域是u 中根据分类御的信息可以准确地划分到知识q 的等价类 中的对象集合。也就是说q 的p 正域是由知识p 所产生的等价类所组成的集合， 这些等价类能够完全地属于知识q 。 令p 和q 为等价关系族，孟p ，如果 胛p = 胛，- i 辨 则称r 为p 中q 不必要的；否则r 为p 中q 必要的。 一1 6 第二章粗糙集理论的基本知识简介 如果p 中的每个r 都为q 必要的，则p 为q 独立的 下面我们引入相对约简以及相对核的概念 相对约简：设s 尸，称s 为p 的q 相对约简，当且仅当s 为p 的q 独立 予族，且p s ( q ) ；肿斗( q ) 由这个定义可知：相对约简一方面可以表示原来 的知识，即和原来的系统的分类能力一样；另一方面它又不包含重复的知识， 每个知识都是必要的也就是说，相对约简是能表示原有知识的最小集显然 相对约简允许有多个 相对核：p 中所有q 必要的原始关系所组成的集合，称为p 的q 核。记为 c 口吻( p ) 。 显然根据约简与核的关系，我们马上可以推导出相对约简和相对核的关系： 倒( d = r 1 峨( d 其中旭噍【p ) 是所有p 的q 约简组成的集合。即相对核是所有相对约简的 交集。 l 相对核与前文中提到的核一样，它可以作为所有相对约简计算的基础，因 为相对核包含在所有的相对约简之中，并且计算可以直接进行；还可以可解释 为在进行知识相对约简时它是不能消去的知识特征集合。 。 例2 4 设j 【= ( 【，置) 是一个知识库，其中u = “，屯，黾) ，p = 墨，垦，玛) ， 等价关系玛，恐，马有下列等价类： 。 u 墨= 而，毛) ， x 2 ，黾) ， b ， ，善7 ) ) ， u 如= 五，而，屯 ， ， 屯，而，工8 ) ， ( ，焉= “而，屯) ， ) ， 屯，而，) ， 黾，矗 等价关系q 有下列等价类： c 厂，q = 而，如， ， 屯，) ， 也，而) ， 于是，由p 导出的分类为 u 耐( 刀= 而，) ， 而 ， ， 屯，黾) ， ，伽7 ) 我们可以得到尸的q 正域： 脚= 毛，而，屯，而 现在，从，中去掉置，得到 u ，( ，一 马) ) = “，黾 ， ) ， z 2 ，而，毛) ， 而，) ， 因为 p 口墨p _ t 焉 ( q ) = 而，b ，而，x ， p o 唧 一1 7 一 第二章粗糙集理论的基本知识简介 所以，尼是户必要的 从尸中去掉见，得到 u 妒一 马) ) = “而，屯，蚝) ， z 2 ，黾 ， x ， ， 而，) ) ， 因为 p 甜，一懈，( q ) ； 而，而，_ ，屯，而 2p ，( q ) 所以，置，是p 中不必要的。 从，中去掉届，得到 u ，( 尸一 墨 ) ；“而，南，墨) ， 屯，黾) ， ，而) ) ， 因为 删 i 马 = 胛p ( q ) 所以，尼是p 必要的。 这样，的q 核就是 蜀，玛) ，它也是p 的q 约简。 2 2 3 知识的依赖性 知识的依赖性可以形式化地定义如下：令置= ，五) 是一个知识库，pg 置， q 胄。贝0 ： 知识q 依赖于知识以记作p j q ) ，拥d ( d f ，珂( r ) 。 知识，与知识q 等价( 记作p z q ) ，当且仅当p j q 且q j p 。 知识p 与知识q 独立( 记作p 生) ，当且仅当，j q 且q 辛p 均不成立。 显然，p z q 当且仅当砌( p ) = i 谢( q ) 。 当知识q 依赖于知识尸时，我们也说知识q 是由知识p 导出来的。 通过简单推导可得下列性质： ( 1 ) 如果p j q 且q r ，则，j r ； ( 2 ) 如果p j q 且g j r ，则p u q 置； ( 3 ) 如果p 兮q u r ，则尸j q 且p j 五； ( 4 ) 如果p j q 且q u 五jz