（系统工程专业论文）粗集理论中的近似精确问题.pdf

摘要 摘要 粗糙集理论是一种处理不精确、巧i 确定性问题的新的数学工具。它建立在分类机制 的基础上，将知识理解为人类对信息、数据的分类能力，用等价关系对空间进行划分， 是一种处理不精确和不完备信息的软计算方法。它与其它处理不确定问题理沦最大的区 别就是它无需提供待处理数据之外的任何先验信息，所有计算都源自数据本身，对问题 的描述和处理应当说是比较客观的。 粗糙集中的不精确性或不确定性产生的主要原因是由于边界的存在，当边界为空时 知识是完全确定的，边界越大知识就越粗糙或越模糊，分类精度越低，越难得到确定的 规则。因此，研究知识的边界问题是粗集理论中提高分类精度的根本问题。 本文主要围绕粗糙集的边界问题，通过引入内外边界及内外近似精确集的思想，结 合模糊集理论、变精度理论、集对分析理论、灰色系统理论等对粗集分类的边界及近似 精度进行了系统的分析，提出了几种切实可行的近似精确集模型和方法，对提高祖糙集 分类精度做了一定的研究。 主要特色和创新点在于：结合内外边界的思想，提出了尺近似精确集和 叫。类近似 精确集的概念；针对粗糙集边界域在不同粒度下的情况，创新性地提出了粒化条件下的 边界求和法及边界积分法：在借鉴王清印等人模糊灰集定义的基础上首次提出了边界模 糊灰集和边界模糊灰数的概念，特别是用正面信息区间隶属度和反面信息区间隶属度来 描述边界元素，是一个崭新的尝试；在模糊粗糙集中引入了粗隶属度的概念，建立了依 参数n 、1 3 双参数的上下近似集双阈值模糊粗糙集模型，及依单参数y 的单闽值模糊粗 糙集模型，对原有的模糊粗糙集模型作了一定的改进；通过引入多数包含关系，对z i a r k o 变精度粗集模型进行了进一步的完善；将变精度粗糙集与模糊粗糙集融合在一起，并结 合实例阐述了变精度模糊粗糙集在近似精度分析方面的作用；在借鉴赵克勤的集对分析 理论基础上，分别提出了基于同一度、对立度的一般相似关系下三参数控制的普通变精 度集对粗集模型和属性客观权重分配下的加权变精度集对粗集模型，用于处理不完备信 息系统具有非常好的效果，值得进一步深入研究。 关键词：粗糙集边界近似精确分类精度 注：本项目由福建省教委科技项目( j a 0 5 2 9 0 ) 资助 a b s t r a c t a b s t r a c t r o u g hs e tt h e o r yi s an e wm a t h e m a t i c a lt o o lo fd e a l i n gw i t hi m p r e c i s e ，u n c e r t a i n p r o b l e m s i ti sb a s e do nc l a s sm e c h a n i s m ，r e g a r d i n gk n o w l e d g ea st h ea b i l i t yo fc l a s s i n g i n f o r m a t i o na n dd a t a i tu s et h er e l a t i o n s h i po fe q u i v a l e n c et o p l o ts p a c e ，i t i sas o f t c a l c u l a t i o nm e t h o do fd e a l i n gw i t hi m p r e c i s ea n di n c o m p l e t ei n f o r m a t i o n t h em o s t d e f e r e n c eb e t w e e nr o u g hs e tw i t ho t h e rt h e o r i e so fd e a l i n gw i t hu n c e r t a i np r o b l e mi st h a ti ti s n on e c e s s a r yt op r o v i d ea n yt r a n s c e n d e n ti n f o r m a t i o na b o u tt h et r e a t i n gd a t a ；a l lc a l c u l a t i o ni s f r o mt h e m s e l v e s ，t h ed e s c r i p t i o na n dd e a l i n ga b o u tt h ep r o b l e m sa r ev e r yi m p e r s o n a l i t y 。 t h em a i nc a u s eo ft h ei m p r e c i s i o na n du n c e r t a i n t yi st h ep r e s e n t a t i o no fr o u g hb o u n d a r y , t h ek n o w l e d g ei sc e r t a i nw h e nt h er o u g hb o u n d a r yi sn u l l ，t h em o r eb i g g e ro ft h er o u g h b o u n d a r yt h em o r er o u g ho rf u z z yo ft h ek n o w l e d g e ，t h em o r el o w e ro ft h ec l a s s p r e c i s i o n ， a n dt h em o r ed i f f i c u l tt of i n dc e r t a i nr u l e s t h u s ，i ti sa ne s s e n t i a lp r o b l e mt oi m p r o v et h e c l a s s p r e c i s i o ni nr o u g hs e to f s m d y i n g t h ek n o w l e d g eb o u n d a r y i nt h i sp a p e r t h ea u t h o ra n a l y z e dt h ea p p r o x i m a t ec l a s s p r e c i s i o na n db o u n d a r yi nr o u g h s e ts y s t e m i c a l l y , v i ai n t r o d u c i n gt h et h o u g h to fi n n e r & o u t e rb o u n d a r i e sa n di n n e r & o u t e r a p p r o x i m a t ed e f i n a b l es e t s ，c o m b i n a t i n gr o u g hs e tw i t hf u z z ys e t ，v a r i a b l ep r e c i s i o nt h e p r y , s e tp a i ra n a l y s i s ( s p a ) ，g r e ys y s t e mt h e o r y , p u tf o r w a r ds o m ef e a s i b l em o d e l sa n dw a y s ，d i d s o m e w o r ko ni m p r o v i n gc l a s s - p r e c i s i o ni nr o u g hs e t m a i nf e a t u r ea n di n n o v a t i o ni sc o n s i s t i n go f f p u tf o r w a r dt h ec o n c e p t i o n so fr - a p p r o x i m a t ed e f i n a b l es e ta n dr c h i l d r e na p p r o x i m a t e d e f i n a b l es e tb yd i n to ft h ei d e ao fi n n e r & o u t e rb o u n d a r y a i ma tt h ec o n d i t i o n si nd i f f e r e n t g r a n u l a r i t yo fr o u g hs e t sb o u n d a r y , p u t t i n gf o r w a r dt h ew a y so fs u n a n di n t e g r a lb a s e do n r o u g hb o u n d a r yi nt h ec o n d i t i o no fg r a n u l a t i n gi n n o v a t i v e l y b r o u g h tf o r w a r dt h ec o n c e p t i o n s o fb o r d e rf u z z yg r e ys e ta n db o r d e rf u z z yg r e yn u m b e rf i r s t l yu s et h ed e f i n eo ff u z z yg r e ys e t o fw a n d q i n g y i nf o rr e f e r e n c e e s p e c i a l l y , t h ea u t h o ru s e dp o s i t i v es i d ei n f o r m a t i o ni n t e r v a l m e m b e r s h i pd e g r e ea n dn e g a t i v es i d ei n f o r m a t i o ni n t e r v a lm e m b e r s h i pd e g r e et od e s c r i b et h e b o u n d a r ye l e m e n t ；i ti sab r a n dn e wa t t e m p t t h r o u g hi n t r o d u c i n gt h ec o n c e p t i o no fr o u g h m e m b e r s h i pd e g r e e ，t h ea u t h o rc o n s t r u c t e dt h em o d e l so fd o u b l ep a r a m e t e rf u z z yr o u g hs e t a n ds i n g l ep a r a m e t e rf u z z yr o u g hs e t ，t h u si m p r o v e dt h eo l dm o d e l s p e r f e c t e dz i a r k o s v a r i a b l ep r e c i s i o nr o u g hs e tt h r o u g hi n t r o d u c i n gm a j o r i t y - i n c l u s i o nr e l a t i o n c o m b i n a t e d v a r i a b l ep r e c i s i o nr o u g hs e tw i t hf u z z yr o u g hs e t ，a n de x p o u n d e dt h eu s eo na n a l y z i n gt h e a p p r o x i m a t ep r e c i s i o no fv a r i a b l ep r e c i s i o nf u z z yr o u g hs e tb yd i n to fa ne x a m p l e b yu s eo f z h a o k e q i n ss e tp a i ra n a l y s i st h e o r y , b r o u g h tf o r w a r dt w on e wm o d e l s ：o n ei sp o p u l a rs e tp a i r 1 a b s t r a c t a n a l 2 _ r s i sv a r i a b l ep r e c i s i o nr o u g hs e tb a s e do nt h es a m ed e g r e e ，o p p o s i t ed e g r e ea n dt h r e e p a r a m e t e r s c o n t r o lo ft h eg e n e r a ls i m i l i t u d er e l a t i o n ，t h eo t h e ri sw e i g h t e ds e tp a i ra n a l y s i s v a r i a b l ep r e c i s i o nr o u g hs e tb a s e do ni m p e r s o n a lw e i g h t sa l l o c a t i o no ft h ea t t r i b u t e s ，t h e s e t w om o d e l ss h o wg r e a te f f e c to nd e a l i n gw i t hi n c o m p l e t es y s t e m ，a n di tw o r t hr e s e a r c hm o r e d e e p l y k e yw o r d s ：r o u g hs e t ；b o u n d a r y ；a p p r o x i m a t ep r e c i s i o n ；c l a s sp r e c i s i o n n o t e s ：t h i sp r o j e c ti ss u p p o r t e db yf u jj a np r o v i n c ee d u c a t i o nd e v e l o p m e n tf u n d ( j a 0 5 2 9 0 ) 2 摘要 摘要 粗糙集理论是一种处理不精确、巧i 确定性问题的新的数学工具。它建立在分类机制 的基础上，将知识理解为人类对信息、数据的分类能力，用等价关系对空间进行划分， 是一种处理不精确和不完备信息的软计算方法。它与其它处理不确定问题理沦最大的区 别就是它无需提供待处理数据之外的任何先验信息，所有计算都源自数据本身，对问题 的描述和处理应当说是比较客观的。 粗糙集中的不精确性或不确定性产生的主要原因是由于边界的存在，当边界为空时 知识是完全确定的，边界越大知识就越粗糙或越模糊，分类精度越低，越难得到确定的 规则。因此，研究知识的边界问题是粗集理论中提高分类精度的根本问题。 本文主要围绕粗糙集的边界问题，通过引入内外边界及内外近似精确集的思想，结 合模糊集理论、变精度理论、集对分析理论、灰色系统理论等对粗集分类的边界及近似 精度进行了系统的分析，提出了几种切实可行的近似精确集模型和方法，对提高祖糙集 分类精度做了一定的研究。 主要特色和创新点在于：结合内外边界的思想，提出了尺近似精确集和 叫。类近似 精确集的概念；针对粗糙集边界域在不同粒度下的情况，创新性地提出了粒化条件下的 边界求和法及边界积分法：在借鉴王清印等人模糊灰集定义的基础上首次提出了边界模 糊灰集和边界模糊灰数的概念，特别是用正面信息区间隶属度和反面信息区间隶属度来 描述边界元素，是一个崭新的尝试；在模糊粗糙集中引入了粗隶属度的概念，建立了依 参数n 、1 3 双参数的上下近似集双阈值模糊粗糙集模型，及依单参数y 的单闽值模糊粗 糙集模型，对原有的模糊粗糙集模型作了一定的改进；通过引入多数包含关系，对z i a r k o 变精度粗集模型进行了进一步的完善；将变精度粗糙集与模糊粗糙集融合在一起，并结 合实例阐述了变精度模糊粗糙集在近似精度分析方面的作用；在借鉴赵克勤的集对分析 理论基础上，分别提出了基于同一度、对立度的一般相似关系下三参数控制的普通变精 度集对粗集模型和属性客观权重分配下的加权变精度集对粗集模型，用于处理不完备信 息系统具有非常好的效果，值得进一步深入研究。 关键词：粗糙集边界近似精确分类精度 注：本项目由福建省教委科技项目( j a 0 5 2 9 0 ) 资助 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研究成果。 本人在论文写作中参考的其他个人或集体的研究成果，均在文中以明 确方式标明。本人依法享有和承担由此论文产生的权利和责任。 栅雠纠r i z l “痧年 月 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。厦门大 学有权保留并向国家主管部门或其指定机构送交论文的纸质版和电 子版，有权将学位论文用于非赢利目的的少量复制并允许论文进入学 校图书馆被查阅，有权将学位论文的内容编入有关数据库进行检索， 有权将学位论文的标题和摘要汇编出版。保密的学位论文在解密后适 用本规定。 本学位论文属于 1 、保密() ，在年解密后适用本授权书。 2 、不保密( ) ( 请在以上相应括号内打“”) 作者签名：母1 易 导师签名：多川三、身荦 厶f 日期：础，阴，日 日期：彤年r ，月，徊 第章绪论 第一章绪论 1 1 粗糙集理论发展的历史和现状 在自然科学、社会科学等许多学科领域中，我们常常都会不同程度地涉及到对不确 定性问题和对不完备信息的处理。从现实中采集到的数据常常存在噪声、数据缺失、不 一致等问题，如仅采用纯数学方法来处理，效果往往不理想。多年来，研究人员一直在 努力寻找科学地处理不完整性和不确定性问题的有效途径。模糊集理论和基于概率统计 的证据理论在处理这类不确定信息方面己取得一定成效，但他们往往需要一些数据的附 加信息或是先验知识，给问题的处理带来了一定的困难。粗糙集理论的出现，为解决这 些问题提供了强有力的数学工具。 粗糙集理论作为一种处理不精确、不确定与不完全数据的新的数学理论，最初是在 1 9 8 2 年，由波兰学者z p a w l a k 提出来的 升。其经典论文r o u g hs e t s 引，宣告了粗糙集理 论的诞生。由于最初的研究理论大多是以波兰文发表的，因此当时并未引起国际计算机 界和数学界的重视，研究的地域也仅限于东欧一些国家。直到1 9 9 0 年前后，由于该理 论在数据的决策与分析、模式识别、机器学习与知识发现等方面的成功应用，才逐渐引 起了世界各国学者的广泛关注。1 9 9 t 年。z p a w l a k 的专著 r o u g h & 8 一t h e o r e t i c a l a s p e c t s o fr e a s o n i n ga b o u td a t a ”酬的问世，标志着粗糙集理论及其应用的研究进入了活跃时 期。1 9 9 2 年在波兰k i e k r z 召开了关于粗糙集理论的第一届国际学术会议，着重讨论了 粗糙集的基本思想。1 9 9 3 在加拿大b a n f f 召开了第2 届国际粗糙集与知识发现( r s d 9 3 ) 研讨会，极大地推动了国际上对粗糙集理论与应用的研究。1 9 9 5 年召开的第4 届模糊理 论与技术国际研讨会( f u z z yt h e o r y & t e c h n o l o g y 9 5 ) 上，针对粗糙集与模糊集的基本 观点与相互关系展开了激烈的讨论，较大地促进了粗糙集的研究。同年，a c m c o m m u n i c a t i o n 将粗糙集列为新浮现的计算机科学的研究课题。1 9 9 6 年在日本东京召开 了第5 届国际粗糙集研讨会，这是第一次在亚洲地区召开的范围广泛的粗糙集研讨会。 2 0 0 5 年在加拿大r e g i n a 大学召开了第十届粗糙集，模糊集和粒计算国际学术研讨会 ( r s f d g r c 2 0 0 5 ) 。 粗糙集理论的研究在中国也得到了较快的发展，从2 0 0 1 年在重庆召开“第1 届中 国r o u g h 集与软计算学术研讨会” 5 5 1 至今已连续召开了五届。2 0 0 3 年1 0 月在重庆举 办“第9 届粗糙集、模糊集、数据挖掘和粒度一软计算的国际会议”。从事粗糙集理论研 第一章绪论 究的队伍不断壮大，研究的深度和广度已有了较大的提高。 粗糙集理论是建立在分类机制的基础上的，它将知识理解为人类对信息、数据的分 类的能力，用等价关系对空间进行划分，是种处理不精确和不完备信息的软计算方法。 其主要思想就是利用已知的知识库，将随机的、不确定的数据用知识库中的知识来近似 表达。它与其它处理不确定问题理论最大的区别就是它无需提供待处理数据之外的任何 先验信息，所有计算都源自数据本身，对问题的描述和处理应当说是比较客观的。 由于粗糙集理论诞生的历史较短，至今为止对其概念的定义都还没有完全统一。一 种是以经典p a w l a k 意义下上下近似集来命名的，另一种是以上下近似所构成的区间来 定义，二者研究的侧重点稍有不同。 目前，粗糙集理论的研究已渗透到模糊集理论、概率统计、神经网络、信息论、证 据理论及灰色系统理论等各个学科，并被广泛应用到机器学习、辅助决策、过程控制、 模式识别与数据挖掘等领域。 1 2 本文研究的意义与内容组织 1 2 1 本文研究的背景与意义 在日常现实生活中，我们大家都会接触和获得大量的信息，而这些信息其不确定性 是绝对的，其确定性只是相对的。之所以说信息是确定的，是因为我们在作出决策之前 都会权衡考虑，去除不确定因素，作出确定、正确的决策。而不确定的信息则会随着人 们认知的扩大逐渐转化为确定的信息。即信息的确定与否实质是一个认知程度和知识分 类能力的问题。 同样，在自然科学、社会科学和工程技术等很多领域中，也都不同程度地涉及到对 不确定因素和对不完备信息的处理。特别是进入信息时代后，产生和收集数据与信息能 力的大大提高，使得各个领域的数据与信息量剧增，同时由于客观条件的限制和人类的 主观参与，使得数据与信息的不精确、不确定、不完整和模糊性等问题更为突出，也更 加复杂。 1 9 8 2 年，由波兰学者z p a w l a k 提出来的粗糙集( r o u g hs e t ) 理论足一种处理不确 定性信息的有效工具，它将知识理解为人类对信息、数据的分类的能力，用等价关系对 空间进行划分，由于它在知识分类时不需要其它先验知识，比较客观公正，因而在处理 不确定性、不完备信息方面取得了前所未有的突破。 经过二十多年的发展，粗糙集理论已日渐成熟，并开始和模糊集理论、概率统计、 一一 第一章绪论 信息论、神经网络、证据理论等多学科融合，取得了重大的研究成果。但仔细分析其发 展历史和趋势，其研究方向主要集中在粗集的数学性质、属性的离散化、核与约简的求 取、粗集模型的拓广等方面，而对其至关重要的分类精度和边界方面的研究却非常少， 既使有也大多仅仅停留在简单的定性分析上。粗集对知识的分类本身是客观的，它无需 额外的先验信息，这也正是它最大的优点但由于边界域的存在，使得它的分类精度受 到限制，而要突破这种限制就必须真正认识、理解知识边界的成因，从根本上解决分类 精度不理想的问题。现今粗糙集和其它许多学科的相互渗透研究也已取得了非常多的成 果，如模糊粗糙集的研究，变精度粗糙集的研究，灰色系统理论与粗糙集的结合研究等， 所有这些成果都为我们进行粗糙集的边界处理和近似精度分析提供了可能。 1 2 2 本文的主要工作与结构安排 粗糙集理论是一种处理不完备、不确定性信息的新的数学工具，它建立在分类机制 的基础上，它在处理数据对是比较客观、公正的，但由于边界域的存在，使得分类耩度 降低，难以得到确定的规则。因此，本文主要围绕粗糙集的边界问题，通过引入内外边 界及内外近似精确集的思想，结合模糊集理论、变精度理论、集对分析理论、灰色系统 理论等对粗集分类的边界及近似精度进行了系统的分析，提出了几种切实可行的近似精 确集模型和方法，对提高粗糙集分类精度做了一定的研究。 本文主要工作如下： ( 1 ) 结合内外边界的思想，提出了r 近似精确集和 叫。类近似精确集的概念，并定 义了相对近似精确集和绝对近似精确集两种尺近似精确集。 f 2 ) 针对粗糙集边界域在不同粒度下的情况，创新性地提出了粒化条件一f 的边界求 和法及边界积分法，并举例说明其具体算法。 ( 3 1 在借鉴王清印等人模糊灰集定义的基础上提出了边界模糊灰集和边界模糊灰数 的概念，并用正面信息区间隶属度和反面信息区间隶属度来描述边界模糊灰数，给出了 边界白化处理的方法。 ( 4 ) 在模糊粗糙集中引入了粗隶属度的概念，建立了依参数a 、日双参数的上下近 似集双阈值模糊粗糙集模型，及依单参数y 的单阈值模糊粗糙集模型，并结合实例具体 说明在a 、b 双参数近似集模型和y 单参数近似集模型下粗集分类的近似精度及近似精 度与n 、b 、y 参数的变化关系。 ( 5 ) 在z i a r k o 提出的变精度粗集模型基础上通过引入多数包含关系。建立了新的 第章绪论 变精度近似集模型，分析了分类精度与多数包含度b 的关系，给出了根据分类精度要求 ( 精度阈值口，) 确定b 取值范围的算法。 ( 6 ) 将变精度粗糙集与模糊粗糙集融合在一起，引入基于多数包含度的变精度模糊 粗糙集模型，结合实例介绍了具体算法。 ( 7 ) 在借鉴赵克勤的集对分析理论基础上，分别提出了基于同一度、对立度下的一 般意义下的集对相似关系，建立了n 、b 、7 三参数控制下的普通变精度集对粗集模型； 在计算各属性的客观权重的基础上重新构建新的加权条件下的集对相似关系，建立了属 性权重分配下的加权变精度集对粗集模型。 本论文共由五部分组成： 第一章介绍了粗糙集理论的发展历史和现状，本文的研究背景与意义，论文的主 要内容提与结构安排； 第二章本章主要介绍了粗糙集理论和灰色系统理论的基本知识，并提出了粗集分 类的精度问题，即近似精确问题： 第三章重点对粗糙集的边界域进行了系统的分析，将边界域分为内边界和外边界， 针对内外边界各自的特点，分别定义了相对近似内( 外) 精确集和绝对近似内( 外) 精 确集两种近似精确集，并提出了边界元素的粒化归类、边界模糊灰集及其白化处理法两 种边界元素处理方法。 第四章本章主要围绕粗糙集的边界问题就如何提高粗集分类的近似精度，分别将 粗糙集理论与模糊集理论、变精度理论、集对分析理论等多种处理不确定性知识的理论 结合，梅建了粗隶属度模型、基于多数包含的变精度粗集模型、变精度模糊粗糙集模型、 基于集对关系的变精度近似集模型，并详细分析了它们在提高分类精度方面的作用。 第五章对本文研究工作进行了总结，并提出了下一步研究方向。 4 第二章粗糙集与灰色系统基本理论 第二章粗糙集与灰色系统基本理论 2 1 粗糙集” 2 j ”1 的基本知识 2 1 1 知识与知识库 假设u a 是我们感兴趣的对象组成的有限集合，称为论域。任何子集x u ，称 为u 中的一个概念或范畴。为了规范化，我们认为空集也是一个概念。u 中的任何概念 族称为关于u 的抽象知识，简称知识。对于i ，f ，j = l ，2 ，门，如果 z u ，五0 ，置n ，= g ，且u l 鼍= u ，则定义l 壬，= x ，：，x 。 为u 上的一个划 分。 u 上的一族划分称为关于u 的一个知识库( k n o w l e d g eb a s e ) 。 假设月为u 上的一个等价关系，u r 表示r 的所有等价类( 或是u 上的分类) 构 成的集合， 工】。表示包含元素ze u 的月等价类。一个知识库就是一个关系系统 k = ( u ，r ) ，其中u 为非空有限集，称为论域，r 是u 上的一族等价关系。 若p r ，且p o ，则n p ( p 中所有等价关系的交集) 也是一个等价关系，称之 为p 上的不可分辩( i n d i s c e r n i b i l i t y ) 关系，记为i n d ( p ) ，且有： 工k 2 肼石 一 这样，u i n d ( p ) ( 既等价关系i n d ( p ) 的所有等价类) 表示与等价关系族p 相关的知识， 称为臣中关于u 的p 基本知识( p 基本集) 。为了简单起见，我们用u p 代替u i n d ( p ) ， i n d ( p ) 的等价类称为知识p 的基本概念或基本范畴。特别地，q r ，则称q 为k 中关 于u 的q 基本知识，q 的等价类为知识r 的q 初等概念或q 初等范畴。 事实上，p 基本范畴是拥有知识p 的论域的基本特性，换句话说，他们是知识的基 本模块。同样，我们可以定义：当k = ( u ，r ) 为一个知识库，i n d ( k ) 定义为k 中所有等 价关系的族，记做：i n d ( k ) = i n d ( p ) 1 a p e r 。 下面讨论两个知识库之间的关系。 设k = ( u ，p ) 与k = ，q ) 为两个知识库。如果i n d ( p ) = i n d ( q ) ，即u p = u q ， 则称知识库k 和k7 ( p 和q ) 是等价的，记作k = k ( 尸= q ) 。因此，当k 和k 有同样 的基本范畴时，知识库k 和k 中的知识都能使我们确切地表达关于论域的完全相同的 事实。这个概念意味着可以用不同的属性集对对象进行描述，以表达关于论域的完全相 5 第二章粗糙集与灰色系统基本理论 同的事实。 对于k 和k 两个知识库，当i n d ( p ) 匕i n d ( q ) 时，我们称知识p ( 知识库k ) 比知 识q ( 知识库k ) 更精细，或者说q 比p 粗糙。当p 比q 更精细时，我们也称p 为q 的 特化，q 为p 的泛化。 2 1 2 不精确范畴，近似与粗糙集 令z u ，且r 为一等价关系。当x 能表达成某些r 基本范畴的并时，称x 是r 可定义的，否则x 为r 不可定义的。 r 可定义集是论域的子集，它可在知识库k 中被精确的定义，而r 不可定义集不能 在这个知识库中被定义。r 可定义集也称为r 精确集，而r 不可定义集也称为r 非精确 集或r 粗糙集( r o u g hs e t ) 。 当存在等价关系r i n d ( k ) 且x 为尺精确集时，集合x u 称为k 中的精确集： 当对于任何r i n d ( k ) ，x 为月粗糙集，则称为k 中的粗糙集。 粗糙集可以近似地定义，通常使用两个精确集，即粗糙集的上近似( u p p e r a p p r o x i m a t i o n ) 和下近似( 1 0 w e ra p p r o x i m a t i o n ) 来描述。 给定知识库k = ( u ，r ) ，对于每个子集石u 和一个等价关系r i n d ( k ) ，定义两 个子集： 堡= u y u r i y 至x = x u | x 。董x r x = u r u r i y n x 彩 = x u | 工 r n x a ) 分别称为x 的只下近似集和r 上近似集。 边界域 钿 ( x ) = r x 一 正域p o s 。( x ) = 墼 负域n e g 。( x ) = u r x 垦x 或p o s 。( x ) 是由那些根据知识r 判断肯定属于的u 中的元素组成的集合；r x 是那些根据知识r 判断可能属于x 的u 中的元素组成的集合：b n 。( ) 是那些根据知识 r 既不能判断肯定属于x 又不能判断肯定属于x 的u 中的元素组成的集合；n e g 。( ) 是由那些根据知识r 判断肯定不属于肖的u 中的元素组成的集合。 从近似的定义，可得下列性质： 定理2 1 第二章相糙集与灰色系统基本理论 ( 1 ) z 为尺可定义集当且仅当麒= r x ； ( 2 ) z 为月的粗糙集当且仅当r x 。 也可将型描述为x 中的最大可定义集，将r x 描述为含有石的最小可定义集。 定理2 2 ( 1 ) x 尼x ( 2 ) 聊= r o = a ，= r u = u ( 3 ) r ( x u y ) = r ( x ) u r 0 ) ( 4 ) 塞( n 均= 星( x ) n 垦( ) ( 5 ) z y j r x 一r y ( 6 ) z y = r x r y ( 7 ) 星( x u y ) 星x u 旦】， ( s ) r ( x n y ) r x n r y ( 9 ) 墨卜爿) = i x ( 1 0 ) r ( x ) = 星x ( 1 1 ) 垦( 型x ) ) = 尺( 星( x ) ) = 宣( x ) ( 12 ) r ( r ( x ) ) = 星( 尺( 石) ) = r ( x ) 2 1 。2 。1 近似和成员关系 集合近似的概念导致了一个新的概念：成员关系。对一个集合的定义是与集合的知 识相联系的，所以成员关系也一定和知识有关，可以形式地定义为： 当且仅当x 星( x ) ，称爿是r 的下成员关系，记作x 至 x ； 当且仅当z e 足( 工) ，称x 是月的上成员关系，记作x r x 。 这里曼。表示根据r ，工肯定属于凰e r 表示根据r ，x 可能属于x 。 成员关系也都依赖于知识，即一个对象是否属于一个集合依赖于知识，并且这不是 绝对特性。 2 1 2 2 粗糙集的分类精度 集合( 范畴) 的不确定性是由于边界域的存在而引起的。集合的边界域越大，其精 确性越低。为更准确地表达这一点，引入精度的概念。由等价关系r 定义的集合鼻的近 似精度为： 以班嗣 第二章粗糙集与灰色系统基本理论 其中x o ，l 工i 表示该集合z 的基数。 精度口。( x ) 用来反映我们对于了解集合x 的知识的完全程度。显然，对于每一个r 且x 至u 有0 ( x ) 1 。当( ) = l 时，x 的r 边界域为空集，集合工为r 可定义 的；当d 。( x ) l 时，集合x 有非空r 边界域，该集合爿为尺不可定义的。 x 的r 粗糙度p 。( z ) 定义： 胁( ) = l a r ( x ) x 的粗糙度与精度恰恰相反，它表示的是集合x 的知识的不完全程度。 从以上计算公式我们可以看出，与概率论和模糊集合论不同，不精确性的数值不是 事先假定的，而是通过表达知识不精确性的概念近似计算得到的，这样不精确性的数值 表示的是有限知识( 对象分类能力) 的结果，我们不需要用一个机构来指定精确的数值 去表达不精确的知识，而是采用量化概念( 分类) 来处理。不精确的数值用来表示概念 的精确度。 除了用数值( 近似程度的精度) 来表示粗糙集的特征外，也可采用拓扑特征来定义 四种不同的重要粗糙集： ( 1 ) 如果丛o 且r x u ，则称x 为尺粗糙可定义。 ( 2 ) 如果r x = o 且r x u ，则称x 为r 内不可定义。 ( 3 ) 如果尺x o 且砝= u ，则称x 为r 外不可定义。 ( 4 ) 如果丛= o 且r x = u ，则称为r 全不可定义。 几种划分的直观意义如下： 如集合工为r 粗糙可定义的，则意味着可以确定u 中某些元素是否属于z 或x ； 如z 为尺内不可定义的，则意味着可以确定u 中某些元素是否属于x ，但不能 确定u 中的任一元素是否属于墨 当x 为r 外不可定义的，则意味着可以确定 ，中某些元素是否属于z 但不能确 定u 中的任一元素是否属于x ； 当x 为r 全不可定义的，则不能确定【，中任一元素是否属于z 或x 。 下面我们给出集合拓扑划分的一个有用性质。 定理2 3 ( 1 ) 集合x 为月粗糙可定义( 或尺全巧i 可定义) 当且仅当x 为尺粗糙可定义( 或 r 全不可定义) ； 第二章粗糙集与灰色系统基本理论 ( 2 ) 集合x 为r 外( 内) 才i 可定义，当且仅当x 为r 内( 外) 不可定义。 至此我们已经介绍了两种刻画粗糙集的方法。其一是用近似程度的精度来表示粗糙 集的数字特征，另一种是用粗糙集的分类来表示粗糙集的拓扑特征。粗糙集的数字特征 表示了集合边界域的大小，但没有说明边界域的结构；而粗糙集的拓扑特征没有给出边 界域大小的信息，它提供的是边界域的结构。 此外，粗糙集的数字特征和粗糙集的拓扑特征间存在一种关系：首先，如果集合为 内不可定义或全不可定义，则其精度为0 ：其次，当集合为外不可定义或全不可定义， 则它的补集的精度为0 。这样即使知道了集合的精度，也不能确定它的拓扑结构；反过 来，集合的拓扑结构也不具备精度的信息。因此在粗糙集的实际应用中，需将边界域的 两种信息结合起来，既要考虑精度因素，也要考虑到集合的拓扑结构。 2 1 2 3 近似分类 令f = ，x ：，x 。) 是u 的一个分类或划分，且独立于知识r ：子集置( f = l ，2 ，n ) 是划分f 的类。f 的r 下近似和上近似分别定义为： 蟛= 路。，些2 ，垦x 。j ； 霹= 豇。砝：，砑。) 。 f 近似分类的精度： i 墨( 五) l_ i l 卜丽i = 1 、 l 一，l 一l 、l f 近似分类的质量： i 星( 1 ) ij i l 蜘k 卜气r 近似分类的精度描述的是当使用知识r 对对象分类时，可能的决策中正确决策的百 分比；分类的质量表示的是应用知识r 能确切地划入f 类的对象的百分比。 几种种近似相等的定义： 令k = ( u ，r ) 是一个知识库，x ，y u 且r i n d ( k ) ( 1 ) 若星x = 星j ，则称集合x 和y 为r 下粗相等，记作x ：。y ； ( 2 ) 若r x = r y 则称集合x 和y 为r 上粗相等，记作x = 。y ； 第二章粗糙集与灰色系统基本理论 ( 3 ) 若x = 】，且= 月y ，则称集合x 和y 为r 相等，记作x z 。y 。 2 1 3 知识约简 知识约简是粗糙集合理论的核心内容之一。众所周知，知识库中的知识并不是同等 重要的，甚至其中某些知识是冗余的。所谓的知识约简，就是在保持知识库分类能力不 变的条件下，删除其中不相关或不重要的知识。 2 1 3 1 约简和核 知识约简中有两个重要的基本概念：约简( r e d u c e ) 和核( c o 嘲。 令r 为一族等价关系，且r r ，如果i n d ( r ) = i n d ( r 一但) ) ，称r 为r 中不必要的， 否则r 为r 中必要的。 如果每一个r r 都为r 中必要的，则称r 为独立的；否则称r 为依赖的。 设q p ，如果q 是独立的，且i n d ( q ) = i n d ( e ) ，则称q 为p 的一个约简。显然，p 可以有多种约简。p 中所有必要关系组成的集合称为p 的核，记作c o r e ( p ) ，且有 c o r e ( p ) = n r e d ( p ) ，其中r e d ( p ) 表示的是p 的所有约简。 2 1 3 2 相对约简和相对核 令p 和q 为u 中的等价关系，q 的p 正域记为p o s ，( q ) ，即 p o s ，( q ) = u ( x ) e u ，口 q 的尸的正域是u 中所有根据u p 的分类信息可以准确地划分到q 的等价类中的去的 对象的集合。 同样令p 和q 为【，中的等价关系族，r p ，如果 p o s h j ( p ) ( 觑d ( q ) ) = p o 薯耐( p f 哪) ( f 胛d ( q ) ) 则称r 为p 中q 不必要的；否则r 为p 中q 必要的。 注：此处用p o s p ( q ) 代替卵s f p l ( 加c ，( q ) ) 。 如果p 中的每个r 都为q 必要的，则称p 为q 独立的( 或p 是相对于q 独立的) 。 设s p ，s 为p 的q 约简当且仅当s 是p 的q 独立子族目p o s s ( q ) = p o s ，( q ) 。p 的q 约 简简称为相对约简。 p 中所有q 必要的原始关系构成的集合称为po o q 核，简称相对核，记为c o r e o ( p ) ， 且有c d r e e ( p ) = n r e d q ( p ) ，其中m 如( p ) 是所有p 的q 约简构成的集合。 第二章粗糙集与狄色系统基本理论 2 1 4 知识的依赖性 令k = ( u ，r ) 是一个知识库，p ，q r ，知识的依赖性可以形式化的定义如下： ( 1 ) 知识q 依赖于知识p ( 记作p j q ) ，当且仅当i n d ( p ) i n d ( q ) ： ( 2 ) 知识q 与知识p 等价( 记作p ；q ) ，当且仅当p j q 且q j p ； ( 3 ) 知识q 与知识p 独立( 记作p q ) ，当且仅当p j q 与q j p 均不成立。 显然，p ；q 当且仅当i n d ( p ) = i n d ( q ) 。当知识q 依赖于知识p 时，我们也说知识q 是由知识p 导出的。 令k = ( u ，r ) 为一知识库，p ，q r 当 后= y a q ) = 峰掣 时，我们称知识qk ( o k 1 ) 度依赖于知识p 的，记为p 。q 。 当k = l 时，称q 完全依赖于p ；当0 k 1 时，称q 粗糙( 部分) 依赖于p ：当女= 0 时，称q 完全独立于p 。若p ；q ，也记为p j q 。系数k 可以看作q 和p 间的依赖 度。 2 1 5 知识表达系统 一个知识表达系统形式上可以用一个四元组s = ( u ，a ，v ，厂) 来表示，其中 队是对象的非空有限集合，称为论域； “：属性的非空有限集合； v = u 圪，圪是属性。的值域； f ：