（计算机应用技术专业论文）特性关系粗糙集中若干关键问题研究.pdf

西南交通大学硕士研究生学位论文第t 页 曼曼曼舅曼皇蔓皇曼舅蔓寰： i _ 一- -_ i i m m l _ i i i ! 曼曼曼曼曼曼皇曼皂曼皇曼量曼舅曼曼曼曼曼 摘要 经典粗糙集理论处理信息系统中的数据是精确的和不缺损的。如今面对日 益复杂和动态变化的数据，信息系统中的数据往往是不完备的，经典粗糙集理 论方法已经不能满足实际需求。然而特性关系粗糙集模型凭借其同时处理丢失 数据和不关心数据的优势，可为不完备信息系统中的数据挖掘技术的改进提供 了强有力的理论支撑。本文对特性关系粗糙集模型中若干关键问题进行了研 究。 首先，在特性关系粗糙集模型下讨论了基于区分矩阵、信息熵、粒度等知 识约简算法，并给出相关的实例来验证了算法的可行性；同时分别讨论了在特 性关系粗糙集模型下信息熵与知识粒度之间的关系和信息熵知识约简与粒度 知识约简的等价性。 其次，通常情况下，当信息系统动态变化时，对象的近似集会产生相应的 变化。本文只考虑信息系统属性值动态变化的情况。运用粒度的思想，给出了 不完备信息系统中属性值粗化细化的定义，讨论了在不完备信息系统下的特性 关系粗糙集模型中属性值粗化细化时近似集的增量更新方法，并通过实例验证 了该方法的有效性。 最后，通过将特性关系分别与容差关系、非对称相似关系的分析比较，发 现了特性关系也存在一些不足。由此本文给出了a 、b 和c 三种新型特性关系， 能较为有效地解决这些不足。并将特性关系与a 、b 和c 三种新型特性关系下 的近似集的变化范围进行了比较分析。同时给出相关的定理，再用实例验证了 定理的正确性。 关键词：粗糙集；不完备信息系统；特性关系；知识约简；增量更新 西南交通大学硕士研究生学位论文第1 i 页 a bs t r a c t t h ec l a s s i c a lr o u g hs e ti so n l yt od e a lw i t hd a t ai ni n f o r m a t i o ns y s t e m st h a ti s p r e c i s ea n dc o m p l e t e h o w e v e r ，i nt h er e a la p p l i c a t i o n s ，m a n yd a t as o u r c e sh a v e d y n a m i cc h a r a c t e r i s t i c s ，a n dt h ed a t ai nt h ei n f o r m a t i o ns y s t e m sc a nb ei n c o m p l e t e t h ec l a s s i c a lr o u g hs e tt h e o r yi sn ol o n g e rv a l i df o rd e a l i n gw i t ht h i sk i n do f p r a c t i c a lp r o b l e m s c h a r a c t e r i s t i cr e l a t i o nb a s e dr o u g hs e tm o d e lw h i c hc a nd e a l w i t hl o s ta n d “d on o tc a r e ”v a l u e sw a sp r o p o s e d i ts u p p o r t sk n o w l e d g ed i s c o v e r y f 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 i nt h i sp a p e r ，s e v e r a lk e yp r o b l e m su n d e r c h a r a c t e r i s t i cr e l a t i o nb a s e dr o u g hs e tm o d e la r ei n v e s t i g a t e d f i r s t l y , k n o w l e d g er e d u c t i o na l g o r i t h m sb a s e do nd i s c e r n i b i l i t ym a t r i x ， i n f o r m a t i o ne n t r o p ya n dg r a n u l a r i t y ，e t c ，a r ep r e s e n t e du n d e rt h ec h a r a c t e r i s t i c r e l a t i o n e x a m p l e sa r ee m p l o y e dt oi l l u s t r a t et h a tt h ev a l i d a t i o no f t h ea l g o r i t h m s a tt h es a m et i m e ，t h er e l a t i o no ft h ei n f o r m a t i o n e n t r o p ya n dk n o w l e d g e g r a n u l a r i t yi sd i s c u s s e d ，a n dt h ee q u i v a l e n c eo fk n o w l e d g er e d u c t i o nw i t hr e s p e c t 1 ：oi n t o r m a t i o ne n t r o p ya n d g r a n u l a r i t yi sp r o v e d s e c o n d l y , t h ea p p r o x i m a t i o n so fc o n c e p t sm a yv a r yw h e nt h ei n f o r m a t i o n s y s t e mi sd y n a m i c a l l yc h a n g i n g t h i sp a p e ro n l yc o n s i d e r st h e s i t u a t i o nt h a t a t t r i b u t ev a l u ed y n a m i c a l l yc h a n g ei nt h ei n f o r m a t i o ns y s t e m a c c o r d i n gt ot h e i d e ao ft h eg r a n u l a r i t y ，t h ed e f i n i t i o n so fa t t r i b u t ev a l u e sc o a r s e n i n ga n dr e f i n i n g i 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 sa r eg i v e n t h e na p p r o a c h e sf o ru p d a t i n gt h e a p p r o x i m a t i o n sa r ed i s c u s s e dw h e na t t r i b u t ev a l u e sc o a r s e n i n ga n dr e f i n i n gu n d e r t h ec h a r a c t e r i s t i cr e l a t i o n f i n a l l y ，e x a m p l e sa r eg i v e nt oi l l u s t r a t et h ev a l i d i t yo f t h ep r o p o s e da p p r o a c h e s f i n a l l y ，t h r o u g ha n a l y z i n g a n dc o m p a r i n gt h ec h a r a c t e r i s t i c r e l a t i o n ， t o l e r a n c er e l a t i o na n dn o n s y m m e t r i c a ls i m i l a r i t yr e l a t i o n ，w ef i n dt h a tt h e r ea r e s o m es h o r t c o m i n g si nt h ec h a r a c t e r i s t i cr e l a t i o n i no r d e rt os o l v et h e s ep r o b l e m s e f f e c t i v e l y ，t h r e en e wc h a r a c t e r i s t i cr e l a t i o n s ：a ，ba n dcc h a r a c t e r i s t i cr e l a t i o n s a r ep r e s e n t e d t h i sp a p e rf u r t h e rd i s c u s s e st h ev a r i a t i o no ft h ea p p r o x i m a t i o n s u n d e ra ，ba n dcc h a r a c t e r i s t i cr e l a t i o n s a tt h es a m et i m e ，s e v e r a lt h e o r e m sa r e g i v e na n ds e v e r a le x a m p l e sa r ee m p l o y e dt oi l l u s t r a t et h et h e o r e m s 西南交通大学硕士研究生学位论文第1 i i 页 k e yw o r d s ：r o u g hs e t ；i n c o m p l e t e i n f o r m a t i o n s y s t e m ；c h a r a c t e r i s t i c r e l a t i o n ；k n o w l e d g er e d u c t i o n ；i n c r e m e n t a lu p d a t i n g 西南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权西南交通大学可以将本论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复印手段保存和汇编本学位论文。 本学位论文属于 1 保密口，在年解密后适用本授权书； 2 不保密日，使用本授权书。 ( 请在以上方框内打“、尸) 学位论文作者虢叫伟氓 指捌币虢 日期：沙i 啤石同日 务白 j 西南交通大学硕士学位论文主要工作( 贡献) 声明 本人在学位论文中所做的主要工作或贡献如下： ( 1 ) 讨论了在特性关系粗糙集模型下信息熵与知识粒度之间的关系和信息 熵知识约简与粒度知识约简的等价性； ( 2 ) 运用粒度的思想，讨论属性值粗化细化时近似集的增量更新方法。并 通过实例验证了该方法的有效性； ( 3 ) 给出了三种新型的特性关系和相关的定理，并用实例验证了定理的正 确性。 本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工作所 得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体 已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中作了明确说明。本人完全了解违反上述声明所引起的一切法律责任将由本 人承担。 学位论文储繇叫档夼 1 3 期：加f 口笔铜f 日 西南交通大学硕士研究生学位论文第1 页 第1 章绪论 1 1 论文的研究意义与目的 粗糙集理论( r o u g hs e tt h e o r y ) 是由波兰科学家p a w l a k 于上世纪八十年 代初提出的一种处理含糊和不精确性问题的新型数学工具【l2 1 。近年来，为了 适应实际工程应用的需求，已有许多学者提出了各种各样的粗糙集模型，如可 变精度粗糙集【”、概率粗糙集 4 1 、模糊粗糙集【5 1 等，其中不完备信息系统【6 789 】 ( 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 ，简称i i s ) 中各种拓展粗糙集模型的应用己 成为粗糙集理论发展的一个重要方面。对于i i s 而言，数据的缺省可能是由两 种原因造成的：一是在某种特殊的环节丢失的数据，比如在数据录入中遗漏的 数据、因误操作而删除的数据，称这种缺省数据为丢失数据，用“? ”表示。 因此，s t e f a n o w s k i 7 】等人构建了其中的相似关系( 满足自反、传递性) 并建立 了近似集的概念来处理这种丢失数据。二是缺省数据对信息系统而言是不相关 或不重要的数据，将其删除不会影响最终结果，称这种缺省数据为不关心数据， 用“术 表示。因此，k r y s z k i e w i c z t6 】提出了i i s 中的容差关系( 满足自反、对 称性) ，并运用容差关系来处理这种数据。但是，当i i s 同时存在丢失数据和 不关心数据的时候，相似关系和容差关系就不能解决这个问题。因此， g r z y m a l a b u s s e 就考虑了一种广义的i i s ，其中的未知属性值既有丢失型的， 又有不关心型的。为了使用粗糙集理论处理这种同时具有丢失型和不关心型的 未知属性值的i i s ，g r z y m a l a b u s s e 提出了特性关系【1 01 1 】( c h a r a c t e r i s t i c r e l a t i o n ) ，特性关系是结合相似关系和容差关系的一种推广形式，仅满足自反 性。 基于经典粗糙集理论处理信息系统中的数据是精确的和不缺损的，即它不 包含对原始不完全数据的处理。如今面对日益复杂和动态变化的数据，经典粗 糙集理论方法已经不能满足实际需求。然而特性关系粗糙集模型凭借其同时处 理丢失数据和不关心数据的优势，可为i i s 中的数据挖掘技术的改进提供了强 有力的理论支撑，有望实现从i i s 中进行高效动态获取规则。本文研究的目的 是：首先讨论如何利用特性关系粗糙集模型来探讨特性关系的知识约简方法， 再讨论了特性关系下属性值粗化细化时近似集增量更新等问题，最后根据 g r z y m a l a , b u s s e 提出的特性关系存在的不足，提出了改进的特性关系。这都可 西南交通大学硕士研究生学位论文第2 页 充分体现特性关系粗糙集理论在处理不确定性问题的优势，并完善粗糙集的理 论与方法，同时对拓展粗糙集的应用等领域有十分重要的意义。 1 2 国内外研究现状 本文涉及到经典粗糙集理论、特性关系粗糙集模型等相关领域知识，下面 简要概述经典粗糙集理论和特性关系粗糙集模型的研究现状。 1 2 1 经典粗糙集理论研究现状 2 0 世纪8 0 年代，许多波兰学者对粗糙集理论及其应用进行了坚持不懈的深 入研究，其中主要是对粗糙集理论的数学性质与逻辑系统进行了广泛的分析。 当时大多数研究成果发表在“b u l l e t i no ft h ep o l i s ha c a d e m i co fs c i e n c e ： m a t h e m a t i c s ”和“b u l l e t i no ft h ep o l i s ha c a d e m i co fs c i e n c e ：t e c h n i c a ls c i e n c e ” 上；同时，他们也开发了一些应用系统。但还没有引起人们的普遍关注。直到 19 9 1 年，p a w l a k 的专著粗糙集一关于数据推理的理论【1 2 】系统全面的阐述 了粗糙集理论，奠定了严密的数学基础。粗糙集理论才得到了学术界的认可。 19 9 2 年s l o w i n s k i 主编的关于“粗糙集应用及其相关方法比较研究的论文集 【13 】较好地总结了这一时期该理论的研究成果，进一步推动了国际上对粗糙集理 论与应用的深入研究。 19 9 2 年在波兰k i e k r z 召开了“第一届国际粗糙集研讨会 1 14 1 。这次会议 着重讨论了集合近似定义的基本思想及其应用。虽然参加这次会议的研究者较 少，范围也不太广泛。但是这次会议选出15 篇论文被刊登在“f o u n d a t i o no f c o m p u t i n ga n dd e c i s i o ns c i e n c e s ”1 9 9 3 年第1 8 卷上，对推动粗糙集的研究起到 了积极的作用。自此以后，每年都召开有以粗糙集为主题的国际会议。 19 9 3 年在加拿大b a n f f 召开了“第二届国际粗糙集与知识发现研讨会 ( r s k d 9 3 ) 1 5j 。这次会议极大地推动了国际上对粗糙集理论与应用的研究， 其主题是粗糙集、模糊集与知识发现。由于此时k d d 正成为研究的热门话题， 一些著名k d d 学者参加了这次会议，并且介绍了许多基于扩展的粗糙集理论 的知识发现方法与系统。 19 9 4 年在美国s a nj o s e 召开了“第三届国际粗糙集与软计算研讨会”【l6 | ， 这次会议广泛地探讨了粗糙集与模糊逻辑、神经网络、进化理论等的融合问题。 19 9 5 年粗糙集理论及应用的几位主要倡导者在第1 1 期a c m 通讯上撰文 f j ，概括地介绍了目前人工智能应用技术之一一一粗糙集理论的基本概念，及 其在知识获取和机器学习、决策分析、知识发现等领域的具体研究项目和进展。 西南交通大学硕士研究生学位论文第3 页 特别值得一提的是19 9 5 年召开的“第四届模糊理论与技术国际研讨会( f u z z y t h e o r y & t e c h n o l o g y 9 5 ) 。在这次会议上，针对粗糙集与模糊集的基本观 点与相互关系展开了激烈的讨论，较大地促进了粗糙集的研究。 19 9 6 年在日本t o k y o 召开了“第五届国际粗糙集研讨会”。这是第一次在 亚洲地区召开的范围广泛的粗糙集研讨会，极大地推动了亚洲地区对粗糙集理 论与应用的研究。 19 9 8 年在波兰召开以“第一届粗糙集和计算的当前趋势 为主题的学术会 议。之后每隔两年开一次【l 引。 19 9 9 年1 1 月在日本召开“第七届粗糙集、模糊集和粒度软计算的国际学 术研讨会( r s f d g r c 9 9 ) ，阐述了当前粗糙集、模糊集的研究现状和发展 趋势，指出将着重在软计算、数据库、a i 和近似推理等理论和应用方面发展。 2 0 0 3 年在重庆举办了“第9 届粗糙集、模糊集、数据挖掘和粒度一软计算的 国际会议 。这次首次在中国举办有关粗糙集的国际会议。而且，2 0 0 3 年11 月2 1 日中国人工智能学会粗糙集与软计算专业委员会( r o u g hs e tt h e o r ya n d s o f tc o m p u t a t i o ns o c i e t y ，c h i n e s ea s s o c i a t i o no fa r t i f i c i a li n t e l l i g e n c e ) 在广州 正式成立，极大地推动了我国粗糙集理论研究。 2 0 0 4 年国际粗糙集协会出版发行第一本粗糙集国际期刊a d v a n c e si n r o u g hs e t ) ) ，为推动粗糙集在全世界的发展作出了重要贡献。随后每年都出 版1 。2 期粗糙集国际期刊，到2 0 0 9 年已出版了l0 期。 2 0 0 5 年1 2 月4 日国际粗糙集学会成立，国际粗糙集学会是一家非营利性 学术组织。该协会主要目的是促进粗糙集理论基础、方法和应用研究。 2 0 0 6 年在重庆召开了由国际粗糙学会、中国人工智能学会粗糙集与软计算 专业委员会“第一届粗糙集与知识技术国际学术会议( r s k t 2 0 0 6 ) 。标志 着一个新的系列性国际学术会议将在中国诞生，将是中国为人类社会由信息技 术时代过渡到知识技术时代的一个重要贡献。“第二届粗糙集与知识技术国际 学术会议( r s k t 2 0 0 7 ) 于2 0 0 7 年在加拿大多伦多召开。2 0 0 8 年在四川成都 召开了由西南交通大学主办和若干国际组织包括国际粗糙集学会，国际电气和 电子工程师协会成都分部以及中国人工智能学会粗糙集与软计算专业委员会 等协办的“第三届粗糙集与知识技术国际学术会议( r s k t 2 0 0 8 ) ”。2 0 0 9 年 在澳大利亚召开了“第四届粗糙集与知识技术国际学术会议( r s k t 2 0 0 9 ) 。 “第五届粗糙集与知识技术国际学术会议( r s k t 2 0 10 ) 将于2 0 10 年在北京 召开。 我国是从2 0 0 1 年开始召开以粗糙集为主题的全国会议。是在重庆召开了 “第一届中国r o u g h 集与软计算学术研究会，【”】。会议邀请了创始人p a w l a k 教 西南交通大学硕士研究生学位论文第4 页 授做大会报告。之后分别在苏州、重庆、舟山、鞍山、金华、太原、石家庄召 开了由中国人工智能学会粗糙集与软计算专业委员会和中国计算机学会人工 智能与模式识别专业委员会联合主办的中国r o u g h 集与软计算系列全国学术 会议，具有较大的影响。极大地推动了我国在粗糙集理论、方法与应用上的研 究。 目前，在许多关于人工智能、模糊理论、信息管理与知识发现等国际学术 会议上经常可以看到许多涉及粗糙集的论文。在国内的计算机核心刊物和会议 上，也不时出现涉及粗糙集的论文。此外，也有不少有关粗糙集的专著 【2 1 【2 2 【2 3 2 4 】 2 5 】。 1 2 2 特- l 生关系粗糙集理论研究现状 国内外许多学者针对不完备信息展开了深入的研究，为利用不完备数据解 决实际问题提供了许多方法。主要集中在不完备信息表的粗糙集模型扩展等方 面，如文献 101 12 62 7 。下面主要讨论特性关系粗糙集理论在国内外的发展 情况。 2 0 0 5 年g r z y m a l a b u s s e 首次提出了特性关系的概念，并讨论了特性关系 下的三种近似( 单一、子集、概念) 【lu ；同时也提出了特性关系粗糙集模型下 属性值缺省时不可区分关系的泛化【10 1 。同年，他还提出了特性关系粗糙集在数 据挖掘方面的一些应用【2 8 2 9 1 。 2 0 0 6 年g r z y m a l a b u s s e 首先区分了两种属性值的缺省，再引入了局部和 整体的概念来计算特性关系粗糙集的上下近似，局部近似比整体近似要要精 确，整体下近似可以用p o l y n o m i a l 算法来定义，但算法要同时找到局部近似和 整体上近似却是n p 问题 3 0 , 3 1 】。 2 0 0 7 年g r z y m a l a b u s s e 提出了使用属性值的微积分方法挖掘数值型数据 【32 1 。同年，他又提出使用属性值计算的方法来挖掘数据型数据，并提出了 m l e m 2 算法。该算法不仅适用完备的数据，也可应用到特性关系粗糙集中 【3 3 ，3 4 】 o 2 0 0 7 年l i 等提出了基于特性关系粗糙集模型的增量更新概念近似集的方 法，并与直接计算近似集的方法进行了比较，实验结果验证了所提出方法的优 越性【”】。同时l i 等又实现了特性关系粗糙集模型框架下多个属性同时增删时 规则提取方法【3 6 】。 2 0 0 8 年s o n g 和l i 等提出了基于云变换和特性关系粗糙集模型下的决策树 构造方法( d t c c r s c r ) 。他们运用云变换来处理连续属性数据，将在特性关 西南交通大学硕士研究生学位论文第5 页 曼。 - - 一一m m m m m m m 一 一 i i 鼍曼皇曼皇 系粗糙集下具有最小加权粗糙度的属性作为当前分枝结点。实验表明运用 d t c c r s c r 方法构造的决策树在大多数实例中比c5 o 有更简单的结构、更高 的分类精度、规则也较好理解【4 引。 2 0 0 8 年g r z y m a l a b u s s e 基于属性概念值的思想，在特性关系粗糙集模型 下提出了三种处理处理缺省属性值的方法【4 1 1 。 2 0 0 9 年g r z y m a l a b u s s e 在特性关系粗糙集模型下，根据近似空间，给出 了新的定义；对于处理不完备数据最好的选择是利用局部最优逼近方法。即下 近似尽可能的大，下近似近可能的小p2 i 。 由上可以看出，对特性关系粗糙集模型的研究是相对较少的，对基于特性 关系粗糙集模型属性值粒度变化下知识增量更新等问题研究还没有相关报道， 因此研究基于特性关系粗糙集模型的相关数据挖掘理论与方法具有重要意义。 1 3 论文主要研究内容 本论文选题是国家自然科学基金项目基于粒计算的动态知识发现中若干 关键问题研究( 编号：6 0 8 7 3 1 0 8 ) 中的部分研究内容。论文主要研究不完备 信息系统下基于特性关系粗糙集模型拓展和动态知识发现方法等。 首先，在特性关系粗糙集模型下分别讨论了信息熵与知识粒度之间的关系 和信息熵知识约简与粒度知识约简的等价性。 其次，运用粒度的思想，讨论了特性关系粗糙集模型中属性值粗化细化时 近似集的增量更新方法，并通过实例验证了该方法的有效性。 最后，将特性关系与容差关系，非对称相似关系进行了比较分析，发现 g r z y m a l a b u s s e 提出的特性关系也存在不足。由此给出了三种新型的特性关系 来解决所存在的不足。 西南交通大学硕士研究生学位论文第6 页 1 4 论文结构 1 5 本章小结 图1 i 论文结构图 本章主要介绍了论文的研究目的与意义，经典粗糙集理论研究现状和特性 关系粗糙集理论研究现状，论文主要研究内容和论文结构。 西南交通大学硕士研究生学位论文第7 页 曼曼皇曼曼舅舅皇曼曼鼍曼曼曼曼皇曼曼孽鼍曼蔓孽皇i 一i i i ii i i i i i i 量皇皇曼曼曼曼曼鼍曼曼曼曼 2 1 经典粗糙集理论 第2 章预备知识 粗糙集的研究对象主要是信息系统，首先介绍信息系统的一般概念。 定义2 1 1 2 3 l 四元组s = ( u ，a ，v ，厂) 称为一个信息系统，其中u 是表示对象的 非空有限集合称为论域；4 是表示属性的非空有限集合，y 表示属性域集合， 圪表示属性a 的值域；f ：u xa v 表示的一个信息函数，它为每个对象在每个 属性上赋予一个信息值，即圪a ，x eu ，f ( x ，a ) e 圪。若存在一个x u ，a ec ， f ( x ，a ) 未知( f ( x ，a ) = 水) ，则称该信息系统是不完备的；否则称该信息系统是完 备的。 2 1 1 粗糙集理论的基础知识 定义2 2 1 设r 是论域【，上的一个等价关系，= 五，k ，兄) 是对论域 r 的一个划分，称为u 上的一个知识。【x 】r = y u lx r y ) 表示关系r 下元素x 的 等价类。 定义2 3 1 2 3 i 若p r ，且尸矽，则p 中全部等价关系的交集称为尸上的不 可分辨关系，记为1 n d ( p ) ： i n d ( p ) = ( x ，y ) i x eu ，y u ，v a p ，f ( x ，口) = 厂( y ，口) ) ( 2 1 ) 称为尸基本集合，它实际上是由论域中关于p 不可分辨的对象组成的 集合，是组成知识的颗粒。若qcp ，n d ( q ) 的等价类称为知识p 的初等范畴。 由q 定义的等价类称为尸初等集合，它是论域中所有具有特定属性的对象构成 的子集。一些初等范畴的交集构成基本范畴。 定义2 4 1 2 3 i 令x u ，r 是论域u 上的一个等价关系，当x 是尺的某些等 价类的并时，称x 是r 可定义的，否则称x 是尺不可定义的。r 可定义集称为 r 精确集，尺不可定义集称为尺粗糙集。 定义2 5 。2 3 1 包含x 中的最大可定义集称为x 的r 下近似，记为r ( x 1 ： r ( x ) - - x u i 【 rc x 】 ( 2 - 2 ) 塑室茎璺銮耋至圭窑耋兰三墨耋圣兰：蚕 包含片的最小可定义集称为x 的r 上近似，记为页f 丑1 i ( ) = 恤u 。n x ；o 】 的边界域记为b n 以： b n 心= r ( x ) - r ( x ) 2 3 ) 2 4 ) 丑( _ j ) 表示在知识r 下u 中所有一定能归入z 的元素集合，r ( x ) 表示在知 识r 下u 中可能归入x 的元素集合，口峨( x ) 表示在知识r 下u 中既不能肯定 归八五，也不能不肯定归八爿的元素集合，如图1 所示，其中网格代表u 关于r 的知识颗粒。当r ( x ) = 旦( 互) 时，称j 关于r 是精确的。当r ( x ) 旦( ) 时，称 关于r 是粗糙的，这时用集合对( 旦( ) ，再啤) ) 来近似表示。 目2 1 粗碴集的近似目下近似 为了准确刻画粗糙近似对概念的逼近程度，下面给出近似精度的定义。 定义2 6 川令x u ，0 ，r 是论域u 上的一个等价关系，工关于r 的 近似精度定义为：坼( x ) = 糌，其中h 表示集合中元素的数目，称为集合的 基数或势。 与近似精度相对应的是粗糙度的概念。 定义2 7 j 2 ”x 关于r 的耜糙度定义为： 西南交通大学硕士研究生学位论文第9 页 ( x ) = l 一( x ) ( 2 5 ) 如果风( x ) = o ，则集合x 关于r 是精确的；如果风( x ) 0 ，则集合x 关 于r 是粗糙的。粗糙度瓜( x ) 描述了粗糙集的不精确程度。 2 1 2 属性约简与核 基于粗糙集的知识获取，主要是通过对原始决策表的约简，即在保持决策 表的决策属性和条件属性之间的依赖关系不发生变化的前提下对决策表进行 约简。在讨论决策表信息系统约简的时候，决策表中所有条件属性形成条件属 性集合c 对论域u 的划分为。同时，决策属性集d = d ) 也对论域u 形成一 个划分为。这两个划分形成了条件属性和决策属性在对论域样本分类上的 知识。属性约简的目标就是要从条件属性集合中发现部分必要的条件属性，使 得根据这部分条件属性形成的相对于决策属性的分类和所有条件属性所形成 的相对于决策属性的分类一致，即和所有条件属性相对于决策属性d 有相同的 分类能力。 定义2 8 1 2 4 i 设有决策系统s = ( u ，a = c u d ，v ，f ) ，其中c ，d 分别代表条件 性集和决策属性集，则d 的c 正域p o s c ( d ) 定义为： p o s e ( d ) = u 鱼( x ) ( 2 6 ) x 定义2 9 t 2 4 i设有决策系 统 s = ( u ，a = c u d ，v ，厂) ， 若 e o s c ( o ) = c o s e c _ ) ( d ) ，则称，为c 中相对于d 可省略的，简称d 可省略的； 否则，称，为d 不可省略的。 定义2 1 0 1 2 4 1 设有决策系统s - - ( v ，a = c u d ，v ，厂) ，条件属性c 相对于决策 属性d 的约简是c 的一个非空子集p ，若它满足： ( 1 ) v a p ，q 都是d 不可省略的； ( 2 ) p o s e ( d ) = p o s c ( d ) 。 则称尸是c 的一个约简，c 中所有约简的集合，记作r e d z ，( c ) 。 定义2 1 1 1 c 中所有约简的交集f i r e d d ( c ) 称为c 的核，记为： c o r e o ( c ) 。 决策表的属性约简是指条件属性集中相对于决策属性集的最小不可省略 集，而属性的核则是约简集中最重要的部分，属性的核可以是空集。 西南交通大学硕士研究生学位论文第10 页 曼曼曼曼量鼍曼曼曼舅舅m l ；m ； = - - 璺曼皇皇曼皇曼皇曼舅曼蔓曼曼曼鼍曼菖曼皇曼曼皇皇曼曼曼舅曼曼! 曼皇笪曼曼 2 1 3 属性的重要性 定义2 1 2 2 3 1 设有决策系统s = ( u ，a 二c ud ，v ，f ) ，决策属性d 对条件属性 c 的依赖度心( d ) 定义为： p c ( o ) = 掣 ( 2 7 ) 段( d ) 表示在条件属性c 下能够确切划入决策分类2 的对象占论域中总 的对象数的比率，表达了决策属性对条件属性的依赖程度。 定义2 1 3 2 3 1 设有决策系统s = ( u ，a = c ud ，矿，f ) ，qec 的属性重要性定义 为： q c ，d ) ( g ) = 半趔= 1 一错 ( 2 _ 8 ) 为： q c ，功( g ) 可以理解为去除属性g 后所发生的对象错误分类比率。 定义2 1 4 2 3 1 设有决策系统s = ( 【，a = c u d ，v ，厂) ，p c 的属性重要性定义 。) ( p ) = 警希产= 1 一错 ( 2 - 9 ) q c ，。) ( p ) x 以理解为去除属性子集p 后所发生的对象错误分类比率。 2 2 特性关系粗糙集理论 定义2 1 5 1 1 1 i 设s = ( u ，a 1 为不完备信息系统，u 是由对象组成的非空有限 集合，a = c u d 为属性集合，这里的c 为条件属性，d 为决策属性并且 c n d = 囝。对于v a a 都有个口的取值集合圪与之关联，形被称为口的域。 如果存在空缺值口( x 1 ，口4 ，x u ，则称s 为不完备信息系统；系统中的空 缺值分别用“? 或“木 表示，“? 表示丢失值，“木 表示不关心的值。 在【1 1 中，g r z y m a l a b u s s e 提出了特性集和特性关系的概念，特性集和特 性关系可以用下面的属性值对的思想来定义。 定义2 1 6 t 设s = ( u ，a ) 为不完备信息系统，令b 是属性，v 是b 的一个属 性取值，= f 6 ，v ) 是属性值对。如果v ? 和木，那么可以按照m = x uib ( x ) = y 形式定义m t 。如果存在一个x u 使得b ( x ) = ? ，那么对于b 的任意属性值1 ，( 1 ，? 西南交通大学硕士研究生学位论文第11 页 和，- c ) ，都有工芒 ( 6 ，v ) ；如果存在一个戈u 使得6 ( 工) = 木，那么对于b 的任意 属性值y ( v ? 和术) ，都有x ei ( 6 ，v ) l 。 定义2 1 7 1 1 1 i 设s = ( u ，a ) 为不完备信息系统，令b a 是一个属性子集， x u ，那么特性集( x ) 被定义为如下形式： 巧( x ) = n 6 ( 工) ) i ( 2 - 1 0 ) 6 口 定义2 1 8 1 1 1 i 设s = ( u ，彳) 为不完备信息系统，令b a 是一个属性子集， x ，y u ，特性关系c 。被定义为如下形式： ( x ，少) c ：台争y ( x ) ( 2 - 11 ) 定义2 1 9 1 1 i 设s = ( u ，a ) 为不完备信息系统，令曰彳是一个属性子集， 石，y u ，特性关系c 。同时也可被定义为如下形式： g = ( x ，y ) 【，2v 口b a ( x ) ? ，口( 工) = 口( y ) v 口( x ) = 木va ( y ) = q ( 2 12 ) 显然，特性关系只具有自反性，而并不满足对称性和传递性。对于这种不 完备信息系统中的粗糙集，仍然可以用两个精确集，即特性关系意义下的粗糙 集的下近似和上近似来描述。 定义2 2 0 1 u 1 在特性关系的意义下，相对于属性子集b 而言，x 的下近似 集x ；定义为： 霹= u 巧( 圳x x ，巧( x ) x 】 ( 2 - 13 ) x 的上近似集群定义为： 硭= u 巧( x ) lx 彳，巧( z ) n x o 】= u 巧( x ) ix x ) ( 2 1 4 ) x 的边界域s ( x 1 定义为： b ( x 、= x ：一x ： 定义2 2 1 1 1 1 i 特性关系的意义下，相对于属性子集b 而言， 舣；和上边界集蠼分别为： 蚁：= x x 毫，蚁：= x ：- x 2 3 本章小结 ( 2 15 ) x 的下边界集 ( 2 1 6 ) 本章讨论了经典粗糙集理论与特性关系粗糙集理论的基础知识。第1 节主 西南交通大学硕士研究生学位论文第12 页 要介绍了经典粗糙集理论的上近似、下近似、边界域、属性约简与核和属性的 重要性等相关定义。第2 节主要介绍了特性关系粗糙集模型下的特性集、特性 关系、上近似、下近似和边界域等相关定义。为后续的章节内容作铺垫。 西南交通大学硕士研究生学位论文第1 3 页 曼曼曼曼曼曼量蔓曼曼曼曼曼曼皇曼鼍蔓蔓曼皇舅i i i i i _ o 毫曼皇曼曼曼皇曼皇曼量曼鼍曼量曼曼! ! 曼曼! 曼皇! 曼曼曼曼曼量暑曼曼皇曼皂曼曼曼曼蔓曼曼曼曼曼曼皇皇皇曼皇曼曼曼 第3 章特性关系粗糙集模型下的知识约简与粒度 知识约简是粗糙集理论的核心内容之一。众所周知，知识库中知识( 属性) 并不是同等重要，甚至其中某些知识是冗余的。所谓知识约简，就是在保持知 识库分类能力不变的条件下，删除其中不相关或不重要的知识。本章在特性关 系粗糙集模型下讨论了基于区分矩阵、信息熵、粒度等知识约简算法，并给出 相关的实例来验证了算法的可行性；同时分别讨论了在特性关系粗糙集模型下 信息熵与知识粒度之间的关系和信息熵知识约简与粒度知识约简的等价性。 3 1 预备知识 在第二章中已经给出了经典粗糙集的约简与核的定义，下面给出特性关系 的约简与核的定义。 定义3 1 1 设s = ( u ，彳) 为不完备信息系统，c 是定义在u 上的特性关系， 如果协u ，口a ，巴( x ) = 巴1 。) ( x ) ，则称口是a 中可省略( 不必要) 的，否 则称口是彳中不可省略( 必要) 的。如果v a a 都是么中不可省略的，则称么是 独立的，否则称爿是依赖的。么中所有必要属性构成的集合称为4 的核，记为 c o r e ( a ) 。 表3 1 不完备信息系统 l l 2 2 2 l 2 l ， 2 l 2 3 4 5 6 西南交通大学硕士研究生学位论文第1 4 页 皇曼曼曼曼曼量曼曼量曼皇量量皇曼曼皇i i 1 1 _ 1i _ _ _ _ , i 一_ 一i i i i i 鼍曼舅曼曼鼍皇皇曼曼曼曼璺璺蔓 定义3 2 1 3 7 i 设s = ( u ，a ) 为不完备信息系统， b a ，如果觇u ， 巴( x ) = g ( x ) ，且对于任意b cb ，若q ( x ) g ( x ) 成立，则称b 是属性集彳的 一个约简，记为r e d ( a ) 。 同样，可以得出以下性质： 性质3 1 1 3 7 1 叩( 彳) = n 哆( 么) 。 例3 1 表3 - 1 中，令b = a , b ，c ，d ) ，由定义2 17 可得表3 - 1 的特性集： 巧( 1 ) = 1 ，3 ，4 ) n 1 ，2 ，5 ，6 ) n 1 ，2 ，4 ，5 ，6 ) r 、 1 ，2 ，6 ) = 1 ) ， 巧( 2 ) = 2 ，3 ，6 ) n 1 ，2 ，4 ，5 ，6 ) n 1 ，2 ，6 ) = 2 ，6 ) ， 巧( 3 ) = 3 ) ， 巧( 4 ) = 1 ，3 ，4 ) n 2 ，4 ，5 ) n 1 ，2 ，4 ，5 ，6 ) n 3 ，4 ，5 ，6 ) = 4 ) ， 巧( 5 ) = 1 ，2 ，4 ，5 ，6 ) 广、 3 ，4 ，5 ，6 ) = 4 ，5 ，6 ) ， i f ( 6 ) = 2 ，3 ，6 ) n 1 ，2 ，5 ，6 ) n 1 ，2 ，4 ，5 ，6 】= 2 ，6 ) 。 因此由定义2 18 - 得表3 1 的特性关系c 占为： g = ( 1 ，1 ) ，( 2 ，2 ) ，( 2 ，6 ) ，( 3 ，3 ) ，( 4 ，4 ) ，( 5 ，5 ) ，( 5 ，4 ) ，( 5 ，6 ) ，( 6 ，2 ) ，( 6 ，6 ) ) 。 在表3 1 中去掉属性a 可得表3 1 特性集为： 巧( 1 ) = 1 ，2 ，6 ) ，巧( 2 ) = 1 ，2 ，6 ) ，( 3 ) = 3 ) ，巧( 4 ) = 4 ，5 ) ，巧( 5 ) = 4 ，5 ，6 ) ， e ( 6 ) = 1 ，2 ，5 ，6 ) 。 由定义3 1 可得：q ( x ) g _ 。) ( x ) ，则属性口在表3 - 1 中是必要的。 在表3 1 中去掉属性b 可得表3 1 特性集为： i s c ( 1 ) = 1 ) ，i c ( 2 ) = 1 2 ，6 ) ，i c ( 3 ) = 3 】，巧( 4 ) = 4 ) ，6 ( 5 ) = 4 ，5 ，6 ) ， 巧( 6 ) = 2 ，6 ) 。 由定义3 1 可得： q ( 工) = q - 6 】( x ) ，则属性b 在表3 1 中是不必要的。 在表3 1 中去掉属性c 可得表3 1 特性集为： 巧( 1 ) = 1 ) ，巧( 2 ) = 2 ，6 ) ，( 3 ) = c a ) ，