（应用数学专业论文）关于粗集的不完备信息系统数据挖掘方法研究.pdf

中文摘要 摘要 粗糙集理论是上世纪八十年代初由波兰数学家p a w l a k 首先提出的一种新的 处理不精确、不完全与不相容知识的数学理论。其主要思想是利用已知的知识或 信息来近似不精确的概念或现象。自上世纪九十年代以来，粗糙集在理论上不断 完善，在应用上广泛扩展，己逐渐成为国际学术界的研究热点之一。 在经典粗糙集中，论域上的等价关系起着至关重要的作用。但在现实中，论 域上的二元关系经常不是等价的，此时经典粗糙集模型的应用受到限制。在不完 备信息系统中，建立一种什么样的二元关系，是进一步研究不完备信息系统的粗 计算、知识约简以及规则提取的基础。本文从经典粗糙集模型中的等价关系入手， 把多数包含关系引入到不完备信息系统中定义了一种变精度模型，对不完备信息 系统的粗糙集模型进行了扩充，这种扩展模型是原来模型的推广和改进，既保留 了原来模型的优点又丢弃了原来模型的缺陷，增强了粗糙集模型的抗噪声的能力。 实际数据库中存在较多的连续型数值属性，而现有的很多数据挖掘方法只能 处理离散型的属性，因而需要对连续属性进行离散化，已经出现了多种连续属性 离散化算法，且各有特色和优劣。本文以信息增益作为属性重要性的度量方法， 以基于最小描述长度原理的决策系统信息熵作为离散化过程的评价函数，提出了 一种改进的连续属性离散化算法。该算法不仅考虑了连续属性的属性值之间的序 关系，也考虑了属性值之间的相对距离关系。 关键字：不完备信息系统；粗糙集；扩展模型；离散化 英文摘要 r e s e a r c ht od a t am i n i n go fi n c o m p l e t ei n f o r m a t i o ns y s t e m b a s e do nr o u g hs e t a b s t r a c t r o u g hs e tt h e o r y , p r o p o s e db yp a w l a ki nt h ee a r l y19 8 0 s ，i sam a t h e m a t i c a l t h e o r yf o rr e a s o n i n ga b o u td a t a t h em a i ni d e ao ft h et h e o r yi st oa p p r o x i m a t ei n e x a c t ， u n c e r t a i nc o n c e p t sb yu s i n go f a v m l a b l ek n o w l e d g eo ri n f o r m a t i o n s i n c e19 9 0 s ，i th a s a t t r a c t e dm u c ha t t e n t i o no fr e s e a r c h e r sa r o u n dt h ew o d d n o w , t h i st h e o r yh a sb e c o m e af l a s hp o i i l ti nt h er e s e a r c ha l g ao fc o m p u t e rs c i e n c ea n di n f o r m a t i o ns c i e n c e i nc l a s s i c a lr o u g hs e t , t h ee q u i v a l e n c er e l a t i o n sp l a yi m p o r t a n tr o l e s i nf a c t , t h e e q u i v a l e n c er e l a t i o n sa r el i k e l yt oi n e x i s t e n c ei np r a c t i c e ，s ot h ec l a s s i c a lr o u g hs e t t h e o r yi s l i m i t e di ni 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 s t a r t e d 、) l ，i mt h ee q u i v a l e n c e r e l a t i o n so fc l a s s i c a lr o u g hs e tm o d e l ，w ep u tf o r w a r dak i n do fe x t e n s i o n sr o u g hs e t m o d e lb yi n t r o d u c e dm a j o r i t yi n c l u s i o nr e l a t i o n n o to n l yd o e st h ee x t e n s i o nr e s e l v e t h ea d v a n t a g e so ft h ep r e s e n tm o d e l ，b u ta l s ot h e s em o d e l sd i s c a r dt h ed i s a d v a n t a g e so f t h ep r e s e n tm o d e l t h i sm o d e li m p r o v e st h et o l e r a n c er e l a t i o na n dm a k e st h er o u g hs e t m o r ef l e x i b l e i nt h er e a ld a t a b a s e s ，t h ed a t ar e c o r d sa r ec o m p o s e do fm a n ya t t r i b u t e s 谢t l l c o n t i n u o u sv a l u e s i n c em o s to ft h ee x i s t i n gm e t h o d so fd a t am i n i n ga r ec a p a b l eo f d e a l i n gw i t ht h ed i s c r e t ea t t r i b u t e s ，i t sn e c e s s a r yt od i s c r e t i z et h ec o n t i n u o u sa t t r i b u t e s f i r s t l y i n t h i st h e s i s ，s o m ec o n c e p t so fr o u g hs e t sa r ec o m b i n e dt os t u d yt h e d i s c r e t i z a t i o no fc o n t i n u o u sa t t r i b u t e s i nt h i sp a p e r , a l la l g o r i t h mf o rc o n t i n u o u s a t t r i b m ed i s c r e t i z a t i o nb a s e do ni n f o r m a t i o ng a i na n dt o l e r a n c ed e g r e ew h i c hi su s e dt o m e a s u r et h ea t t r i b u t e si m p o r ti si n t r o d u c e d t h i sm e t h o dt h i n k so v e rn o to n l yt h e o r d i n a lr e l a t i o no fa t t r i b u t ev a l u e s ，b u ta l s ot h er e l a t i v ed i s t a n c eo fa t t r i b u t ev a l u e k e yw o r d 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 s ：r o u g hs e t ：e x t e n d e dm o d e l ； d i s e r e t i z a t i o n 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果，撰写成硕 士学位论文竺基壬担塞的丕壶备值息丕筮錾握揎坦友法班荭：。除论文中已经注明引 用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本论 文中不包含任何未加明确注明的其他个人或集体已经公开发表或未公开发表的成果。 本声明的法律责任由本人承担。 论文作者签名：霭耙 瓣狷2 罗日 学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连海事大学研究生学位论文提交、版权使用管 理办法一，同意大连海事大学保留并向国家有关部门或机构送交学位论文的复印件和电子版， 允许论文被查阅和借阅。本人授权大连海事大学可以将本学位论文的全部或部分内容编入有 关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论文。 保密口，在 年解密后适用本授权书。 本学位论文属于： 保密口 不保密日毒在以上方框内打。，) 论文作者签名：宫慨导师躲京骄 日期：劬g 年硐咖 基于粗集的不完备信息系统数据挖掘方法研究 第1 章绪论 1 1 本文的研究背景和意义 随着信息的不断快速增长，从数据中获取知识的理论越来越凸显重要，对数 据分析方法要求也越来越高，虽然已有较多的数据分析相关技术，但有效的智能 数据分析理论与技术方法还远没有成熟，对它们的深入理解还存在很大差距。 上世纪6 0 年代由l a z a d e h 提出的模糊集理论，使得含糊概念有了具体的 数学描述，但模糊集理论没有给出含糊概念的计算方法，其应用基础很大程度上 还要依赖人们的某些先验知识，从而限制了其应用的客观实际性。 粗糙集理论是p a w l a k 教授【l 刁提出的一种研究不完备、不确定知识和数据的 表达、学习、归纳的理论方法，其主要思想就是在保持分类能力不变的前提下， 通过知识约简，导出问题的决策或分类规则，从而获得知识的简洁表达。在粗糙 集的理论中，知识被认为是一种对对象进行分类的能力1 3 ，知识库是分类方法的 集合，这些描述虽然不是十分完备严格，但却非常清晰地体现了粗糙集模型的基 本思想，为粗糙集理论奠定了基础，并逐步形成了自身理论体系。 在数据挖掘诸多方法中，粗糙集理论对于处理不确定性复杂系统是一种较为 有效的方法，它与概率方法和证据理论等其它处理不确定性问题理论的最显著区 别是它无需提供问题所需处理的数据集合之外的任何先验信息，所以对问题的不 确定性的描述或处理也是比较客观的【4 】。经典粗糙集理论处理的数据是精确的和 不缺损的，然而在现实中，数据的不精确甚至缺损是常见的。当信息系统中存在 未知值( 空值) 时，称为不完备信息系统。针对不完备信息系统，人们提出来很 多处理方法。 如何从海量数据中获取不同简洁程度的知识表达已成为当前研究的一个热 点，但数据库中数据的缺失又限制了很多理论与方法对不完备信息系统的有效处 理1 5 咱】。现在虽然对空值有了大量的研究，但基于粗糙集理论的不完备信息系统 的研究还很薄弱，特别是在不改变原信息系统的前提下如何从不完备信息系统中 获取知识的理论与方法的研究更为迫切。 第1 章绪论 粗糙集理论认为知识是论域在等价关系下形成的划分，所以它便于处理具有 离散属性值的信息系统，而不能直接处理具有连续属性值的系统。出于拓展粗糙 集理论应用范围的要求，合理的离散化算法可以有效的指导数据离散化过程，为 应用粗糙集理论进行数据挖掘做好了前期准备。 1 2 不完备信息系统下的数据挖掘 粗糙集理论也不是万能的，对建模而言，尽管粗糙集理论对知识不完全的处 理是有效的。但是，由于粗糙集理论未包含处理不精确或不确定原始数据的机制， 因此，单纯地使用这个理论不一定能有效地描述不确定或不精确的实际问题。同 时，由于粗糙集理论只能作用于具有离散值的系统，其应用领域也受到了局限。 这意味着，需要其他方法的补充。 1 2 1 不完备信息系统的研究现状及分析 不完备信息系统的知识发现是人工智能领域的重要问题。现实世界的数据库 中的数据很少是完备的：丢失的数据、观测不到的数据、隐藏的数据、录入过程 中发生错误的数据等等是现实世界数据库的一个常见特征。目前有多种方法用于 不完备信息系统的知识获取问题，其中处理空值最简单直接的方法就是删除带有 空值的对象，但删除空值可能造成数据浪费。第二类方法就是通过数据补齐的方 法将不完备信息系统转化为完备信息系统【卜引，再利用完备信息系统的方法进行 处理。如通过统计分析填补空值【9 】，利用其它条件属性的取值和决策属性的取值 或属性之间的联系来估计空值。利用贝叶斯模型和证据理论【1 0 】也是比较常见的数 据补齐方法，但贝叶斯模型需要知道概率密度，而证据理论则需要证据函数，这 些数据之外的信息往往很难得到。在粗糙集理论中，t z u n g - p e ih o n g 等人【8 】利用 上下近似提出了一种填补空值并提取规则的方法，但这种方法无法处理空值较多 的信息系统。另一种做法是让专家根据一定的条件给出空值的估计值，但这种方 法有很大程度的主观性和随意性。还有一种处理空值的方法就是用所有可能的取 值代替空值，根据不同的组合把不完备信息系统转化为完备信息系统。但这种方 法当信息系统中空值较多时计算复杂度过高，效率极低，同时得到的知识并非可 基于粗集的不完备信息系统数据挖掘方法研究 靠。 由于删除和补齐空值处理方法的局限性，人们提出了第三种处理方式：在不 改变信息系统的前提下对不完备信息系统进行研究【1 1 1 。但由于不确定性值的出 现，不能够在对象集上找到符合实际需要的等价关系，因此，只能从对象之间的 相似性来考虑对象之间的关系。就目前的研究情况来看，对不完备信息系统的粗 糙集理论的研究主要采取了相容关系【1 2 1 、非对称相似关系和量化容差关系【1 3 】，王 国胤【1 钾提出了限制容差关系，y a o 州1 5 1 通过定义邻域算子研究了一般二元关系的 粗糙集模型，虽然此文并未特别针对不完备信息系统，但完全可以推广到不完备 信息系统上的一般二元关系。 1 2 2 数据离散化的研究现状及分析 数据开采中经常遇到的技术难点有两点【1 弘1 9 】：一是数据的不完整性，即数据 库中某些个别记录在某些属性上可能存在空值现象，给发现、评估和解释一些重 要的模式带来了困难；另外一个难点是数据库中的某些属性上的属性值是连续的， 如果不对这些数据进行处理，那么给规则的提取带来了很大的困难，必须对这些 连续的数据进行离散化处理。 上个世纪9 0 年代初期，数值属性的离散化开始受到机器学习界的关注，并逐 步吸收了统计学、信息论等领域的研究成果。一些基于信息熵【1 6 】的方法开始出现 在了离散化处理当中。 c h i u ，c h e u n g 和w o n g 在1 9 9 0 年提出了一种基于覆盖离散化空间的最大化 s h a n n o n 熵【1 6 1 的层次化离散化算法。 c a t l c t t1 9 9 1 年研究出了在决策树领域，使用基于信息熵的离散化，做为实现 显著加快拥有许多连续属性的大量数据集的归纳的方法d 2 离散化算法。使用 多个条件标准一每个分区的最小示例数、分区的最大数目和最小信息增益来防止 每个属性分区的递归形式。 1 9 9 3 年，f a y y a d 和i r a n i 将递归信息熵最小限度启发式方法应用于离散化处 理，并且把它与最小描述长度标准方法结合起来，用以控制连续空间中分区产生 的个数。 第1 章绪论 目前，人们提出了许多经过改进的离散化处理方法。如针对数值属性的无监 督离散化，提出了基于概率模型的离散化算法一s t a t d i s c 算法，以及最直观且 容易被理解而且是从全局考虑的由h s n g u y e n 等提出的布尔逻辑和粗集理论相 结合的离散化算法等。 在目前已有的文献中，关于离散化的方法有【2 0 】：e q u a l w i d m 、 e q u a l f r e x l u e n c y 、1 - r u l e 、i d 3 、c 4 5 、m d l p 、f u s i n t e r 等。 1 3 本文的研究内容及主要创新点 本文以不完备信息系统为研究对象，研究了不完备信息系统的变精度粗糙集 模型扩展和决策表连续属性离散化问题，提出了改进的扩展模型。并且针对粗糙 集不能处理决策表中连续属性的缺陷，给出了改进基于信息增益的连续属性离散 化算法。 ( 1 ) 基于容差关系、非对称相似关系、量化容差关系、限制容差关系，结合 粗集的变精度理论，对原来的模型进行了改进，提出了不完备信息系统下改进的 变精度限制容差关系模型，提高了灵活性和适应性。 ( 2 ) 提出了一种基于决策表相容度与信息增益的连续属性离散化算法，该算 法在离散化过程中不仅考虑了连续属性的属性值之间的序关系，也考了属性值之 间的相对距离关系，并且能够自适应的依据给定阈值得到理想的离散化结果。 1 4 本文的组织结构 第1 章绪论，阐述了本文的研究背景和意义，概述了不完备信息系统下的数 据挖掘研究进展和状况。 第2 章介绍了粗糙集的基本理论及其在数据挖掘中的应用，并介绍了粗糙集 的一种扩充变精度粗糙集。 第3 章介绍了不完备信息的粗糙集扩展模型，分析了这几种模型的优缺点， 并提出了改进的变精度限制容差关系。 第4 章介绍了现有的连续属性离散化算法，并对现有离散化算法进行了简单 的划分。提出根据决策表相容性的反馈信息自动调节阈值的改进离散化算法。 基于粗集的不完备信息系统数据挖掘方法研究 第5 章本文工作的总结和未来工作的思考。 5 第2 章粗糙集理论基础 第2 章粗糙集理论基础 1 9 8 2 年，以波兰数学家p a w l a k 为代表的研究者在研究不精确、不确定性及不 完全知识表示和分类的基础上，首次提出了粗糙集理论，用于处理不确定 ( u n c e r t a i n t y ) 、含糊性( v a g u e n e s s ) 知识。粗糙集理论的主要优势在于它不需要 关于数据的任何预备或额外的信息，并且能有效地分析和处理不精确、不一致和 不完整等各种不完备信息，并从中发现隐含的知识，揭示潜在的规律。 2 1 粗糙集理论的研究现状 粗糙集理论及其在知识发现中的应用是一个较新的研究领域，它提供了丰富 的处理不完备性、不确定性和模糊性的方法和工具。近年来，粗糙集理论的方法 已成为知识发现领域的主流之一。 目前，对粗糙集理论研究集中在其数学性质、粗糙集拓广、粗糙集理论中的 度量、与其他不确定方法的关系和互补以及有效约简算法等方面【2 l 】。 在粗糙集理论数学性质方面的研究，主要讨论粗糙集的代数结构、拓扑结构 以及粗糙集的收敛性等问题，致力于构造或生成约简空间圈。一些新的数学概念 也不断出现，如粗糙理想、粗糙半群等1 2 3 1 ，随着粗糙结构、代数结构、拓扑结构、 序结构等各种结构的不断整合，必将引出新的富有生机的数学分支。 在粗糙集拓广方面的研究主要涉及变精度粗糙集模型1 2 4 ) 、模糊粗糙集模型与 粗糙模糊集模型【2 5 1 、基于相似关系的粗糙集模型【2 6 】、基于一般关系的粗糙集模型 【2 7 1 、口r s t 模型幽】、基于优势关系的粗糙集模型 2 9 1 、基于覆盖的粗糙集模型3 0 1 、 不完备信息系统下的粗糙集模型以及对连续系统离散化等。 在粗糙集理论的度量方面主要研究粗糙集数据分析中的度量、知识不确定性 度量以及粗糙集与粗糙关系数据库的信息度量等3 1 3 3 1 。 在粗糙集理论与其它处理模糊性或不确定性方法之间的研究中，主要讨论它 与模糊集理论和d e m p s t e r - s h e f e 证据理论的关系与互补【3 6 1 。神经网络与粗糙集 方法对于从数据中进行特征提取的关系的研究也是非常有意义的课题 3 7 、3 9 】。 董王塑堡塞塑至：塞鱼堡星墨竺墼塑垫塑立鎏堕壅 另外，由于粗糙集的逻辑是关于粗糙集的不确定性的基础，发展这类逻辑的 理论基础也是目前粗糙集理论的研究课题。 近年来r o u g h 集理论的已成为信息科学最为活跃的研究领域之一，已在很多 实际领域取得了成功的应用，如医学诊断、市场分析、银行的数据分析、全球气 候分析、药物的化学结构分析、决策树分析等。例如：美国n a s a 的j o h n s o n 空 间中心利用l e r s 学习系统来发展空间自由行走的医学专家系统；希腊的工业发 展银行e t e b a 应用r s 求取贷款信用；美国的环境保护署利用l e r s 来增进资源 之间的协调等。我国也在国家自然科学基金，国家8 6 3 计划和一些省市基金的支 持下开展了一定的研究工作，逐渐的得到一些研究成果。国内已经连续召开了三 届r o u g h 集会议以及关于粗糙集、模糊集以及粒度计算的国际会议。 2 2 粗糙集的基本概念 定义2 1 m 称s = ，a ，y ，厂) 是一个信息系统；其中，u 为对象的非空有限集 合，称为论域；a 为属性的非空有限集合；矿= u 圪，圪是属性a 的值域； f ：ux 彳哼v 为信息函数，它为每个对象的每个属性赋一信息值，即 v a a ，工u ，f ( x ，口) 圪，设彳= c u d ，c r i d = 彩，c 为条件属性集，d 为决策属 性。 将具有条件属性和决策属性的信息系统称为决策表或决策系统。 一个信息系统对应一个关系数据表：反过来一个关系数据表也对应着一个信 息系统，因此信息系统是数据表的抽象描述。 定义2 2 1 4 0 1 设u 是对象集，令 u 2 = 【，【厂= ( 耳，) l 而，乃u ) ( 2 1 ) r 互u 2 称为u 上的一个等价关系，若尺满足以下条件： ( 1 ) 自反性：( 玉，再) r ，a n ) ； ( 2 ) 对称性：“，x j ) rj ( x j ，再) r ，( v f ，j 刖： 第2 章粗糙集理论基础 ( 3 ) 传递性：( 而，) 尺，( ，x k ) r ( 薯，) r ，( v f ，j ，k a n ) 。 设尺是u 上的一个等价关系，记【薯】置= u i ( ，x j ) 尺) ，则【薯】r 称为包含 玉的等价类。可以证明：若【】足k ，则薯。 x rcu ，= 1 ，2 ，g ，且x = x l ，五，) ( 墨f 2 j ，g ) 。若q 墨cu ， 则x 称为u 的一个覆盖；若x 是u 的一个覆盖且墨n 置= g ( ，s ) ，则x 称为u 的一个划分，z 称为一个类。 i 已u r = f i x , 置l 葺cu ) ，贝t ju r 是u 的一个划分。 定义2 3 删设尺是u 上的一个等价关系，u r 表示r 的所有等价类构成的 集合，【x k 表示包含元素x e u 的r 等价类。一个知识库就是一个关系系统 k = 缈，r ) ，其中u 为非空有限集，称为论域，r 是u 上的一个等价关系族。 定义2 4 4 0 1 若p c _ r ，r p g f 2 j ，h , j n p ( p 中所有等价关系的交集) 也是一 个等价关系，称为p 上的不可分辨( i n d i s c c m i b i l i t y ) 关系，记为z n d ( p ) ，且有 【乩粕，) = f i x 盂 ( 2 2 ) 这样，u i i n d ( p ) 表示与等价关系族p 相关的知识，称为k 中关于【，的p 基本知识，i n d ( p ) 的等价类称为知识p 的基本概念或基本范畴。事实上，p 基本 范畴是拥有知识p 的论域的基本特性，即知识的基本模块。 对于粗糙集可以近似的定义，我们使用两个精确集，即粗糙集的上近似( u p p e r a p p r o x i m a t i o n ) 和下近似( l o w e ra p p r o x i m a t i o n ) 来描述。 定义2 5 1 4 0 1 给定知识库足= 缈，尺) ，对于每个子集xsu 和一个等价关系 r i n d ( k ) ，定义两个子集： ；鳞愿”溅。j 如阮然辩。g # 。 ：、 一： 、 攀雾ii 藿 囊 q 萎_ 豢| ) 饕篱黎 。薹鬻缪 二，巍；麓黔l i 溺徽2 繇i 一 f 誊ji 篝一? ；j 0 蕊 | | i | “ v 。黔舞 。，一誓涉r 第2 苹租糙集理论基础 那些根据知识尺既不能判断肯定属于x 又不能判断肯定属于一x ( 即u x ) 的 u 中元素组成的集合；n e g 胄( x ) 是由那些根据知识r 判断肯定不属于z 的u 中元 素组成的集合。 定理2 1 【删 ( 1 ) x 为r 可定义集当且仅当r x = r x ； ( 2 ) x 为r 的粗糙集当且仅当r x r x 。 2 3 变精度粗糙集 前面介绍的粗糙集理论中的知识约简问题都是在p a w l a k 粗糙集模型下进行 的。p a w l a k 粗糙集模型的一个局限性是它所处理的分类必须是完全正确的或肯定 的，因而它的分类是精确的。p a w l a k 粗糙集模型的另一个局限性是它所处理的对 象是已知的，且从模型中得到的结论仅使用于这些对象，但在实际应用中，往往 需要把从小规模对象集中得到的结论应用于大规模对象集上去，p a w l a k 粗糙集模 型的这些局限性限制了它的应用。 变精度粗糙集理论是对经典粗糙集理论的扩展，它在包含度概念的基础上， 引入了变精度因子，即允许一定程度的错误分辨率存在，这一方面完善了近似空 间的概念，另一方面也有利于粗糙集理论从认为不相关的数据中发现相关数据。 定义2 6 4 0 1 设置y 是论域u 的两个非空子集，x 关于y 的相对错误分类 度c ( x ，y ) 定义为： c c x ，y ，= # l x n 】，l l y l ! 妻：三： ( 2 5 ， 其中1 1 表示集合的基数。 从以上定义可以看到，c ( x ，y ) = 0 当且仅当x 】，如果要将x 中的元素分 基于粗糙集的不完备信息系统数据挖掘方法研冗 类到y 中，则误分的可能性程度是：c ( x ，】，) x l 哆0 0 ，这正是c ( x ，y ) 的意义 所在。真正错分类的元素数目为c ( x ，r ) x l x i ，c ( x ，】，) i 彳i 为绝对分类误差。 定义2 7 【删如果我们设定一个阈值( 通常) ，则可定义部分包含关系如下： b。 y d xo rx g y i fc ( x ，y ) ， ( 2 6 ) 称x 以包含于l ，或】r 以包含丘 应用集合的部分包含关系的概念，将p a w l a k 的上、下近似的概念推广如下： 定义2 8 1 4 0 1 设( 【，r ) 为近似空间，其中论域u 为非空有限集合，r 为【厂上 的等价关系，v r = e , ，岛e 。) 为r 的等价类或基本集构成的集合。对于 ( 0 5 ，l 】，栅u ，定义x 的下近似为 x = u e u r i x 三毋， ( 2 7 ) i - ， 或者 r _ x = u e u i r i c ( e ，x ) _ l - f l ， ( 2 8 ) 墨卢x 也称为正区域，记为p o s r ，( x ) 。 定义x 的上近似为 矿工= u e u r i c ( e ，x ) 仍 ( 2 9 ) 定义x 的夕边界域为 b n r ，( x ) = u e u 尺1 1 一f l c ( e ，工) ，则x 与之非对称相似的对象集合西( 工) 定义为： 西1 ( 功= y l y e u a s b ( x , y ) ， 定义3 5 在非对称相似关系下，对象集合工关于属性集b c 的下近似集和 上近似集分别为： b _ s ( x ) = 扛卜u 西1 ( 功x ) ( 3 5 ) 矿( x ) = u & ( x ) x e x( 3 6 ) 非对称相似关系还具有以下性质： 定理3 1 设不完备信息系统s = ( u ，a ，v ，f ) ，b a ，xcu ，则：e ( 石) s b ( x ) 且( 工) s ；1 ( x ) 。 定理3 2 设不完备信息系统s = ( u ，彳，v ，f ) ，b a ，乃( x ) 是包含z 的相容类。 第3 章不完备信息系统下的粗糙集拓展模型 则：( 1 ) 咒( x ) 瓦( z ) 且1 ( 工) 瓦( x ) ；( 2 ) & ( 工) u 西1 ( x ) 瓦( x ) 。 对于不完备信息系统中的个体，由于已知信息的不同，也可以根据已知信息 的相同程度来刻画它们之间的相近似程度。据此，s t e f a n o w s k i 等人提出了基于量 化容差关系的扩充粗糙集模型。 不同的量化容差( 近似) 关系可以用不同的比较规则来定义。给定一个量化 容差关系，对于个体对象全集【，中的每个元素，s t e f a n o w s k i 定义了容差类的概念， 它是一个用关于参考元素的容差度作为成员函数的模糊集合。如果容差度的值取 为l ，就可以得到容差类的概念。 给定待描述的集合x 和对象集合z 互u ，s t e f a n o w s k i 给出了关于集合z 为集 合x 的上近似、下近似的程度的定义。基于这种观点，对象全集( 厂的每个子集都 可能是集合x 的不同程度的上近似和下近似。为此，s t e f a n o w s k i 对通常的逻辑连 接词采用了如下的函数表示。 定义3 6 逻辑非( 否定) 函数： o ，l 卜 【0 ，1 】，要求n ( 0 ) = 1 ，n ( i ) = 0 。 通常将逻辑非函数表示为n ( x ) = l - x 。 定义3 7t n o r ? l 是一个连续非降函数t ：【0 l 】2 - - , o ，1 】，要求t ( x , 1 ) = x 。 即t n o r m 代表合取。t r l o r f f t 通常有3 种表示： 最小值：t ( x ，y ) = m i n ( x ，y ) ； 乘积：t ( x ，y ) = x x y ； l u k a s i e w i c zt r o r l 能：t ( x ，y ) = m a x ( x + y 一1 ，0 ) 定义3 8t c o r l o r r a 是一个连续非降函数s ：【0 ，1 卜吖0 ，1 】，要求s ( 0 ，y ) = y 。 很明显，t c o t l o r m 代表析取。t c o t l o r m 通常有3 种表示： 最大值：s ( x ，y ) = m a x ( x ，y ) ； 乘积：s ( x ，y ) = 工+ y x x y ； 基于粗集的不完备信息系统数据挖掘方法研究 l u k a s i e w i c zt c o n o r m ：s ( x ，j ，) = ( x + y ，1 ) 。 如果s ( x ，y ) = ( 丁( ( x ) ，( y ) ) ) ，德摩根律就成立，称这样的( ，t ，s ) 三元组 为德摩根三元组。 定义3 9i ( x ，y ) 是x 蕴涵j ，的程度函数，： o ，l 】2 专【0 ，l 】。 定义3 1 0 给定对象集合z ( 厂，x u 和属性集合b c ，做如下定义： ( 1 ) z = 以v 越o ( z ) 互x ； ( 3 7 ) ( 2 ) z = 石口营v 磁o ( z ) 1 3 x * 0 。 ( 3 8 ) 其中，o ( z ) 是对象z 的近似不分明类，对o ( z ) 的定义可作如下函数解释： v 工x ( 力= 矿，x ( x ) ，j 工x 0 ) = 阿s ，x ( x ) ，xs 】r = ，( ，( 段( x ) ，以( 功) ) ， xn y 彩= d 3 ，( x ( 工) y ( 工) ) = 纠母( 丁( 版( 工) 乒l ( 石”) ( z ) = ( t ：) ( j ( 盹力，功) ) ， 心( z ) = z 蛇( 多旧( ：) ( z ( r ( z ，功，砌) 。 其中亿) 是集合z 为x 的下近似的程度，以。( z ) 是集合z 为x 的上近似 的程度，o ( z ) 是对象z 的容差类，r ( z ，工) 是元素x 属于元素z 的容差类的成员隶 属度，工是元素x 属于集合x 的成员隶属度0 0 ，l 】) 。 在k r y s z k i c w i e z 提出的基于相容关系的扩充粗糙集模型中，由于未知值被认 为是和任意已知属性值都相等的，会导致两个个体在没有明确相同的己知属性信 息( 或者极少相同的己知属性信息) 的情况下就被误判定在同一个相容类中；而 在s t e f a n o w s k i 提出的基于相似关系的扩充粗糙集模型中，由于相似关系的非对称 性，一些明显具有大量相同的已知属性信息，直观上就可以判定为相似的个体之 间却不满足相似关系，因而不能划分在同一个相似类中。而在s t e f a n o w s k i 提出的 量化容差关系中，需要预先知道信息系统中属性值的概率分布情况，这对于一个 新的不完备信息系统来说是很困难的在甚至连系统的整体情况都还不清楚的 第3 章不完备信息系统f 的租糙集拓展模型 时候，如何能够精确地知道其分布概率? 鉴于这些扩充关系的局限性，王国胤等 人提出了一种限制容差关裂1 0 1 。 定义3 1 l 设不完备信息系统s = ( u ，a ，v ，f ) ，b 互c ，则限制容差关系定义 为： l b ( x ，j ，) = ( 工，y ) 【，u i ( 工，y ) ( p n ( x ) a p b ( y ) f 2 j ) ， ( 3 9 ) 其中b ( x ) = c p b a f ( x ，c ) 。 从限制容差的定义可以看出，限制容差关系实际就是在容差关系下加入限制 条件弓( 曲n b ) a ，限制容差关系是自反和对称的，但不满足传递性。 设厶( 砷= y 陟【， ( 工，y ) 厶“y ) ) ，xc _ u ，b c c ，则 矿( x ) = x k u 厶亿力量x ， ( 3 1 0 ) 矿( x ) = x 卜( ， ( 厶“y ) x o ) ( 3 1 1 ) 分别为在限制容差关系下，对象集合x 关于属性集bc _ c 的下近似集和上近似集。 容差关系的优点是在属于下近似集中的对象在无需补齐缺损的情况下，依靠 原有属性值就可以与属于不同决策类的对象区分。容差关系的不足是容差关系认 为空值是和任意值都潜在相等的，这会导致两个个体对象在没有明确相同的已知 属性信息，或者只有极少相同的己知属性信息的情况下就被判定在同一个容差类 中，因此很容易将实际不同属性值的个体对象误判为同一类，即容差关系的要求 过于宽松，如对象( 1 ，1 ) 和对象( ，2 ，l ，) 没有任何相的已知属 性值，但在相容关系下却划分在统一容差类中。 非对称相似关系的优点表现为缺损程度越低的对象属于下近似集的几率越 高。非对称相似关系缺点是：由于非对称相似关系实际上是一种偏序关系，可能 将具有很多相同己知属性值的对象划分到不同的相似类，而且缺损程度越小的对 基于租集的不完备信息系统数据挖掘方法研究 象的与之非对称相似的对象集合1 ( x ) 相对越小，这使得划分的粒度过细，从而 非对称相似关系下的下近似集元素过多，但支撑每条规则的对象数太少，会产生 过拟和现象或矛盾情况，即相似关系要求过于苛刻。如果在一个大型的信息系统 中，一两个很相似的个体对象也许由于稍微的一点不完备信息就被认为是完全不 同的，如对象( 2 ，4 ，8 ，l o ，1 2 ，) 和对象( 2 ，4 ， ，8 ，1 0 ，1 2 ，) 仅有少许属性值未知，其它属性值都相同，其实两者很相似，但却不满足非对称 相似关系。 比较容差关系和非对称相似关系，如果对象工与之非对称相似的对象都包含 于疋则对象x 肯定属于x 类；相反，如果对象y 非对称相似于x 中的某个对象， 则对象y 可能属于z 类，则得到如下定理。 定理3 3 给定信息系统s = ，a ，v ，厂) 和个体对象集合z 在非对称相似关系 下，石的上近似和下近似是对在容差关系下的上近似和下近似的改进。 从上面的讨论可以看出，容差关系和相似关系是对不可分辨关系的扩充的两 个极端：相容关系的条件太宽松，使得易于将根本没有相同己知属性的个体误分 到同一个相容类，而相似关系却可能将具有很多相同已知属性信息的个体分到不 同的相似类中。限制容差关系刚好介于容差关系和相似关系这两个极端情况之间。 根据容差关系、非对称相似关系和限制容差关系的定义，这三种关系的上下 近似集具有如下关系：给定z 互u ，艿三c ，则 垦7 ( x ) 互垦工( x ) b j ( x ) ， 否s ( z ) 否( x ) 否r ( x ) 。 由上面对限制容差关系的讨论可知，限制容差关系同时具备了容差关系和非 对称相似关系的优点。从分类粒度上分析，限制容差关系划分的粒度比容差关系 小，比非对称相似关系大，它克服了容差关系下易形成很多不一致性规则的缺点， 也克服了非对称相似关系下支撑每条规则的对象数过少的缺点。但是限制容差关 系还存在两个缺点。其一是对完全没有相同属性值对象的情况处理不够理想。这 第3 章不完备信息系统下的粗糙集拓展模型 种情况可以详细表示为：两个对象没有共同存在的己知属性值，即两个对象不满 足p s ( x ) n p b ( y ) f 2 j 这个条件。且可再细分为两种情况：两个对象的属性值完全 不知；存在已知的属性值。限制容差关系认为前一种情况的两个对象不可分辨， 而后一种情况可以分辨。这两种情况下对象x 和y 没有任何一个相同的属性值， 限制容差关系却认为这两种情况的可分辨性不同，这显然不合情理。既然没有任 何一个相同的属性值，干脆认为这两个对象可以分辨。其二是与容差关系相比， 限制容差关系实质上是排除了两个对象可以化归为同一类的情况：两个对象在某 些个属性上的都为“ 。两个很相似的个体对象也许由于在某一个或一些属性上 的取值都为“ 就判定为属于不同的类中，如对象( 2 ，6 ，8 ，1 0 - - - ) 和( 2 ， ，6 ，8 ，1 0 ) 。 量化容差关系的优点是量化容差关系的矩阵是一个对称方阵，它根据信息表 中已有的信息，刻画了个体对象间的差异，比容差关系矩阵更精确地描述了对象 间的相似程度。这种对象间相似程度的量化，更符合人们的主观要求，但它需要 知道信息系统中属性值的概率分布情况，这对于一个新的不完备信息系统来说有 时候是困难的，这是该方法的一个缺点。 3 3 基于改进型限制容差关系的粗糙集模型 上面介绍的几种不完备信息系统下的粗集的扩展模型都弱化了粗糙集理论基 础的等价关系，以此来实现对经典粗糙集理论的扩充，但是元素之间的关系描述 不够精细，概念表示不精确，因此我们就会想到设计一个拥有度量值的新模型来 改善这种情况。 我们认为在将不完备信息系统中的元素按某种关系分类时，应该对由此产生 的每一个子集中的每个元素赋予一个其隶属于该集合的度量值。 定义3 1 2 不完备信息系统s = ( u ，彳= c u d ，v ，f ) ，x _ cu ，b c ，每一个 子集中的每个元素赋予一个其隶属于该集合的度量值为 基于粗集的不完备信息系统数据挖掘方法研究 聃加踹删， 其中b ( x ) = c l c b 八厂( 工，c ) ) ，1 i 表示集合的基数。 定义3 1 3 不完备信息系统s = ，a = c u d ，矿，力，x u ，bsc ，我们定 义以程度口( 0 口) ， ( 3 1 3 ) 为改进的限制容差关系。 可以看出改进的限制容差关系满足自反性和对称性，但不满足传递性。 定义3 1 4 设s = ( u ，a = c u d ，y ，力是一个信息系统，若x c u ，b c ， ( o s 口1 ) ，设e ( x ) = y l y u a ( x , y ) e ( 工，y ) ，则在改进的限制容差关系下， 对象集合x 关于属性集b 的下近似集和上近似集分别为 鲑( 朋= z u l e ( 毛y ) x ， ( 3 1 4 ) 、 蓐( x ) = i c e 【，陋( 毛y ) n x f 2 j ( 3 1 5 ) 定义3 1 5 不完备信息系统s = ( u ，a = c u d ，y ，f ) ，x 量u ，关于条件属性子 集b c 的度量值为口( 0 口1 ) 的( o 5 一 j 旧( 石) j 一f 。 义基于度量值口的的正域定义为p ( x ) = 垦：( x ) ( 3 1 6 ) ( 3 1 7 ) u u 石 x ，fl【，z【 = = 、，、， x x ，l，l 声口 卢口 曰一 一曰 第3 章不完备信息系统下的粗糙集拓展模型 琏于度量值口的的边界域定义为： 6 ，z ，多c x ，= x 【，i 一 琏于度量值口的的负域定义为： 咒科c 耻卜 卜 1 1 一 j ( 3 1 8 ) ( 3 1 9 ) 根据上面提出的限制容差关系下的集对变精度粗糙集模型，下面讨论它的一 些性质。 定理3 4 设s = ( u ，a = c u d ，y