（计算机软件与理论专业论文）基于粗糙集理论的属性约简算法研究(2).pdf

摘要 2 0 世纪8 0 年代以来，随着商务贸易电子化，政府和企业事务自动化的迅速 普及，信息系统中累积了大规模的数据，数据丰富、信息贫乏成为当今数字化社 会面临的一个巨大挑战。如何从海量的、多样的数据中挖掘潜在的、有利用价值 的信息是当前数据挖掘的主要研究课题。粗糙集理论是波兰数学家z p a w l a k 于 1 9 8 2 年提出的研究模糊性和不确定性的数学工具。它的重要特点是不需要预先 给定某些特征或属性的数量描述而直接从给定问题的描述集合出发，在保持分类 能力不变的前提下，通过知识约简，导出概念的分类规则。知识约简是知识发现 和规则提取的重要手段，目前的知识约简算法主要是基于粗糙集理论，面对庞大 的数据量，高效快速的算法至关重要。 本文首先综述了粗糙集理论在国内外的研究现状，探讨了粗糙集理论的相关 概念、工作步骤和关键技术。然后提出了两种基于等价关系的高效属性约简算法： 1 ) 将粒计算和粗糙集理论相结合，给出了决策表系统中的粒子分解方法， 以及正域粒子空间和非正域粒子空间的计算方法，并提出在粒表示下以属性重要 性作为启发信息的属性约简算法。分析表明该算法时间复杂度较小，实验证明该 算法不仅能有效地对决策表进行约简，且效率高； 2 ) 将免疫思想融入遗传算法中，以避免遗传算法陷入局部最优，并把核概 念引入免疫遗传算法的初始抗体群用来提高算法的性能，依照决策属性对条件属 性的依赖度，结合抗体浓度提出基于免疫遗传算法的属性约简算法，实验表明该 算法能有效地对决策表进行约简，并能快速收敛于全局最优。 关键词：数据挖掘；粗糙集；粒计算；属性约简；免疫遗传算法 a b s t r a c t s i n c et h e1 9 8 0 s ，a l o n gw i t ht h ee l e c t r o n i cc o m m e r c e ，a sw e l la st h er a p i d p o p u l m i z a t i o no fa u t o m a t i o ni ng o v e r n m e n ta n de n t e r p r i s ea f f a i r s ，am a s so fd a t ai s a c c u m u l a t e di ni n f o r m a t i o ns y s t e m s ；”d a t ar i c ha n di n f o r m a t i o np o o r ”h a v eb e c o m ea g r e a tc h a l l e n g eo ft h ed i g i t a lc o m m u n i t y i nt h ev a s ta n d d i v e r s ed a t a , h o wt om i n e p o t e n t i a la n dv a l u a b l ei n f o r m a t i o ni st h em a i nr e s e a r c ht o p i c so fd a t am i n i n g r o u g h s e tt h e o r y , w h i c hi sp r o p o s e db yp o l i s hm a t h e m a t i c i a nz p a w l a ki nt h e1 9 8 2 ，i sa n e wm a t h e m a t i c a lt o o ls t u d i e df o rf u z z i n e s sa n du n c e r t a i n t y u n d e rt h ep r e m i s eo f m a i n t a i ni n v a r i a b i l i t yo ft h ec l a s s i f i e d a b i l i t y , w i t h o u tp r e - s e t t i n g t h en u m b e r d e s c r i p t i o no fc e r t a i nc h a r a c t e r i s t i c so ra t t r i b u t e sb u td i r e c t l yf r o mag i v e ns e to fa d e s c r i p t i o no f t h ep r o b l e m ，e d u c e dt h ec l a s s i f i c a t i o nr u l e so fc o n c e p tt h r o u g h k n o w l e d g er e d u c t i o ni st h ei m p o r t a n tf e a t u r eo fr o u g hs e t a ni m p o r t a n tm e a n so f k n o w l e d g ed i s c o v e r ya n de x t r a c t i n g r u l e si sk n o w l e d g er e d u c t i o n t h ec u r r e n t k n o w l e d g er e d u c t i o na l g o r i t h mi sb a s e dm a i n l yo nt h er o u g hs e tt h e o r y , i nt h ef a c e o fah u g ea m o u n to fd a t a , e f f e c t i v ea n dr a p i da l g o r i t h mi sc r u c i a l f i r s t l y ，t h er e s e a r c ha c t u a l i t i e sa th o m ea n da b r o a do fr o u g h s e tt h e o r ya r e s u m m e du pi nt h ep a p e r , w h o s er e l e v a n tc o n c e p t s ，w o r k i n gp r o c e s s e sa n dp i v o t a l t e c h n o l o g i e sa r ed i s c u s s e d m o r e o v e rt w or a p i da t t r i b u t er e d u c t i o na l g o r i t h m sa r e p r o p o s e db a s e do ne q u i v a l e n c er e l a t i o n ： 1 ) f i r s t l y ，c o m b i n i n gw i t hg r a n u l a rc o m p u t i n ga n dr o u g hs e tt h e o r y ，t h e g r a n u l a rd e c o m p o u n d i n gm e t h o da l o n gw i t ht h ec o m p u t i n gw a y so fp o s i t i v ea n d n e g a t i v eg r a n u l a rr e g i o ni nd e c i s i o nt a b l es y s t e ma r eg i v e n ，f u r t h e rm o r e t h ea t t r i b u t e r e d u c t i o na l g o r i t h mb a s e do ng r a n u l a re x p r e s s i o ni sp r o p o s e ，g i v i n gt h ea t t r i b u t e i 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 n a n a l y s i ss h o w st h a tt h et i m ec o m p l e x i t yo ft h i s a l g o r i t h mi ss m a l l e r , a n dt h ee x p e r i m e n t a lr e s u l tp r o v e st h a tt h ep r o p o s e da l g o r i t h m n o to n l yc a nr e d u c et h ed e c i s i o nt a b l ee f f i c i e n tb u tr a p i d 2 ) i no r d e rt oa v o i dt h eg e n e t i ca l g o r i t h mg e t i n gi n t op a r t i a lo p t i m u m ，t h e s e c o n da l g o r i t h mu s i n gi m m u n et h i n k i n gj o i n e di n t og e n e t i ca l g o r i t h m ，a n dt h ec o r ei s i n t r o d u c e dt h ei n i t i a la n t i b o d yc o l o n yo fi m m u n eg e n e t i ca l g o r i t h mt oi m p r o v e c a p a b i l i t y a c c o r d i n gt od e p e n d e n c eo fd e c i s i o na t t r i b u t ev s c o n d i t i o na t t r i b u t e ， c o m b i n i n gw i t ht h ec o n s i s t e n c yo fa n t i b o d y ，t h ea t t r i b u t er e d u c t i o na l g o r i t h mi s p r o p o s e db a s e do ni m m u n eg e n e t i ca l g o r i t h m t h ee x p e r i m e n tr e s u l ts h o w st h a ti tc a n r e d u c ed e c i s i o nt a b l ee f f e c t i v e l ya n dc o n v e r g er a p i d l yi nt h eg l o b a lo p t i m u m k e yw o r d s ：d a t am i n i n g ；r o u g hs e t ；g r a n u l a rc o m p u t i n g ；a t t r i b u t er e d u c t i o n ； i m m u n eg e n e t i ca l g o r i t h m i i i 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：起敏日期：弘螺年写月1 8 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“ ) 作者签名： 赵钛 导师签名： 、多可 日期：刎年g 月f g 日 日期：助8 年亏月i 富日 1 1 研究的背景和意义 第一章绪论 近年来，随着计算机、网络和通讯等信息技术的高速发展，商务贸易的电子 化，政府和企业事务自动化的迅速普及，产生了大规模的数据；同时日益增长的 科学计算和大规模的工业生产过程也提供了海量数据。数据丰富、信息贫乏是当 今数字化社会面临的一个巨大挑战。在海量数据背后隐藏着许多重要的信息，因 此人们希望对其进行更高层次的分析，以便能够更好地利用这些数据。目前的数 据库系统可以高效地实现数据的录入、查询、统计等功能，但是无法发现数据中 存在的关系和规则，无法根据现有数据库中的数据预测未来的发展趋势，缺乏挖 掘数据背后隐藏的知识的手段和方法。知识发现n 1 ( k n o w l e d g ed i s c o v e r y ，简称 l ( d d ) 和数据挖掘翻( d a t am i n i n g ，简称d m ) 正是在这种情况下产生和发展的一种 新型数据分析技术。数据挖掘是知识发现过程中的核心步骤，粗糙集( r o u g hs e t ) 理论作为一种应用于数据挖掘中的数学工具1 有着它不可替代的优点。 属性约简( a t t r i b u t er e d u c t i o n ) 是粗糙集理论中一个重要的研究课题。一般说 来，数据库中的数据属性并不是同等重要的，而且还存在冗余，这不利于做出正 确而简洁的决策。属性约简要求在保持数据库的分类和决策能力不变的条件下， 删除不相关或不重要的属性。人们总期望找到最小约简，但这已被证明是一个 n p 完全问题跚。由于在粗糙集的属性约简中约简属性集必须满足2 个条件，即 保持原分类质量不变和属性集中不含冗余属性，故粗糙集的属性约简是一个多约 束、多目标的搜索优化过程。尽管基本粗糙集理论与其他处理不确定性的理论相 比，具有不可替代的优越性，但是仍然存在着某些片面性与不足之处。例如：在 研究属性约简的问题时，考虑数据的规模是比较少的情形；对于海量数据的情形， 时间和空间复杂度较大。所以寻找快速、有效的启发式属性约简算法是研究粗糙 集理论的一个有意义的课题。 1 2 粗糙集理论的国内外研究现状 近年来，粗糙集理论已经应用于机器学习、决策支持、知识发现、专家系统、 模式识别等领域。目前对粗糙集理论的研究主要集中在求解属性的最小约简、较 小约简和最简规则集h ，5 1 。粗糙集有效算法方面的研究包括如何求等价类、上近 似、下近似、正区域、约简和核等等。现在国际上已经研制出了一些粗糙集工具 应用软件，如k d d r 是由加拿大r e g n i a 大学研制开发的基于可变精度粗糙集扩 展模型的数据库知识发现口1 系统。k d d r 系统曾成功应用于医学数据分析和电 信市场的决策分析等。l e r s 是美国k a n s a s 大学开发的基于粗糙集的实例学习系 统，该系统曾用于医学研究、气候预测和环境保护等阶1 。r o u g hd 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 g h 是挪威t r o l ld a t al n c 公司开发的，它包括数据输入、预处理、编辑、生成可辨 识矩阵、集合近似、约简、生成规则、预测和分析功能。r o s e t t a 是波兰华沙大 学和挪威科技大学联合开发的基于粗糙集的k d d 决策分析系统，该系统可以处 理多种格式的数据，如文本和数据库等，这些数据以决策表的形式存在于r o s e t t a 系统中，当决策表成功装载入p r o j e c t 后，系统使用粗糙集理论逐步分析数据， 最后得到决策规则。目前，国内学术界对粗糙集理论有了一定的研究，但对其在 数据挖掘中的应用还不够深入。现有的算法存在一定的缺点，这大大地阻碍了粗 糙集理论的应用。 当前，对粗糙集( r o u g hs e t ) 理论的研究集中在数学性质、粗糙集拓广、与其 它不确定方法的关系和互补及有效算法等方面： 1 ) 粗糙集理论数学性质方面的研究，主要讨论粗糙集的代数结构、拓扑结 构及粗糙集的收敛性问题。 2 ) 粗糙集拓广方面的研究主要涉及粗糙集模型( 或称变精确性粗糙集模型) 与对连续属性的离散化等。 3 ) 粗糙集理论与其他不确定性方法之间关系的研究中，目前主要讨论其与 模糊集理论和d s 证据理论的关系和互补。 4 ) 在粗糙集有效算法方面的研究，主要集中于： ( 1 ) 导出规则的增量式算法； ( 2 ) 约简的启发式方法； ( 3 ) 粗糙集基本运算的并行算法。 5 ) 基于粗糙集的逻辑是关于粗糙集的不确定推理的基础，发展这类逻辑的 2 理论基础也是目前粗糙集理论研究的重要课题。 粗糙集理论中有效算法的研究是粗糙集理论在人工智能研究中的一个主要 方向。目前，粗糙集理论中有效算法研究主要集中在规则提取、属性约简算法以 及与粗糙集有关的神经网络和遗传算法研究等。属性约简是粗糙集理论的核心问 题之一。属性约简的任务就是在保持知识表达系统中分类能力不变的情况下，删 除其中不相关或不重要的属性。但是己经证明求解所有约简和求解最小约简都是 n p h a r d 问题。属性约简与核的求解一直就是粗糙集理论研究的热点与难点。现 有的粗糙集属性约简算法大致可以分为三类： 1 ) p a w l a k 数据约简算法。这种方法按照属性约简的定义进行求解，需要对 条件属性集的幂集中的所有元素进行考察，因而具有指数型时间复杂度，该算法 具有很强的理论指导意义，但其计算速度慢，且不易于计算机实现，因此，其实 际应用的局限性较大。 2 ) 区分矩阵属性约简方法。波兰华沙大学的著名数学家s k o w r o n 阳1 提出的 区分矩阵是求最小约简的有利工具。通过区分矩阵得出核属性，根据核属性求区 分函数的最小析取范式，最后得到的每个析取分量对应着一个约简，因此可 以得到最小约简。算法的时间复杂度为d ( 2 吲掌h 母p 卜l o g u i ) ，其中x 为条件属 性的子集，a 为属性集合，妙i 叫为对象( 实例) 集合。该算法比p a w l a k 数据约简 算法的时间复杂度减少一半，并可以求出信息系统的所有约简，可以找到最小属 性约简；但该算法在处理海量数据的信息系统属性约简问题上不是非常有效的。 3 ) 启发式属性约简算法。目前，对这类约简算法的研究较多。主要有基于 遗传算法、通过属性重要度或区分矩阵中属性频度等启发信息来寻求信息系统的 约简。这类方法可以对大规模数据集进行处理。现有的关于属性约简的文献大部 分都是在基于属性重要度和基于区分矩阵两种算法的基础上提出，典型的有 x h u 提出的基于属性重要度的约简算法嘲，基于属性依赖度的约简方法n 帕，苗 夺谦等人的基于属性互信息的约简方法1 ，基于区分矩阵属性频率n 2 3 的约简算法 和基于关联矩阵n 3 1 等约简算法都各有优点。w r o b l c s w s k ij 等人n 帕提出的基于遗 传算法求最小属性约简的算法也得到比较好的效果。文献n 5 1 提出了一种在优化初 始群体基础上提高算法性能的启发式遗传算法，以属性重要度作为约简启发式信 息；代建华等n 明提出的算法是通过信息论中互信息来定义的属性重要度为启发式 3 信息进行遗传算法约简，具有较好的约简效果和收敛速度。 1 3 本文的工作 目前有很多求解最小约简的算法，至今，在那些大数据量高维数的决策表上 进行最小约简的求解还没有一种很好的解决方法。本文以粒计算和免疫遗传算法 为工具对属性约简算法进行研究，具体内容如下： 1 ) 综述了粗糙集理论的国内外研究现状，分析了粗糙集在属性约简的优势。 2 ) 分析和研究了经典粗糙集的属性约简理论。 3 ) 将粒计算理论和粗糙集理论相结合，提出了决策表系统中的粒子分解方 法，以及在粒表示下以属性重要性作为启发信息的属性约简算法，并进行了实例 分析。 4 ) 研究在遗传算法中引入免疫思想，提出基于免疫遗传算法的属性约简算 法，将核引入免疫遗传算法的初始抗体群来提高算法的性能，依照决策属性对条 件属性的依赖度，并结合抗体浓度，能维持进化过程中个体的多样性，从而提高 了算法的全局搜索能力，避免陷入局部最优。 1 4 本文的组织 本文章节及内容的安排如下： 第一章绪论。概述粗糙集理论的国内外研究状况；介绍本文的工作安排。 第二章粗糙集理论。介绍粗糙集理论的基本概念。 第三章基于粒计算的属性约简算法。基于粗糙集的等价关系构造粒子，提 出了决策表系统中的粒子分解方法，以及在粒表示下以属性重要性作为启发信息 的属性约简算法，并分析该算法的正确性和时间复杂度。 第四章基于免疫遗传算法的属性约简。提出在遗传算法中加入免疫思想， 并将核概念引入免疫遗传算法的初始抗体群来提高算法的性能，依照决策属性对 条件属性的依赖度，并结合抗体浓度，能维持进化过程中个体的多样性，从而提 高了算法的全局搜索能力，避免陷入局部最优。 第五章结论与展望。总结了本文的研究工作，阐明本文研究工作中的难点 和创新点，提出进一步研究的方向。 4 第二章粗糙集理论 粗糙集理论是波兰数学家z p a w l a k 于1 9 8 2 年提出的，研究模糊性和不确定 性的一种新的数学工具，它的重要特点是不需要预先给定某些特征或属性的数量 描述而直接从给定问题的描述集合出发，在保持分类能力不变的前提下，通过知 识约简，导出概念的分类规则。它能有效地处理不精确、不一致、不完备信息， 并从中发现隐含的知识，揭示潜在的规律。目前，粗糙集理论已被成功应用于机 器学习、人工智能、模式识别、数据挖掘、智能信息处理等领域。下面阐述粗糙 集理论的基础知识，作为后续章节的理论准备。 2 1 知识分类 设u 一西是感兴趣的对象组成的有限集合，亦即论域。任何子集x u ，称 为u 中的一个概念或范畴。为规范化起见，认为空集也是一个概念。u 中的任 何概念族称为关于u 的抽象知识，简称知识。u 上的一族划分称为关于u 的一 个知识库，它构成了一个特定论域u 的分类。 定义2 1 设r 是u 上的一个等价关系，c ，r 表示r 的所有等价类构成的集 合，k 】r 表示包含元素x umr 等价类。一个知识库就是一个关系系统 k 1 1 缈，r ) ，其中u 为非空有限集合，称为论域，尺是u 上的一个等价关系族。 定义2 2 设尺是u 上的一族等价关系，若p 尺，且p m ，则n p ( p 中 所有等价关系的交集) 也是一个等价关系，称为p 上的不可分辨( i n d i s c e r n i b i l i t y ) 关系，记为i n d p ) ，即 i n d ( p ) 一 o ，y ) 【，x ui 厂0 ，口) t ( y ，口) ，v a 互尸 且有 【x k p ) 一ni x 矗 r g p 这样u i n d ( p ) 表示与等价关系族p 相关的知识，称为k 中关于u 的p 基本 知识。为简单起见，用u p 代替u i n d ( e ) ，i n d ( p ) 的等价类称为知识p 的基本 5 概念或基本范畴，p 的基本概念拥有知识p 的论域的基本特性知识的基本模 块。 同样，也可以定义：当k 一，尺) 为一知识库，i n d ( k ) 定义为k 中所有等价 关系的族，记作切d ( k ) 一 i n d ( p ) i 乒p 尺】- 。 由上面的概念可知，知识实际上是一族等价关系，是区分论域中不同对象的 能力。它将论域分割成一系列的等价类，每个等价类之间是不可分辨的。 例2 1 表2 1 所示的个体集合 1 ，2 ，3 ，4 ，5 ，6 ) 称为论域，即所要考察的对象 全体。每个个体在四个属性( 头疼、肌肉疼、体温和流感) 上对应四个取值，那么 每个个体与其对应属性取值就构成了一个元组。如果按照某个或多个属性来描述 这些个体，就可以得到不同的分类知识。 表2 1 信息表 为方便起见，定义四个等价关系( 即属性) ：头疼墨，肌肉疼心，体温墨和 流感心，通过这些等价关系，可以得到下面四个等价类： u r = “1 ，2 ，3 ) ， 4 ，5 ，6 ) u 恐= “1 ，2 ，3 ，4 ， 5 ，6 u 玛= “l ，4 ) ， 2 ，5 ， 3 ，6 ) u 兄= “1 ，4 ，5 ， 2 ，3 ，6 ) 也可以按照属性的组合来分类，例如： u 假u r 2 ) = 1 ，2 ，3 ) ， 4 ) ， 5 ，6 ) ) 6 u 假u r ) = “1 ) ， 2 ，3 ) ， 4 ，5 ， 6 由上例可以看出，可以用不同的标准来对论域进行分类，得到不同的概念和 抽象，有的概念是需要的，而有的则不需要，数据挖掘就是要探寻有用的概念，并 得到概念之间的联系。 2 2 信息系统与决策表 2 2 1 信息系统 定义2 3 形式上，四元组i s1 ，a ，v ，厂) 称为一个信息系统( i n f o r m a t i o n s y s t e m ，简称i s ) 。其中u 表示对象的非空有限集合，称为论域；a 表示属性的 非空有限集合，v u 吲圪，屹表示属性a 的值域；厂：ux a 呻y 是一个信息函 数，它为每个对象的每一个属性赋予一个信息值，即v ae a ，x e u ，f ( x ，口) 屹。 若存在一个x e u ，口c ，f ( x ，口) 未知，( 记作f ( x ，口) 1 ) ，则称信息系统是不 完备的；否则称信息系统是完备的。在本小节中，如不做特殊说明，均认为信息系 统是完备的。 信息系统的数据以关系表的形式表示，关系表的行对应要研究的对象，列对 应对象的属性，对象的信息是通过指定对象的各属性值来表达。容易看出，一个 属性对应一个等价关系，一个表可以看作是定义的一个等价关系簇，即知识库。 知识约简可以转化为属性约简和值约简。 2 2 2 决策表 决策表是一类特殊而重要的知识表达系统，多数决策问题都可以用决策表形 式来表达。决策表可以根据知识表达系统定义如下： 定义2 4 对于信息系统i s 一，a ，v ，厂) ，如果a c u o ，c 称为条件属性 集合，d 表示决策属性集合，且c n d 。西，则称信息系统s 为决策表。 条件属性c 和决策属性d 的等价关系i d ( c ) 和i n d ( d ) 的等价类分别称为条 件类和决策类。 7 一个决策表中的决策属性有时是唯一的，称为单一决策；有时是不唯一的，称 为多决策。因为一个多决策表可以变换成单一决策表，所以，本文只研究单一决策 表。 2 3 不精确范畴，粗糙集与上、下近似集 上一节介绍的不可分辨关系是粗糙集理论的一个关键概念，它通常是和一个 属性集合联系在一起的。例如在表2 1 中，考虑属性头疼和肌肉疼，对于对象4 和对象6 ，其头疼的值都是“否，肌肉疼的值都是“是 。因此从属性集 头疼， 肌肉疼) 的角度来看，这两个对象是不可分辨的。由此构成的不可分辨集 “1 ，2 ，3 ， 4 ，6 ) ， 5 ) ) 称为基本集。任意多个基本集的并称为可定义集。 定义2 5 令x u ，尺为u 上的等价关系。当x 能表达成某些尺基本范畴 的并时，称x 是r 可定义的；否则称z 是r 不可定义的。尺可定义集也称作r 精 确集；r 不可定义集也称为尺非精确集或尺粗糙集。 对于粗糙集可以近似地定义，使用粗糙集的上近似( 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 6 给定信息系统s 一缈，a ，v ，) ，对于每个子集x 【，和一个等价关 系r 彳，定义两个子集： _ g o l j ( y e u r i y x ) 1 0 ( 一岬e u r i y n x 一西 分别称它们为x 的r 下近似集和尺上近似集。 由上近似和下近似，可以得到正区域( p o s i t i v er e g i o n ) 、负区域( n e g a t i v e r e g i o n ) 和边界域( b o u n d a r yr e g i o n ) 的概念。 定义2 7 给定信息系统胚= ，a ，v ，厂) ，对于每个子集xc _ u 和一个等价关 系尺g 彳，集合x 相对于尺的正区域定义为： p o s 置( x ) 一斛 定义2 8 给定信息系统i st 缈，a ，v ，厂) ，对于每个子集x u 和一个等价关 8 系尺彳，集合z 相对于r 的负区域定义为： n e g 足( x ) 一u 一肠 定义2 9 给定信息系统岱一( u ，a ，v ，厂) ，对于每个子集x 【厂和一个等价关 系尺彳，集合x 相对于r 的边界域定义为： b n 置( x ) 一r x 一丛 r x 或p o s ( x ) 是由那些根据知识r 判断肯定属于x 的u 中的元素组成的 集合；恝是由那些根据知识r 判断可能属于z 的u 中的元素组成的集合； 何) 是那些根据知识冗既不能判断肯定属于x 又不能判断肯定属于一x 的矽 中的元素组成的集合。 有了上述定义，可以得到上近似、下近似、正区域和边界域之间的关系，其 表示如下： r 岱) tp o s r 岱) u 6 伍) 。r _ ( x ) u b n 僻) 例2 2 在表2 2 所示的信息表中，若取属性集p = 头疼，肌肉疼) ， x 2 e 2 ，e 4 ，e 6 ) ，则有：u p ； 乜，乞，岛) ， 巳，气) ， ) 丛- p o s e ( x ) - 巳，e 6 ) ，p xs 巳，e 2 ，巳，巳，气， n e g p 僻) 一u 一蹦- 他 ，锄p 僻) 一p x 一丛t 奴，e 2 ，e 3 。 表2 2 信息表 9 2 4 近似分类和近似分类质量 集合的不精确性是由于边界域的存在而引起的，集合的边界域越大，其精确 性越低。为了更准确地表达这一点，引入了精度概念。 定义2 1 0 给定信息系统i s 一缈，a ，v ，) ，rc _ a ，设集合x 是论域u 上的 一个关于知识尺的粗糙集，则x 的尺近似精度为： 姒跏矧 其中x 一垂，lxl 表示集合x 的基数，若xt ，则定义僻) = l 。 精度用来反映了解集合x 的知识的完全程度。显然o s ( x ) 1 。当 ( x ) 一1 时，集合x 是尺可定义的；当( x ) 一【， r ( x 2 ) 1 蜀u 足一奴，e 2 ，e 3 ，气，气 ， 但) = ( 1 + 0 ) ( 6 + 5 ) = o 0 9 ， 妒) = ( 1 + o ) 6 ：0 1 7 。 将粗糙集的概念与普通集合论相比较，可以看出粗糙集的基本性质，如元素 的成员关系、集合的等价和包含等，都与不可区分关系所表示论域的知识有关。 因此，一个元素是否属于某一个集合，不是该元素的客观性质，而取决于对它的 了解程度；同样，集合的相等和包含也没有绝对的意义，也取决于对所研究问题 中集合的了解程度。 2 5 知识的依赖性与知识约简 知识约简是粗糙集理论的核心内容之一。众所周知，知识库中知识( 属性) 并不是同等重要的，甚至其中某些知识是冗余的。所谓知识约简，就是在保持知 识库分类能力不变的条件下，删除其中不相关或不重要的知识。通常只能根据经 验来选择权重，这依赖于人的先验知识。根据上节中介绍的知识尺对集合簇f 近 似分类的质l r 足伊) 这一概念，可以对论域样本属性的重要程度进行度量，而不 依赖于人的先验知识。 2 5 1 信息系统的知识约简 定义2 1 6 给定信息系统i s 一，a ，v ，) ，令r 为论域u 上的一个等价关系 簇，p e rc _ a ，如果i n d 僻) = i n d ( r 一 毋) ，则称p 为尺中不必要的；否则称p 为 尺中必要的。 1 2 定义2 1 7 给定信息系统i s = ，a ，v ，厂) ，令尺为论域u 上的一个等价关系 簇，p e r a ，如果每一个p e r 都为尺中必要的，则称r 为独立的，否则称r 为依赖的。 定义2 1 8 给定信息系统i si ，a ，v ，) ，设p 是定义在u 上的一个等价关 系族，p 中所有必要的关系组成的集合称为等价关系族尸的核，记作c o r e ( p ) 。 定义2 1 9 给定信息系统i si ，a ，v ，) ，设p 和q 是定义在u 上的等价关 系族，q p ，如果 ( 1 ) i n d ( q ) = i n d ( p ) ( 2 ) q 是独立的 则称q 为p 的一个约简。 显然，p 可以有多个约简。核与约简有如下关系： c o r e ( p ) = f i r e d ( p ) 其中，r e d ( p ) 表示p 的所有约简。可以看出，核这个概念有两方面的用处： 首先它可以作为所有约简的计算基础，因为核包含在所有的约简之中，并且计算 可以直接进行；其次可解释为在知识约简时它是不能消去的知识特征集合。 2 5 2 决策表的知识约简 决策表( d t , d e c i s i o n - m a k i n gt a b l e ) 的属性约简，即相对约简，就是要从条 件属性集合中发现部分必要的条件属性，使得根据这部分条件属性形成的相对于 决策属性的分类和所有条件属性所形成的相对于决策属性的分类一致，即和所有 条件属性相对于决策属性d 有相同的分类能力。 定义2 2 0 在决策表d t 一，c u o ，v ，厂) 中，p c ，设u d = ，k9 o o ，匕) 表示决策属性集合d 在u 上形成的划分，则决策属性集d 对于条件属性集p 的 相对正域定义为： p o s p ( d ) - u 化) d 的p 正域是u 中所有根据划分u p 的信息可以准确地分类到关系d 的等 价类中去的对象集合。 定义2 2 1 在决策表d ti ，c u d ，v ，厂) 中，r c ，若va e r ，有 p o s 置( d ) ；胁r 口 ( d ) 则称属性ae r 是尺相对于d 不重要的，否则称属性ae r 是尺相对于d 重 要的。对若v b c ，若b 任一元素相对于d 都是必要的，则称口相对于d 是对 立的。 定义2 2 2 在决策表d t 一，c o d ，v ，) 中，尺c ，s r ，若s 为尺的相 对约简，当且仅当s 是r 中d 独立的，且 p o s s ( d ) 2 p o s r ( d ) 定义2 2 3 在决策表d t 一，c u d ，v ，厂) 中，称c 中所有相对必要属性构成 的集合为c 的相对核，记为c o r e d ( c ) 。 定理2 1 在决策表d t 一缈，c o d ，v ，) 中，令r e d d ( c ) 表示条件属性c 的 所有相对约简，n - c o r e d ( c ) = n 蒯d ( c ) 证明：见参考文献 3 1 2 5 3 知识依赖度与分类精度 定义2 2 4 在决策表d t = ，c o d ，v ，厂) 中，决策属性d 对条件属性集c 的 依赖度定义为： 七一r e ( d ) 一峰掣 当k = 1 时，称d 完全依赖于c ；当0 k 1 时，称d 粗糙( 部分) 依赖于c ； 当k = o 时，称d 完全独立于c 。 在决策表中，不同的属性可能具有不同的重要性。为了找出某些属性( 或属性 集) 的重要性，一般的方法是从表中去掉一些属性，再来考察没有该属性后分类 1 4 会怎样变化。若去掉该属性后相应的分类变化较大，则说明该属性的重要性较高； 反之，说明该属性的重要性较低。 令c 和d 分别为条件属性集和决策属性集，属性子集c c 关于d 的重要 性定义为： s 瞎( c - ，c ，d ) 一y c ( d ) 一比p ) 定义2 2 5 在决策表d t 一，cud ，v ，) 中，p c 是定义在u 上的等价关 系族，x e u d ，知识p 将x 中每个类中元素的划分精度定义为： b ( x ) - q p x i i zl 2 6 本章小结 本章主要介绍了粗糙集理论的产生和特点，粗糙集理论是一种研究模糊性和 不精确性的新的数学工具，能有效地分析和处理不精确、不一致、不完整等各种 不完备系统，并从中发现隐含的知识，揭示潜在的规律。讨论了粗糙集理论对知 识的定义，以及粗糙集理论中各上近似、下近似、边界区，描述了知识表达系统 的组成，基于粗糙集理论的属性约简、决策表的定义。粗糙集理论的主要思想是 保持分类能力不变的前提下，通过知识约简，简化决策表。 第三章基于粒计算的属性约简算法 3 1 粒与粒计算简介 信息粒化( i n f o r m a t i o ng f 孤u l a t i o n ) 的基本思想出现在许多领域n ，如粗糙集、 f u z z y 集、证据理论、聚类分析、数据库、机器学习、数据挖掘等。1 9 7 9 年，f u z z y 集创始人美国科学家l a z a d e h n 町首次提出了模糊信息粒化问题，随后信息粒化 得到了人们越来越多的关注。h b o b s 于1 9 8 5 年提出了粒度( g r a n u l a d t y ln 钔的概念， 并对公式中的谓词定义了不可区分关系。l a z a d e h 在1 9 9 6 年到1 9 9 7 年期间第 一次提出粒计算( g r a n u l a rc o m p u t i n g ) 嘲川的概念。预计在不远的将来，粒计算将 会在软计算、知识发现、数据约简、数据挖掘中扮演越来越重要的角色。 人类认识、推理和决策都是在大量的信息中进行的。l a z a d e h 一1 认为人类 的认识和推理是由三个基本概念构成：粒化( g r a n u l a t i o n ) 、组织( o r g a n i z a t i o n ) 和因 果( c a u s a t i o n ) 。粒化涉及整体分解为部分；组织涉及部分结合成整体；而因果则 涉及原因与结果间的联系。他进一步提出粒计算，认为粒计算是一把大伞，覆盖 了所有有关粒的理论、方法、技术和工具。他指出：“粗略地说，粒计算是模糊 信息粒理论的超集，而粗糙集理论和区间计算是粒数学的子集”。 所谓信息粒实际上是人类为解决其在处理和存储信息上的能力有限问题的 一种反映，也就是人类在解决和处理大量复杂信息时，由于人类自身的能力有限， 只能把大量复杂信息按其各自的特征和性能将其划分成若干较简单的块，而每个 如此划分出来的块被看成是一个信息粒。这种处理信息的过程就称为信息粒化 ( i n f o r m a t i o ng r a n u l a t i o n ) 。例如，停车场问题的信息粒化，是指按车子的性能、 型号和大小将停车场划分成若干块，其中每一块停放一种性能或一种型号或一种 大小的车子，这里所说的块也就是信息粒。 粒计算( g r a n u l a rc o m p u t i n g ) 删是一种基于问题概念空间划分的新的智能 计算理论和方法，目前在国际上逐步得到了人工智能有关研究人员的重视。在人 工智能( a r t i f i c i a li n t e l l i g e n c e ，简称a i ) 研究中，对问题的求解，可以理解成将 整体分解成局部，直至分解成最小的能直接求解的基本问题，随后将各局部问题 的解合并，从而得到整体问题的一个解。在知识的表示和规则获取过程中，需要 给出粒的定义和粒的运算规则。关于粒计算问题，可以从以下两方面进行研究： 1 6 一是粒子的结构，二是粒子计算。前者主要解决粒子的形成、表示和解释，后者 主要解决粒子的使用问题。 本章以粒计算为基础，利用粗糙集中的等价关系来构建粒子，给出了粗糙集 中的粒子表示、粒子之间的运算规则，决策表系统的粒子分解方法以及在粒表示 下以属性重要性作为启发信息的属性约简算法。 3 2 决策信息系统的粒子分解 文献 2 6 1 中提出了一种基于粗糙集理论的粒度模型，使用属性值商的等价关 系来构造粒，为便于论述，下面先对文献1 2 6 的粒度模型做简单的介绍。 在粗糙集中，如果两个对象在某个条件属性集上的属性值均相等，则这两个 对象在该条件属性集上是不可分辨的。对于某个对象x ，设a ( x ) 是x 在属性a 上 的属性值，可以定义如下的粗糙逻辑性质： 性质l0 ，v ) ( 或写成n ，ae a ，y 圪) 是原子公式，原子公式是公式。 性质2 如果a 和b 是原子公式，那么- , a ，a b ，avb ，) ，a 呻曰是公式。 性质3 按性质l 和性质2 定义的公式，使用连接词一， ，v ，_ ，进行有限次 运算所组成的式子是公式。 根据以上性质可以看出，在等价关系下，某个属性集上属性值相等的对象可 以构成一个集合，且这些对象在该属性集上是满足等价关系，可以利用这个集合 来定义粒子。 定义3 1 t , a 1 ：函数f - 1 0 ，) 表示在属性口( 口彳) 上值为，的对象集合，决策信 息系统的粒子可定义为：g ，一( 0 ，y ) ，1 ( 口，y ”，其中( 口，y ) 为粒子g r 的语法，g r 被称为决策信息系统中的原子粒子。 设卿妒是形如( 口，1 ，) 的原子公式使用逻辑连接词一， ，v ，呻，付所得的逻辑组 合，- 1 p ) 表示满足逻辑组合驴的组合粒子。 使用粒子思想对信息系统进行直接处理，首要任务就是要获