（计算机应用技术专业论文）粗糙集与vague集的理论及应用研究.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 粗糙集理论是近年来发展起来的一种有效的处理不精确、不确 定、含糊信息的数学理论方法。其解决问题的出发点是信息系统 中知识的不可分辨性。v a g u e 集理论是一种新型的处理模糊信息的 数学工具，由w l g a u 和d j b u e h e r 于1 9 9 3 年提出。v a g u e 集本 质上是f u z z y 集的扩展，但与f u z z y 集相比较，它能更好和更准 确的表达模糊信息，在处理模糊信息方面更具有优势。 粗糙集的一个重要应用是对信息系统进行降维处理( 也就是 知识约简) ，信息系统降维包括数据约简和属性约简。决策表是一 类特殊而重要的信息系统。多数决策问题都可以用决策表的形式 表达，这一工具在决策应用中起着重要的作用。本文在分析了目 前决策表属性约简方法的缺点后，提出了一种新的方法，即基于 等价类的属性约简法，并用v c c + + 实现了该方法；在充分研究了 决策表的性质后，分别给出了相容决策表与不相容决策表的所需 元素个数，这对数据采集有着指导意义；另外，讨论了完备决策 表与不完备决策表属性约简之间的关系，这对于不完备决策表的 属性约简有着重要意义，并给出了一种新的不完备决策表属性约 简方法。 模糊熵的概念最早由z a d e h 提出，它是一种描述模糊信息量 的工具。在模糊集理论和v a g u e 集理论中模糊熵都是研究重点 之一，它是将模糊集理论和v a g u e 集理论应用于模糊聚类、模式 识别、图像处理等基础。本文在分析了目前v a g u e 集模糊熵构造 方法的缺点后，提出了一种新的构造法。 虽然粗糙集理论和v a g u e 集理论都是研究信息系统中信息的 不确定性问题，但两者的出发点、特点等都不同，它们之间是互 补的关系。目前将粗糙集理论和模糊集理论进行结合研究的文献 很多，但笔者还没有看见将粗糙集理论和v a g u e 集理论进行结合 研究的文献，于是，本文将粗糙集理论和v a g u e 集理论进行结合， 给出了粗糙v a g u e 集概念，并讨论了粗糙v a g u e 集的模糊熵、粗 糙度、相似度量等问题，另外对广义粗糙v a g u e 集的构造与公理 化进行了研究。最后将粗糙v a g u e 集理论应用到v a g u e 决策表的 属性约简。 关键词粗糙集；v a g u e 集；粗糙v a g u e 集；知识约简；模糊熵 西南交通大学硕士研究生学位论文第1 l 页 a b s t r a c t r o u g hs e ti s8v a l i dm a t h 印a t i c a lt h e o r yd e v e l o p e di nr e c e n ty e a r s w h i c hh a st h e8 b i l i t yt od e a lw i t hi m p r e c i s e ，u n c e r t a i n ，a n dv a g u e i n f o r m a t i o n t h es t a r tp o i n to fr o u g hs e tt h e o r ys o l v i n gp r o b l e m si s i n d i s c e r n i b l en a t u r ek n o w l e d g ei ni n f o r m a t i o ns y s t e m v a g u es e ti s an e wm a t h e a t i c a lt h e o r yp r o v i d e db yw l g a ua n dd j b u e h e ri n 1 9 9 3 ，w h i c hh a st h ea b i l i t yt od e a lw i t hv a g u ei n f o r m a t i o n i nn a t u r e ， v a g u es e ti sd e v e l o p m e n to ff u z z y s e t i n c o i i l p a r i s o nw i t hf u z z ys e t ，v a g u es e ti sb e t t e rf o re x p r e s s i n g v a g u ei n f o r m a t i o np r e c i s e l y ， a n dh a st h ep r e p o n d e r a n c ei n p r o c e s s i n gv a g u ei n f o r m a t i o n a ni l p o r t a n ta p p l i c a t i o no fr o u g hs e ti st or e d u c et h e d i m e n s i o no fi n f o r m a t i o ns y s t e m ( i e k n o w l e d g er e d u c t i o n ) t h ek n o w l e d z er e d u c t i o ni n c l u d e sd a t ar e d u e t i o na n d a t t r i b u t er e d u c t i o n d e c i s i o nt a b l ei sas d e c i a la n d i m p o r t a n ti n f o r m a t i o ns y s t e m m a n yd e c i s i o np r o b l e m sc a nb e e x d r e s s e dw i t hd e c i s i o nt a b l e ，a n dt h i st 0 0 1c o n t r i b u t e st o d e c i s i o na p p l i c a t i o n t h i sp a p e ra n a l y s e st h ed i s a d v a n t a g e o ft h ep r e s e n td e c i s i o na t t r i b u t er e d u c t i o n ，a n da n e wm e t h o d i sp r o p o s e d ，w h i c hi sa t t r i b u t er e d u c t i o na p p r o a c hb a s e do n t h ee q u i v a l e n tc l a s s e s a n dt h i sa p p r o a c hi si 叩l e m e n t e db y v c c 十十a f t e rs t u d y i n gp r o p e r t i e so fd e c i s i o nt a b l ef u l l y ， t h en u 加b e ro fe l e m e n t sn e e d e df o rb o t hc o m d a t i b l ed e c i s i o n t a b l ea n di n c o m p a t i b l ed e c i s i o nt a b l ea r ei n t r o d u c e d ，w h i c h p l a y sa ni m p o r t a n tr 0 1 ei nd a t ac 0 1 l e c t i n g b e s i d e s ， t h e r e l a t i o n s h i po fa t t r i b u t e r e d u c t i o nb e t w e e n c o m p l e t e d e c i s i o nt a b l ea n di n c o m p l e t ed e c i s i o nt a b l ei sd i s c u s s e d ， w h i c hh a sa ni m p o r t i n gm e a n i n gf o ra t t r i b u t er e d u c ti o no f i n c o l p l e t e d e c i s i o nt a b l e ，a n da n e wm e t h o do fi ti s p r e s e n t e d t h ec o n c e p to ff u z z ye n t r o p yw a sp r o p o s e db yz a d e he a r l y ， a n di t i sat 0 0 1o fd e s c r i b i n gf u z z yi n f o r m a t i o na m o u n t i n t h ef u z z ys e tt h e o r ya n dv a g u es e tt h e o r y ， f u z z ye n t r o p yis o n eo ft h em o s ti m d o r t a n tr e s e a r c h e s a n di ti n t r o d u c e st h e f u z z ys e tt h e o r ya n dv a g u es e tt h e o r y t ot h ea p p l i c a t i o n 西南交通大学硕士研究生学位论文第l ii 页 o f f u z z yc l u s t e r i n g ，p a t t e r ni d e n t i f i c a t i o n ，i 们a g e m a n i p u l a t i o na n ds oo n t h ep a p e ra n a l y s e st h ed e m e r i t so f t h ep r e s e n tf u z z ye n t r o p yc o n s t r u c t i n gm e t h o do fv a g u es e t ， a n dp r o v i d e san e wa p p r o a c h t h o u g hr o u g hs e ta n dv a g u es e tt h e o r ya r eu s e dt os t u d y t h ei n f o r m a t i o nu n c e r t a i n t yi nt h ei n f o r m a t i o ns y s t e m s ，t h e s t a r t i n gp o i n ta n dc h a r a c t e r i s t i c so fb o t ha r ed i f f e r e n t ， a n dt h e ya r ec o 叩l e e n t a r y n o wt h el i t e r a t u r e sa b o u tt h e f u s i o ns t u d yb e t w e e nf u z z ys e ta n dr o u g hs e ta r en u m e r o u s ， b u tt h el i t e r a t u r e sa b o u tt h ef u s i o ns t u d yb e t w e e nv a g u es e t a n dr o u g hs e ta r el i t t l e s or o u g hv a g u es e tt h e o r yi s p r e s e n t e da f t e rf u s i o ns t u d yb e t w e e nv a g u es e ta n dr o u g hs e t a n dt h ef u z z ye n t r o p y 、r o u g h d e g r e e 、 s i m i l a r i t ym e a s u r e so f r o u g hv a g u es e ta r ef u r t h e rs t u d i e d i na d d i t i o n ，t h e c o n s t r u c t i o na n da x i o m a t i cr e s e a r c ho fg e n e r a l i z e dr o u g h v a g u es e ta r ed is c u s s e d a tl a s tt h ep a p e ra p p li e st h er o u g h v a g u es e tt h e o r yt ot h ea t t r i b u t er e d u c t i o no fv a g u ed e c i s i o n t a b 】e k e y 咖d s ：r o u g hs e t ：v a g u es e t ：r o u g hv a g u es e t ：k n o w l e d g e r e d u c t i o n ；f u z z ye n t r o p y 西南交通大学硕士研究生学位论文第1 页 1 1 粗糙集理论 第一章绪论 1 1 1 粗糙集提出背景及研究现状 粗糙集理论是一种处理含糊、不精确性问题的新型数学工具， 由波兰的p a w l a k 教授于2 0 世纪8 0 年代初提出，近年来受到国内 外众多学者的重视。 经典逻辑中只有真、假二值，但实际上有大量含糊现象存在 于真与假之间。因此，长期以来许多逻辑学家和哲学家就致力于 研究含糊概念。早在1 9 0 4 年，谓词逻辑的创始人g f r e g e 就提出 了含糊一词，并把它归结到边界线，也就是说在全域上存在一些 个体既不能在其某个子集上被分类，也不能在该子集的补集上被 分类。2 0 世纪6 0 年代初，l a z a d e h 提出了模糊集，不少理论计 算机科学家和逻辑学家，试图通过这一理论解决g f r e g e 的含糊 概念，但遗憾的是，模糊集是不可计算的，没有给出数学公式描 述这一含糊概念，故无法计算出它的边界线上的具体的含糊元素 数目。8 0 年代初，z p a w l a k 针对g f r e g e 的边界线区域思想提 出了粗糙集，他把那些无法确认的个体都归于边界线区域，而这 种边界线区域被定义为上近似集和下近似集之差集。由于上近似 集和下近似集都可以通过等价关系给出确定的数学公式描述，所 以含糊元素数目可以被计算出来，即在真假二值之间的含糊程度 可以计算，从而实现了g f r e g e 的边界线思想。粗糙集理论主要 兴趣在于它能以不完全信息或知识去处理一些不分明现象的能 力，或依据观察、度量到的某些不精确的结果而进行分类数据的 能力。 粗糙集理论自问世以来，无论是在理论或应用上都是一种新 的、最重要的并且迅速发展的研究领域。它在知识发现、机器学 习、知识获取、决策分析、专家系统、决策支持系统、归纳推理、 矛盾归结、模式识别、模糊控制等方面的成功应用，引起了各国 学者的广泛关注。1 9 9 1 年p a w l a kz 出版了专著 4 7 ，系统全面 地阐述了粗糙集理论，奠定了严密的数学基础。该书与1 9 9 2 年出 版的粗糙集理论应用专集 4 8 较好地总结了这一时期粗糙集理论 西南交通大学硕士研究生学位论文第2 页 与实践的研究成果，促进了它的进一步发展，现已成为学习和应 用粗糙集理论的重要文献。自1 9 9 2 年在波兰k i e l a z 召开了第一 届粗糙集国际研讨会后，每年都召开 l _ 祖糙集为主题的国际会议， 推动了粗糙集理论的拓展和应用。1 9 9 4 年国际上成立了粗糙集学 会( i n t e r n a t i o n a lr o u g hs e ts o c i e t y ) ，参加的成员来自波兰、 美国、加拿大、日本、挪威等多个国家。1 9 9 5 年a c m c 0 珊u n i c a t i o n 将粗糙集列为新出现的计算机科学的研究课题。目前粗糙集理论 已成为信息科学最为活跃的研究领域之一。粗糙集研究在我国的 发展也很快，在粗糙集的理论研究及应用方面取得了一定的研究 成果，出现了一定数量的相关文献和专著。 1 1 2 粗糙集理论的特点 1 ) 粗糙集不需要先验知识。模糊集和概率统计方法是处理不 确定信息的常用方法，但这些方法需要一些数据的附加信息或先 验信息，如模糊隶属函数和概率分布等，这些信息并不容易得到。 粗糙集分析方法仅利用数据本身提供的信息，无须任何先验知识。 2 ) 粗糙集是一个强大的数据分析工具。它能表达和处理不 完备信息；能在保留关键信息的前提下对数据进行化简并求得知 识的最小表达式；能识别并评估数据之间的依赖关系，揭示出概 念简单的模式：能从经验数据中获取易于证实的规则知识，特别 适于智能控制。 3 ) 粗糙集与模糊集分别刻化了不完冬信息的两个方面。粗 糙集以不可分辨关系为基础，侧重分类，模糊集基于元索对集合 隶属程度的不同，强调集合本身的含糊性。从粗糙集的观点看， 粗糙集合不能清晰定义的原因是缺乏足够的论域知识，但可以用 对清晰集合逼近。虽然粗糙集和模糊集特点不同，但它们之间 有着密切的关系，有很强的互补性。粗糙集和证据理论也有一些 相互交叠之处，在实际应用中可以相互补充。 1 2 v a g u e 集理论 1 2 1v a g u e 集提出背景 随着社会和科学技术的发展，人们在对某个事情或事件进行 珏南交通大学硕士研究生学位论文第3 页 判断、推理、预测、决策时，历面对的信息常常是不精确的、不 完全的、或模糊的，这就要求我们在计算机中模拟人的智能行为 时，计算机能够处理这类信息。为此，在c o n t o r 的集合论的基础 上，美国学者l a z a d e h 于1 9 6 5 年提出了模糊集理论，在模糊集 中，一个对象( 元素) 是否属于某个模糊集的隶属函数可以在 0 ，1 中取值，这就突破了传统的二值逻辑的束缚。近3 0 多年来，模糊 集理论在模糊决策、模糊专家系统、特别是在模糊控制等众多智 能系统中得到了广泛的应用，并取得了令人瞩目的成就。 模糊集理论最基本的特征是：承认差异的中间过渡，也就是 说承认渐变的隶属关系，即一个模糊集爿是满足某个( 或几个) 性 质的一类对象，每个对象都有一个互不相同的隶属于爿的程度， 隶属函数，“) 给每个对象分派一个0 和1 之间的数作为它的隶属 度。但是，要注意的是隶属函数给每个对象分派的是 o ，1 中的一 个单值，这个单值既包含了支持z 爿的证据，也包含了反对工爿 的证据。这显然是不合理的。 为了解决上述模糊集理论的不足，g a u 和b u e h r e r 于1 9 9 3 年 提出了一个新的处理模糊信息的模糊理论一v a g u e 集。v a g u e 集 本质上是模糊集的扩展，但与模糊集相比较，它能更好和更准确 的表达不确定信息，在处理不确定信息方面更具有优势。在v a g u e 集中，用一个真隶属函数f 。0 ) 和一个假隶属函数，。0 ) 来描述其 隶属度的边界，这两个边界就构成了 0 ，1 的一个子区间 o ) 卜厶o ) 。0 0 ) 表示对一个对象的支持度，厶o ) 表示反对度， 卜 ) 一厶o ) 就表示未知度( 既不支持也不反对) 。 1 2 2v a g u e 集理论研究现状 v a g u e 集理论为处理模糊、不精确、不完全数据提供了一种 新的数学工具，现已广泛应用于数据挖掘、机器学习、知识发现、 近似推理、决策分析、人工智能、医疗诊断系统等领域，并取得 了很好的效果。但v a g u e 集理论毕竟提取的时间还很短，所以 v a g u e 集理论还不够系统、完善，还需要进一步的研究。 西南交通大学硕士研究生学位论文第4 页 1 3 粗糙集理论及v a g u e 集理论发展前景 1 3 1 粗糙集理论的发展前景 不确定性是姐糙集理论的关键词，它涉及集合论定义中的许 多实质性内容。集合的近似定义是现代数学中的重要概念之一， 而与布尔逻辑非常相关的经典集合论又是数字计算机运算的核 心。众所周知，许多实践问题不能满足现在计算机的求解条件， 特别是机器学习、模式识别以及某些控制问题等，这种困难常常 使得不能建立描述个体的算法。而粗糙集理论及其扩充对于建立 此类个体的近似描述，提供了一种精确的数学技术。 可以预言，粗糙集方法将在数据挖掘和软计算，特别是处理 大型数据库和复杂问题等方面，显示出“英雄有用武之地”的气 魄。特别对于从数据中提取各种格式的关联规则的研究尤其重要。 在数据挖掘和知识发现中，可利用各种知识源和各种知识结构的 有利条件探讨混合系统中新的算术方法，也就是说，粗糙集方法 将和其他软计算方法结合起来使用。 1 3 2v a g u e 集理论的发展前景 目前，国内外在模糊专家系统、模糊控制、模糊决策支持系 统、模糊模式识别等许多领域的智能系统的研究中，其核心部分 近似推理都是采用z a d e h 教授提出的基于模糊集的合成推理方法 来实现的，这种采用单蕴涵的近似推理模式存在如下问题：模糊 集的隶属度仅是 o ，1 中的一个单值，它既包含了支持该对象的证 据，同时也包含了反对该对象的证据。这说明模糊集并不是处理 模糊知识的最好理论和工具。v a g u e 集理论的提出给我们解决这 种问题提供了崭新的思路。 1 4 本文内容与主要工作 西南交通大学硕士研究生学位论文第5 页 1 i4 1 内容安排 本文的内容安排如下： 在第一章介绍了粗糙集和v a g u e 集的提出背景、研究现状及 发展前景；第二章与第四章分别系统地介绍了租糙集和v a g u e 集 的基本理论：第三章详细的讨论了决策表的约简问题：第五章研 究了v a g u e 集的模糊熵的构造方法；第六章提出粗糙v a g u e 集理 论，并研究了粗糙v a g u e 集的模糊熵、粗糙度、相似度量等问题， 另外还研究了广义粗糙集的构造和公理化；第七章将粗糙v a g u e 集理论应用到v a g u e 决簸表的属性约简：最后一章对全文进行了 总结，并对进一步的工作进行了展望。 1 4 2 本文主要工作 本文的主要工作有： 1 ) 在分析了目前决策表属性约简方法的缺点后，给出了一种新 的方法，即基于等价类的属性约简法，并用v c c + + 实现。 2 ) 在分析了基于粗糙集信息观的决策表属性约简方法的缺点 后，对其进行了改进。 3 ) 在充分研究了决策表的性质后，分别给出了相容决策表与不 相容决策表的所需元素个数，这对数据采集有着指导意义。 4 ) 讨论了完备决策表与不完备决策表属性约简之间的关系，这 对于不完备决策表的属性约简有着重要意义，并给出了一种不 完备决策表属性可能约简方法。 5 ) 在分析了目前v a g u e 集模糊熵构造方法的缺点后，给出了一 种新的构造法。 6 ) 研究了粗糙v a g u e 集，讨论了粗糙v a g u e 集的模糊熵、粗糙 度、相似度量等问题，并对广义粗糙v a g u e 集的构造与公理化 进行了研究。 7 ) 将粗糙v a g u e 集理论应用到v a g u e 决策表的属性约简。 西南交通犬学硕士研究生学位论文第6 页 第二章粗糙集基本理论 粗糙集理论为我们提供了一种描述不确定事物的数学语言， 使我们可以采用不同的精度来分析数据。本章介绍粗糙集理论的 一些基本知识。 2 1 知识表达 设u 是我们感兴趣的非空对象集合，称为论域。对于任何子 集z u 可称之为一个u 中的概念或范畴。l ，中的任何概念旗称 为关于u 的抽象知识，简称知识。u 上的一族划分称为关于u 的 一个知识库。 设r 是非空集合u 上的等价关系，商集u 尺是r 产生的对 u 的划分。一个知识库就是一个关系系统k = ( u ，r ) ，其中u 为 论域，r 是u 上的一族等价关系。 若p r ，且p - ，则n p ( p 中所有等价关系的交集) 也 是一个等价关系，称为p 上的不可区分关系，记为i n d ( p ) 。这样， u i n d ( p ) 就表示与等价关系族p 相关的知识，称为k 中关于u 的 p 基本知识。 2 2 粗糙集合 设z u ，r 为u 上的一个等价关系，当盖能表达成某些尺 基本概念的并时，称x 是r 可定义的，否则称置为r 不可定义的。 尺可定义集可以在知识库莨中精确地定义，而r 不可定义集币能 在知识库k 中定义，称r 不可定义集为r 粗糙集。 对于粗糙集可以通过两个可定义集来近似定义，即通过粗糙 集的上近似、下近似来描述： 定义2 1 t 给定知识库置= ( u r ) ，对于每个子集x 【，和一个 等价关系尺e i n d ( k ) ，定义两个可定义子集： 等价关系尺i n d ( k ) ，定义两个可定义子集： 西南交通大学硕士研究生学位论文第7 页 星僻) = u ( y u r l y x ) ， r ( x ) 一u ( y u r i y n 并妒 分别称它们为z 的r 下近似集和r 上近似集。 定义2 2 ：设星伍) 、r 何) 为x 的r 下近似集和r 上近似集，则 称钿。( z ) 一月( x ) 一星( x ) 为x 的r 边界域；p 。僻) - 星( x ) 为 x 的r 正域；n 蹭。( x ) 一u r 暖) 为盖的r 负域。 定义2 3 ：设显( x ) 、r 暖) 为x 的r 下近似集和r 上近似集，则 称m ( x ) = 1 一星( z ) r ( z ) 为工的r 粗糙度。 2 3 知识约简及知识依赖性 2 1 知识约简 知识约筒是粗糙集理论的核心内容之一。众所周知，知识库 中的知识并不是同等重要的，甚至其中某些知识是冗余的。所谓 知识约简，就是在保持知识库分类能力不变的条件下，删除其中 不相关或不重要的知识。 定义2 4 ：设r 为一族等价关系，r r ，若：i n d ( r ) = i n d ( r f r ) ) ， 则称足为r 中不必要的；否则称r 为r 中必要的。 定义2 5 ：若r 中每一个r 都是必要的，则称r 为独立的；否则 称r 为依赖的。 定义2 6 ：设q p ，若i n d ( q ) = i n d ( p ) ，且对于v r c q ， i n d ( r ) ，i n d ( p ) ，则称q 是p 的一个约简。 定义2 7 ： 设q 1 ，统是p 全部约简， 则称 c o r e ( 尸) = 幺n n q 为尸的核。 西南交通大学硕士研究生学位论文第8 页 定义2 8 ：设| p 和q 是u 中的等价关系，q 的p 正域记为 p ，( q ) ，即：p ，( q ) 2u 僻) 。 x 甘j f q 定义2 9 ；设p 和q 是等价关系，r p ，若p ，( q ) = p 伽，。( q ) ， 则称r 是尸中q 不必要的；否则r 是p 中q 必要的。 定义2 1 0 ：若p 中每一个r 都是q 必要的，则称p 为q 独立的。 定义2 1 1 ：设s p ，若胛。( q ) = 删，( q ) ，且对于v 尺c s ， p 。( q ) 删，( q ) ，则称s 是p 的一个q 约简。p 的所有q 约简 的交集称为p 的q 核。 2 3 2 知识依赖性 知识的依赖性可定义如下： 定义2 1 2 ：设置= ( u ，r ) 是一个知识库，尸，q r 。于是有： 1 ) 知识q 依赖于知识p ( 记为p j q ) 当且仅当i n d ( p ) i n d ( q ) ； 2 ) 知识q 与知识p 等价( 记为p s q ) 当且仅当p q 且q p ； 3 ) 知识q 与知识p 独立( 记为p q ) 当且仅当p j q 与q p 都不成立。 有时候知识的依赖性是部分的，这意味着知识q 仅有部分是 由知识p 导出的，部分可导出可由知识的正域来定义。 定义2 1 3 ：设k = ( u ，r ) 是一个知识库，p ，q r 。当 西南交通大学硕士研究生学位论文第9 页 七；y ，( q ) ；i 胛，( q ) l i u l 时，我们称知识q 是t ( o s 尼s 1 ) 度 依赖于知识p 的，记为， 。q 。 2 4 决策表 决策表是一类特殊而重要的信息系统。多数决策问题都可以 用决策表的形式表达，这一工具在决策应用中起着重要的作用。 决策表可以根据知识表达系统定义如下： 设s 一，爿，y ，) 是一知识表达系统，爿一c u d ，c n d 一庐， c 称为条件属性集，d 为决策属性集，则称s 为一决策表。 在决策表中，最重要的是提取决策规则。当然，在产生决策 规则之前，可以首先对决策表进行数据和属性约简。设置；与y ，分 别代表u c 与u d 中的各个等价类，d e s ( x ，) 表示对等价类丑； 的描述，即等价类z ；对于各条件属性值的特定值；d e s ( 一) 表示对 等价类的描述，即等价类一对于各决策属性值的特定值。决策 规则定义如下： ，| f ：d e s ( z ，) 一d e s ( ) ，石。n 一妒， 规则的确定性因子p ( z ，巧) 2 l n x ；i l x ；i ，o 肛( x ，一) s 1 。 西南交通大学硕士研究生学位论文第1 0 页 第三章决策表约简 3 1 决策表性质研究 设d 丁一，c u d ，y ，) 是一个决策表，其中，u 一恤l 一，h f ) 是 对象的非空有限集合，c 是条件属性的非空有限集合，d 称为决策 属性，矿uk 是属性值的集合，k 称为口的值域，：u y 4 t w 是一个信息函数，它指定u 中每一个对象x 的各个属性值。 定义3 1 ：设爿c c ，工，y 【，称它们是彳不相容的，若 ，o ，爿) 一，( ) ，爿) 且，d ) 一，( y ，d ) 。否则称它们是4 相容的。 定义3 2 ：设一c c ，x ；，瓦u ，拥d ( c ) ，称它们是一不相容的， 若，( x 。，一) 一，( 墨，爿) 且，暖；，d ) ，( 以，d ) 。否则称它们是彳相 容的。 定义3 3 ；设爿c c ，x u ，称在d r 中是不相容的，蓿d r 中 存在y u ，石与) ，是爿不相容的。否则称x 在d t 中是爿相容的。 定义3 4 ：设爿c c ，x u 删( c ) ，称盖在d t 中是爿不相容 的，若d r 中存在x u 猁( c ) ，工与x 。是爿不相容的。否则 称石在d r 中是a 相容的。 定义3 5 ：设工u ，称其是无效的，若，o ，d ) 中含空值( 用“+ ” 表示) 。否则称其为有效的。 定义3 6 ：设z ，称其是确定的，若x 是有效的且，c ) 中 不含空值。若x 是有效的但，0 ，c ) 中含空值，则称其为不确定的。 定义3 7 ：设z e ，称其是独立的，若n r 中不存在y u ，其 西南交通大学硕士研究生学位论文第1 l 页 ，0 ，c ) 一，( _ ) ，c ) 且，o ，d ) t ，( y ，d ) 。否则称z 是不独立的a 定义3 8 ：称d t 是不相容的，若d 丁中血u ，x 是c 不相容的。 否则称d f 是相容的。 定义3 9 ：称d r 是不完备的，若d r 中蛩u ，x 是不确定的。 否则称d r 是完备的。 根据定义3 8 、3 9 ，可将d z 分为完备相容决策表、不完备 相容决策表、完备不相容决策表、不完备不相容决策表。 定理3 1 ：设彳c c ，工u ，若z 是c 不相容的，则x 是a 不相 容的。 证明：x 是c 不相容的，则砂，其， ，c ) 一，( y ，c ) 但 ，0 ，d ) 一，( _ ) ，d ) ，于是有，0 ，爿) 一，( y ，爿) 且， ，d ) 一，( y ，d ) ， 这表明x 是爿不相容的。 定理3 2 ：设爿c c ，x u ，若x 是4 相容的，则x 是c 相容的。 证明：( 反证法) 假设x 是4 相容的，且是c 不相容的。显然，假 设同定理3 1 矛盾。 定理3 3 ；设x u ，若x 是4 相容的，则有【z 】。【x 】。其中【z l 表示，0 ，彳) 相同的元素集合，k b 表示， ，d ) 相同的元素集合。 证明：对于v y p l ，有，o ，爿) - ，( y ，彳) ，又因为x 是爿相容的 所以，有，0 ，d ) 一，d ) ，故y 【叫。，因此有【x l 【叫。 定理3 4 ：u 拥d ( c ) 在d 丁中是c 相容的。 证明：对于锻u 抽d ( c ) ，若x z 1 ，则，皤，c ) 厂僻1 ，c ) ， 于是x 与z 是c 相容的，所以，定理得证。 定理3 5 ：设爿c c ，x u 砌( c ) ，工x ，若x 在d 丁中是c 相容的，则j 的4 相容性与x 的爿相容性是一致的。 证明：因为z z ，z 在d t 中是c 相容的，所以对于如苫有： 西南交通大学硕士研究生学位论文第1 2 页 ， ，c ) = ，( y ，c ) 且，o ，d ) 一，( ) ，矗) ，也就是说x 与y 是相同的。 因此x 与y 的一相容性是一致的。故x 的爿相容性与x 的爿相容 性是一致的。 定理3 6 ：设4 c c ，z u ，耐( c ) ，若工在d r 中是爿相容的， 则、k x ，z 的爿相容性与c 相容性是一致的。 证明：1 ) 若茗在d r 中是c 不相容的，则x 在d r 中是爿不相容 的，此时x 的彳相容性与c 相容性是一致的。 2 ) 若x 在d t 中是c 相容的，则x 的爿相容性与x 的爿相容 性是一致的。又因为盖在d 丁中是4 相容的，所以x 在d r 中是爿相 容的。此时x 的a 相容性与c 相容性是一致的。定理得证。 3 2 数据约简 对决策表d r 进行数据约简，首先就是删除决策表中无效的 元素；而对于所有属性取值都相同的元素只保留一个。也就是说， 经过数据约简的决策表，其所有元素都是有效且独立的。对于决 策表，目的是要从中获取决策规则，而无效的元素是得不到任何 决策规则的，所以必须删除。那么，删除不独立的元素是否影响 规则提取就是问题的关键。显然相同的元素只能得到相同的决策 规则，所以删除不独立的元素不会减少提取的规则数目。但分析 发现，删除不相容决策表中不独立的元素可能影响规则的确定性。 为了解决这个问题，可以给不相容决策表添加一栏元素个数 项p 。但元素个数项p 对于c 相容元素是没有意义的，这是因为 由相容元素得到的规则的确定性是l ，不会因元素个数的多少而 改变。因此对于相容决策表不用添加元素个数项p 。 定理3 7 ：对于相容d t ，最多有1 1 个确定的独立的元素。l 诈i 表示c 值域的元素个数。 定理3 8 ：对于不相容d r ，最多有1 。1 个确定的独立的元素。 这两个定理对于数据采集有着指导意义和经济意义。数据并 非越多越好，对于相容d r ，若确定的独立的元素个数己等于 i ，则不必继续采集数据了。对于不相容d r ，若确定的独立 西南交通大学硕士研究生学位论文第1 3 页 的元素个数已等于i wi ，且不相容元素之间的比率基本保持不 变，则可停止采集数据了。 3 3 属性约简 3 3 1 完备决策表的属性约简 3 3 1 1 目前主要方法及其不足 目前，决策表属性约简方法很多，但主要只有三种，其他方 法基本上都是根据这三种方法改进来的。 方法一：基于粗糙集代数观的约简法 定义3 1 0 ：设n c ，若p 吣。 ) 一p 珊。 ) ，则称口是不必要的 否则称口是必要的。 定义3 1 l ：设爿c c ，4 是c 的d 约简，若爿满足： 删c 似) - 眇 ) 且对于c 4 ，胛c q ) 胛。( d ) 。 定义3 1 2 ；设c d ，e ( c ) 是c 的d 核，若c ，口是必要的，则 n c b ，e ( c ) 。 表3 一l 决策表l uabcduabcd 110l140o1o 210l05ll12 30ol 2 对于决策表l ，显然有约简扣，砖，而且核c d 腭( c ) = 和，6 ) 。现 在根据上述方法计算如下： u 扣，6 ，c 卜， n 2 ) ， 3 4 ) ， 毋) 2 u 扣，6 ) ，u d ) ； 1 ) ， 2 4 ) ， 3 ，5 ) ) ， 则有，p 。( d ) 一p 。q ) - 5 ) ，于是c 是不必要的。 西南交通大学硕士研究生学位论文第1 4 页 u 扣，c ) 一 1 ，2 ，5 ， 3 ，4 ) ) ，则有，p 伽。似) 一声，于是6 是必要的。 u p ，c ) 昌= 扎2 ，3 ，4 ) ， 毋) ，则有，p 哪。p ) m 毋，于是矗是不必要 的。所以核c d ( c ) = 吣。u ， 6 一 仉2 ，3 4 ) ， 5 ，则有， p 。 ) 一 5 ) ，所以有约简忙) 。上述方法计算的结果显然与实际 不符。 方法二：基于租糙集信息观的约简法 设u 加d “) - ，k ) ，u 砌( c ) 一心，x 。，则d 相对 于c 的条件熵为： h ( dl c ) 一一二d p 伍t ) ：d p ( k x ；) 1 0 9 尸佤z ；) 。其中 尸( z i ) 叫x ；i ，i u l ，p 暇工。) 爿kn z ji i x ；i ，f 一1 ，万， t ；1 ，打。 表3 2 决策表2 uabcdua bcd 10o0050 10l 200 1 l6 llo0 3o1o07l1o o 4 olol8llol 定义3 1 3 ：设口c ，若h l c ) - 日似i c 一口 ) ，则称口是不必 要的；否则称口是必要的。 定义3 1 4 ：设4 c c ，彳是c 的d 约简，若一满足： h i c ) 一h q i 彳) 且对于v b c 爿，日u l c ) - 日( d i 四) 。 定义3 。1 5 ；设国陀( c ) 是c 的d 核，若地c ，痒是必要的，则 口c b 陀( c ) 。 对于决策表2 ，显然有约简 6 ，c ，而且核c d r e ( c ) = p ，c 。但 西南交通大学硕士研究生学位论文第1 5 页 根据上述方法计算的结果是核c 0 ”( c ) = c ，没有约简。这显然与 实际不符。 方法三：基于区别矩阵的约简法 s k o 耵o n 等学者提出了区别矩阵的概念，并给出了基于区别矩 阵来计算属性约简的方法，其中区别矩阵m 一枷。) ，。定义为： f 口c i ，0 ；，口) 一，0 。，4 ) ，o ，d ) 一，o 。，d ) 胧4 。1 妒( 空集) ，否则 构造区别函数g ；vm 。，将其转化为极小析取范式 h i 叫月p f g v d ，则每个6 就是决策表的一个属性约简。h u 等学者将 其应用到核属性的计算中，其给出的结论是：当且仅当某个川。为 单个属性时，该属性属于核c d 陀( c ) 。 表3 3 决策表3 u a b c d uabcd l1o1l 40ooo 2 1o105ll11 300 o1 对于决策表3 ，显然其属性约简和核属性都为p 。但根据上 述方法计算的结果是：如，吣与 6 ，c ) 都是属性约简。 3 3 1 2 基于等价类的属性约简法 笔者对其他约简方法( 如：文献 3 2 、 3 9 、 4 卜4 5 ) 研究 发现，这些方法都是分别根据以上三种方法改过来的，但遗憾的 是这些方法都不能从根本上解决问题，它们都只能应用于某一类 决策表。研究发现要计算决策表的属性约简以及核属性，关键是 要考虑u f ，耐( c ) 中的等价类的相容性。然而以上方法只考虑了决 西南交通大学硕士研究生学位论文第1 6 页 策表中单个对象的相容性，而没有考虑u 抽d ( c ) 中等价类的相容 性，这就是这些方法不足的根本原因。于是本文给出了基于 u 伽d ( c ) 中等价类相容性的属性约简、核属性的定义： 定义3 1 6 ：设爿c c ，彳是c 的d 约简，若，蔓满足：，1 ) 垤u ，砌( c ) ，z 都是4 相容的；2 ) c ，酗u 涮( c ) ， 膏是b 不相容的。 定义3 1 7 ：设爿l 一，一。c c ，它们是c 的所有d 约简，则核属性 集c 口冲( c ) = 4n n 以。 定义3 1 8 ：设口c c ，口c b m ( c ) ，若翦v 俐( c ) ，z 是 c 一忙) 不相容的。 于是可以将原决策表转换成以u ，打以( c ) 中的等价类为单个对 象的新决策表，由定理3 4 可知新决策表是相容的。研究可知，上 述三种方法计算相容决策表的属性约简和核属性一定会得到正确 的结果，而新决策表显然是相容决策表，于是可用上述方法计算 新决策表的属性约简和核属性。另外，研究发现，新决策表的属 性约简和核属性就是原决策表的属性约筒和核属性。下面来证明 这一结论正确性。 定理3 9 ：设d r 是由决策表d r 根据本文方法转换得到的， 爿c c ，则有：爿是d r 的约简4 是d 丁的约简。 证明：设d r 一，c u d ，y ，) ，d r