（应用数学专业论文）基于信息熵的属性约简及其应用.pdf

中文摘要 摘要 多属性群决策是一类常见的群体决策问题，所研究出来的解决方法己经成功 地应用于工程、经济、市场分析、管理等实际问题中。本文重点讨论粗糙集的理 论在多属性决策中的应用。粗糙集( r o u g hs e t ) 理论是一个新的数据挖掘方法，其主 要思想是保持分类能力不变的情况下，通过属性约简，达到发掘知识并简化知识 的目的。而信息熵在粗糙集理论中有着重要的应用，它可用来度量知识的不确定 性、属性关联的重要性及粗糙集的不确定性等。本文从知识熵的基础知识入手， 介绍基于传统信息熵的知识约简同时，从信息论的角度，对决策表中属性重要性 的大小进行度量，并在此基础上，研究了基于互信息大小的知识约简算法，基于 条件熵的知识约简算法，及基于正域与条件熵结合的知识约简算法。通过对基于 信息熵属性约简算法的分析，讨论了启发信息的构造，进而给出了在此基础上提出 的以粗糙集的代数理论为基础，以条件信息熵为属性约简的启发式信息的改进算 法，来得到尽可能小的属性约简。然后分析了在知识约简过程中现有条件信息熵的 不足，从一种扩展的信息观的角度出发，讨论了r o u g h 集理论的信息论观点。并 给出一种新的条件信息熵，用于粗糙集数据分析中的属性简约，以弥补现有信息熵 的不足，并给出改进的算法。与基于现有条件信息熵的约简算法相比，该约简算 法时间复杂度变化不大，但在对不一致决策表进行约简时，可以得到更加完备的约 简。 最后本文将用信息熵确定属性重要性的方法到多属性决策中。首先应用改进 的算法将所给的数据属性进行约简，然后运用信息熵的相关知识给出综合评价结 果。结果表明，这种方法能够充分说明实际问题，并且大大地简化了原有问题考 虑的属性数目，使得最后的评价结果简单鲜明。总体来说，得到了预期的良好效 果，具有一定的理论和实践的价值。 关键词：粗糙集；属性约简；信息熵；多属性决策 英文摘要 r e s e a r c ha n da p p l y c a t i o no na t t r i b u t er e d u c t i o nm e t h o d s b a s e do ni n f o r m a t i o ne n t r o p y a b s t r a c t m u l t i p l e - a t t r i b u t ed e c i s i o n m a k i n g ( m a d m ) m e t h o d o l o g y h a sb e e no n eo ft h et o p i s s u e st h er e s e a r c h e r sd i s c u s s e d ，w h i c hh a sb e e ns u c c e s s f u l l ya p p l i e di nm a n yr e a l l i f e p r o b l e m s i ne n g i n e e r i n g ,f i n a n c e s ，m a r k e ta n a l y s i s ，m a n a g e m e n ta n do t h e r s w e a n a l y z e st h ec h a r a c t e r i s t i co ft h ec o m p l e xd e c i s i o nm e t h o d sa n di n t r o d u c ei n t e r n a t i o n a l a d v a n c e dt h o u g h t sa n dm e t h o d ss u c ha sr o u g h ts e t st h e o r yi n t oc l a s s i c a lm u f t i a t t r i b u t e d e c i s i o n r o u g hs e ti s an e wm e t h o do fd a t am i n i n g i t sb a s i ct h e o r yi st h r o u g h a t t r i b u t i o nr e d u c t i o n ，o b t a i n i n gk n o w l e d g ew i t ht h es a m ea b i l i t yo fc l a s s i f i c a t i o n a t t r i b u t er e d u c t i o nb a s e do ni n f o r m a t i o ne n t r o p yi so n eo ft h ei m p o r t a n ti s s u e so fr o u g h s e tt h e o r y i nt h i st h e s i s ，b yt h ec o m p r e h e n s i o na n da n a l y s i so fd a t am i n i n ga l g o r i t h mb a s e d o nt h er o u g hs e tt h e o r y ，s e v e r a lh e u r i s t i ca l g o r i t h m sf o ra t t r i b u t i o nr e d u c t i o nb a s e do l l k n o w l e d g ee n t r o p yh a v eb e e np r o p o s e d a f t e ra n a l y z i n gt h ea l g o r i t h m ，t h er e a s o nf o r i n c o m p l e t er e d u c t i o ni sf o u n d r e g a r d i n gt h es i g n i f i c a n c eo f a t t r i b u t ed e f i n e df r o mt h e v i e w p o i n to fi n f o r m a t i o nt h e o r y 嬲h e u r i s t i ci n f o r m a t i o n t h ec o n s t r u c t i o no ft h e h e u r i s t i ci n f o r m a t i o ni sd i s c u s s e d ，a n da l li m p r o v e da l g o r i t h mw h i c hc o m b i n e dt h e a l g e b r ao f t h er o u g hs e tt h e o r ya n dt h ec o n d i t i o n a li n f o r m a t i o ne n t r o p yi sp u tf o r w a r d t h ec o n d i t i o n a li n f o r m a t i o ne n t r o p yi st h eh e u r i s t i ci n f o r m a t i o no ft h ea t t r i b u t e r e d u c t i o n a l g o r i t h mi sb a s e do nc o n d i t i o n a li n f o r m a t i o ne n t r o p yf o rr e d u c t i o no f d e c i s i o nt a b l e ，b u tt h ea l g o r i t h mi si n c o m p l e t ef o rs o m ed e c i s i o nt a b l e ，s oa ni m p r o v e d a l g o r i t h mw h i c hc o m b i n e dt h ea l g e b r ao ft h er o u g hs e tt h e o r ya n dt h ec o n d i t i o n a l i n f o r m a t i o ne n t r o p yi sp u tf o r w a r d t h ee x p e r i m e n tr e s u l t ss h o wt h a tt h i sa l g o r i t h mc a l l f i n dt h em i n i m a lr e d u c t i o nf o rd e c i s i o nt a b l e t h ed i s a d v a n t a g e so ft h ec u r r e n tc o n d i t i o n a li n f o r m a t i o ne n t r o p ya r ea n a l y z e d s o e x t e n s i v ea t t e n t i o nh a sb e e ng i v e n b a s e do nt h i se n t r o p yt h en e ws i g n i f i c a n c eo fa l l a t t r i b u t ei sd e f i n e da n dc o m p a r e dw i t ht w os i g n i f i c a n c e so ft h i sa t t r i b u t eb a s e do nt h e 英文摘要 a t t r i b u t ei sd e f i n e da n dc o m p a r e dw i t ht w os i g n i f i c a n c e so ft h i sa t t r i b u t eb a s e do nt h e p o s i t i v er e g i o na n dt h ec u r r e n tc o n d i t i o n a li n f o r m a t i o ne n t r o p yr e s p e c t i v e l y f i n a l l y ，a h e u r i s t i ca l g o r i t h mf o rk n o w l e d g er e d u c t i o ni sd e s i g n e da n da ne f f i c i e n ta l g o r i t h mf o r c o m p u t i n gc o n d i t i o n a li n f o r m a t i o ne n t r o p yi sp r o p o s e d a l s o ，t h i sr e d u c t i o na l g o r i t h m i sm o r ec a p a b l eo ff i n d i n gt h em i n i m a lo ro p t i m a lr e d u c t s i n c er o u g hs e th a sb e e np r e s e n t e di t st h e o r ya n dm e t h o dg e td e v e l o p m e n t c o n t i n u o u s l y f u r t h e r m o r ew ep u tf o r w a r das e to fm u f t i a t t r i b u t ed e c i s i o nm e t h o d s b a s e do nr o u g hs e tt h e o r y w ep r o v et h e s es e t so fm e t h o dh a v et h et h e o r yv a l u ea n d p r a c t i c ev a l u e k e yw o r d s ：r o u g hs e t ；a t t r i b u t i o nr e d u c t i o n ；i n f o r m a t i o ne n t r o p y ；m u l t i p l e a t t r i b u t ed e c i s i o n - m a k i n gm e t h o d o l o g y 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成博i i 硕士学位论文= = 基王信! 塾墒的屋丝约篮丛墓廑旦：。除论文中已经注 明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中以明确 方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公开发表或 未公开发表的成果。 本声明的法律责任由本人承担。 论文作者签名：年月日 学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连海事大学研究生学位论文提交、 版权使用管理办法”，同意大连海事大学保留并向国家有关部门或机构送交学位 论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将 本学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或 扫描等复制手段保存和汇编学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于：保密口 不保密口( 请在以上方框内打“4 ”) 论文作者签名： 导师签名袁噼 只期：年月同 基于信息熵的属性约简及其应用 第1 章绪论 1 1 本文的研究背景和意义 市场竞争r 益激烈的今天，企业或个人都经常面临着复杂的决策问题，不仅 需要快速做出决策，而且需要解决决策问题中多种不确定性所带来的困难。因此， 开展决策分析一的理论与方法研究，不仅对管理科学的发展具有重大的理论意义， 而且对解决许多复杂的决策问题也有特别重要的现实意义。多属性决策是现代决 策科学的一个重要组成部分，它在工程设计、经济、管理和军事等诸多领域中都 有着广泛的理论与实际应用背景，如投资决策、项目评估、工厂选址、投标招标、 产业部门发展排序、经济效益综合评价等。多属性决策的实质是利用已有的决策 信息通过一定的方式对一组有限个备选方案进行排序并择优。它主要由两部分组 成，( 1 ) 是决策信息的获取( 属性权重和属性值) 。( 2 ) 通过一定的方式对决 策信息进行集结并对方案进行排序和择优。属性权重的确定是多属性决策中的一 个核心问题，近年来关于这方面的研究己受到人们的关注，并取得了较大进展。 迄今为止，人们从不同角度，提出了许多确定权重的方法，这些属性赋权法大致 可以分为四类：客观赋权法，主观赋权法，组合赋权法，交互式赋权法。客观赋 权法是利用客观信息属性值赋权的一类方法，该方法不含人的主观因素。主要有 熵值法、形心法、离差最大化法、线性规划法、目标规划法、基于方案满意度法、 基于方案贴近度法、两阶段法等。 本文利用粗糙集的理论重点研究熵值法。r o u g h 集理论是近年来发展起来的一 种有效地处理不精确、不确定、含糊信息的数学理论方法。粗糙集理论以不可分 辨关系为基础，通过集合的近似来描述粗糙概念。由近似空间由决策信息系统来 表示，扩展到在一个决策信息系统上用属性来定义粗糙集合。随着韦h 糙集理论的 提出和发展，它在各个领域得到了广泛的应用，在机器学习、数据挖掘、智能数 据分析、控制算法获取等领域取得了很大的成功，现在，该理论已被成功地应用于 粒度计算嘲、软计算限4 1 、信息检索吲和数据挖掘睁8 1 等领域。粗糙集方法的简单 实用性是令人惊奇的，它能在创立后的不长时间内得到迅速应用是因为具有以下特 第1 章绪论 点： ( 1 ) 能处理各种数据，包括不完整( i n c o m p l e t e ) 的数据以及捌有众多变量的数据； ( 3 ) 处理数摒的不精确性和模棱两可( a m b i g u i t y ) ，包括确定性和非确定性情况； ( 4 ) 求得知识的最小表达( r e d u c t ) 和知识的各种不同颗粒( g r a n u l a r i t y ) 层次； ( 5 ) 从数据中揭示出概念简单，易于操作的模式( p a t t e r n ) ； ( 6 ) 产生精确而又易于检查和证实的规则，特别适于智能控制中规则自动生成。 但是，在粗糙集理论中，进行属性约简仍是一个远未解决的问题。属性是关 于对象特征的描述，有些对象可能具有相同的描述，这是它与数据库的不同。决 策信息系统强调论域中的对象对决策信息系统形式表示的数据。在决策系统中，人 们关心的是哪些条件属性对于决策属性更重要，属性约简实际上就是确定决策规 则中的条件属性。一般的约简算法就是在保证与原决策系统相同相关系数的前提 下，选择尽可能简单的条件属性集。基于粗糙集理论的数据约筒基本原理通过求 属性重要性并排序，在泛化关系中找出与原始数据具有同等决策能力的极小相关 属性集合，实现信息简约，以获得更简洁的知识。粗糙集理论具有基于示例学习 的特点，很适合于进行数据约简。知识约简是粗糙集的核心内容之一，是它一个 n p - h a r d 问题，因此许多学者从不同的角度提出了获取信息系统和决策系统属性的 约简算法。这些算法大体上可以分三大类【9 1 ：第一类是基于代数理论的，第二类是 基于区分矩阵和区分函数构造的 l o i ；第三类是基于信息熵理论【1 1 1 的。此外，目前 还有一些学者n 2 1 3 1 正在研究用粗糙集理论对不完备信息系统进行分析。对r o u g h 集知识约简在信息论观点和传统的代数观点下的关系进行了研究，有学者发现在 一些条件下两种观念存在等价关系，而在另外的条件下又呈现出不等价的关系【i4 1 。 两种观点下的属性约简问题也成为粗糙集研究的热点问题之一。 1 2 粗糙集理论与多属性决策结合研究现状 粗集理论与多属性决策相结合的有关研究还处于初始而零散的阶段。多属性 决策的难点在于属性间的矛盾性和各属性值的不可公度性，求解多属性决策问题 必须解决这两个难点。其中不可公度性在经典多属性决策中通过属性矩阵的规范 基于信息熵的属性约简及其应用 化可以得到部分解决，但这些规范化方法一方面无法反映属性的重要性，同时对 于许多属性值不可计算的决策问题显得有些局限。在其他理论中，这种重要性可 在辅助知识的基础上事先假设，并用“权重”表达。在r o u g h 集中，无需使用任 何先验信息，而能给属性重要性一种基于数据的客观量度。在国外，近期出现一 些方法上的研究，确定权重是经典多属性决策的前提。权重的确定有许多方法， 但只给出判断矩阵，而专家和决策者没有给出指标权重的情况下，可以采用熵权 值法进行多目标决策。其基本思想是：把信息熵和熵权的概念引入到评价指标判 断矩阵中，从而使评价指标具有熵的性质。经典方法通常是让决策人首先把各目 标作成对比较，这种比较可能不准确，也可能不一致，因为决策人完全是依赖主 观经验来进行判断的。一般来说，描述不同对象特征的属性集是较大的，在经典 的多属性决策理论与方法中，大多要求属性集是最小的，在这样的要求下，才能 保证决策模型的合理性。而对于一般多属性信息系统瓦言，有些属性对分类决策 并不总是必要的。不同的属性对分类决策，有些是绝对必要的，去掉该属性必然 会影响分类的结果，有些是绝对不必要的，去掉该属性并不影响分类的结果，有 些属性则是相对必要的，它可能与其他属性联合才能确定分类。信息系统属性约 简就是要在属性集中寻找一个最小的属性集，它能完全确定分类，约简后的属性 集与未经约简的属性集对论域的分类结果是相同的。权是属性重要性的量化表示 但在属性较多时，决策人往往难于直接确定每个属性的权重，对于属性值为逻辑 值的权重判断更是困难。 多属性决策是多目标决策在发展过程中逐渐形成的一个类别，因此，它的发 展过程与多目标决策的发展过程密不可分。早在1 8 9 6 年v p a r e t o 提出了向量优化 的概念，从经济学的角度把本质上不可比较的多个目标化成单个目标进行优化求 解。之后很长一段时间，多目标决策涉及到多目标概念的研究没有取得任何有价 值的成果。直到1 9 4 4 年，j vn e u m a n n 和o m o r g e n s t e r n 从对策论角度提出了彼此 矛盾情况下的多日标决策问题，标志着近代意义上多目标决策的诞生，多目标决 策的理论和方法也逐步发展起来。在理论研究方面，多属性决策自从其诞生以来 就二直是学术界关注的研究课题。近年来，不确定多属性决策引起了学术界的广 第1 章绪论 泛关注。第二次世界大战以后，随着一些基础理论如数学、运筹学和经济学的发 展，不同领域的学者们对多目标决策问题进行了研究，也逐步分化出了多属性决 策的概念、理论和方法。如：k a z i m i e r zz a r a s ( 2 0 0 1 ) 提出了多属性随机优势评估问 题的带偏好关系的r o u g h 近似方法5 1 ；s a l v a t o r eg r e c o ( 2 0 0 2 ) 提出了多属性多准则 分类题的粗集方法引；r a m a n n a s ( 2 0 0 2 ) 提出了基于粗集近似空间的软件质量测 评方法m 。在众多研究中，十分有价值的是a l a ms s ( 2 0 0 2 ) 提出的基于r o u g h 方法的a h p 排序方法，它直接对传统的多属性决策方法进行了改进8 1 。在国内， 张梅和李怀组( 2 0 0 3 ) 提出了国际竞争力因素分析的粗集方法9 1 ；何亚群( 2 0 0 4 ) 提出 了不完全信息的多属性粗集决策分析方法1 ，该文针对有偏好信息但信息不完全 的多属性决策问题，给出了一种基于拓展粗集的决策分析方法等等。综述之，粗 集理论的快速发展及作为新型工具对决策研究的支撑作用，又能弥补诸多多属性 决策现时的缺陷与难点问题，因而就此展开深入而系统的研究，学术和应用价值 重大。 1 3 本文的研究内容及主要创新点 第一介绍粗糙集的基本知识体系，包括基于粗糙集的任务、方法、研究对象 等，并介绍了基于粗集理论的发现方法在国内外的研究现状。 第二介绍信息熵的相关定义定理，主要研究在不同信息熵定义下属性约简方 法，然后给出了几种基于信息熵的算法及改进算法。 第三深入分析讨论了在数据表一致与不一致情况下的知识约简问题，研究了 在新的条件熵定义下的属性约简算法，并给出改进的的约简算法。 第四将信息熵重要性引入到多属性决策中，采用基于信息熵的多属性决策方 法并在经济指标的粗集综合评价中实践，最后，所有的结果通过计算机编程进行 实现，得到了比较客观可信的评价结果。 基丁二信息熵的属性约简及其应用 1 4 本文的组织结构 第一章对多熟悉性决策理论的发展、特点进行了简单扼要的回顾，对粗糙集 理论在多属性决策中的应用做了简要介绍。将国内外对粗糙集研究现状作了全面 分析，阐述了本文研究工作的核心意义。 第二章介绍了粗糙集的基本定义定理，研究了在一致决策表中基于信息熵的 粗糙集约简算法及改进算法，分析了约简的基本性质。通过对知识熵的分析从不 同的角度描述了决策信息系统的特征，研究基于不同特性的属性约简算法。 第三章对于扩展的和改进的条件熵进行研究，对在此基础上的算法研究比较 其优越性并给出改进的算法。 第四章给出新的条件信息熵的定义，介绍了新的条件信息熵下属性重要性的 度量，研究了基于新属性重要性约简算法，并给出改进算法。 第五章研究了信息熵在项目评价中的应用，先运用改进算法将原始决策表进 行属性约简，然后再确定约简后的各属性重要性，最后确定较优项目。 第2 章粗糙集理论基础 第2 章粗糙集理论基础 粗糙集理论是波兰数学家z p a w l a k ”1 于1 9 8 2 年提出的一种数据分析理论。用 于处理不确定( u n c e r t a i n t y ) 含糊性( v a g u e n e s s ) 知识。粗糙集理论的主要优势 在于它不需要关于数据的任何预备或额外的信息，高效的约简算法是粗糙集理论 应用于数据挖掘与知识发现领域的基础，寻求快速的约简算法仍是粗糙集理论的 主要研究课题之一。 2 1 粗糙集理论的研究现状 粗糙集理论自提出以来，其理论与方法不断得到发展，在许多方面克服了传 统数据分析理论显现出的诸多不足，表现出其独特的优势，受到了国内外学术界 的广泛关注目前，对r o u g h 集理论的研究基于两种观点。一是代数观点，即以不可分 辨关系为基础，通过引入上近似集和下近似集，在集合运算上定义。二是信息论 观点，即从信息论的角度对r o u g h 集理论进行研究。 随着粗糙集理论的发展，与之相关联的研究也越来越多。近年来，粗集理论 在世界发展迅速。在国外，对粗集理论的研究主要集中在代数结构和逻辑研究上 面：对代数结构的研究主要集中在粗集拓扑及其性质上面，它阐述了模糊集与粗集、 证据理论与粗集理论的关系；对逻辑的研究主要是r o u g h 逻辑及处理近似推理的 逻辑工具上，并建立了粗集与概率逻辑、粗集与模态逻辑等的统一框架。 各国学者在上述研究中产生了一系列的成果。o r l o w s k a ( 1 9 8 5 ) 提出以等价关 系作为新的谓词；p a w l a k ( 1 9 8 7 ) 建立了五个逻辑真值；l o w i n s k i r 1 ( 1 9 9 2 ) 提出 了扩展粗集模型的概念；l i u 和l i n ( 1 9 9 6 ) 卜叫基于拓扑学观点定义了类似上近似和 下近似的算子和，并建立了带这两个算子的近似推理的逻辑演绎系统。l i u ( 1 9 9 9 ) 弘卅 还提出带算子和的逻辑的近似推理模式和归结原理，并证明了它的归结完备性定 理。在国内，西安交大的张文修教授对粗集理论1 ( 2 0 0 1 ) 和概念格理论m 1 ( 2 0 0 5 ) 都有深入探讨，重庆邮电的王国胤教授1 2 7 1 ( 2 0 0 1 ) ，南昌大学的刘清教授m 1 ( 2 0 0 1 ) 的先后出版专著来介绍粗集，使得对粗集的研究成为学者们普遍重视和高度关注 基于信息熵的属性约简及其应用 的热点。山东大学的史开泉1 教授提出的s 粗集( 2 0 0 2 ) 和函数s 粗集3 0 1 ( 2 0 0 5 ) f 拘 概念，以及近几年来的有关奇异粗集p 研究成果，对经典的粗集的概念进行了扩 展，将对粗集的研究从静态过程延拓到动态过程，在国内外引起高度关注，也为 将动态粗集理论运用到多属性决策中提供了理论上的依据和支持嗍。这些研究都 不约而同的用到了粗糙集理论，不论是在决策方面、评价方面以及与其他方法的 相互关系上面，而且也得出了一些有用的结论。另外，还有很多应用粗糙集理论 解决实际问题的相关文献介绍。另外，自从1 9 9 2 年开始以来每年都要召开以粗集 理论为主题的国际会议，国际上成立了r o u g h 集学会( i r s s ，官方网 站：h t t p ：w w w r o u g hs e t s o r g ) ，并在互联网上定期发布电子公告( 可以 h t t p ：l l w w w c s u r e g i n a c a r o u g h s e t 中的r o u g hs e tc o m m u n i t y 中了解粗集研究进 展) ，以粗集为主题的国际期刊也已经正式出版，这些都加速了粗集理论的交流与 发展。 2 2 粗糙集的基本理论 2 2 1 基本定义 粗糙集理论从新的视角对知识进行了定义，把知识看作是关于论域的划分， 从而使得对知识能够进行严密的分析与处理。粗糙集理论中所有的概念和运算都 是通过代数学的等价关系和集合运算来定义的，我们称之为粗糙集理论的代数表 示。在代数表示下，粗糙集理论的很多概念与运算的直观性较差，人们不容易理 解其本质，文献 2 2 】证明了知识约简在信息和代数两种不同表示下是等价的。我们 将对粗糙集理论中的知识作新的理解，建立知识与信息熵的关系，称此表达为粗 糙集理论的信息表示。文献【l 】定义的信息表示是本文所讨论的信息表示的基础， 其建立了粗糙集理论中的知识与信息熵的关系，从而使我们能够从信息的角度对 粗糙集理论的主要概念与运算进行表达。 定义2 1 设尺是u 上的一个等价关系，u r 表示r 的所有等价类构成的集 合，【叫异表示包含元素工u 的r 等价类。一个知识库就是一个关系系统，k = ( ( ，尺) 其中u 为非空有限集，称为论域，月是u 上的一个等价关系族。 第2 章粗糙集理论基础 定义2 2 川若尸s 尺，且尸g ，则n p ( j d 中所有等价关系的交集) 也是一个 等价关系，称为p 上的不可分辨( i n d i s c e m i b i l i t y ) 关系，记为i n d ( p ) ，且有 x 】，d f p l = n m r 。 这样，u i n d ( p ) 表示与等价关系族p 相关的知识，称为k 中关于【厂的p 基 本知识，i n d ( p ) 的等价类称为知识p 的基本概念或基本范畴。事实上，p 基本范 畴是拥有知识p 的论域的基本特性，即知识的基本模块。对于粗糙集可以近似的 定义，我们使用两个精确集，即粗糙集的上近似( u p p e ra p p r o x i m a t i o n ) 和下近似 ( l o w e ra p p r o x i m a t i o n ) 来描述。 定义2 3 给定知识库k = ( u ，r ) ，对于每个子集x gu 和一个等价关系 r 1 n d ( k ) ，定义两个子集： 一r x = u y u i r y x ) ， r x = u y u i r r n x o ) ， 分别称它们为x 的r 下近似集和上近似集。 集合b n 露( x ) = r x - _ r x 称为x 的尺边界域；p o s 足( x ) = 型称为x 的只正域； n e g 足( x ) = r x 称为x 的尺负域。显然：r x = p 伽异( x ) u b n 足( x ) 。 丛或p o s r ( x ) 是由那些根据知识r 判断肯定属于x 的u 中元素组成的集合； r x 是由那些根据知识尺判断可能属于x 的u 中元素组成的集合；b n 足( x ) 是由那 些根据知识r 既不能判断肯定属于x 又不能判断肯定属于x ( 即u x ) 的u 中 元素组成的集合；n e g 。( x ) 是由那些根据知识r 判断肯定不属于x 的u 中元素组 成的集合。 定理2 1 1 1 ( 1 ) x 为尺可定义集当且仅当r x = r x ； ( 2 ) x 为尺的粗糙集当且仅当r x r x 。 定义2 4l l ( 约简) 令属性集合b a ，对某一属性a b ，如果有 i n d ( b ) = 刷d ( b p ) ) ，那么称a 是曰中不必要的，否则称a 是b 中必要的。 如果属性集合曰s 彳满足下面两个条件6 ： 基于信息熵的属性约简及其应用 ( 1 ) i n d ( b ) = i n d ( a ) ，( 2 ) v a b ，i n d ( b ) i n d ( b - a ) 勇5 么，曰就是 a 的一个约简。 在粗糙集理论中，从信息系统是否包含决策属性来看属性约简分为绝对约简 和相对约简两种。绝对约简不考虑决策属性，而相对约简则针对决策属性。绝对 约简可以转化为相对约简，所以一般情况下的约简都是指相对约简。 定义2 5 【1 5 属性集合a 的所有必要的属性构成属性约简的核，记为c o p 陋( a ) 。 记r e d ( a ) 为彳的所有约简的集合，那么存在如下关系： c o r e ( a ) = i r e d ( a ) 即彳的所有约简的交集构成彳的属性约简的核。决策表属性核的计算往往是 基于r o u g h 集理论的决策信息系统约简过程的出发点和关键。不相容决策信息系 统是信息系统约简处理研究的重点。 定义2 6 b 1 设u 为一个论域，p 和q 为定义在u 上的两个等价关系簇且 q p 。如果( 1 ) n d ( q ) = i n d ( p ) ，( 2 ) q 是独立的，则称q 是p 的一个绝对 约简。 即若知识q 是知识p 的绝对约简，那么【厂中通过知识p 可区分的对象，同样 可以用知识q 来区分。 定义2 7 设p 和q 是全域u 上的等价关系的族集，所谓族集q 的尸一正区域， 记作p ( q ) 定义为：p o s e ( q ) = up ( x ) 。 x e u 口 集族q 的p 一正区域是全域c ，的所有那些使用分类【，尸所表达的知识，能够 正确地分类于【，q 的等价类之中的对象的集合。一个集合x 相对于一个等价关系 p 的j 下区域就是这个集合的下近似( x ) 而一个等价关系q 相对于另一个等价关 系p 的i f 区域的概念是解决分类q 的等价类( 一般视为决策类) 之中的那些对象 可由分类p 的等价类( 一般视为条件类) 柬分类的问题。 第2 章粗糙集理论基础 2 2 2 信思系统 粗糙集理论中的知识表达方式一般采用信息表或称为信息系统的形式，它可 以表示为四元组t = ( u ，r ，v ，厂) 是一个知识表达系统，其中u 为对象的非空有限集 合，称为论域，r 为属性的非空集合，矿= u 圪，圪是属性口的值域：口r 。 f ： u x r v 是一个信息函数，它为每个对象的每个属性赋一个信息值，即 v 口彳，石u ，f ( x ，口) 圪。知识表达系统也称为信息系统，通常也用t = ( 【，尺) 来 表示。对于这样的信息系统，每个属性子集就定义了论域上的一个等价关系，即 尸r ，定义属性集j p 的不可区分关系加d ( p ) 为 i n d ( p ) = ( 工，y ) u xu v a p , f ( x ，口) = 厂( y ，口) 如果，( x ，y ) i n d ( p ) 则称x 和j ，是不可区分的。 定义2 8 川给定决策表信息系统r = ( u ，a = c ud ，v ，厂) ，设u 是非空论域，c 是非空条件属性集，曰c ，d d ，决策属性d 相对于曰的相对正域是： p o s s ( d 12 拦| d 些 定义2 9 1 1 设尸和q 都是等价关系族，如果 p 删即( i n d ( q ) ) = p 肋( p 一( 肋( q ) ) 则称r p 是p 上q 可约去的；否则r 是p 上a 不可约去的。所有p 中q 不可约去 的等价关系集合称为j p 的q 核，记作c o r e o ( p ) 。 定义2 1 0 t 2 0 1 令x 是u 中根据条件属性c 可定义的分类，y 是u 中根据决策属 性d 定义的分类， 对于每个薯，所u ， 定义一个函数 d ，：d e s 。( 薯) 一d e s d ( y i ) ：蕾n 辫a ，对于薯x ，y i y 函数以称为决策表t 中的 决策规则。当或为一决策规则时，d 。对于c 的约束记作d xi c ，对于d 的约束记作 d ，l d ，d ，i c , nd ，l d 分别称做或的条件和决策。如果对于每个y x ，d xl c = d ，i c 意 基于信息熵的属性约简及其应用 味着4j d = | d ，则称决策规则t 是一致的，否则称为是不一致的只有当所有决 策规则都是一致的时候，决策表才是一致的，否则决策表是不一致的。 定义2 11m 1 在决策表t = 中，称p o s 。( d ) 为决策表r 的一致 对象集，u - p o s 。( d ) 为决策表r 的不一致对象集；若p o s 。( d ) = u ，则称决策表 r 为一致决策表，否则称决策表r 为不一致决策表。 本章小结： 本章主要介绍了粗糙集理论的产生和特点。讨论了粗糙集理论对知识的定义， 以及粗糙集理论中各上近似、下近似、边界区，阐述了知识表达系统的组成，基 于粗糙集理论的属性约简、决策表的定义等。粗糙集理论是一种研究模糊性和不 精确性的新的数学工具，能有效地分析和处理不精确、不一致、不完整等各种不 完备系统，并从中发现隐含的知识，揭示潜在的规律。 第3 章基于信息熵的属性约简算法 第3 章基于信息熵的属性约简算法 熵的概念最初源于热力学，1 8 5 6 年，由c l a u s i u s 证式引入，并将其定义为热 流量与温度之比。1 8 7 7 年，b o l t z m a n n 建立了玻尔兹曼定律，给出了熵的统计意义， 将这一概念拓宽到统计力学。1 9 4 8 年，s h a n n o n 通过其经典论文“am a t h e m a t i c a l t h e o r yo fc o m m u n i c a t i o n ，建立了关于不确定性的一种定量化的度量，奠定现代 信息论的理论基础。随后，1 9 5 7 年由j a y n e s 提出的最大熵原理和1 9 5 9 年由 k u l l b a c k l e i b l e r 提出的最小叉熵原理，进一步丰富了这一概念的内涵，并极大地 扩宽了它的应用领域。熵作为不确定性的度量与上述两个熵优化原理，把熵的概 念带入了一个全新时代。不仅被应用于自然科学，而且渗入到了社会科学、医学和 经济学等各个学科领域。 3 1 信息熵研究现状及分析 信息熵由s h a n n o n 刨于1 9 4 8 年提出。粗糙集理论作为一种新型的数据分析理 论与方法提出以来，以集合整体直接逼近的方式，实现非确定与不完整信息条件 下的知识处理，在面向海量数据分析方面体现了其独有的特征。基于粗糙集的数 据分析，其基本思想在于通过对冗余属性的约简，进行属性的泛化，从而得出满 意的决策规则。国内外对属性约简算法和相关问题作了许多研究，特别是基于属 性重要性的启发式算法思想的提出具有十分重要的标志意义。目前，对r o u g h 集理 论的研究基于两种观点。一是代数观点，即以不可分辨关系为基础，通过引入上 近似集和下近似集，在集合运算上定义。二是信息论观点，即从信息论的角度对 r o u g h 集理论进行研究。一些学者基于信息熵理论对r o u g h 集理论进行了研究， 得到了r o u g h 集理论的信息观描述，也对这两者之间的关系进行了初步的研究。 信息熵是信息论的核心内容，基于条件熵的约简体现了决策信息系统的整体不确 定性，信息熵体现了约简规则集合的泛化能力。信息熵、决策熵和条件熵等从不 同的角度描述了决策信息系统的特征，主要体现在他们对不确定性和约简的影响。 目前对信息熵的扩充定义及算法研究是粗糙集研究的热点之一。例如扩展了的 基于信息熵的属性约简及其应用 s h a n n o n 的信息熵m 1 ，能够有效地对r o u g h 集模糊性进行度量，增益函数使其拥 有了补集的本质；通过信息熵概念1 的引入，形式化地给出了概念内涵的重要程 度，结合用户的兴趣度，对概念进行约简，提出了约简概念格渐进式构造算法等等。 但仍有一些问题需进一步的研究，如利用信息熵建立知识不确定性和模糊性之间 的联系，利用信息熵度量不完全决策表的不确定性，利用信息熵构造不完备决策 表知识约简的启发式算法等。 熵作为一种新的世界观，和“能”一样，普遍适应于自然界的各个领域。物 理学中的熵，最初是克劳修斯0 8 6 5 ) 把它作为描写系统的热力学态函数而引入的， 并把热力学第二定律表述为熵增原理。1 8 7 7 年，玻尔兹曼( b o l t z m a n ) 等价地引入了 统计意义的熵。热力学物质系统内部的微观本质，必须在宏观性质上体现出来， 当状态确定时，物质系统的热力学混乱度也一定，状态熵函数是混乱度的单调递 增函数，两者间的定量关系可用著名的波尔兹曼公式表述，该公式指明了熵是无 序的量度，即熵增大，无序程度增加。1 9 4 8 年，香农在其狭义信息论中，参照玻 耳兹曼熵引入信息熵来描写概率信息系统状态的不确定性。如果把物质系统可能 出现的状态视为一随机事件，则个随机变量x 的熵可以理解为在试验之前取值 不确定程度( 即无序程度) 的一种度量。 信息熵是信息论中的重要概念，在信息论中有着非常重要的应用。随着信息 理论的不断发展，信息熵在保持它基本性质和含义的基础上，它的内涵和应用范 围在不断地拓展，在许多科学研究领域都得到了新的应用。信息熵在光学领域， 在统计学的谱估计中哗，在生命科学领域，在医学领域中都有着广泛的应用。信 息熵是系统紊乱程度的测度。对一个具体的系统来说，如果这个系统随机性很大、 非常混乱、毫无秩序，则此系统的信息熵就一定很大。反之，如果一个系统是确 定的、具有一定的规则、服从一定的秩序，则此系统的信息熵就一定小。因此， 可以把信息熵引伸应用到对事物集合中一些相互对立性质的量度，判断事物集合 中的有序与无序、确定性与随机性、组织性与散漫性、规则性与杂乱性、简并性 与多样性，并对其相互对立的概念进行量度。信息熵具有以下几种基本性质：( 1 ) 对 第3 章基于信息熵的属性约简算法 称性；( 2 ) 确定性：( 3 ) 非负性；( 4 ) 扩展性；( 5 ) 可加性；( 6 ) 强可加性；( 7 ) 递增 性；( 8 ) 极值性；( 9 ) 上凸性。 3 1 1 粗糙集合中划分的概率表示 设u 为一论域【2 6 1 ，设p ，q 在u 上导出的划分分别为x ，y ( x = 五，置，以) ，y = x ，k ，k ) ) ，则p ，q 在u 的子集组成的。代数上的概 率分布及p 与q 的联合概率分布分别为： c x ：p ，= p 喜_ ，p 2 。五2 ，：p 丢奠， c y ：p ，= p 夏，p 复，：p 麓， 陋小 p 珊，p 勰，：淼， ，其中 舭，= 种啦一鹏，= 斜小墟m 舭唧= 钾， i = l ，2 ，l ；歹= 1 ，2 ，m 。其中，各个变量的概率定义如下：符号c a r d ( e ) 表示集合e 的基数：以置) = c a r