（运筹学与控制论专业论文）信息系统中连续属性的离散化及规则提取.pdf

摘要 摘要 粗糙集的理论基础是集合论，它只能处理离散数据，现实中大量的实型 数据必须进行离散化，因而，研究连续属性的离散化具有重要的理论和现实 意义，本论文对连续属性离散化的方法及不完备信息系统的规则提取进行了 研究。 1 研究了基于模糊聚类的离散化方法，他们都是基于传递闭包的方法， 经一系列的非恒等变换，使得离散后决策表信息丢失较多。给出了一种基于 摄动的模糊聚类的属性离散化方法。 2 大多数对连续属性的离散化方法采用的是领域知识，不具有普遍适应 性的特点，给出基于连续属性的重要性，用自组织特征映射进行优化，以决 策表相容性为判决标准的连续属性离散化方法。 3 针对大多数的离散化方法没有考虑不同连续属性离散化结果间的互补 性和相关性，每个属性的离散化过程都是独立进行的，往往会改变信息系统 不可分辩关系，容易产生不合理和冗余的离散化划分点，提出了基于系统最 大依赖度的连续属性的离散化方法。 4 粗糙集作为一种软计算方法，可以客观地从数据中获取知识，针对现 实中存在的大量不完备的信息系统结合粗糙集理论本身，在研究分布约简、 最大分布约简、分配约简基础上，给出了一种最大分布约简与规则提取的矩 阵算法。 本文的研究成果，对于拓宽粗糙集的理论及粗糙集在数据挖掘中的应用， 有一定的理论和实践意义。 关健词：粗糙集，数据挖掘，知识发现，属性离散化，规则提取 屯子科技大学顼士学位 a b s t r a c t t h eb a s eo f r o u g hs e tt h e o r yi ss e tt h e o r y i tc a no n l yd e a jw i t hd i s c r e t ed a t a s oc o n t i n u o u sa t t r i b u t e sm u s tb ed i s c r e t e d r e s e a r c h i n gt h em e t h o do fd i s c r e t i z i n ga t t r i b u t eh a si m p o r t a l l ts i g n i f l c a t i o ni nt h e o r ya n dr e a l i s t i c i nt h i sp a p e rw e h a v es t u d i e dt h em e t h o d so ft h ed i s c r e t j z a t i o no fc o n t i n u o u sa t t r i b u t e sa n do b t a i n k n o w l e d g ef r o mi n c o m p l e t ei n f o r m a t i o ns y s t e m s 1 t h ef u z z yc l u s t e r i n gm e t h o d so ft h ed i s c r e t i z a t i o ni sb a s e do nt r a n s i t i v e c l o s u r e i th a sp a s s e dt h r o u g has e r i e so fi d e n t i c a lt r a i l s f o r m a t i o n i tm a yl o s ea1 0 t o fi n f o r m a t i o ni nd i s c r e t i z a t e dd e c i s i o n m a k i n g w eh a v eg a v e nam e m o do ft h e d i s c r e t i z a t i o no ff u z z yc l u s t e r i n gm e t h o d sb a s e do np e r t u r b a t i o n ( f c m b p ) 2 m a s so fm e t h o d so ft h ed i s c r e t i z a t i o na d o p tk n o w l e d g eo fd o m a i n ，a n di t c a l lo n l yb e 印p l i c a b i ei nn sd o m a i n w et h i n ko v e rt h ei 瑚【p o r t a n c eo fa t t r i b u t e s a n do p t i m i z er e s u l to fd i s c r e t i z a t i o n 丽t hs e i f o r g a n i z i n gf c a t u r em 印( s o f m ) w e g a v eam e t h o do ft h ed i s c r e t i z a t i o no fr o u g hs e t sc o n t i n u o u sa t t r i b u t eb a s e do n t h es e l f - o r g a n i z j n gf e a t u r em a p 3 m a s so fm e t h o d so fm ed i s c r e t i z a t i o nh a v en o tt h i n ko v e rr e l a t i v i t y b e t w e e nb e f b r ed i s c r e t i z a t i o na n dd i s c r e t i z a t e d t h ed i s c r e t i z a t i o no fa t t r i b u t e s a r e a c c o m p l i s h e di n d e p e n d e n c e n c a nc h a n g e i n d i s c e m i b i l i t y r e l a t i o ni n i n f o r m a t i o n s y s t e m a n di n d u c e i l l o g i c a l i t y a n d r e d u n d a n c ed o t w e g a v e d i s c r e t i z a t i o no fc o n t i n u o u sv a l u e da t t r i b u t e sb a s e do ni n t e r d e p e n d e n c eo f i n f o r m a t i o ns y s t e m 4 t h er o u g hs e tt h e o r y ，a sas o f tc o m p u t em e t h o d ，i san e wm a t h e m a t i c a l t 0 0 1t od e a lw i t hv a g u e n e s sa n du n c e r t a i n t y i tc a no b t a i nk n o w 】e d g ef r o md a t a o b j e c t i v i t y t h e r e a r ea1 0 to f i m p e r f e c t i o n i n f o 彻a t i o n s y s t e m i nf a c t d i s t r j b u t j o nr e d u c t i o n ，m a x i m u md i s t r i b m i o nr e d u c t i o na n da s s i g n m e mr e d u c t i o n a r ei n t r o d u c e di n t ot 1 1 ei n c o m p l e t ei n f o r m a t i o ns y s t e m s o nt h j sc o n d i t i o nw e p r e s e n t sa l g o r i t h m s f o r a s s i g n m e n tr e d u c t i o n ，m a x i m u m d i s t r i b u t i o n r e d u c t i o n a 1 9 0 r i t h m sf o rr e d u c t i o na r ev a l i d a t e db ye x p e r i m e n t s i ts h o w st h a t i i a b s t r a c t t h e s ea l g o r i t h m sc a nf i n dc o r r e s p o n d i n gr e d u c t i o nr e s u l t s 0 u rw o r kh a v ew i d e n e da p p l i c a “o na r e ao fr o u g hs e ti nt h e o r e t i ca n d p r a c t i c a l i t yac e r t a i ne x t e n t k e y w o r d s ：r o u g hs e t ，d a t am i n i n g ，d i s c r e t i z i n ga t t r i b u t i o n ，k n o w l e d g ed i s c o v e i y ，r u l e sp i c k u p 1 i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 躲3 型醢 嗍跏严f 。月加日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名： 盟导师签名：竖 日期：加口厂年p ，曰 第一章绪论 1 1 概述 第一章绪论 随着数据库技术的日益普及，面临着快速扩张的数据海洋，人们如何有 效利用丰富的数据海洋所蕴涵的宝藏为人类服务，人们所依赖的数据分析工 具却无法有效地为决策者提供其决策支持所需要的相关知识【l j ，于是，一个 新的研究领域一一数据挖掘与知识发现应运而生了。由于蕴藏知识的数据信 息大多存储于数据库中，因此又称知识发现为数据库中的知识发现( k d d k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) 或者数据挖掘( d md a t am i n i n g ) 。 知识发现是从目标数据集合中识别出有效的、新颖的、潜在有用的，以 及最终可理解的模式的非平凡过程，知识发现的对象主要是数据库，因此我 们也称知识发现为数据库知识发现。对于数据库来说，知识发现的研究内容 是，能自动地去处理数据库中大量的原始数据，从中挖掘出具有必然性、富 有意义的模式【2 j 。 粗糙集( r o u 曲s e t s ) 3 】是波兰数学家z p a w l a k 在1 9 8 2 年提出的一种分析 数据的数学理论，该理论在分类的意义下定义了模糊性和不确定性的概念， 是一种处理不确定、不完整数据、不精确问题的新型数学工具，它从新的角 度来看待知识，认为知识是源于人类的分类( c l a s s i f i c a t i o n ) 能力，主要应用于 对不完整、不精确信息的表达与处理上。 在数据挖掘中，系统采集到的数据存在许多不确定的因素和不完全信息有 待处理，传统的处理方法，如模糊集理论、证据理论和概率统计理论等，囡 需要数据的附加信息或先验知识，有时在处理大量数据的数据库方面无能为 力。粗糙集作为一种软计算方法，可以客观地从数据中获取知识，利用集合 的上、下近似集合以及集合中的不可分辨关系，粗糙集可以对知识进行分类 进而挖掘出信息系统中潜在知识，最终形成决策规则，可以克服传统不确定 处理方法的一些不足。 基于粗糙集自身独有的优点，自从提出后该理论就一直是各国科学家研 究的热点。目前，粗糙集理论己被广泛应用于人工智能、知识发现与数据挖 电子科技大学硕士学位论文 掘、模式识别与分类、智能控制、故障检测等领域。 1 2 论文的研究背景 ( 1 ) 知识发现和数据挖掘研究现状及发展方向 1 9 8 9 年8 月在美国底特律召开的第1 1 届国际人工智能联合会议i j c a l 中，举行了数据库中知识发现的专题讨论( k d dw o r k s h o p ) ，接着，美国人工 智能学会在1 9 9 1 年、1 9 9 3 年和1 9 9 4 年连续举行了k d dw o r k s h o p 。在统一 这些讨论的基础上，美国计算机学会成立了知识发现与数据挖掘专业委员会 s i g k d d ，并于1 9 9 5 年在加拿大蒙特利尔召开了第一届知识发现与数据挖掘 国际学术会议( t h ea c ms i g k d di n t e m a t i o n a lc o n f c r e n c eo nk n o w l e 如e d i s c o v e r ) ra n d d a t am i n i n g ) 。k d d 已成为许多国际学术会议关注的焦点，如 s i g m o d ，i e e e ，s p i e d m 等。 数据挖掘技术最初就是面向应用的，尤其是在银行、电信、保险、交通、 零售等商业领域，数据挖掘所能解决的典型商业问题有：客户关系管理、数 据库营销、客户群体划分、交叉销售等市场分析行为，以及客户流失性分析、 客户信用记分及欺诈发现等等。另外数据挖掘在生物学以及工业领域也有很 广泛的应用【4 】，知识发现和数据挖掘未来发展方向有： 1 挖掘算法的效率和可扩放性。目前数据库数据量大，维数高，使得 数据挖掘的搜索空间增大，发现知识的盲目性提高。如何充分利用领域的知 识，剔除与发现任务无关的数据，有效地降低问题的维数，设计出高效率的 知识发现算法是发展的重点。 2 数据的时序性。在应用领域的数据库中，数据在不断地更新，随着时 间的推移，原先发现的知识将小而有用，我们需要随时问逐步修正发现模式 来指导新的发现过程。 3 和其它系统的集成。知识发现系统应该是数据库、知识库、专家系 统、决策支持系统、可视化工具、网络等多相技术集成的系统。 4 交互性。可以利用贝叶斯确定数据的可能性及其分布来利用以前的 知识，再就是利用演绎数据库本身的演绎能力发现知识，并用于指导知识发 现的过程。 5 发现精炼的模式。可以利用领域知识进一步提练发现模式，从中提 取有用的知识。 第一章绪论 6 互联网下知识的发现。w w w 正日益普及，从中可以找到很多新的 知识，已有一些资源发现工具来发现含有关键字的文本，但对在w w w 上发 现知识的研究不多。 数据挖掘与知识发现作为一门新兴的具有很大发展潜力的多学科融合的 基础科学，得到了各跨国公司和各国学者的重视和关注【4 】。 ( 2 ) 粗糙集理论研究现状 上世纪七十年代初，波兰学者zp a w l a k 领导的波兰科学院和华沙大学的 研究小组，开始对信息系统逻辑特性进行长期基础性研究，他们针对从实验 中得到的以数据形式表述的不精确、不相容和不完备问题，进行分类分析。 1 9 8 2 年z p a w l a k 发表经典论文r o u g hs e t s ，宣告粗糙集理论( r s t ) 的诞生f 3 j ， 但当时的研究仅限于波兰等少数东欧国家，该理论的提出时并未受到国际智 能研究领域的重视。到9 0 年代，数据挖掘逐渐引起了广大学者的重视，粗糙 集理论才被广泛认识并迅速发展起来。 1 9 9 1 年z p a w l a k 发表了专著r o u g hs e t s ：t h e o r e t i c a l a s p e c t so f r e a s o n i n g a b o u td a t a 【5 1 ，系统全面地阐述粗糙集理论，奠定了粗糙集理论严密的数学 基础，从而掀起了粗糙集的研究高潮。1 9 9 2 年，在波兰召开了第一届国际粗 糙集研讨会，这次会议着重讨论了集合近似的基本思想及其应用。1 9 9 3 年在 加拿大召开了第二届国际粗糙集与知识发现研讨会，由于该次会议正值知识 发现成为热门研究话题，一些著名知识发现学者参加了这次会议，并且提出 了许多应用粗糙集的数据挖掘的方法与系统，粗糙集与知识发现和数据挖掘 紧密地联系在了一起。1 9 9 6 年在日本召开的第五届国际粗糙集研讨会极大地 推动了亚洲和我国对粗糙集理论与应用的研究目前，美国、加拿大、波兰、 日本都有研究粗糙集的专门机构。 近年来，粗糙集已广泛应用于知识发现与数据挖掘、决策支持与分析、 专家系统、智能控制、模式识别等领域。国外己经开发出了一些基于粗糙集 的数据挖掘系统，如r e g i n a 大学利用粗糙集开的数据挖掘系统k d d r ，该 系统目前被广泛应用于医疗诊断、电信业等领域。美国k a n s a s 大学开发的 k e r s ( l e a m i n g 行o me x a m p l e sb a s e do nr s ) 系统，该系统被应用于医疗诊断、 社区规划、全球气象研究等方面。 国外日前在粗糙集领域的理论研究主要集中在约简的优化算法、粗糙集 理论和模糊理论、粗糙集理论与神经网络理论等其它人工智能技术的结合、 粗糙逻辑等理论上面，还有如粗糙集的扩展模型也是一个研究的热点。在应 电子科技大学硕士学位论文 用方面，工程学者广泛重视粗糙集应用于数据挖掘、模式识别等行业。 我国在粗糙集理论方面的研究起步很晚，直到9 0 年代末期才开始研究， 然而进展很快。如目前中科院、清华大学等研究所或者高校都开始了对此理 论的系统研究并取得了丰硕的成果。 1 3 论文研究内容 粗糙集理论作为一种数据挖掘的数学工具有着其他理论不可替代的优点 受到研究学者的广泛关注，因此研究粗糙集理论有着极其重要的理论和现实 意义。在粗糙集理论的研究中，虽然连续属性的离散化不是什么研究热点， 然而它是数据预处理中的一个重要部分，对于粗糙集这种主要是以离散型变 量作为属性类型的学习方法，连续性变量必须被离散化才能够被学习，国内 外许多学者都对此方面予以了关注，连续属性的离散化也是本论文的一个研 究重点。另一方面，由于粗糙集与数据挖掘技术的紧密联系关系，本论文还 研究了基于粗糙集数据挖掘一一规则提取方法，并在参考目前这方面的研究 基础上给出了一种基于粗糙集理论的规则提取的矩阵算法。 1 4 论文组织与结构 第一章绪论，主要介绍了粗糙集、数据挖掘的基本概念，国内外在粗糙 集及数据挖掘方面的研究状况，以及论文的研究背景及工作内容。 第二章数据挖掘综述，介绍了数据挖掘的数据挖掘基本知识、数据挖掘 方法和技术、数据挖掘研究中的技术难题等内容。 第三章粗糙集基本理论，介绍粗糙集理论的基本概念，粗糙集研究的核 心内容以及粗糙集的一些重要性质。 第四章连续属性离散化方法研究，本章介绍了属性离散化的概念和方法， 针对不同的情况，分别提出了几种连续属性离散化方法。 第五章基于粗糙集理论的数据挖掘，介绍了基于相容关系的不完备信息 系统的数据挖掘模型，在此基础上给出了一种最大分布约简与规则提取的矩 阵算法。 第六章结束语，本章对全文工作进行了总结并对全文的工作进行了展望。 第二章知识发现与数据挖掘技术综述 第二章知识发现与数据挖掘技术综述 2 。1 知识发现和数据挖掘基本知识 知识发现也有人称之为数据挖掘( d a t am i n i n g ) ，在许多文献中，研究者 们往往不加区别地使用这两个术语，可以认为数据挖掘、知识发现是同义词。 早期k d d 是指知识发现，现在则统称知识发现和数据挖掘( k n o w l e d g e d i s c o v e r ya n dd a t am i n i n g ) 。 关于知识发现，学术界比较公认的定义是知识发现领域知名学者f a y y a d 和p i a t e s k y s h a p i r o 【6 】给出的，即知识发现是从大量数据中识别出有效的、新 颖的、潜在有用乃至最终可理解的模式的非平凡的过程。f a y y a d 等人给出了 如图2 1 所示的知识发现的一般过程，从图可见，知识发现是多步骤衔接， 反复进行人机交互的过程。具体说明如下：( 1 ) 数据选择，( 2 ) 数据清洁，( 3 ) 数据变换，( 4 ) 数据挖掘，( 5 ) 模式评价与解释。 在上述的每个步骤k d d 系统会提供处理工具完成相应的工作。该过程不 是单向的，在过程的任意步骤都可以返回以前的阶段进行再处理，直到得到 满意的结果。 卅 预 转 处 按 船 理型 数 f d 1 藏 掘 据 2 2 数据预处理 图2 1 知识发现的一般过程 数据库中常常包含许多含有嗓声、不完整、甚至是不一致的数据。显然， 对数据挖掘所涉及的数据对象必须进行预处理，以提高数据挖掘对象的质量， 并最终达到提高数据挖掘所获模式知识质量的目的2 1 。 电子科技大学硕士学位论文 ( 1 ) 数据预处理的基本内容 数据预处理主要包括：数据清洗、数据集成、数据转换、数据消减。 数据清洗是指消除数据中所存在的噪声以及纠正其不一致的错误1 7 】， 数据清洗通常包括：添补遗漏数据、平滑噪声数据、识别或去除异常值，以 及解决不一致问题1 8 j 。 数据集成是将来自多个数据源的数据合并到一起构成一个完整的数据 集，由于描述同一个概念的属性在不同数据库取不同的名字，在进行数据集 成时常常会引起数据的不一致或冗余【9 】。 数据转换是将数据构成一个适合数据挖掘的描述形式，有以下内容：平 滑、合计、泛化、规格化及属性构造【l 。 数据消减通过删除冗余特征或聚类消除多余数，目的是缩小所挖掘数据 的规模，却基本不影响最终的挖掘结果。数据消减的主要策略有以下几种： 数据立方合计、维数消减、数据压缩、数据块消减以及离散化与概念层次生 成等【1 1 】。 这里提及的各种数据预处理方法，并不是相互独立的，而是相互关联的， 数据预处理能够帮助改善数据的质量，帮助提高数据挖掘进程的有效性和准 确性，因此数据预处理是整个数据挖掘与知识发现过程中的一个重要步骤。 ( 2 ) 数据离散化 数据离散化是数据预处理中的一个重要部分，它是一种数据消减方式。 所谓离散化就是利用取值范围或更高层次概念来替换初始数据，将连续取值 属性的域值范围分为若干区间，消减连续取值属性的取值个数【1 ”，对于粗糙 集、决策树这种主要是用来学习以离散型变量作为属性类型的学习方法，连 续性变量必须被离散化才能够被学习1 1 。 2 3 数据挖掘方法和技术 现有的多种数据分析方法从总体上均可归类到统计学习方法、机器学习 方法以及仿生物学方法这三大类中的某一种，在应用上这些方法各有利弊， 需要针对具体挖掘问题选择合适的技术。 f 1 ) 统计学习方法 统计方法是从事物的外在数量的表现去推断该事物可能的规律性。传统 的统计方法在解决机器学习问题中起着基础性的作用，主要研究渐近理论。 6 第二章知识发现与数据挖掘技术综述 常见的方法有回归分析、聚类分析、主元分析以及相关分析等。在传统的统 计学习方法基础上，己经形成多种新型的数据分析方法，如基于范例的推理 方法，n a i v e 贝叶斯和贝叶斯网络，新兴的支持向量机技术则是建立在计算 学习理沦的结构风险最小化原则之上，主要针对两类分类问题在高维空间中 寻找一个超平面作为两类的分割，以保证最小分类错误率，其重要优势在于 可处理线性不可分情况【1 4 】。 ( 2 ) 机器学习方法 机器学习方法是目前研究的重点，从采用的技术上看，可分为两大类： 基于决策树的技术和基于决策规则的方法。 基于决策树的技术以信息论原理为基础建立决策树，最后获得的知识表 示形式是决策树，最为著名的方法就是q u i n i a n 开发的i d 3 方法，还有一些 决策树方法，如a s s i s t a n tp r o f e s s i o n a l ，i d l 以及p r i s m 等。 基于决策规则的方法又可细分为两类，一是在决策树基础上加入规则求 取步骤获得决策规则的方法，如c n 2 方法、c 4 5 方法，a q l 5 及其系列版本 等；另一种则是直接具有规则求取能力的方法，如r o u g h 集、f u z z y 集，这 两类方法可以结合使用产生更好的规则集合【l “。 ( 3 ) 仿生物技术 仿生物技术典型的方法是神经网络方法和遗传算法，这两种方法己经形 成了独立的研究体系，在数据挖掘中发挥着巨大作用。 神经网络模拟人脑神经元结构，以m p 和h e b b 学习规则为基础，建立 了前馈式网络、反馈式网络和自组织网络。前馈式网络可用于预测及模式识 别，反馈式网络擅长联想记忆和优化计算，而自组织网络极适用于聚类研究。 遗传算法是按照自然进化原理提出的一种优化策略。在求解过程中，通 过最好解的选择和彼此组合，可以期望解的集合将会越来越好。在数据挖掘 中，遗传算法能够用来形成变量问依赖关系假设。 2 4 数据挖掘研究中的技术难题 在数据挖掘研究和开发己取得令人瞩目的进展的同时，许多尚待解决和 完善的课题也摆在了研究者面前。涉及数据的问题包括噪声数据、缺夫数据、 冗余数据、海量数据、动态数据等。噪声数据的属性值是不精确或错误的， 会影响抽取的模式的准确性，造成最终结果的不确定性。数据的缺失现象在 电子科技大学硕士学位论文 关系数据库中经常发生，这种情况给发现、评估和解释模式带来了困难，要 求知识发现模型应当具有近似决策能力。与不完整数据相反，给定的数据集 中可能含有冗余的或者不重要的属性或对象，从而增加时间空间开销和结果 规则的复杂度。数据库中数据量的迅速增长，是促进数据挖掘技术发展的原 因之一，也是数据挖掘技术首先要解决的问题。数据库的基本特点是库中的 内容是动态改变的，所以知识发现方法应当具有增量式学习的能力【l 。 为了能够有效的从数据库大量的数据中抽取模式知识，数据挖掘算法必 须是高效的和可扩展的，相应数据挖掘算法的运行时间是可以预测的并可以 接受的。己发现的知识应能准确描述数据库中的内容，并能用于实际领域。 数据挖掘系统还应能很好地处理和抑制噪声数据和不希望的数据，所以要研 究度量知识质量的方法。数据挖掘应该能够用高水平语言、可视化表示或其 它表示方式来描述所挖掘出的知识，以使用户更加容易的理解和应用所挖掘 出的知识。 8 第三章r o u g h 集基础知识 第三章r o u g h 集基础知识 粗糙集理论作为一种新型的处理不确定性知识的工具，它能有效地处理 下列问题：不确定或不精确知识的表达；从实例中获取知识；不一致信息的 分析；根据不确定和不完整的知识进行推理；在保留信息的前提下进行数据 约简；近似模式分类；识别并评估数据之间的依赖关系。不可分辨关系是粗 糙集理论中的最基本概念，并引入上近似和下近似等概念来刻画知识的不确 定性和模糊性；引入约简和核进行知识的化简等计算“”。 3 1 r o u g h 集的基本概念 3 1 1 知识的分类观点 粗糙集理论认为知识足人类对对象进行分类的能力，这里的对象是指所 能涉及的任何事物，称为以下论域。知识构成某一感兴趣领域中各种分类模 式的一个集合，它提供了关于现实的显事实，以及能够从这些显事实中推导 出隐事实的推理能力，通常可用等价关系代替分类。定义3 1 到定义3 9 均来 自文献 18 。 定义3 1 给定论域u ，任何子集x 互u 可称为u 中的一个概念或范畴， 它们构成了特定论域u 的分类。其巾，z u ，置o ，当f 时， 置n 置= o ，i ，= 】，2 月 知识系统处理的是u 上的分类族，一个分类族就定义为一个u 上的知识 库；这样，知识库就是表达智能系统各种基本分类方式的集合。 定义32 若关系凡是论域u 上的划分且= 置，五，五 表达的等价关系 的一个集合，称k = ( u ，脚为近似空间，u r 是月( 或u 的分类) 的所有等价类。 其中每一类表示为m 。= y i y u 丑( y ) = r ( y ) ) ，这样，一个知识库就是一个 关系系统，可以表达为世= ( u ，矗) ，u r 中的集合称为基本概念、初等范畴或 者知识模块。 定义3 3 信息系统表示为s = ( u ，爿，矿，) ，其中u 是对象的非空有限集， 一是属性的非空有限集，：u 一一矿，使得对任何口一，有厂( ，日) k 其 一是属性的非空有限集，：u 一j 矿，使得对任何口一，有，( t ，日) 圪其 9 电子科技大学硕士学位论文 中矿= ij 圪代表属性d 的值域。 d e 定义3 4 信息系统如果表示为s = ( u ，4 y ，力，其中v 和，的意义不变， c u d = 4 是属性的非空有限集，且c n d = 庐，c 表示条件属性集，d 表示决 策属性集，则此种信息系统被称为决策表。 定义3 5 设p 月，p a ，尸中全部等价关系的j p 交集也是一个等价关 系，称为不可分辨关系( i n d i s c e r n i b i l i t yr e l a t i o n ) ，记为优d ( p ) 对于信息系 统s = ( u ，4 ，矿，力，若有且一，且r a ，则州d ( 月) 为： z = d ( r ) 2 厶( z ) 2 ( x ，y ) u u i v 口r ，正( z ) = 六( y ) ) 优d ( r ) 是一个等价关系，且是u 的一个划分，记为u 胁口( r ) 定义3 6 称属性值序偶对( 口，v ) ，口彳，v k 为一个原子特征。任何原 子特征或它的合取被称为一个描述子，称全部属性的原子特征的合取为一个 充分描述子。对属性b 4 ，不取空值的描述子被称为b 一完全描述， 0 ( 岛v ) 忙缸u 阮( 曲= v ) 代表具有原予特征( 口，v ) 的对象的集合a 可见，概念即对象的集合，概念的分类就是u 上的知识，u 上的分类的 集合就是矿上的一个知识库。 3 1 2 知识的概率分布 粗糙集理论把知识看做是具有粒度的，苗夺谦证明了知识粗糙性定义的 偏序较细都是单调下降的【l ，这说明知识粗糙性实质上是所含信息多少的更 深层次上的刻画( 2 0 。知识被理解成关于论域的各种划分模式，对论域进行一 种划分就得到关于论域的一组基础概念。如果在论域中选取一个对象，那么 该对象就随机地满足某个基础概念，所以在粗糙集中知识被看作随机变量。 设u 为一个论域，尸和q 为u 上的两个等价关系族。可以把尸和q 定义为 【，的子集组成的盯一代数上的两个随机变量。 定义3 。7 设p 和q 为u 上导出的划分分别为爿和】，删4 ) 表示集合的 基数，x = 洲删固= 域，五，_ ，) 与y = 叫= 蔓，一j 墨) ，则p 和 q 在u 的子集组成的仃一代数上定义的概率分布分别为： 阮纠= p 盏，p 亳，ip 复， ，瞰纠= p 矗，p 急，ip 麓， 第三章r o u 曲集基础知识 其中删= 鬻， 尸 ) = 1 ，f = l ，2 ，甩， l = 1 吣) = 器，善吧) _ 1 = ，2 ，m 定义3 8p 和q 的联合分布定义为： = 鼢：粥_ 勰 ， 鼽p = 鬻， 尸( 墨r ) = 1 ，f = 1 ，2 ，= 1 ，2 ，m 辟lj = i 有了概率分布和联合分布的定义后，就可以定义知识的条件概率了。 定义3 9 在已知知识p 的条件下，知识q 的条件概率定义为： 鹏脚= 等序l ，2 ，蛳- 1 ，2 ，啪 3 1 3 新型的成员关系 粗糙集拓展了经典集合论，把用于分类的知识嵌入集合内，作为集合组 成的一部分。一个对象x 是否属于集合肖，需要根据拥有的关于论域的知识 来做出判断，可分为三种情况：( 1 ) z e j ；( 2 ) z 拦x ；( 3 ) 可能x 丑，也可能 x 诺传统集合论和模糊集合论都是把成员关系作为原始概念来处理，在 r o u g h 集中，成员关系不再是一个原始概念，无需像在模糊集合中认为给元 素指定一个隶属度，从而避免了主观因素的影响。而且认为不确定与成员关 系有关，而模糊性则表现在集合本身f 2 l 】。 定义3 1 0 【2 2 l 没z u 且x 彳，厶( x ) 是x 的等价类，集合z 的粗糙隶 属函数定义为：心( x ) = 旦笔等勰 显然粗糙隶属函数群是域u 到 o ，1 】的函数，即；：u 斗 o ，1 】且 群( ) o ，1 ，隶属关系是根据己有的分类知识客观计算出来的，描述了一个 对象集合属于某一基本范畴的程度，能够从全域上的个体加以计算，而不是 电子科技大学硕士学位论文 主观给定的。因此，粗糙隶属函数可看作是x 的条件概率，如果 五，e l ( z ) ，那么有心“) = 群( 屯) = 群( x ) ；如果工熨x ) ，则有厶( 石) z ， 所以磁 ) = 1 3 1 4 概念的边界观点 r o u g h 集认为知识的粒度性造成用己有知识不能精确表示某些概念和造 成对象之间的不可分辨2 3 】，因而产生了不精确的边界思想，为刻画这种模糊 性，r o u g h 集采用两个精确集近似地来表示2 4 1 。 定义3 1 1 【2 2 】设j u ，属性集合丑爿，x 的下近似显( x ) ( u p p e r a p p m x i m a t i o n ) 和上近似j 瓦y ) ( 1 0 w e r 印p r o x i m a t i o n ) 分别为： 星( j ) = 缸u 陋】。互x ) 或者显( z ) = u x k ： x k 工) ： 矗( z ) = 缸u | 坷。n j 拼或者露( z ) = u 嘲r ：【胡。n z 以 下近似- ( 石) 是利用知识r ，u 中所有一定能划入x 的元素的集合；上 近似页( x ) 是利用知识r ，u 中所有可能划入x 的元素的集合。 定义2 1 2 1 2 2 1 集合p 傩。( 工) = 丛称为x 的r 正域，而集合u 一星( 肖) 称为 x 的r 负域，记为e 嚷( 工) ，集合肼。( x ) = r ( x ) 一墨( z ) 称为x 的边界域。 易得上近似集、下近似集、正域和边界域之间的以下关系： r ( 上) = p o 峨( ) u 曰( _ ) = 墨( ) u 丑( x ) = u 堡( ) 这几个集合的基数之间存在如下关系： c r d ( u 引忱k ( 置) ) = c h r d ( r ( z ) 显( z ) ) 如果，边界域觋( j ) 为空，则集合是关于r 的精确集；反之，称集 合是关于r 的粗糙集。 3 1 5 粗糙度和分类质量 粗糙集的不确定性是由于粗糙集z 的边界不确定性引起的，集合z 的边 界域越大，其确定性程度就越小。 定义3 1 3 f 2 4 】假定集合x 是论域u 上的一个关于知识r 的粗糙集，定义 其r 精度( 简称精度) 为：呔( ) = o 耐( 豇j ) ) c 口耐( r ( z ) ) ，其中工，如果 1 2 第三章r o u g h 集基础知识 x = 妒，定义如( x ) = 1 定义3 1 4 假定集合x 是论域u 上的一个关于知识月的粗糙集，定义 其尺粗糙度为：最( x ) = 1 一蟊( z ) 定义3 1 5 设集f = 五，五，五) ， u = u 五是论域u 上定义的知识， f # 1 r 是一个属性子集，定义r 对f 近似分类的精度以( f ) 和分类质量分别为 以( f ) = c 缸d 哩( 五) ) o 耐( 面( 五) ) ， 仁1l _ 1 珞( f ) = o 耐哩( 五) ) 血耐( 净l 如果删。( x ) = ，那么称x 是月可定义的，否则就称石是粗糙的。显然， 一个集合j 是否粗糙与具体的属性集合r 上的知识相关。集合x 可视为一个 概念，如果z 在属性集合r 上是粗糙的，那么说明五不足以完全描述z 所对 应的概念。模糊性和不确定性在此有了联系，模糊性是由不确定性来表示的。 但是，粗糙概念可以通过两个精确概念来粗糙地定义，就使我们可以精确地 讲述不精确的概念。 3 2 知识的化简 知识化简与知识的依赖性是r o u 曲集理论的两个最基本问题，知识之间 的依赖性决定知识是否可以进行约简，根据依赖性所定义的知识的重要性往 往是知识约简的重要启发式信息。 ( 1 ) 知识的约简及相对约简 约简与核是两个最重要的概念，知识的约简是指知识的本质部分，它能 定义所考虑的知识中遇到的所有基本概念，而核是其最重要的部分。 定义3 1 6 设r 是等价关系的一个族集，r r 。若d 俾一，) = n 恤( 且) ， 称关系，在集r 中是可省略的，否则就是不可省略的。若集月中每个关系，都 是不可省略的，则称集r 是独立的，否则就是依赖的。 定义3 1 7 若q p 是独立的，并且优d ( q ) = 上( p ) ，则称q 是关系集p 的一个约简( r e d u c t ) 。在集p 中所有不可省略的关系的集合称为p 的核( c o r e ) ， 以c 0 曰e ( p ) 来表示。 电子科技大学硕士学位论文 定理3 1 集族p 的核等于p 的所有约简的交集，即 r e ( p ) = n r e d ( p ) 核的概念具有两方面的意义。首先，可以作为计算所有约简的基础，因 为核包含于每一个约简之中，其计算是直接的。其次，核可以解释为知识最 重要的部分的集合，进行知识的约简时不能够删除它。 一般的约简方法是逐个向核中添加可省略的关系，并进行检查。可省略 的关系集合的幂集的基数是多少，就有多少种添加的方式。最好的情况是所 有不可省略的关系集合本身就是约简，此时的约简是唯一的。所以，计算所 有简约与计算一个最佳简约都是n p 难题1 3 “。 ( 2 ) 知识的相对约简 在应用中，一个分类相对于另一个分类的关系十分重要，因此需要讨论 知识的相对约简和相对核的概念，首先定义相对正域的概念。 定义3 1 8 设p 和q 是论域u 上的等价关系的集，集q 的p 正域记作 尸。哪( q ) ，定义为p g 晖( q ) 2u ( 趵 r e u ，口 集9 的尸正域是论域u 的所有那些使用分类u p 所表达的知识中能够 正确地分类到u q 的等价类之中的对象的集合。 定义3 1 9 设p 和q 是论域u 上的等价关系的集族，r p 若 p ( 塔彻( p ) ( 上 = d ( q ) ) = p ( 塔m d ( 卜 埘) ( 彻( q ) ) 则称关系月在集p 中是9 可省略的，否则称为q 不可省略的。如果在集p 中 的每个关系r p 都是q 不可省略的，则称p 关于q 是独立的，否则就称为是 依赖的。 定义3 2 0s 尸称为p 的q 约简，当且仅当s 是p 的q 独立的子集，且 p o 瞰( q ) 一p 啤( q ) ；集p 中的所有q 不可省略的初等关系的集合，称为集尸 的q 核，记作c 呱( p ) 定理3 2 集p 的q 核等于集p 的所有q 约简的交集，即 c d 四( p ) = n r 2 d o ( p ) 其中月觋( p ) 是集p 的所有q 约简的集。 第三章r o u g h 集基础知识 设p 与q 是论域u 上的等价关系的族集，集q 的集p 正域p 啤( q ) 是使 用知识p 能够分类于知识q 的概念之中的所有对象的集合。如果整个知识尸 对于将对象分类于知识q 的概念中都是必要的，那么知识就是q 独立的，知 识p 的q 核知识是知识p 的本质部分，在不影响将对象分类于q 的概念之中 的能力的前提之下，q 核知识是不能被删除的。以上定义3 1 6 到定义3 2 0 及定理3 2 均来于文献 2 2 】。 3 3 知识的依赖性及属陛的重要性 ( 1 ) 知识的依赖性关系 要进行知识的约简，并从一个给定知识中导出另一个知识，必须研究数 据库中知识间的依赖性关系吲。 定义3 2 1 【2 4 】设k = ( u ，r ) 是一个近似空间，p ，q r ( 1 ) 知识q 依赖于知识p ，当且仅当n 口( p ) 优d ( q ) ，记作p j q ； ( 2 ) 知识p 和知识q 是等价的，当且仅当p j q 且q j 尸，记作p = q ， 明显地，p = q 当且仅当刷d ( p ) = 优d ( q ) ； ( 3 ) 知识p 和知识q 是独立的，当且仅当p j q 且q j p 均不成立，记作 p q 依赖性可以是部分独立的，就是从知识p 能推导出知识q 的一部分知识， 或者说知识q 只有一部分依赖于知识p 的，部分依赖性可以由知识的正域来 定义。 定义3 2 2 州设世= ( u ，r ) 是一个知识库，p ，q r ，称知识9 以依赖度 七( o 七s 1 ) ) 依赖于知识p ，记作尸 。q ，当且仅当 拧邶渤= 蒙俨 蹴舢卜。；。罨辫 ( 1 ) 若七= l ，称知识q 完全依赖于知识p ； ( 2 ) 若o 女 l ，称知识q 部分依赖于知识尸 ( 3 ) 若女= o ，则称知识q 完全独立于知识p 电子科技大学硕士学位论文 y p ，9 反映了