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

基于粗糙集理论的属性约简算法研究 摘要 粗糙集理论是2 0 世纪8 0 年代发展起来的种新的处理含糊性和不确定性问 题的数学工具，它是智能信息处理的一种重要方法，基于不可区分性思想和知识 简化方法。属性约简算法是粗糙集理论的核心内容。粗糙集属性约简的研究在知 识获取、机器学习、模式识别、决策分析、模型建立等实际应用中有重要的意义， 但是，由于属性约简被证明是一个n p h a r d 问题，因此，研究更为有效的属性 约简算法，有效地获取较优的属性约简，降低算法的时间复杂度，寻求快速的约 简算法仍是粗糙集理论的主要研究课题之一。 本文首先介绍了粗糙集理论的基本概念和相关知识，对粗糙集理论中基于区 分矩阵、属性重要度、信息熵的属性约简算法进行了系统综述，并且详细分析了 算法的时间复杂度和空间复杂度。 由于传统的粗糙集模型没有与关系数据库系统结合，该模型许多计算的基本 操作都是在平面文件上进行的，没有利用高性能的数据库集合操作。鉴于此，研 究人员提出了新的基于数据库系统的粗糙集模型，在关系代数的基础上对核属性 和约简进行重新定义，从而利用高效的面向集合的数据库系统操作。在此基础上， 提出了一种新的基于数据库系统的属性约简算法。最后，将此算法与几种典型的 属性约简算法从算法运行时间和约简结果的准确性进行了对比，得出了相应的结 论。 关键字：粗糙集，属性约简，数据库系统 s t u d yo na t t r i b u t er e d u c t i o na l g o r i t h mb a s e do nr o u g hs e t a b s t r a c t r o u g hs e tt h e o r yi san e wm a t h e m a t i c a lt o o lw h i c hc a nt a c k l ea m b i g u i t ya n d u n c e r t a i n t yd e v e l o p e df r o mt h e1 9 8 0 s i ti sa ni m p o r t a n tm e t h o do fi n t e l l e c t i v e i n f o r m a t i o nt r a n s a c t i o n ，w h i c h b a s e do f n o n d i s t i n g u i s h a n d k n o w l e d g e r e d u c t i o n f i n d i n gt h em i n i m a lr e d u c t i o ni so n eo ft h em o s ti m p o r t a n tw o r k si nt h e r e s e a r c ho fr o u g hs e tt h e o r y , a sa ni m p o r t a n tp a r to fs o f tc o m p u t i n g ，a t t r i b u t e r e d u c t i o np l a y sa p p l i c a t i o n sh a v ep l a y e da ni m p o r t a n tr o l e ，e s p e c i a l l yi nt h ea r e a so f k 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 e a n i n g ，p a t t e r nr e c o g n i t i o n ，d e c i s i o na n a l y s i sa n d m o d e l i n ge t c h o w e v e r , i th a sb e e np r o v e dt h a tf i n d i n gt h em i n i m a lr e d u c t i o n si sa n p - h a r dp r o b l e m s oi ti st h em a i ns t u d ya r e ao nr o u g hs e ti nr e s e a r c h i n ge f f e c t i v e 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 ，a c q u i r i n gt h ep e r f e c tr e s u l to fa t t r i b u t er e d u c t i o na n d r e d u c i n gt h et i m ec o m p l e x i t y f i r s t l y , t h et h e s i sr e v i e w st h et h e o r i e sa n dm e t h o d so fr o u g hs e ts y s t e m a t i c a l l y , a n da n a l y z e st h ea l g o r i t h m so fa t t r i b u t er e d u c t i o nb a s e do nd i s c e r n i b i l i t ym a t r i x ， a t t r i b u t es i g n i f i c a n c e ，i n f o r m a t i o ne n t r o p y t h et i m ec o m p l e x i t ya n d s p a c ec o m p l e x i t y o ft h e s ea l g o r i t h m sh a v eb e e na n a l y z e dd e t a i l e d l y t h et r a d i t i o n a lr o u g hs e t sm o d e ld i d n tc o m b i n ew i t ht h er e l a t i o nd a t a b a s e s y s t e ma n da l lt h ei n t e n s i v ec o m p u t a t i o n a lo p e r a t i o n sa r ep e r f o r m e di nf l a tf i l e s ， r a t h e rt h a nt a k ea d v a n t a g e so ft h ev e r ye f f i c i e n ts e t - o r i e n t e dd a t a b a s eo p e r a t i o n s i n v i e wo ft h a t ，t h er e s e a r c h e r sp r o p o s e dan e wr o u g hs e t sm o d e lb a s e do nd a t a b a s e s y s t e ma n dr e d e f m e dt h ec o r ea t t r i b u t e sa n dr e d u c t i o nb a s e do nr e l a t i o na l g e b r ai n o r d e rt ot a k ea d v a n t a g e so ft h ev e r ye f f i c i e n ts e t o r i e n t e dd a t a b a s eo p e r a t i o n s b a s e d o nt h i s ，w ep r o p o s et 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 mb a s e do nd a t a b a s e f i n a l l y , w e c o m p a r et h ep r o p o s e da l g o r i t h mw i t ho t h e ra t t r i b u t er e d u c t i o na l g o r i t h mo nt h e r u n t i m eo ft h ea l g o r i t h ma n dt h e a c c u r a c yo fr e d u c t i o n r e s u l ta n dd r a ws o m e c o n c l u s i o n k e yw o r d s ：r o u g hs e t , a t t r i b u t er e d u c t i o n ，d a t a b a s es y s t e m 学位论文独创性声明、学位论文知识产权权属声明 学位论文独创性声明 本人声明，所呈交的学位论文系本人在导师指导下独立完成的研究成果。文中 依法引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法律意义上 已属于他人的任何形式的研究成果，也不包含本人己用于其他学位申请的论文或成 果。 本人如违反上述声明，愿意承担由此引发的一切责任和后果。 论文作者签名： 它埠 1 眺卟钿户 学位论文知识产权权属声明 本人在导师指导下所完成的学位论文及相关的职务作品，知识产权归属学校。 学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权利。本人离校 后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单位仍然为 青岛大学。 本学位论文属于： 保密口，在年解密后适用于本声明。 不保利 ( 请在以上方框内打“4 ) 论文作者签名 导师签名： 5 1 钿今日 ? 多月乡日 雌中 么 易 第一章绪论 1 1 研究的背景和意义 第一章绪论 近十几年，随着科学技术飞速的发展，经济和社会都取得了极大的进步，随 着计算机、网络和通讯等信息技术的高速发展，信息处理在整个社会规模上迅速 产业化，在技术上表现为整个社会对大规模数据操作的产业化。这使得人们所积 累的数据越来越多，并且数据与信息系统中的不确定性更加显著。海量杂乱的数 据背后隐藏着许多重要的信息，人们希望能够对其进行深入分析，以便更好地利 用这些数据所隐藏的信息。目前的数据库系统可以高效地实现数据的录入、查询、 统计等功能，但无法发现数据中存在的关系和规则，无法根据现有的数据预测未 来的发展趋势。缺乏挖掘数据背后隐藏的知识的手段，导致了“数据爆炸但知识 贫乏 的现象。同样，传统的统计技术也面临了极大的挑战。这就急需有新的方 法来处理这些海量般的数据。于是，人们结合统计学、数据库、机器学习等技术， 提出数据挖掘来解决这一难题一1 。 数据挖掘是最近几年来随着数据库和人工智能发展起来的一门新兴的技术。 其处理对象是大量的日常业务数据，目的是为了从这些数据中抽取一些有价值的 知识或信息。它的出现为自动和智能地把海量数据转化为有用的知识提供了有力 的手段。人们把原始数据看作是形成知识的源泉，就像从矿石中采矿一样。原始 数据可以是结构化的，如关系数据库中的数据；也可以是半结构化的，如文本、 图形、图像数据甚至是非结构化的异构数据，如分布在网络上的w e b 数据。发现 知识的方法可以是数学的，也可以是非数学的；可以是演绎的，也可以是归纳的。 发现的知识可以用于信息管理、查询优化、决策支持、过程控制等，还可以用于 数据自身的维护。因此，数据挖掘融合了数据库、人工智能、机器学习、统计学 等多个领域的理论和技术是- - l 广义的交叉学科。 数据预处理是数据挖掘中的重要一环n 叭。实际系统中的数据一般都具有不完 全性、冗余性和模糊性，很少能直接满足数据挖掘算法的要求。另外，海量的实 际数据中无意义的成分很多，严重影响了数据挖掘算法的执行效率，而且由于其 中的噪声干扰还会造成无效的归纳。因此要使挖掘内核更有效地挖掘出知识，就 必须为它提供干净、准确、简洁的数据。 属性约简是数据规约的一种形式，这个过程是从原属性集合中删除不相关和 冗余的属性选出属性子集，以便根据确定的准则使属性空间得到最优的约简田1 。 青岛大学硕士学位论文 图1 1 属性约简步骤 属性约简通常作为数据挖掘的一个预处理步骤n 们，在数据选择和为数据挖掘 作准备的过程中起着重要的作用。而所谓的属性约简，就是在保持知识库分类能 力不变的条件下，删除其中不相关或不重要的属性。通过属性约简，去掉不必要 的属性，可以使知识表示简化，又不丢失基本信息，如果能将冗余属性删除，则 可以减小系统规模，节约成本，并能提高系统潜在知识的清晰度n 引。 近年来，在许多应用领域，如基因项目、文本分类、图像恢复和客户关系管 理等n 羽，数据在实例的数量和属性的数量两方面都有了巨大的增长。如此海量的 数据给许多机器学习算法在可伸缩性和学习性能方面带来了严重的问题。例如， 高维数据( 即包含数以百计或数以千计属性的数据集) 可能包含大量的不相关和 冗余的信息，其中大部分属性与挖掘任务不相关，是冗余的。尽管领域专家可以 挑选出有用的属性，但这可能是一项困难而费时的任务，特别是当数据的行为不 清楚的时候更是如此。遗漏相关属性或留下不相关属性都是有害的，会导致所用 的挖掘算法无所适从。这可能导致发现的模式质量很差。此外，不相关或冗余的 属性增加了数据量，可能会减慢挖掘进程。因此，在面对如此高维数据的今天， 对数据挖掘任务来说，属性选择成为一种必然的选择。可是，在大小和维度两方 面呈现出的巨大的增长趋势都给属性选择算法造成了严峻的挑战。 粗糙集理论是一种刻画不完整性和不确定性的数学工具n 吲，其主要思想就 是在保持分类能力不变的前提下，通过知识约简，导出问题的分类规则。粗糙集 理论能有效地分析和处理不精确、不一致、不完整等各种不完备信息，并从中发 现隐含的知识，揭示潜在的规律。其特点是算法简单，无需提供数据之外的任何 先验信息，可直接从给定问题的描述集合出发，通过不可分辨关系和等价类确定 2 第一章绪论 给定问题的近似域，从而找出该问题的规律。粗糙集理论的应用和其算法的研究， 是近年来知识发现、数据挖掘领域的一个热门话题。在粗糙集研究领域人们己经 开发了许多粗糙集模型，粗糙集理论的一个核心问题就是约简，由于大型数据库 中常常包含许多对发现规则来讲是冗余的、不必要的属性，研究人员发现，如果 能将冗余属性删除，将大大提高系统潜在知识的清晰度，降低知识发现的时间复 杂性，提高发现效率。因此，将粗糙集理论应用于属性约简具有广泛的应用前景 和定的商业价值。 1 2 国内外研究概况 基于粗糙集理论的属性约简是一个非常有研究价值，也是一个非常有挑战性 的研究课题n 3 。近些年来，国内计算机领域的一些专家提出了“数据浓缩 陇1 的 概念。数据浓缩是指在一定条件下去掉数据库中的冗余数据。显然属性约简和数 据浓缩问题实质上研究的内容是相同的，数据浓缩可看作属性约简的通俗名称。 属性或者数据浓缩具有十分重要的研究价值，因此吸引了国内外学者在这方面开 展大量的研究。许多学者也从各个不同方面、采用不同的技术和策略对该课题进 行了研究，根据所要处理的决策表的不同，可分为对相容决策表的属性约简和对 不相容决策表的属性约简啼】，由于粗糙集理论不需要先验知识，粗糙集理论经常 与模糊集等数学工具进行结合瞄1 ，另一方面，基于粗糙集理论的算法也是层出不 穷，比如j e l o n e k 等人提出的j e l o n e k 算法n 刀，h u n 叼算法等。并根据这些算法建 立了一些实验系统，例如美国k a n s a s 大学开发了基于r o u g hs e t 方法的学习系统 l e r s ，加拿大r e g i n a 大学研究开发了k d d r 系统。但是这些系统离实际的商 用系统还有一定的距离，并且也受所采用的约简算法的约束，在效率和准确性方 面还存在着一定的问题。下面主要介绍一些经典的属性约简算法和实验系统。 1 一般属性约简算法 这是一个国内外学者常采用的一个算法n 们，对于决策表中的每一个条件属性 a ；，如果删除该属性口；，使得分类不受影响，则说明属性a ；是相对于决策属性d 不必要的，从决策表中可以将该属性删除，否则不能删除。这是常规的属性约简 算法的简单表述。 上述算法是能够得到决策表的一个属性约简结果，但不一定能够得到一个满 意的属性约简结果。利用这个算法，我们可以采用搜索策略来得到所有可能的属 性约简结果。但是不幸的是，由于这是一个组合爆炸问题，穷尽的搜索所需要的 时间和空间代价都很高，实际计算属性约简的时候，往往采用某种启发式搜索。 2 基于区分矩阵的属性约简算法 3 青岛大学硕士学位论文 基于区分矩阵的属性约简算法1 已经比较成熟，并且在一些实际的约简问题 中得到应用。步骤如下：首先构造矩阵，由差别矩阵产生差别函数，再对差别函 数进行简，得到差别函数的析取范式形式，析取范式中的每一项就是一个约简。 这种法可以求出所有约简，但算法复杂度高，只适合数据量比较小的情况。 3 基于属性重要性的启发式算法n 町 基本思想是：利用属性重要性伫町作为启发式信息，将核属性作为初始属性集， 在这个属性集中每次加入属性重要性最大的属性，直到该集合是一个约简为止， 然后再检查这些属性是否可以删除，若可以则删除之，直到所有的属性都不能删 除为止。 4 基于信息熵的属性约简算法啪2 基本思想是通过增加某属性后系统分类能力的变化来评价属性的重要来对 信息表进行约简。根据信息论中定义的熵与条件熵，以决策属性的熵和决策属性 和条件属性的条件熵进行差值，以差值的大小衡量属性的重要性，差值越大，则 重要性越大。 5 粗糙集理论的实验系统 l e r s 是美国k a n s a s 大学开发的基于r o u g hs e t 的实例学习系统，它是 c o m o n l i s p 在v a x 9 0 0 0 上实现的。l e r s 系统曾用于医学研究、气候预测和环境 保护等。l e r s 的输入采用特定的文件格式。该格式类似于信息表，但采用附加信 息方式来表明条件属性、决策属性、属性的优先级信息。用户可以选择系统提供 的机器学习或知识获取算法。对于机器学习算法，系统对每个概念产生最小判别 描述。对于知识获取算法，系统产生所有能从输入数据中归纳出的规则，每个都 是最小形式，可以用于专家系统等需要知道知识尽量多的场合。 尽管机器学习选项不能产生全部规则，但是它的时间复杂度是多项式的，而 知识获取算法的复杂度是指数的，这样对于大的输入文件是不太实际的。这也是 这个系统的不足之处所在。 k d d - r 是加拿大r e g i n a 大学研制开发的基于可变精度r o u g hs e t 模型的数据 库知识获取系统一3 。该系统是在u n i x 系统下用c 语言实现的，成功应用于医学 数据分析和电信市场的决策分析等。该系统由4 部分组成：数据预处理单元，属 性依赖分析和消除冗余性单元，规则提取单元，决策单元。 数据预处理单元把原始信息表中的数据进行离散化处理。属性依赖分析和消 除冗余属性单元是基于可变精度粗糙集模型的。同原始粗糙集模型相比，可变精 度粗糙集模型在计算集合的下界、边界区和负区域时有一定的灵活性。k d d r 使用粗糙集相应的公式来计算条件属性和决策属性之间的依赖性、相对约简和 核。 4 第一章绪论 1 3 课题主要研究工作 粗糙集理论具有一定的局限性，其中一个一个缺陷是计算的低效率，这限制 了它在现实世界的大数据集的应用。为了寻找约简、核和不必要属性，粗糙集模 型需要根据条件和决策属性的值构造全部的等价类，这一过程十分耗时，因此这 一模型是非常低效和不可行的，对大数据集没有可伸缩性，而这是数据挖掘应用 的一个普遍的要求。 本课题的主要研究任务是借鉴粗糙集理论的相关知识，在对已有的基于粗糙 集理论的约简算法研究的基础上，对其进行改进，将粗糙集与关系数据库系统相 结合，在关系代数的基础上对核属性和约简进行重新定义，从而利用高效的面向 集合的数据库系统操作，以提高属性约简的效率。 1 4 章节安排 论文的结构与章节安排如下： 第一章介绍了论文研究背景和意义，引入了基于粗糙集理论的属性约简算 法，分析了目前国内外研究动态，并简要描述了本文主要的工作以及组织结构。 第二章介绍了粗糙集理论的基本知识和核心概念。包括知识表达系统，不 可分辨关系，集合的上下近似，知识的约简和核，知识的依赖性等。 + 第三章首先介绍了几种经典的基于粗糙集理论的属性约简算法，然后将粗 糙集理论与关系数据库系统相结合埋在关系代数的基础上对核属性和约简进行 了重新的定义，提出了种新的基于数据库系统的属性约简算法。并通过实例证 实了其有效性。 第四章通过实验将本文提出的基于数据库系统的属性约简算法与几种经典 的属性约简算法从约简结果，算法运行时间进行比较，分析比较结果。 第五章结束语，对整个论文工作进行了总结，并对基于粗糙集理论的属性 约简算法进行了展望。 5 第二章粗糙集理论知识 第二章粗糙集理论知识 粗糙集理论是一种新的处理模糊和不确定性知识的数学工具。其主要思想就 是在保持分类能力不变的前提下，通过知识约简，导出问题的决策或分类规则。 下面将阐述粗糙集理论的基础及其思想1 ，作为后面章节的理论准备。 2 1 知识与分类 在信息系统中，人们首先碰到的就是对知识的理解和表达。一般认为，知识 是人类实践经验的总结和提炼，具有抽象和普遍的特性，是属于认识论范畴的概 念。知识直接与真实或抽象世界有关的不同分类模式联系在一起，任何一个物种 都是由一些知识来描述的，利用物种不同的属性知识描述，可以对物种产生不同 的分类。 定义2 1 设u f 2 j 是我们感兴趣的对象组成的有限集合，称为论域。任何 子集xg u 称为u 中的一个概念或范畴。为规范化起见，我们认为空集也是一 个概念。u 中的任何概念簇称为关于u 的抽象知识，简称知识。【，上的一族划 分称为关于u 的一个知识库，它构成了一个特定论域u 的分类。 定义2 2 设尺是u 上的一个等价关系，u 尺表示r 的所有等价类( 或者u 上的分类) 构成的集合，防l 表示元素z u 的尺的等价类。一个知识库就是一 个关系系统k 一缈，尺) ，其中【，为非空有限集，称为论域，r 是【，上的一族等价 关系。 定义2 3 若p r ，且p ，i 囝，则np ( p 中所有等价关系的交集) 也是 一个等价关系，称为p 上的不可区分关系，记为i n d ( p ) ，且有 阢k c p ，= 脚n x k 这样，u i n d 俨) ( 即等价关系i n d ( p ) 的所有等价类) 表示与等价关系族p 相关 的知识，称为k 中关于u 的p 基本知识( p 基本集) 。为简单起见，我们用u p 代替u i n d ( p ) ，i n d ( p ) 的等价类称为知识p 的基本概念或基本范畴。特别的，如 果q j 5 c ，则称q 为k 中关于【，的q 初等知识，q 的等价类为知识r 的q 初等概 7 青岛大学硕士学位论文 念或q 初等范畴。 例1 表2 - 1 给出了一个手机的集合u = ( s l ，s 2 ，s s ) 。 表2 - 1 手机的集合 u颜色( c )外形( s ) 价格( p ) s l 黑直板 低 s 2 蓝滑盖高 s 3 黑翻盖低 s 4 蓝翻盖低 s 5 银白直板低 s 6 银白滑盖低 s 7黑 翻盖低 s s银白 翻盖高 手机的集合可以按颜色分为黑，蓝，银白三类。 黑： s t ，s 3 ，s t ，蓝： s 2 ，s 4 】，银白： s 5 ，s 6 ，s 8 ) 手机的集合按外形可分为直板，滑盖，翻盖三类。 直板： s l ，s 5 ) ，滑盖： s 2 ，s 6 ，翻盖： s 3 ，s 4 ，s 7 ，s s 手机的集合按价格可分为低，高两类。 低： s i ，s 3 ，s 4 ，s s ，s 6 ，s 7 ) ，高： s 2 ，s 8 ) 所以可以得到下面三个等价类： u c = s l ，s 3 ，s 7 ， s 2 ，s 4 】， s 5 ，s 6 ，s 8 u s = s l ，s 5 ， s 2 ，s 6 ， s 3 ，s 4 ，s 7 ，s 8 ) ， u p = “s l ，s 3 ，s 4 ，s 5 ，s 6 ，s 7 ) ， s 2 ，s 8 ) 2 2 不精确范畴，近似与粗糙集 令x u ，r 为u 上的一个等价关系。当x 能表达成某些尺基本范畴的并 时，称x 是只可定义的；否则称x 是足不可定义的。尺的可定义集也称做r 精 确集，而r 不可定义集也称为r 非精确集或r 粗糙集。 对于粗糙集可以近似地定义，我们使用两个精确集，即粗糙集的上近似和下 近似来描述。 定义2 4 给定知识库k - 缈，j r ) ，对于每一个子集x 【，和一个等价关系 r 俐僻) ，定义两个子集： 8 第二章租糙集理论知识 邑z - - u u ，r l y e x ， 融- t 咿e u i r i y f l x - o l 下近似，上近似也可用下面的等式表达； 8 膏忸，lb l c j r r x - x e ulb l n x - o 其中扛k 为包含z 元素的r 等价类。集合6 n ( ：r ) - 瓦r 一星r 称为x 的r 边界 域。p o s ( x ) _ r x 称为x 的r 正域。n e g ( x ) - u i 膏称为x 的凡负域。 显然：p , x 2p o s ( x ) u b n 僻) 星r 是由那些根据知识r 判断肯定属于卫的u 中元素组成的集合：元r 是那 些根据知识r 判断可能属于z 的u 中元素组成的集合；b n 。似) 是那些根据知识 r 既不能判断肯定属于x 又不能判断属于u x 的u 中元素组成的集合； n e g 。伍) 那些根据知识r 判断肯定不属于_ ：r 的，中元素组成的集合。 下面的性质是显而易见的： 定理2 1 ( 1 ) x 为r 的可定义集当且仅当元f = 曼x ( 2 ) x 为r 的粗糙集当且仅当元z 8 x 附2 1 糨糙韭概念) h 虐罔 由圈2 - 1 可以看出图中椭圆形区域为集合x ，椭圆中深颜色区域为z 的下 近似，整个网格状区域为：r 的上近似。租糙集z 可由两个精确集上近似与下近 青岛大学硕士学位论文 似描述。 集合( 范畴) 的不精确性是由于边界域的存在而引起的。集合的边晃域越大， 其精确性近似则越低。为了更准确的表达这一点，我们引入了精度的概念。由等 价关系r 定义的集合x 的近似精度为 “跏矧 其中x f 2 j ，lxl 表示了集合x 的基数。 精度口r 僻) 用来反应我们对于了解集合x 的知识的完全程度。显然，对每 一个r 和x _ u 有0 s 口尺( x ) s1 。当a r ( x ) = 1 时，x 的r 便捷与为空集，集合 x 为r 可定义的；当口尺( x ) 现在从p 中去掉r l 得到 u ( p - r 1 ) ) = u ，r 3 - - - - x l ， ， ) ( 3 ，x 4 ， x 2 ，x 7 ，x 8 ) ， x 6 因为 p o s ( p 删) ( q ) = x l ，x 3 ，x 4 ，x 5 ，x 6 p o s 户( q ) 故r 1 是p 中q 必要的。 从p 中去掉r 2 得到 u ( p - ) ) = u r l ，凡) = “x l ，x 5 ，x 6 ， x 3 ，x 4 ， x 2 ，x s ， x 7 ) ) 由此导出正域 p o s ( p 一) ( q ) = x 1 ，) ( 3 ，x 4 ，) 【5 ，x 6 ，x 7 = p o s 尸( q ) 因此为p 中q 不必要的。 最后省略p 中的黜得到 u ( p 一 r 3 ) = u r 1 ， = x l ，x 3 ，x 4 ，x 5 ) ， x a ，x 8 ) ， x 6 ，x 7 ) 正域为 p o s ( ， r 2 ，) ( q ) = f 2 j p o s ，( q ) 青岛大学硕士学位论文 因此黜为p 中q 必要的。 这样p 的q 核为 r l ，r 3 ) ，它也是p 的q 约简。 2 3 3 知识依赖性 知识依赖性可形式化地定义如下：令k = ( ，u 尺夕是一个知识库，p ，qc r 1 知识q 依赖于知识p ( 记作尸兮q ) 当且仅当i n d 伊夕c _ i n d 夕 2 知识p 与知识q 等价( 记作p - - - q ) 当且仅当p 兮q 且q 专p 3 知识p 与知识q 独立( 记作p q ) 当且当且p 垮q 与q = p 均不成立 当知识q 依赖于知识p 时，我们也说知识q 是由知识p 导出的。 知识的依赖性可能是部分的，这意味着知识q 仅有部分是由知识尸导出的， 部分导出可由知识的正域来定义。 定义2 9 令k = ，删为一知识库，且p ，qc _ r ，当七= ，p ( q ) = i p o s p ( q ) l i 刎时，我们称知识q 是k ( 0 s ks 1 ) 度依赖于知识p 的，记作p 兮k q 。 当k = l 时，我们称q 完全依赖于p ；当0 sk 墨1 时，称q 粗糙( 部分) 依赖 于p ；当k = 0 时，称q 完全独立于p 。如果p 号l q ，也记为p 辛q 。 由上述定义可知，依赖度k 反映了根据知识p 将对象分类到知识q 中的能力， 当p 辛q 时，则由q 导出的分类u q 的正域覆盖了知识库的k x l 0 0 个元素； 另一方面，只有属于分类正域的元素能被唯一的分类，即对象的k x1 0 0 可以通 过知识p 划分入分类u q 的模块中。 2 4 知识表达系统与决策表 知识表达系统n 2 1 在智能数据处理中占有十分重要的地位，知识表达系统的基 本成分是研究对象的集合，而这些对象的知识是通过指定对象的基本特征( 属性) 和它们的特征值( 属性值) 来描述的。 定义2 1 0 一个信息系统s 可表示为：s = ( u ，a n , t ) ，其中，u 为对象的非空有限 集合，称为论域；a 是属性的非空有限集合；v = 【j y a ，v a 是属性a 的值域；f u d a v 是一个信息函数，它为每个对象的每个属性赋予一个信息值，即v ae a ， x e u ，f ( x ，a ) e v 。令p a ，定义属性集p 的不可区分关系i n d ( p ) 为： i n d ( p ) 一 o ，y ) ux ui c a p ，f ( x ，a ) af ( y ，口) ) 。i n d ( p ) 把对象划分为k 个 1 4 第二章粗糙集理论知识 等价类，记为u v f x l ，x 2 ，x k ) 。 知识表达系统的这个定义可以用表格表达来实现。知识的表格表达法可以看 作是_ 种特殊的形式语言，用符号来表达等价关系，这样的数据表称作知识表达 系统或简称为k r s ，有时也称为信息系统属性值表。在知识表达系统数据表中， 列表示属性，行表示对象( 如状态，过程等) ，并且每行表示该对象的一条信息， 数据表可以通过观察、测量得到。容易看出，一个属性对应一个等价关系，一个 表可以看作是定义的一族等价关系。 因为知识库和知识表达系统之间有一对一映射关系，这样，所有涉及知识库 的定义都可以用知识表达系统的定义来描述，因此，知识库中任一等价关系在中 表示为一个属性和用属性值表示的关系的等价类。表中的列可看作某些范畴的名 称，而整个表包含了相应知识库中所有范畴的描述，包含了能从表中数据推导出 的所有可能的规律。所以，知识表达系统是对知识库中有效事实和规律的描述。 而知识约简可以转化为属性约简。 例2 5 表2 2 给出了一个关于某些病人的知识表达系统， 表2 2 病人头痛 肌肉痛体温 e l 是是正常 e 2 是是高 e 3 是是很高 e 4 否是正常 e 5 否否高 e 6否 是很高 u = e l ，e 2 ，e 3 ，& ，e s ，e 6 ) ，a = 头痛，肌肉痛，体温 若取属性集p = 头痛，肌肉痛，x = e 2 ，b ，e 6 ，则有u p = e l ，e 2 ，e 3 ，【e 4 ，e 6 ，【b ) p 基本集为 e l ，e 2 ，e 3 ， ，e 6 ， e 5 ) e x = p o s 。( x ) 一 e 4 ，e 6 ) ，p x 一 e l ，e 2 ，e 3 ，e 4 ，e 6 n e g ，仁) 一u 一脚= e 5 ) ，b n p g ) 一以丛= 帆e 2 ，e 3 属性集 头痛，肌肉痛，体温) 有一个约简 头痛，体温) ， 头痛，体温) 亦是核 决策表口2 1 是一类特殊而重要的知识表达系统。多数决策问题都可以用决策表 的形式表达，这一工具在决策应用中起着重要的作用。 定义2 1 1 设s ：( u ，八v f ) 为一知识表达系统，a = c u d ，c n d = o ，c 称为条件属性集，d 称为决策属性集。具有条件属性和决策属性的知识表达系统 青岛大学硕士学位论文 称为决策表。 例2 6 表2 3 给出了一个关于某些病人的决策表，其中u = e i ，e 2 ，e 8 ， c = 头痛，肌肉痛，体温) ，d = 流感) 表2 3 条件属性决策属性 病人头痛肌肉痛体温流感 e l 是是正常否 e 2是是高是 e 3 是是很高是 e 4 否是正常否 e 5 否否高否 e 6 否是很高是 e 7否否 高是 e s否 是很高 否 令c l = 头痛，c 2 圳【肉痛，c 3 = 体温，则 u c l = e l ，e z ，e 3 ， e 4 ，e s ，e 6 ，e 7 e 8 h u c 2 - - e l ，e 2 ，e 3 ，e 4 ，e 6 ，e 8 ) ， 8 5 ，e 7 ) u c 3 ) = “e l ，e 4 ， e 2 ，e s ，e t ， e 3 ，e 6 ，e 8 ) ) u o ，c 2 = e l ，e 2 ，e 3 ) ， e 4 ，e 6 ，e 8 ， e 5 ，e 7 ) ) u o ，c 3 = e l ， e 2 ) ， e 3 ， ， e 5 ，e t ， e 6 ，e q u c 2 ，c 3 = e l ，e 4 ， e 2 ) ， e 5 ，e 7 ) ， e 3 ，e 6 ，e q u c = e 1 ) ， e 2 ， e 3 ) ， e 4 ) ， e s ，e 7 ， e 6 ，e 8 u d = e 2 ，e 3 ，e 6 ，e 7 ) ， e l ，e 5 ，e 8 ) ) p o s c ( d ) 一 e 1 ) u e 2 u e 3 u & = e l ，e 2 ，e 3 ，e 4 k = ) ，c ( d ) = lp o s cc d ) l i u l = 4 8 = o 5 所以d 部分依赖于( 依赖度为0 5 ) 于c 。又因为 p o s ( c c 1 ) ) ( d ) = e x ，e 2 ，e 4 ) p o s c ( d ) p o s ( c 一 c 2 ) ) p ) i e 1 ，e 2 ，e 3 ，& = p o s c p ) p o s ( c 一p ) i 乃一p o s c ( d ) p o s t c c 2 ，c 1 ) ) p ) i e l ，& 一p o s c p ) 1 6 第二章粗糙集理论知识 p o s ( c c 2 ，c 3 1 ) ( d ) - f 2 j - p o s c ( d ) 所以c 的d 约简( 相对约简) 为c - c 2 ) = c t ，c 3 ，c 的d 核( 相对核) 也为 c l ， c 3 2 5 区分矩阵 区分矩阵( d i s c e r n i b i l i t ym a t r i x ) 是由波兰华沙大学的著名数学家s k o w r o n 汹1 提出来的，是近年来在r o u g hs e t 约简上出现的一个有力工具，利用这个工具， 可以将存在于复杂的信息系统中的全部不可区分关系表达出来。特别是它能很容 易地计算约简和核。 令s = u ，a ，v ，f ) 是一个知识表达系统，l u l = n s 的区分矩阵是一个n n 矩阵，其中任一元素为 a ( x ，y ) = a e a lf ( x ，a ) 一f ( y a ) 因此口( x ，y ) 是区别对象x 和y 的所有属性的集合。 下面我们引人一个布尔函数，称其为区分函数( d i s c e r n i b i l i t yf u n c t i o n ) ，用 表示，对每个属性a e a ，我们指定一个布尔变量a 。若口( x ，y ) = a l ，a 2 ，扯) 囝， 则指定布尔常量1 。( 布尔) 区分函数可定义如下： = 兀口伍，y ) j ，y i e u 刖 区分函数有如下性质：函数的极小析取范式中所有合取式式属性集a 的 所有约简。由上可知，约简是满足能区别由整个属性集区别的所有对象的属性极 小子集。 易知，如果b c _ a 是满足条件b n 口( x ，y ) a ，va ( x ，y ) 彩的极小子 集( 关于包含) ，则b 是a 的一个约简。 核是区分矩阵中所有单个元素组成的集合，即 c o r e ( a ) = a e a i 口o ，y ) 一a 】i ，其中x , y e u 例2 7 考虑表2 4 给出的知识表达系统，表2 4 对应的区分矩阵由表2 5 给出。 表2 4 uabcd 1o1 2 o 21202 310lo 421 0 1 1 7 青岛大学硕士学位论文 区分矩阵是对称矩阵，因此我们仅需计算矩阵的一半元素。 表2 5 o a ，b ，c ，d 0 口，b ，cb ，c ，d 0 口，c ，da , b ，d 口，b ，c ，d 0 口，c ，d b b ，c ，d口，d0 表2 5 对应的区分函数为 a = ( 口vb v c vd ) a0vbvc ) ( 口vc vd ) a ( 口vc vd ) p vcvd ) ( 口vbve ) ab ( 口vbvcvd ) ( 6v c va ) a ( 口vd ) = a bvb d 因此这个知识表达系统有两个约简 a ，b 和 b ，d ) ，核是 b 】 对于决策表s = ( u ，a ，v ，f ) ，a = c ud ，c nd = o ，c 为条件属性集，d 为决 策属性集，我们可用类似的方法计算其相对约简和相对核。 1 8 第三章属性约简算法研究 第三章属性约简算法研究 属性约简是粗糙集理论中的核心内容n 吼悖】。一般情况下，信息系统中的条件 属性并不是同等重要的，有些条件属性是多余的，删除这些多余的条件属性并不 影响原来的系统。属性约简就是在不影响原来的系统的情况下，删除不相关或不 重要的条件属性，使原有的系统得到简化。在不同的系统中，或者在不同的条件 环境下，人们对属性约简的要求和期望是不一致的。如果在某个系统中，存在一 些属性，它们的属性值难以得到，这种情况下所需要的就是获取代价较少的属性 约简。而一般的情况下，属性约简算法希望得到的约简是包含条件属性的数目尽 可能的少m 3 。本文讨论的就是一般的情况。而所说的最优属性约简就是所获得 的约简的条件属性个数最少。 获取属性的约简的方法有很多，但无论什么方法，对于约简算法的目的都是 一样的：算法的有效性比较好，算法的效率比较高，最终获得最佳属性约简。这 个目的有一个前提条件：不损失原有信息系统的信息。最佳可以指多方面的，比 如获得的是含有属性最少的约简，或者得到的约简可以得到最优的决策规则，又 或者获得的约简可以使得数据量约简最大。目前，一般考虑的最佳约简指的是属 性最少的约简。 在粗糙集理论中，最为重要的是决策表和区分矩阵，尤其是区分矩阵，许多 基于粗糙集理论的属性约简算法都以它为基础。区分矩阵起到解释的作用，比较 的直观，其实质是利用逻辑运算中的吸收律和其他演算法则来达到数据约简的目 的。 高效的约简算法是粗糙集理论应用于数据挖掘与知识发现领域的基础，但是 求解所有约简及最小约简问题都是n p h a r d 瞵1 问题，即当数据库中数据量增大时， 该问题的复杂度将以指数增加。因此，寻求快速的约简算法仍是主要的粗糙集理 论研究热点之一u 引。 3 1 一般属性约简算法 一般属性约简算法汹1 主要是利用粗糙集的基本概念，如正域、重要性和核等 来进行计算，本文首先就计算这些基本概念的时间复杂度的问题做出了比较详细 的分析。 1 计算等价关系的复杂度 求等价关系的的最坏时间复杂度为o ( i v l l n f ) 。其中u 为属性集合。r 为对 1 9 青岛大学硕士学位论文 象集合。这是因为在最坏情况下需要扫描对象集合两次，每个对象一次，每个对 象的等价类一次。一个改进的算法是首先按给定属性集对对象排序，然后扫描一 遍即可。这样它的复杂度就降低到o t d u l ) r l l o g l r i ) 。 2 计算上下近似的复杂度 如果己经给定条件属性和决策属性的等价类，只需测试该集合在条件属性下 的等价类是否包含或部分包含在决策属性下的等价类中即可。等价类的个数在最 坏的情况下等刁：l u i ，因此在已经给定的划分下求上下近似的复杂度为o ( i u i ) 。这 样整个复杂度最坏是o ( ( i v l ) l r l l o g l r i ) 。 3 计算属性重要性的复杂度 属性的重要性在于去掉该属性后正区域的变化大小