（计算机应用技术专业论文）基于粗糙集理论的知识获取方法研究.pdf

摘要 粗糙集理论是八十年代初由波兰学者z p a w l a k 提出的个数据分 析的有力工具，近年来日益受到各领域的广泛关注，并已在机器学习、 模式识别、决策分析、过程控制、数据库知识发现、专家系统等领域得 到了成功的应用。研究基于粗糙集理论的知识获取方法有着重要的意义。 本文基于粗糙集理论，对信息系统中的一些知识获取方法进行了研 究，并取得了以下研究成果： 在信息系统的决策规则获取方面，针对协调决策表提出了- - ；f o o 基于 正向近似的决策规则挖掘算法。实例表明该算法简单有效。这些结果将 有助于基于粗糙集的知识发现研究。 在不完备信息系统不可区分性的度量方面，将多值信息系统与含有 缺省值的不完备信息系统统一起来，借鉴信息系统中知识粒度与信息熵 的思想，针对含有缺省数据或不精确数据( 即含有缺省值或多值) 的不 完备信息系统，定义了系统的不可区分度与可区分度，并讨论了二者的 性质，建立了二者之问的关系，并且证实了不完备信息系统的不可区分 度与可区分度可退化为完备信息系统的知识粒度与信息熵。这些结果为 研究信息系统不可区分性的度量提供了新的角度。 在不完备信息系统( 含有缺省数据或不精确数据) 的属性约简方面， 针对不完备信息表，基于系统的可区分度给出了属性重要性度量，并提 出了一种基于可区分度的属性约简启发式算法；针对不完备决策表，基 于条件可区分度给出了属性重要性度量，并提出了一种基于条件可区分 度的属性约简启发式算法。实例表明，上述算法能得到不完备信息表的 约简和不完备决策表的相对约简。这些结果对研究不完备信息系统中的 知识约简有着重要的指导意义。 本文基于粗糙集理论对信息系统中的知识获取方法进行了一些研 究。但是，知识获取正处于发展阶段，粗糙集理论在知识获取中的应用 还有许多问题值得研究，本文的研究工作是一个尝试，相关工作还有待 进一步深入。 关键词：粗糙集；不完备信息系统；不可区分度；可区分度；约简 中图分类号：t p l 8 r e s e a r c ho nm e t h o do fk n o w l e d g ea c q u i s i t i o n b a s e do nr o u g hs e tt h e o r y p a n gj i f a n g ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db yp r o f l i a n gj i y e a b s t r a c t r o u g hs e tt h e o r yp r o p o s e db yp o l a n ds c h o l a rz p a w l a ki ne a r l y19 8 0 s i sap o w e r f u lt o o lf o rd a t aa n a l y s i s t h e yh a v eg a i n e di n c r e a s i n g l ys t u d y i n g i nr e c e n ty e a r s ，a n dh a v eb e e ns u c c e s s f u l l yu s e di nw i d e l yf i e l d ss u c ha s m a c h i n el e a r n i n g ，d e c i s i o na n a l y s i s ，p r o c e s sc o n t r o l ，k n o w l e d g ed i s c o v e r yi n d a t a b a s e ，e x p e r ts y s t e me t c t h e r e f o r e ，s t u d y i n gt h em e t h o do fk n o w l e d g e a c q u i s i t i o nb a s e do nr o u g hs e tt h e o r yh a si m p o r t a n ts i g n i f i c a n c e i nt h i st h e s i s ，b a s e do nr o u g hs e tt h e o r yw em a k ea l li n v e s t i g a t i o no nt h e m e t h o d so fk n o w l e d g ea c q u i s i t i o ni ni n f o r m a t i o ns y s t e m a n dt h em a i n r e s e a r c h f u lr e s u l t si sa sf o l l o w s i na s p e c to fd e c i s i o nr u l e sa c q u i s i t i o ni ni n f o r m a t i o ns y s t e m s ，a sf o r c o n s i s t e n td e c i s i o nt a b l e ，ad e c i s i o nr u l e sm i n i n ga l g o r i t h mb a s e do np o s i t i v e a p p r o x i m a t i o ni sp r o p o s e d t h ee x a m p l es h o w st h a tt h i sa l g o r i t h m i ss i m p l e a n de f f i c i e n t t h e s er e s u l t sw i l lb eh e l p f u lf o rs t u d y i n gf o rk n o w l e d g e d i s c o v e r yb a s e do nr o u g hs e tt h e o r y i na s p e c to ft h em e a s u r eo fi n d i s c e m i b i l i t yi ni m p e r f e c ti n f o r m a t i o n s y s t e m ，t h em u l t i v a l u e di n f o r m a t i o ns y s t e ma n dt h ei n c o m p l e t ei n f o r m a t i o n s y s t e mw i t hm i s s i n gv a l u e sa r eu n i f i e d i n t oa s y s t e m a s f o r i m p e r f e c t i n f o r m a t i o ns y s t e m ( i n c l u d em i s s i n gd a t aa n di m p r e c i s ed a t a ) ，u s i n gt h ei d e a o fk n o w l e d g eg r a n u l a t i o na n di n f o r m a t i o ne n t r o p yi ni n f o r m a t i o ns y s t e m ，t h e i n d i s c e m i b i l i t ya n d t h ed i s c e r n i b i l i t yo fi n f o r m a t i o ns y s t e ma r ed e f i n e d ，t h e i r i m p o r t a n tp r o p e r t i e sa r ed i s c u s s e da n dt h er e l a t i o n s h i pb e t w e e nt h e mi s e s t a b l i s h e d a l s oi ti sp r o v e dt h a tt h ei n d i s c e m i b i l i t ya n dt h ed i s c e m i b i l i t yo f i m p e r f e c ti n f o r m a t i o ns y s t e md e g e n e r a t ei n t ot h ek n o w l e d g eg r a n u l a t i o na n d i n f o r m a t i o ne n t r o p yi nc o m p l e t ei n f o r m a t i o ns y s t e m t h e s er e s u l t sp r o v i d e n e ws t u d yv i e wf o rt h em e a s u r eo fi n d i s c e m i b i l i t y i na s p e c to fa t t r i b u t er e d u c ti ni m p e r f e c ti n f o r m a t i o ns y s t e m ，a sf o r i m p e r f e c ti n f o r m a t i o nt a b l e ，t h ea t t r i b u t es i g n i f i c a n c ei sm e a s u r e db a s e do n t h ed i s c e r n i b i l i t yo fi n f o r m a t i o ns y s t e m ，a n dah e u r i s t i ca l g o r i t h mo fa t t r i b u t e r e d u c tb a s e do nt h ed i s c e r n i b i l i t yi sp r o p o s e d ；a sf o ri m p e r f e c td e c i s i o nt a b l e ， t h ea t t r i b u t es i g n i f i c a n c ei sm e a s u r e db a s e do nt h ec o n d i t i o n a ld i s c e m i b i l i t y o fi n f o r m a t i o ns y s t e m ，a n dah e u r i s t i ca l g o r i t h mo fa t t r i b u t er e d u c tb a s e do n t h ec o n d i t i o n a ld i s c e r n i b i l i t yi sp r o p o s e d t h ee x a m p l es h o w st h a tt h ea b o v e a l g o r i t h m sc a r lf i n dt h er e d u c to fi m p e r f e c ti n f o r m a t i o nt a b l ea n dt h er e l a t i v e r e d u c to fi m p e r f e c td e c i s i o nt a b l e t h e s er e s u l t sh a v ei m p o r t a n ti n s t r u c t i v e s i g n i f i c a n c e f o r s t u d y i n g o nt h e k n o w l e d g ea c q u i s i t i o n i n i m p e r f e c t i n f o r m a t i o ns y s t e m w eh a v ed o n es o m es t u d yo nt h em e t h o do fk n o w l e d g ea c q u i s i t i o ni n i n f o r m a t i o ns y s t e mb a s e do nr o u g hs e tt h e o r y , b u tk n o w l e d g ea c q u i s i t i o ni s i nab o o m i n gs t a g ea n dt h e r ea r em a n yp r o b l e m sw o r t hs t u d y i n go nt h e a p p l i c a t i o no fr o u g h s e tt h e o r yi nt h i sf i e l d o u rw o r ki sj u s tab e g i n n i n g ，a n d r e l a t e dw o r dn e e d st ob ef u r t h e rd e v e l o p e d k e y w o r d s ：r o u g hs e t ；i m p e r f e c ti n f o r m a t i o ns y s t e m ；i n d i s c e m i b i l i t y ； d i s c e r n i b i l i t y ；r e d u c t 引言 第一章引言 1 1 论文研究的目的及意义 智能信息处理是当前信息科学研究领域的一个热点。在过去几十年中，人们通 过不断地探索、研究和实践，在专家系统、知识工程、模糊集、人工神经网络等领 域取得了大量的成果。但知识获取，特别是基于实际概括和归纳学习的机器知识获 取方法却越来越成为一个瓶颈。人们希望自动地从数据中获取潜在的依赖模型，而 不是借助于过多的先验知识。所以如何从海量数据库中获取知识，使之能应用于专 家系统，并为决策提供依据，成为信息技术需要解决的重要问题。 本文跟踪国际学术前沿，基于粗糙集理论，借鉴粒度计算的些思想与方法， 针对完备与不完备信息系统( 含有缺省数据或不精确数据) ，分别给出了一些有效的 知识获取方法，这些研究成果不仅丰富和发展了粗糙集理论，而且为信息系统中的 知识获取方法提供了新的思路。 1 2 ，国内外研究现状 1 2 1 粗糙集理论的研究现状 粗糙集( r o u g hs e t ，简写为r s ) 是波兰学者z p a w l a k 为开发自动规则生成系统及 研究软计算问题于1 9 8 2 年提出的。最初关于r s 理论的研究大部分是用波兰语发表 的，因此当时没有引起国际计算机学界和数学界的重视，研究地域也局限在东欧一 些国家。直到8 0 年代末才引起各国学者的注意。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 ga b o u td a t a ” 2 】和1 9 9 2 年r s l o w i n s k i 主编的关于“粗糙集应用 及其相关方法比较研究”的论文集的出版，推动了国际上对粗糙集理论与应用的深 入研究。1 9 9 2 年在波兰k i e k r z 召开了第一届国际粗糙集合研讨会，从此每年召开一 次以粗糙集理论为主题的国际研讨会，加速了粗糙集理论的发展和交流 3 。7 。我国于 2 0 0 1 年5 月在重庆举行了第一届中国r s 理论与软计算学术研讨会。以后每年都召开一 次中国粗糙集与软计算学术研讨会，促进了粗糙集理论在国内的发展 8 。1 。 r s 理论是一种处理不精确、不确定与不完全数据的新的数学方法。由于它在机 器学习与知识发现、数据挖掘、决策支持与分析、专家系统、归纳推理、人工智能、 模式识别与分类、故障检测等方面的广泛应用，现已成为一个热门的研究领域。r s 基于粗糙集理论的知识获取方法研究 理论主要兴趣在于它恰好反映了人们用r s 方法处理不分明问题的常规性，即以不完 全信息或知识去处理一些不分明现象的能力，或依据观察度量到的某些不确定的结 果而进行分类数据的能力。 粗糙集理论具有一些独特的观点。这些观点使得粗糙集特别适合于进行数据分 析。如知识的粒度性：粗糙集理论认为知识的粒度性是造成使用已有知识不能精确 地表示某些概念的原因。通过引入不可区分关系作为粗糙集理论的基础，并在此基 础上定义了上下近似等概念，粗糙集理论能够有效地逼近这些概念；新型成员关系： 与模糊集合需要指定成员隶属度不同，粗糙集的成员是客观计算的，只和已知数据 有关，从而避免了主观因素的影响。采用粗糙集理论作为研究知识发现的工具具有 许多优点。粗糙集理论将知识定义为不可区分关系的一个族集，这使得知识具有了 一种清晰的数学意义，并可使用数学方法进行处理。粗糙集理论能够分析隐藏在数 据中的事实而不需要关于数据的任何附加信息。但是，在粗糙集合应用于实际系统 时，仍然存在一些实际问题。例如约简的有效计算问题，如何处理数据中的噪音和 丢失值问题。为解决上述问题，有许多工作集中在寻求有效的约简算法和对经典粗 糙集理论的扩展上。 此外，基于粗糙集理论的粒度计算研究也是粗糙集研究的一个重要方向。粒度 计算是2 0 世纪6 0 年代由美国著名学者l az a d e h 提出的一种信息处理的新的概念和 计算范式，覆盖了所有有关粒度的理论、方法、技术和工具的研究f 】“2 1 j 。 粗糙集理论的核心思想是给定一个论域u ( 非空有限集合) ，及论域u 上的一个 等价关系足，称序对( u ，月1 是一个近似空间或知识库。在近似空间中，等价关系将论 域【，分割成两两互不相交的等价类，每一个等价类对应一个粒子，同时称商集 u r = x 】。 v x u ) 是近似空间的一组知识基，也代表了论域的一种粒度。这样对 于论域上的任何一个子集( 近似空间的一个概念) 就可以用它的上、下近似来刻画。 z p a w l a k 于1 9 9 8 年提出了利用等价类来描述“粒度”，用“粒度”来描述概念 的粗糙集理论f 2 2 。g jk l i r 运用颗粒的相似性探讨了一些粒度计算的基本问题 2 3 。 工yl i n 在粒度计算的结构、表示及应用方面进行了一系列研究，主要研究了二元关 系( 领域系统、粗糙集和信任函数) 下的粒度计算模型，讨论了粒度计算中的模糊 集和粗糙集方法【2 ”。加拿大r e g i n a 大学教授yy y a o 在研究粗糙集理论的基础上， 提出了基于邻域系统的粒度讨算模型【2 5 】，并成功应用于知识发现领域。接着yy y a o 又从集合理论出发，提出了幂代数、区间数值代数和区问集合代数三种粒度计算模 型，他还从对象之间的等价、相似以及近邻关系多个方面对粒度进行了研究 2 7 j 。 引言 此外，文 2 8 建立了完备信息系统下知识粒度、信息熵和粗糙熵之问的关系。文 2 9 建立了动态粒度下的粗糙集模型。目前基于粗糙集的粒度计算己成为人工智能领域 研究的热点之- - 3 0 ，3 。 粗糙集理论由于其在数据挖掘方面的应用而受到广泛的关注。最近几年，粗糙 集理论在数据缩减与规则生成、大数据集、多方法融合、信息检索、粗糙逻辑、决 策支持和原型系统等方面的应用研究都得到了长足发展。 r s 理论的生命力在于它具有较强的实用性，从诞生到现在虽然只有二十几年的 时间，但已经在许多领域取得了令人鼓舞的成果。例如：模式识别、地震预报、股 票数据分析、数据库中的知识发现、粗糙控制、医疗诊断、专家系统、人工神经元 网络、决策分析等等。 总之，r s 是一种较有前途的软计算方法，为处理不确定性信息提供了有力的分 析手段。我们相信r s 具有广阔的发展空间，今后会在更多的实际领域中发挥作用。 1 2 2 不完备信息系统与多值信息系统的研究现状 r s 理沦以信息系统作为研究对象，如果信息系统中的某些数据存在缺失，称它 为不完备信息系统，否则为完备信息系统。最初由z p a w l a k 提出的r s 理论是面向完 备信息系统的，因此使用r s 理论处理不完备信息系统的早期做法是使用其他方法先 将不完备信息系统转化为完备信息系统，然后应用r s 方法对数据进行处理。处理缺 失值的方法一般有两种：一种是删去带有缺失值的对象；另一种是将每个带有缺失值 的对象用一个可能的对象集合来代替。这些方法由于缺乏对缺失值的直接处理，因而 存在众多的不足。例如，两种处理方式中前一种将会丢失数据中很多有用的知识， 而后一种则会造成数据规模的急剧扩张。针对以上问题，近年来很多r s 理论研究者提 出了多种能够直接对不完备信息系统进行处理的基于r s 理论的扩充模型和方法。 1 9 9 7 年m k r y s k i e w i c z 提出了不完备信息系统的基于容差关系的粗糙集模型及 其知识约简方法，从而为粗糙集的实用化迈出了可喜的一步【3 2 3 ”。m k r y s k i e w i c z 还 比较了几种不完备信息系统的数据分析方法，得出下述结论：( 1 ) 一个规则是确定的， 如果此舰则在原不完备信息系统的每个完备拓展中是确定的；( 2 ) 从不完备决策表中 剔除包含空值的对象后，挖掘的知识可能为伪规则( 对原不完备系统不一定成立) 【3 4 1 。 1 9 9 9 年，j s t e f a n o w s k i 等人区分了不完备信息系统的两个不同语义：“遗失值” 语义和“缺省值”语义，引入了非对称相似关系“缺省值”语义，并在此基础上提 出了基于非对称相似关系的粗糙集扩展模型【” 。2 0 0 1 年，j s t e f a n o w s k i 又提出了基 于量化容差关系的粗糙集模型| 3 。 基于粗糙终理论的知识获取方法研究 2 0 0 2 年王国胤在对以上三个模型进行分析的基础上提出了基于限制容差关系的 粗糙集扩展模型” 。此外，文 3 8 基于m k r y s k i e w i c z 的容差关系对传统的粗糙集理 论在不完备信息系统下进行了初步的拓展。文 3 9 】则基于m k r y s k i e w i c z 的容差关 系，提出了不完备信息系统下的变精度粗糙集模型。 对于缺省值“+ ”本质上是可以通过一些“相似”或“相容”的属性值来“替代”， 这就导致基于相容或相似关系的不完备信息系统。对于遗失值“+ ”，如果仍通过“相 似”值替代，就显得不够合理，但可以考虑“+ ”与其它属性值的“序”关系，这就 导致基于偏序或拟序关系的不完备信息系统。 总之，探讨如何从不完备信息系统中获取有用的知识具有重要的理论和现实意 义，虽然前人对空值有了大量研究 4 0 4 2 ，但基于粗糙集理沦的不完备信息系统的研 究还很薄弱，特别是在不改变原信息系统的前提下从不完备信息系统中获取知识的 理论与方法的系统研究还相对较少。 多值信息系统也是一种常见的粗糙集模型。例如，在数据收集时可能不知道该 属性的具体值，而只知道它可能取几个值之中的一个。显然，这里谈到的取多值的 情况是指多值之间存在“或”的情况。 2 0 0 1 年清华大学胡可云等从实际应用出发提出了多值r o u g h 集模型，定义了共同 关系、共同对、共同类等一系列新概念，并在此基础上重新定义了上近似、下近似 的概念，讨论了相关的性质 4 3 】。 总之，多值粗糙集模型也是粗糙集理论中一种比较常见的模型，如何从多值信 息系统中获取有用的知识也是我们需要研究的一个重要课题。 在理论讨论的很多情形下，为了讨论问题方便，同时也不失一般性，通常可以 将某个属性中的缺省值“+ ”看作是可以取到浚属性值域中的任一值 。此时，就可 以将含有缺省值的不完备信息系统与多值信息系统统一起来，而完备信息系统就是 不完备信息系统属性值取单一值时的一种特殊情形。按照这样的思路，理论探讨时 会显得更为协调合理，应用处理方丽也会更加一致方便( 例如使用同一种算法解决 不同问题) 。 本文第四、五章正是在上述思路的指导下，将多值信息系统与含有缺省值的不 完备信息系统统一起来，基于粗糙集理论对含有缺省数据或不精确数据( 即含有缺 省值或多值) 的不完备信息系统进行研究，为从不完备信息系统中获取知识提供一 种有效的粗糙集方法，以实现海量数据库的知识发现，丰富粗糙集理论的内涵。 4 引言 1 3 本文主要结果概述 本文基于粗糙集理论，并借鉴粒度计算的一些思想与方法，针对协调决策表的 规则获取、不完备信息系统( 含有缺省数据或不精确数据) 的不可区分性度量以及 不完备信息系统( 含有缺省数据或不精确数据) 的知识约简几个方面做了一些探索 性的工作，论文主要研究结果如下： 第二章介绍了粗糙集理论的基本概念。 第三章针对协调决策表，利用具有偏序关系的多个属性集对其进行逐渐细化的 动态规则挖掘，提出了一种基于正向近似的决策规则挖掘算法。实例表明该算法简 单有效。 第四章借鉴信息系统中知识粒度与信息熵的思想，讨论了不完备信息系统中不 可区分性的度量方法。首先给出了对象之间不可区分度的定义，接着在此基础上定 义了信息系统的不可区分度和可区分度，并讨论了二者的性质，建立了二者之间的 关系。并且证实了不完备信息系统的不可区分度和可区分度可退化为完备信息系统 的知识粒度与信息熵。 第五章给出了一种不完备信息系统的知识获取方法。针对不完备信息表，基于 系统的可区分度给出了属性重要性度量，并提出了一种基于可区分度的属性约简启 发式算法：针对不完备决策表，基于条件可区分度给出了属性重要性度量，并提出 了一种基于条件可区分度的属性约简启发式算法。实例表明，上述算法能得到不完 备信息表的约简和不完备决策表的相对约简。 第六章概括了本文的主要结果，说明了本文研究的理论意义及其应用价值，指 出了有待进一步解决的问题及以后值得注意的研究方向。 基于粗糙集理论的知识孙取方法研究 第二章粗糙集理论的基本概念 2 1 近似集 一个近似空问s 是一个二元组s = ( u ，r ) ，其中u 是一个非空有限集，称为论域。 r 是u 上的一个二元关系，称为不可区分关系( i n d i s c e m i b i l i t yr e l a t i o n ) 。假设月是 u 上的一个等价关系，如果( x ，y ) r ，则说x 和y 在s 中是不可区分的。关系r 的 等价类称为s 中的基本集。假设对于每个近似空间s ，空集总是基本集。 s 中任何有限集的并称为s 中的可定义集。s 中所有可定义集用d 矿( s ) 来表示。 设u ，x 为u 中的一个对象。 x 。表示所有与x 不可区分的对象组成的集合， 即由x 决定的尺等价类。集合x 关于r 的下近似定义为 9 】： 一r x = j u l 。j ) ， ( 2 1 ) 实际上是由那些根据已有知识判断肯定属于爿的对象所组成的最大集合，也称 为x 的正区域，记作p o s 。( ) 。 集合x 关于r 的上近似定义为9 1 ： r x = j u i 【x 月n x a ， ( 2 2 ) 瓦z 是由那些根据已有知识判断可能属于x 的对象所组成的最小集合。 集合拥月( 嗣= r x - _ r x 称为并的r 边界域；p o s 月( z ) = 丛称为的r 正域； n e g 。( 爿) = u - r x 称为x 的r 负域。显然：r x = p o s 月( x ) u b n 。( z ) 。 2 2 信息系统 一个信息系统是一个二元组s = ( u ，a ) ，其中 ( 1 ) u 是对象的非空有限集合； ( 2 ) a 是属性的非空有限集合： ( 3 ) 对v a a ，有一个映射l ，l ：u 斗，其中匕是d 的值集。 容易看出，一个属性对应一个等价关系，一个表可以看作是定义的一族等价关 系，即知识库。 每一个属性集p a 决定了一个二元不可区分关系i n d ( p ) ，即 i n d ( p ) = ( z ，y ) u u i v a p ，a ( x ) = d ( ) ，) ) 。( 2 3 ) 易证，i n d ( p ) 是集合u 上的一个等价关系。关系i n d ( p ) ，p a ，构成了u 的 粗糙集理论的基本概念 一个划分，用u i n d ( p ) 表示。u i n d ( p ) 中的任何元素 z ，d 称为等价类或信息 颗粒，这里卜 ，d 。= 抄i ( x ，_ y ) i n d ( p ) 。 令u 1 n d ( p ) 和u n ( q ) 是论域u 上的不可区分关系p 和q 导出的划分，如果 对于橱u i n d ( p ) ，存在y u 1 n d ( q ) 使得x y ，则记为 u i n d ( p ) u i n d ( q ) 。 在不产生混淆的情况下，常用u p 代替u i n d ( p 1 。 令u a = 砜，r ，r 。) ，我们有最小划分a ( u ) = x i z u ) ，和最大划分 j ( = 渺) 。如果论域不会引起混淆，我们也可以将j ( u ) 和j ( 【，) 记为刍和j 。 设p 和q 是有限集u 上的划分，定义偏序关系如下： p q r e , p ，j q ，q 呻只q ， 其中p ! q 表示划分q 比划分p 粗糙( 或者划分p 比划分q 精细) 。 如果p ! q t i p q ，则称划分g 比划分p 严格粗糙( 或者划分尸比划分q 严格 精细) ，记为p _ q 。 2 3 不完备信息系统与多值信息系统 通常，信息系统被认为是完备的，即属性值没有缺省。然而，不完备信息系统 却是普遍存在的。 如果对于至少个属性n a ，圪包含空值，则称s 是一个不完备信息系统 ( i n c o m p l e t ei n f o r m a t i o ns y s t e m ) 3 3 ，3 4 ，否则它是完备的。这表明完备信息系统是不完 备信息系统的一种特殊情形。对于属性d 的缺省值，通常认为可取p 中的任一值， 用+ 来表示。 设p a ，我们定义相容关系： s i m ( p ) = ( “，v ) u u l v a p ，a ( u ) = a ( v ) 或a ( u ) = + 或n ( v ) = + ) 。( 2 4 ) 易知，s i m ( p ) = ns i m ( a ) 。 令品( “) 表示对象集 v ui ( “，v ) 田m ( p ) 。s ，( “) 是与“可能不可区分的对象 的最大集合( 相对p 而言) 。 设u s i m ( p ) 表示分类，即一族集合 品( “) f “u 。u s i m ( p ) 中的元素称为 基于粗糙集理论的知识获取方法研究 相容类或信息颗粒。u s i m ( p ) 中的相容类一般不构成u 的划分，它们构成u 的覆 盖，即对于每一个u u 有& ) 0 ，且u 品( “) = u 。 “e “ 设x u 且p a ，则p x 是x 的下近似，当且仅当 p _ x = x u i 酢( x ) 肖) = 工l 昂( 工) x ) 。 ( 2 5 ) 前是x 的上近似，当且仅当 芦= x u i 酢( x ) n o ) = u ( s p ( x ) ix x ) 。 ( 2 6 ) 与完备信息系统一样，p _ x 是肯定属于的对象的集合，而曩y 是可能属于x 的 对象的集合。 用u 皿m ( 4 ) = i s 。( “) l “来表示分类， 我们有最细分类 j ( 【，) ： s 。( “) ：似l “e u ) ，和最粗分类| ：；l ( u ) = 只( “) = | “e u ) 。如果论域不会 引起混淆，亦可将a ( u ) 和a ( u ) 记为彳和一。 设s ：( u ，爿) 是一个不完备信息系统，p ，q a ，定义偏序关系三如下： p 羔q 营对v i 1 ，2 ，i u l ) ，我t f n s ，( “) s o ( “i ) ，其中p 三q 表示q 比p 粗 糙( 或者p 比q 精细) 。 如果p 5 q g p q ，则称q 比p 严格粗糙( 或者p 比严格q 精细) ，记为p _ q 。 事实上，p q 曹对v i 1 ，2 ，| u i ) ，我们有s e ( u 。) ( 吩) ，并且存在 j 1 ，2 ，一，lu1 ) ，使得s ，( “，) cs o ( “。) 。 多值信息系统也是一种常见的粗糙集模型。一个多值信息系统是一个有序对 m ：，a ，y ) 4 3 1 ，其中u 为非空有限集合，称为论域。a 是属性集合，v 是a 中属 性的值域，矿是属性口a 的值域。对于每个x u ，a ，有( z ) ，其中( x ) 表示x 在n 上的取值且 a ( x ) 巨1 。 多值信息系统是对信息系统的自然扩展，如果对所有的ze u ，n a ，都有 a ( x ) 1 ，则多值信息系统退化为经典的信息系统。 设只。= 月。v 圪i 口锄是定义在属性集a 上的相似关系的集合，当且仅当 相似关系r o 满足：1 ) 自反性v v 圪，v r a v ：2 ) 对称性u r kj v 2 r a v i 。 r 粗糙集理论的基奉概念 易证t r 。= f 7r o 。 若x 和y 是关于d 相似的，当且仅当a ( x ) r 。( y ) 。 若x 和y 是关于a 相似的，当且仅当对v a a ，有a ( x ) r 。( _ y ) ，记为x r 。y 。 v x u ，定义x 关于a 的相似类为只( ) = y u l 斌。力，即e ( x ) 是与x 相似的 所有对象构成的集合。 下面给出一种多值粗糙集中的相似关系，以确定两个多值属性值之间的相似性。 若工与y 关于属性口相似，当且仅当日( x ) n ( y ) o 。 若x 与y 关于属性集合b a 相似，当且仅当对v a b ，有a ( x ) n a ( y ) a 。 所以，论域u 按相似关系r 。来划分，得到了lu f 个相似类，即 u r 。= s a ( ) x u ，u r 。中的相似类一般不构成对论域的划分，它们构成了对 论域的覆盖，即u u r 。= u 。 2 4 决策表与决策规则 一个信息系统s = ( u ，a ) ，如果a = c u d ，c n d = ，则称信息系统( u ，a ) 为一个 决策表，其中c 中的属性称为条件属性，d 中的属性称为决策属性。特别地，如果 p o s 。( d ) = u ，则称决策表s 为协调决策表。 在决策表中，不同的属性可能具有不同的重要性。 给定一个信息系统s = ( ，爿) ，令p i q a ，q 的p 正域记为p o 昂( q ) 9 1 ，即 p o s ，( q ) = u 掣。( 2 7 ) “e u l 0 令s = ( 厂，爿) 为一个信息系统，且p , q c _ a 。当k = ( q ) = f p o s ，( q ) l ，1 u f 时，我 们称q 是k ( o k 1 ) 度依赖于p 的，记作p = 蕞q 纠。 设s = ( u ，a ) 是一决策表，属性c c 在c 中对d 的重要性定义为： 5 辔芑( c ) = y c ( d ) - 7 c - i 。r ( d ) 。 ( 2 8 ) 在决策表s = ( u ，a ) 中，若c c ，则任意属性c c c 关于属性集c + 对d 的 重要性定义为： 基于粗糙集理论的知识获取方法研究 s 喀； ) = y 。- u c l ( d ) 一7 c , ( d ) 。 ( 2 9 ) 在决策表中，最重要的是决策规则的产生。 给定一个协调决策表s = ( u ，a ) ，令x ，和y j 分别代表u c 与u d 中的各个等价 类，d e s ( x i ) 表示对等价类五的描述，即等价类x ，对于各条件属性值的特定取值； d e s ( y i ) 表示对等价类一的描述，即等价类_ 对于各决策属性值的特定取值。 决策规则定义如下： 0 ：d 目( x i ) d e j ( v j ) ，置。 规则的确定性因子 ( 五，) = i x ，n i i x i i ，0 a ( x ，) 1 。 ( 2 1 0 ) 当( 墨，) = 1 时，勺是确定的；当0 掣( 五，0 ) l 时，r o 是不确定的。 2 5 约简与核 信息系统中的知识并不是同等重要的，甚至其中某些知识是冗余的，因此需要 在保持知识库分类能力不变的条件下，删除其中不相关的知识，即知识约简。独立、 约简与核是利用粗糙集进行知识约简时用到的三个主要概念9 1 。 设s = ( u ，a ) 是一个信息系统，a ，如果i n d ( a ) = 1 n d ( a 一恤) ) ，则称a 为a 中不必要的；否则称a 为4 中必要的。 如果每一个a a 都为a 中必要的，则称a 为独立的：否则称a 为依赖的。 设p a 。如果p 是独立的，且 n d ( p ) = 1 n d ( a ) ，则称p 是爿的一个约简。显 然，a 可以有多种约简。a 中所有必要关系组成的集合称为爿的核，记作c o r e ( a 1 。 核与约简有如下关系：c o r e ( a ) = l r e d ( a ) ，其中r e d ( a ) 表示a 的所有约简。 令p ，q c _ a ，口p ，如果p m ( p ) ( q ) ) = p o s w v ( p 巾”( n d ( ) ，则称d 为p 中q 不必要的；否则a 为p 中q 必要的。 如果p 中的每个属性a 都为q 必要的，则称p 为q 独立的。 设s p ，s 为p 的q 约简当且仅当s 是p 相对于q 独立的属性子集且 粗糙集理论的基本概念 p o s 。( q ) = p o s ，( q ) 。p 的q 约简称为相对约简。 p 中所有q 必要的原始关系构成的集合称为p 的q 核，简称为相对核，记为 c o r ( p ) 。 相对核与相对约简有如下关系：c o r e q ( p ) = a r e d 口( p ) ，其中m 叱( j p ) 是所有p 的 q 约简构成的集合。 基于粗糙集理论的知识获取方法研究 第三章决策表中基于正向近似的知识获取方法 决策表一般包含了某一领域的大量数据记录，是领域知识的载体。经典的粗糙 集理论对决策表的研究一般都是通过先对决策表进行约简，然后利用约简产生的单 一属性集( 即确定的等价关系) 来生成决策规则4 6 。4 8 。但是，这种思想有个不足之 处就是分类过程的非动态性，从而导致了决策规则挖掘的非动态性49 1 。在实际应用 中，我们往往需要从多个角度或者多个层次来分析问题、解决问题。也就是说，对 同一个研究对象，需要用一个等价关系族来进行研究，而不是经典粗糙集理论里的 单一等价关系2 9 1 。本文借鉴文 2 9 中提出的正向近似原理对协调决策表进行决策规则 挖掘，提出了一种动态的决策规则挖掘算法。实例表明该算法是有效的。 3 1 基本概念 经典的粗糙集理论采用的是单一属性集，即确定的等价关系。z p a w l a k 认为用 一对上、下近似集合可以粗糙地定义和描述论域中的任意一个子集。在这种情况下， 对对象的粗糙描述便产生了边界域，它可以定量地刻画其粗糙度。 定义3 1 9 1 给定信息系统s = ，爿) ，对于每个子集x u 和一个等价关系 j d a ，定义两个子集： p x = u y u p l y x ，( 3 1 ) p x = y u p y n o ) ，( 3 2 ) 分别称它们为的p 下近似集和彳的p 上近似集。 下近似、上近似也可用下面的等式表达： 一p x = 缸u l x 】p x ) ， ( 3 3 ) 户= x uj x l n x o ) 。( 3 4 ) 集合加，( z ) = p x 一丛称为的p 边界域：p o s ，( x ) = 丛称为x 的p 正域； n e g ，( 工) = u 一肘称为肖的j d 负域。显然：尸= p o s p ( x ) u b n p ( 膏) 。 令p ，o a ，o 的p 正域记为p o s ，( q ) ，即 p o s ，( q ) = u p x 。( 3 5 ) x e “，口 q 的p 正域是u 中所有根据分类圳p 的信息可以准确地划分到关系q 的等价类中去 决策表中基于正向近似的知识获取方法 的对象集合吼 在以往的研究中，人们在描述和刻画问题时一般都是采用单一属性集( 即确定 的等价关系) ，但是，这种方法有个不足之处就是边界域不能够变化，不便于对它作 进一步的分析研究。这时就要用到具有偏序关系的多个属性集来分析和解决问题。 3 2 正向近似 在实际应用中，我们往往需要从多个角度或者多个层次来分析和解抉问题，即 存在以下两种情况：( 1 ) 对同一个问题采用不同的角度来研究；( 2 ) 对同一个问题采 用多个层次来研究2 9 1 。在第二种情况里，又可分为逐渐细化和逐渐粗糙两种情况， 且所采用的多个属性集之间要具有一定的偏序关系。 逐渐细化主要用于处理对研究对象刻画和描述过于粗糙，仍需作进一步更精细 的刻画的情况；而逐渐粗糙则相反，主要处理目前所进行的刻画和描述过于精细， 丢失了一些对象的抱团性质，需要使之粗糙一些的情形。 用具有偏序关系的多个属性集( 即