（管理科学与工程专业论文）粗糙集理论在数据挖掘中若干问题的研究.pdf

山东师范大学硕士学位论文 租糙集理论在数据挖掘中若干问题的研究 摘要 随着数据库技术的迅速发展咀及数据库管理系统的广泛应用，数据呈海量增长，出现 了“数据爆炸但知识贫乏”的现象。在这种情形下，数据挖掘作为处理海量数据的工具便 应运而生了。目蔚，数据挖掘中常用的方法和技术有：统计分析方法、决策树、神经网络、 遗传算法、模糊集方法、粗糙集理论、可视化技术等等。在诸多方法中，粗糙集理论与方 法对于处理复杂系统不失为一种较为有效的方法。 粗糙集理论是波兰数学家z p a w l a k 于1 9 8 2 年提出的种分析不完整、不精确、不确 定数据的数据分析理论。将粗糙集理论应用于数据挖掘，具有明显的优越性无需提供 所需处理的数据集合之外的任何先验信息，利用数据集上的等价关系对知识的不确定程度 进行度量。恰恰是这一点，使得粗糙集理论在数据挖掘中具有更强的生命力。目前，粗糙 集理论广泛应用于数据挖掘的多个方面，比如：属性约简，连续属性离散化，关联规则挖 掘等等。本文主要研究孝且糙集理论在属性约简和连续属性离散化两个方面的应用。 属性约简是租糙集理论研究的核心问题之一，通过属性约简，删除决策表中不必要的 属性，在不丢失狭藏表基本信息的前提下，简化知识的表示，这正是人们所期望的。粗糙 集理论不能直接对连续属性进行处理而现实中的决策表往往含有连续属性，返是制约粗 糙集理论应用的个重要方面。因此在数据预处理阶段需要将连续属性离散化。 针对粗糙集理论在这两个方面的应用，本文主要做了如下工作： ( 1 ) 提出了一种通过构造约简树对决策表中的属性进行约简的方法。该方法方便有 效、容易被人们理解，在一定程度上降低了属性约简算法的时间复杂度。 ( 2 ) 从逻辑代数的角度出发，定义了可辨布尔矩阵，给出了可辨布尔矩阵的性质， 用柬简化可辨稀尔矩阵的变换，建立了用可辨布尔矩阵和线性逻辑方程组表示的属性约简 模型，讨论了该模型的求解方法，给出了线性逻辑方程组有解、有唯一解的充分必要条件。 提出了分类系数的概念，给出了一种基于分类系数和线性逻辑方程组的新的高效的属性约 简算法。 ( 3 ) 将可辨靠尔矩阵和线性逻辑方程组用于连续属性离散化：建立了关于断点集与 可辨布尔矩阵的逻辑方程组，在逻辑方程组解的基础上提出了一种新的连续属性离散化算 法。 ( 4 ) 将上述提出的属性约简算法和连续属性离散化算法用于数据挖掘过程中，建立 了一个基于睾h 糙集理论的数据挖掘模型。 数据挖掘本身及粗糙集理论还有许多问题值得探讨，本论文将二者结合研究肯定还有 许多不完善的地方，相关工作还有待进一步研究。 关键词：数据挖掘，粗糙集，属性约简，可辨布尔矩阵，逻辑方程组 分类号：t p l 8 i l l 山东师范凡拳硕士学位论立 s o m er e s e a r c ho nd a t am i n i n gb a s e do nr o u g hs e t st h e o r y a b s t r a c t w i t l lt h er a p i dd e v e l o p m e n to fd a t a b a s et e c h n o l o g ya n dt h ea b r o a da p p l i c a t i o no fd a t a b a s em a n a g e m e n ts y s t e m ，t h ed a t ai n c r e a s e sv e r yq u i c k l y s od a t ai se x c e s s i v eb u tk n o w l e d g e i ss p a r eu n d e rt h i sc o n d i t i o n , d a t am 戤n ga st h et o o lo f d e a l i n gw i t ht h ea b t m d a md a t ac o m e s i n t ob e i n g a tp r e s e n lt h em e t h o d sa n dt e c h n o l o g i e si nd a t am i n i n ga r ea sf o l l o w s ：s t a t i s t i c a l a n a l y s i sm e t h o d , d e c i s i o nt r e e ，a r t i f i c i a ln e u r a ln e t w o r k ，g e n e t i ca l g o r i t h m ，f u z z ys e t s m e t h o d , r o u g hs e t st h e o r y , v i s u a lt e c h n o l o g ye r e a m o n gs om a n ym e t h o d s ，r o u g hs e t s t h e o r yi sak i n do f m o r ev a l i dm e t h o dt od e a lw i t ht h ec o m p l i c a t e ds y s t e m r o u 曲s e t st h e o r yp u tf o r w a r db yp o l ez p a w l a ki n1 9 8 2i san e wd a t aa n a l y s i st h e o r yo f a n a l y z i n ga n dd e a l i n gw i t hu n c e r t a i na n di n c o m p l e t ed a t a r o u g hs e t su s e di nd a t am i n i n gh a s o b v i o u ss u p e r i o r i t y i th a sn on e e dt ob ep r o v i d e da n yk n o w l e d g eo u t s i d eo ft h ed a t aw h i c h n e e d st ob cp r o c e s s e d i tm a k e s1 t s eo ft h ee q u i v a l e n c et e l a t i o n $ t om e a g u r et h ei n d e t e r m i n a t i o n d e g r e eo fk n o w l e d g e e x a c t l yb e c a u s eo ft h i s r o u g hs e t st h e o r yh a ss t r o n g e rl i f ei nd a t a m i n i n g ，a tp r e s e n t ，r o u 曲s e t st h e o r yi sa p p l i e di nm a n ya s p e c t so f d a t am i n i n g ，f o re x a m p l e ： a t t r i b u t er e d u c t i o n ，d a t ad i s c r e t i z a t i o n , a s s o c i a t i o nr u l em i n i n g , c l a s s i f i c a t i o nr u l em i n i n g e t c i nt h i sp a p e r , t h ea t t r i b u t er e d u c t i o na n dr e a lv a l u ea t t r i b u t e sd i s c r e t i z a t i o nb a s e do nr o u 曲 s e t st h e o r ya r ed i s c u s s e d a t t r i b u t er e d u c t i o ni so n eo ft h em o s ti m p o r t a n tp r o b l e m si nr o u 【g hs e t st h e o r y n l c k n o w l e d g ei sr e d u c e db ya t t r i b u t er e d u c t i o n d e l e t i n gu n n e c e s s a r ya t l r i b u t e so nt h ep r e m i s eo f k e e p i n gt h ei n f o r m a t i o no fd e c i s i o nt a b l e t h a tr o u g hs e t st h e o r yc a l l td e a lw i t hr e a lv a l u e a t t r i b u t e sc o n s t r a i n st h ea p p l i c a t i o no fr o t 【g hs e t st h e o r y b u tt h e r ea r em a n yr e a lv a l u e a t 【r i b u t e si nr e a ll i f e s ot h er e a lv a l u ea t t r i b u t e sn e e dt ob ed i s e r e f i z e dd u r i n gt h ed a t a p r e t r e a t m e n t f o r t h e t w oa p p l i c a t i o n s o f r o u g hs e t s t h e w o r k s d o n e i n t h e p a p e r a r ea s f o l l o w s ： ( 1 ) a na t t r i b u t er e d u c t i o na l g o r i t h mb a s e do nr e d u c t i o nt r e ei sp r o p o s e d t h i sa l g o r i t h mi s s i m p l e ，e a s yt ob eu n d e r s t o o d i ta l s or e d u c e st h et i m ec o m p l e x i t yo ft h ea l g o r i t h mt os o m e e x t e n t ( 2 ) f r o mt h ev i e wo f l o g i ca l g b e r a , t h ed i s c e r n i b l eb o o l e a nm a t r i xi sd e f i n e d 1 1 1 ec h a r a c t e r o ft h em a t r i xa n dt h et l a t l s f o r n - 1 a t i 0 1 1t or e d u c ei ta r ep r e s e n t e d t h ea t t r i b t r mr e d u c t i o nm o d e i r e p r e s e n t e db yd i s c e r n i b l eb o o l e a nm a t r i xa n dl i n e a rl o g i c a le q u a t i o n si se s t a b l i s h e d ，a n dt h e m e t h o dt of i n dt h es o l u t i o n so ft h em o d e li sd i s c u s s e d t h en e c e s s a r ya n ds u f f i c i e n tc o n d i t i o n f o rl i n e a rl o g i c a le q u a t i o n sh a v i n gs o l u t i o n sa n dt h eo t h e rf o rl i n e a r1 0 9 i c a le q u a t i o n sh a v i n g u n i q u es o l u t i o na r eo b t a i n e d t h ec o n c e p to fc l a s s i f i c a t i o nc o e f f i c i e n ti sp r o p o s e d f i n a l l y , a s i m p l e ，v i s u a la n dh i 曲e f f i c i e n ta t t r i b u t er e d u c t i o na l g o r i t h mb a s e do nc l a s s i f i c a t i o nc o e f f i c i e n t 1 v 山东师范大学颂士学位论文 a n dl i n e a rl o g i c a le q u a t i o n si sg i v e n ( 3 ) d i s c e r n i b l eb o o l e a nm a t r i xa n dl o g i c a le q u a t i o n sa r en s e di n r e a lv a l u ea t t r i b u t e d i s c r e t i z a t i o n t h el o g i c a le q u a t i o n sb e t w e e nc l 吐s e t sa n dd i s c e r n i b l eb o o l e a nm a t r i xi s e s t a b l i s h e d f i n a l l y , an e w r e a lv a l u ea t t r i b u t e sd j s c r e t i z a t i o na l g o r i t h mi sg i v e n ( 4 ) f i n a l l y , t h ea t l r i b u t er e d n c t i o i la l g o r i t h ma n d t h en e wr e a lv a l u ea a r i b u t c sd i s c r e t i z a t i o n a l g o r i t h ma l eu s e di nd a t am i n i n g a d a t am i n i n gm o d e lb a s e do nr o u 曲s e t si sp u tf o r w a r d m a n yp r o b l e m si nd a t am 诚n g a n dr o u g hs e t st h r yn e e dt ob ed i s c u s s e d a n dt h e r ea l e m a n yp r o b l e m so f c o m b i n i n gt h e m t h ea c c o r d i n gw o r kw i l lb ed o n ei nt h ef u t u r e k 。y w o r d s ：d a t am i m n g ，r o u g hs e t s ，a t t r i b u t cr e d u c t i o n , d i s c e r n i b l eb o o l e a nm a t r i x ，l o g i c a l e q u a t i o n s s u b j e c t c l a s s i f i c a t i o n ：t p l 8 v 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得 ( 注：如没有其他需要特别声明的， 本栏可空) 或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：白运会 导师签字：彻 学位论文版权使用授权书 本学位论文作者完全了解兰撞有关保留，使用学位论文的规定，有权保髫并向国 家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅本人授权堂撞可 以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等 复制手段保存、忙编学位论文。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：臼运会 导师签字 签字晶期：2 0 0 7 年f 月3 5 日 泐 签字胁2 0 0 了年r 月妒 山东师范大学硕士学位论叟 1 1 课题的研究背景 第一章前言 近年来，随着商务贸易电子化、政府和企业事务自动化的迅速普及，产生了大规模的 数据，同时同益增长的科学计算和大规模的工业生产过程也提供了海量数据。在海量数据 背后隐藏着许多重要的信息，因此人们希望对其进行更高层次的分析，以便能够更好地利 用这些数据。目前的数据库系统可以高效地实现数据的录入、查询、统计等功能，但是无 法发现数据中存在的关系和规则，无法根据现有数据库中的数据预测未来的发展趋势，缺 乏挖掘数据背后隐藏的知识的手段和方法，导致了“数据爆炸但知识贫乏”的现象。 知识发现和数据挖掘正是在这种情况下产生和发展的一种新型数据分析技术。知识发 现是指从目标数据集合中识别出有效的、新颖的、现在有用的、以及最终可理解的模式的 非平凡过程。知识发现的对象主要是数据库，因此我们也称知识发现为数据库知识发现 ( k d d ) 。对于数据来说，知识发现的研究内容是，能自动地去处理数据库中大量的原始 数据，从中挖掘出具有必然性、富有意义的模式。所谓数据挖掘，就是指从数据库中抽取 隐台的、先前未知的、具有潜在应用价值的信息和知识的过程。数据挖掘是知识发现过程 中的核心步骤。 日糙集理论( r o u g hs e t s ) ”1 在数据挖掘方面表现出极大的发展潜力。粗糙集理论是 波兰数学家z p a w l a k 于1 9 8 2 年提出的一种分析不确定、不完整、不精确数据的数学工具 。”。粗糙集理论主要应用在对不完整、不精确信息的表达与处理上。该理论从新的角度来 看待知识，认为知识是源于人类以及其它物种的分类( c l a s s i f i c a t i o n ) 能力，在此基础上， 引入代数学中的等价关系来讨论知识。与人工智能领域中其它处理不完整、不精确数据的 数学工县相比，粗糙集理论有着它自身不可替代的优点。如：粗糙集理论不需要任何对数 据的先验知识，而统计理论则需要知道数据先验概率，模糊集理论则需要知道隶属度等。 这样相糙集理论可以客观地从数据中获取知识利用集合的上、下近似集合以及集合中的 不可辨识关系，对知识进行分类进而挖掘出信息系统中的潜在知识，最终形成决策规则。 因此，粗糙集理论对于不确定性的描述是一种客观的表达。粗糙集理论的优点决定了该理 论在处理信息的不完整性、不确定性、模糊性中将大有作为。 粗糙集理论与数据挖掘密切相关。粗糙集理论是数据挖掘领域中的又一个有效的新的 方法与数学工具。首先，数据挖掘研究的对象多为关系型数据库。而关系型数据库的关系 表可以被看作是粗糙集理论中的决策表。第二，现实世界中的规则有确定性的和不确定性 的，数据库中也包古有确定的和不确定的潜在规则，从数据库中发现不确定性的知识，这 就为粗糙集方法提供了用武之地。第三，数掘库中的数据可能含有噪声，而排除数据处理 过程中的噪声也是粗糙集理论的特长之一。第四，在数据挖掘领域，其它处理工具如神经 网络方法不能自动地选择合适的属性集，利用租糙集理论方法进行数据预处理去掉多余的 属性，这样可以提高数据处理的效率，而如模糊集理论或者统计学方法则需要数据库中数 据的先验知识，在这方面耦糙集理论能更好地表达数据库中的数据。第五，由于粗糙集理 l 山表师范丈学硕上学位论文 论自身的优点，使得经过粗糙集方法处理得到的决策规则和推理过程较神经网络等理论工 具更易于被证实和检测。 粗糙集理论自身独有的这些优点，使得自粗糙集理论被提出后就一直是各国科学家研 究的热点。目前，粗糙集理论被广泛应用于人工智能、知识发现与数据挖掘、模式识别与 分类，智能控制、故障检测等。 用租糙集理论进行处理时，首先面对的就是数据库，通常数据库中某些记录可能存在 空值、噪音现象，也可能某些属性的属性值是连续的。对于这些情况必须要先进行预处理。 一般而言，对于这些情况的处理会影响到后面的处理过程。因此预处理工作的好坏，直接 影响到下一步的规则获取，在研究粗糙集理论中必须要予以重视。另方面，作为粗糙集 理论的核心研究工作之一的属性约简一直是广大学者的研究热点。就目前而言，已经找到 了若干约简算法然而还没有一个公认的、高效的约简算法。因此，找出一个高效的约简 算法仍然是目前靼糙集理论中的一个非常值得重视的研究领域。 1 2 租糙集理论的研究现状 睾h 糙集理论是波兰数学家z p a w l a k 于1 9 8 2 年首先提出的，该理论刚刚被提出时未受 到国际智能研究领域的广泛重视，当时的研究也仅限于波兰等几个东欧国家。到了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 la s p e c t so fr e a s o n i n ga b o u t d a t a ，奠定了粗糙集理论的基础，从而掀起了粗糙集的研究热湖。1 9 9 2 年在波兰召开了 关于粗糙集理论的第一届国际学术会议，这次会议着重训论了粗糙集理论的基本思想及其 应用。以后每年都召开一次以粗糙集理论为主题的国际研讨会。1 9 9 3 年在加拿大召开了 第二届国际拳h 糙集与知识发现研讨会，这次会议积极推动了国际上对粗糙集应用的研究。 由于这次会议正值知识发现成为热门研究话题，一些著名知识发现学者参加了这次会议， 并且提出了许多应用粗糙集理论的数据挖掘的方法与系统，至此，粗糙集理论与知识发现 和数据挖掘紧密地联系在了一起。1 9 9 4 年在美国召开了第三届国际辊糙集与软计算研讨 会，这次会议广泛地探讨了粗糙集与模糊逻辑、神经网络、进化计算等的融合问题。1 9 9 5 年a c m c o m m u n i c a t i o n 将粗糙集列为新浮现的计算机科学的研究课题。1 9 9 9 年在日本召 丌了第七届粗糙集、模糊集、数据挖掘和粒度软计算国际会议，主要阐述了当前粗糙 集、模糊集的研究现状和发展趋势。2 0 0 0 年在加拿大召开了第二届粗糙集和计算的当前 趋势学术会议。当前许多重要的国际学术会议都把粗糙集理论的研究列入主要内容之一 。 近几年来粗糙集理论已经应用于机器学习、决策支持、知识发现、专家系统、模式 识别等领域。目前对粗糙集理论的研究主要集中在求解属性的最小约简、较小约简和最简 规则集【5 6 j 。粗糙集有效算法方面的研究包括如何求等价类、上近似、下近似、正区域、 约简和核等等。 山东师范大学硕士学位论文 现在国际上已经研制出了一些粗糙集工具应用软件，如k d d r 是由加拿大r c g n i a 大 学研制丌发的基于可变精度粗糙集扩展模型的数据库知识发现k d d 系统。k d d - r 系统曾 成功应用于医学数据分析和电信市场的决策分析等。u i 巧是美国k l t l l s 大学开发的基于 粗糙集的实力学习系统，l e r s 系统曾用于医学研究、气候预测和环境保护等o q 。r o u g h d a s r o u g hc l a s s 是波兰p o z n a n 工业大学开发的基于粗糙集的k d d 决策分析系统。 r o u g he n o u 曲是挪威t r o l ld a t ah l c 公司开发的，它包括数据输入、预处理、编辑、生成 可辨识矩阵、集合近似、约简、生成规则、预测和分析功能。r o s e t t a 是波兰华沙大学和 挪威科技大学联合开发的基于粗糙集的k d d 决策分析系统。该软件目前应用较广，r o s e t t a 可以处理多种格式的数据，如文本和数据库等，这些数据以决策表的形式存在于r o s c t m 系统中。当决策表成功装载入p r o j e c t 后，系统使用粗糙集理论逐步分析数据，最后得到 决策规则。除了以上介绍的几种系统外，还有一些其它系统，例如加拿大r c d u c ts y s t e m l n c j f 发的d a t a l o g i c r ，中科院计算技术研究所开发的k d t ，南京大学研制的k n i g h t 。 目前，国内学术界虽然对粗糙集理论有了定的认识，但是对于它在数据挖掘中的应 用还不够重视，对不同类型的决策表的属性约简、连续属性离散化还未提出高效率的、可 行的算法。现存的算法也不能够很好地进行处理，存在一定的缺点。这大大地阻碍了粗糙 集理论在实际中的应用。 1 3 本文的研究内容 在粗糙集理论的研究中，属性约简一直是研究的热点国内外研究学者都对此特别关 注。到目前为止，已经提出了一些约简算法。这些算法都是基于粗糙集理论，而粗糙集理 论中所有的概念与运算都是通过代数学的等价关系和集合运算来定义的，在这种定义下， 粗糙集理论的很多概念与运算的直观性较差，人们不容易理解其本质。连续数据离散化问 题是数据挖掘中的一个很重要的问题，很多数据挖掘算法都需要把连续数据离散化之后才 可实施。为解决这些问题，本文主要傲了以下工作： ( 1 ) 提出了种通过采用宽度优先的策略构造约简树，从而对决策表中的属性进行 约简的方法。约简树构造完毕，也就找到了属性集的极小约简。该方法方便有效、容易被 理解。 ( 2 ) 从逻辑代数的角度出发，建立了用可辨布尔矩阵和线性逻辑方程组表示的属性 约简模型，讨论了可辨布尔矩阵的性质和模型求解方法给出了线性逻辑方程组有解、有 唯一解的充分必要条件。提出了分类系数的概念，给出了一种基于分类系数和线性逻辑方 程组的新的高效的属性约简算法。 ( 3 ) 定义了可辨布尔矩阵，建立了关于断点集与可辨布尔矩阵的线性逻辑方程组， 在逻辑方程组解的基础上提出了一种新的连续属性离散化算法。 ( 4 ) 将上述提出的属性约筒算法和连续属性离散化算法用于数据挖掘过程中，建立 了一个基于粗糙集理论的数据挖掘模型。 山东师范人学硕士学位论文 1 4 本文的组织结构 本文针对当前属性约筒算法和连续属性离散化算法存在的缺点提出了新的算法，并将 这些算法用于数据挖掘过程中，提出了一个基于粗糙集理论的数据挖掘模型，同时还介绍 r 数据挖掘和半日糙集理论的一些基本概念，本文的组织结构如下： 第一章：前言介绍课题的研究背景、研究现状、本人做出的成果等内容。 第二章：允绍了粗糙集理论的基础知识。首先介绍了粗糙集理论的基本概念，包括知 识、不可辨识关系、粗糙集的近似；然后介绍了知识约简和知识的依赖性；最后给出了知 识表达系统，决策表以及可辨识矩阵的定义。 第三章：介绍了数据的离散化。首先介绍了数据离散化的方法；然后介绍了粗糙集中 离散化问题的描述；最后提出了基于逻辑方程组解的连续属性离散化方法，并进行了实例 分析。 第四章：介绍了属性约简算法。首先介绍了经典的粗糙集属性约简算法：然后提出了 约简树的构造方法，分析了约简树的性质，以及构造约简树的时间复杂度并给出了实例分 析；接着介绍了基于可辨识矩阵的基本属性约简算法；最后提出了粗糙集概念与运算的分 类系数表示，建立了属性约简的线性逻辑方程组模型，给出了模型求解的方法，提出了基 于分类系数和线性逻辑方程组的属性约简算法，分析了算法的时间复杂度并给出了实例分 析。 第五章：介绍了基于租糙集理论的数据挖掘模型。首先是对数掘挖掘的概述，包括数 据挖掘的定义，分类和方法：然后介绍了数据挖掘模型；最后建立了一个基于粗糙集理论 的数据挖掘模型。 山东师范，= 学硕士学位论文 第二章租糙集理论的基础知识 粗糙集理论是一种新的处理模糊和不确定知识的数学工具。其主要思想就是在保持知 识库分类能力不变的前提下，导出问题的决策和分类规则。本章将分别介绍p a w l a k 粗糙 集3 1 模型的基本概念，作为以后各章的基础。 2 1 粗糙集理论的基本概念 2 1 1 知识与不可辨识关系 在粗糙集理论中，“知识”被认为是一种将现实或抽象的对象进行分类的能力【2 】。如 在远古时代，人们为了生存必须能分辨出什么可以食用，什么不可以食用；医生给病人诊 断，必须辨别出患者得的是哪一种病。这些根据事物的特征差别将其分门别类的能力均可 看作是某种“知识”。 设u o 是我们感兴趣的对象组成的有限集合，称为论域。任何子集z 正u ，称为u 中的一个子集或范畴。u 中的任意概念族称为关于u 的抽象知识，简称知识。本文主要是 对在 ，上能形成划分的那些知识感兴趣。一个划分，定义为：f _ x i ，z 2 ，盖 ，其中， n * 量u ，z a ，工n 蜀= 0 ( i ，i ，= 1 ，2 ，月) ，u 石= u a i = 1 定义2 1u 上的一族划分称为关于【，的一个知识库( k n o w l e d g eb a s e ) 。一个知识库 就是一个关系系统k = ( u ，r ) ，其中u 是非空有限集，且为u 上等价关系的一个族集。 叫r 表示置的所有等价类( 或者u 上的分类) 构成的集合，k 表示的是包含元素 x u 的置等价类。 定义2 2 若p 置，且p a ，则p 中所有等价关系的交集也是一个等价关系，称为p 上的不可辨识关系，记为i n d ( p ) ，且有【x 】。d ( ，) = n 瞄h 。 这样，u f 以( 尸) ( 即等价关系i n d ( e ) 的所有等价类) 表示与等价关系p 相关的知识， 称为足中关于u 的p 基本知识( p 基本集) 。为简单起见，我们用叫p 代替v i n a c p ) ， i n d ( p ) 的等价类称为知识p 的基本概念或基本范畴。特别地，如果q r ，则称q 为置中 关于u 的9 初等知识，旦的等价类为知识且的q 初等概念或q 初等范畴。 同样，当置= ( u ，r ) 为一个知议库i n d ( k ) 定义为足中所有等价关系的族。 ， 山东师范太学硕士学位论文 现举例说明，给定一个玩具积木的集合u = x l ，x 2 ，m ，x 4 ，z “x 7 ，x g ) 。现在这些积木 有不同的颜色( 红、黄、蓝) ，形状( 方、圆、三角) ，体积( 小，大) 。因此，这些积木 就可以用颜色、形状、体积这些知识来描述。例如一块积木可以是蓝色、方而大的，或者 黄色、圆而小的。现在我们根据某一属性描述这些积木的情况，就可以按颜色、形状、体 积分类。 按颜色分类，红： x 1 ，z 3 ，x 7 ；黄： x ，x h ：3 ；蓝： x 1 , x 4 ； 按形状分类，方：( x 2 ，x 6 ；圆：( x 1 ，x 5 ：三角： x 3 ，j c 4 ，x 7 ，册) ； 按大小分类，小：扛1 ，x 3 ，拍，x s ，j 6 ) ；大： x 2 ，3 ；7 ，j l 。 换种说法，我们定义三个等价关系( 即属性) ：颜色置l ，形状r 2 和大小r 3 ，通过这 些等价关系，可以得到下面三个等价类： t ：e l = “z i ，躬，z 7 ， 船，x b x s ) ， x 2 ，靠 ， 叫r2 = x ， ， x 2 ，埘， x 3 ，x 4 ，x 7 ，x s ， u r3 = “x l ，x m 洲) ， 坞x 7 ，埘 。 可以看出，这些等价类是由知识库置= ( u ， 置，r 2 ，震，) ) 中的初等概念( 初等范畴) 构 成的。 基本范畴是初等范畴的交集构成的，例如下列集合： x 1 ，z 3 ，x 7 n 母3 ，x 4 ，x 7 ，x 8 j = 船，x 7 ， x 2 ，x 6 n x 2 ，x 4 ) = 扛2 ) ， 它们分别为 r i ，r 2 ) 的基本范畴，即：红色三角形，蓝色方形。 下列集合： ，x 3 ，x 7 n z 耳x 4 ，x 7 ，x 8 ) n ( x 2 ，x 7 ，肼卜 x 7 ) ， x 2 ，z 6 ) n x 2 ，x 4 n x 2 ，x ，x 8 = x 2 ) ， 它们分别为l 地盖：，r ，) 的基本范畴，即：红色大三角形，蓝色大方形。 2 1 2 粗糙集的近似 令x 量u ，且是u 上的一个等价关系。当x 能表达成某些月基本范畴的并时，称片是 r 可定义的：否则称x 是冠不可定义的。 6 山东师范 学硕士学位论文 r 可定义集是论域的子集，它可以在知识库中精确的定义，而胄不可定义集不能在这 个知识库中定义。置可定义集也称为r 精确集，而盖不可定义集也称为胄非精确集或r 粗 糙集。 租糙集可以近似地定义，我们使用两个精确集，即粗糙集的上近似( 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 ) 集来描述。 定义2 3 设集合x u 盂c i n d ( k ) ，定义两个子集： 丛= u r u r 1 r x ， 页= u r u r l y f l x o 分别称它们为z 的r 下近似集和r 上近似集。 集合b n j , ( x ) = 面一鲋称为x 的r 边界域；p o s 一( x ) = 趟称为x 的丑正域； n e g j i ( x ) = u 一融称为x 的震负域。 或p o s ( x ) 是由那些知识矗判断肯定属于x 的【，中元素所组成的集合；时是由 那些知t h 月判断可能属于x 的u 中元素所组成的集合；6 m ( j 0 是由那些知识且既不能判 断可能属于爿又不能判断肯定属于一j 的u 中元素所组成的集合：n e g a ( x ) 是由那些知识 月判断肯定不属于工的u 中元素所组成的集合。 下面的性质是显而易见的： 定理2 1 ( 1 ) x 为r 可定义集当且仅当肼= ： ( 2 ) x 为r 粗糙集砑心： 我们也可以将丛描述为j 中的最大可定义集，将戤描述为含有工的最小可定义 集。 根据集合工的上近似和下近似的不同情况，可以定义四种不同的重要的粗糙集： ( 1 ) 如果型o 且戤u 。则称j 为胄粗糙可定义； ( 2 ) 如果p o t = g 且瓦y u ，则称x 为r 内不可定义； ( 3 ) 如果鲋国且戤= ( ，则称x 为皿外不可定义； ( 4 ) 如果篮= 必且黔= u ，则称盖为置全不可定义。 这种划分的直观意义是这 手的： 如果集合鼻为彘和糙可定义，则意睬着我们可醴确定d 中的莱些元素属于并或一z ， 山东师范大学硕士学位论文 如果集合z 为矗内不可定义，则意味着我们可以确定u 中的某些元素是否属于x ， 但不能确定u 中的任一元素是否属于x 。 如果集合z 为月外不可定义，则意味着我们可以确定u 中的某些元素是否属于彳， 但不能确定u 中的任一元素是否属于一j 。 如果集合为胄全不可定义，则意味着我们不能确定u 中的任一元素是否属于j 或 一x 。 粗糙集理论与传统的集合论有着相似之处，但是它们的出发点完全不同。传统集合论 认为，一个集合完全由其元素决定，一个元素要么属于这个集合，要么不属于这个集合， 即它的隶属函数x ( x ) 0 0 1 。模糊集合对此做了拓广，它给成员赋予一个隶属度，即 肛( x ) 【o ，1 ，使得模糊集合能够处理一定的模糊和不确定数据，但其隶属度往往具有人 为的因素在里面，这为它的应用带来一定的不便。在租糙集理论中，隶属关系不再是一个 原始概念，因此无需人为给元素指定一个隶属度，从而避免了主观因素的影响。粗糙集理 论认为不确定与隶属关系有关，而模糊性则表现在集合本身。 集合的不精确是由于边界域的存在而引起的。集合的边界域越大，其精确性则越低。 为了更准确地表达这一点，我们引入精度的概念。 定义2 4 由等价关系r 确定的集合z 的近似精度为 a n r z l 其中，工o ，i 表示集合上的基数。 ( 2 1 ) 精度口一( z ) 用来反映我们对于了解集合x 知识的完全程度。显然，对每一个r 和 j 。u 有0 口r ( z ) l 。当口一( ) 譬i 时，说明z 的r 边界域为空集，集合j 为五可定义 的；当d ”( x ) 】时。说明集合并有非空月边界域，集合x 为r 不可定义的。 现举例9 1 来说明粗糙集和精度的概念，给定一个知识库k = ( u ，r ) 和一个等价关系 置i n d ( k ) ，其中u = x 0 ，x 1 ，x 2 ，x 3 ，期，x 5 ，x 6 ，x 7 ，x 8 ，x 9 ，x l o ) ，且有r 的下列等价类：e l = z x 1 e 2 = ( 舰，x 6 , x g ，e 3 = 妁，z 5 ，e 4 = 拟，x 8 ，西= x 7 ，x l o 。 集合x i = x 0 ，扎x 4 ，z 。) 为r 可定义集，因为： 默，= 瓦= e t u e 一。 集合z 2 = x o ，x x x ，z x 8 ，) 为且粗糙可定义集，因为 鱼卢b ue 4 = ：3 ，x 4 ，x ，x 磅， 型酬 山东帅舡大擘碘士学位论文 r x 2 = e 1 u e , u e 4 u 五j = z 。，x 1 ，x 3 , x 4 ，z ，z ，x s ，x t o ， 凰：r x ：且堡t ：or 瓜，u ，故j ：为r 粗糙可定义集。 b n h ( x z ) = e t o e s = x o , x i ，j 7 ，x l o j ， a 月( x 2 、= 4 8 = 0 5 。 集合x 3 = x o ，x 2 ，柏 为r 内不可定义，因为： 凰、= o t r x ，= ej u e z u e t = x o ，x t ，x 2 ，x 3 ，x ，x 6 ，x 9 j u ， 集合x = f 姗，z l ，x 2 ，弘x ，工， 为胄外不可定义，因为： 出= e l = ( x 口，) o ， m = u ， x 的边界和精度为： b i n ( x + ) = e 2 u 而u e 4 u e 5 = x 2 ，x 3 ，x 4 ，z 5 ，x 6 , x 7 ，x 8 ，柏o 口月( x 4 ) ：2 1 1 。 2 2 知识约简和知识的依赖性 知议约简和知识的依赖性是粗糙集理论中两个最基本的问题f 。知识约简是研究知识 库中每个等价关系是否都是必要的，以及如何删除不必要的知识。知识约简在机器学习、 信息系统分析与数据挖掘领域都具有重要的应用意义。知识之间的依赖性决定知识是否可 以进行约简，根据依赖性所定义的知识的重要性往往是知识约简的重要的启发式信息【1 l 】。 2 2 1 知识约简 知识约简中有两个基本概念：约简( r e d u c t 】和核( c o r e ) 。 定义2 5 令p 为一族等价关系，r p ，如果i n d ( p 一 r ) = i n d ( p ) ，则称关系且在p 中 是不必要的；否则称关系r 在p 中是必要的。 不必要的关系在知识库中是多余的，如果将它从知识库中删除掉，不会改变知识库的 分类能力；相反，如果从知识库中去掉一个必要的关系，则一定会破坏这个知识库的分类 能力。 9 山东师范大学硕士学位论文 定义2 6 令p 为一族等价关系，r p ，如果每个关系r p 在p 中都是必要的，则称 族集尸是独立的；否则称p 是依赖的。 对于依赖的关系族，其中包含有多余的关系，可以对其约简；而对于独立的关系族， 是不可以对其进行约简的。 通过以上的定义以及简单的推导，我们得到如下的定理： 定理2 2 如果p 是独立的，q p ，则称q 也是独立的。 证明：用反证法。假设q p 且q 是依赖的，则存在s c q ，使得i n d ( s ) = 砌( 9 ， 这就意味着 i n d ( s u ( p - q ) ) = i n d ( p ) ，s o ( p - q 1 c p 因此，是依赖的，这与已知条件是矛盾的，故定理得到了证明。 守义2 7 设u 是一个论域，尸、q 为定义在u 上的两个等价关系族，且q p ，如果 满足； ( 1 ) i n d ( p ) = m d ( q ) ； ( 2 ) q 是独立的。 则称q 是p 的一个约简( r e d u c t ) 。 定义2 8 设u 是一个论域，p 为定义在【，上的一个等价关系族，_ p 中所有必要关系组 成的集合，称为族集p 的核( c o p e ) ，记作c o r e ( p ) 。 通过以上的定义以及简单的推导，我们得到如下的定理： 定理2 3c o r e ( p ) = n r e d ( p ) ，其中的r e d ( p ) 表示族集p 的所有约简。 从上面的定理可以看出，核的用处有两个方面：第一，它可以作为所有约简的计算基 础，因为由核的定义我们知道，核包含在所有的约简