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

山东师范大学硕士学位论文 粗糙集理论在数据约简中的应用研究 摘要 数据挖掘面对的是大规模、超大规模的数据库或数据仓库，日益增长的海量数 据，给数据挖掘提出了新的挑战。随着数据挖掘技术研究的深入与成熟，在挖掘过 程中挖掘算法的效率提高越来越不明显，但是数据挖掘的预处理工作仍然没有明显 的提高。于是数据预处理工作就显得越来越重要。 数据预处理包括数据清理、数据集成和交换、数据约简等操作把原始的数据库 或者数据仓库变换成适合挖掘的模式，为进一步的数据挖掘做准备已有一些比较 成熟的数据预处理技术，但面对日益增长的海量数据和日趋复杂的数据结构数据预 处理还有很多工作要做 粗糙理论是用来处理模糊和不确定性知识的数学工具，是一种有效的软计算方 法。其主要思想是在保持分类能力不变的前提下，通过知识约简，导出问题的决策 或分类规则，利用区分矩阵可以方便地求出数据约简面对大数据集、或复杂的数 据结构，人们又提出了区分矩阵的改进算法，以及和其他学科相结合的算法，来提 高数据预处理的效率 属性约简是数据预处理的一个重要环节，已经证明求所有属性的最小约简是一 个n p 完全问题，所以，研究也只能从提高求约简的效率上来着手本文从基本的 粗糙集理论、数据预处理的基本知识入手，详细介绍了粗糙集约简的基本算法、一 种改进的算法，j e l o n e k 提出的基于属性重要性的算法，h u 提出的基于频率函数的 算法；以及与遗传算法相结合的算法、粗糙集约简的一种贪心算法，这些算法都在 一定程度上改进了基本的基于区分矩阵的属性约简算法，也都有其适应的特定环 境，合理地运用能够有效地对数据进行处理，进而提高数据挖掘的质量和速度 本文在总结前人的研究成果的基础上，提出了一种基于属性重要性的粗糙集约 简的并行算法，该算法借鉴文献【2 l 】赵斌等人提出的贪心算法，把求逼近精度和属 性重要性的工作合理地分配到多台处理机上分别计算，然后汇总数据，进而得到属 性集的约简，经过理论分析和模拟实验，证明该算法是可行的、有效的 关键词：数据挖掘，粗糙集，约简，数据预处理，区分矩阵 山东师范大学硕士学位论文 a 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 ar e d u c t i o n a b s t r a c t d a t am i n i n gd e a l sw i t hb i go rh u g cd a t a b a s eo rd a t aw a r e h o u s e s a st h ed a t a b a s e g r o w sl a r g e ra n dl a r g e r , d mi sf a c i n gn e wc h a u e n g e t lt h e s ed a y s t h et e e l m o l o g yo f d m h a sl a n dg r e a tp r o g r e s sa n db 嘲e sw e l l b u tt h e yh a v el e s sa n dl e s si n f e c t i o no nt h e e t t i c i a a e yo f d m d a t ap r e - p r o e e s s i n ga s 趾i m p o r t a n tc o u r o fd m p l a y sak e yp a r to fd m i t c o m p o s e sd a t ac l e a n i n g ，d a t ai n t e g r a t i o na n dc o m m u t a t i o n , d a t ar e d u c t i o na n ds o0 1 1 1 , a t t e rt h i sc o u i s et h ed a t aw i l lb ec h a n g e di n t ot h ef o r mt h a tw en e o 正s o m cm a t u r es k i l l s a l ea p p r o a c h e d b u ti no r d e rt od e a lw i t ht h cg r o w i n gg r e a tc a p a c i t yd a t aa n dc o m p l e x d a t as t r u c t u r em a n yw o r k ss h o u l db cd o n e r o l 啦s e tt h e o r yi sam a t h st o o lw h m au s e dt od e a lw i t hf u z z yu n c e r t a i n t y k n o w l e d g e i t sat e c h n i q u ef o re f f i c i e n c ys o t te o m p u d n g t h em a i ni d e ai so nt h eb a s i s o fk e e p i n gt h ea b i l i t yo fs o r t i n g ，u s i n gr e d u c t i o n , t og e tt h ed e c i s i o n - m a k i n gr u l e s w e c 粕g e tt h ed a t ar e d u c t i o ne a s i l yb yd i s e e r n i b i l i t ym a t r i x s o m ep e o p l ep u t sf o r w a r d s o m eu p s w i n gm e t h o d sb a s e d0 1 1 d i s e e m i b i l i t ym a t r i xa n d c o m b i n i n gt oo t h e rs u b j e c t st o d e a lw i t hm o l ec o m p l e xd a t a a t t r i b u t er e d u c t i o ni sa ni m p o r t a n tp a r to f d a t ap i o 部i n g i ti sp r o v e dt h a tt og e ta l l r e d u c t i o no ft h ea t t r i b u t ei sn - p - h a r d s ow es t a r tw i t hi m p r o v i n gt h ec f f i e i e n e yo f r e d u c t i o n i nt h i st h e s i sip r e s e n tr o u g hs e t sa n dd a t ap r e - p r o e e s s i n gt h e o r y t h e nt h e b a s i ca l g o r i t h m so fr o u g hs e t sa n dau p s w i n gm e t h o da r ea p p r o a c h e d a f t e rt h a ts o m e o t h e ra l g o r i t h m sa l et o l d ：s u c h 嬲j e l o n e k s ：aa l g o r i t h m sb a s e do na t t r i b u t e si m p o r t a n c e ； h u s ：aa l g o r i t h m sb a s e do nf r e q u e n c yf u n c t i o n a l g o r i t h m sc o m b i n e dt od e s c e n d i b l i t y m a t r i x ac u p i d i t ys t r a t e g y a l la b o v ea r i t h r a e t i ec a np r o v et h ee t t i e i e n e yo fr e d n c t i o l a w h i l eu s e dp r o p e r l y a n dt h e ) a r eb e t t e rt h a nt h eb a s i ca l g o r i t h m sb a s e do nd i s e e r n b i l i t y m a t r i x a tl a s t , ap a r a l l e lr o u g hs e tt h e o r yr e d u c t i o na l g o r i t h m sb a s e do na t l r i b u t e i m p o r t a n c ei sp r e s e n t e d l e a r n i n gf r o mc u p i d i t ys t r a t e g y , d i s t r i b u t et h et a s kt od i f f e r e n t m a e l a i n e s ，a n dg e tt o g e t h e rt h er e s u l t sf i o mt h e mt og e tt h ef i n a lr e d u c t i o n i ti sp r o v e dt o b ee t t i e i e n e yf r o mt h e o r e t i ca n df r o mt l a es i m u l a t ee x p e r i m e n t a t i o n k e y w o r d s ：i ) a t l m i n i n g , r o b g l as e t s ，r e d u c t i o n , d a t al 。r e - p r o e e u i n g , d i s c e r n i b i l i t yl l l t r i x 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得 ( 注：如 没有其他需要特别声明的，本栏可空) 或其他教育机构的学位或证书使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示谢意。 学位论文作者签名夕容。建军 导师签字： 学位论文版权使用授权书 掳司 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权堂撞可以将学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在 解密后适用本授权书) 学位论文作者签名夕笞l建筮 i 导师签字： 41 撕刽 签字日期：2 0 07 年夸月少日 签字r 期：2 0 07 年毒月力日 山东师范大学硕士学位论文 粗糙集理论在数据约简中的应用研究 第一章绪论 1 1 数据挖掘及数据预处理研究概述 数据挖掘是从大量数据中提取或“挖掘”知识它是人工智能、机器学习与 数据库技术等多学科相结合的产物，是信息技术自然演化的结果，它受数据库系 统、统计学、机器学习、可视化和信息科学等学科的影响。数据挖掘可以对多种 数据进行操作，如：关系数据库、数据仓库、事务数据库、高级数据库系统( 如； 面向对象的数据库、对象关系数据库、空间数据库、时间数据库和时间序列数 据库、文本数据库和多媒体数据库等) 、展开文件和w e b 自2 0 世纪6 0 年代以 来，数据库和信息技术已经系统地从原始的文件处理演化到复杂的、功能强大的 数据库系统。自7 0 年代以来，数据库系统的研究和开发已经从层次和网状数据 库系统发展到开发关系数据库而数据挖掘的正式研究是从1 9 8 9 年8 月举行的 第一届k d d ( k n o w l e d g e d i s c o v e r y i n d a t a b a s e ) 国际学术会议上提出的【i 】我国 的数据挖掘研究是从1 9 9 7 年我国国家自然科学基金首次支持该领域的研究项目 开始的十年来，国内的许多科研单位和高等院校竞相开展数据挖掘的基础理论 及其应用研究 2 1 ，并取得了丰硕的成果如国家图书馆的多库目录检索系统，清 华同方全文数据库检索系统等阴 一般研究者认为数据挖掘的过程而言，可以包括以下几个步骤： 1 ) 数据清理( 清除噪声或不一致数据) ； 2 ) 数据集成( 多种数据源可以组合在一起) ； 3 ) 数据选择与变换( 从数据库中检索与分析任务相关的数据并转换成适 合挖掘的形式) ； 4 ) 数据挖掘( 整个过程的基本步骤，使用智能方法提取数据模式) ； 5 ) 模式评估( 根据某种兴趣度度量，识别表示知识的真正有趣的模式) ； 6 ) 知识表示( 把数据挖掘的结果展示出来) 数据预处理是数据挖掘过程中的一个重要步骤，包括数据清理、数据集成和 转换、数据约简等。通过数据的预处理为数据挖掘提供高质量的数据和方便挖掘 山东师范大学硕士学位论文 的模式 随着数据挖掘技术研究的深入与成熟，在挖掘过程中挖掘算法的效率提高越 来越不明显，但是数据挖掘的预处理工作仍然没有明显的提高。据统计，在一个 完整的数据挖掘过程中，数据预处理要花费6 ( p 左右的时间。本文希望通过 粗糙集理论，结合已有的粗糙集约简的算法，提出一种更有效的数据约简方法， 以提高数据约简的速度和效率、减小算法的时间复杂度和空间复杂度 1 2 粗糙集理论研究现状 粗糙集是波兰数学家z p a w l a k 于1 9 8 2 年提出的一种数据分析理论，是用 来处理模糊和不确定性知识的数学工具巧3 。其主要思想是在保持分类能力不变的 前提下，通过知识约简导出问题的决策或分类规则。目前，粗糙集理论已被成功 地应用于机器学习、决策分析、过程控制、模式识别与数据挖掘等领域。结合其 他学科的研究成果，在数据的预处理过程中可以充分发挥它自身的优点，对属性 进行约简，从来达到数据预处理的目的当数据库特别大时，在单个处理机上进 行数据约简，可能花费很多时间，于是，基于并行计算的数据约简逐渐成为研究 的热点【2 8 1 。 虽然粗糙集理论到现在只有二十几年的研究历史，但取得的研究成果是令人 瞩目的。它是一种非常有前途的软计算方法，为处理不确定信息提供了强有力的 分析手段。现在的研究主要在于讨论粗糙集的代数性质与拓扑结构，以及粗糙集 的收敛性等问题。粗糙集在处理数据挖掘中，虽然已经取得了巨大的成果，但存 在着问题，如用知识库建立区分矩阵，当知识库较大时，效率会很低，甚至不可 行。又如属性频率函数启发算法，通常情况下可能求出的是最小属性约简的超集， 而属性集没有属核时求不出属性约简。 1 3 本文的研究和组织 本论文主要研究粗糙集理论在数据约简中的应用，通过对已经有的算法分析 研究和比较，总结各种算法的优缺点，并结合并行计算的思想，提出一种基于属 性重要性的粗糙集约简的并行算法。主要工作； 1 本文的第二章较详细的介绍了粗糙集理论的一些基本概念、基本性质、 2 山东师范大学硕士学位论文 粗糙集的一些基本算法，以及租糙集的几种常见的粗糙集模型；第三章简单介绍 了数据预处理的一些基本知识，包括：数据预处理的必要性、数据预处理得方法， 如：数据清理、数据集成和转换，并主要对数据约简以及约简方法作了分析和介 绍 2 对已有的基于粗糙集的属性约简算法进行了分析和总结，这一部分在文 中对应着第四章主要讲了：粗糙集用于属性约简的现状；粗糙集约简的基本算 法基于区分矩阵的约简算法；基于区分矩阵的启发式算法：基于属性重要性 的约简算法和基于频率函数的启发式算法；与其他学科相结合的算法：与遗传算 法相结合的算法和粗糙集约简的贪心算法 3 并行计算和粗糙集约简的一种并行算法这部分内容在文章的第五章， 可以分为三大部分1 ) 并行计算的简单介绍；2 ) 并行计算的p r a m 模型3 ) 基 于粗糙集约简的并行算法。其中前两部分都是为第三部分作铺垫的，第三部分也 是整篇论文的核心部分。 山东师范大学硕士学位论文 第二章粗糙集理论 粗糙集理论是一种新的处理模糊和不确定性知识的数学工具，其主要思想就 是在保持分类能力不变的前提下，通过知识约简，导出问题的决策或分类规则 目前，粗糙集理论已经成功地应用于机器学习、决策分析、过程控制、模式识别 与数据挖掘等领域 6 1 2 1 基本概念 2 1 1 知识与知识库 设u o 是对象组成的有限集合，称为论域。任何子集x e u ，称为u 中的 一个概念或范畴。( ，中的任何概念族称为关于u 的抽象知识，简称知识。一个 划分f 定义为：f = 五，丘，x 。 ；x ，u ，置m ，置n x ，；西，对于 j ，i , y = 1 , 2 ，- - h ；u 置= u l i l u 上的一族划分称为关于u 的一个知识库( k n o w l e d g eb a s e ) 。 设置是u 上的一个等价关系，u r 表示r 的所有等价类( 或者u 上的分类) 构成的集合，【明。表示包含元素x e u 的置等价类。一个知识库就是一个关系 系统k = ，r ) 其中u 为非空有限集，称为论域，r 是( ，上的一族等价关系。 若p c r 且p o ，则n p ( p 中的所有等价类的交集) 也是一个等价关系， 称为p 上的不可区分( i n d i s c e m i b i l i t y ) 关系，记为胁d ( 尸) 。且有p 】叫p ) = n 【x l r 朋， 这样，u _ f n d ( p ) ( 即等价关系f ，村( p ) 的所有等价类) 表示与等价关系族p 相关 的知识，称为足中关于u 的p 基本知识( p 基本集) 。为简单起见，我们用u p 代替u i n a ( ? ) ，跏d ( d 的等价类称为知识p 的基本概念或基本范畴。特别地如 果q r ，则称q 为k 中关于u 的q 初等知识，q 的等价类为知识r 的g 初等 概念或q 初等范畴。 4 山东师范大学硕士学位论文 事实上，p 基本范畴是拥有知识p 的论域的基本特性，换句话说，它们是知 识的基本模块同样，我们也可定义t 当x = ( 阢置) 为一个知识库，i n d ( a 3 定义为k 中所有等价关系的族，记作i n d ( 茁) = i n d ( p ) i ，p e 五) 2 1 2 粗糙集的定义及其性质 一、定义 令x u ，胄为u 上的一个等价关系，当工能表达成某些r 基本范畴的并 时，称j 是r 可定义的：否则称x 为震不可定义的矗可定义集是论域的子集， 也称作矗精确集，它可在知识库置中精确地定义；而震不可定义集不能在这个 知识库中定义，也称为盖非精确集或五粗糙集( r o u g hs e t ) 。当存在等价关系 r e 耐( x ) 且x 为r 精确集时，集合x e 称为置中的精确集；当对于任何 r e 伽d ( x ) ，x 都为置粗糙集时，则x 称为置中的粗糙集。 对于粗糙集可以近似地定义两个精确集，即粗糙集的上近似( 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 ) 对于 每一个子集x c u 和一个等价关系r e 删( 幻，定义两个子集： ： 墨x = u 】，e u r i 】，田，r x = u 】，e u r i y n x o ) 分别称它们为z 的r 下近似集和r 上近似集。 下近似、上近似也可用下面的等式表达： 星x = x u i f x 】re j ，r x = x e u i 【列rn z 中) 集合拥。( x ) = g x - 丛称为x 的边界域；p o s r ( x ) = 墨r 称为x 的置正域； n e g 月) = 【，一心称为z 的r 负域。显然：r x = 胛 ( x ) u b n ( 幻 鱼或p o s 。( 柳是那些根据知识r 判断肯定属于石的【，中的元素组成的集 合；兄r 是那些根据知识且判断可能属于x 的u 中的元素组成的集合；b n 。( z ) 是那些根据知识置既不能判断肯定属于j 又不能判断肯定属于一x ( 即u x ) 的u 中的元素组成的集合；甥。是那些根据知识胄判断肯定不属于x 的u 5 山东师范大学硕士学位论文 中的元素组成的集合。 二、性质 定理l ( 1 ) x 为置可定义集当且仅当丛= 面； ( 2 ) x 为r 粗糙集当且仅当i x 融。 从近似的定义，可以直接得到胄下近似集和上近似集的下列性质： 定理2 ( 1 ) 丛x 肼； ( 2 ) 舯= 肿= 西，= r u = u ； ( 3 ) 页uy ) = 融u 哥； ( 4 ) 星( x f ly ) = 趑n 掣： ( 5 ) x j ，j 墨r _ e r ； ( 6 ) z y j 劢e 7 0 ； ( 7 ) 墨( x u y ) ；丛u 矽。 ( 8 ) - ( z ny ) 砑n 西； ( 9 ) 墨( x ) 一勋； ( 1 0 ) k ( - z ) 一丛5 ( 1 1 ) 星( 查) = 矗( 量r ) = _ e x ； ( 1 2 ) r ( 兄幻= g ( e x ) = 兄r 。( 证明见参考文献6 ) 集合近似的概念导致了一个新的概念成员关系，因为在上面的方法中， 对于一个集合的定义是与集合的知识相关联的，所以成员关系一定也和知识有 关，可以形式地定义： 工岛x 当且仅当x e 丛： 疑r y 当且仅当x 腰； 这里墨。表示根据r ，x 肯定属于凰邑表示根据r ，x 可能属于兄分别称曼。和 一为下成员关系和上成员关系。成员关系依赖于我们的知识，即一个对象是否 6 山东师范大学硕士学位论文 属于一个集合依赖于我们的知识，并且这不是绝对特性由定理2 可以得到成员 关系的性质t 定理3 ( 1 ) x e x j j e 彳j 矗r l ( 2 ) x y j ( x 鹭；硝且联j 艇y ) ； ( 3 ) x e ( x u n 当且仅当x e x 或x e y l ( 4 ) x e _ ( x n 】，) 当且仅当x _ e x 且秽l ( 5 ) 矩或x e y 蕴x e ( x u 功； ( 6 ) x e ( x n n 蕴涵x e x 且x e y ； ( 7 ) x e _ 卜彳) 当且仅当埏x 不成立； ( 8 ) 难( x ) 当且仅当罐x 不成立。 为简单书写，以上定理中的式子中省略了下标且 2 1 3 约简与核 知识约简是粗糙集理论的核心内容之一我们知道，知识库中的知识( 属性) 并不是同等重要的，对于特定的应用( 决策) ，可能用到的属性并不相同有些 属性可能是冗余的，所谓知识约简，就是在保持知识库分类能力不变条件下，删 除其中不相关或不重要的知识( 属性) 知识约简有两个基本概念：约简和核。 令且为一族等价关系，r e r 如果i n d ( r ) = m a ( r 一 r ) ) ，则称f 为r 中不 必要的；否则称掣为胄中必要的如果每个r e r 都为足中必要的则称r 为独 立的；否则称r 为依赖的 设q e p 如果q 是独立的，且矗1 d ( q ) = i n d c p ) ，则称q 为p 的一个约简。显 然，户可以有多种约简，中所有必要关系组成的集合称为尸的核，记作c o r e ( p ) 核与约简有如下关系； 定理3c o r e ( p ) = n r e d ( e ) ，其中r e d ( p ) 表示p 的所有约简 证：( 1 ) c o r e ( p ) n r e d ( p ) 设r c o r e ( p ) ，则需要证明r n r e d ( p ) 若 7 山东师范大学硕士学位论文 rf 、r c d ( p ) ，则存在某个q r e d ( p ) ，使得r 叠q 从而有q c p 一 母， i n d ( q ) ) i n d ( p 一 r ) 2i n d ( p ) 而我们知道，i n d ( q ) f f i i n d ( p ) ( q 是p 的一个约简) 于是： i n d ( p 一 r ) ) f f i i n d ( p ) ，这说明r 在p 中是不必要的，即足叠c o r e ( p ) ，矛盾 ( 2 ) c o r e ( p ) 2 f k e d ( p ) 设r e f i r e d ( p ) ，则需要证明r g c o r e ( p ) 。若 矗叠c o r e ( p ) 。则r 在p 中是不必要的，于是有i n d ( p 一 r ) f i n d ( p ) 。另外，因 为约简总是存在的，而p - r 有一个约简p 0 ，从扁p 一 埘知r t 扁，p - r ) 的 约简p 0 满足： 1 ) i n d ( p o ) = i n d ( p - r ) t 2 ) 如果户c 扁，贝i | i n d ( p 一 r ) ) f f i i n d ( p ) ，这两个条件可以重写为： l ) i n d ( p o ) = i n d ( p ) ： 2 ) 如果p c 岛，则i n d ( p ) = i n d ( ”) ，因为马p 一 哪c p ，所以，p 0 是p 的一个约简，因此，存在某个q r e d ( e ) ，使得p 戒，因此r 叠q ，从而 r e r 陆e d ( p ) ，矛盾。 可以看出，核这个概念的用处有两个方面：首先它可以作为所有约简的计算 基础，因为核包含在所有的约简中，并且计算可以直接进行；其次可解释为在知 识约简时它是不能消去的知识特征集合。 2 1 4 知识表达系统 知识表达在智能数据处理中占有十分重要的地位形式上，四元组 s = ，彳，矿，力是一个知识表达系统，其中： 矾对象的非空有限集合，称为论域； 彳：属性的非空有限集合； 矿= u 圪，圪是属性的值域： 8 山东师范大学硕士学位论文 f ：u x a _ y 是一个信息函数，它为每个对象的每个属性赋予一个信息值， 即v a e a ，工e u ，f ( x ，口) e r o 知识表达系统也称为信息系统，通常也用跹阢爿) 来代替s = ( ( ，a ，矿，力。 知识表达系统的数据以关系表的形式表示。关系表的行对应要研究的对象，列对 应对象的属性，对象的信息是通过指定对象的各属性值来表达。一个属性对应一 个等价关系，个表可以看作是定义的一族等价关系，即知识库。通过这种转换 可以把知识的约简转化为属性约简。 2 1 5 决策表 决策表是一类特殊而重要的知识表达系统多数决策问题都可以用决策表形 式来表达，决策表在决策应用中起重要作用对于知识表达系统s = ( 以彳，) ， 彳= c u d ，c n d = 中，c 称为条件属性集，d 称为决策属性集，具有条件属 性和决策属性的知识表达系统称为决策表。 在决策表中不同的属性具有不同的重要性。知识约简就是根据属性的不同重 要性，去掉那些不重要或者冗余的属性，从而使得属性集更简洁，更有意义 般的方法是从条件属性中去掉一些属性，再考察没有该属性后分类会不会发生变 化。如果去掉某一属性相应分类变化较大，则说明该属性是重要的，约简中应当 包含该属性或者该属性可能是核( 或核中的属性) ；否则属性是不重要的 2 1 6 区分矩阵和区分函数 利用区分矩阵可以方便地表达知识，并且利用区分函数，可以容易地计算约 简和核。下面给出区分矩阵的构造和利用区分矩阵进行约简的方法 给定知识表达系统：s - - ( u ，a ，v ，力，i ( ， 一( 1 卅代表对象集合中对象的个 数) ，s 的区分矩阵是一个一x 一的矩阵，其任一元素为； 口( 五力= 口e a i f ( x ，口) f ( y ，口) ) 即a ( x ，力是区别对象x 和y 的所有属性集合。为了求属性的约简，下面引入 一个布尔函数。称其为区分函数( d i s c e r n i b i l i t yf u n c t i o n ) ，用表示，对每个属 9 山东师范大学硕士学位论文 性d e a ，指定一个布尔变量。a ”，如果a ( x ，力= ( a l ，a 2 ，m o 则指定一个布 尔函数口l v a 2 v 口t ，用烈毛力来表示；g g a ( x , y ) = o ，则指定布尔常量1 ( 布 尔) 区分函数可定义如下： = 1 7 4 力 ( z , y ) e l l x ；1 区分函数有如下性质：函数的极小析取范式中的所有合取是属性集a 里的 所有约简核是区分矩阵中所有单个元素组成的集合即： c o r e ( a ) = 口a i 口阮力= 口) ，其中x , y u 。 这样就可以很容易通过对属性进行构造区分矩阵，通过区分函数求出约简后 属性，为进一步的数据挖掘做准备，但是直接利用区分矩阵和区分函数求属性的 约简对于简单的属性表还可以，对于较复杂的决策表就会“力不从心。了。现在 已经有很多基于区分矩阵和区分函数的改进算法，将在本文后面的章节讲到。 2 2 粗糙集模型的算法 粗糙集方法已经被成功应用于分类问题、决策分析、求属性重要性和核以及 属性约简，对于粗糙理论的应用而言，设计有效的算法是非常重要的。下面介绍 几种基于决策表的粗糙集模型算法。如算法p 和算法i 都可以用来求属性的分类； 算法l 可以用来求下近似；算法r 可以求上近似。 2 2 1 算法p 算法p 给出知识系统的一个分类。设( u ，a ) 是一个信息系统，对于每一 个属性口ea ，引入一个u 中的划分u a ：两个对象虬l ，e u 在同一类中当且仅当 口( ”) = 口( v ) 算法p ： 对于信息系统( 玑一) ，设( ，- - u ，“2 ，“m ，算法p 对于口a 给出了分 类。使用下面的指针：j 指向当前的输入对象1 , 1 1 ；j 记录已经找到的j 个类 k ，e ；_ ，取值l ，2 ，j ，用来检验当前的输入对象是否有口( ”) = 口( v ) 1 0 山东师范大学硕士学位论文 如果对于某个，有口( ”) = 口，则令蜥在巧中；虬e 巧；否则，建立一个新 类，j 唧+ l ，e = “ 当算法结束时，我们有划分u l a = k ，巧，以) 具体 算法如下， s t 印l ：( 初始化) 令t 卢l ，产l ，k = “ ： s t e p 2 ：如果卢lu i ，分类结束。便可以得到分类：u a = k ，e ； s t 印3 ：如果k i 硼，则令：卢件l ，产j + l 。继续； s t y ：如果产s ，令s = s + l ，并建立新类圪= 溉 ，转s t c p 2 。如果，勺，则 令产_ ，+ l ，继续； s t y 5 ：如果口( 机) = 口( 巧) ，则巧= 扣j ，转s t e p 2 ；否则，转s t e p 4 该算法对于每个属性逐步的判断对信息系统进行分类。该算法的优点是算法 相对简单，整个算法需要进行l + 2 + ( i ( ，i 1 ) ；d 门硼2 ) 次比较因此，算法的复 杂性为d r l 硼2 ) 。 2 2 2 算法l 。 算法l 给出信息系统的一个子集的下近似。设矽e u ，对于分类u a ，定义 w 的下近似，为矿“= u r t c ，。y 妒y ，也用s 功表示。子集( 叨称为w 关于 属性a 的支持子集，司( 矿) 爿缈) l i u i 称为形关于属性口的支持度，同样， 对于分类u a 定义形的上近似为矽7 4 广= u r 彬，。r n - r y 算法l ： 设( 仉0 ) 是一个信息系统，令u l a = f i ，既，圯 ，1 a s q u i ，口e a ， e c ，。 s t 印1 ：( 初始化) 令产l ，= o ； s t 印2 ：如果巧e 矽，则令三= 三u u ，否则继续； s t e p 3 ；如果_ ，可，算法结束，矽( v a ) - = 工。否则继续； s t 印4 , 令_ ，影 l ，返回s t c p 2 。 i i 山东师范大学硕士学位论文 很明显，该算法的复杂性为线性的。即只和子集n 的个数有关 2 2 3 算法r 根据算法l ，类似地可以设计一个求集合上近似的算法设( u ，彳) 是一 个信息系统u a t k ，屹) ，i - - - s s i u i ，矿u 算法r 给出了矿关于 u a 的上近似矿7 矿= u p 。( ，。, l v n r 矿。 s t e p l ：( 初始化) 令产l ，r = o ； s t e p 2 - 如果n 矿 中，则令r = r u ，否则继续； s t e p 3 ：如果，哪，算法结束，w w 4 ) t = r 否则继续； s t e p 4 ：令产= + l ，返回s t e p 2 。 显然，该算法的复杂性也为线性的，只和子集个数有关 以上给出的三个算法，虽然简单，但是给处理大型数据库、数据仓库中的数 据实现求分类、上、下近似带来了很大方便，而且可以实现数据的自动化处理。 为以后的数据挖掘做准备。 2 3 几种常用的粗糙集模型 p a w l a k 提出的粗糙集模型，在很多实际问题中，就会受到这样那样的限制， 于是产生了几种实际应用中的一般关系下的租糙集模型。包括变精度粗糙集模 型、概率粗糙集模型、模糊粗糙集模型、基于随机集的粗糙集模型等。下面几节 分别对这几种粗糙集模型简要介绍。 2 3 1 变精度粗糙集模型 粗糙集理论的中心问题是分类分析，p a w l a k 粗糙集模型的一个局限性是它 所处理的分类必须是完全正确的或者肯定的，因为它是严格按照等价类来分类 的，因而它的分类是精确的，即：“包含”或“不包含”，而没有某种程度上的“包 含”或者“属于”而p a w l a k 粗糙集模型的另一个局限性是它所处理的对象是已 知的且从模型中得到的所有结论仅仅适用于这些对象集。但在实际应用中，往往 需要将一些小规模的对象集中得到的结论应用到大规模的对象中去。 山东师范大学硕士学位论文 2 3 1 1 多数包含 为了引入变精度粗糙集模型，先要了解一下什么是多数包含关系 设x 和y 表示有限论域u 的非空子集如果对于每一个口e 石有口ej ，则 称y 包含卫记作l ，2 x 令 眠d = 岳i x n y t l l x l , i i 姑 其中因表示集合x 的基数。称c ( x , d 为集合x 的关于集合y 的相对错误分类 率。即如果将集合x 中的元素分到集合】，中，则做出分类错误的比例为： 口d 1 0 0 ，真正错分类的元素数目为c 】，) 冈称c 玲因为绝对分类 误差 令o s 口 o 5 ，多数包含关系定义为：】，三j c ( x ，1 9 s “多数”要求 隐含着x 与y 中的公共元素的数目大于x 中元素数目的5 0 显然，y x 当 且仅当c ( x 。1 9 = 0 2 3 1 2 变精度粗糙集 有了多数包含的定义，在基本粗糙集模型的基础上引入一个变量 p ( o s o 5 ) ，就可以对粗糙集重新定义设( 阢置) 为近似空间，其中论域 【，为非空有限集合，震为u 的等价关系，u i r = 蜗，垦，e 为胄的等价类或基 本集构成的集合。对于x u ，定义j 的下近似为： _ r p = u e e u i r l x 三毋，或者= u e u i r i c ( e 柳仍 岛x 也称为正区域，记为p o s r # ( x ) 。 定义x 的夕上近似为： 邱= u e e u i r lc ( e j 0 l - p 定义石的，边界域为： b n r # = u e e u i rj c ( e j ) l - 所 定义石的负域为： 山东师范大学硕士学位论文 n e g r p ( x ) = u ( e e u r l c ( e ，柳l - p j 的正区域( 或x 的下近似) 可以理解为将【，中的对象以不大于夕的 分类误差分于x 的集合。石的p 负区域相应理解为将u 中的对象以不大于p 的 分类误差分于j 的补集( _ 功的集合 2 ：3 1 3 近似约简 属性约简是粗糙集模型中最重要的概念之一，也是本文的重点之一条件属 性集关于决策属性集q 的约简或挖约简是p 的一个子集r e d 以q ) ，且满足： ( 1 ) r ( p ，幺) = r ( r e d ( p ，q ，) ，q ，卢， ( 2 ) 从r e d ( p , q , ) 中去掉任何一个属性，都将使( 1 ) 不成立。 其中，r e d ( p , q , ) 表示决策属性集q 与条件属性集p 的依赖性。引入 p ( o s 。 x 关于如依参幽的概率( i ) 型正域，边界和负域分别为： p o s ( x ，口，夕) = ! 鬯。( 。d = x u i p ( x l 【x 】) 口) ， b n ( x ，o t ，) = x u l p ( x i 【朋) 口， n e g ( x ，口，刃= u p i p = 工e u i ，( _ 幻i l 硼) 当p _ l 。( x ) = p i p ( x ) 时，或者等价地当b 墨口，历= m 时，称z 依参数凶 关于4 概率( 1 ) 型可定义集，否贝称x 依参数粥关于4 概率( i ) 型租糙集。 特殊地，当口= 1 ，= 0 时，概率( i ) 型的上近似和下近似就和p a w l a k 提出的 上近似和下近似统一成同一种表示。因此，概率粗糙集模型是p a w l a k 粗糙集的 推广形式。但它的边界要比p a w l a k 粗糙集的边界小，正域和负域都比p a w l a k 的 正域和负域大，因为概率( i ) 型粗糙集允许将p a w l a k 粗糙集边界中条件概率大 于零小于l 的某一部分等价类也计入到它的正域里面，还将其边界中一部分并入 到它的负域中去其应用也更加广泛。 2 3 3 模糊粗糙集模型 模糊集理论是美国计算机与控制论专家l a z a d e h 于1 9 6 5 年提出来的。目 前，以模糊推理为核心的人工智能技术在许多领域取得了明显的成果和经济效 益。结合模糊集理论，把经典粗糙集理论加以推广就可以得到模糊粗糙集理论定 义下面分别介绍模糊集和模糊粗糙集。 山东师范大学硕士学位论文 经典集合是一个分明集合，它对应着二值逻辑，即一个论域中的对象或者属 于这个集合或者不属于这个集合，二者必居其一但是实际问题中，有些关系就 不能用二值逻辑来表示例如。张三跑的快，李四跑的慢”这里“快”和“慢” 之间并没有明确的界限，在一定意义下它是一种过渡状态为了描述类似的不分 明的状态，引入隶属函数的概念所谓论域u 上的一个隶属函数是指u 到【o ，l 】 的一个映射。论域【，上的一个模糊集合彳是由【，上的一个隶属函数4 ：u 一 0 ，1 】 来表示，其中彳表示元素x 隶属于模糊集合a 的程度 这样，对于论域u 上的对象工和( ，上的一个模糊集合彳，就不能简单地说j 是绝对属于还是不属于，而只是说工在多大程度上属于4 ，隶属度4 正是x 属于彳的程度的数量指标，若j 4 ( 玲旬，则认为苫完全不属于4 ，若彳o ) = 1 ，则认 为x 完全属于；若o ( 彳l l ，则说x 以程度彳属于彳 对于给定的近似空间，足是论域【，上的一个等价关系，一为u 上的一个模 糊集合，彳关于( u 固的一对下近似4 ，和上近似一一定义为u 上的一对模糊集合， 如果。= a r ，则称a 为可定义的，否则称彳为模糊粗糙集。称4 。是彳关于( “回 的正域，称4 一是a 关于( u r ) 的负域，称彳一n ( 4 。) 为彳的边界。 模糊集和粗糙集都有可以用来描述