（计算机软件与理论专业论文）增量式粗糙集属性约简算法的研究.pdf

摘要 粗糙集理论是波兰数学家z p a w l a k 提出的一种可用于处理不精确性、模糊性 和不确定性的有效的数学工具。其特点是在无先验知识或者附加信息的情况下处 理数据。粗糙集在数据挖掘、知识约简等方面有很好的应用前景。 属性约简是粗糙集理论的核心内容之一，其能够在保证系统分类和决策能力 不变的前提下对数据库中的冗余属性进行约简，简化知识表示，提高系统处理的 效率，方便用户决策。由于信息系统在对象、属性变化时，需要得到更新后的信 息系统的属性约简，这样，对于增量式粗糙集属性约简算法的研究慢慢开展开来。 本文通过对增量的粗糙集求核以及属性约简算法进行深入研究，主要的研究 内容如下： ( 1 ) 提出了一种改进的基于正区域的决策表增量属性约简算法。首先计算原 决策表与增量决策表的等价类、核、j 下区域等信息。其次通过分析，原决策表以 及增量决策表的等价类与新决策表的等价类关系，得到新决策表的等价类；分析 原决策表的正区域信息，增量决策表的正区域信息，得到新决策表的j 下区域等信 息。最后根据上述的条件作为基于正区域的决策表求核。在新决策表核属性集合 的基础上，使用属性重要性算法对决策表进行属性约简。 ( 2 ) 提出了一种改进的基于信息熵的决策表增量属性约简算法。首先将决策 表划分成多个小的同构的决策表，然后对各个同构决策使用基于信息熵的算法求 核，最后通过对原决策表与各同构决策表在属性约简之间核，等价类等的关系， 整合得到整个决策表的属性约简。 关键词：粗糙集；属性约简； 增量； 信息熵 a b s t r a c t r o u g hs e tt h e o r yw i l l 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 k ，t h i st h e o r y w a sm a d eo fan o n - p r e c i s i o n ，a m b i g u i t ya n du n c e r t a i n t yo fa ne f f e c t i v em a t h e m a t i c a l t 0 0 1 t h ea d v a n t a g e so ft h i st h e o r yd on o tn e e d p r i o r ik n o w l e d g e so ra d d i t i o n a l i n f o r m a t i o n s ，a n di th a sag o o da p p l i c a t i o np r o s p e c t si nd a t am i n i n g ，k n o w l e d g e r e d u c t i o n ，e t c a t t r i b u t er e d u c t i o ni so n eo ft h ec o r ec o n t e n t s ，w h i c hc a ne n s u r et h ec l a s s i f i c a t i o n a n dd e c i s i o n - m a k i n gc a p a c i t yu n d e rt h ep r e m i s eo fc o n s t a n tr e d u c t i o no fr e d u n d a n t a t t r i b u t e si nad a t a b a s e ，t os i m p l i f yt h ek n o w l e d g er e p r e s e n t a t i o n , t oi m p r o v et h e e f f i c i e n c y o fs y s t e m p r o c e s s i n g ，t h e c o n v e n i e n c e d e c i s i o n m a k i n g b e c a u s e o f a t t r i b u t e so ro b j e c t sc h a n g i n go fi n f o r m a t i o ns y s t e m ，p e o p l en e e dt og e tan e w a t t r i b u t er e d u c t i o n ，8 0t h a t ，t h er e s e a r c ho nr o u g hs e t sf o ri n c r e m e n t a la t t r i b u t e r e d u c t i o na l g o r i t h mh a sb e e nl a u n c h e ds l o w l y b a s e do nd e e ps t u d i e so ni n c r e m e n t a la t t r i b u t e sr e d u c t i o na l g o r i t h m sa n dc o r e c o m p u t i n ga l g o r i t h m so ft h er o u g hs e tt h e o r y ，t h em a i nr e s e a r c hc o n t e n t sa r ea s f o l l o w s ： ( 1 ) w ep r o p o s ea ni m p r o v e di n c r e m e n t a la t t r i b u t e sr e d u c t i o na l g o r i t h mb a s e do n t h e p o s i t i v er e 西o n a ld e c i s i o n - m a k i n gt a b l e f i s r t l y c a l c u l a t et h e o r i g i n a l d e c i s i o n - m a k i n gt a b l e a n di n c r e a s e da m o u n to fd e c i s i o nt a b l e n u c l e a r s ，a n d e q u i v a l e n c ec l a s s s e c o n d l y ，a c c o r d i n gt ot h ea n a l y s i so ft h er e l a t i o n s h i pb e t w e e nt h e o r i g i n a ld e c i s i o nt a b l e ，a n dt h ei n c r e m e n to fd e c i s i o nt a b l e se q u i v a l e n c ec l a s s ，w e c a ng e tt h et h en e wd e c i s i o nt a b l e se q u i v a l e n c ec l a s s a c c o r d i n gt ot h ea n a l y s i s b e t w e e nt h eo r i g i n a ld e c i s i o nt a b l e sr e g i o n a li n f o r m a t i o na n dt h ep o s i t i v er e g i o no f i n c r e m e n t a lt a b l e ，w ec a ng e ti n f o r m a t i o n so ft h en e wi n c r e m e n t a lt a b l e sp o s i t i v e r e g i o na n do t h e ri n f o r m a t i o n s a n dw i t ht h ec o n d i t i o n sa sa b o v e ，t h ed e c i s i o nt a b l e s c o r ec o u l db ec a l c u l a t e d f i n a l l yc a l c u l a t et h ea t t r i b u t er e d u c t i o no ft h en e w i n c r e m e n t a ld e c i s i o n - m a k i n gt a b l e ，u s i n gt h ea l g o r i t h mb a s e do na t t r i b u t ei m p o r t a n c e i i ( 2 ) a ni m p o r o v e da l g o r i t h mh a sa d v a n c e db a s e do nt h ei n f o r m a t i o ne n t r o p y a t t r i b u t er e d u c t i o na l g o r i t h m t h i sa l g o r i t h mi su s e dt og a i nt h ea t t r i b u t er e d u c t i o ns e t s o fa ni n c r e m e n t a ld e c i s i o n m a k i n gt a l b e f i r s t l y , d i v i d et h ed e c i s i o n - m a k i n gt a b l ei n t o s o m es m a l ld e c i s i o n m a k i n gt a b l e s s e c o n d l y , c a l c u l a t et h e s es m a l ld e c i s i o n m a k i n g t a b l e s c o r e sb a s e do nt h ee n t r o p ya l g o r i t h m f i n a l l y , a c c o r d i n gt ot h er e l a t i o n s h i p b e t w e e nt h e s es m a l ld e c i s i o n m a k i n gt a b l e sa n dt h eo r i g i n a lt a b l e , w ec o u l dg a i nt h e a t t r i b u t er e d u c t i o no ft h i so r i g i n a ld e c i s i o n - m a k i n gt a b l e k e yw o r d s ：r o u g h ts e t ；a t t r i b u t er e d u c t i o n ；i n c r e a m t a l ；i n f o r m a t i o ne n t r o p y i l i 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名： 杳c 、 日期加p 年乡月多日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。同时授权中国科学技术信息研究所将本论文收录到 中国学位论文全文数据库，并通过网络向社会公众提供信息服务。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名： 苍坎 日期：孑够年乡月e l 跏硌下v 纸脚一日 第一章绪论 1 1增量粗糙集属性约简研究的的背景和意义 随着当代科学技术的飞速发展，人们在收集和处理数据方面的能力日益增强， 在收集数据方面在数量和精确度上都有了很大的提高。我们需要根据这些复杂的 数据中得出某些规则来确定决策。在得到规则的同时删除不影响系统决策能力的 属性的过程在粗糙集理论中叫属性约简。因为冗余属性的存在，既对计算机资源 的浪费( 需要大量的存储空间) ；又干扰人们作出正确决策。属性约简是在保持决 策系统分类或决策能力不变的条件下，删除其中不相关或不重要的属性。换言之， 就是通过对决策表中已有数据及其关系的分析，在不影响原决策表功能的前提 下，将一些无用的不影响原系统的知识表示的多余属性去掉，以达到约简条件属 性集的目的。 当前，智能信息处理已成为信息科学理论以及应用研究中的一个热点问题。 尤其是近年来，人工智能方法发生了很大的发展，在对于高层次智能行为的研究 中，研究还处于知识表示和符号推理上。而随着计算机技术的飞速发展，知识在 不同时期被赋予不同的含义，知识将与大量观察和实验数据的处理、归纳、分类 相联系。因此如何对不完整数据进行分析、推理，以及发现数据间的关系，提取 有用规则和约简信息处理以及研究不精确、不确定知识的表达、学习、归纳方法 等已成为智能信息处理中的重要的研究对象。经过多年的研究，人们在对专家系 统、知识工程、人工神经网络、模糊集等领域进行的许多的实践和探索后，取得 了很多很好的成绩。随着信息时代的到来，数据飞速地增长，并且在许多情况下 数据中含有大量的多余的信息和噪声。那么如何从这些数据中挖掘潜在的、有价 值的信息( 知识) ，这就向人类的智能信息处理能力提出了挑战。因此，研究能够 从大量信息中形成实际概念的系统就显得尤为重要。 上世纪七十年代术到八十年代初，波兰控制论专家p a w l a k 及其合作者为解决 如何在带有不确定的数据资源上进行知识获取和知识表示这一问题创立了一种 全新的数学理论一粗糙集理论( r o u g hs e t st h e o r y ) 【l 】。现在，以粗糙集理论为 支撑的各种数据分析方法统称为：粗糙集数据分析( r s d a ) c 2 1 。粗糙集数据分析 ( r s d a ) 与传统的方法相比有一些不同：如：统计学方法基于的是数据的概率分 布假设，它采用b a y e s 法则进行规则提取。由于该方法在推导过程中所用的先验 概率和条件概率均需要建立在大量的统计资料上，所以它不适合于数据规模较小 的决策问题。而r s d a 贝j 相反，它不是刻意减少数据的不确定性，而是描述这种不 确定性，即使在数据规模较小的情况下，也能最大限度地导出决策规则。证据理 论采用信任函数和取值表示对某个概念的信任程度。通常信任度和似然度是由专 家给出基本概率分配函数( m a s s 函数) 后通过计算的到的，因而证据理论带有很 大的主观性。而在粗糙集理论中，一个待认识的普通概念是被两个精确概念( 可 被认识的、可被现有的信息精确表达的) 从外延的角度近似表达。根据数据本身， 他们被确定的计算出来。这一过程不需要任何关于数据的外加信息。信息系统的 属性约简算法的研究是一个比较重要的工作。国内外学者在这个方面做了很多研 究，但对于增量情况下的属性约简的算法还不是很多。 1 2 国内外研究现状 经过二十余年的发展，粗糙集理论及其应用在世界范围内的受到广泛关注， 许多国际会议将其列为专题。自粗糙集理论提出以来，大致从两方面研究粗糙集 理论及其应用。一方面是对粗糙集的理论研究，主要集中在粗糙代数、粗糙集拓 扑及其性质、粗糙逻辑及近似推理的逻辑工具等方面。这些研究结果充分论述了 粗糙集与模糊集、证据理论与粗糙集理论之间的关系，也建立了粗糙集与概率逻 辑、粗糙集与模态逻辑之间的关系。另一方面，有关粗糙集方法的函数研究方面， 近年来出现了不少粗糙数及粗糙隶属函数的研究，发表了不少实数粗糙离散化等 方面的论文。粗糙集理论在应用方面的研究也在不断涌现，通常这些应用联系于 被称为粗糙集数据分析( r s d a - r o u g hs e td a t aa n a l y s i s ) 的技术。利用粗糙集 处理的主要问题包括数据库中的数据约简、数据相关性的发现、数据意义评估、 由数据产生决策控制算法、数据的近似分类、数据中的相似性或差异性发现、数 据中范式的发现以及因果关系发现等。 知识约简是粗糙集理论的核心内容之一，其主要思想是在保持信息系统的分 2 类能力不变的前提下，消除信息系统( 决策表) 中不必要的知识，导出最终的决 策或分类规贝l j t 3 1 。许多属性约简首先从求核属性集合开始。在求核方面的研究已 有不少，其中h u 提出的基于差分矩阵的求核算法是比较好的求核算法闻。此算法 能有效减少计算量，从而提高求核的效率，缺点是在某些情况下，不能得到正确 的核。叶东毅教授等人对此算法为基础，设计出新的差分矩阵的算法，并证明此 算法的正确性。此算法的缺点是计算量比较大o - n ；王国胤教授则在求核上从代 数观点和信息论观点上进行了比较深入的探讨。分析这两个观点上的求核的一致 性和差异性，有效地对叶东教毅授提出的算法进行了补充网。此算法的缺点也是 效率低的问题。杨明教授等人的改进的差别矩阵及其求核方法则在改正h u 算法在 某些情况下得不到核的错误的同时降低了计算的复杂度。对于信息系统增加对象 或者删除对象，添加属性或者删除属性，需要更新核属性或者更新约简【l 孓乃】，现 在已经有相关的研究。目前对增量情况下的粗糙集核更新或者属性约简更新的算 法主要是基于正区域、区分矩阵、信息熵角度下给出的增量算法阱羽。这些算法 是针对信息系统在增加一个对象，或者多个对象，一个属性或者多个属性下，原 来信息系统在添加或者删除对象或者属性后的变化规律来更新信息系统的核或 者约简。 1 3 粗糙集理论的研究内容和应用 1 3 1粗糙集理论的研究内容 在粗糙集理论提出后，人们大致从两方面来研究粗糙集理论及其应用。一方 面是对粗糙集理论的研究，其研究主要集中在粗糙代数、粗糙集拓扑及其性质、 粗糙逻辑及近似推理的逻辑工具等方面。这些研究的结果主要是论述了粗糙集与 模糊集、证据理论与粗糙集理论之间的关系，同时也建立了粗糙集与概率逻辑、 粗糙集与模态逻辑这些概念之间的关系。另一方面，在粗糙集方法的函数研究方 面，这些年来，人们应用粗糙集及其理论方法发表了很多文章并解决实际中许多 问题。 3 1 3 2 粗糙集理论的应用 粗糙集理论在应用方面的研究在粗糙集理论提出后日渐增多，这些应用主要 是与粗糙集数据分析( r s d a - - r o u g hs e td a t aa n a l y s i s ) 这一技术相关。利用粗 糙集来处理的主要问题主要是数据库中的数据约简、数据相关性的发现、数据意 义评估、由数据产生决策控制算法、数据的近似分类、数据中的相似性或差异性 发现、数据中范式的发现以及因果关系发现等。特别地，粗糙集方法在医学、药 学、银行、金融、市场研究、工程设计、气象学、振动分析、开关函数、冲突分 析、图像处理、声音识别、并发系统分析、决策分析、字符识别以及其它领域都 有重要应用。因此，r o u g h 集理论与其它一些软计算理论，诸女i f u z z y 集、粒计算、 神经网络、遗传算法等均已经成为当前国内计算机及相关专业的研究热点。 1 4 该文主要研究内容和结构组织 除绪论外，本文主要内容如下： 第二章中概述了粗糙集的基本概念及属性约简算法。主要是在属性约简过程 中用到的一些基本概念：知识与知识库、不可分辨关系、近似与粗糙集、下上近 似集、正域、负域和边界域、知识约简、知识的依赖性、信息系统和决策表。 另外第二章还介绍粗糙集属性约简的几种基本的算法：基本的属性约简算法、基 于区分矩阵的属性约简算法、基于属性重要性的算法、基于信息熵的属性约简算 法。 第三章介绍基于正区域的决策表增量属性约简算法研究。对正区域求核中遇 到的计算等价类效率低如何解决的问题，以及怎么根据原有决策表，新增决策表 得到的核、等价类等信息，得到新决策表的核，属性约简。在本章中，从算法的 原理，要解决的问题开始到最终给出一种改进的基于正区域的决策表增量属性约 简算法。最后进行实验，并分析得到增量下的算法效率比标准的算法好。 第四章介绍基于信息熵的决策表增量属性约简算法研究。将一个决策表划分 成多个小的同构决策表，从这些同构决策表计算得到的核、属性约简与原决策表 的核、属性约简的关系，给出了决策表在信息熵下的增量属性约简算法，通过实 4 验证明此算法的有效性。 最后总结全文所做的工作，工作中存在的不足和缺点，并指出今后的研究方 向。 第二章粗糙集属性约简算法 2 1信息表知识表达系统 2 1 1 知识的分类概念 知识是人类通过实践认识到的客观世界的规律性的东西，是人类实践经验的 总结和提炼，具有抽象和普遍的特性，知识是信息经过加工处理、解释、挑选和 改造而形成的。知识是命题、规则等的集合。知识一般可分为说明性的知识、过 程性的知识和控制性的知识。说明性的知识提供概念和事实。例如，一个智能检 索系统中，说明性的知识包括说明具体事实的数据库内容。用规则表示问题的知 识称作过程性的知识。智能检索系统中利用过程性的知识处理说明性知识。用控 制策略表示问题的知识称为控制性知识。控制性知识包括有关各种处理过程、策 略和结构的知识，常用来协助整个问题求解的过程p l 】。 通常我们在对显示问题进行处理的时候，会将我们讨论的现实个体( 或称元 素、对象、样本) 局限在某一个特定的区域范围之内，这个区域内的所有个体就 组成了问题的论域u 。以分类为基础，可以将分类理解成等价关系，而这些等价 关系对论域u 进行划分。对于论域中由等价关系划分出来的任意子集x ，都可以 称为u 的一个概念。这罩我们认为空集也是一个特殊的概念。论域u 中的任意 概念簇成为关于论域u 的抽象知识，简称为知识，它代表了论域【，中个体的分 类。 知识的可以定义为：给定一组数据( 集合) u 和等价关系集合r ，在等价关系 集合尺下对数据集合u 进行划分，成为知识，记为u r 。u 上的一簇划分称为 关于【，的知识库。 设u 是一个论域，尺是u 上的一个等价关系。u 尺表示u 上由r 导出的 所有等价类。【石】矗表示包含元素x 的尺的等价类，x u 。一个知识库就是一个关 系系统k = u ，p ) ，其中u 是论域，尸是u 上的一个等价类。如果q 互p 且q 囝， 则n q ( q 的所有等价类的交) 也是一个等价关系，记作i n d ( q ) 。 6 定义2 1 设k = u ，p ) 和k i = u ，q ) 是两个知识库。如果i n d ( p ) = i n d ( q ) ， 则称k 和k ( 或q 和尸) 是等价的，j 已 f fk 兰k ( 或尸兰q ) 。 2 1 2 信息表达系统 知识的表达是信息系统的关键。所谓知识获取，就是要从大量数据信息中发 现有用的、有规律的信息，也就是将知识从数据表达方式转换为一种新的目标表 达形式。基于粗糙集理论的知识发现，主要是借助于信息表这样的一种有效的数 据表知识表达方式。 信息表知识表达系统的基本成分是研究对象的集合，关于这些对象的知识是 通过指定对象的属性( 特征) 和它们的属性值( 特征值) 来描述的。一般地，一个信 息表知识表达系统s 可以表示为 s = 这里，u 是对象的集合，r = c u d 是属性集合，子集c 和d 分别成为条件属性 集和决策属性集，矿= uk 是属性值的集合，k 表示属性，r 的属性值的范围， 即属性，的值域厂：u xr _ v 是一个信息函数，它指定u 中的没一个对象x 的属 性值。 对于每一个属性子集bc _ r ，定义不可分辨二元关系i n d ( b ) 是一个等价关 系，即i n d ( b ) = f i x ，y ) eu z , v 6 b ( 6 ( x ) = 6 ( y ) ) ) ，显然，i n d ( b ) = ni n d ( b ) 。 b e 口 2 1 3 决策表 决策表是一类特殊的而且比较重要的一类比较特殊的知识表达系统。它表示 当满足某些条件时，决策应当如何进行。决策表定义如下： 定义2 2 一个决策表是一个信息表知识表达系统s u ，r ，矿，厂 r = c u d 是属性集合，子集c 和d 分别成为条件属性集和决策属性集，d g 。 条件属性c 和结果属性d 的等价关系i n d ( c ) 和i n d ( d ) 的等价类分别称为条 件类和决策类。 根据决策表中的决策属性是否唯一来判断决策表是单一决策表还是多决策。 7 2 2 粗糙集的基本概念 令xsu ，且尺为一等价关系。当x 是某些r 的基本范畴的并时，我们称x 为尺可定义的，否n x 为r 不可定义的。r 可定义集合是论域的子集合，它可在 知识库k 中被精确地定义，而尺不可定义集不能在这个知识库中被定义。尺可定 义集也称为尺精确集，而r 不可定义集也称为尺非精确集。 当存在一个等价关系r i n d ( k ) 且x 是尺精确集，集合x u 称为k 中的精 确集；当对于r i n d ( k ) ，但x 为尺粗集，则x 称为k 中的粗集合。粗糙集可近似 地定义，使用两个精确集( 粗糙集的上近似集合和下近似集合) 来描述。 定义2 3 假定给定知识库k = ( u ，尺) ，对于每个x u 和一个等价关系 r i n d ( k ) ，可以根据尺的基本集合的描述来划分集合x 。为了衡量 d e s ( y ，) ，r r ) 精确地说明x 中对象的隶属度情况，考虑两个子集合： 足( x ) = u r u r ：y 互x ) r 一( x ) = u r u r ：】，n x a ) 分别称它们为x 的r 的下近似和尺的上近似。 上近似集、下近似集也可用下面的等式来描述： 足( x ) = u x u ：【x 】r x ) r 一( x ) = u x u ： x 】rn x a ) 即当且仅当【z 月x ，x 足( x ) 时；当且仅当 x 】月n x g ，x r 一( x ) ，集合 b n r ( x ) = r 一( x ) 一足( x ) 称为x 的r 边界。引( x ) 是对于知识尺既不能归入x 也 不能归入一彳的元素的集合。 我们也把p o s r ( x ) = 足( x ) 称为x 的r 正区域，把n e g r ( x ) = u 一足( x ) 称为 x 的负区域，把剧( x ) 称为x 的边界域。 r 一( x ) 是对于知识尺、u 中所有一定能归于x 的元素的集合，r 一( x ) 是对于 知识r 、u 中可能归入x 的元素的集合： 2 3 知识的约简与数据的依赖性 知识约简和知识的依赖性是粗糙集理论中两个最基本的问题圈。知识约简是 研究知识库中每个等价关系是否都是必要的，以及如何删除不必要的知识。知识 约简在机器学习、信息系统分析与数据挖掘等领域都具有重要的应用意义。知识 之间的依赖性决定知识是否可以进行约简，根据依赖性所定义的知识的重要性往 往是知识约简的重要信息。 2 3 1知识的约简和核 在对约简和核进行讨论之前，我们先作如下定义： 定义2 4 令尺为一等价关系簇，且，r ，当i n d ( r ) = i n d ( r 一，) ，称，为尺 中可省略的，否则，为r 中不可省略的。 当对于任一，r ，若尺不可省略，则簇尺为独立的。若尺是独立的，且 p c _ r ，则p 也是独立的。当q 是独立的，且i n d ( p ) = i n d ( q ) ，q p 为p 的 约简。显然尸可以有很多种约简。p 中所有的不可省略关系的集合，称为p 的核， 记作c o p e ( e ) 。 核与约简的关系如下： 定理1c o r e ( p ) = n r e d ( p ) ，其中r e d ( p ) 是p 的所有约简簇。 证明：当q 为p 的一个约简，且r p q ，则 i n d ( p ) = i n d ( q ) ，q p p ) p 则i n d ( q ) = i n d ( r ) ，设r = p 一 ，) ，我 们可以得出，为冗余的，即，诺c o r e ( p ) ，且c o r e ( p ) gn ( q ：q r e d ( p ) ) 。 假设，gc o r e ( p ) ，即r 是p 中冗余的，则意味着i n d ( p ) = i n d ( p p ) ) 可以导出存在独立子集合s 互p p ) ，因此i n d ( s ) = 1 n d ( p ) ，故s 是尸的一个 约简，且尺s 。这表明：c o r e ( p ) 3n q ：q r e d ( p ) ) 。 可以看出，核这个概念的用处有两个方面：首先它作为所有约简的计算基础， 因此核包含在所有的约简之中，并且计算可以直接进行；其次它可以解释为：当 知识约简时它是不能消去的知识特征部分的集合。 2 3 2 知识的相对约简和核 本节我们介绍知识的相对约简和相对核的概念。 定义2 5 令尸和q 为论域( ，中的等价关系，q 的p 正区域。记为 9 p o s e ( q ) = u ( x ) ，p 和q 为论域u 中的等价关系簇，当 尸粥赫( p ) ( 胁d ( q ) ) = p ( p - ，) ) ( 上d ( q ) ) 时，称，p 为p 中q 可省略的。否则， 为p 中q 是不可省略的。 对于【，p 的分类，u q 的正区域是论域中所有通过用分类u p 表达的知 识能够精确地划入到u q 的对象集合中。 定义2 6 当p 中的每一个，是q 不可省略的，则称p 为q 独立的( 或者称p 对 于q 独立的) 。当s 为p 的q 独立子簇，且p o s s ( q ) = p o s p ( q ) ，则簇scp 称为 尸的q 约简。 当尸中的每一个，都为q 不可省略的，则称p 为q 独立的( 或者称尸是对于 q 独立的) 定义2 7p 中q 不可省略原始关系簇称为p 的q 核，记为c o r e o ( p ) 。 定理2c o r e o ( p ) = ( r e d o ( p ) 其中r e d e ( p ) 是尸的所有q 的约简簇。 证明与定理1 类似。 2 3 3 知识的依赖性 在进行知识约简的过程中，要从给定的知识中导出另一知识需要研究数据库 中函数之间的依赖关系。 依赖性可形式地定义： 令知识库k = ( u ，r ) ，且令p ，q 曼r ； ( 1 ) 当i n d ( p ) si n d ( q ) 时，知识q 是依赖于知识尸的； ( 2 ) 当尸j q 且q j p 时，知识p 是和知识q 等价，即p 兰q ( 3 ) 当不存在pjq ，且不存在qj p 时，p ，q 是独立的。 显然，当且仅当i n d ( p ) = i n d ( q ) 时，有p jq 。 我们通过一个示例来说明知识依赖的定义： 例假设给定知识p 和知识q ，且有以下的分类： 【，p = 五，黾) ， 恐，黾) ， 屯) ， 吒) ， 而) ) 【，q = “，) ， 屯，x 7 ，) ， 毛，民) ) 可见i n d ( p ) 互i n d ( q ) ，因此有p j q 。 1 0 2 3 4 知识依赖性的度量 为了度量知识的依赖性，我们形式化地定义知识的部门可推导性。 定义2 8 令知识库k = ( u ，r ) ，且令p ，q 至r ，当 k = r d q ) = c a r d ( p o s e ( q ) ) c a r d ( u ) 时，我们称知识q 是k 度可导的 ( 0 k 1 ) ，记作p j 。q 。其中c a r d 表示集合的基数。当k = 1 时，我们称q 是由 p 全可导的；0 k 1 时，我们称q 是尸粗可导的；当k = o 时，称q 是全不可导的。 根据属性依赖度的定义，任意属性a c r 的重要度的定义为： s i g ( a ，r ，d ) = k ( r u 缸) ，d ) 一k ( r ，d ) 由依赖性的定义可以得到，当pj ；q 时，则由q 导出的分类【，q 的正区域 将覆盖知识库k x l 0 0 的所有元素；另一方面，只有属于分类的正区域元素才 能被唯一的分类，即对象的k x l 0 0 元素通过知识尸划入分类u q 的集合中。 而系数0 ( q ) 是q 和尸之间依赖的度量网。 2 4 粗糙集属性约简算法 属性约简是粗糙集理论中的一个核心内容。在一般情况下，信息系统中的条 件属性并不是同样重要的，其中一些条件属性是多余的，在删除这些多余的条件 属性后，原系统的分类能力不会发生改变。属性约简就是在不影响原来的系统的 情况下，删除不相关或不重要的条件属性，使原有的系统得到简化网。在不同的 系统中，或者在不同的条件环境下，人们对属性约简的要求和期望是不一致的。 如果在某个信息系统中，存在一些属性，它们的属性值难以得到，这种情况下我 们所需要的就是求解信息系统的最小属性约简。而一般的情况下，我们希望得到 的约简是包含条件属性的数目尽可能的少的属性约简集合嗍。 2 4 1 基于区分矩阵的约简算法 区分矩阵是通过引入代数知识，将对知识库的约简问题转化为对矩阵的约简 问题。它是s k o w r o n 在1 9 9 1 年提出的一种基本的、常用的属性约简算法。利用区 分矩阵来构造区分函数，然后利用合取和吸收律来对区分函数进行约简，使之成 为析取范式，每个合取子式则就是约简后集合d 5 】。 定义2 9 给定信息系统s = ，论域u 中的元素个数为 i u i - ，l ，属性个数ia i _ 聊，s 的区分矩阵定义为一个对称的矩阵m ( s ) = 【c ：f ， 。h ， 其中，第i 行第j 列处的元素白定义为： ， 一j a l a e a t t ( x ，a ) f ( x 1 ，d ) ，( 而d ) f ( x j ，d ) o 玎一1o e s e 即勺是能够区分对象x ，y 的所有属性的集合。 显然，区分矩阵是一个对称矩阵，所以在分析区分矩阵时仅取其下三角部分。 由区分矩阵构造布尔函数，然后求出s 的全体约简，具体步骤如下： 输入：s = 输出：约简集合r e d ( u ) ( 1 ) 计算信息系统s 的区分矩阵m ( s ) ( 2 ) 根据区分矩阵m ( s ) 计算相关的区分函数厶( s ) ； ( 3 ) 计算区分函数厶( s ) 得到析取范式的每一个主蕴含式就是一个约简，求出 所有的约简。 下面给出基于区分矩阵的算法： 输入：一个目标决策系统s = ( u ，a ，v ，f ) ，其中u 是论域，a = c u d ，c 是 条件属性集合，d 是决策属性集合。 输出：s 的属性约简与核约简 ( 1 ) 计算u 1 n d ( c ) ，令c o r e = a ，r e d ( u ) = a ，n = iu i n d ( c ) l ，定义 一个区分矩阵m ( n ，z ) ，并给所有元素赋值为0 ： ( 2 ) 生成区分矩阵，将矩阵中属性组合数为l 的属性( 核) 列入到属性集合中 ( 核属性集合) 。 f o ri = lt on f o rj = i + lt on f o rk = lt o c l i f g ( 置) g ( 一) a n do k ( 置) o k ( t ) t h e n m ( i ，j ) = m ( f ，j ) u c i ) 1 2 ) ( 3 ) 求约简以及核 f o ri = lt on f o rj = i + lt on i f jm ( i ，j ) i = 1t h e nc o r e = c o r e u m ( i ，j ) r e d ( u ) = r e d ( u ) nm ( i ，) ) 即c o r e 为核，r e d ( u ) 为属性约简。 2 4 2 基于属性重要性的约简算法 在属性约简的过程中，如果从决策表中去掉某些属性，增加某些属性，删除 某些对象，添加某些对象都会相应地改变分类。在决策表中去掉某些属性，增加 某些属性，删除某些对象，通过考查其对决策的影响来找出重要的条件属性集来 进行约简。 由于信息系统的约简是个n p - h a r d 问题，所以在研究约简算法时使用启发信 息进行搜索决策表的约简。通常使用属性重要性作为启发式搜索的依据。因为信 息系统的属性重要性是建立在分类能力上的，所以，在衡量条件属性的重要性程 度的过程中，使用基于属性依赖度、j 下区域的代数方法和基于信息熵、条件熵和 互信息的信息论方法来衡量 骆铡。 属性的重要性有多种定义，在不同启发式条件下得到的表达式并不相同。下 面给出的是其中一个定义。 2 4 3 基于属性依赖度的约简算法 定义2 1 0 信息系统s = ，a = c u d ，c n d = f 2 j ，bcc ，则 a ( b ，d ) 刊p o s c ( d ) i iui 表示条件属性对决策属性的依赖程度。 定义2 1 1 信息系统s = ，a = c u d ，c n d = a ，则任意的属 性子集合b 在c 中的重要性定义为： s i g ( b ，c ) = o t ( b ，d ) 一a ( c b ，d ) 由于基于依赖度的属性约简算法还不是很完备，所以在计算的最后还需要另 外做一个反向消除的过程来确保属性约简的最小性。算法如下： 输入：信息系统s = ，其中u 是论域，a = c ud ，c 是条件属 性集合，d 是决策属性集合。 输出：s 的一个相对约简 步骤： ( 1 ) 初始化，约简集为空； ( 2 ) 对于不在约简集中的所有条件属性a t a ，计算其重要性s i g ( a i ，a ) 并按 重要性大d , t 4 序； ( 3 ) 取出重要性m a x ( s i g ( a i ，a ) ) 最大的条件属性，将其加入到