（计算机软件与理论专业论文）粗糙集理论在数据库中的应用研究.pdf

山东大学硕士学位论文 摘要 粗糙集理论是一种处理含糊和不确定性问题的新型数学工具，已广泛应用于 机器学习、决策分析、知识发现、专家系统、决策支持系统、模式识别、模糊控 制等领域。 目前粗糙集理论在数据库中的应用主要集中在两个方面：一个是数据库中的 知识发现( 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 ，简称k d d ) ，另一个是粗糙关系数 据库模型( r o u g hr e l a t i o n a ld a t a b a s em o d e l ，简称r r d m ) 。 知识约简( 又称属性约简) 是k d d 中粗糙集理论处理的主要问题，现有的 基于区分矩阵和区分函数的知识约简算法的时间复杂度一般为o ( 川2 i u l 2 ) ，其中 u | 是论域u 中个体的数目，i a | 是属性个数，当数据量很大时，这些算法的可行性 就面临巨大挑战，这些算法的低效性在一定程度上也限制了粗糙集理论的广泛应 用，因此寻求高效的知识约简算法具有重要的意义。 粗糙关系数据库模型( r r d m ) 是粗糙集理论和经典关系数据库模型相结合 的产物，目前国内外学者对r r d m 的研究主要集中在粗糙关系操作，粗糙关系 查询，粗糙函数依赖，粗糙关系中的信息熵等研究上，但是所有的文献都是就 r r d m 的某一方面进行论述，并且很多概念定义得不够规范准确，因而如果能 从粗糙关系数据结构、粗糙关系操作、粗糙关系完整性约束、粗糙关系规范化四 个方面，构建一个完善的粗糙关系数据库的数学模型，必将对今后真正实现并应 用推广这个模型，奠定完备坚实的理论基础。 本文将研究工作放在：寻求高效可行的知识约简算法方面，和从全局角度对 粗糙关系数据库模型给予一个比较完整规范的描述方面，主要创新成果如下： l 、提出了一种基于划分加细的新的知识约简定义，并证明了它和经典的基 于正区域的知识约简定义等价，利用这个定义求解知识约简能够减少计算量。 2 、引入了一种一致度来度量决策表中条件属性对决策属性的重要性，以此 一致度作为知识约简算法的启发信息以缩小搜索空间，并证明了条件属性的一致 度越小，其对决策的重要性就越小，从而说明了以此一致度作为启发信息是合理 的。 东大学硕士学位论文 3 、在l 、2 的基础上设计了一种基于划分加细和一致度的启发式知识约简算 法，此算法的时间复杂度为o ( i c l 2 iu | ) ，其中i cj 为条件属性个数，l u i 为论域u 中个体 的数目，低于现有的经典知识约简算法，而且计算量较小。 4 、率先提出了从粗糙关系数据结构、粗糙关系操作、粗糙关系完整性约束、 粗糙关系规范化这四个方面，建立一个完整的粗糙关系数据库模型； 5 、提出了粗糙关系完整性约束，以完善粗糙关系数据库模型对不完全信息 的处理能力： 6 、提出了粗糙关系规范化理论及相应的规范化算法，以解决在粗糙关系数 据库逻辑设计中如何构造一个好的数据库模式问题。 关键词：粗糙集；数据库中的知识发现；知识约简：决策表；粗糙关系数据库。 i l 山东大学硕士学位论文 a b s t r a c t r o u g hs e tt h e o r yi san e w m a t h e m a t i c a lt o o lt od e a l 、i mv a g u ea n du n c e r t a i n p r o b l e m s ，w h i c hh a sb e e nw i d e l ya p p l i e di nm a c h i n el e a m i n g ，d e c i s i o na n a l y s i s ， k n o w l e d g ed i s c o v e r y , e x p e r ts y s t e m , d e c i s i o ns u p p o r ts y s t e m ，p a t t e r nr e c o g n i t i o n ， f u z z yc o n t r o lo ro t h e rf i e l d s a tp r e s e n tt h er e s e a r c ho i la p p l i c a t i o no fr o u g hs e tt h e o r yi nd a t a b a s ef o c u s e s o nt w oa s p e c t s ：o n ea s p e c ti sk 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 ) ，t h eo t h e r a s p e c ti sr r d m ( r o u g hr e l a t i o n a ld a t a b a s em o d e l ) k n o w l e d g er e d u c t i o n ，w h i c hi sa l s on a m e da t t r i b u t er e d u c t i o n ，i so n eo ft h e m a i np r o b l e m si nk d dt h a tr o u g hs e tt h e o r yd e a l s 、i m t h et i m ec o m p l e x i t yo f p r e s e n tk n o w l e d g ea l g o r i t h m s t h a tb a s e do nd i s c e r n i b l em a t r i xo rb a s e do n d i s c r i m i n a t i o nf u n c t i o ni sg e n e r a l l yo ( i a l 2 i u 2 ) ，w h e r ei st h en u m b e ro fa t t r i b u t e s a n di u li st h en u m b e ro fe l e m e n t si nd i s c o u r s ed o m a i nu w h e nt h ed a t aa m o u ti sv e r y l a r g e ，t h ef e a s i b i l i t yo ft h e s ea l g o r i t h m sw i l lf a c ec h a l l e n g e a n dt h el o we f f i c i e n c yo f t h e s ea l g o r i t h m sh a sa l s ol i m i t e dt h ew i d ea p p l i c a t i o no fr o u g hs e tt h e o r y s oi th a s g r e a ts i g n i f i c a n c ei ns e e k i n gt h ea l g o r i t h mw i t hh i g he f f i c i e n c ya n dg o o df e a s i b i l i t y r o u g hr e l a t i o n a ld a t a b a s em o d e l ( r r d m ) i sac o m p o s i t ep r o d u c t i o no f r o u g hs e tt h e o r ya n dc l a s s i c a lr e l a t i o n a ld a t a b a s em o d e l n o wi nt h es t u d yo n r r d m , t h ed o m e s t i ca n df o r e i g ns c h o l a r ss t u d i e ds o m ea s p e c t ss e p a r a t e l yw i t h o u t c o m b i n i n gt h e mt o g e t h e r , a n ds o m ec o n c e p t so fr r d m i sn o td e f i n e dn o r m a l l y s oi f a ni n t e g r a t e da n dn o r m a ld e s c r i p t i o no fr r d mi sc o n s t r u c t e df r o mf o u ra s p e c t s ：t h e r o u g hr e l a t i o n a ld a t as t r u c t u r e ，t h er o u g hr e l a t i o n a ld a t a b a s eo p e r a t i o n s ，t h er o u g h r e l a t i o n a li n t e g r i t yc o n s t r a i n ta n dt h er o u g hr e l a t i o n a ln o r m a l i z a t i o n ，i tw i l lc e r t a i n l y l a yac o m p l e t et h e o r e t i c a lf o u n d a t i o no ft h ei m p l e m e n t a t i o na n dt h ew i d ea p p l i c a t i o n o f r r d m t h er e s e a r c hw o r ko ft h i sp a p e rf o c u s e so nt w oa s p e c t s ：o n ea s p e c ti st os e e k 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 晰t hh i g he f f i c i e n c ya n dg o o df e a s i b i l i t y ，t h eo t h e r a s p e c ti st oc o n s t u r c t 锄i n t e g r a t e da n dn o r m a ld e s c r i p t i o no fr r d mf r o mg l o b a l i i i l i j 东大学硕士学位论文 p e r s p e c t i v e t h em a i nr e s e a r c ha c h i e v e m e n t sa l ef o l l o w i n g ： 1 an e wk n o w l e d g er e d u c t i o nd e f i n i t i o nb a s e do np a r t i t i o ns u b d i v i s i o ni s p r o p o s e d ；i t se q u i v a l e n c et ot h ec l a s s i ca t t r i b u t er e d u c t i o nd e f i n i t i o nb a s e do np o s i t i v e r e g i o ni sp r o v e d b yu s i n gt h i sn e wk n o w l e d g er e d u c t i o n ，t h ec a l c u l a t i o na m o u n to f k n o w l e d g er e d u c t i o na l g o r i t h mw i l ls h r i n k 2 ac o n s i s t e n td e g r e ei si n t r o d u c e dt oe v a l u a t et h ei m p o r t a n c eo fc o n d i t i o n a t t r i b u t ef o rd e c i s i o na t t r i b u t e t h i sc o n s i s t e n td e g r e ei st a k e na st h eh e u r i s t i c i n f o r m a t i o ni nk n o w l e d g er e d u c t i o na l g o r i t h ma n di ti sp r o v e dt h a tt h es m a l l e ro ft h e c o n d i t i o n a la t t r i b u t e sc o n s i s t e n td e g r e et h el e s si m p o r t a n c eo fi tf o rd e c i s i o na t t r i b u t e ， s oi ti sr a t i o n a lt ot a k et h i sc o n s i s t e n td e g r e ea st h eh e u r i s t i ci n f o r m a t i o n 3 b a s e do nt h ea b o v er e s u l t s ，ah e u r i s t i ck n o w l e d g er e d u c t i o na l g o r i t h mi s d e s i g n e d t h et i m ec o m p l e x i t yo f t h i sa l g o r i t h mi so ( i c l 2 1 0 1 ) ，w h e r ei c ii st h en u m b e r o fc o n d i t i o n a la t t r i b u t e sa n di u ii st h en u m b e ro fe l e m e n t si nd i s c o u r s ed o m a i nu c o m p a r i n g 埘t hs o m ec l a s s i c a la l g o r i t h m so fk n o w l e d g er e d u c t i o n ，t h i sa l g o r i t h mh a s l o w e rt i m ec o m p l e x i t ya n ds m a l l e rc a l c u l a t ea m o u n t 4 a ni n t e g r a t e dr o u g hr e l a t i o nd a t a b a s em o d e li sc o n s t r u c t e db yf o u r a s p e c t s ：t h ed a t as t r u c t u r eo fr o u g hr e l a t i o n ，t h er o u g hr e l a t i o n a ld a t a b a s e o p e r a t i o n s ，t h er o u g hr e l a t i o n a li n t e g r i t yc o n s t r a i n ta n dt h er o u g hr e l a t i o n a l n o r m a l i z a t i o n 5 t h er o u g hr e l a t i o n a li n t e g r i t yc o n s t r a i n ti sp r o p o s e dt oc o n s u m m a t et h e c a p a b i l i t yo fr r d m t os o l v eu n c e r t a i ni n f o r m a t i o n 6 t h er o u g hr e l a t i o n a ln o r m a l i z a t i o ni sp r o p o s e dt os o l v et h ep r o b l e mt h a t h o wt oc o n s t r u c taw e l l - d e f i n e dd a t a b a s es c h e m ai nl o g i c a ld e s i g no fr o u g hr e l a t i o n a l d a t a b a s e k e y w o r d s ：r o u g hs e t ；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 ；k n o w l e d g er e d u c t i o n ； d e c i s i o nt a b l e ；r o u g hr e l a t i o n a ld a t a b a s em o d e l i v 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律责任由本人承担。 论文作者签名： 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：二逖导师签 山东大学硕士学位论文 第一章引言 1 1 粗糙集理论的产生背景与发展研究现状 经典逻辑中只有真、假二值，但在现实世界中广泛存在含糊现象，其逻辑值 不是非真即假，而是介于两者之间。因此，早在1 9 0 4 年，逻辑学家g f r e g e 就 提出了含糊( 德文v a g u e ) 概念，用边界线区域来表示那些既不能被分类于某个 集合又不能被分类于该集合的补集的元素；2 0 世纪6 0 年代初，l a z a d e h 提出 了模糊集( 英文f u z z ys e t ) ，但它是不可计算的，没有给出数学公式计算边界 线区域中的含糊元素个数：1 9 8 2 年，波兰华沙理工大学的p a w l a k 教授提出了粗 糙集，其主要思想是通过全域上的等价关系来定义全域上某个子集的上、下近似， 用该子集的下近似来表示全域中那些能被分类于该子集的元素，而用该集合的上 近似的补集来表示全域中那些不能被分类于该子集的元素，上、下近似之差就是 边界线区域( 也就是g f r e g e 的含糊概念) 。由于上、下近似的计算有确定的数 学公式，所以边界线区域中的含糊元素个数可以被计算出来，即在真假二值之间 的含糊程度可以明确计算出来。 作为一种处理含糊和不确定性问题的新型数学工具，粗糙集理论自问世以 来，得到了无数学者的坚持不懈地深入研究。最初的关于粗糙集的研究大多是以 波兰文发表的，因此当时并未引起国际上数学界和计算机界的重视，研究地域局 限于东欧各国。在2 0 世纪8 0 年代末和9 0 年代初由于其在知识发现等领域 得到了成功的应用而越来越受到国际上的广泛关注。特别是1 9 9 1 年z p a w l a k 的第一本关于粗糙集的专著和1 9 9 2 年r s l o w i n s k i 主编的关于粗糙集应用及其 与相关方法比较研究的论文集的出版，推动了国际上对粗糙集理论与应用的深入 研究。1 9 9 2 年在波兰k i e k r z 召开了第1 届国际粗糙集讨论会，这次会议着重讨 论了集合近似定义的基本思想及其应用，其中粗糙集环境下机器学习的基础研究 是这次会议的四个专题之一。这次会议选出1 5 篇论文刊登在“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 卷上。从此每年召开一次以 粗糙集理论为主题的国际研讨会。1 9 9 3 在加拿大b a n f f 召开了第2 届国际粗 糙集与知识发现( r s d 9 3 ) 研讨会，这次会议极大地推动了国际上对粗糙集理 论与应用的研究，其主题是粗糙集、模糊集与知识发现。些k d d 领域的著名 山东大学硕士学位论文 学者参加了这次会议，并且介绍了许多基于扩展的粗糙集理论的知识发现方法与 系统。特别值得一提的是在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 ) 上，针对粗糙集与模糊集合的基本观点与 相互关系展开了激烈的讨论，较大地促进了粗糙集的研究。1 9 9 6 年底在日本东 京召开了第5 届国际粗糙集研讨会，这是第一次在亚洲地区召开的范围广泛的 粗糙集研讨会。1 9 9 8 年6 月在波兰华沙召开了“第1 届粗糙集和计算的当前 趋势学术会议。1 9 9 9 年1 1 月在日本召开了“第7 届粗糙集、模糊集、数 据挖掘和粒度一软计算的国际学术研讨会”( r s f d g r c 9 9 ) ，阐述了当前粗糙集、 模糊集的研究现状和发展趋势，指出将着重在软计算、数据库、a i 和近似推理 等理论和应用方面发展。2 0 0 0 年1 0 月在加拿大又召开了“第2 届粗糙集和计 算的当前趋势 学术会议。2 0 0 1 年在日本召开了“粗糙集理论和粒度计算国际 研讨会。2 0 0 2 年在美国召开了“第3 届粗糙集和计算的当前趋势”学术会议。 目前，在许多关于人工智能、模糊理论、信息管理与知识发现等国际学术会议上 经常可以看到许多涉及粗糙集的论文。 中国学者也积极投身于粗糙集理论的研究。2 0 0 1 年5 月在重庆召开了“第1 届中国r o u g h 集与软计算学术研讨会”，邀请了创始人z p a w l a k 教授做大会报 告。随后每年的研讨会在规模和质量上均呈良好的增长趋势。2 0 0 2 年1 0 月在苏 州召开了“第2 届中国r o u g h 集与软计算学术研讨会”。2 0 0 3 年1 0 月在重庆召 开了“第3 届中国r o u g h 集与软计算学术研讨会”，并同时举办“第9 届粗糙集、 模糊集、数据挖掘和粒度一软计算的国际会议。 同时，在2 0 0 3 年还成立了中 国人工智能学会粗糙集与软计算专业委员会，粗糙集的研究队伍也更加壮大，研 究成果在深度和广度上有了更大的发展。2 0 0 4 年1 0 月在舟山召开了“第四届中 国r o u g h 集与软计算学术研讨会”。在国内的计算机核, c , , t j j 物和会议上，也不时 出现涉及粗糙集的论文。此外，也有不少有关粗糙集的专著。 经过近些年的研究和发展，粗糙集已经从理论上日趋完善，且已经被证实在 实践中是非常有用的，其在信息系统分析、人工智能及应用、决策支持系统、知 识与数据发现、模式识别与分类、故障检测、过程控制等诸多领域都取得了成功 的应用。由于粗糙集理论对不确定性的描述是相对客观的，且在无需先验信息的 情况下提供了严格地处理数据分类问题的数学方法，能在保留关键信息的前提下 2 山东大学硕士学位论文 对数据进行兼并求得知识的最小表达，揭示出简单的模式，能从经验数据中获取 已证实的规则知识，因此在处理不确定性问题上相对于其它理论工具具有不可替 代的优越性，更成为数据挖掘的一个重要工具。 1 2 本文的研究内容和意义 由1 1 可知，粗糙集理论的应用领域非常广，而本文是把研究工作放在粗 糙集理论在数据库中的应用上，目前粗糙集理论在数据库中的应用主要集中在两 个方面：一个是数据库中的知识发现( k n o w le d g ed is c o v e r yi nd a t a b a s e ，简称 k d d ) ，另一个是粗糙关系数据库模型( r o u g hr e l a t i o n a ld a t a b a s em o d e l ，简 称r r d m ) 。 知识发现是指人们用先进、有效的手段，对各种“数据矿藏”( 信息资源) 进行开采，智能、自动地从中挖掘出“黄金”( 有价值的信息与知识) 的过程。 由于蕴含知识的信息大多存储于数据库中，数据库中的知识发现( k n o w l e d g e d i s c o v e r yi nd a t a b a s e ，简称k d d ) 成为当前知识发现的主要研究课题。在k d d 中，粗糙集理论处理的主要问题包括数据库中的数据约简、数据相关性、相似性 或差异性、因果关系的发现、数据意义的评估、由数据产生决策控制算法、数据 的近似分类等等。其中，数据库中的数据约简又包括知识约简( 也称属性约简) 和值约简，其主要思想是：将一些无关或多余的信息丢掉( 属性约简是去掉多余 的属性列，值约简是去掉多余的属性值) 而不影响其原有功能，将约简后的信息 重新组合而产生新的决策规则，新的决策规则的前提信息和结论信息可能不同于 约简前的任何一条决策规则，但它们能经推理而得到相同或近似的结果，因此这 样的研究对数据挖掘以及数据库的进一步应用将产生新的影响，其应用前景是广 阔的。现有的基于区分矩阵和区分函数的知识约简算法的时间复杂度一般为 0 ( ia 2u 2 ) ，其中lu l 是论域u 中个体的数目，lai 是属性个数，当数据量很大时， 这些算法的可行性就面临巨大挑战，这些算法的低效性在一定程度上也限制了粗 糙集理论的广泛应用，因此寻求高效的知识约简算法具有重要的意义。 粗糙关系数据库模型( r o u g hr e l a t i o n a ld a t a b a s em o d e l ，简称r r d m ) 是 粗糙集理论在数据库中的另一个重要应用。e f c o d d 于七十年代提出了经典的 关系数据库模型( r e l a t i o n a ld a t a b a s em o d e l ，简称r d m ) ，其处理能力主要是 山东大学硕士学位论文 针对确定性信息，目前已经得到了广泛的应用和认可，但其对不确定性数据的处 理能力较差，随着应用面的扩大和数据量的急剧膨胀，出现了各种不确定信息， 不完全信息，模糊信息，因此有必要对r d m 进行扩充。t h e r e s ab e a u b o u ef ， f r e d e r i c ke p e r r y 于1 9 9 3 年提出了r r d m ，并随后进行了一些深入细致的探讨， 目前国内外学者对r r d m 的研究主要集中在粗糙关系操作，粗糙关系查询，粗糙 函数依赖，粗糙关系中的信息熵等研究上，但是所有的文献都是就r r d m 的某一 方面进行论述，并且很多概念定义得不够规范准确。因而如果能从粗糙关系数据 结构、粗糙关系操作、粗糙关系完整性约束、粗糙关系规范化四个方面，构建一 个完善的粗糙关系数据库的数学模型，必将对今后真正实现并应用推广这个模 型，奠定完备坚实的理论基础。 本文的主要研究成果是：提出了一种高效可行的启发式知识约简算法，从全 局的角度对粗糙关系数据库模型给予了一个比较完整规范的描述。具体的创新点 如下： 1 、粗糙集理论中经典的知识约简定义有两种：第一种是从代数集合观点出 发、基于正区域的知识约简定义，第二种是从信息论的信息熵观点出发、基于条 件熵的知识约简定义。本文提出了一种新的基于划分加细的新的知识约简定义， 并证明了它和经典的基于正区域的知识约简定义等价，利用这个定义求解知识约 简能够减少计算量。 2 、受第二种知识约简定义中条件熵计算公式的启发，把对数运算换成除法 运算，本文引入了一种一致度来度量决策表中条件属性对决策属性的重要性，以 此一致度作为知识约简算法的启发信息以缩小搜索空间，并证明了条件属性的一 致度越小，其对决策的重要性就越小，从而说明了以此一致度作为启发信息是合 理的。 3 、在1 、2 的基础上设计了一种基于划分加细和一致度的启发式知识约简算 法，和许多经典的知识约简算法相比，此算法的时间复杂度较低，计算量大大减 少。 4 、率先提出了从粗糙关系数据结构、粗糙关系操作、粗糙关系完整性约束、 粗糙关系规范化这四个方面，建立一个完整的粗糙关系数据库模型。 5 、提出了粗糙关系完整性约束，从而完善了粗糙关系数据库模型对不完全 4 山东大学硕士学位论文 信息的处理能力； 6 、提出了粗糙关系规范化理论及相应的规范化算法，从而解决了在粗糙关 系数据库逻辑设计中如何构造一个好的数据库模式问题。 1 3 本文的组织结构 本文是按照下面的结构组织的： 第二章介绍了粗糙集理论的一些基础概念，这些概念是第三、四章内容的共 同基础，因而单列一章。 第三章阐述了一种基于划分加细和一致度的启发式知识约简算法。首先介绍 了信息系统和决策表概念，列出了经典的两种知识约简定义，然后提出一种新的 基于划分加细的知识约简定义，并证明了这个定义和经典的基于正区域的定义等 价，接着引入了一种一致度来度量条件属性对决策属性的重要性，最后以一致度 作为启发信息并结合新的知识约简定义，设计了一种复杂度较低计算量较少的知 识约简算法。 第四章阐述了一个较完整的粗糙关系数据库模型。主要从粗糙关系数据结 构、粗糙关系操作、粗糙关系完整性约束、粗糙关系规范化这四个方面，对粗糙 关系数据库模型给予了一个比较规范完整地描述，并提出了一些尚待解决的问 题。 第五章对本文的工作做了一个总结，指出本文的不足，并对下一步的研究工 作进行展望。 【j 东大学硕士学位论文 第二章粗糙集理论基础概念 1 1 节已经提到：粗糙集理论的主要思想是通过全域上的等价关系来定义全 域上某个子集的上、下近似，用该子集的下近似来表示全域中那些能被分类于该 子集的元素，而用该集合的上近似的补集来表示全域中那些不能被分类于该子集 的元素，上、下近似之差就是边界线区域( 也就是g f r e g e 的含糊概念) 。下面 就用严格的数学定义逐步阐明上述思想。 2 1 近似空间 【定义2 1 1 】 6 1 一个近似空间是一个二元组a s = ( u ，r ) ，其中：u 是由我们感兴 趣的对象组成的非空有限集合，称为论域；r 是u 上的一个等价关系。 说明：用【x 】r 表示包含u 中元素x 的r 等价类，用商集u r 表示r 的所有 等价类构成的集合，r 的所有等价类构成u 的一个划分。 【定义2 1 2 】3 设为论域u 上的一个等价关系族，另一等价关系族 ， o ，则( d 中所有等价关系的交集称为上的不可分辨关系，记作 i n d ( ( d ) ，即有【x 】帅( o ) = n 【x 】r 显然，m - d ( ( d ) 也是等价关系。 r 这两个定义比较抽象，下面举个例子说明一下： 【例2 1 】u = x l ，x 2 ，x 3 ，x 4 ，x 5 ) ，= r 1 ，r 2 ，i u ，i 是恒等关系，其中： r l = ， ， ， ) ui ， r 2 = ， ， ， ) ui ， r 3 = ， ， ， ， ， ， ， ) ui ， 若= r l ，r 2 ，由定义2 1 2 ， i n d ( ) 咏ln r 2 = ， ) ui ， 其中包含x l 的小i d ( ) 等价类为【x 1 】i n d ( 。) = 【x l 】r 1n 【x 1 】r 2 = x l ，x 2 。 用上面等价关系的表示过于繁琐，可以改用商集来间接描述等价关系和不可 6 山东大学硕士学位论文 分辨关系如下： u r i = “x l ，x 2 ， x 3 ，x 4 ) ， x 5 ) ， u r 2 = x l ，x 2 ) ， x 4 ，x 5 ， x 3 ) ) ， u r 3 = x 1 ，x 2 ，x 3 ， x 4 ，x 5 ) ， u m - d ( ) = u r 1 ，i 也 = “x 1 ，) 【2 ， x 3 ) ， x 4 ， x 5 ) 说明：不可分辨关系是p a w l a k 的标准粗糙集理论中最基本的概念。若 e i n d ( ( d ) ，则称对象x 与y 是不可分辨的，即x , y 存在于不可分辨关系i n d ( ) 的同一个等价类中。或者说，依据等价关系族形成的分类知识，x 与y 无法 区分。例如上面例2 1 中：( d = r l ，r 2 ，r 1 ，r 2 e 应x t u 的两种分类方法， 既属于r 1 又属于r 2 ，从而属于i n d ( ) ，因此x l ，x 2 在不可分辨关系i n d ( ) 下不可区分。 【定义2 1 3 】暗3u i n d ( ) 中的各等价类称为基本集。对于集合x c _ u ， 若x 可以表示成某些( d 基本集的并，则称x 是 可定义集，否则，称x 是 不可定义集。 2 2 知识与知识库 简单地说，知识就是一个分类方法，对应一个等价关系，知识库就是分类 方法的族集，对应一个等价关系族，其严格的数学定义如下： 【定义2 2 1 】1 称论域u 的子集为u 上的概念，o 也是一个概念，概念的 族集称为u 上的知识，u 上知识的族集构成关于u 的知识库。特别地，近似空 间a s = ( u ，r ) 中，u r 对应u 的一个划分，是关于u 的知识。 【定义2 2 2 】 6 1 设u 为论域，为u 上的等价关系族，另一等价关系族 ，g ，则u m - d ( ) 称为u 的基本知识，u i n d ( ) 中的每一 个等价类称为知识的基本概念。特别地，若等价关系q e ，则称u q 为u 的q 初等知识，u q 中的每一个等价类称为u 的q 初等概念。由于选取的 7 【l j 东大学硕士学位论文 不同子集可得到u 的不同知识，因此称k = c o ，) 为知识库。 约定：为了表示简单，用u ( d 表示u r n d ( ) 。 给定知识库k = c o ，) ，知识库的知识粒度由不可分辨关系i n d ( ) 的等 价类决定。 对e 述定义，举例说明如下： 【例2 2 】对于学生集合u = x l ，x 2 ，x 3 ，x 4 ，x 5 ，x 6 ，由下表： 汰 年级外语成绩性别 x l 优 男 x 2 良女 x 3良女 x 4 优女 x 5 优男 x 6 差女 可得三个等价关系：r 1 = ix 与y 年级相同 ， r 2 = ix 与y 外语成绩相同 ， r 3 = ix 与y 性别相同 。 ( 1 ) u r 1 = “x l ，x 5 ，x 6 ， x 2 ，x 3 ， x 4 ) ， u r 2 = x l ，x 4 ，x 5 ， ) 【2 ，) 【3 ) ， x 6 ) ， u r 3 = “x l ，x s ， x 2 ，x 3 ，x 4 ，x 6 ) 分别是关于年龄、成绩、性别的初等知识，其中的每个等价类是知识库 k = m ， r 1 ，r 2 ，i u ) 的初等概念。 ( 2 ) = r 1 ，r 2 ， u 的( d 基本知识为u r n d ( ) = x l ，x 5 ， x 2 ，x 3 ， x 4 ， x 6 ) ， u 的( d 基本概念为 x 1 ，x 5 ， x 2 ，) 【3 ) ， x 4 ， x 6 ) 。 ( 3 ) u i n d ( r 1 ，r 2 ，r 3 ) = x l ，x 5 ) ， x 2 ，x 3 ) ， x 4 ) ， x 6 ， 它表达了知识库k - - c o ， r 1 ，r 2 ，i u ) 的粒度情况。 2 3 粗糙集 f i 东大学硕士学位论文 【定义2 , 3 1 】4 ，5 ，6 1 对于近似空间a = ( u ，r ) ，若x 是u 的任意一个子集，令 一r x = u y y u r 且y x ) ，r x = u yy u r 且】，nx o ) ，则称型为x 的r 下近似，心为x 的r 上近似。 【定义2 , 3 2 】4 ，5 ，6 1 当心= r x = x 时，称x 是r 精确集，即x 可以精确地 表示为某些r 基本概念的并。当型r x 时，称x 是r 粗糙集，即x 是一个 粗糙概念，只能通过一对精确概念蛸肼“近似”地描述。 【定义2 3 3 】4 ，5 朋当x 为r 粗糙集时，称b n r ( x ) = 趟一丛为x 的i 邀界 域，p o s r ( = 型为x 的r 正域，n e g r ( x ) = u r x 为x 的r 负域。 以上粗糙集的定义比较抽象，下面举个例子说明一下： 【例2 3 】近似空间a = ，r ) ，其中： u = l ，2 ，3 ，4 ，5 ，6 ，u r = “1 ，3 ) ， 2 ，4 ) ，1 5 ， 6 = y l ，y 2 ，y 3 ，y 4 ) 。 对x l = 1 ，2 ，5 ， 星x 1 _ y 3 = 5 ，r x i = y 1u y 2 u y 3 = 1 ，3 ) u 2 ，4 u 5 = l ，2 ，3 ，4 ，5 ) ， 由于r _ x i c rx 1 ，因而x 1 是r 粗糙集； 对x 2 = 1 ，2 ，3 ，4 ， 一r x 2 = y 1u y 2 = 1 ，3 ) u 2 ，4 ) = l ，2 ，3 ，4 ，r x 2 = y 1u y 2 一 l ，2 ，3 ，4 ) ， 由于丛x 2 = r x 2 = x 2 ，因而x 2 是r 精确集。 粗糙集x l 的r 边界域b n r ( x 1 ) = r x l 一r _ x l = 1 ，2 ，3 ，4 ) ，( 这就是边界线区 域，对应g f r e g e 的含糊概念) 粗糙集x l 的r 正域p o s r ( x 1 ) = r x i = 5 ， 粗糙集x 1 的r 负域n e g r ( x 1 ) = r x 1 - rx i = 6 ) 。 9 山东大学硕士学位论文 也可以用下面的图示来理解上述粗糙集相关基础概念： 心 l 、添 i _ 一 一一 n 添渌 添 八、心 闷i 心 y 弋n 卜、 、心s 划 一 、 图中：外围大矩形表示整个论域u ，大矩形中的每个小方格表示u 上等价关系r 划分u 的每个等价类，闭合曲线所围部分表示u 的一个子集x ，双阴影部分表示x 的下近似，双阴影加单阴影部分表示x 的上进似，而单阴影部分表示x 的边界域。 租糙集的一些基本性质如f ： ( 1 ) 型x r x ( 2 ) 垦= rg = o ，垦u = ru = u ( 3 ) r ( xuy ) = rxury ，垦( xny ) = 星xn 垦y ( 4 ) x yj rx ry ，rx r y ( 5 ) 垦( uy ) 垦xu 垦】厂，尺( xn 】，) 尺xn 尺y ( 6 ) 垦( x ) = 尺x ，尺( x ) = 垦x ( 7 ) 垦( 蹦) - - r ( 丛) - - 型，垦( 胱) = r ( 肘) - - - r x 2 4 粗糙集的特征描述 可以从两个角度来描述粗糙集的特征：一个是数字特征，用于描述其边界域 的相对大小，另一个是拓扑特征，用于描述其边界域的结构。 1 0 山东大学硕士学位论文 2 4 1 数宇特征 数字特征是用近似精度来表示的，其定义如下： 啶如a 川刚由等价关和定义州睦集厶x 的酬螨度为州耻髑。 说明：( 1 ) 显然，0 ( x ) 1 。 ( 2 ) ( x ) 反映了利用知识r 近似表示x 的完全程度。当( x ) = 1 时， x 是r 精确集：当o ( x ) 0 ，则称a 是c 相对于d 的一个知识约简。 举例说明上述定义如下： 例3 3 】在0 1 1 3 2 的表3 z o e ， u c = “i ) ，( 2 ，3 ，4 ，5 ，6 ) ，( 7 ，8 ，9 ，1 0 ) ) ， 由定义3 3 1 可得h ( c ) 一击l 。g 咕) 一言l 。g 岳) 一焉l 。g ( 南) = 。4 。 对于条件属性c 的子集a = ( b ，c ) ， u a = ( 1 ) ，( 2 ，3 ，4 ，5 ，6 ) ， 7 ，8 ，9 ，1 0 ) ) ，由定义3 3 1 可得 h c a ，= 一 ：。g c 击，一言- 。g c 嘉，一；吾。g c 杀，2 。4 - 。 而对a 中的任意一个属性( b 或c ) ： u ( a 一 b ) ) = u ( c ) = 1 ，7 ，8 ，9 ，1 0 ) ，( 2 ，3 ，4 ，5 ，6 ) ， u ( a 一 c ) ) = u ( b ) = f 1 ，2 ，3 ，4 ，5 ，6 ) ， 7 ，8 ，9 ，1 0 ) ) ， 由定义3 3 2 可得 1 6 山东大学硕士学位论文 h ( b ) l a 一 b ) = 一而5 。而1