（计算机应用技术专业论文）基于粗糙集的多知识库信息融合.pdf

摘要 粗糙集理论是2 0 世纪8 0 年代初由波兰数学家p a w l a kz 首先提 出的一种新型的处理模糊和不确定知识的数学工具，其基本思想是在 保持分类能力不变的前提下，通过知识约简，导出概念的分类规则。 目前，己在数据挖掘、机器学习、模式识别、决策分析、人工智能、 故障检测等方面得到了广泛的应用。 本文主要对基于粗糙集产生多知识库方法以及其决策的融合问 题进行了研究。用粗糙集理论的方法根据一个数据库建立单个知识 库，往往很难保证其完备性。这样的知识库在分类新对象时有可能出 错。论文通过研究粗糙集产生多知识库的基本原理，给出了多知识库 的形式化定义，完善了符号体系。并在此基础上给出了一种基于粗糙 集产生多知识库的新算法，并与其它算法相比较，说明该算法的结果 具有更好的完备性。 在用多知识库来对新对象进行分类识别的过程中，很关键的问题 是如何对多个决策结果进行融合得到最终的决策。目前，对于多个决 策结果仅仅是通过简单的组合，造成分类识别的准确性和可信度较 低。论文根据多源信息融合原理，对多个决策结果进行融合，研究了 一种基于证据理论的融合算法，该算法可以提高整个分类识别的准确 性和可信度。 属性值的约简是粗糙集理论的核心内容之一。它的目的就是在保 持规则集的分类能力的条件下，删除多余属性值，进一步简化规则集。 从而，得到最小的知识库。本文针对粗糙集理论中值约简这个重要问 题进行了研究，给出了一种利用决策规则质量的属性值约简算法。该 算法比现有的值约简算法更简化，并用实例说明了其有效性。 最后，对全文进行了总结，并指出有待进一步研究和完善的问题。 关键词：粗糙集，多知识库，决策规则质量 a b s t r a c t r o u 曲s e tt h e o r y , i n t r o d u c e db yp a w l a kz i ne a r l y 19 8 0 s ，i sa n e wm a t h e m a t i c a lt o o ld e a l i n gw i t hv a g u e n e s sa n du n c e r t a i n t y t h e b a s i ci d e ai st od e r i v ec l a s s i f i c a t i o nr u l e so fc o n c e p t i o nb yk n o w l e d g e r e d u c t i o nw i t ht h ea b i l i t yo fu n c h a n g e dc l a s s i f i c a t i o n i nr e c e n ty e a r s ，i t h a sb e e nw i d e l yu s e di nt h ea r e ao fd a t am i n i n g ，m a c h i n el e a r n i n g ， p a r e mr e c o g n i t i o n ，a r t i f i c i a li n t e l l i g e n c e ，f a u l td i a g n o s i s ，e t c t h er e s e a r c hw o r k si nt h et h e s i si sg e n e r a t i n gm u l t i p l ek n o w l e d g e b a s e su s i n gr o u g hs e ta n df u s i o np r o b l e mo fd e c i s i o nr u l e a c c o r d i n gt o ad a t a b a s ew i t hr o u g hs e tm e t h o dt os e tu pa ni n d i v i d u a lk n o w l e d g eb a s e ， i ti sv e r yd i f f i c u l tt og u a r a n t e ei t sc o m p l e t e n e s s s u c hak n o w l e d g eb a s e m a ym a k em i s t a k e sw h i l ec l a s s i f y i n gt h en e wt a r g e t t h r o u g hr e s e a r c h t h eb a s i cp r i n c i p l eo f g e n e r a t i n gm u l t i p l ek n o w l e d g eb a s e su s i n gr o u g h s e t ，t h et h e s i sp r o v i d e st h e f o r m a l i z a t i o nd e f i n i t i o no f m u l t i p l e k n o w l e d g eb a s e si no r d e rt op e r f e c ts y m b o l i cs y s t e m an e wa l g o r i t h m o f g e n e r a t i n gm u l t i p l ek n o w l e d g eb a s e si sp r e s e n t e db a s e do nr o u g hs e t t h en e wa l g o r i t h mi sm o r ec o m p l e t i v et h a nt h ea l g o r i t h ma tp r e s e n t d u r i n gt h ep r o c e s so fc l a s s i f y i n ga n dd i s c e r n i n gt h en e wt a r g e t u s i n gm u l t i p l ek n o w l e d g eb a s e s ，t h ek e yp r o b l e mi sh o w t of u s em a n y d e c i s i o n si no r d e rt og e tt h ef i n a ld e c i s i o n a tp r e s e n t ，t og e tt h ef i n a l d e c i s i o no n l yp a s sas i m p l ec o m b i n a t i o no fs e v e r a ld e c i s i o n s s ot h e a c c u r a c ya n dc r e d i b i l i t yo ft h ef i n a ld e c i s i o na r el o w e r a c c o r d i n gt ot h e p r i n c i p l eo ff u s i n gm u l t i p l es o u r c e i n f o r m a t i o nan e wa l g o r i t h mi s p r e s e n t e db a s e do ne v i d e n c et h e o r y t h ea l g o r i t h mc a ni m p r o v et h e a c c u r a c ya n dc r e d i b i l i t yo ft h ef i n a ld e c i s i o n t h ev a l u er e d u c t i o ni so n eo ft h eh i g h l i g h to fr o u g hs e tt h e o r y i t s p u r p o s ei st h a tr e d u c e ss u p e r f l u o u sa t t r i b u t e sv a l u ea n dm a k e st h er u l e s e tm o r eg e n e r a l i z a b l eo nt h ec o n d i t i o nt h a tk e e pc l a s s i f i c a t i o nc a p a c i t y o ft h er u l es e t a c c o r d i n g l y , i tc a ng e tt h el e a s tk n o w l e d g eb a s e 。t h i s p a p e rd i s c u s s e so n ei m p o r t a n ti s s u ei nr o u g h s e tr e s e a r c hw h i c hi sv a l u e r e d u c t i o n av a l u er e d u c t i o na l g o r i t h mi sp r e s e n t e db a s e do nd e c i s i o n r u l eq u a l i t y t h en e wa l g o r i t h mi sb r i e f e rt h a nt h ea l g o r i t h ma tp r e s e n t 1 i t h ee x p e r i m e n t a la n d p e r f o r m a n c es t u d i e ss h o wt h a ti ti sw o r k a b l e f i n a l l y , ar e c a p i t u l a t i v ec o n c l u s i o ni sg i v e n ，a n dt h ef u t u r ef e s e a r c h d i r e c t i o n sa r ep r o p o s e d k e yw o r d s r o u g hs e t ，m u l t i p l ek n o w l e d g eb a s e s ，d e c i s i o nr u l e q u a l i t y i l i 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致 谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得中南大学或其他单位的学位或证书而使用过的材 料。与我共同工作的同志对本研究所作的贡献均己在在论文中作了 明确的说明。 作者签名：星盔日期：兰! ! ! 年三月卫目 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位 论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论 文：学校可根据国家或湖南省有关部门规定送交学位论文。 雠名：堕翮签缸魄碰年上月血 硕士学位论文第一章绪论 第一章绪论 粗糙集理论是一种处理模糊和不精确性问题的新型数学工具。其主要思想 是，在保持信息系统分类能力不变的前提下，通过知识约简，导出问题的决策 或分类规则。目前，粗糙集理论已被应用于机器学习、故障诊断、控制算法获 取、过程控制以及关系数据库中的知识获取等各种应用领域，并取得了巨大的 成功。本章介绍了粗糙集的提出背景、特点、研究现状和粗糙集理论与其它智 能理论的关系，以及论文研究的内容和结构。 1 1 粗糙集理论的产生和发展 1 1 1 粗糙集理论提出的背景 众所周知，在经典逻辑中只有真、假二值，但实际上有大量含糊现象存在 于真与假之间。比如，在医学领域中的“健康”和“生病”就不可能精确的判 断其真假性。因此，长期以来许多逻辑学家和哲学家就致力于研究含糊概念。 早在1 9 0 4 年，谓词逻辑的创始人f r e g eg 就提出了含糊( 德文v a g u e ) 一词， 并把它划分到边界区域，也就是说在论域上存在这样的个体对象，它既不属于 某个子集，也不属于该子集的补集。二十世纪六十年代初，z a d e hla 提出 了模糊集这个概念，不少理论计算机科学家和逻辑学家试图以模糊集为工具， 解决f r e g eg 提出的含糊概念，但由于模糊集没有给出描述这一含糊概念的数 学公式，因而无法计算出它的边界区域上具体含糊元素的数目。到了八十年代 初，p a w l a kz 针对f r e g eg 提出的边界区域思想提出了粗糙集【2 】，他把那些无 法确认的个体都归于边界区域，并把上近似集和下近似集之差集定义为边界区 域。由于上、下近似集可以通过等价关系给出确定的数学公式描述，所以在真 假二值之间的含糊程度可以计算，从而实现了f r e g eg 的边界区域思想。 1 1 2 粗糙集理论的特点 粗糙集理论是一种刻划不完整性和不确定性的数学工具，能有效地分析不 精确、不一致、不完整等各种不完备的信息。粗糙集理论依据对某一概念的支 持程度对问题的论域划分成三部分：肯定支持此概念、肯定不支持此概念和可 能支持此概念。其有以下特点【3 5 l ： 硕士学位论文第一章绪论 1 它能处理各种数据，包括不完整的数据以及拥有众多变量的数据： 2 它能处理数据的不精确性和模棱两可，包括确定性和非确定性的情况： 3 它能求得知识的最小表达形式和知识的各种不同颗粒层次； 4 它能从数据中揭示出概念简单、易于操作的模式： 5 它能产生精确而又易于检查和证实的规则，特别适于智能控制中规则的 自动生成。 此外，与其他软计算工具相比，粗糙集具有很强的定性析能力，即不需要 预先给定某些特征或属性的数量描述，如统计学中的概率分布、模糊集理论中 的隶属度或隶属函数等，而是直接从给定的信息出发，通过不可分辨关系和不 可分辨关系确定问题的近似域，从而找烈隐含在数据中的内在规律。 1 1 3 粗糙集理论的研究现状与前景 1 9 8 2 年波兰学者p a w l a kz 提出粗糙集理论以后，由于当初的研究大多数 是波兰文发表的，因此这项研究当时并没有引起国际计算机界和数学界的重视， 研究地域仅局限于东欧一些国家。此后，粗糙集理论引起了许多数学家、逻辑 学家和计算机研究人员的兴趣，他们在粗糙集的理论和应用方面作了大量的研 究工作。1 9 9 1 年，p a w l a kz 的专著“r o u g hs e t s ：t h e o r e t i c a la s p e c t so f r e a s o n i n g a b o u td a t a 6 1 和1 9 9 2 年，s l o w i n s k ir 主编的“i n t e l l i g e n td e c i s i o ns u p p o r t ： h a n d b o o ko f a p p l i c a t i o n sa n da d v a n c e so f r o u l g hs e t st h e o r y ”【7 j 的问世，对这一 段时期理论和实践工作的成果作了较好的总结，同时促进了粗糙集在各个领域 的应用。 粗糙集理论的生命力在于它具有较强的实用性，从诞生到现在虽然只有二 十几年的时间，但已经在许多领域取得了令人鼓舞的成果。它近年来受到国际 上越来越多学者的关注，粗糙集理论的国际学术会议已逐步发展为年会2 1 ， 成立了粗糙集的国际学术团体，并在i n t e m e t 上定期发布电子公告。由于粗糙集 能够定量处理不完备和不确定的信息和数据，因此它作为一种具有极大潜力和 有效的知识发现工具受到学者们的广泛关注。目前，对粗糙集的研究主要在以 下两个方面： 1 粗糙集理论的理论方面的研究 ( 1 ) 粗糙集理论模型的推广 粗糙集理论模型的推广一直是粗糙集理论研究的主流方向，目前主要有两种 思路，分别是构造性方法和公理化方法【l ”。其中较为实用的是构造性方法。构造 性方法是对原始粗糙集模型的般性推广，即从近似空间的概念出发研究粗糙集 及其近似算子。它是以论域上的二元关系或布尔子代数作为基本要素的，然后导 硕士学位论文 第一章绪论 出粗糙集代数系统。这种方法所研究的问题往往来源于实际，所建立的模型有很 强的应用价值，其主要缺点是不易深刻了解近似算子的代数结构。 粗糙集的三个基本概念是论域空间、等价关系和概念集合。因此，构造性方 法的粗糙集模型推广分别有将论域从一个推广到多个，将二元等价关系推广为多 元等价关系以及将近似空间进行推广三个分支。 目前，从论域方向推广的只有一种双论域的情况【1 4 1 ，这时的二元关系就变成 为两个论域笛卡尔乘积的一个子集。对于将论域推广到多个的情形来研究粗糙集 理论的文献目前我们还未见到。 从等价关系方向的推广j 一种是将论域上的二元等价关系推广成为任意的二 元关系得到了一般关系下的粗糙集模型【l5 j ；另一种是将对象x 所在的等价类看成 是一个邻域，从而推广导出了基于邻域算子的粗糙集模型【l6 】；也有将由关系导出 的划分推广成为一般的布尔子代数，以此出发去定义粗糙集和近似算子的1 1 7 j ：更 般的有将普通关系推广成模糊关系或模糊划分而获得模糊粗糙集模型。 从近似空间方向的推广，是与其它处理不确定、不精确或模糊的理论( 如概 率论、模糊数学、信息论、证据理论等) 结合起来进行研究的。当知识库中的知 识是由于随机原因或经统计得到的，即知识库中的知识很可能是不确定的，很多 学者提出了统计( 或概率) 粗糙集模型 1 8 - 2 0 1 ，可变精度租糙集模型实质上也可以 归入这类模型，寻求具有最小风险的b a y e s 决策问题也可以转化为这类模型。这 一类模型在数据分析的增量式机器学习中有重要应用【2 ”。目前所见到的此类模型 中，近似空间中的二元关系大都是等价关系，对于非等价关系给出的情况文章的 尚没见到。基于随机集的粗糙集模型冽既是对基于邻域算子的粗糙集模型的推 广，又适用于双论域情形，同时也是对统计粗糙集模型的推广。 代数方法也称公理化方法( 有时也称为算子方法) ，这种方法不是以二元关 系为基本要素，它的基本要素是一对满足某些公理的一元近似算子，即粗糙代数 系统中近似算子是事先给定的。这种方法研究的明显优点是能够深刻了解近似算 子的代数结构，其缺点是应用性不够强。 近似算子的某些公理能保证有一些特殊类型的二元关系的存在，使这些关系 能够通过构造性方法产生给定的算子；反过来，由二元关系通过构造性方法导出 的近似算子一定满足某些公理，使这些公理通过代数方法产生给定的二元关系。 公理化方法的研究一开始只局限于粗糙代数系统，即公理与二元等价关系相 对应情形，后逐渐发展到一般关系下的粗糙集系统 2 3 , 2 4 。至今为止，关于公理化 方法的粗糙集理论研究大多局限于经典集情况，对于模糊集情况虽有讨论【2 “，但 比较少。 硕士学位论文 第一章绪论 ( 2 ) 粗糙集理论数学性质方面的研究 粗糙集理论数学性质方面的研究主要是对粗糙集理论中知识的不确定性问 题进行理论研究，包括讨论粗糙集代数结构( s t o n e 代数等) 、拓扑结构和粗糙 逻辑与推理等问题i 。 粗糙集理论的研究不断深入，它与其他数学分支的联系也更加显得紧密。 例如，从算子的观点看粗糙集理论，与之关系比较紧密的有拓扑空间、数理逻 辑、模态逻辑、格与布尔代数、算予代数等：从构造性和集合的观点看，它与 概率论、模糊数学、证据理论、图论、信息理论等联系较为密切。粗糙集的理 论研究需要以这些理论作为基础，同时也相应地带动了这些理论的发展。 目前，粗糙集理论研究与应用只限于对数据给出的知识问题进行处理，对 于文本和连续图像问题的处理尚未见到【2 7 1 。由于随机集理论在图像处理中已获 得了成功的应用，所以，对粗糙集理论与随机集理论结合的进一步研究有望使 它在图像处理上获得成功。 纯数学理论与粗糙集理论结合的研究导致了新的数学概念的出现，例如， “粗糙逻辑”、“粗糙理想”和“粗糙半群”，等等。随着粗糙结构与代数结构、 拓扑结构、序结构等各种结构的不断整合，必将推动粗糙集理论的快速发展【2 引。 ( 3 ) 约简算法的研究 粗糙集的核心技术为约简，是研究的焦点之一。p a w l a k 提出了对应属性约 简和值约简概念的最小约简，可以自动生成更简洁的规则，去除决策表中大量 不必要的知识。之后，众多学者纷纷提出了新的约简方法，如w r 6 b l e w s k ij 提 出用遗传算法寻找最小约简【2 9 】，王国胤等提出了基于可辨识矩阵和逻辑运算的 约简算法【3 0 1 。由于寻找最小约简是n p h a r d 问题【3 ”，p a w l a k 提出了近似最小约 简的算法，s a p i e c h ap 、s l c e z a kd 与周育健【3 2 】等也从应用角度提出了近似算法， 苗夺谦等从信息论的角度提出了知识约简的一种启发式算法【3 3 1 ，s k o w r o n 提出 能够在决策表中有冲突和不一致的情况下获取规则的算法1 3 4 。 此外，还有一些粗糙集理论方面的研究，比如粗糙集的数学性质方面的研 究和粗糙逻辑与推理以及粗糙集理论和其他方法的结合。 2 粗糙集理论的应用方面的研究 ( 1 ) 围绕粗糙集理论与应用研究，开发出相应的软件支撑系统。 l e r s ( 1 e a m i n gf r o me x a m p l e sb a s e do nr s ) 系统是美国k a n s a s 大学开发的基 于粗糙集的实例学习系统，是用c o m m o nl i s p 在v a x 9 0 0 0 上实现的。该系统 曾用于医学研究、气候预测和环境保护等，已在n a s a sj o h n s o n ( n a t i o n a l a e r o n a u t i c sa n ds p a c ea d m i r f i s t r a t i o n 美国国家航空和宇宙航行局、空间中心应用 了多年，充分显示出它在利用专家系统进行全球气候变化研究中所起的作用【3 卯。 硕士学位论文第一章绪论 k d d r 系统是由加拿大r e g i n a 大学研制的，它基于可变精度粗糙集扩展 模型，采用知识发现的决策矩阵方法。该系统是在u n i x 系统下用c 语言实现 的，它具有x w i n d o w s 的菜单驱动界面，该系统成功应用于医学数据分析、电 信市场的决策分析及水资源调度等口。 r o u g hd a s 和r o u g hc l a s s 是波兰p o a z n a n 工业大学计算科学研究所智能 决策支持系统实验室研制的。该系统实现了p a w l a k 的基本粗糙集模型和可变精 度粗糙集模型。它们对任务分别执行解释和描述，r o u g hd a s 执行信息系统数 据分析任务，r o u g hc l a s s 支持新对象的分类，并成功应用于医学、药剂学、技 术诊断、金融和管理科学、图像与信号处理、软件工程评估等 3 ”。 r o u g he n o u 曲是挪威t r o l ld a t a l n c 公司开发的，包括数据输入、预处理、 编辑、生成可辨识矩阵、集合近似、约简、生成规则、预测和分析【3 8 1 。此外， 我国也有一些系统如在国家8 6 3 计划的资助下，周育健等开发了l i s p 语言环境 下的基于粗糙集的表示语言和中国科学院计算技术研究所开发的k d t 和南京 大学研制的k n i g h t 等。 ( 2 ) 粗糙集理论在实际应用过程中涌现了很多成功的范例【8 。“。 d u n t s c hi 、a na 、g r z m a l a b a s e 、s w i n i a r s k ir 等在租糙集预测方面迸行 了理论与应用研究，k o s t e kb 、b r i n d l ed 与c z y z e w s k ia 分别在语音识别方 面做了大量工作，其中c z y z e w s k ia 采用粗集作为神经网络的前后端处理， s w i n i a r s k ir 。将粗糙集理论与神经网络结合起来进行手写字符识别及图像纹理 识别，l i n g r a sp 、m i t r as 与n g u y e n 分别提出了粗糙集神经网络。我国关于这 方面的应用尚不见报道。 综上所述，粗糙集理论在基于知识的各种信息系统中发挥了其独有的优势。 正因为如此，近几年来，粗糙集理论受到了广大数据挖掘研究者的重视，取得 了一些成功。目前，波兰、加拿大、日本和美国关于粗糙集的理论研究与应用 处于世界前列。近年来，我国的一些学者也开始了这方面的研究工作，并且国 家8 6 3 计划与自然科学基金对有关粗糙集理论的研究也进行了资助。但相对国 际上的研究成果，我国这方面还处于起步阶段，尤其是在应用研究上。 在今后几年内，粗糙集知识发现将有以下几个可能的研究方向： 1 基于粗糙集理论的粗糙逻辑以及不精确推理的研究。该项研究不仅对于 知识的挖掘和表示，而且对于人工智能中的不确定性推理将发挥重要作用。 2 快速、高效的约简算法。约简算法是粗糙集知识发现的基础，目前还没 有一种十分有效的约简算法。 3 粗糙集w e b 知识发现问题。随着i n t e m e t 的迅速扩展，w e b 页面的增加， 利用粗糙集进行w e b 知识发现将是今后最重要的课题之一。 硕士学位论文第一章绪论 4 与模糊集方法等其他方法的结合问题j 目前有很多知识发现方法，粗糙 集如何与其他方法结合，可能是提高知识发现效率的一种途径。 1 2 粗糙集理论与其它智能理论 各种智能理论取长补短，相互结合，可以实现不同的应用目的；粗糙集理 论同样可以与模糊集理论、神经网络、遗传算法、概念格和证据理论等其它智 能理论结合，实现更强大和更优良的功能。 1 粗糙集理论与模糊集理论 模糊集理论和粗糙集理论是处理不完整性和不确定性系统的两釉方法，都 是对经典集合理论的改进。模糊理论主要处理论域中对象之间的差异在中间过 渡中的不分明性。普通集合论中，一个对象对于一个集合，或者属于，或者不 属于。模糊集认为一个对象对于一个集合，总是以某种程度属于该集合。模糊 集合以一个取值在 0 ，1 】的函数描述这种隶属关系。模糊集的运算处理的是集 合中个体对于集合的隶属关系。模糊集方法需要一些先验附加知识，例如模糊 隶属函数、基本概率分布函数。粗糙集则是另外一种刻划不完整性和不确定性 的数学工具。它能从不精确、不一致、不完备的信息中发现知识，它几乎不需 要任何先验知识。模糊集和粗糙集可以通过模糊一粗糙集模型和粗糙模糊集 3 9 1 它们都是描述数据的不精确性，但一个从隶属度出发，一个从集合论出发。将 模糊集与粗糙集相融合，可以更加贴切地描述所研究的对象【4 “。表1 一l 就粗糙 集理论和模糊集理论的不同点给出了一个直观的比较。 表1 - 1 粗糙集理论和模糊集理论的比较 模糊集理论粗糙集理论 描述的对象属于同一类的不同对象不同类之间的对象 对象对于集合的隶属关 描述的关系 对象在集合内的不可分辨关系 系 描述内容 对象对于集合的隶属度集合在论域空间中的粗糙度 描述方法 隶属函数上、下近似集，正、负域，边界 先验知识 需要不需要 与经典集合的联系截集上近似，下近似 计算方法模糊集的运算 属性约简和属性值约简 硕士学位论文 第一章绪论 2 粗糙集理论与神经网络 粗糙集理论定义条件属性和决策属性间的依赖关系，即输入空间与输出空 间的映射关系是通过简单的决策表简化得到的，而且通过去掉冗余属性，可以 大大简化知识的表达空间维数，其决策表的简化又可以利用并行算法处理。 神经网络完成输入空间与输出空间的映射关系是通过网络结构不断学习、 调整、最后以网络的特定结构表达。由于神经网络无需现实函数表达而完成并 行处理，因此将神经网络与粗糙集算法结合是很有意义的。 粗糙集理论与神经网络融合主要体现在两个方面，一方面使用粗糙集方法 可以提供更精练的训练样本，提高神经网络的学习速度；另一方面可将两种理 论有机融合，如通过将经典神经元改造为粗糙神经元，拓展了经典神经网络模 型，在有些情况下可以更好地拟合数据的特征，提高网络的预测性能j 。 3 粗糙集理论与遗传算法 遗传算法是一种基于自然选择和基因遗传学原理的优化搜索方法。将其应 用于工程领域，就是为了将自然系统的重要机理运用到工程系统、计算机系统 或商业系统等人工系统的设计中。遗传算法在计算机上模拟生物的进化过程和 基因的操作，并不需要对象的特定知识，也不需要对象的搜索空间是连续可微 的，它具有全局寻优的能力1 4 ”。些用常规的优化算法有效解决的问题，采用 遗传算法寻优技术往往能得到更好的效果。粗糙集与遗传算法结合的应用，可 以将粗糙集知识约简已提取到的最简规则用遗传算法进行最大限度的基于研究 对象的优化，优化的结果往往会对真正最优规则的形成产生重要的影响【4 川。 利用遗传算法与粗糙集理论相结合解决问题时应首先考虑以下几个问题： 编码问题、适应度函数、遗传算子的选择、算法结束条件等。解决编码问题时， 对于利用粗集理论推导出的规则，每一个规则对应为遗传算法的一条染色体， 为此采用多参数编码方法。规则的适应度通过专家按规则编码的语义段进行评 判，并给出可信度值，然后将规则的各个语义段的可信度值相加，便得到一个 评价这条规则的分数。利用遗传算法与粗糙集理论相结合的方法的最终目标就 是遗传算法能够在随机产生的初始规则集上不断优化，最后将由粗糙集理论约 简后的规则全部学习到并完成遗传优化1 4 ”。 4 粗糙集理论与概念格 概念格是根据二元关系提出的一种概念层次结构，是数据分析和规则提取 的一种有效工具郴j 。从数据集中生成概念格的过程实际上是一种概念聚类的过 程，它的每个节点被称为一个概念，概念的外延表示为属于这个概念的所有对 象的集合，而内涵则表示为所有这些对象所共有的属性的集合。概念格在本质 上描述了对象和属性之间的联系，表明了概念之间的泛化和例化关系，而它的 硕士学位论文第一章绪论 h a s s e 图则实现了对数据的可视化。 概念格及其h a s s e 图体现了概念内涵和外延的统一，反映了对象和特征间 的联系以及概念问的泛化与例化关系。概念格的每个概念就是具有最大共同属 性的对象的集合，在形式背景中，外延即是由内涵所确定的等价类。因此，粗 糙集的一些性质包括等价类，上、下近似等都可以通过概念格来描述。同时， 由概念格的特殊结构更容易导出函数依赖。在这个基础上，可以使用概念格进 行直观的条件属性的约简。 5 粗糙集理论与证据理论 粗糙集理论与d s 证据理论在处理不确定性的问题方面其产生和研究的方 法是不同的，但却有某种相容性，粗糙集理论是为开发规则的机器自动生成而 提出的，而d s 理论主要用于证据推理，这两种理论的动机是不同的。粗糙集 使用集合的上、下逼近而证据理论使用信任函数作为主要工具。粗糙集对给定 数据的计算是客观的，无须知道关于数据的任何先验知识( 如概率分布等) ，而 d s 证据理论是用一对信任函数和似然函数在给定证据下对假设进行估计和评 价。粗糙集理论中的下近似和上近似的概率恰好分别是信任函数和似然函数， 然而生成信任函数和似然函数的基本概率分配函数( 即m a s s 函数) 方法是不同 的，前者来自于系统中数据本身，比较客观，而后者往往来自于专家的经验， 带有很强的主观性【4 9 1 。 6 粗糙集理论与其它理论 目前，与粗糙集理论相关的理论还有专家系统、b a y e s 理论、概率统计理 论、统一集论等。 专家系统主要由知识库和推理机两部分组成。粗糙集理论可以不需要先验 信息，从大量数据中提取规则的特性，为构造和简化专家系统知识库提供了较 好的途径。文 5 0 ， 5 1 都是将粗糙集理论引入故障诊断专家系统，利用粗糙集 理论的约简算法消除知识库的冗余，从而实现了对知识库结构和性能的有效维 护及完善。 粗糙集理论和b a y e s 理论都具有基于规则推理的特点。粗糙集理论排斥先 验知识，推理得到的规则集易受数据噪声的影响。基于b a y e s 概率理论的因果 连接模型，在处理不确定性上比粗糙集理论更简洁和方便。但是，粗糙集理论 约简过程包含了对冗余信息的剔除，因果连接模型并无这个过程。因此，可以 把这两者结合起来用于推理过程。 此外，粗糙集与随机集，粗糙集与图论结合等都为解决不完备、不相容数 据上的数据挖掘问题提供了更好的理论基础和拓展空问。其他根据数据集的特 点与需求，发展粗糙集以适应需要，也有许多工作要做，如把不分明关系扩展 硕士学位论文 第一章绪论 为相似关系等，都可将粗糙集理论的应用拓展到更广阔的领域52 1 。 1 3 论文研究的内容和结构 1 3 1 论文研究的主要内容 粗糙集理论是一种用于数据分析和分类的数学工具。其主要任务就是从这 些数据中发现潜在的规律，建立能够取代该数据集的知识库( 即i f t h e n 规则 集) ，从而利用该知识库对新对象进行分析，做出决策。但是，单一的知识库往 往丢失了过多的信息，而无法对新对象做出正确的判断。本文主要对基于粗糙 集理论的多知识库的信息融合进行了研究，具体做了以下一些工作： 1 用粗糙集理论的方法根据一个数据库建立单个知识库，往往很难保证其 完备性。这样的知识库在分类新对象时有可能出错。k o n o n e n k o 等提出了多知 识库( 或冗余知识) 的概念，其思想是根据一个数据库建立多个知识库，并适 当组合各个知识库的决策结果。论文通过研究粗糙集产生多知识库的基本原理， 给出多知识库的形式化定义，完善了符号体系。并在此基础上给出一种基于粗 糙集产生多知识库的新算法，并与其它算法相比较，说明该算法的结果具有更 好的完备性。 2 在用多知识库来对新对象进行分类识别的过程中，很关键的问题是如何 对多个决策结果进行融合得到最终的决策。目前，对于多个决策结果仅仅是通 过简单的组合，造成分类识别的准确性和可信度较低。论文根据多源信息融合 原理，对多个决策结果进行融合，研究了一种基于证据理论的融合算法，该算 法可以提高整个分类识别的准确性和可信度。 3 属性值的约简是粗糙集理论的核心内容之一。它的目的就是在保持规则 集的分类能力的条件下，删除多余属性值，进一步简化规则集。从而，得到最 小的知识库。本文针对粗糙集理论中值约简这个重要问题进行了研究，给出了 一种利用决策规则质量的属性值约简算法。该算法比现有的值约简算法更简化， 并用实例说明了其有效性。 1 3 2 论文的结构 本文共分为六章，其结构如下： 第一章：绪论。主要介绍了粗糙集理论的提出背景、特点、研究现状与前 景和粗糙集理论与其它智能理论的关系，以及论文研究的内容和结构。 第二章：粗糙集理论的基本知识。介绍了粗糙集理论中的基本概念，包括： 硕士学位论文第一章绪论 知识与不可分辨关系、上、下近似集和粗糙集、信息系统和决策表、属性约简 和核。 第三章：基于粗糙集产生多知识库的方法。主要介绍了基于粗糙集产生多 知识库的基本原理，给出了其形式化定义，给出了一种基于粗糙集产生多知识 库的新算法，并与其它算法相比较，说明该算法的结果有更好的完备性。 第四章：多知识库的信息融合。在用多知识库来对新对象进行分类识别的 过程中，很关键的问题是如何对多个决策结果进行融合来提高整个分类识别的 准确性和可信度。本章研究了一种多个决策结果的融合方法，并用实验证明其 有效性。 第五章：针对粗糙集理论中值约简这个重要问题进行了研究，绘出了一种 利用决策规则质量的属性值约简算法。该算法比现有的值约简算法更简化，并 用实例说明了其有效性。 第六章：总结与展望。对论文工作进行了总结，并指出有待进一步研究和 完善的问题。 硕士学位论文第二章粗糙集理论的基本知识 第二章粗糙集理论的基本知识 粗糙集理论为我们提供了一种描述不确定事物的数学语言，使我们可以采 用不同的精度来分析数据。本章介绍了粗糙集理论的基本概念【2 6 】，作为后续章 节的基础。 2 1 知识与不可分辨关系 “知识”这个概念在不同的范畴内有多种不同的含义。在粗糙集理论中， “知识”被认为是一种将现实或抽象的对象进行分类的能力【5 ”。而对象是指任 何我们可以想到的东西，例如实际物体、状态、抽象概念、过程、时刻等。假 定我们具有关于论域的某种知识，并使用属性及其值来描述论域中的对象。例 如：空间物体集合u 具有“大小”、“形状”这两种属性，“大小”的属性值取 为大、中等、小“形状”的属性值取为方、圆、三角形。从离散数学的观点看， “大小”、“形状”构成了u 上的族等效关系。u 中的物体，按照“大小”这 一等效关系，可以划分为“大的物体”、“中等的物体”、“小的物体”等集合： 按照“形状”这一等效关系，可以划分为“方的物体”、“圆的物体”、“三角形 的物体”等集合；按照“大小+ 形状”这一合成等效关系，又可以划分为“大的 圆物体”、“中等的方物体”、“小的三角形物体”等集合。如果两个物体同 属于“大的圆物体”这集合，它们之间是不可分辨关系，因为描述它们的属 性都是“大”和“圆”。不可分辨关系的概念是粗糙集理论的基石，它揭示出论 域知识的颗粒状结构。 粗糙集理论延拓了经典的集合论，把用于分类的知识嵌入集合内，作为集 合组成的一部分。一个对象是否属于某个集合需根据现有的知识来判断，可分 为三种情况：( 1 ) 对象肯定属于这个集合：( 2 ) 对象肯定不属于这个集合；( 3 ) 对象可能属于也可能不属于这个集合。集合的划分密切依赖于我们所掌握的关 于论域的知识，是相对的而不是绝对的。 假定我们感兴趣的对象的有限集合u ，称为论域。u 的任一子集，可称为 一个u 中的概念或范畴。规范化起见，认为空集也是一个概念。u 中的任何概 念簇称为关于 厂的抽象知识，简称知识，它代表了对u 中个体的分类。论域u 上的一个划分s 是这样定义的：s = ( ，局，舶) ：这里的咒- u ，岸西， s 的子集无交集，即n 置西，且它们包含了论域u 中所有的元素，即z = u ； 其中游，f ，户1 ，2 ，n 。u 上的一族划分被称为关于u 的一个知识库。 硕士学位论文第二章粗糙集理论的基本知识 定义2 1 设r 是u 上的一簇等价关系，u r 表示r 的所有等价类( 或者u 上的分类) 构成的集合，b 1 昱表示包含元素x u 的r 的等价类，则个知识库 可以定义为j p ( u ，r ) 。若p c r ，且p 庐，则p 中所有等价关系的交集也是 一个等价关系，称为p 上的不可分辨关系，记为f 材( 尸) ，且有m i n dc p ) = n 【巩。 这样，( 肌n d ( p ) 表示与等价关系族p 相关的知识，称为k 中关于u 的尸 的基本知识。为简便起见，我们将u i n d ( p ) 记为p ，i n d ( p ) 的等价类称 知识p 的基本概念或基本范畴。特别地，如果q r ，则称q 定义不可分辨的 等价关系类就是p 的初等知识，且i n d ( q ) 的等价类称为知识r 的q 的初等 概念或q 初等范畴。因此，根据属性不可分辨关系的等价类形成了知识的基本 模块。根据我们的知识i n d ( 尸) ，无法识别等价类中的对象。也就是说，等价 类构成了知识的粒度。而这种知识的粒度正是粗糙集理论中产生不确定性的原 因。 例2 1 给定一玩具积木的集合【，- ( x l ，x 2 ，x 1 0 ) ，积木的集合u 可以 按颜色r 1 ( x l ，x 3 ，x 7 ，x 9 为红色，x 2 ，x 4 ，x 1 0 为蓝色，x 5 ，x 6 ，x 8 为黄色) 、 形状r 2 ( x l ，x 5 ，x 1 0 为圆形，也，拍，妇为方形，x 3 ，“，x 7 ，x 8 为三角形) 、 体积r 3 ( x 2 ，x 7 ，x 8 ，x 9 ，x 1 0 较大，x 1 ，x 3 ，娟，z 5 ，x 6 较小) 进行分类， 根据这三个等价关系r l ，r 2 ，r 3 ，可得到下列三个等价类： u 偎1 = ( x l ，x 3 ，x 7 ，x 9 ) ，( x 2 ，x 4 ，x 1 0 ) ，( x 5 ，x 6 ，z 8 ) ) ， u r 2 = ( x l ，x 5 ，x 1 0 ) ， x 2 ，x 6 ，x 9 ) ， x 3 ，x 4 ，x 7 ，x 8 ) ) ， u r 3 = t x 2 ，x 7 ，x 8 ，x 9 ，x 1 0 ) ， x l ，x 3 ，x 4 ，x 5 ，x 6 ) ) 。 这些等价类是由知识库j o ( u ， r 1 ，r 2 ，r 3 ) ) 中的初等范畴构成的。考 虑以下由初等范畴的交集构成的基本范畴：( x l ，x 3 ，x 7 ，x 9 ) n ( x 1 ，x 3 ，x 4 ， x 5 ，x 6 ) = x l ，z 3 ) ， x 5 ，x 6 ，x 8 ) n ( x 2 ，x 7 ，x 8 ，x 9 ，x 1 0 ) = x 8 ) 。它 门 分别为基于( r 1 ，r 3 ) 的基本范畴，即：较小红色，较大蓝色。又例如集合( x l ， x 3 ，x 7 ，石9 ) n x 2 ，x 6 ，x 9 ) n x 2 ，x 7 ，x 8 ，x 9 ，x 1 0 ) = x 9 ) 为基于( r 1 ， r 2 ，尺3 ) 的初等范畴得到的基本范畴，即：红色大方形。由此看出，我们可以 用不同的标准来对论域进行分类，得到不同的概念和抽象，有的概念是我们需 要的，有的概念是没有价值的，知识获取就是要探寻有用的概念，并得到概念 之间的关系。 下面讨论两个知识库之间的关系。 令k i = ( u ，p ) 和k 2 = ( u ，q ) 为两个知识库。若i n d ( p ) = i n d ( q ) ， 即u p = u q ，则称朋和 = 2 ( 尸和q ) 是等价的，记作k 1 2 j ( 2 ( p 2 q ) 。因 此，当k 1 和k 2 有同样的基本范畴集时，知识库k l 和尥中的知识都能使我 们确切地表达关于论域的完全相同的事实。