（检测技术与自动化装置专业论文）基于粗糙集的属性约简算法及其应用研究.pdf

摘要 摘要 题目：基于粗糙集的属性约简算法及其应用研究 学科：控制科学与工程专业：检测技术与自动化装置 硕士研究生姓名：颜艳导师姓名：杨慧中 p a w l a kz 提出的粗糙集( r o u g hs e t s ，简称r s ) 理论是一种全新的刻划不完整性和不 确定性的新的数学工具，它能有效地分析和处理不精确、不完整、不一致等数据，并从 中发现隐含的知识，揭示潜在的规律。目前该理论已得到了国际众多学者的重视，r s 理论已被广泛应用于数据挖掘、机器学习、数据库知识发现、决策支持系统、故障诊断 等领域。 本文着重对粗糙集理论的核心问题之一决策表的属性约简问题进行了研究。属 性约简是在保持知识库的分类或决策能力不变的前提下，删除其中不相关或不重要的知 识。具体研究内容如下： 对于完备的离散型的信息系统，从信息论的角度考虑粗糙集属性约简问题。基于互 信息的概念定义了一种新的属性重要度，并以此属性重要度为启发式信息提出了一种基 于改进的互信息增益率的启发式算法。利用条件熵计算属性间的相关性，并将属性相关 性的定义融入到遗传算法的适值函数中，使得约简结果含有较少的属性，而且降低了它 们的相关性。 经典粗糙集理论不能处理不完备信息系统，在深入学习和研究了现有的几个关于不 完备信息系统的粗糙集扩展模型的基础上，指出它们的不足之处。因为条件属性的重要 性存在差异，通过引入差异度，对不完备信息系统中属性的重要性进行了定义，提出了 一种基于权重联系度的属性约简算法，通过实例仿真说明该算法的优越性。 制约粗糙集理论发展和应用的另一方面是，该理论无法直接用于连续数据。目前处 理连续数据的方法大部分是基于数据离散化，但是这种方法在某种程度会造成信息的损 失。引入样本之间的相似性和改进的属性广义区分度的概念，并定义属性的全局相似性 程度，根据样本之间的全局相似关系直接对属性值为连续数据的决策系统进行属性约 简，避免了数据离散化过程中信息的丢失。最后将其应用于汽轮机组故障诊断系统中， 实验结果表明该方法的有效性。 关键词：粗糙集；信息系统；启发式算法；属性约简：遗传算法；信息论；全局相似关 系；故障诊断 a b s t r a c t a b s t r a c t r o u g hs e t 限s ) t h e o r y , i n t r o d u c e db yp a w l a kz ，i san o v e lm a t h e m a t i c a lt o o lt od e a l 埘t l lv a g u e n e s sa n du n c e r t a i n t y i ti sap o w e r f u lm a t h e m a t i c a lt o o lf o ra n a l y z i n gu n c e r t a i n ， f u z z yk n o w l e d g ea n dc a ne f f e c t i v e l yd e a l 谢t 1 1t h ei m p r e c i s e ，i n c o m p l e t e ，o ru n c e r t a i nd a t a n o wi th a sa t t r a c t e dm u c ha t t e n t i o no fr e s e a r c h e r sa r o u n dt h ew o r d i nr e c e n ty e a r s ，i th a s b e e ns u c c e s s f u l l ya p p l i e dt od a t am i n i n g ，m a c h i n el e a r n i n g ，k n o w l e d g ed i s c o v e r yf r o m d a t a b a s e ，d e c i s i o ns u p p o r ts y s t e m s ，f a u l td i a g n o s i se t c t h i sa r t i c l ee m p h a t i c a l l ys t u d i e so no n eo ft h ei m p o r t a n tp r o b l e mo fr o u g hs e t t h e o r y 也e r e d u c t i o no ft h ed e c i s i o nt a b l e a t t r i b u t er e d u c t i o np r e s e r v e st h e o r i g i n a l m e a n i n ga n dr e d u c e st h ei r r e l e v a n ta n du n i m p o r t a n tk n o w l e d g e t h ed e t a i l sa r es t u d i e da s f o l l o w s ： i nr e g a r dt oac o m p l e t ea n dd i s c r e t ei n f o r m a t i o ns y s t e m ，c o n s i d e ra t t r i b u t er e d u c t i o ni n t h ev i e wo fi n f o r m a t i o nt h e o r y ad e v e l o p e da t t r i b u t ei m p o r t a n c em e a s u r em e t h o di sd e f i n e d b a s e do nt h em u t u a li n f o r m a t i o nb e t w e e ns e l e c t e da t t r i b u t ea n dd e c i s i o na t t r i b u t e ，a n dt h e m e a s u r ei su s e da s t h eh e u r i s t i ci n f o r m a t i o ni nt h ep r o p o s e da l g o r i t h m c o n d i t i o n a l i n f o r m a t i o ne n t r o p yi su s e dt oc o m p u t er e l e v a n c eo fa t t r i b u t e sa n di ti su s e di nf i t n e s s f u n c t i o no fg e n e t i ca l g o r i t h mt oa s s u r er e d u c t i o nh a sf e wa t t r i b u t e sa n dr e l e v a n c eb e t w e e n a t t r i b u t e s t r a d i t i o n a lr o u g hs e tt h e o r yi sg e n e r a l l yi n c a p a b l eo fh a n d l i n gi n c o m p l e t ei n f o r m a t i o n s y s t e m a f t e rs t u d y i n gt h ee x t e n s i o n so fr o u g hs e tm o d e l ，p o i n to u tt h e i rs h o r t a g e s f o r e s s e n t i a l i t yo fa t t r i b u t ee x i s t i n gd i f f e r e n c e ，ad e v e l o p e da t t r i b u t ei m p o r t a n c em e a s u r em e t h o d i sd e f i n e db a s e do nt h ed i f f e r e n c ed e g r e eo fa t t r i b u t e s 。i t sp r o p o s e d 趴a t t r i b u t er e d u c t i o n a l g o r i t h mb a s e do nc o n n e c t i o nd e g r e eo fe s s e n t i a l i t yo fa t t r i b u t e a ne x a m p l es h o w st h a tt h e p r o p o s e da l g o r i t h mi sa ne f f e c t i v em e t h o d a n o t h e rt h er o u g hs e tt h e o r yd e f e c tw h i c hb l o c k si t sd e v e l o p m e n ta n da p p l i c a t i o ni s t h a ti tc a l ln o tb ee m p l o y e do nc o n t i n u o u sv a l u e sd i r e c t l y p r e v i o u s l yd i s c r e t i z a t i o nm e t h o di s a p p l i e db e f o r e h a n di no r d e rt ot r a n s f o r mt h ed a t ai n t od i s c r e t ev a l u e s ，b u tt h i sm a yr e s u l ti n i n f o r m a t i o nl o s s n l en o t i o n so fs i m i l a r i t yb e t w e e no b je c t sa n di m p r o v e dg e n e r a li m p o r t a n t d e g r e eo fa na t t r i b u t ea r ei n t r o d u c e d t h eg l o b a ls i m i l a r i t ym e a s u r eb e t w e e no b j e c t si s d e f i n e db yt h e m ad i r e c tr e d u c t i o nm e t h o di sa p p l i e dt oc o n t i n u o u sa t t r i b u t e su s i n gt o l e r a n c e r e l a t i o nb yt h eg l o b a ls i m i l a r i t yr e l a t i o n t m sm e t h o da v o i d sl o s i n gt h ei n f o r m a t i o ni nt h e d a t a sd i s c r e t i z a t i o np r o g r e s s f i n a l l y , t h em e t h o di sa p p l i e dt of a u l td a t a , a n dt h er e s u l ts h o w s t h a tt h em e t h o di se f f e c t i v e k e y w o r d s ：r o u g hs e t ；i n f o r m a t i o ns y s t e m ；h e u r i s t i ca l g o r i t h m ；a t t r i b u t er e d u c t i o n ；g e n e t i cf l g o f i t h m ； i n f o r m a t i o n t h e o r y ；g e n e t i ca l g o r i t h m ；g l o b a ls i m i l a r i t yr e l a t i o n ；f a u l td i a g n o s i s l i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南 大学或其它教育机构的学位或证书而使用过的材料与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意 签 名： 赢事厶 日 期： 厶国3 乃 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规定： 江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文， 并且本人电子文档的内容和纸质论文的内容相一致 保密的学位论文在解密后也遵守此规定 签名： 导师签名： 础色 日 期： 山口艿_ ；，5 ) - 3 j 玉沪。1 5 第一章绪论 第一章绪论 1 1 引言 随着人类社会的不断发展与进步，计算机与网络信息技术的飞速发展使得各个领域 的数据和信息急剧增加，据估计大概每2 0 个月，地球上的信息量就要翻一倍。这种现 象对人类的影响是双面的：一方面，丰富的资源为人们提供了几乎可以获取一切信息的 可能；另一方面，海量的数据及其质量的良莠不齐，又使人们常常感到无所适从。因此 如何在大量杂乱无章的数据中，挖掘潜在的、有利用价值的信息，给人类的智能信息处 理能力提出了前所未有的挑战。传统的数据库管理系统已不能满足人们对大量数据进行 知识抽取、发现数据间隐藏的依赖关系，从而为决策提供科学支持的需要。在这种状况 下，用数据库管理系统来存储数据，用机器学习的方法来分析数据，挖掘大量数据背后 的知识，这两者的结合促成了数据库中的知识发现的产生。因此，一门新兴的自动信息 提取技术：知识发现和数据挖掘，它的出现为自动和智能地把海量的数据转化成有用的 信息和知识提供了有效的手段。 数据挖掘n 1 ，是指从大量的、不完全的、有噪声的、模糊的、随机的实际数据中， 提取隐含在其中的、人们不知道的、但又是潜在有用的信息和知识的过程。数据挖掘一 般看作是基于数据库的知识发现的一个部分，知识发现主要包括五个步骤：选择数据、 预处理数据、数据约简( 如果需要) 、进行数据挖掘及其提取模式和关系、解释并评价 发现的结构。数据挖掘是知识发现最关键的步骤，也是知识发现技术的难点，所以在通 常情况下可以不加区分的使用二者。在数据挖掘中，一方面要面对海量数据，另一方面 由于客观世界的多样性和复杂性，以及人们对许多事务理解的模糊性，从实际系统采集 到的数据可能包含各种噪声，许多不确定因素和不精确信息存在着。针对不确定信息或 不精确信息，数据挖掘技术包括模糊集理论口咱3 、证据理论“卅和粗糙集理论卅等。 1 2 粗糙集理论的研究意义 粗糙集( r o u g hs e t ，简称r s ) 理论是一种全新的刻划不完整性和不确定性的数学工 具，它能有效地分析和处理不精确、不完整、不一致等数据，并从中发现隐含的知识， 揭示潜在的规律1 。r s 理论是由波兰学者p a w l a kz 在1 9 8 2 年口1 提出的，1 9 9 1 年p a w l a k z 出版了专著1 ，系统全面地阐述了r s 理论，奠定了严密的数学基础。该书与1 9 9 2 年出 版的r s 理论应用专集较好的总结了这一时期r s 理论与实践的研究成果，现已成为学 习和应用r s 理论的重要文献。 r s 理论是建立在分类机制基础上的，将知识理解为对数据的划分。其主要思想是 在保证分类能力不变的前提下，通过知识约简，导出问题的决策或分类规则。粗糙集理 论具有如下的特点旧1 ： 1 )粗糙集是一个强大的数据分析工具。它能表达和处理不完备信息；能在保留 关键信息的前提下对数据进行化简并求得知识的最小表达式；能识别并评估 数据之间的依赖关系，揭示出概念简单的模式；能从经验数据中获取易于证 实的规则知识。 江南大学硕士学位论文 2 )粗糙集方法不需要先验知识。模糊集、d s 证据理论和概率统计方法是处理 不确定信息的常用方法，但这些方法需要一些数据的附加信息或先验知识， 如模糊隶属度函数、基本概率分配和概率分布等，这些信息有时并不容易得 到，r s 分析方法仅利用数据本身提供的信息，无须任何先验知识。 3 )粗糙集与模糊集分别刻画了不完备信息的两个方面3 ：粗糙集以不可分辨关系 为基础，侧重分类，模糊集基于元素对集合隶属程度的不同，强调集合本身 的含混性。虽然粗糙集和模糊集特点不同，但它们之间有着密切的关系，有 很强的互补性n 们。 近年来，r s 理论日益呈现出在人工智能和认知科学中的重要性和优越性，特别是 在机器学习、数据挖掘、决策分析、数据库知识发现、专家系统、决策支持系统、故障 诊断和模式识别等领域，受到越来越多的研究人员的关注n 卜埔1 。 1 3 粗糙集理论的研究现状 当前，对粗糙集理论的研究工作主要集中在以下几个方面。 1 3 1 数据的预处理 粗糙集的数学基础是集合论，难以直接处理连续和不完备的的属性。而现实决策表 中连续和不完备的数据是普遍存在的。 连续数据的离散化是制约粗糙集理论实用化的难点之一。连续数据离散化的根本出 发点是在尽量减少决策表信息损失的前提下，得到简化和浓缩的决策表，以便用粗糙集 理论进行分析，获取决策所需要的知识。根据不同的准则，离散化方法可以分为不同种 类：等间隔和等频率区间法、单规则离散器法h 刀、基于统计检验的离散化方法n 观；基于 熵的离散化方法n 心u 、自适应离散化算法钔、布尔量推理离散算法等。 但是这些方法或多或少的都存在一定的缺陷，还没有一种比较公理化的方法。 在实际问题中，待处理的信息表由于遗失或者获取条件的限制，数据常有某种程度 的不完备，即表中的某些属性值是未知的。对于这种情况，目前主要通过以下途径对信 息表中的空值进行处理：删除法，即删除含有空值的对象，但删除空值可能造成数据浪 费；数据补齐，将不完备信息系统转化为完备信息系统，如m e a nc o m p l e t e r 算法、 c o m b i n a t o r i a lc o m p l e t e r 算法等。 但是这些方法均是对原信息系统的一种人为的猜测，很可能会破坏原信息系统中所 包含的知识。 1 3 2 扩展模型 对p a w l a kz 给出的粗糙集模型进行泛化处理一直是粗糙集理论研究的主要方向， 这个研究方向往往来源于实际应用，要求所建立的模型有很强的应用价值。在p a w l a kz 给出的原始粗糙集模型中，等价关系( 划分) 和概念( 近似集合描述) 是2 个最基本的 要素，因而，推广也主要是从这2 个方向展开的。 r s 认为知识是一种分类的能力，表现为知识是有粒度的，等价关系是r s 的基本概 念。在具体应用时，由于数据的不完备性，使得r s 的使用范围受到限制。为此，很多 学者将等价关系进行了推广，得到了基于容差关系的粗糙集理论、基于相似关系的粗糙 2 第一章绪论 集理论和基于限制容差关系的粗糙集理论等。 对集合和近似空间进行推广是与其他处理不确定、不精确或模糊的知识的理论( 如 概率论、模糊数学、证据理论等) 结合起来进行研究的。传统的r s 理论是用精确集来 定义上下近似集的，在实际应用中，缺乏对噪音数据的适应能力，基于这个考虑，z i a r k o w 提出了一种可变精度粗糙集模型( v a r i a b l ep r e s c i o nr o u g hs e t ，v p r s ) ，k a t z b e r g 进 一步提出了不对称边界的v p r s 模型，使得模型更加一般化。针对知识库中知识的获得 往往具有一定的随机性，张文修等人提出了基于随机集的r s 模型1 ，认为近似逼近好 坏的本质在于包含度的大小。当知识库中的知识模块都是清晰概念，而被描述的概念为 模糊概念时，b a n e r j e e 等人建立了r o u g h 模糊模型来解决此类问题的近似推理，当知识 库中的知识模块也是模糊的，d u b o i s 等人提出了模糊r s 模型。 1 3 3 有效算法的研究 目前有关粗糙集有效算法的研究主要集中在属性约简、规则提取等方面。属性约简 是粗糙集理论中一个重要的研究课题，因为知识库中的知识( 属性) 并不是同等主要的， 甚至其中某些知识是冗余的，特别当数据库数据是随机采集的时候，其冗余性更为普遍， 冗余知识的存在，一方面是对资源的浪费( 需要存储空间) ；另一方面干扰人们作出正确 而简洁的决策。所谓属性约简是在保持知识库的分类或决策能力不变的前提下，删除其 中不相关或不重要的知识。在粗糙集理论里，决策表约简通常不是唯一的，人们总期望 找到最小约简，但这已被证明是一个n p h a r d ，导致n p h a r d 的主要原因是属性的组合 爆炸问题。由于不同的要求，可以选择不同的约简算法，如对于文本分类要求用较少的 属性来表征各个特征，那么可以选择可以得到较少约简结果的算法，而有些情况要求很 准确的表征决策属性，那么可能就需要一些冗余信息来表征各个特征，那么就需要采用 可以得到较高的准确率的算法。到目前为止，人们已提出了若干个属性约简算法，其中 应用较多的是： 基于差别矩阵以及在此基础上的一些改进算法乜5 。矧 基于启发式算法船7 。制 基于遗传算法的粗糙集属性约简算法口u 动态数据约简算法。 约简中的属性个数直接影响到决策规则的编码长度，因此要得到最简洁的决策规则 首先必须得到一个包含最小属性的约简，即最小约简。通过约简操作，降低属性的维数， 总结出适用于决策支持的知识规则，基于粗糙集理论获取的规则精炼且便于存储和使 用。目前基于粗糙集的决策规则获取( 值约简) 的主要方法有： 原始的基于核值的方法 原始的等价类匹配方法 基于布尔推理的最小决策算法 考虑覆盖度的规则方法 确定性规则和概率规则方法。 3 江南大学硕士学位论文 1 3 4 与其他方法的结合 ( 1 ) 与神经网络的结合研究 粗糙集和神经网络是数据挖掘问题中最常用的方法。因为粗糙集理论能够有效的去 除冗余，但对错误判断的决定机制比较简单，由此产生的决策规则不太稳定而且分类精 确性不高；而神经网络有较低的分类错误出错率且稳健性比较好，但当训练样本数据存 在不确定、冗余及噪声时，会出现神经网络训练时间太长，网络规模较大等问题。两者 的结合口删3 ，利用粗糙集理论强大的数据约简功能和神经网络对噪声数据的敏感性进行 数据挖掘，可以提高数据挖掘的效率，即利用粗糙集对数据进行预处理，消除冗余特性， 这样简化神经网络的结构，提高了训练速度。 ( 2 ) 与模糊集的结合研究 粗糙集理论和模糊集理论都是研究信息系统中知识不完善、不精确问题的方法。模 糊集和粗糙集理论在处理不确定性和不精确性问题上推广了经典集合论。虽然有一定的 相容性和相似性，但它们的侧重点不同。从知识的“粒度 的描述上来看，模糊集是通 过对象关于集合的隶属程度来近似描述的；而粗糙集是通过一个集合关于某个可利用的 知识库的一对上、下近似来描述的。模糊集的隶属度函数大多是专家凭经验给出的，往 往带有很强的主观性，目前所见的模糊粗糙集模型口渊3 就是将粗糙集理论和模糊集理论 去弊吸利的结合来描述知识的不确定性和不精确性。 ( 3 ) 与信息的结合研究 信息熵是事件不确定性程度的度量，它能够从确切的数值度量去描述知识，因此， 利用信息论中的熵的原理来评价属性的重要性，从而用于粗糙集的属性的约简中 3 7 删。 粗糙集中知识的粗糙性实质上是其所含信息多少的一种更深刻的描述，可以利用信息熵 来刻画粗糙集中不确定性和模糊性。 1 3 5 应用研究 粗糙集理论对于人工智能和认知科学是十分重要的，自问世以来，无论是在理论或 是应用上都是一种新的、重要的、迅速发展的科学。目前，它主要应用于一下几个领域： ( 1 ) 股票数据分析，文献 4 1 1 给出了用r s 方法分析十年间股票的历史数据，研究股 票价格与经济指数之间的依赖关系，获得预测规则。 ( 2 ) 医疗诊断，文献 4 2 1 提供了应用r s 理论提取头痛的各种病症，并得到了病症的 模型，结果表明，与专家经验相比，该方法是合理有效的。 ( 3 ) 故障诊断，r s 理论在故障诊断上的应用尤为瞩目，利用r s 理论对可能产生故 障的各种情况进行分析约简，得到引起故障的原因。文献 4 3 很好的说明r s 理论在故 障诊断中的应用。 ( 4 ) 人工神经网络，粗糙集与神经网络结合已越来越成为研究的热点，粗糙集特有 的对不精确、不一致数据的表达能力，延伸了神经网络对该类数据的处理能力。粗糙集 与神经网络的结合应用大致分为三类：一类是用粗糙集对数据进行预处理，在不损失源 数据的有用信息的同时删除多余属性，从而减少数据集的大小以及噪声的干扰，同时也 减少了训练时间，提高了效率；第二类是将粗糙集引入神经网络的设计中去，设计一种 4 第一章绪论 粗糙神经元，并将其和传统的神经元结合构造粗糙神经网络；第三类是将粗糙集用于神 经网络的结构设计，目前该类应用一般是将粗糙集分析用于模糊神经网络的构造上。 ( 5 ) 文本分类，随着电子信息量的急剧增长，信息过滤和信息检索越发重要。而对 于目前大量的高位数据进行分类却是一个很困难的事情，当把这些高位数据运用粗糙集 属性约简技术处理之后，消除了数据集中的冗余知识，从而可以得到一个包含少量前提 条件的规则组成的规则库1 。 1 4 论文的研究内容及安排 1 4 1 主要研究内容 鉴于粗糙集理论不需要先验知识、能表达和处理不完备信息、能识别并评估数据间 的依赖关系、建立数据模型等特点，本文主要研究的内容可以概括为一下几个方面： ( 1 ) 粗糙集理论的基本介绍 粗糙集理论是一种新的处理模糊和不确定性知识的数学工具。本文比较全面地介绍 了与之相关的基本概念、粗糙集理论的发展历史、研究现状以及应用背景。 ( 2 ) 离散完备信息系统的属性约简算法 从信息论的角度考虑粗糙集属性约简问题，并给出粗糙集理论和概念的信息表示， 定量刻划了知识的粗糙性，详细讨论了知识的粗糙性与信息的关系，考虑了条件属性对 决策属性的信息熵，并构造了相应的启发式算法，并将遗传算法引入到属性约简的算法 中。 ( 3 ) 不完备信息系统的属性约简算法 经典粗糙集理论不能直接处理不完备决策表，本文主要分析了几个关于不完备信息 系统的粗糙集扩展模型，由于条件属性的重要性存在差异，因此引入了差异度的概念， 用它来计算属性相似的权重，并提出了基于权重联系度的粗糙集模型。 ( 4 ) 连续信息系统的属性约简算法 经典粗糙集理论只能处理离散型的数据，为了避免离散化过程中造成某种程度的信 息损失，根据样本之间的相似关系直接对属性值为连续实数的决策系统进行属性约简。 1 4 2 论文安排 本文围绕粗糙集属性约简算法的原理及其应用展开研究，全文共分六章，各章内容 安排如下： 第一章：绪论 对粗糙集理论进行了较为全面的评述。首先介绍了粗糙集理论的提出背景和特点， 然后详细阐述了粗糙集理论的研究现状，主要集中在数据的预处理、粗糙集的扩展模型、 有效算法和与其他方法的结合等方面。 第二章：经典粗糙集的基本理论 本章详细介绍了经典粗糙集相关的基础理论知识，包括知识与知识库，不精确范畴、 近似与粗糙集，知识的约简与相对约简，以及知识的依赖性及其度量。 第三章：离散完备信息系统的属性约简方法 从信息熵和互信息的概念出发，考虑了条件属性对决策属性的信息熵，定义了一种 5 江南大学硕士学位论文 改进的基于互信息增益率的属性重要性度量方法，并构造了相应的启发式算法。 针对属性约简对目标子集的两个要求，属性子集的各个属性与决策属性的相关性和 属性子集的各个属性之间的相关性，提出了属性相关性的定义，并利用遗传算法作为约 简工具，提出了一种知识相对约简的方法。 第四章：不完备信息系统的属性约简方法 介绍了粗糙集的扩展模型，并指出它们的不足之处，提出了一种基于权重联系度粗 糙集模型。首先用基于容差关系的粗糙集模型粗略地估算出条件属性的重要度，然后利 用权重联系度粗糙集模型约简不完备决策表。 第五章：基于连续数据的知识约简及其在故障诊断中的应用 本章根据样本之间的全局相似关系直接对属性值为连续实数的决策系统进行属性 约简，并将该算法应用到一个故障诊断中。 第六章：总结与展望 对本文介绍的基于粗糙集的属性约简算法进行了总结分析，并提出了今后需要进一 步研究的问题。 6 第二章粗糙集理论基础 第二章粗糙集理论基础 2 1 引言 智能决策中的一个重要概念就是知识，所有的决策都依赖于知识。要解决比较复杂 的问题需要大量的知识以及处理这些知识的机构，然而随着信息社会的发展，知识日益 庞大复杂，这给信息的处理与知识的获取带来了困难。所谓知识获取船羽，就是从海量信 息中发现其中有用规律。粗糙集理论是面向人类认识知识的数学学科，认为知识是人类 对对象进行分类的能力，不可分辨关系是粗糙集理论中的最基本概念。在此基础上，粗 糙集理论引入上近似和下近似等概念来刻划知识的不确定性和模糊性；引入约简和求核 进行知识的约简等计算。本章将介绍知识与知识库的概念，粗糙集的理论知识，以及知 识约简的基础概念和理论汹3 。 2 2 知识和知识库 设u a 是要研究对象组成的有限集合，称为论域。任何子集xsu ，称为u 中的 一个概念或范畴。u 中的任何概念族称为关于u 的抽象知识，简称知识。一个划分f 定 义为：f = x l ，x 2 ，以 ；置cu ，五a ，五n = f 2 j ，对于i 歹，i ，= 1 ，2 ，万； u 五= u 。 l = l u 上的一族划分称为关于u 的一个知识库( k n o w l e d g eb a s e ) 。 设尺是u 上的一个等价关系，u r 表示r 的所有等价类构成的集合， x 】凡表示包含 元素x u 的尺等价类，一个知识库就是一个关系系统k = ( u ，r ) ，其中u 为论域，r 是 u 上一族等价关系。 若p c _ r ，且p ca ，则np 也是一个等价关系，称为p 上的不可区分关系，记为n d ( p ) ， 且有： 【乩d ( p ) = n 【x 】r r e p 这样，u n d ( p ) 表示与等价关系族p 相关的知识，称为k 中关于u 的p 基本知识。 为了方便，我们常用u p 代替u i n d ( p ) ，i n d ( p ) 的等价类称为知识p 的基本概念或 基本范畴。特别地，如果q r ，则称q 为k 中关于u 的q 初等知识，q 的等价类为知 识r 的q 初等概念或q 初等范畴。 同样，我们定义：当k = 缈，r ) 为一个知识库，1 n d ( k ) 定义为k 中所有等价关系 的族，记作1 n d ( k ) = n d ( p ) ia psr 。 定义2 1四元组s = ，a ，y ，f ) 是一个知识表达系统，其中u 表示对象的非空有 限集合，称之为论域；a = cud 是表示属性的非空有限集合，c 称为条件属性集合，d 表示决策属性集合，rc nd = a ；矿= u 圪，圪是属性a 的值域；f 表示u xa 专v 的一 个信息函数，它为每个对象的每个属性赋予一个信息值，即v a a ，x u ，f ( x ，a ) 圪。 若d = a ，则称信息系统为数据表，否则称为决策表。若存在一个x u ，a c ，f ( x ，口) 7 江南大学硕士学位论文 未知( 记做：f ( x ，口) = ) 则称该知识表达系统是不完备的；否则称该知识表达系统是 完备的。 在粗糙集理论中，知识表达系统又称为信息系统( 在本文中知识表达系统和信息系 统是相同的，不作区分) ，可以表示成信息表的形式。信息表的列表示属性，行表示对 象，每个单元格表示对象的属性值。 例2 1 表2 - 1 是一个信息系统s ，其中属性集合a = 口，b ，c ，d ) ，论域u = 而，x 2 ，x 3 ， 颤，而， 。如果令c = 口，b ，c ) ，d = d ) ，那么s = ( u ，cud ，v ，f ) 就是一个决策表。 令条件属性集合r = 口，b ) ，那么r 对应的不可区分关系i n d ( r ) 可以导出等价划分： u r = 而，恐，而 ， 而，) ， 蚝 ) 。 同样，决策属性集合d = d ) ，那么d 所对应的不可区分关系i n d ( d ) 导出的等价划 分为： u d = 而，确，屯) ， 吃，恐，) ) 。 表2 - 1 信息系统s t a b 2 - 1i n f o r m a t i o ns y s t o ms 口bcd 而 11o0 屯 l111 而 1121 以 010o 恐 o110 讫 0o21 2 3 不精确范畴，近似与粗糙集 定义2 2 给定知识库k = ，r ) ，对于每个子集，x 互u 和一个等价关系r k ， 把以下两个集合分别称为x 的r 下近似集( 1 0 w e ra p p r o x i m a t i o n ) 和上近似集( u p p e r a p p r o x i m a t i o n ) ： 堡( = 缸u ：【明r 互柳， 欠( x ) = x u ： x 】旯n r 囝) 。 即当且仅当【x k x ，x 墨( x ) ，当且仅当 x kn x 囝，x r ( x ) 。 星( x ) 是利用知识尺，u 中所有一定能归入x 的元素的集合；足( x ) 是利用知识尺， u 中所有可能归入x 的元素的集合。 定义2 3 把集合p o s r ( x ) = 墨( x ) 称为x 的r 正域；把n e g r ( x ) = u r ( x ) 称为 x 的尺负域；把b n 只( x ) = 尺( x ) 一星( x ) 称为x 的r 边界域。 正域p o s r ( x ) 或x 的下近似是那些对于知识r 能完全确定属于x 的对象的集合； 负域n e g r ( x ) 是那些对于知识r 毫无疑问的不属于x 的对象的集合；它们是属于x 的 补集；边界域是某种意义上论域的不确定域，对于知识尺，属于边界域的对象不能确定 第二章粗糙集理论基础 地划分是属于x 或是属于- , x ( x 的负域) 。x 的上近似是有那些对于知识尺不能排除 它们属于x 的可能性的对象组成的，从形式上看，上近似就是正域和边界域的并集。x 的上近似、下近似、正负域和边界域可以用图l 表示呻1 。图中每个矩形式区域代表一个 等价类，闭合曲线围成的区域表示u 的一个子集x 。 图1 粗糙集概念示意图 “ f i g1s k o t c hm a po fr o u g hs e t sc o n c e p t i o n 例2 2以表2 1 的信息系统s 为例，五= 而，x 4 ，x 5 ，由前面的例2 1 可知，不可 区分关系i n d ( r ) 导出3 个等价类，分别是 x l ，x 2 ，而) ， 两，黾) ， 讫 ，那么五的r 下近似 星( 墨) ，r 上近似豆( 五) ，以及只边界域b n ( x 。) 分别是： 基( 五) = 拖，黾) ， r ( 五) = 而，而，为，x 4 ，而) ， b n ( x 1 ) = 毛，x 2 ，x 3 。 令x u ，尺为u 的一个等价关系。当x 能表达成某些r 的基本范畴的并时，我 们称x 是尺定义的；否则称x 为r 不可定义的。r 可定义集称作天的精确集，而天不 可定义集称为尺的非精确集或粗糙集。 当存在等价关系r i n d ( k ) ，且x 为尺精确集时，集合x u 称为k 中精确集； 当对于任何r i n d ( k ) ，x 都为尺粗糙集，则x 称为k 中的粗糙集。 集合的不精确性是由边界域的存在而引起的，集合的边界域越大，精确性则越低。 为了表达集合的精确性，引入了精度的概念。由等价关系只定义的集合x 的近似精度为： a r ( x ) = i _ r x i i r x l ， 其中，x a ，i 木i 表示集合x 的基数。0 a r ( x ) 1 ，当a r ( x ) = 1 时，x 的只边界域 为空集，集合x 为r 可定义的；当a r ( x ) 。 定义两种量度来描述近似分类的不确定性： 一种是根据尺，吼的近似分类精度，该精度描述当使用知识r 对对象进行分类时， 可能的决策中正确决策的百分比： 口r ( 吼) = i 戤i i 甄i 。 i = li = i 另一种是根据r ，飒的近似分类质量，该质量表示应用知识灭能确切地划入吼类的 对象的百分比： 坩 ， ( 吼) = 丛，i - i 。 i = l， 。 2 4 知识的约筒及相对约筒 知识的约简是粗糙集理论中的核心问题之一，因为在实际应用中，知识库中的知识 并不是同等重要的，甚至有些知识是冗余的。所谓知识约简，就是在保持知识库分类能 力不变的条件下，删除其中不相关或不重要的知识乜钔。 定义2 4 令r 为一族等价关系，r r ，如果l n d ( r ) = 肋( r 一 尺 ) ，则称r 为r 中不必要的，否则称r 为r 中必要的。如果每一个r r 都为r 中必要的，则称r 为独立的；否则称r 为依赖的。 定义2 5 设s = ( u ，a ，v ，f ) 是一个知识表达系统，p a 且q 互尸，如果： 1 ) q 是独立的， 2 ) i n d ( q ) = i n d ( p ) ， 则称q 为尸的一个约简。显然，尸可以有很多种约简。尸中所有必要关系组成的集合称 为尸的核，记作c o r e ( p ) 。 定理2 1 k = ，r ) 是一个知识库，p ，qcr ，当且仅当i n d ( p ) 兰i n d ( q ) 时，知 识尸与知识q 等价。 定义2 6 令尸和q 为u 中的等价关系，q 的尸正域记为p o s e ( q ) ，即p o s p ( q ) = 【j 蹦，q 的尸正域是u 中所有根据分类u p 的信息可以准确地划分到关系q 的等价 x e v o 类中去的对象集合。 定义2 7 令p 和q 为等价关系族，r p ，如果： 尸傩知( p ) ( 肋( q ) ) = p 傩南( p 一懈) ( 肋( q ) ) ， 则称r 为p 中不必要的；否则r 为p 中q 必要的。如果p 中的每个足都为q 必要的，则称p 、 1 0 第二章粗糙集理论基础 为q 独立的( 或p 相对于q 独立) 。为简单起见，记p o s e ( q ) 为p ( p ) ( n d ( q ) ) 。 定义2 8 令s = ，a ，v ，厂) 是一个知识表达系统，p ，q 彳且s p ，s 为p 的 约简当且仅当s 是p 的独立子族且p o s s ( q ) = p o s p ( q ) ，p 的q 约简称为相对约简。 2 5 知识的依赖性及其度量 要进行知识的约简，并从一个给定知识中导出另一知识，必须研究知识库中知识之 间的依赖关系。依赖性可形式化地定义如下： 定义2 9 令s = ( u ，a ，v ，f ) 是一个知识表达系统，p ，q 冬彳。当i n d ( p ) 1 n d ( q ) ，知识q 依赖于知识p ；当pjq 且qjp ，知识p 和q 是等价的，记为p 量q ， 当不存在pjq ，且不存在qjp ，p 和q 是独立的。 知识的依赖性有时候可能是部分的，这意味着知识q 仅有部分是由知识p 导出的， 部分可导出可由知识的正域来定义。 定义2 1 0 令s = ( u ，a ，v ，) 是一个知识表达系统，p ，q 分别为条件属性集和决策 属性集，当k = y e ( q ) = ip o s v ( q ) i | ui 时，我们称知识尸是k 度依赖于知识q 的，记 p j 七q 。其中，表示集合包含的元素个数。通常，k o ，1 】。 当k = 1 时，称q 完全依赖于尸，这表示决策表为一致的或确定的。 当o k 1 时，称q 粗糙( 部分) 依赖于尸。 当k = o 时，称q 完全独立于p 。 由依赖性的定义可知，当pj 七q 时，则由q 导出的分类叫q 的正域覆盖了知识库 的k 1 0 0 个元素；另一方面，只有属于分类正域的元素能被唯一的分类，即对象的 k 枣1 0 0 可以通过知识p 划入分类u q 的模块中，即k 1 0 0 的对象通过知过p 划入 叫q 的初等范畴。因此，k 也称为p 对