（计算机软件与理论专业论文）基于粒计算的决策表属性约简.pdf

山东大学硕士学位论文 詈= ! 詈1ii i i_i_iiii ! 詈! 詈詈 摘要 近年来，随着信息处理技术的广泛应用，使各行各业的电子化迅速普及，产 生了海量数据信息，如何获取和发现有价值的信息并将其运用于生产实践中非常 关键。因此，一个能够分析数据并且可以智能提取信息的研究领域知识发现 ( k n o w l e d g ed i s c o v e r y ) 应运而生并得到迅速发展，其中数据挖掘( d a t am i n i n g ) 成 为当前知识发现的主要研究课题之一。 属性约简在数据挖掘或数据分析过程中有着重要的意义。一个信息系统或决 策表可能有多个约简，而且约简后属性的个数将直接影响后续数据分析中规则模 型的规模。人们希望找出信息系统或决策表的最小约简，但是求解最小约简已被 证明是一个n p 问题。 通过研究目前主要几种属性约简算法，发现多数算法选择从计算核心属性开 始，按照各属性的重要程度逐渐扩大待求属性集，不同的属性重要度定义派生出 不同的属性约简算法，主要有基于s k o w r o na 的区分矩阵的属性约简算法；基于 属性重要性的约简算法；基于信息熵的属性约简算法等方法。本文比较分析了目 前几种主要不同属性约简算法的设计方法，在粗糙集和粒计算理论基础上，就如 何实现信息系统和决策表基于属性重要程度的约简算法做了进一步研究。本文的 具体工作如下： 1 、提出了一种新的知识相对分布的度量方法。从粗糙集理论认为知识是区 分事物能力的角度出发，利用属性之间具有不同区分能力的特点，给出一种新的 度量知识的方法，其分布函数主要基于知识粒之间直观的分布变化，在此基础上 提出了相对分布度的概念，用来考察属性间知识分布变化情况，之后分析了其合 理性，并给出了相关性质。在相对分布概念的基础上，为了约简后产生具有更加 确定性的规则，提出了联合相对分布度的概念。 2 、提出了两种属性约简方法。一是在决策信息系统下基于相对分布度的属 性约简算法。该算法利用相对分布度重新定义了属性的重要度，将属性重要度作 为启发式信息，设计了相关约简算法。二是以联合相对分布度定义了属性重要度， 并设计了相关约简算法。通过实例分析两种算法的特点及时间复杂度。 山东大学硕士学位论文 3 、通过对标准数据进行了测试实验，研究了算法的执行效率；与同类算法 相比较，分析了各自的优缺点，验证了算法的可行性和有效性。 最后，概括了本文的主要结果，说明本文工作的理论意义和应用价值，指出 本文的不足和有待进一步解决的问题。 关键词：粗糙集；粒计算；决策表；属性约简：相对分布 i i 山东大学硕士学位论文 a b s t r a c t i nr e c e n ty e a r s ，、) v i t l law i d er a n g eo fi n f o r m a t i o np r o c e s s i n gt e c h n o l o g y a p p l i c a t i o n sa n dt h ep r e v a l e n c eo fe l e c t r o n i c f a c i l i t i e si ni n d u s t r y ，t h e r ei sah u g e a m o u n to fd a t ai n f o r m a t i o n i t sv e r yc r i t i c a lf o rp e o p l et od i s c o v e rh o wt oo b t a i n v a l u a b l ei n f o r m a t i o nt h a ti sa p p l i e dt op r o d u c t i o ni nd a i l yl i f e t h e r e f o r e ，an e w r e s e a r c hf i e l do fa n a l y z i n gd a t aa n de x t r a c t i n gi n t e l l i g e n c ei n f o r m a t i o no o m ei n t o b e i n ga n dd e v e l o p eq u i c k l y ，t h a ti sc a l l e d k n o w l e d g ed i s c o v e r y t h e d a t am i n i n g h a sb e c o m eo n eo ft h em a i nr e s e a r c ht o p i c so f t h ek n o w l e d g ed i s c o v e r y a t t r i b u t er e d u c t i o ni nd a t am i n i n go rd a t aa n a l y s i sh a sa ni m p o r t a n ts i g n i f i c a n c e a ni n f o r m a t i o ns y s t e mo rd e c i s i o nt a b l em a yh a v em a n yr e d u c t i o n s ，b u tr e d u c t i o n r e s u l t sw i l ld i r e c t l ya f f e c tt h ed a t aa n a l y s i sa n dt h er u l e so ft h em o d e l p e o p l eh o p et o i d e n t i f yi n f o r m a t i o ns y s t e m so rd e c i s i o nt a b l eo ft h em i n i m a lr e d u c t i o n ，b u tt h e m i n i m a lr e d u c t i o ns o l u t i o nh a sb e e np r o v e dt ob ea nn pp r o b l e m b ys t u d y i n gs e v e r a lm a i na t t r i b u t er e d u c t i o na l g o r i t h m s ，m o s ta l g o r i t h m ss t a r t f r o mt h ec a l c u l a t i o no ft h ec o r ea t t r i b u t ea n de x p a n dt h ea t t r i b u t es e tg r a d u a l l y a c c o r d i n gt od i f f e r e n ti m p o r t a n td e g r e e so fa t t r i b u t e t h e r ea r ed i f f e r e n td e f i n i t i o n so f a t t r i b u t er e d u c t i o na l g o r i t h m , m a i n l yb a s e do nt h es k o w o mad i s t i n c t i o nm a t r i x a t t r i b u t er e d u c t i o na l g o r i t h m , b a s e do nt h ei m p o r t a n c eo fa t t r i b u t er e d u c t i o na l g o r i t h m ， b a s e do ni n f o r m a t i o ne n t r o p yr e d u c t i o na l g o r i t h ma n do t h e rm e t h o d s i nt h i sp a p e r , w eg i v eac o m p a r a t i v ea n a l y s i so ft h ec u r r e n ts e v e r a lm a i nd i f f e r e n c e sa t t r i b u t e r e d u c t i o na l g o r i t h ma n dd oaf u r t h e rs t u d yo nh o wt or e a l i z et h ei n f o r m a t i o ns y s t e m s a n dd e c i s i o nt a b l er e d u c t i o na l g o r i t h mb a s e do nr o u g hs e t sa n dg r a n u l a rc o m p u t i n g t h e o r i e s t h em a i na c h i e v e m e n t so ft h i sd i s s e r t a t i o ni n c l u d e ： 1 an e wk n o w l e d g em e a s u r e m e n ti sp r e s e n t e d b a s e do nt h ev i e w p o i n tt h a t a t t r i b u t e sh a v ed i f f e r e n td i s c e m i b l ea b i l i t yi nr o u g hs e tt h e o r y ；t h ec o n c e p to f k n o w l e d g er e l a t i v ed i s t r i b u t i o ni sp r o p o s e df i r s t l y i t sd i s t r i b u t i o nf u n c t i o ni sb a s e d o n t h ei n t u i t i o n i s t i cd i v e r s i f i c a t i o no fd i s t r i b u t i ：o na m o n gd i f f e r e n tk n o w l e d g eg r a n u l e s a n di t sp u r p o s ei st h a tw ec a l lo b s e r v et h es i t u a t i o no fk n o w l e d g ed i s t r i b u t i o nc h a n g e b e t w e e nd i f f e r e n ta t t r i b u t es e t s w ea n a l y z er a t i o n a l i t yo ft h ed e f i n i t i o n ，a n dg i v e s o m ec o r r e l a t i v ep r o p e r t i e s m o r e o v e r ，b a s e do nt h ec o n c e p to fk n o w l e d g er e l a t i v e i i i 山东大学硕士学位论文 d i s m b 们o n ，u n i t e dr e l a t i v ed i s t r i b u t i o ni sd e f i n e di no r d e rt oo b t a i nm o r ec e r t a mr u l 铺 a f t e rr e d u c t i o n 2 t w od i f f e r 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 m si ni n f o r m a t i o ns y s t e ma r e p r o p o s e d t h ef i r s ta l g o r i t h mr e d e f i n e sa t t r i b u t ei m p o r t a n c ea c c o r d i n gt ot h er e l a t i v e d i s t r i b u t i o na n dt a k e st h en e wa t t r i b u t ei m p o r t a n c ea sh e u r i s t i ci n f o r m a t i o na n d d e s i g n sah e u r i s t i cr e d u c t i o na l g o r i t h m ；t h eo t h e ra l g o r i t h mr e g a r d su n i t e dr e l a t i v e d i s t r i b u t i o na sa t t r i b u t ei m p o r t a n c ea n dah e u r i s t i cr e d u c t i o na l g o r i t h mi sp r e s e n t e d f r o mt h ee x a m p l e ，t h ea l g o r i t h m ss u p e r i o r i t yh a sb e e nc o m p a r e da n dt h ea l g o r i t h m c h a r a c t e r i s t i ch a sb e e na n a l y z e d 3 t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h ea l g o r i t h mi se f f i c i e n c ya n df e a s i b i l i t y ， a n dc o m p a r ea d v a n t a g e sa n dd i s a d v a n t a g e so ft h ea l g o r i t h m s a tl a s t ，a l le x p e r i m e n t a l s y s t e mh a sp e r f o r m e do nt h er e a ld a u t f i n a l l y ，t h ew o r ko ft h i sd i s s e r t a t i o ni ss u m m a r i z e da n dt h e o r e t i c a ls i g n i f i c a n c e a n d p o t e n t i a la p p l i e dv a l u eo ft h er e s e a r c ha r ee x p l a i n e d , s o m ed e f i c i e n c i e sa n dt h e p r o s p e c t i v eo ff u t m er e s e a r c hi sd i s c u s s e d k e y w o r d s ：r o u g hs e t io r a n u l a ro o m p u t i n g ；d e c i 5 i o nt a b i e ；a t t r i b u t e s r e d u o i o n ：r e i a t i g od i s t r i b u t i o n 原创性声明和关于学位论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律责任由本人承担。 论文作者签名：望堑盈日期：丝翌：! ! ：兰 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：遑纽导师签名魈堕么期：出 山东大学硕士学位论文 1 1 引言 第一章绪论 近年来，随着计算机、网络和通信等信息技术的高速发展，信息处理技术的 广泛应用，各行各业电子化迅速普及，产生了海量数据信息，面对日益增长的海 量数据，如何获取和发现有价值的信息并将其运用于生产实践非常重要。传统的 统计数学分析手段只能获取数据的表层信息，而不能在对数据充分理解的基础上 获得数据背后的内在关系和隐含信息，这样人们就无法理解并有效地使用这些数 据。人们迫切地感到需要新的技术和工具在大量数据中智能且自动地抽取出有价 值的知识或信息，使宝贵的数据资源得到充分利用。所以，一个能够分析数据并 且可以智能提取信息的研究领域知识发现( k n o w l e d g ed i s c o v e r y ) 应运而生 并得到迅速发展，其中的数据库知识发现即数据挖掘( d a t am i n i n g ) 成为当前知识 发现的主要研究课题。 自波兰科学家z p a l a w k 教授提出粗糙集理论后，粗糙集理论作为一个处理 不确定、不精确、不完备信息的数学工具，在人工智能和认知科学，特别是在智 能信息处理方面，如知识的表达与推理、数据分析、知识发现、机器学习、知识 获取、决策分析、过程控制等领域得到了广泛的应用。粒计算( g r a n u l a r c o m p u t i n g ，简称g r c ) 是在过去几十年中，人们在专家系统、知识工程、人工 神经网络、模糊集合等众多领域不断实践和探索的过程中提出的一种新的智能信 息处理理论，它覆盖了所有有关粒的理论、方法、技术和工具的研究。粒计算既 是模糊信息粒度、粗糙集、商空间、区间计算等诸多理论的超集，也是粒数学的 子集。由于粒计算能有效地分析和处理模糊、不精确、不一致的问题，现已成为 国际上人工智能研究的重要方法之一。同时，在机器学习、模式识别、数据挖掘、 知识发现、模糊和智能控制、语意w e b 服务等众多领域，粒计算都有着广泛的 应用前景。 山东大学硕士学位论文 1 2 研究现状 1 2 1 租糙集理论 本世纪7 0 年代，从事关于信息系统逻辑特性研究的波兰学者z p a w l a k 1 3 - 1 5 提出了粗糙集相关理论。1 9 8 2 年，z p a w l a k 发表了经典论文r o u g hs e t s 1 3 】，标 志着粗糙集理论的诞生。此后，粗糙集理论引起了许多数学家、逻辑学家和计算 机研究人员的兴趣，他们在粗糙集理论和应用方面作了大量研究工作。1 9 9 1 年 出版z p a w l a k 的专著【1 4 】，对粗糙集在一段时期内的理论和实践工作成果作了较 好的总结，同时促进了粗糙集在各个领域的应用。此后召开与粗糙集有关的国际 会议进一步推动了粗糙集的发展。 国内粗糙集理论的研究开始于1 9 9 4 年，王钰、苗夺谦等b3 ，8 】在我国引入粗 糙集理论方面作出了重要贡献。张文修、梁吉业、吴伟志等1 4 , 1 0 ，4 3 1 提出了基于随 机集的粗糙集模型，并研究了粗糙集理论同包含度理论之间的关系。马志锋、刑 汉承等在粗糙控制方面作了深入的研究。但总体来说，粗糙集在国内的研究起步 较晚，其研究主要集中于理论方面，成功开发及应用的案例较少。 粗糙集理论是一个强大的数据分析工具。它仅利用数据本身提供的信息，不 需要任何先验的或附加的数据信息，这与其它分析方法相比有很大优势。而其它 方法往往需要一些数据的附加信息或先验信息，如模糊集中模糊隶属函数和概率 分布，d e m p s t e r s h a f e r 理论中基本概率赋值等，但是这些信息有时并不容易得到。 基于此，粗糙集理论能够分析隐藏在数据中的事实，方便地获取确定和可能规则 知识，表达和处理不完备信息：可以在保留关键信息的前提下对数据进行化简并 求得知识的最小表达式；能够识别并评估数据之间的依赖关系，揭示出概念简单 的模式；此外，粗糙集理论能够从经验数据中获取易于证实的规则知识，特别适 合于智能控制。 目前，对粗糙集理论及其应用的研究主要集中在以下几个方面： ( 1 ) 粗糙集的数学性质 粗糙集理论数学性质方面，主要研究粗糙集的代数结构与拓扑结构，以及粗 糙逻辑、粗糙收敛性、粗糙集的分析性质等。一些新的数学概念不断出现，如粗 糙半群、粗糙群、粗糙函数、粗糙微积分等。随着粗糙结构、代数结构、拓扑结 2 山东大学硕士学位论文 构、序结构等各种结构的不断整合，将推动粗糙集理论的快速发展，刺激产生新 的有生机的数学分支。 ( 2 ) 粗糙集模型的推广模型 粗糙集理论在进行数据分析时，常常会遇到噪声、空值等情况，传统的粗糙 集方法己无法解决，因而各种粗糙集的扩展模型应运而生。针对空值，一些研究 者提出了不完备信息决策表【4 l4 2 1 ，建立了不完备决策表的属性约简【4 2 1 和核的定 义m 1 ，以及相关的属性约简算法【4 5 】。对于不一致决策表，为了实际需要，一些 学者提出了变精度粗糙集模型【l g l ，它对经典粗糙集的上近似集和下近似集概念进 行了改进，使得这一模型在处理不确定数据时，更符合实际。 粗糙集自身发展的同时，与其它理论方法，如神经网络 4 6 1 、模糊集1 7 1 、 信息论【4 刀等相互融合集成，有效地提高知识挖掘能力。 粗糙集在处理数据挖掘中，虽然已经取得了巨大的成果，但仍存在着问题， 如用知识库建立区分矩阵，当知识库较大时，效率会很低，甚至不可行。又如属 性频率函数启发算法，通常情况下可能求出的是最小属性约简的超集，而属性集 没有属性核时求不出属性约简。 1 2 2 粒计算理论 自z a d e h1 9 7 9 年发表论文“f u z z ys e t sa n di n f o r m a t i o ng r a n u l a r i t y t l 6 】”以来， 研究人员对信息粒度化的思想产生了浓厚的兴趣。z a d e h 认为很多领域都存在信 息粒的概念，只是在不同领域中存在的表现形式不同。自动机与系统论中的“分 解与划分”，最优控制中的“不确定性”，区间分析里的“区间数运算，以及 d s 证据理论中的“证据”都与信息粒有密切的联系。后来，h o b b s 在1 9 8 5 年 直接用粒度( g r a n u l a r i t y ) 这个词作为论文题目在国际人工智能联合会议上发表论 文2 7 1 ，讨论了粒的分解与合并，以及如何得到不同大小的粒，并提出了产生不同 大小粒的模型。 l i n 主要研究二元关系( 邻域系统、粗糙集和信任函数) 下的粒计算模型， 论述了基于邻域系统的粒计算在粒结构、粒表示和粒应用等方面的问题，给出了 粒计算中的模糊集和粗糙集方法【6 ，7 1 ，并将粒计算方法引入数据挖掘和机器发现 领域。依据人们在解决问题时能从几个不同粒度世界去分析和观察同一个问题， 并且很容易地从个粒度空间转到另一个粒度空间的模型，张钹和张铃在1 9 9 0 3 山东大学硕士学位论文 年针对复杂问题求解，从仿生学的观点提出了问题求解理论，建立了一种商结构 的形式化体系，给出一套解决信息融合、启发式搜索、路径规划和推理等问题的 理论和算法，并已有一些相关研究和应 1 , 2 8 1 。 1 9 9 7 年z a d e h 进一步指出，世上有三个基本概念构成人类认识的基础：粒 化、组织及因果关系【1 7 1 。总体来看，粒化是整体分解为部分，组织是部分结合为 整体，而因果关系则涉及原因与结果间的联系。物体粒化产生一系列的粒子，每 个粒子即为一簇点( 物体) ，这些点难以区别，或相似、或接近、或以某种功能 结合在一起。在l i n 的研究基础上，y a o 结合邻域系统对粒计算进行了研究1 1 1 ， 挣3 5 1 ，并将它应用于知识挖掘等领域，建立了概念之间的i f t h e n 规则与粒度 集合之间包含关系的联系，并提出利用由所有划分构成的格求解一致分类问题， 为数掘挖掘提供了新的方法和视角。结合粗糙集理论，y a o 探讨了粒计算方法在 机器学习、数据分析、数据挖掘、规则提取、智能数据处理和粒逻辑等方面的应 用。y a o 给出了粒计算的三种观点【3 5 】： ( 1 ) 从哲学的角度看，粒计算是一种结构化的思想方法； ( 2 ) 从应用的角度看，粒计算是一个通用的结构化问题求解方法； ( 3 ) 从计算的角度看，粒计算是一个信息处理的典型范例方法。 为了探讨粗糙理论在各种环境下的应用，建立粗糙集理论在各个专业领域中 的应用前景，s k o w r o n 2 2 3 6 1 以包含度概念来研究粒近似空间上的粗糙下近似和粗 糙上近似，发表了一系列关于信息粒和粒计算的文章。2 0 0 2 年苗夺谦等b3 ，8 1 对 知识的粒度计算进行了探讨，引入属性重要度的概念以及在求最小约简方面的应 用，并提出了协调度的概念以及在构造决策树方面的应用。王国胤 3 7 - 4 0 等提出 了基于容差关系的粒计算模型，使用属性值上的容差关系给出了不完备信息系统 的粒表示、粒运算规则和粒分解算法，同时结合粗糙集中的属性约简问题，提出 了不完备信息系统在粒表示下属性必要性的判定条件，并对粒计算方法在规则提 取方面作了尝试性的应用研究。粒计算方法的应用也越来越广泛，已经渗透到自 然科学和社会科学的很多领域。 总的来说粒计算是一种理论，一套方法学，一种技术，是在处理过程中使用 粒子来描述空间或求解问题的工具，它使得空间描述或问题求解更加可行。粒计 算覆盖了凡是可以用到粒子进行研究的相关领域。 4 山东大学硕士学位论文 1 3 论文研究内容 本文主要研究属性约简算法及其实现。针对包含大规模真实数据的信息决策 系统，设计了两种不同的属性约简算法，并且对两种算法进行了实验分析和比较。 研究主要内容如下： l 、提出了一种新的知识相对分布的度量方法。从粗糙集理论认为知识是区 分事物能力的角度出发，利用不同属性间区分能力大小不同的特点，给出了一种 新的度量有效知识量的方法，其分布函数基于直观的知识粒度分布变化特性，通 过分析度量的合理性，给出了相关性质，并且在知识量的基础上，提出了相对分 布度的概念，用来考察属性间知识的变化情况。在此基础上为了进一步获得既有 高准确度、又有高覆盖度的规则集，提出了一种基于覆盖度和准确度联合指标作 为重要度衡量信息的知识度量方法，称其为联合相对分布度，并将其作为属性重 要度的量度。 2 、提出了两种属性约简方法。一是在决策信息系统下基于相对分布度的属 性约简算法。该算法利用相对分布度重新定义了属性的重要度，将属性重要度作 为启发式信息，设计了相关约简算法。二是以联合相对分布度定义了属性重要度， 并将其作为启发信息，并设计了相关约简算法。通过实例分析两种算法的特点及 时间复杂度。 3 、通过对标准数据进行了测试实验，研究了算法的执行效率；与同类算法 进行比较，分析了各自的优缺点，验证了算法的可行性和有效性。 1 4 论文组织结构 围绕属性约简的相关内容，本文做了探索性工作。组织结构如下： 第一章首先介绍分析了粗糙集和粒计算理论的研究现状和特点，说明了选题 的意义和研究目标。最后给出了本论文的主要研究内容和成果。 第二章分别介绍粗糙集与粒计算的相关理论，以及两种理论相互结合形成的 基于粗糙集的知识粒表示方法，为下一步基于粒计算的属性约简研究奠定理论基 础。 第三章首先分析了决策表属性约简有代表性的典型算法，给出了两种不同的 属性重要度度量算法：一种是以属性相对分布作为属性重要度的启发式算法；另 山东大学硕士学位论文 一种是基于知识依赖，以覆盖度和准确度的综合评价为基础的启发式算法。最后 根据实例对两种算法进行比较，并且分析了算法的特点。 第四章使用u c i 部分数据集对提出的算法进行实验，根据实验结果比较两 种算法的效率和性能，并且分析了算法的特点。 第五章对课题研究做了客观总结，以及有待进一步的研究内容。 6 山东大学硕士学位论文 2 1 粗糙集理论 第二章粗糙集与粒计算 粗糙集理论是一种处理不精确、不确定与不完全数据的数学工具。该理论建 立在分类机制基础上，将分类理解为在特定空间上的等价关系，而等价关系构成 了对该空间的划分。其主要思想是在保持分类能力不变的前提下，通过知识约简， 导出问题的决策或分类规则。与其它处理不确定和不精确问题理论的最显著的区 别，是它无需提供问题所需处理的数据集合之外的任何先验信息，所以对问题的 不确定性的描述或处理可以说是比较客观的，由于这个理论未能包含处理不精确 或不确定原始数据的机制，所以这个理论与概率论、模糊数学和证据理论等其他 处理不确定或不精确问题的理论还有很强的互补性。 2 1 1 知识与不可区分关系 设研究对象组成的是一个非空有限集合，称为论域，记作u ，即u o 是讨 论的论域。任何子集x 互u ，称为u 中的一个概念或范畴。【厂中的任何概念族 称为关于【厂的抽象知识，简称知识。 一个划分孝定义为：善= 五，x 2 ，以) ；置u ，置，x ；n x ，= o ， 一 对于f ，i ，j = l ，2 ，l ；u = u 。 i = i u 上的一族划分称为关于u 的一个知识库( k n o w l e d g eb a s e ) 。 设r 是u 上的一个等价关系，u r 表示r 的所有等价类构成的集合，【乩；表 示包含元素x u 的r 等价类。一个知识库就是一个关系系统k = ( u ，口) ，其中u 为非空有限集，称为论域，口是u 上的一族等价关系。 若pc 口且p g ，则n 尸( p 中的所有等价类的交集) 也是一个等价关系， 称为p 上的不可区分( i n d i s c e m i b i l i 锣) 关系，i 已为r o d ( p ) ，且有卜】砌( 即= nt x 】。 r e p 这样，u m d ( p i ) ( 即等价关系m d ( p ) 的所有等价类) 表示与等价关系族p 相关 的知识，称为k 中关于u 的p 基本知识( p 基本集) 。使用u p 代替u i f n d ( p ) ， 7 山东大学硕士学位论文 i n d ( p ) 的等价类称为知识p 的基本概念或基本范畴。特别地如果o 口，则称q 为q 中关于u 的q 初等知识，q 的等价类为知识口的9 初等概念。 事实上，尸基本范畴是拥有知识尸的论域的基本特性，即它们是知识的基本 模块。同样，也可定义：当k = ( u ，口) 为一个知识库，i n d ( k ) 定义为k 中所有等 价关系的族，记作i n d ( k ) = i n d ( p ) i o p c r 。 2 1 2 粗糙集与上近似、下近似 令x u ，r 为u 上一个等价关系。当x 能表达某些尺基本范畴的并时， 称x 是尺可定义的：否则称x 为月不可定义。r 可定义集是论域的子集，它可 以在知识库足中精确定义。尺可定义集是论域的子集，也称作尺精确集，而尺不 可定义集不能在这个知识库中定义，也称为尺非精确集或尺粗糙集( r o u g hs e t ) 。 当存在等价关系r i n d ( k ) 且x 为r 精确集时，集合x u 称为k 中的精 确集；当对于任何r m a ( k 1 ，x 都为r 粗糙集，则x 称为足中的粗糙集。 对于粗糙集可以近似地定义为两个精确集，即粗糙集的上近j 以( 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 = ，口) ，对于每一 个子集x u 和一个等价关系r i n d ( k ) ，定义两个子集： 厨= u y u ry x ，斟= u eu r yn x o 分别称它们为x 的r 下近似集和r 上近似集。下近似、上近似也可用下面 的等式表达： r x = z ul 【z 】尺x ) ，1 0 ( = x uj x 】rn x o 集合6 ( 朋= 厨一麟称为x 的边界域：p o s r ( x ) = _ r x 称为x 的r 正域； n e g r ( x ) = u 一厨称为x 的r 负域。显然面= 肛( x ) u ( 。 掣或p o s r ( x ) 是那些根据知识r 判断肯定属于x 的u 中的元素组成的集 合；面是那些根据知识尺判断可能属于x 的u 中的元素组成的集合；6 ( 朋是 那些根据知识尺既不能判断肯定属于x 又不能判断肯定属于口x ( 即u x ) 的 u 中的元素组成的集合；n e g r ( x ) 是那些根据知识r 判断肯定不属于x 的u 中 的元素组成的集合。上近似、下近似是粗糙集的重要概念。正域是粗糙集理论特 山东大学硕士学位论文 有的概念，其最初的目的是试国解决不确定知识的描述域测量以便建立不确定 推理模型。 上近似、下近似以及边界域的之间的关系可以用图1 表示 垂 o x n # 一x 下i 罐( 芷城) x 的上、下近似之差 ( 边界域) x 的负域 图21 论域c ，中子集x 的上、下近似及边界域 粗糙集的表示只是由两个精确集近似地衰示。这种近似的大小是可咀刻画 的。由上圈可以看出粗糙集的不精确性是由于边界域的存在而引起的。集合的边 界域越大，精确性越低，粗糙度越大。如果边界域为空集，刚粗糙集就称为精确 集。 粗糙集理论中，不精确的数值不是预先假定的，而是通过表达知识不精确性 的概念近似计算得到的，这种不精确性的数值表示的是有限知识( 知识的粒度性) 的结果。粗糙集理论不需要预先指定一个精确数值去表达不精确的知识。 2 1 3 知识约简 知识库中的知识( 属性) 不具有同样的重要性，甚至其中某些知识属于冗余。 知识约简就是在保持知识库分类能力不变的条件下，删除其中不相关或不重要的 知识，是粗糙集理论的核心内容之一。 定义2 l 令口为一族等价关系，r e 口，如果耐佃) = m d ( d 一两，则称r 为 口中不必要的：否则称r 为口中必要的。如果每一个r 口都为口中必要的，则 称口为独立的：否则称口为依赖的。 山东大学硕士学位论文 设oc _ p ，如果q 是独立的， i n d ( q ) = i n d ( p ) ，则称q 为尸的一个约简。 根据这个定义可以知道，约简有三方面性质：首先，约简所表达的对系统的划分 与原来的知识库所形成的划分是完全一致的，即约简所表达的知识和原来的知识 具有相同的表达能力：其次，是独立性，即最小性，约简是能够表达原来的知识 库的最小集合，约简后不可能再进行约简；第三，是多样性，显然尸可以有多种 约简。 尸中所有必要关系组成的集合称为尸的核，记作c o r e ( p ) 。核与约简有如下 关系：c o r e ( p ) = n r e d ( p ) ，其中心d p ) 表示尸的所有约简。核概念的作用是作 为所有约简计算的基础，因为核包含在所有的约简中，并且计算可以直接进行： 可解释为在知识约简时是不能消去的知识特征集合。 在应用时，一个分类相对于另一个分类的关系十分重要，上面的概念是一个 分类中所表达的知识的粒度性。下面介绍知识的相对约简( r e l a t i v er e d u c t ) 和相对 核( r e l a t i v ec o r e ) 的概念。 q 的pi e 域是p o s e ( q ) = u 蹦l x e u i q 。 q 的p 正域是【，中根据分类u p 的信息可以准确地划分到知识q 的等价类 中的对象集合。即q 的p 正域是由知识尸所产生的等价类所组成的集合，这些等 价类能够完全地属于知识q 。 若p o s 尸( q ) = p o s p - ( r ) ( q ) ，称尺为p 中q 不必要的：否则r 为p 中q 必要的。 如果尸中的每个r 都为q 必要的，则p 为q 独立的。 相对约简是设s p ，称s 为尸的q 相对约简，当且仅当s 为p 的q 独立子 族，且p o s s ( q ) = p o s p ( q ) 。由该定义可以知道相对约简一方面可以表示原来的 知识，即和原来的系统的分类能力一样；另一方面它又不包含重复的知识，每个 知识都是必要的。也就是说，相对约简是能够表示原有知识的最小集合。同时相 对约简有多个。 相对核是p 中所有q 必要的原始关系所组成的集合，称为p 的q 核。记为 c o r e q ( p ) 。 相对核与相对约简的关系是( p ) = n 旭屹( p ) ，其中r e d q ( p ) 是所有p 的 q 相对约简构成的集合。即相对核是所有相对约简的交集。 山东大学硕士学位论文 相对核的作用是作为所有相对约简计算的基础，因为相对核包含在所有的相 对约简之中，并且计算可以直接进行；也可以解释为它在知识约简时不能消去的 知识特征集合。 2 1 4 知识依赖性 知识的依赖性可形式化定义如下：令k = ( u ，r ) 是一个知识库，p ，q r 。 ( 1 ) 知识q 依赖于知识p ( 记作p j q ) 当且仅当m d ( p ) i n d ( q ) 。 ( 2 ) 知识p 与知识q 等价( 记作p 兰q ) 当且仅当pjq 且q p 。 ( 3 ) 知识p 与知识q 独立( 记作p q ) 当且仅当p j q 与q j p 均不成 立。 当知识q 依赖于知识p 时，也可以说知识q 是由知识p 导出。有时候知识的 依赖性是部分的，可由知识的正域来定义。 令k = ，r ) 为一知识库，且p ，q r 。当七= y r ( q ) = 竺等时， 称知识q 是k ( o k 1 ) 度依赖于知识p ，记作pj 。q 。 当k = l 时，称q 完全依赖于p ；当0 k l 时，称q 粗糙( 部分) 依赖于p ； 当后= 0 时，称q 完全独立于p 。由依赖性的定义可知，当p j 。q 时，由q 导出 的分类u q 的正域覆盖了知识库中k x l 0 0 个元素；另一方面，只有属于分类 正域的元素能被唯一的分类，即对象的k x l 0 0 可以通过知识p 划入分类u q 的模块中。系数y r ( q ) 可以看做是q 和p 间的依赖度。 2 1 5 信息系统与决策表 知识表达系统也称为信息系统，在数据处理中有着十分重要的地位。形式上， g 阮g gs = ( u ，a ，v ，f ) 是一个知识表达系统( 通常用s = ( u ，彳) 代替) ，其中： u ：对象的非空有限集合，称为论域； 么：属性的非空有限集合； 矿= u 圪，圪是属性口的值域； a a - a f ：u x a 专矿是一个信息函数，它为每个对象的每个属性赋予一个信息值， 即v a a ，x u ，f ( x ，口) 圪 山东大学硕士学位论文 知识表达系统的数据以关系表的形式表示。关系表的行对应要研究的对象， 列对应对象的属性，对象的信息是通过指定对象的各属性值来表达。一个属性对 应一个等价关系，一个表可以看作是定义的一族等价关系，即知识库。通过这种 转换可以把知识的约简转化为属性约简。 决策表是一类特殊而重要的知识表达系统。多数决策问题都可以用决策表形 式来表达，决策表在决策应用中起着重要的作用。对于知识表达系统 s = ( u ，a ，v ，) ，a = c u d ，c n d o ，c 称为条件属性集，d 称为决策属性 集，具有条件属性和决策属性的知识表达系统称为决策表。 在决策表中不同的属性具有不同的重要性。知识约简就是根据属性的不同重 要性，去掉那些不重要或者冗余的属性，从而使得属性集更简洁。从条件属性中 去掉一些属性，再考察没有该属性后分类会不会发生变化。如果去掉某一属性相 应分类变化较大，则说明该属性是重要的，约简中应当包含该属性或者该属性可 能是核：否则不重要。 令c 和d 分别是条件属性和决策属性集，属性子集c 。c 关于d 的重要性 定义为( c ) = 您( d ) 一r c ) ，特别当c 。= a ) 时，属性口c 关于d 的重要 性为( 口) = y c ( d ) 一您一 。 ( d ) 。 2 2 粒计算理论 粒度计算( g r a n u l a rc o m p u t i n g ) 是信息处理的一种新的概念和计算范式，覆盖 了所有有关粒度的理论、方法、技术和工具的研究，主要用于处理不确定的、模 糊的、不完整的和海量的信息。粗略地讲，一方面它是模糊信息粒度理论、粗糙 集理论、商空间理论、区间计算等的超集，另一方面是粒度数学的子集。具体地 讲，凡是在分析问题和求解问题中，应用了分组、分类和聚类手段的一切理论与 方法均属于粒度计算的范畴，对它的研究引起了人们的关注，已成为人工智能领 域新近研究的热点方向之一。 粒度计算思想实质是用简单易求、低成本的足够满意近似替代精确解，即利 用不精确、不完整、不确定和海量信息的可容度来实现智能系统或智能控制的易 处理、鲁棒性、低代价和更好地刻画现实世界。 1 2 山东大学硕士学位论文 2 2 1 粒计算的基本概念 粒计算研究的对象所具有的结构称为粒结构，主要组成成分包括粒、层次及 分层结构。粒度计算主要关注两个基本问题，一个是如何构造粒度，另一个是怎 样用粒度进行计算。前者研究粒度的形成( f o r m a t i o n ) 、表示( r e p r e s e n t a t i o n ) 和解释 ( i n t e r p r e t a t i o n ) ，而后者则讨论问题求解过程中粒度的使用问题。下面介绍粒计算 中的几个基本概念。 一、粒的描述 粒是粒度计算中最基本的概念。基本粒没有十分确切的定义，可以称最小的、 不可或不需要再分解的粒为基本粒。一个粒可以被解释为是由多个小的粒子组成 的较大的单元。它与给定的粒度标准有关系。也可以