（管理科学与工程专业论文）关于信息系统中知识约简及相关问题的研究.pdf

山东师范大学硕士学位论文 摘要 粗糙集理论r s ( r o u g hs e t s ) 是由波兰华沙理工大学的z p a w l a k 教授等 一批科学家提出的研究不完整、不精确或者是模糊知识的一种组织和分析方法 自提出以来，已经在模式识别、数据挖掘、决策分析等很多方面得到广泛应用。 知识约简是粗糙集理论的精髓之一利用粗糙集理论及其约简算法可以进行知 识获取、机器学习等然而，知识约简离不开一系列的算法作支持，包括判断 属性的重要性、求核和属性约简等因此，约简算法的设计和实现就成为知识 约简研究的重要内容之一 除此之外，由于各种各样的原因，数据表中数据错误或数据缺失的现象常 常出现，这就使得表中某些对象的某些实际值未知，导致了待处理数据有某种 程度的不完整。如何对不完备的信息系统进行属性约简，也是研究的一个新方 向 本文主要针对粗糙集在完备信息系统及不完备信息系统中的理论及知识约 简做了一些研究。所作的主要工作有： 1 、研究了粗糙集理论的基本知识，介绍了近似的相关定义以及性质，并给 出了完备信息系统下的知识约简的相关定义。 2 、对完备信息系统下的粗糙集理论中当前已提出的属性约简算法进行了 简单分析，在可辨矩阵的基础上提出了差别矩阵的概念，研究了差别矩阵的性 质并进行了证明，由此给出了一个基于差别矩阵的知识约简算法。 3 、从经典粗糙集模型中的等价关系入手，对不完备信息系统的粗集模型进 行了扩充，总结了五种扩充的粗集模型这几种扩充模型是原来扩充模型的推 广和改进，既保留了原来模型的优点又丢弃了原来模型的缺陷。 4 、将完备信息系统下基于等价关系的粗糙集理论中的各种定义及性质推 广到基于相容关系而建立的不完备信息系统中。从而进一步完善了其理论体系 同时将可辨矩阵及差别矩阵的相关定义推广到不完备信息系统中，并给出了一 个基于差别矩阵的知识约简算法，证明了约简判定定理 山东师范大学硕士学位论文 关键词：粗糙集；完备信息系统；不完备信息系统；知识约简：近似； 可辨矩阵 分类号：t p l 8 山东师范大学硕士学位论文 s t u d yo f k n o w l e d g er e d u c t i o n a n dr e l a t e dp r o b l e m si n i n f o r m a t i o ns y s t e m r o u g hs e tt h c o r yi si n t r o d 叫b yp r o f e s s o rz p a w l a ki nw a r s a wu n i v e r s i t yo f t e e h n o l o g y , p o l a n d , w h i c hi sar e s e a r c hm e t h o do fo r g a n i z a t i o na n da n a l y z eo f i n c o m p l e t e ，i n a c c u r a t eo rv a g u ek n o w l e d g e s i n c ei th a sb e e ni n t r o d u e 翔i , r o u g hs e t s h a v eb e e nu s e dw i d e l yi nm a n yf i e l d s s u c h 瑟m o d e lr e c o g n i t i o n , d a t am i n i n ga n d d e c i s i o na n a l y z e k n o w l e d g er e d u c t i o ni sak e r n e lp r o b l ei nt h er e s e a r c ho f r o u g hs e t t h e o r y t h er e d u c t i o na l g o d t l m ab a s e do nt h er o u g hs e tt h e o r yc a nb eu s e di nt h e a r e a so fk n o w l e d g ea c q u i s i t i o n , m a c h i n el c a r a i n g _ ，a n ds oo n 肋懵嘴：k n o w l e d g e r e d u c t i o ni sd c p c - n d c n to nas e r i e so f s u p p o r t i n ga l g o r i t h m ss u c ha st h ec a l c u l a t i o no f a t t r i b u t es i g n i f i c a n c e 、缸d i n gc o r e 、a t t r i b u t er e d u c t i o n s o ，d c s i g ha ni m p l e m e n t a t i o n o f r e a u c t i o na l g o r i t h mi so d co f i m p o r t a n tc o n t c n t so f r o u g hs e tr e s e a r c h b e s i d e s , t h e r ea 旭m i s t a k e so rm i s s i n gd a t ai nt h ed a t as e td u et o c ar i o u s r e a s o n s ，s o ，t h a th o w t or e d u c ea t t r i b u t e so l li n c o m p l e t ei n f o r m a t i o ns y s t e mi san e w s t u d ya s p e c t i nt h i st h e s i s ， w ec o n d u c ts o m er e s e a r c ho l lr o u g hs e tm o d e l si nb o t hc o m p l e t e a n di n c o m p l e t ei n f o r m a t i o ns y s t e m m ym a i nr e s u l t sa 地a sf o l l o w s ： 1 、w es t u d yt h eb a s i ck n o w l e d g eo fr o u g hs e t , i n t r o d u c et h ei n t e r r e l a m d d e f i n i t i o n sa n dp r o p e r t i s eo f t h ea p p r o x i m a t i o nr e l a t i o n 2 、u n d e rt h ei n c o m p l e c ei n f o r m a t i o ns y s t e m , b a s e do l lr e s e a r c h i n ga n d a n a l y z i n gt h er e d u c t i o na l g o r i t h m si nr o u g hs e t , w eb r i n gu pan e wd e f i n i t i o no f d i f f c r e a t i a b i l i t ym a t r i xb a s e do nt h ed i s c e r n i b i l i t ym a n b , , t h e ng i v e sa na l g o r i t h m 3 、s t a r t e dw i t ht h ee q u i v a l e n c er e l a t i o n so fc l a s s i c a lr o u g hs e tm o d e l w ep u t f o r w a r df i v ek i n d so fe x t e n s i o n s u g hs e tm o d e l n o to n l yd o e st h ee x t e n s i o n r e s f r v et h ea d v a n t a g eo ft h ep r e s e n tm o d e l , b u ta l s ot h e s em o d e l sd i s c a r dt h e d i s a d v a n t a g eo f t h el e s e n tm o d e l m 山东师范大学硕士学位论文 4 、t og oas t e pf u r t h e r , w es p r e a dt h ed e f i n i t i o n sa n dp r o p e r t i e so ft h e c o m p l e t ei n f o r m a t i o ns y s t e mw i t ht h ee q u i v a l e n c er e l a t i o n s t ot h ei n c o m p l e t e i n f o r m a t i o ns y s t e mw i t ht h et o l e r a n c er e l a t i o n s i nt h em e a n w h i l e ，w ea l s os p r e a d t h ed i f f e r e n t i a b i l i t ym a t r i xa n dd i s c e r n i b i l i t ym a t r i xt oi t a ti a s t , w eg i v ear e d u c t i o n a l g o r i t h mb a s e do nt h e j u d g e m e n t st h e o r e mo f a t t r i b u t e sr e d u c t i o n k e yw o r d s ：r o u g hs e t ；c o m p l e t ei n f o r m a t i o ns y s t e m ；i n c o m p l e t ei n f o r m a t i o ns y s t e m ； k n o w l e d g er e d u c t i o n ；a p p r o x i m a t i o n ；d i s c e r n i b i l i t ym a t r i x c l a s s i f i c a t i o n ：t p l 8 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得二一( 注：如没有其他需要特别声明 的，本栏可空) 或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 蟊君 导师签字文静 学位论文版权使用授权书 本学位论文作者完全了解生! 撞有关保留、使用学位论文的规定，有权保留并向国家 有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权堂撞可以 将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等 复制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：感瑶霄导师孬：退长扛 导师签字：一葛；l 签字日期：2 0 07 年r 月玎1 3 签字日期：2 0 0 7 j 月2 箩1 5 t 山东师范大学硕士学位论文 1 1 绪论 第一章引言 当今，社会已经进入了网络信息时代，计算机与网络信息技术的飞速发展 使得各个领域的数据和信息急剧增加( 信息爆炸) ，并且由于人类的参与使数据 与信息系统中的不确定性更加显著( 复杂系统) 如何从大量的、杂乱无章的、 强干扰的数据( 海量数据) 中挖掘潜在的、有利用价值的信息( 有用信息) ，这 给人类的智能信息处理能力提出了前所未有的挑战 信息系统这个概念作为智能信息处理领域的一个具有形式化定义和明确语 义的专业术语，出现于波兰学者z p a w l a k 于1 9 8 2 年提出的粗糙集理论中数 据库模型、数据的决策与分析、模式识别、机器学习等领域的许多问题的描述 框架可以归结为信息系统信息系统中的不确定性问题、知识获取问题一直是 信息科学领域关注的热点。 粗糙集理论是波兰学者z p a w l a k 于1 9 8 2 年提出的一种数据分析理论最初关 于粗糙集理论的研究主要集中在波兰，因此当时并没有引起国际计算机界和数学 界的重视。直到1 9 9 0 年前后，由于其在数据的决策与分析、模式识别、机器学习 与知识发现等方面的成功应用，才引起了世界范围内各国学者的广泛关注1 9 9 1 年z p a w l a k 的专著 粗糙集一关于数据推理的理论 ( r o u g h s e t s t h e o r e t i c a l a s p e c t so f r e a s o n i n ga b o u t d a t a ) 1 1 】的闯世，标志着粗糙集理论及 其应用的研究进入了活跃时期1 9 9 5 年a c mc o m m u n i c a t i o n 将粗糙集列为新浮现 的计算机科学的研究课题。目前，粗糙集理论已经成为信息科学最为活跃的研究 领域之一同时，该理论还在医学、化学、材料学、地理学、管理科学和金融等 学科得到了成功的应用掰 知识约简是粗糙集理论处理信息系统的重要手段，它在保持信息系统分类能 力不变的前提下，导出问题的决策或分类规则。粗糙集理论中的知识约简研究大 部分都集中在关于完备信息系统的绝对约简以及完备决策表的相对约简上；对于 不完备信息系统、不完备决策表的知识约简，人们也进行了研究，但还不够深入 尽管不完备决策表缺少信息，但仍然蕴涵一些有用的知识，这些知识对于不完备 山东师范大学硕士学位论文 信息下的决策，是很有意义的。 1 2 粗糙集的研究与发展状况 1 2 1 粗糙集的应用和研究现状 粗糙集理论是一种处理模糊和不精确知识的数学工具，对于处理复杂系统 不失为一种有效的方法，因为它和概率方法、模糊集方法和证据理论方法等其 他处理不确定问题理论的最显著区别是它无需提供问题所需的数据集合之外的 任何先验信息粗糙集能有效地分析不精确、不一致、不完整等各种不完备的 信息，还可以对数据进行分析和推理，从中发现隐含的知识，揭示潜在的规律。 由于粗糙集理论可以支持知识发现的多个步骤，如数据预处理、数据缩减、 规则生成等，因此基于粗糙集理论的知识发现系统被认为具有独特的优势。 粗糙集理论是建立在分类机制的基础上，它将分类理解为在特定空间上的 等价关系门研究粗糙控制问题，这是一个很吸引人的研究方向。国外目前在粗 糙集领域的研究主要集中在约简的优化算法、粗糙集理论和模糊理论，粗糙集 理论同神经网络理论等其他人工智能技术的结合、粗糙逻辑等课题上。论文对 于约简算法的研究正是粗糙集领域中个非常重要的课题。我国在粗糙集领域 的研究起步较晚，但我国在这个领域的发展速度很快，目前中科院、清华大学 等研究所和高校已加入到这个领域中，并取得了一定的成果 目前，租糙集理论的主要研究方向如下： ( 1 ) 属性约简和规则获取。属性约简是粗糙集用于数据分析的重要方面 根据区分矩阵和区分函数及布尔运算可以求出属性集的所有最小约简，但是由 于求所有最小约简是n p 问题，因此一般只适合小数据集。实际应用中大都采 用启发式算法目前常见的启发式算法是属性重要度方法：即根据属性重要度 来对属性进行选择和有效约简。另外还可以利用遗传算法来求最小约简等。通 过属性约简的结果来获得最小决策规则。 ( 2 ) 经典粗糙集模型的扩展粗糙集理论用于数据挖掘时会碰到噪音数据、 数据缺失、大数据量的一系列经典模型处理不理想的情况，于是出现了扩展的 模型。包括可变精度模型、相容模型和相似模型等。可变精度模型：有一定容 2 山东师范大学硕士学位论文 错能力，在一定情况下退化为经典模型。而相容模型和相似模型：可以处理数 据库中的缺失值 ( 3 ) 粗糙集和其它多种方法的融合。包括和模糊集的融合、和神经网路的 融合、和概率统计方法的融合、和支持向量机( s v m , s u p p o r tv e c t o rm a c h i n e ) 的融合等等。 1 2 2 粗糙集理论的优点 作为一种研究不精确、不完整信息分类问题的数学工具，粗糙集理论有许 多优点1 3 】： 一 ( 1 ) 粗糙集理论在数学上非常严密，有一整套处理数据分类问题的数学方 法，特别当数据是不确定，不完整和不精确的时候； ( 2 ) 粗糙集理论将知识定义为不可分辨关系的簇，因此，知识有比较清晰 的数学含义，很方便用数学方法来分析处理； ( 3 ) 基于租糙集的计算方法非常适合并行处理，粗集计算机的研制工作已 在进行之中； ( 4 ) 粗糙集理论的实用性非常强，该理论是为开发自动规则生成系统而提 出的，因而它的研究完全是应用驱动的； ( 5 ) 粗糙集理论无需提供除问题所需处理的数据集合之外的任何先验信 息，这是和模糊理论与证据理论最主要的区别： ( 6 ) 发现数据中隐含的模式和关系，对数据进行约简，评价数据的重要性， 从数据中产生规则，结果易于理解。 1 3 知识约简的研究与发展情况 知识约简是指在不影响知识表达能力的条件下，通过消除冗余知识，从而 获得知识库的简洁表达的方法。在粗糙集理论中，就是针对信息系统，在保持 信息系统分类或决策能力不变的前提下，通过消除冗余属性和冗余属性值，最 终得到信息系统的分类或决策规则的方法。知识约简是粗糙集理论的精髓，是 从信息系统中获取知识的方法和途径，也是粗糙集理论的重要研究内容和热点 3 山东师范大学硕士学位论文 之一。 在粗糙集理论中，知识约简分为属性约简和属性值约简，由于属性值约简 相对较为简单，一般很少研究，相关内容可以参见文献【4 】。属性约简则困难得 多，甚至到现在还没有完全解决，因此仍然是粗糙集理论的研究重点。基于此， 有时又将知识约简理解为属性约简，本文将沿用这种说法。 1 完备信息系统下知识约简的研究现状 知识约简是粗糙集理论的核心内容之一。所谓知识约筒，就是在保持知识 的分类能力不变的条件下，删除其中不相关或不重要的知识许多学者从不同 角度提出了获取信息系统及决策表的属性约简算法。这些算法可以分为两类嘲： 一类是基于信息嫡即s h a n n o n 嫡的启发式算法。但启发式算法往往不能得到系 统的所有约简另一类是基于可辨矩阵和可辨函数构造的。由于在可辨矩阵中 会出现大量的重复元素，因而降低了属性约简算法的效率 2 不完备信息系统的研究现状 目前国内外涉及不完备信息系统下粗糙集理论研究的人还很少，主要有以 下几种模型： m k r y s k i e w i c z 提出的不完备信息系统的基于相容关系的粗糙集模型及其 知识约简方法。j $ t e f a n o w s k i 提出的基于非对称相似关系的粗糙集扩展模型 s t c f a n o w s k i 提出的基于量化相容关系的粗糙集模型。王国胤在对以上三个模型 分析的基础上提出了基于限制相容关系的粗糙集扩展模型张宏宇等人提出了 不完备信息系统下的变精度租糙集模型 知识约简是粗糙集理论的重要研究内容，关于知识约简的论文及算法层出 不穷。到目前为止，能找到所有约简的算法的时间复杂度都很高，两所有启发 式算法又不能保证算法的完备性。可以说，知识约简还是个远未完全解决的 开放性问题。 1 4 本文结构 本文章节及内容安排如下： 第一章引言 概述了粗糙集的应用与发展现状，粗糙集理论的优点，并介绍了知识约简 4 山东师范大学硕士学位论文 理论的研究现状 第二章粗糙集理论 介绍了粗糙集理论与知识约简的基本概念及相关性质 第三章基于完备信息系统的知识约简算法研究 整理并介绍了目前基于完备信息系统的各类知识约简算法。 第四章基于差别矩阵的知识约简算法 在可辨矩阵的基础上提出了差别矩阵的概念，并提出一个基于差别矩阵的 知识约简算法，对其进行了简单分析 第五章不完备信息系统下的粗糙集理论 简单介绍了空值的定义及常见的处理方法，并分析了当前国际与国内已提 出的不完备信息系统中拓展的粗糙集模型，包括基于相容关系、相似关系以及 限制相容关系的不同种类的粗糙集模型。 第六章基于相容关系的不完备信息系统理论及知识约简算法 详细介绍并充实了基于相容关系的不完备信息系统理论，讨论在该模型下 的粗糙集性质，并从一个新的角度给出一个相关的知识约简算法。 第七章总结与展望 本文内容的总结及未来工作的思考。 5 山东师范大学硕士学位论文 第二章粗糙集理论 2 1 引言 粗糙集理论是建立在分类机制的基础之上的，它将分类理解为在特定空间 上的等价关系，而等价关系构成了对该空间的划分粗糙集理论将知识理解为 对数据划分的结果，每一被划分的集合称为概念。它的主要思想是利用已知的 知识库，将不精确或不确定的知识用已知的知识库中的知识来近似刻画。该理 论与其他处理不确定和不精确问题理论的最显著的区别在于它无需提供问题所 需处理的数据集合之外的任何先验信息，所以对问题的不确定性的描述或处理 较为客观由于该理论未包含处理不精确或不确定原始数据的机制，所以这个 理论与概率论、模糊数学和证据理论等其他处理不精确或不确定问题的理论又 有很强的互补性。 总的来看，完备信息系统情形下的粗糙集理论基础的研究日臻完善，已基 本构成了较为完整的理论基础，并在各个方面的应用也取得了显著成效。本章 就将介绍一下本文所涉及的粗糙集理论的相关知识 2 2 粗糙集理论的基本概念 2 2 1 知识与知识库 知识是人类通过实践认识到的客观世界的规律性的东西，是人类实践经验 的总结和提炼，具有抽象和普遍的特性。知识是信息经过加工处理、解释、挑 选和改造而形成的。知识是命题、规则等的集合。一般分为说明性知识、过程 性知识和控制性知识 4 1 。 在人工智能领域，知识被认为是基于对研究对象分类的能力通常，我们 在对现实问题进行处理的时候，会将我们讨论的现实个体( 或称为元素、对象、 样本) 局限在某一个特定的区域范围内，这个区域范围内的所有个体就组成了 闯题的论域u 定义2 1 1 1 l ：设u 囝是我们感兴趣的对象组成的有限集合，称为论域。 以分类为基础，可以将分类理解为等价关系，而这些等价关系对论域【，进 6 山东师范大学硕士学位论文 行划分对于论域中由等价关系划分出的任意子集z ，都可以称之为c ，中的一 个概念论域u 中的任意概念簇称为关于( ，的抽象知识，简称为知识，它代表 了对u 的个体的分类。这样，知识可以这么被定义 定义2 2 1 1 l ：给定一组数据( 集合) u 和等价关系置，在等价关系r 下对数 据集合u 的划分，称为知识，记为u r 定义2 3 u ：一个划分尹定义为： 9 = ，恐， ： 芬c ( ，五簪。，x , n x j = 。，对于f 工i , j = l ，2 ，弼皂五= u u 上的一族划分称为关于u 的一个知识库( k n o w l e d g eb a s e ) 。 定义2 4 1 1 i ：若p 量r ，1 1 p o ，则f - 妒( p 中所有等价关系的交集) 也是 一个等价关系，称为p 上的不可区分( i n d i s e e r n i b i a t y ) 关系，记为加d ( p ) ，且 有【x 】w ( ，) 2 0 【硝- 这样，u i n d ( e ) ( 即等价关系玩d ( p ) 的所有等价类) 表 示与等价关系族尸相关的知识，称为足中关于( ，的，基本知识( p 基本集) 。 为简单起见，我们用u p 代替u l n a ( p ) ，i d c p ) 的等价类称为知识p 的基本t 概念或基本范畴。特别的，如果q r ，则称q 为置中关于u 的q 初级知识，q 的等价类为知识则 勺q 初级概念或q 初级范畴。 事实上，基本范畴是拥有知识p 的论域的基本特性。换句话说，它们是 知识的基本模块。 定义2 5 1 1 l ：当kf f i ( u ，r ) 为一个知识库，涮( 足) 定义为中所有等价关系的 族，记作俐( 的f f i i n a ( e ) l o p r ) 。 定义2 6 1 1 1 ：令。rf f i ( u ，刃和足；，q ) 为两个知识库，靴n d ( p ) f f ii n d c q ) ， 即u i p f f i u q ，则称置和k ( p 和q ) 是等价的，记作k = k 妒= q ) 因此， 当k 和x 有同样的基本范畴集时，知识库x 和x 中的知识都能使我们确切地 表达关于论域的完全相同的事实。 定义2 7 1 1 1z 对于足= ，p ) 和k f f i ( u ，9 两个知识库，当删( 尸) c 蒯( q ) 时，我们称知识p ( 知识库k ) 比知识q ( 知识库k ) 更精细，或者说q 比p 7 山东师范大学硕士学位论文 更粗糙。当p 比q 更精细时，我们也称p 为q 的特化，q 为p 的推广。这意味 着，推广是将某些范畴组合在一起，而特化则是将范畴分割成更小的单元 2 2 2 近似与粗糙集 定义2 8 t l l ：令z u ，r 为u 上的一个等价关系。当z 能表达成某些五基 本范畴的并时，称z 是r 可定义的；否则称工为r 不可定义的。 r 可定义集是论域的子集，它可在知识库k 中精确地定义，而r 不可定义 集不能在这个知识库中定义。盂可定义集也称为r 精确集，而r 不可定义集也 称为r 非精确集或粗糙集( r o u g h s e t ) 定义2 9 1 1 1 ；当存在等价关系r m a ( k ) 且z 为r 精确集时，集合并u 称 为芷中的精确集；当对于任何震砌( 幻，z 都为五粗糙集，则x 称为置中的 粗糙集。 对于粗糙集可以近似地定义，我们使用两个精确集，即租糙集的上近似 ( u p p e ra p p r o x i m a t i o n ) 和下近似( 1 0 w c za p p r o x i m a t i o n ) 来描述。 定义2 1 0 f 1 1 ：给定知识库k = ( u ，r ) ，对于每个子集xc _ 【，和一个等价关系 r f ，d ( 的，定义两个子集： _ - , z , x - - - u y e u r i y z ， 麟= u 】，6 u r l y n x g ) 分别称它们为的下近似集和上近似集 下近似、上近似也可用下面的等式表达： 丛= x u r z ) ， r x ； x e u l x r f l x o 集合丑矗= 腰一些称为x 的五边界域：e o s , ( x ) = 丛称为x 的胄正域； n e e , ( x ) = u 一融称为x 的r 负域。显然：p , x = p o s r ( x ) u b n ( x ) 丛或p o s 。( x ) 是由那些根据知识r 判断肯定属于z 的u 中元素组成的集 合；瓦r 是那些根据知识r 判断可能属于z 的矿中元素组成的集合；b z v 月( , t 3 是 那些根据知识五既不能判断肯定属于x 又不能判断肯定属于一x ( 即u z ) 窖 山东师范大学硕士学位论文 的u 中元素组成的集合； c z a r ( x ) 是那些根据知识震判断肯定不属于z 的u 中元素组成的集合 下面的性质是显而易见的。 定理2 1 1 1 1 ( 1 ) x 为r 可定义集当且仅当r x ；劢 ( 2 ) x 为r 粗糙集当且仅当r x 劢 我们也可将鱼描述为x 中的最大可定义集，将瓦r 描述为含有x 的最小 可定义集。 从近似的定义，我们可以得到r 下近似集和上近似集的下列性质。 定理2 2 1 1 1 ： 【1 ) 垦) ( 三x 欺 ( 2 ) 胗= 肋= a ，= r u = u ( 3 ) r ( x u 】，) = 肛u r y ( 4 ) 星( z n y ) = n 重7 ( 5 ) x 】，j 丛e ( 6 ) x 二y j r x r y ( 7 ) 豇x u d 2 丛u 鹫 ( 8 ) r ( x n 】，) 足z u 心 ( 9 ) 豇o d = 一j t r ( 1 0 ) r ( d = - 丛 ( 1 1 ) r r x ：i 肘：r x ( 1 2 ) 尼膦= 星时= 肘 定理2 3 1 1 i ： ( 1 ) 礓z 蕴涵x x 蕴涵磊x ； ( 2 ) z 】，蕴涵( 逛蕴涵增且磊x 蕴涵圆) ； ( 3 ) x 苫( x u d 当且仅当x 孩或x 吾； ( 4 ) x e ( x n d 当且仅当x 笪且硝； ( 5 ) 善些或工f 蕴涵硬z u y ) ； ( 6 ) x 苫( x n d 蕴涵工酉且工召： ( 7 ) x e ( - x ) 当且仅当x e x 不成立： ( 8 ) x 0 当且仅当礁z 不成立。 2 2 3 知识约简 知识约简是粗糙集理论的核心内容之一网众所周知，知识库中知识( 属 性) 并不是同等重要的，甚至其中某些知识是冗余的所谓知识约简，就是在 9 山东师范大学硕士学位论文 保持知识库分类能力不变的条件下，删除其中不相关或不重要的知识。 定义2 1 2 ：令孵为一族等价关系，re 吼， 果i n d ( 9 1 ) = i n d ( 9 1 一 胄 ) ， 则称足为飒中不必要的：否则称卫为孵中必要的。 定义2 1 3 1 1 】：如果每一个r 孵都为吼中必要的，则称倪为独立的；否则称 孵为依赖的。 定理2 5 1 1 i ：如果吸是独立的，p 吼，则p 也是独立的 定义2 1 4 1 1 1 ；设q g p ，如果q 是独立的，且n ( q ) = 届，d ( p ) ，则称q 为 尸的一个约简。显然，p 可以有多个约简。尸中所有必要的属性组成的集合称 为p 的核，记作c o r e ( p ) 。 核与约简有如下关系。 定理2 6 ：c o r e ( p ) = t i r e d ( p ) ，其中r e d ( p ) 表示p 的所有约简的集合，且 f l r e d ( p ) = nq 。 q e g 即l ( e ) 可以看出，核这个概念的用处有两个方面：首先它可以作为所有约简的计 算基础，因为核包含在所有的约简之中，并且计算可以直接进行；其次可解释 为在知识约简时它是不能消去的知识特征集合。 在应用中，个分类相对于另一个分类的关系十分重要，因此下面将介绍 知识的相对约简( r e l a t i v er e d u c t ) 和相对核( r e l a t i v ec o r e ) 的概念。 定义2 1 5 1 1 1 ：令p 和q 为等价关系族，r p ，如果 p 0 口( 竹( j m d ( q ) ) = p o 吒呱叫r ) ( n r d ( q ，则称r 为p 中q 不必要的；否则r 为p 中q 必要的。 为简单起见，本文采用p 缉( q ) 代替p o 。( 竹( n d ( q ) 定义2 1 6 f l l ：如果p 中的每个r 都为q 必要的，则称p 为q 独立的( 或_ p 相 对于g 独立) 。 定义2 1 7 1 1 ；设s 尸，s 为p 的q 约简当且仅当s 是，的q 独立子族且 ，0 峰( 9 = p o s e ( q ) 。p 的q 约简简称为相对约简。尸中所有q 必要的原始关 1 0 山东师范大学硕士学位论文 系构成的集合称为p 的q 核，简称为相对核，记为c o e e q ( 即 定理2 7 1 1 ：见( p ) = n 兄b ( p ) ，其中见凹b ( p ) 是所有p 的q 约简构 成的集合。 2 2 4 信息系统与决策表 定义2 1 8 ：形式上，四元组8 = ( u ，五，矿，乃是一个信息系统( i n f o r m a t i o n s y s t e m ) ，其中： u ：对象的非空有限集合，称为论域； 五：属性的非空有限集合，r = c u d 子集c 和d 分别称为条件属性集和 决策属性集；r ：y = uk ，是属性，的值域； f ：u x r 哼矿是一个信息函数，它为每个对象韵每个属性赋予一个信息值， 即r r ，x u ，f ( x , r ) 巧 通常s = 彤，见d 简记为s = u ，两$ f f i ，彤也称为知识表达系统或知识r 定义2 1 9 1 1 l ：s t u ，r , v ，力是一个信息系统，具有条件属性和决策属性的信， _ 息系统可以表达为决策表，记为r = ( u ，r ，y ，f ) 其中，关系训够) 和关系蒯t d ) 的等价类分别称为条件类和决策类 简单介绍一下两个信息系统之间的关系 定义2 2 0 ：令墨= 和邑= ，吃) 为两个信息系统若肋( 巧) = 肋( 匕) ， u p v r , = u v = ，则称和t ( 或墨和气) 是等价的，记作i 。t ( 或l t ) 这个概念意味着可以用不同的属性集对对象进行描述，以表达关于论域的 完全相同的事实 对于置= ( u ，墨) 和嘎= ，吒) 两个信息系统，当肋( 巧) c 肋( ) 时，称信息 系统墨( 或属性集墨) 比信息系统墨( 或属性集恐) 更精细，或者称墨比一更 粗糙当比毛更精细时，也称薯为t 的特化，& 为的推广 山东师范大学硕士学位论文 第三章基于完备信息系统的知识约简算法研究 3 1 引言 r s 理论除了对知识的不精确性给出描述之外，其另一个最重要的贡献是提 供了一种对数据库中的知识进行约简的方法。从前面的讨论可以看出，一个信 息系统或决策表可能有多个约简，即它们的约简不是唯一的。约简中属性的个 数将直接影响r s 理论导出的规则的规模。一般来说，约简中的属性越少，则 由它导出的规则数就越少；而且，用这些规则对新的对象进行分类时的检验代 价就越低，在实际应用中，人们总是希望找出信息系统或决策表的最小约简。 如果一个信息系统研究的对象数目为m ，属性的数目为一，考察一个属性 集的简化要进行o ( n m 2 ) 次比较，一个属性也可构成2 个子集，这些子集都有可 能是最小子集，那么要求出所有最小简化子集的运算将是o ( 2 “x m 2 ) 川嘲次基本操 作，这是一个很耗时的复杂运算最小子集求解既是粗糙集理论研究中的基本 问题，也是一个复杂问题，w o n g s k m 和z i a r k o w 在1 9 8 5 年已经证明找出 一个信息系统或决策表的最小约简是n p - h a r d 问题1 9 1 ，这主要是因为要求出最 小约简需要尝试属性的各种组合，必然要遇到组合爆炸问题。在a i 领域中，解 决这种问题的一般方法是利用启发信息，减少问题的求解的搜索空间【1 0 1 本章 将对完备信息系统下的粗糙集理论中当前已提出的知识约简算法进行简单分 析，并给出相应的知识约简算法 3 2 知识约简的一般方法 3 2 1 基本算法 根据约简的定义，从表中删除属性，如果删除属性后的表能表达原来的信 息系统，继续比较；如果不能，就恢复为前一个表，然后删除另外一个属性 直到所有的属性都不能删除时。这时，我们得到的就是信息系统的一个约简。 算法描述： 输入：信息系统s = ( 【，y ，n ，其中u 为论域，为属性集，彳= c u d ， 1 2 山东师范大学硕士学位论文 c n d = o ，c 为条件属性集合，d 为决策属性集合 输出：约简倒 s t c - p 1 初始化；r e d = c = s t e p 2 令t e m p = r e d s t e p 3 如果t e m p a ，进行循环 取口e c ，判断：如果一 4 ( d ) = p $ 0 ( d ) ，贝l j r e d = r e d 一 口 ：并 t e m p z r e d ；否贝把矾p = t e m p 一 4 ； s t e p 4 输出r e d 上述算法，能够得到决策表的一个属性约简结果，但不一定能够得到一个 满意的属性约简结果。利用这个算法，还可以采用搜索策略得到所有可能的属 性约简如果采用宽度优先策略，可以首先从原始决策表中删除一个属性，得 到所有可能的包含一一1 个条件属性的子决策表然后再反复地在这些子决策表 上进行上述操作，最终就可以得到所有可能的属性约简。同样，也可以采用深 度优先策略。但是，由于这是一个组合爆炸问题，穷尽的搜索所需要的时间和 空间代价都很高，实际计算属性约简的时候，往往采用某种启发式算法 3 2 2 基于信息熵即s h a n n o n 熵的启发式算法1 1 - 1 4 4 1 1 这种算法的基本思路是：先计算出核，而后根据其它属性的重要程度依次 在核的基础上添加或者也可以根据决策属性对条件属性的依赖程度依次剔除掉 那些对分类不产生影响的属性，直到使所得的知识与原信息系统( 或决策表) 的分类能力相同为止。 在基于信息熵的约简算法中认为添加最重要属性后，信息熵的增量最大， 即 s i g ( c , b ，_ ) = h c c l 口) = 日( 口u c ) 一h ( 聊 鼢c c ：e 舻一恕身4 ) c 为最重要的属性。其中日( b ) 、h ( c l 研为知识b 的信息熵及知识b 相 对于知识c 的条件其定义如下：设p 、q 为论域u 上的两个等价关系族，且 山东师范大学硕士学位论文 u i 耐( p ) = 五，奠，以) ，u l 耐( q ) ；辑，圪，y _ ) ，则知识p 的信息熵h c p ) 为： 日( 一2 - l - l z p ( x j ) l o g p ( x 1 ) 知识相对于知识的条件熵为： 日 l 一2 嚆p 三1 ( y j l x i 崦p ( 0i 五) 算法的终止条件为；日( = 日( ) 。 其典型算法如下： 输入：一个决策表r = ( u ，c u d ，矿，) ，其中，u 为论域，c 、d 分别为条件 属性集和决策属性集 输出：该决策表的一个相对约简口。 s t e p l 计算决策表r 中决策属性集d 相对条件属性集c 的条件熵h ( d 1 0 。 s t e p 2 计算条件属性集c 中相对决策属性集d 的核属性集c o ，并令 , 4 i t = c c o s t y 3 令b = c o s t e p 3 1 如果l 叫! = o ，则计算条件熵日( d i 口) ，转s t e p 3 4 ； s t e p 3 2 对每个属性qe a t t ，计算决策属性集d 相对条件属性集b u h 的 条件熵日( d i b u q ) ； s t e p 3 3 选择使( d ib u q ) 最小的属性q ( 若同时有多个属性达到最小 值，则从中选取一个与占的属性值组合数最少的属性) ，加= 彳盯一 勺) ， 丑= 口u 町 ； s t e p 3 4 若日( d l 功= 日( d ic ) 则终止，否则转s t e p 3 2 3 2 3 基于依赖度的知识约简算法【1 5 】【1 6 1 1 4 山东师范大学硕士学位论文 定义3 1 等价关系族相对于等价关系族的依赖度 在信息系统中s = ，) 中，u 是论域，是关系族，设p ，q c a 的关系族， 那么q 对p 的依赖度d e p p ( q ) ，定义成： 锄= c a r d p o s 删耐 p ) ( ( i u n d ) ( q ) ) 当然，0 = a e p _ p ( q ) = 1 ( 1 ) 当d e p e ( q ) = l 时，则q 对p 是强依赖的； ( 2 ) 当却，( q ) 1 时，则q 对p 是弱依赖的； ( 3 ) 当d e p e ( q ) = 0 时，则q 对p 是完全不依赖的 根据定义3 1 中依赖度的定义， 果a e p x ( d ( 4 ) d e p z ( r ) = c a r d , p o $ 耐删t x ) ( i n d ) ( y ) ) ( 5 ) 矿( 如h ( 】功= l ( 6 ) c o m e ( x ) = c o e , e ( x ) nz ( 7 ) e m t f o r ( 8 ) r e m m ( c d r e ( x ) ) 3 2 4 遗传算法在知识约简中的应用 3 2 4 1 遗传算法简介1 9 】冽 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 是模拟达尔文的遗传选择和自然淘汰 1 5 山东师范大学硕士学位论文 的生物进化过程的计算模型。它是由美国m i c h i g a n 大学的j h o l l a n d 教授于1 9 7 5 年首先提出的其基本过程如图： 遗传算法是具有“生成一检测”迭代过程的搜索算法，其操作对象是种群 中的所有个体。选择( s e l e c t i o n ) 、交叉( c r o s s o v e r ) 和变异( m u t a t i o n ) 是遗传 算法的三个主要操作，遗传算法通过这三个操作模拟了大自然的进化过程 3 2 4 2 基于遗传算法的知识约简算法1 7 】【1 8 1 定义3 1 ：设尸c c ，对于划分“，匕，)