（计算机应用技术专业论文）遗传算法信息熵结合属性约简算法研究.pdf

摘要 粗糙集( r o u g hs e t s ) 理论是由z p a w l a k 教授于2 0 世纪8 0 年代 初提出的一种用于处理不确定性和含糊性知识的数学工具，其基本思想 是在保持分类能力不变的前提下，通过知识约简，导出概念的分类规则。 它无需提供相关数据集合以外的任何先验信息，适合于发现数据库中隐 含的、潜在有用的规律，即知识，找出其内部数据的关联关系争特征。 近年来，粗糙集理论和应用取得了很大的成功，已成为软计算方法的重 要分支，其涉及的领域包括模式识别、机器学习、决策分析和决策支持、 知识获取、知识发现等。 首先本文介绍了经典( p a w l a k 型) 祖糙集的基本理论。其次介绍 了信息熵、遗传算法的基本思想在此基础上提出了一种新的属性绚简 算法。本文以信息论角度定义的属性重要性度量作为启发式信息，通过 构造一个埘d 删巧p 。p ( f 棚算予来引入启发式信息，使得选择的属性子 集的分类能力不变该算子体现了一种利用启发式信息的局部搜索技 术，使碍算法既保持整体优化特性，叉具有较怏的收敛速度主要用于 求解决蓑表中的相对属性约简 关键词：粗糙集曩性约简遗传算法信惠熵 a b s t r a c t r o u g hs e t 啪i n 谢a l i z e db yp r o f e s s o rz p a w l a ki i le a r l y1 9 8 0 s ，h 黔b e e n p r o v e dt o b e 蛐e x l l e n tm 幽m a t i c a lt l d e a l i n gw 曲u n c e r t a i n 柚dv a g u e d e s c r i 州o no fo b j e c 招，w b o b a s i ci d i st od e r i v ec i a s s 砺c a t i o nm l e so fc o n c e p t i o n b yk n o w l e d g e 硎u 曲o nw i 血t l l ea b i l 时o fc l 龉s i 妇i 仰u n c h 柚g e d i tm a yf i n dt 1 1 e h i d i r 培a n dp o 锄撕a ln 1 1 ，t l l 砒i sl 妒a w l e d g e ，脚m cd a t aw i t l l o m 锄yp r e j i m i i l a r yo r a d d i 廿o n a li n f 0 珊撕o n h lr e c e n ty e a r s ，私a ni m p o 栅tp a r to fs o f tc o m p u t i i l m u g h s e tt i l e o f y 锄d 溉印p l i c a l i o mh a v ep l a y e da ni m p o r t 锄tr o l e ，e s p e c 谢l y 访t l l ea r e a so f p a 佳e mr e c 倒廿0 n ，i i l a c h i n el e 枷抽g ，d e c i s i o na i l a l y s i s ，h l o w l e d g ed i s c o v e r ya 1 1 d k n o w l e d g ea c q u i s n i o n 咖 f i r s t i y t h i sc l s i c 4 lp a 【w l a kr o u g h髓t sb 踮e do nt h ee q u i v a l e n c er e la t l o ni s i n n o d u c e d 弛d 掣m e d ba l g o m i l i n si 直l f o m l a t i o na i 们p 弘s e c o n d l 斗i ti n t r o d u c eb 如i c i d e o i o 盱f 甜鲫e 廿ca l g o 斑h m 醐di 1 1 f b m 洲o nt l l 琳t h p o s e dt l l en e w sa 1 9 0 r i 岫 o fa t 口i b u t e m d u 硝册黜卿州h gt h es 咖谲c 蚰c eo f 附i sd e f i n e d 疗d mt h e v i e 、v p o i n to fi n f o n 嘣也e o r y 塘l j r i s 廿ci i l 】b m 蜥o n a ne 妊b c 虹v eh e u r i s t i cg e n e 蛞c a 1 9 0 r i 岫f o rm i l l i m 汹l l g i 砒i v er e d u 甜o ni sp 哪m e d an e wo p e r a t o ri su s e df o r i 1 1 打o d u c i n gm eh e u r i 娟ci n f o 朋埔廿s o 踮t 0m a i n t 8 i l l 曲ea b l i t yo f s 讯c a “o no f t h e 黼i b u t e s t n m a i n u s i n g 协鞠e k 也e l a n v e0 f 蛐晡b u t er c d u c 娃o n 第一章序言 1 1 研究的目的和意义 存现代社会，随着计算机应用的越来越广泛，每年都要积累大量的 信息，即数据。这些数据来自各种领域，如医疗机构、科学观察、公共 服务等等。这些数据中隐含着巨大有价值的信息。然而，从这些数据中 得出信息又是人力所不及的。所以，一种能分析数据，并提出新的为人 所理解的知识的计算机系统是非常有用的，而这一过程即是数据挖掘 ( d a t am i n i n g ，d m ) “。7 。还有很多和这一术语相近似的术语，如从数 据席中发现知识( k n o w l o d g ed i s c o v e r yi f ld a l a b a s e ，k d d ) “j 、数据分 析、数据融合( d a t af u s i o n ) 以及决策支持等。人们把原始数据看作是 形成知识的源泉，就像从矿石中采矿一样。原始数据可以足结构化的， 如关系数据库中的数据，也可以是半结构化的，如文本、图形、图像数 据，甚至是分布在网络上的异构裂数据。发现知识的方法可以是数学的， 也可以是非数学的：可以是演绎的，也可以是j 纳的。发现了的知识可 以被用于信息管理、肖询优化、决策支持、过程控制等，还可以用于数 据自身的维护。因此，数据挖掘是一门很广义的交叉学科，它汇聚了不 问领域的研究者。尤其是数据库、人工智能、数理统计、可视化、并行 计算等方面的学者和工程技术人员一“”。 特别要指出的是，数据挖掘技术从一开始就是面向应用的。它不仅 是而向特定数据库的简单检索查询调用，而且要对这些数据进行微观、 小观乃至宏观的统汁、分析、综合和推理，以指导实际问题的求解，企 图发现事件问的相互关联，甚至利用已有的数据对未柬的活动进行预 测。例如加拿大b c 省电话公司要求加拿大s i m o n f r a s e r 大学k d d 研究 组，根据其拥有十多年的客户数据，总结、分析并提出新的电话收费和 管理办法，制定既有利于公司又有利于客户的优惠政策1 。这样一束， 就把人们对数据的应用，从低层次的末端查询操作，提高到为各级经营 决策者提供决策支持。这种需求驱动，乃，比数抛库查询更为强大。同时 需要指出的是，这里所说的知识发现，不是要求发现放之四海而皆准的 真理，也不是要去发现崭新的自然科学定理和纯数学公式，更不是什么 机器定理证明。所有发现的知识都足相对的，是有特定j j 提和约束条件、 而向特定领域的，同时还要能够易于被用户理解，最好能用自然语吉表 达发现结果。函此数据挖掘和知识发现( d m k l ) ) 的研究成果是很讲求实 际的。 数据挖掘在许多领域，如医学和d n a 分析、金融、零售业、f 乜信业 等得到应用，井对他们的发展起了积极的作用。 进行数据挖掘的方法有许多，而租集( r o u g hs e t s ) 方法便是其中 的主要方法之一“。一般来讲，大多数机构建立数据库的目的是为了有 效的管理信息资源。换句话说，在大多数机构数据被存储在数据库中很 少是专门为了挖掘发现知识。因此，数据库会有许多不完善之处，常常 包含许多对发现规则来讲是冗余的和不必要的属性，不确定值或会导致 不精确测量的错误、噪音等。如果这些冗余属性不去掉，不仅发现规则 的时间复杂性增长，而且发现规则的质量下降。而粗集方法是一种采用 新方法来处理模糊性和不精确性知识的数学方法“。”3 。粗集方法可以用 来处理这些类型的问题，它可以对数据进行预处理，通过属性约简，去 掉冗余属性，从而可提高发现效率，降低错误率。 总的来说，随着k d d 的兴起，粗糙集理论越来越受到k d d 研究者的 重视有以下几点原因。 首先，k 叩研究的对象多为关系型数据库。关系表可被看作为粗糙 集理论中的决策表，这给粗糙集方法的应用带来了极大的方便。 第二，现实世界中的规则有确定性的，也有不确定性的。从数据库 中发现不确定性知识，为粗糙集方法提供了用武之地。 第三。从数据中发现异常，排除知识发现过程中的噪声干扰也是粗 糙集方法的特长。 第四，运用粗糙集方法得到的知识发现算法有利于并行执行，可以 极大的提高发现效率。对于大型数据库中的知识发现来说，这是非常关 键的。 第五， k d d 采用的其他技术，如神经网络的方法，不能自动的选 2 择合适的属性集，而利用粗糙集方法进行预处理，去掉多余属性，可以 提高发现效率。 第六，用粗糙集方法得到的决策规则及推理过程，比模糊集方法或 神经网络方法，更容易验证和检测。 所以，粗糙集方法在数据挖掘中的应用越来越广。 综上所述，通过应用粗集理论于数据挖掘的领域，能对大型数据库 中不完整 数据进行分析和学习，并取得了一定的成果，有着广泛的应用前景和重 要的应用价值。 1 2 国内外研究现状 1 2 1 国际会议及机构 自k 叩一词首次出现在1 9 8 9 年8 月举行的第1 1 届国际联合人工 智能学术会议以来。迄今为止，由美国人工智能协会主办的k d d 国际研 讨会已经召开了1 3 次，规模由原来的专题讨论会发展到国际学术大会， 人数由二三十人到超过千人论文收录数量也迅速增加，研究重点也从 发现方法逐渐转向系统应用直到转向大规模综合系统的开发，并且注重 多种发现策略和技术的集成，以及多种学科之间的相互渗透。其他内容 的专题会议也把数据挖掘和知识发现列为议题之一，成为当前计算机科 学界的一大热点。 世界上研究数据挖掘的组织、机构或大学很多。比较著名的如卡内 基梅隆大学( 有机器制造d m 、多媒体数据库d m 、互连网d m 三个研究中 心) 、斯坦福大学、麻省理工学院。著名研究机构如：a c m ( a c ms p e c i a l i n t e r e s tg r o u po nk n o w l e d g ed i s c o v e r yi nd a t aa n dd a t am i n i n g ) 、 k d n e t ( t h ee u r o p e a nk n o w l e d g ed is c o v e r yn e t w o r ko fe x c e ll e n c e ) 、 n c d m ( t h en a t i o n a lc e n t e rf o rd a t am i n i n g ( n c d m ) a tt h eu n i v e r s i t y o f1 1 1 i n o i sa tc h j c a g o ( u i c ) ) 历届k d d 国际学术会议一览表卜l f 时间l 地点l 会议名称i 参加人数i 收录论文比例数 1 9 8 9 61 r k s h o nk 叻；r k s h o do nk 叩3 0 ，2 ：l 1 9 9 1 7 l 怕r k s h o p0 n 曲di w o r k s h o po nk 叩 4 63 5 ：1 1 9 9 3 7 i 骱r k s h o do ni ( d dl w o r k s h 0 o 门k d d4 0 5 ：1 1 9 9 5 n t r e a lc a n a d a k d d - 1 9 9 53 4 05 ：1 一 ” 一 一 ”一 十f 一 。 1 9 9 6 峪! 如d0 r e g e n k d d - 1 9 9 6 4 5 咀h 一 。 1 9 9 7 8 ，帅o r tb e a c hl k d p l 9 9 79 7 ：1 1 0 ：3 l 。塑9 坠8 ：s 鲤盥 2 0 0 0 8 旧o s t o n j k ! 蔓l 艘9 al k d 卜2 0 0 0 ，。柳! ：捌鼽u f 聊匹鼬，嘲 ，2 0 0 2 6 e d m o n t o 鱼a l b e r t a 。c a n a d a ：2 0 0 3 7h s h i n g t o n 。d c ，u s 1 2 2 刊物、书籍、网站： k 加一2 0 0 l k d 沪2 0 0 2 k d d _ 2 0 0 3 。，。一一 j 一二二一ij i e e e 的k n o w l e d g ea n dd a t ae n g i n e e r i n g 会刊率先在1 9 9 3 年出版 了k d d 技术专刊。并行计算、计算机网络和信息工程等其他领域的国际 学会、学刊也把数据挖掘和知识发现列为专题和专干0 讨论，甚至到了脍 炙人口的程度。此外，在i n t e r n e t 上还有不少k 叩电子出版物，其中 以半月刊k n o w l e d g ed i s c o v e r yn u g g e t s 最为权威 ( h t t p ：w w w k d n u g g e t s c o m s u b s c r i b e h t m l ) 。i e e e 的k n o w l e d g e a n dd a t ae n g i n e e r i n g 会刊在1 9 9 3 年出版的k d d 技术专刊，所发表的 5 篇论文代表了当时k d d 研究的最新成果和动态，较全面地论述了k d d 系统方法论、发现结果的评价、k d d 系统设计的逻辑方法，集中讨论了 鉴于数据库的动态性冗余、高噪声和不确定性、空值等问题，k d d 系统 与其它传统的机器学习、专家系统、人工神经网络、数理统计分析系统 的联系和区别，以及相应的基本对策。6 篇论文摘要展示了k 叻在从建 立分子模型到设计制造业的具体应用。在网上还有许多自由论坛，如 d me m a i lc l u b 等。此外，数据库、人工智能、信息处理、知识工程等 领域的国际学术刊物也纷纷开辟了k d d 专题或专刊。 不仅如此，在i n t e r n e t 上还有不少k 叻电子出版物，其中以半月刊 k n o w l e d g ed i s c o v e r yn u g g e t s 最为权威，如要免费订阅，只需向 h t t p ：w w w k d n u g g e t s c o m s u b s c r i b e h t m l 发送一份电子邮件即可， 还可以下载各种各样的数据挖掘工具软件和典型的样本数据仓库，供 人们测试和评价。另一份在线周刊为d s 十( d s 代表决策支持) ，1 9 9 7 年1 0 月7 日丌始出版，可向d s t r i a l t g c c o m 提出免费订阅申请。在网上， 还有一个自由论坛洲e m a 儿c l u b ，人们通过电子邮件相互讨论d m k d 的热点问题。其它相关数据挖掘的站点有数百个之多，下面列出的是几 个较为著名的站点。h t t p ：w w a a a i o r g 、 h t t p ：w w w c a l d c s c m u e d u 、h t t p ：w w w c o m p e t i a c o m h o m e h t t p ：w 1 w c r i s p d m o r g 、h t t p ：w w w c r m 2 d a y c o m d a t a m i n i n g h t t p ：w 唧k d d r e s e a r c h o r g 、h t t p ：m l is w w w w k a p n l 、 h t t p ：a g e n t s w w w m e d i a m i t e d u g r o u p s a g e n t s 、 至于跚x d 的专业书籍，目前已达2 5 0 本之多，可以在任何大型书店找到 十本以上的专业书。 1 2 3 国内研究现状 与国外相比，国内对d m k d 的研究稍晚，没有形成整体力量。1 9 9 3 年国家自然科学基金首次支持对该领域的研究项目。目前，国内的许多 科研单位和高等院校竟相开展知识发现的基础理论及其应用研究，这些 单位包括清华大学、中科院计算技术研究所、空军第三研究所、海军装 备论证中心等。其中，北京系统工程礤究所对模糊方法在知识发现中的 应用进行了较深入的研究，北京大学也在开展对数据立方体代数的研 究，华中理工大学、复旦大学、浙江大学、中国科技大学、中科院数学 研究所、吉林大学等单位开展了对关联规则开采算法的优化和改造：南 京大学、四川联合大学和上海交通大学等单位探讨、研究了非结构化数 据的知识发现以及w e b 数据挖掘。 l ，2 4 嘲软件开发技术的现状及趋势 当前数据挖掘的软件已经发展到了第四代，下面说明了各代软件的基本 特点； 第一代数据挖掘软件 特点：支持一个或少数几个数据挖掘算法、挖掘向量数据 ( v e c t o r v a l u e dd a t a ) 、数据一般一次性调进内存进行处理、典型 的系统如s a l f o r ds y s t e m s 公司早期的c a r t 系统 ( w w w s a l f o r d s y s t e m s c o m ) 。 缺陷：如果数据足够大，并且频繁的变化，这就需要利用数据库 或者数据仓库技术进行管理，第一代系统显然不能满足需求。例如： 新加坡国立大学开发的c b a 系统。基于关联规则的分类算法，能从关 系数据或者交易数据中挖掘关联规则，使用关联规则进行分类和预测。 第二代数据挖掘软件 特点：与数据库管理系统( d b m s ) 集成、支持数据库和数据仓库， 和它们具有高性能的接口具有高的可扩展性。能够挖掘大数据集、以 及更复杂的数据集、通过支持数据挖掘模式( d a t am i n i n gs c h e m a ) 和数据挖掘查询语言增加系统的灵活性、典型的系统如d b m i n e r ，能通 过d m q l 挖掘语言进行挖掘操作。 缺陷：注重模型的生成，如何和预言模型系统集成导致了第三代 数据挖掘系统的开发例如：d b m i n e r 、s a se n t e r p r i s em i n e r 第三代数据挖掘软件： 特点：和预言模型系统之州能够无缝的集成，使得由数据挖掘软 件产生的模型的变化能够及时反映到预言模型系统中、由数据挖掘软 件产生的预言模型能够自动地被操作型系统吸收，从而与操作型系统 中的预言模型相联合提供决策支持的功能、能够挖掘网络环境下 ( i n t e r n e t e x t r a n e t ) 的分布式和高度异质的数据，并且能够有效地 和操作型系统集成。 缺陷：不能支持移动环境例如： s p s sc 1e m e n t i n e 它以p l 的 格式提供与预言模型系统的接口 第四代数据挖掘软件： 特点：目前移动计算越发显得重要，将数据挖掘和移动计算相结合 是当前的一个研究领域。第四代软件能够挖掘嵌入式系统、移动系统、 和普遍存在( u b i q u i t o u s ) 计算设备产生的各种类型的数据。p k d d 2 0 0 1 上k a r g u p t a 发表了一篇在移动环境下挖掘决策树的论文。k a r g u p t a 是 马里兰巴尔的摩州立大学( u n i v e r s i t yo f m a r y l a n db a l t i m o r ec o u n t y ) 正在研制的c a r e e r 数据挖掘项目的负责人，该项目研究期限是2 0 0 1 年 4 月到2 0 0 6 年4 月，目的是开发挖掘分布式和异质数据( u b i q u i t o u s 设备) 的第四代数据挖掘系统。 l 2 5 数据挖掘软件发展的三个阶段 独立的数据挖掘软件( 9 5 年以前) 特点：独立的数据挖掘软件对应第一代系统，出现在数据挖掘技术 发展早期。研究人员开发出一种新型的数据挖掘算法，就形成一个软件。 这类软件要求用户对具体的算法和数据挖掘技术有相当的了解，还要负 责大量的数据预处理工作。比如c 4 5 决策树，平行坐标可视化 ( p a r a l l e l c o o r d i n a t ev i s u a li z a t i o n ) 。 横向的数据挖掘工具集( 9 5 年开始) 发展原因：随着数据挖掘应用的发展，人们逐渐认识到数据挖掘软 件需要和以下三个方面紧密结合：1 ) 数据库和数据仓库；2 ) 多种类型 的数据挖掘算法：3 ) 数据清洗、转换等预处理工作。随着数据量的增 加，需要利用数据库或者数据仓库技术进行管理，所以数据挖掘系统与 数据库和数据仓库结合是自然的发展。现实领域的问题是多种多样的， 一种或少数数据挖掘算法难以解决挖掘的数据通常不符合算法的要求， 需要有数据清洗、转换等数据预处理的配合，才能得出有价值的模型。 发展过程：随着这些需求的出现，1 9 9 5 年左右软件开发商开始提供 称之为“工具集”的数据挖掘软件。 特点：此类工具集的特点是提供多种数据挖掘算法，包括数据的转 换和可视化。由于此类工具并非面向特定的应用，是通用的算法集合， 可以称之为横向的数据挖掘工具( h o r i z o n t a ld a t am i n i n gt o o l s ) 由 于此类工具并非面向特定的应用，是通用的算法集合，所以称之为横向 的数据挖掘工具 典型的横向工具有：i b mi n t e l l i g e n tm i n e r 、s p s s 的c l e m e n t i n e 、 s a s 的e n t e r p r i s em i n e r 、s g i 的m i n e s e t 、0 r a c l ed a r w i n 等 纵向的数据挖掘解决方案( 9 9 年开始) 发展原因：随着横向的数据挖掘工具的使用日渐广泛，人们也发现 这类工具只有精通数数据挖掘算法的专家才能熟练使用，如果对算法不 了解，难以得出好的模型。1 9 9 9 年开始，大量的数据挖掘工具研制者 开始提供纵向的数据挖掘解决方案( v e r t i c a ls o l u t i o n ) ，即针对特 定的应用提供完整的数据挖掘方案。于纵向的解决方案，数据挖掘技术 的应用多数还是为了解决某些特定的难题，而嵌入在应用系统中。如 一在证券系统中嵌入神经网络预测功能 一在欺诈检测系统中嵌入欺诈行为的分类识别模型 一在客户关系管理系统中嵌入客户成簇分类功能或客户行 为分析功能 一在机器维护系统中嵌入监检测或识别难以定性的设备故 障功能 一在数据库营销中嵌入选择最可能购买产品的客户功能 一在机场管理系统中嵌入旅客人数预测、货运优化功能 一在基因分析系统中嵌入d n a 识别功能 在制造生产系统中嵌入质量控制功能等 典型的纵向工具：k d l ( 主要用于零售业) 、o p t i o n s c h o i c e ( 主要 用于保险业) 、h n c ( 欺诈行为侦测) 、u n i c am o d e ll ( 主要用于市场营 销) 。 下面的表格卜2 列举了当前各类d m 软件或工具在市场上的使用情况 ： d a t am i n i n gt o o l sy o ur e g u l a r l yu s e ： 6 2 8r e s p o n d e r s ，1 2 5 2v o t e s s o r t e db yd e c r e a s i n gv o t e s s p s sc 1 e m e n t i n e( 1 7 6 ) s p s s a n s w e rt r e e ( 1 l o ) s a s( 1 0 2 ) e x c e l( 9 2 ) y o u ro w nc o d e( 8 7 ) c a r t m a r s( 7 6 ) s a se n t e r p ris em in e r( 7 6 ) o t h e rc o m e r c i a lt o o l s ( 5 1 ) m ic r o s o f ts q ls e r v e r ( 5 0 ) o t h e rf r e e o p e ns o u r c et 0 0 1s( 4 9 ) p r u d s y sx e l o p e s( 4 6 ) w e k a ( 4 4 ) i n s i g h t f u lm i n e r ( 3 8 ) r ( 3 7 ) c 4 5 c 5 o s e e 5( 3 6 ) m a t l a b( 3 2 ) i b mi n t e l l i g e n tm i n e r ( 2 2 ) 0 r a c l es u i t e( 1 9 ) 统计表明目前世界上比较有影响的典型数据挖掘系统主要有： s p s s c l e m e n t i n e ，w e k a ，s a s ，c a r t m a r s ，s p s s a n s w e r t r e e ，s a s e n t e r p r i s em i n e r ，m a t l a b ，m i c r o s o f ts q l s e r v e r ，i n s i g h t f u lm i n e r 等。 1 3 主要研究内容 首先本文介绍了经典( p a w l a k 型) 粗糙集的基本理论。其次介绍 了信息熵、遗传算法的基本思想。在此基础上提出了一种新的属性约简 算法。本算法是将信息论角度定义的属性重要性度量作为启发式信息引 入遗传算法。通过构造一个新算子来引入启发式信息，使得选择的属性 子集的分类能力不变。该算子体现了一种利用启发式信息的局部搜索技 术，使得算法既保持整体优化特性，又具有较快的收敛速度。主要用于 求解决策表中的相对属性约简。 9 第二章粗糙集基本理论 粗糙集理论是一种新的处理模糊和不确定性知识的数学工具。其主 要思想就是在保持分类能力不变的前提下，通过知识约简导出问题的决 策或分类规则”“。下面将阐述粗糙集理论的基础及其思想，作为后面章 节的理论准备。 2 1 知识与分类 在信息系统中，人们首先碰到的就是对知识的理解和表达。一般认 为，知识是人类实践经验的总结和提炼，具有抽象和普遍的特性，是属 于认识论范畴的概念。知识直接与真实或抽象世界有关的不同分类模式 联系在一起，任何一个物种都是由一些知识来描述的，利用物种不同的 属性知识描述，可以对物种产生不同的分类。 设u 是本文感兴趣的对象组成的有限集合，称为论域。任何子 集u 称为u 中的一个概念或范畴。为规范化起见，本文认为空集也 是一个概念。u 中的任何概念族称为关于u 的抽象知识，简称知识。u 上的一族划分称为关于u 的一个知识库，它构成了一个特定论域u 的分 类。 设r 是u 上的一个等价关系，u r 表示r 的所有等价类构成的集 合， x k 表示包含元素z u 的r 等价类。一个知识库就是一个关 系系统k = ( u ，r ) ，其中u 为非空有限集，称为论域，r 是u 上的一族等 价关系。 若p r ，且j ) 妒。则n p ( p 中所有等价关系的交集) 也是一 个等价关系，称为p 上的不可区分( i n d i s c e r n i b i l i t y ) 关系，记为 i n d ( p ) ，且有 【j j 肌f ( p ) = ! ，l x j r，n 一 k 一i ， 这样，u i n d ( p ) 表示与等价关系族p 相关的知识，称为k 中关于 u 的p 基本知识，i n d ( p ) 的等价类称为知识p 的基本概念或基本范畴。 事实上，p 基本范畴是拥有知识p 的论域的基本特性，即知识的基本模 块。 例如，给定一玩具积木的集合u = x 1 ，x 2 ，x 8 ) ，并假设这些积 木有不同的颜色( 红、黄、蓝) ，形状( 方、圆、三角) ，体积( 大、小) 。 因此，这些积术都可以用颜色、形状、体积这些知识来描述。例如一块 积木可以是红色、小而圆的，或黄色、大而方的等。如果根据某属性 描述这些积木的情况就可以按颜色、形状、体积分类。 2 2 不精确范畴，近似与粗糙集 令x ，r 为u 上的一个等价关系。当x 能表达成某些r 基本 范畴的并时，称x 是r 可定义的；否则称x 为r 不可定义的。r 可定义 集也称作r 精确集，而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 ) 来描述。 给定知识库k = ( u ，r ) ，对于每个子集x u 和一个等价关系r 加d ( 足) ， 定义两个子集： 墨z = y y ，月f y 。y )r 9 9 、 r = h ，u ，胄i y i f 2 一叭 分别称它们为x 的r 下近似集和r 上近似集。 集合6 ( 爿) = 见r 一称为x 的r 边界域；p d 卧( ) = 型称为x 的r 正域：一昭。( ) = u 一蹦称为x 的r 负域。显然， 见y = p o ( 肖) y 6 ( x ) 。 或p 傩。( x ) 是由那些根据知识r 判断肯定属于x 的u 中元素组 成的集合；砑是那些根据知识r 判断可能属于x 的u 中元素组成的集 合：6 ( j ) 是那些根据知识r 既不能判断肯定属于x 又不能判断肯定 属于x 的u 中元素组成的集合；疗曙。( z ) 是那些根据知识r 判断肯定 不属于x 的u 中元素组成的集合。 集合的不精确性是由于边界域的存在而引起的，集合的边界域越 大，其精确性越低。为了更准确地表达这一点引入了精度的概念。由等 价关系r 定义的集合x 的近似精度为： 州舻嚣 。， 其中x ；，l x 表示集合x 的基数。 精度用来反映本文对于了解集合x 的知议所知的完全程度。显然， o 口月( x ) l 。当口r ( ) = 1 时，集合x 为r 可定义的；当口。( 肖) 1 时，集合x 为r 不可定义的。 当然，也可以用其它景度来定义集合x 的不精确程度，比如，用x 的r 粗糙度户。( x ) 来定义： 风( 肖) 2 1 一( x ) ( 2 5 ) x 的r 粗糙度与精度恰恰相反，它表示的是集合x 的知识的不完全程度。 除了用数值( 近似程度的精度) 来表示粗糙集的特征外，也可以根 据上下近似的定义来表达粗糙集的另一个有用的特征，即拓扑特征。 下面定义四种不同的重要粗糙集： 1 ) 如果丝妒且肼u ，则称x 为r 粗糙可定义； 2 ) 如果型= 且r x u ，则称x 为r 内不可定义； 3 ) 如果鱼妒且r x = u ，则称x 为r 外不可定义； 4 ) 如果丛= 庐且蹦= u ，则称x 为r 全不可定义； 这个划分的直观意义如下：如果集合x 为r 粗糙可定义，则本文可 以确定u 中某些元素属于x 或x ：如果x 为r 内不可定义，意味着本 文可以确定u 中某些元素是否属于x ，但不能确定u 中任一元素是否 属于x ；如果x 为r 外不可定义，本文可以确定u 中某些元素是否属于 x ，但不能确定u 中任一元素是否属于x ；如果x 为r 全不可定义，则 本文不能确定u 中任一元素是否属于x 或x 。 粗糙集的数字特征表示了集合边界域的大小，但没有说明边界域的 结构；而粗糙集的拓扑特征没有给出边界域大小的信息，它提供的是边 界域的结构。因此在粗糙集的实际应用中，本文需要将边界域的两种信 息结合起来，既要考虑精度因素，又要考虑到集合的拓扑结构。 粗糙集理论还对集合类关于近似空间的分类问题定义了上近似和 下近似。令f = x l ，x 2 ，x n ) 是u 的一个分类或划分，这个分类独立 1 2 于知识r ，子集x i 是划分f 的类。f 的r 下近似和上近似分别定义为： f = 趔l ，丛2 星妇 ( 2 6 ) r ，= 尼r 1 ，尼r 2 一r 肋) ( 2 7 ) 有两个量度来描述近似分类的不精确性，第一个量度为根据知识r ， f 的近似分类精度： j 心i 口口( f ) = 等一 y 劂 爿l ( 2 8 ) 第二个量度为根据知识r ，f 的近似分类质量； 幽l 旷卜秆 协9 ) 近似分类的精度描述的是当使用知识r 对对象分类时，可能的决策 中正确决策的百分比；分类的质量表示的是应用知识r 能确切地划入f 类的对象的百分比。 将粗糙集的概念与普通集合论相比较，可以看出粗糙集的基本性 质，如元素的成员关系、集合的等价和包含等，都与不可区分关系所表 示的论域的知识有关。因此，一个元素是否属于某一个集合，不是该元 素的客观性质，而取决于对它的了解程度：同样，集合的相等和包含也 没有绝对的意义，而取决于对所研究问题中集合的了解程度。 2 3 知识约简与知识的依赖性 知识约简是粗糙集理论的核心内容之一。所谓知识约简，就是在保 持知识库分类能力不变的条件下，删除其中不相关或不重要的知识。当 了解一个论域中的样例的时候，可以通过知道其属性值来对样例进行处 理。但是在现实情况中，有时不知道一个样例的所有属性值，只能根据 部分属性值来进行判定；有时需要确定个论域中是否每个属性的重要 程度是一样的，因为度量不同属性值的代价可能不同。在专家系统中， 也会遇到类似的权重问题，重要性高的属性在作决策时赋予大的权重。 通常只能根据经验来选择权重，这依赖于人的先验知识。根据上节中介 绍的知识r 对集合簇f 近似分类的质量( f ) 这一概念，可以对论域样 本属性的重要程度进行度量，而不依赖于人的先验知识。 令r 为一族等价关系，p r ，如果加d ( 尺) = m d ( 月一 p ) ) ，则称p 为r 中不必要的：否则称p 为r 中必要的。如果每一个尸r 都为r 中必要的，则称r 为独立的，否则称r 为依赖的。 设q 妄尸，如果q 是独立的，且加d ( g ) = f d ( _ p ) ，则称q 为p 的一 个约简。显然，p 可以有多种约简。p 中所有必要关系组成的集合称为 p 的核，记作c o ，日( p ) 核与约简有如下关系： ，p ( p ) = ir 耐( p ) ( 2 一1 0 ) 其中。，p d ( p ) 表示p 的所有约简。可以看出，核这个概念有两方面的用 处：首先它可以作为所有约简的计算基础，因为核包含在所有的约简之 中，并且计算可以直接进行：其次可解释为在知识约简时它是不能消去 的知识特征集合。 田；田+ 田+ 田+ 圈 r f ， c 由 r 啊 r r 批r 扣j 图2 一l ：对象类别与分类的关系 不可区分关系r a ，b ，c ，d 可以看作每一个属性口 口，6 ，c ，d ) 的不 可区分关系r a ) 的重叠。这样，并不是所有的属性在“叠加”r a ，b ，c ，d 时都是必需的。一个约简是一个最小子集b 彳，a = a ，b ，c ，d ，使 r b = r a 。在本例中，约筒是 a ，b ， b ，d ) ，和 c ，d 。 1 4 在应用中，一个分类相对于另一个分类的关系十分重要。令p 和q 为u 孛豹等徐关系，q 鹳p 歪域记为尹豁， 窑) ，都 p o sp t 秘= 、擎 “0 ( 2 1 1 ) q 的p 难域是u 中所有根据分类u p 的信息可以准确地划分到关系 q 的等价类巾去的对象的集合。 令p 鞍q 为等徐关系族，霆p ，魏栗 p 。耐( p ) ( 加d ( q ) ) = p o 口划i p ， 哪) ( 加d ( q ) ) ( 2 一1 2 ) 粼称r 秀p 孛q 不警器豹；否粼r 秀p 中毪宓要靛。梵麓孳起霓，逸羯 p o 郎( q ) 代替印5 州，) ( j 耐( 9 ) 。如果p 中的每个r 都为q 必要的，则称 p 为q 独立的。 设s g ，s 巍p 熬q 约麓当显仅懑s 是p 豹q 独立子族豆 p s ( 9 。p 。邮( q ) ( 2 1 3 ) p 的q 约简简称为相对约简。p 中所裔q 必要豹原始关系构成的煞合称 麓p 静q 攘，篱称楚轺对孩，记秀饧( d 。褪对孩与穗薅终麓懿关系 如下： c 帆口( p ) 。i e 如( 户) ( 2 一1 4 ) 其中愆而( 印楚所有p 豹奄终篱褥褒静集合。 知识的依赖性可形式化地定义如下：令k = ( u ，r ) 是一个知识库， p ，9 足 1 ) 知识q 依赖于知识p ( 记作p j 9 ) 当且仅当涮( p ) g 玩d ( q ) ： 2 ) 知识p 与知识q 等价( 记作p z q ) 当且仅当p j q 且q j p ； 3 ) 知识p 与知识q 独立( 记作p q ) 当且仅当p jq 与q j p 均 不成立。 当知识q 依赖于知识p 时，也就是说知识o 是由知识p 导出的。有 时知识的依赖性可能是部分的，这意味着知识q 仅有部分是由知识p 导 出的，部分可导出可以由知识的正域来定义： 令k = ( u ，r ) 为一知识库，且尸，q r ，当 七= ，( q ) = j p 。j ，( q ) j i u l 时，( 2 1 5 ) 本文称知识q 是k 度依赖于知识p 的，记作户。q 。 当k = 1 时称q 完全依赖于p ；当o k i 时称q 粗糙依赖于p ；当k = 0 时称q 完全独立于p 。系数炸( q ) 可以看作q 和p 间的依赖度。 部分依赖性p j t 9 的量度k 不能完全反映u q 中类之阳j 的分 布情况，一些决策类可能完全由p 描述，但另一些可能仅仅由p 部分描 述。因此，本文需要使用一个系数，p ( ) = 多f f 肖 ，( u q ) 来 表明通过知识p 能将u q 中每个类的多少个元素正确划分。 这样，两个值，( q ) 和y ，) ，( x u q ) 给出了知识p 的“分类 能力”关于分类u q 的全部信息。 2 4 毅谈表达然统篙决策蓑 鲡谈表达在餐怒数撵楚遴中占毒卡努耋甏懿遗像。知识裹迭豢绕鹣 基本磁份鼹研究辩象的集合，焚予这整对象韵知识可通邋指定对象的嫠 本特缓和它们鹩特征缓寒描述。 形式上。隧元缝s ；( 玎，砭矿，力怒一个知谈表达系统，其中 玎；辩象的静奎有限集合，称为论域； 一：属毪的非窑霄黼集合； y 。三瓦，匕是属性a 秘德域； 、厂：酗x 囊岭矿是个信怠涵数，它必每个对黎的每个属性赋予个 售惑凭，帮垤蠢，善，( x ，蹄圪。 1 6 知识表达系统也称为信息系统。通常也用s = ( u ，爿) 来代替 s = ( u ，爿，矿，厂) 。 知识表达系统的数据以关系表的形式表示，关系表的行对应要研究 的对象，列对应对象的属性，对象的信息是通过指定对象的各属性值来 表达。容易看出，一个属性对应一个等价关系，一个表可以看作是定义 的一族等价关系，即知识库，知识约简可以转化为属性约简。 决策表是一类特殊而重要的知识表达系统，多数决策问题都可以用 决策表形式来表达。决策表可以根据知识表达系统定义如下： 设s = ( u ，爿，矿，、) 是知识表达系统，爿= c y d ，c id = 矿，c 称 为条件属性集，d 称为决策属性集。具有条件属性和决策属性的知识表 达系统称为决策表。 在决策表中，不同的属性可能具有不同的重要性。为了找出某些属 性( 或属性集) 的重要性，一般的方法是从表中去掉一些属性，再来考 察没有该属性后分类会怎样变化。若去掉该属性后相应的分类变化较 大，则说明该属性的强度大，即重要性高；反之，说明该属性的重要性 低。 令c 和d 分别为条件属性集和决策属性集，属性子集c c 关于d 的重要性定义为 o j l d ( c ) = ，( - ( d ) 一段q j ( d ) ( 2 1 6 ) 在决策表中，最重要的是决策规则的产生。设s = ( u ，彳，y ，) 是 一个决策表，4 = c y d ，c id = 妒，其中c 为条件属性集，d 为决策属 性集。令x ，和分别代表u c 与u d 中的各个等价类，如s ( x ，) 表示对 等价类z ，的描述，即等价类z ，对于各条件属性值的特定取值；毖s ( 一) 表示对等价类巧的描述，即等价类一对于各决策属性值的特定取值。决 策规则定义如下： ：出j ( 置) 斗如s ( y j ) ，iz ， ( 2 一1 7 ) 规则的确定因子( z ”y ，) = 陟iz 。i i x ，i ，o