（计算机应用技术专业论文）基于粗糙集的数据约简技术及应用研究.pdf

硕士论文基于枢糙集的数据约简技术及应用研究 摘要 智能信息处理是当前信息科学研究中的一个热点问题。随着信息时代的到来，信 息量不断增长，信息模式越来越复杂，因此对信息分析工具的要求也越来越高针对 以上这些问题，波兰华沙理工大学的p a w l a k 教授在2 0 世纪8 0 年代提出了粗糙集 ( r o u g hs e t ) 理论，主要用来研究不完整、不确定知识和数据的表达、学习、归纳 目前该理论已得到了国际众多学者的重视。 本文着重对租糙集的核心问题之决策表的约简进行了研究。决策表的约简 包括决策表属性的约简和属性值的约简两部分。具体研究内容如下： 首先主要研究了属性约简中基于差别矩阵的约简算法和遗传算法，通过实例应 用，对它们的性能进行了分析；另外研究了属性的值约简算法，并通过实例应用对以 核值为基础的值约简算法和一种启发式值约简算法做了比较。 然后深入研究了四种属性约简的启发式算法，m i b a r k 算法，c e b a r k c c 算法， c e b a r k n c 算法和属性频度算法。通过实例应用，对三种基于信息量的m i b a r k ， c e b a r k c c 和c e b a r k n c 约筒算法在算法的起点、终止条件、时间复杂度等几个不同的 方面进行了分析；另外还对属性频度算法进行了改进，并通过实验证明，与原有算法 相比改进算法能够得到决策表的较优约简。 最后主要研究了粗糙集理论在入侵检测中的应用，并运用k d d c u p 离线数据做了 实验仿真。 关键词：粗糙集，差别矩阵，决策表，启发式算法，属性约简 硕士论文基于租糙集的数据约简技术及应用研究 a b s t r a c t a st h ed e v e l o p m e n to ft h ei n f o r m a t i o ns c i e n c e t h es t y l eo ft h ei n f o r m a t i o ni sm o r e a n du i o l ec o m p l i c a t e d , s ow en e e ds o m es u i n g a n u l y l i c a lt 0 0 1 i nt h ee a r l y1 9 8 0 s , p r o f e s s o r p a w l a kz l 竹- o p o s c dt h er o u g hs e tt h e o r y , t h i st h e o r yi sa 1 e wm a t h e m a t i c a lt o o lw h i c h c a nb eu s e dt od e a lw i t hi m p r e c i s e , i n c o m p l e mo ru n c e r t a i nc l a s s i f i e dq u e s t i o n s ，n o wi th a s a t t r a c t e dm u c ha t t e n t i o f t h er e s e a r c h e r sa r o u n dt h ew o r d t h i sa r t i c l ee m p h a s i ss t u d yo nt h ei m p o r t a n tp r o b l e mo fr o u g hs e tt h e o r y - t h e r e d u c t i o no ft h ed e c i s i o nt a b l e ，i tc o n t a i n sa t t r i b m er e d u c t i o na n da t t r i b u t c sv a l u e r e d u c t i o m t h em a i nc o n t e n to f t h i sp a p e rw i l lb ei n t r o d u c e di nd e t a i li nt h ef o l l o w i n gt e x t ： f i r s t , i n l r o d u c et h ea m i b u t er e d u c t i o na l g o r i t h mw h i c hb a s e do 1t h ed i s c e r n i b i l i t y m a t r i xa n dt h eg e n e t i ca l g o r i t h m , a n da n a l y z et h ec a p a b i i r yo ft h e s ea l g o r i t h m sv i at h e a p p l i c a t i o no fi n s t a n c e s i na d d i t i o n , c o m p a r et h ea t t r i b u t e sv a l u er e d u c t i o na l g o r i t h m s w h i c hb a s e d0 1 1c o r e sv a l u ew i t hs o m eh e u r i s t i cv a l u er e d u c t i o na l g o r i t h m t h e nl e s a k l c ht h eh e u r i s t i ca l g o r i t h m sd e e p l y , t h e ya 球m m a r k ，c e b a r k c c c e b a r x n ca n da t t r i b u t ef e q u e n c ya l g o r i t h m a sw ea l lk l o w , m i b a r k ，c e b a r k c c a n dc e b a r k n ca l g o r i t h ma r ca l lb a s e do 1t h ei n f o r m a t i o nm e a s l h 北，b u tt h e yh a v es o m e s h a r pc o n s t r a t si nt h ea l g o r i t h m ss t a r t i n g , e n d i n gc o n d i t i o n ，c o m p l e x i t yo f t i m ea n ds o0 1 1 i nt h i sp a r t ，a m i b u t cf r e q u e n c ya l g o r i t h mi si m p r o v e d , t o o a c c o r d i n gt ot h er e s u l to ft h e e x p e r i m e n t a t i o n ，t h ei m p r o v e da l g o r i t h mc o u l dg a i n e dt h eb e t t e rr e d u c t i o n i nt h el a s tp a r to f t h ep a p e r ，a n a l y z et h ea p p l y i n go f t h er o u g hs e ti nt h ei d s ，a n dd o ae x p e r i m e n t a t i o nw i t h 也ek d d c u p 9 9d a t a k e y w o r d ：r o u g hs e t ，d i s c e r n i b i l i t ym a t r i x ，d e c i s i o nt a b l e ，h e u r i s t i c a 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 声明户明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本 学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发表或 公布过的研究成果，也不包含我为获得任何教育机构的学位或学历而使 用过的材料。与我一同工作的同事对本学位论文做出的贡献均已在论文 中作了明确的说明。 研究生签名：歪3 觚 岫6 年伯门b 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或 上网公布本学位论文的部分或全部内容，可以向有关部门或机构送交并 授权其保存、借阅或上网公布本学位论文的部分或全部内容。对于保密 论文，按保密的有关规定和程序处理。 研究生签名：团题 必。石年厂月抽 硕士论文基于辊糙集的数据约倩技术及应用研究 1 1 概述 第一章绪论 当今社会已经进入了网络信息时代，计算机与网络信息技术的飞速发展使得各个 领域的数据和信息急剧增加，并且由于人类的参与使数据与信息系统中的不确定性更 加显著“1 如何在大量杂乱无章的强干扰数据中挖掘潜在的、有利用价值的信息，给 人类的智能信息处理能力提出了前所未有的挑战。由此产生了人工智能研究的一个新 领域数据挖掘和数据库知识发现，而粗糙集理论对于处理复杂系统在该领域中不 失为一种较为有效的方法闻 粗糙集理论( r o u g hs e t ) 是波兰数学家z p a w l a k 教授在1 9 8 2 年提出的。该理 论是一种处理不确定性、不精确和模糊知识的数学工具跚，它在对不完整数据进行分 析、推理，发现数据间的关系，提取有用特征，简化信息，研究不精确、不确定知识 的表达、学习、归纳方面具有独特的优势。近年来引起了学术界的关注，并已成功地 应用于机器学习、决策分析、模式识别等领域中 在各种应用过程中，如何高效的处理各种应用数据一直是要解决的重要问题。用 粗糙集理论对数据进行处理，与其他的方法相比，概括地讲主要具有以下特点“。： ( 1 ) 不需要先验知识。模糊集和概率统计方法是处理不确定信息的常用方法，但 这些方法需要一些并不容易得到的附加信息或先验信息，如模糊隶属函数和概率分布 等。粗糙集数据分析方法仅仅利用数据本身提供的信息，无须任何先验知识。 ( 2 ) 粗糙集是一个强大的数据分析工具例如：表达和处理不完备信息；在保留 关键信息的前提下对数据进行约简，并求得知识的最小表达式；识别并评估数据之间 的依赖关系。 ( 3 ) 运用租糙集方法从训练数据中获取的规则易于被人们理解和证实。 ( 4 ) 刻画了不完备信息的两个方面：模糊性和不确定性模糊集基于元素对集合 隶属程度的不同，强调集合本身的模糊性；粗糙集以不可区分关系为基础，用一对上 下近似集来描述，并且侧重于分类。粗糙集不能清晰定义，是因为论域中缺乏足够的 钿识。粗糙集和模糊集之间有着密切的关系，具有很强的互补性。 ( 5 ) 粗糙集方法可以较大程度地降低计算时间复杂度。 ( 6 ) 粗糙集理论基于可靠的数学推导，可以与其它计算方法联合使用。例如，粗 睦集理论与神经网络、遗传算法、贝时斯等方法结合。粗糙集理论与其它软计算方法 勺集成也是当前粗糙集发展的一种趋势。 硕士论文摹于耦粘集的数据约简技术及应用研究 1 2 粗糙集的发展概况 1 2 1 粗糙集理论提出的背景 以往讨论的经典逻辑中只有真和假两个值，但事实上有很多模糊的对象存在于这 两个值之间嘲。由此，很多学者致力于含糊概念的研究。早在2 0 世纪初，谓词逻辑 的创始人g f r e g e 就提出了。含糊”一词，并把它归结到边界线，这里的边界线主要 是指在整个论域中存在一些个体既不属于某个子集的分类，也不属于该子集的补集的 分类。1 9 6 5 年，美国计算机与控制论专家l a z a d e h 提出了模糊集理论脚，当时不少 理论计算机科学家和逻辑学家，曾努力通过这一理论来解决g f r e g e 提出的含糊概 念，但是模糊集需要先验知识并且到目前为止还没有很完备的数学理论。 1 9 8 2 年p a w l a k 教授提出了粗糙集，该理论能够把那些无法确认的个体都归于边 界域，并且这种边界域定义为上近似集合与下近似集合的差集瑚而上近似和下近似 都可以通过等价关系给出确定的描述，所以边界域元素的个数可以被计算出来，从而 解决了存在于真和假两个值之间的含糊程度的计算，从而实现了边界域的思想。 1 2 2 粗糙集的发展历程 粗糙集理论为处理具有模糊、不精确或不完全信息的分类问题提供了一种新的工 具。起初，由于这个理论建立在商集基础之上，较为复杂的数学使得这个理论未能引 起人工智能研究者的注意，研究地域也仅局限于波兰等东欧一些国家，当时许多波兰 学者对粗糙集理论及其应用进行了坚持不懈的研究，其中对粗糙集理论的数学性质与 逻辑系统进行了广泛的分析。当时大多数研究成果发表在b u l l e t i no ft h ep o l i s h a c a d e m i co fs c i e n c e s 州”上，同时，他们也开发了一些应用系统，但都处于萌芽阶 段，直至j 1 9 9 0 年前后，由于该理论在数据的决策与分析、模式识别、机器学习与知识 发现等方面的应用，才逐渐引起世界数学界和计算机界的广泛关注。1 9 9 1 年z p a w l a k 教授关于粗糙集的专著的问世和1 9 9 2 年r s l o w i n s k i 主编的关于粗糙集应用及其与相 关方法比较研究的论文集的出版标志着粗糙集理论及其应用的研究进入了活跃时期。 z p a w l a k 所建立的r o u g hs e t 理论有3 个部分“。“，( 1 ) 使用上、下近似表示知识 的不确定性r o u g h h e s s ，把某一论域中无法确认的个体归属于边界区域，而这种边界 区域正是上近似集和下近似集之差。( 2 ) 对数据库的知识约简。( 3 ) 基于r o u g h n e s s 的 推理。z p a w l a k 建立r o u g h n e s s 的本意是为了不确定性推理，但是，近几年的研究表 明，r o u g hs e t 中的不确定性推理可能是这个理论中最不重要的部分，而最重要的是 约简，其次是r o u g h n e s s 的重要性不是为了推理，而是为了表示不同简洁程度知识的 粒度m ，r o u g hs e t 可以作为表示知识粒度的一个显现的测量。由于r o u g hs e t 理论的 2 硕士论文 基于租糙集的数据约俏技术及应用研究 本意已经有所改变，目前r o u g hs e t 理论上最为重要的意义是将机器学习问题定义在 等价关系对空间的划分上，即商集理论上，并由此系统地提出独立约简的概念。 1 9 9 1 年，s k o w r o n 提出了差别矩阵原理“，这也是迄今为止r o u g hs e t 理论中最 为重要的研究成果。这个原理与洪家荣教授在1 9 8 6 年提出的“扩张矩阵原理”十分相 似。它的基本操作非常简单，以致大多数计算机工程师都可以理解，就是对所有样本 的所有属性两两比较，并收集属性值不同的属性，构成差别元素；约简则是将所有带 有约简属性的差别元素从差别矩阵中删除，直到差别矩阵为空差别矩阵原理是目前 为止进行数据库知识约简的最基本最重要的原理，几乎所有的属性约简算法都以它为 基础嘲。如属性频度算法、属性重要度算法等。 1 2 3 粗糙集的研究对象 粗糙集的研究对象是由一个多值属性集合描述的一个对象集合“”，比如由温度， 风力、湿度等属性描述的一个天气情况集合对于每个属性都有其对应的取值范围， 而对象、属性和属性值就构成了一个决策问题的基本要素。通常情况下，把这种表达 形式看作是一个二维表，表的行对应论域中的一个对象，列对应于对象的属性，并且 各行中都包含了表示相应对象信息的取值，还有各个对象的类别成员的信息。通常情 况下关于对象的可得到的信息不一定足以划分其成员类型，也就是说这种不精确性导 致了对象的不可分辨性。给定对象间的一个等价关系，即导致由等价类构成的近似空 间的不分明关系，粗糙集就用不分明对象类形成的上近似和下近似来描述。 这些近似分别对应了确定属于给定类的最大的对象集合和可能属于给定类的最 小的对象集合，并且这两个集合的差就是一个边界集合，它包含了所有不能确定是 否属于给定类的对象粗糙集方法可以解决信息系统的分类问题，通过除去冗余信息 得到的决策规则能够很好地近似分类，而且它还可以表达属性之间依赖关系 1 2 4 粗糙集的应用现状 粗糙集理论对于人工智能和认知科学是十分重要的，自问世以来，无论是在理 论或是应用上都是一种新的、重要的、迅速发展的科学。在目前它主要应用于以下几 个领域； ( 1 ) 医疗诊断1 医疗诊断是基于粗糙集理论进行知识获取研究的一个重要实 践领域。 ( 2 ) 股票数据分析“。应用粗糙集方法可以分析股票的数据，从而可以研究股 票价格与经济指数之间的依赖关系，获得预测规则。 ( 3 ) 地震预报运用粗糙集理论研究地震前的地质和气象数据与里氏地震级 预士论文基于扭糙集的数据约简技术及应用研究 剐的依赖关系 ( 4 ) 数据挖掘从数据库中获取知识，是当前人工智能和数据库技术交叉学 科的研究热点之一- 目前粗糙集方法是知识发现的一种重要的方法，由此获取的知识 更精练且便于存储和使用。 ( 5 ) 客户行为分析“”电子商务在国内外已经逐渐开展起来，分析客户的特点是 最大限度提高商业活动的效率和成功机会、实现最大商业价值、降低商业成本的重要 因素，而粗糙集在这方面的应用使得商家可以更好的分析市场的潜在客户 ( 6 ) 文本分类町随着电子信息量的急剧增长，信息过滤和信息检索越发重要。 而对于目前大量的高位数据进行分类却是一个很困难的事情，当把这些高位数据运用 粗糙集属性约简技术处理之后，消除了数据集中的冗余知识，从而可以得到一个包含 少量前提条件的规则组成的规则库。这种方法既可以降低关键词集合的维数又可以保 持关键词集合中的信息。 ( 7 ) 入侵检测“”现在将粗糙集理论技术应用到入侵检测中，可以自动地从 大量的数据信息中发现新的安全规则，从而可以建立一个智能化的入侵检测系统。并 且利用粗糙集的属性约简以及值约简算法可以提高挖掘的效率，获得简洁高效的规 则。 1 。3 本文的主要工作 本文主要研究的内容可以概括为以下几个方面： 1 1 ) 粗糙集的理论知识 粗糙集理论是一种新的处理模糊和不确定性知识的数学工具。本文比较全面地介 绍了与之相关的各种子问题，比如知识与知识库，知识的约简，知识表达系统和决策 表等 ( 2 ) 决策表的约简 决策表的约简主要包括两个步骤：决策表的属性约简和决策表属性值的约简。在 这部分内容中主要研究了基于差别矩阵的约简算法，遗传算法，以及启发式的值约简 算法等，并对其中的各种算法做了实例分析和性能比较。 ( 3 ) 属性约简的启发式算法 在本文中主要研究分析了几种基于属性重要度的属性约简算法，并对其中的属性 频度算法进行了改进，改进的思路就是把同时达到最大频度的属性进行再次分析，将 其中分类能力强的属性添加到约简集合中，这样就可以得到决策表的较优约简，通过 实验分析证明了该算法的有效性。 ( 4 ) 粗糙集理论在入侵检测中的应用 在目前，随着信息社会的快速发展，网络的稳定与安全受到了多方面的影响，网 4 硕士论文基于粗糙集的数据约简技术及应用研究 络数据量越来越大，也越来也复杂，随之而来就是要从这些大量复杂的网络数据中获 得有用的知识也越发的困难。将粗糙集理论应用到入侵检测，可以实现自动的获得简 洁有效的安全规则，实现了准确性高且智能化的入侵检测系统。 1 4 本文的结构 本文就基于租糙集的数据约简技术做了一些相关的研究和探讨仔细分析了基于 差别矩阵的属性约简算法、遗传算法和属性约简中的启发式算法，并对基于属性频度 的约简算法做了改进。另外结合了相关的实例进行分析测试，取得了较满意的结果。 本论文的章节安排如下： 第一章是绪论。主要介绍了本文的主要内容，粗糙集的特点以及粗糙集的发展概 况等。 第二章是粗糙集基础理论。在本章中详细介绍了粗糙集相关的基础理论知识，包 括知识与知识库，不精确范畴，近似与粗集，知识的约简和依赖性，知识表达系统和 决策表。 第三章是决策表的约简分别介绍了决策表的属性约简和决策表属性值的约简， 并对各算法做了实例应用和性能分析 第四章是属性约简的启发式算法。介绍了算法的来源和几种不同的启发式算法， 并进行了性能分析对属性额度算法做出了改进，针对那些频度一样的属性再用它们 的分类能力来判断该把哪个属性加入到决策表的属性约简集合中，经过实验分析证明 了改进算法能够得到较优的约简。 第五章是粗糙集理论在入侵检测中的应用。在本章首先简单介绍了入侵检测系统 的概念以及结构，然后分析了粗糙集理论在入侵检测中的应用。用k d d c u p 9 9 离线数 据做实验分析，经过数据预处理以及约简并获得了决策规则。 第六章是总结与展望。对本文介绍的内容傲了总结分析。 预士论文基于租糙集的数据约简技术及应用研究 2 1 引言 第二章粗糙集基础理论 人工智能研究中的一个重要概念是智能需要知识“”。要解决比较复杂的问题需要 大量的知识以及处理这些知识的机构，然而随着信息社会的发展，知识日益庞大复杂， 这给信息的处理与知识的获取带来了困难，本文所讨论的粗糙集理论对这些问题的处 理给出了有效的解决方式。 知识表达是智能信息系统的关键，所谓知识获取跚，就是从海量信息中发现其中 的有用规律，即将知识从原始的表达方式转换成一种人或计算机等能够识别的方式。 基于粗糙集理论的知识发现是借助于信息表这样一种有效的数据表知识表达方式，通 过数据的预处理以及知识约简，从而获得有效的人类或计算机容易处理的规则洲。本 章将首先介绍了知识与知识库的概念以及粗糙集的理论知识，而后对知识约简的基础 概念和理论做了详细介绍。 2 2 知识与知识库 知识是人类通过实践认识客观世界的产物，它是信息经过加工处理、解释、挑选 和改造而形成的捌一般认为，知识是人类经验的总结和提炼，具有抽象和普遍的 特性。在信息系统中首先碰到的就是对知识的理解和表达，从认知科学的观点来理解 的话可以认为知识源于人类的分类能力。 在粗糙集理论中，知识被认为是一种将抽象或现实的对象进行分类的能力瞳i 】 对象指客观世界中存在的任何事物，包括状态、过程、时刻等抽象概念知识直接与 真实或抽象世界有关的不同分类模式联系在一起，这里称之为论述的论域。知识是由 我们感兴趣的领域的分类模式组成，它提供关于现实的明显事实，同时也具有明显事 实推导出模糊事实的推理能力，若要研究的对象中的两个元素具有相同的信息，则它 们是不可区分的，即根据已有的信息不能够将其划分开，这就是一种等价关系旧。 若u o 是要研究对象的有限集合，称其为论域，任何子集x c _ u ，称为u 中的一 个概念或范畴，为规范化起见我们认为空集也是一个概念。u 中的任何概念族称为关 于u 的抽象知识，简称知识。在粗糙集理论中我们主要关注在论域u 上能形成划分的 那些知识，一个划分可定义为”f = x l 2 ) 【3 ，。) ( i ，x ，u ，x 。n x j o ，对于 i j ，i ，j = 1 ，2 ，r l ，u ) ( i = u 。而u 上的一族划分就称为关于u 的一个知识库m 。 融 设u 是一个论域，r 是u 上的一个等价关系，u r 表示u 上由r 导出的所有等价 6 硕士论文 基于粗糙集的数据约简技术及应用研究 类。f x l 表示包含元素x 的r 等价类，xe u 一个知识库就是一个关系系统k - ( u ， r ) ，其中u 是论域，r 是u 上的一个等价关系族若p c r ，且p o ，则n p ( p 的所 有等价关系的交) 也是一个等价关系，记作i n d ( p ) ，而u i 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 初等概念。 定义2 1 硼设k _ ( u ，p ) 和m _ ( u ，q ) 是两个知识库，若i n d ( p ) = i n d ( q ) ，则 称k 和m ( 或q 和p ) 是等价的，记作k - - m ( 或者p 善q ) 。 定义2 1 意味着可以用不同的属性集对对象进行描述，以表达关于论域的完全相 同的事实。另外对于两个知识库k _ ( u ，p ) 和忙( u ，q ) ，当i n d ( p ) c i n d ( q ) 时， 称知识库p 比知识库q 更精细，或者说q 比p 更粗糙。当p 比q 更精细时，我们称p 为q 的特化，q 为p 的推广。由以上可知，推广是将某些范畴组合在一起，而特化则 是将范畴分割成更小的单元。 2 3 粗糙集基本概念 2 3 1 不精确范畴、近似与粗集 假设一个知识库或信息系统( 下文统称知识库) k = ( u ，r ) ，其中u 为一组对象组成 的非空有限集合，r 为u 上一组等价关系。任何一个r r ，r 为u 上的一个等价关系，那 么a = ( u ，r ) 称为一个近似空间，r 为一个不可区分关系，记为i n d ( r ) u i n d ( r ) 的等 价类称为基本范畴，i n d ( k ) = i n d ( r ) fa r r j 设x 为u 的一个对象子集，x 称为u 中的一个概念或者范畴。如果r e i n d ( k ) ，x 的下近似墨x ( 1 0 , e ra p p r o x i m a t i o n ) 和上 近似x ( u p p e ra p p r o x i m a t i o n ) 分别定义为瑚： 墨x = u y u rly 三x ( 2 1 ) 矗x = u y u riy n x o ( 2 2 ) 墨x 由根据知识r 判断肯定属于x 的u 中元素组成；夏x 由根据知识r 判断可能属于x 的u 中元素组成。p o s r = 基x 表示x 的r 正域，n e g r ( 为= u _ 豆x 表示x 的r 负域，另外 b n 。( ) ( ) = 豆x 一星x 表示x 的r 边界域。x 的上近似、下近似、正负域和边界域可以用图 2 3 1 表示。图中每个矩形式区域代表一个等价类，圆形表示u 的一个子集x 。 其中的黑色区域就是子集x 的下近似星x ，灰色区域是子集x 的上近似豆x ，白色区 域是子集x 的负域。 7 硕士论文基于租糙集的数据约简技术及应用研究 图2 3 1 租糙集示例图 当x 能表达成某些r 基本范畴的并时，我们称x 是r 可定义的；否则称x 为r 不可定义 的。r 可定义集称作r 的精确集，而r 不可定义集称为r 的非精确集或粗糙集( r o u g h s e t ) 当存在等价关系r i n d ( k ) 且x 为r 精确集时，集合x u 称为k 中精确集；当对于 任何r ei n d ( k ) ，x 都为r 粗糙集，则x 称为k 中的粗糙集 定理2 1 ” ( 1 ) x 为r 可定义集当且仅当星x - 豆x ( 2 ) x 为r 粗糙集当且仅当星x 豆x 由此，我们也可以将墨x 描述为x 中的最大可定义集，而豆x 则描述为含有x 的最小 可定义集。这样，范畴就是可以用已知知识表达的信息项，一般情况下，在一个给定 的知识库中，并不是所有的对象子集都可以构成范畴的，因此，这样的子集可以看作 为粗范畴，它只能用知识通过两个精确范畴，即上、下近似集租略地定义 2 3 2 粗糙集的数字特征和拓扑特征 在粗糙集理论中，范畴( 集合) 的不精确性是由于边界域的存在而引起的，集合 的边界域越大，则其精确性越低，为了表达集合的精确性，引入了精度的概念。由等 价关系r 定义的集合x 的近似精度m 为： 叫署 ( 2 3 ) 其中x a ，i x i 表示集合x 的基数。我们用精度鲰( ) ( ) 来反映我们对集合x 的知识了解 的完全程度，很显然，对于任何一个r f f x c _ u 都有o ( x ) 1 。另外由粗糙集的定 义可知：当a r r ( x ) = l 时，x 的r 边界域为空集，集合x 为r 可定义的；当吒( x ) l 时， 集合x 有非空r 边界域，集合x 为r 不可定义的。 8 硕士论文基于粗糙集的数据约简技术及应用研究 另外，除了用数值( 近似程度的精度) 来表示粗糙集的特征外，也可根据上、下 近似的定义来表达粗糙集的另外一个有用的特征，即拓扑特征下面定义的四种定义 描述了粗糙集的拓扑特征“一： ( 1 ) 星x 彩，且豆x u ，则称x 为r 粗糙可定义 ( 2 ) 墨x = 0 ，且夏x u ，则称x 为r 内不可定义 ( 3 ) 星x 彩，且豆x = u ，则称x 为r 外不可定义 ( 4 ) 基x = 彩，且豆x = u ，则称x 为r 全不可定义 这个划分也可以这么直观的定义： 如果集合x 为r 粗糙可定义，则可以确定u 中某些元素属于域一x 。 如果集合x 为r 内不可定义，则可以确定u 中某些元素肯定属于一x ，而不能确定任 何一个元素属于x 。 如果集合x 为r 外不可定义，则可以确定u 中的某些元素属于x ，而不能确定任一元 素属于一x 。 如果集合x 为r 全不可定义，则不能确定u 中的任一元素属于x 或一x 。 至此讨论了两种描述粗糙集特征的方法，其一是用近似精度来表示粗糙集的数字 特征：其二是用粗糙集的分类表示粗糙集的拓扑特征。粗糙集的数字特征只是表示了 集合边界域的大小，丽拓扑特征提供的是边界域的结构，因此在实际的应用当中要把 两种信息结合起来，既要考虑精度，又要考虑到集合的拓扑结构。 此外，粗糙集的数字特征和拓扑特征之间存在着一种关系，当集合为内不可定义 或全不可定义时，其精度为0 ；若集合为外不可定义或全部可定义时，则其补集的精 度为0 2 4 知识的约简和依赖性 2 4 1 知识的约简和核 知识的约简是租糙集理论中的核心问题之一，我们都知道，知识库中的知识并不 是同等重要的，甚至其中某些知识是冗余的，所以所谓的约简，就是在保持知识库分 类能力不变的情况下，删除其中不相关或不重要的知识“。 知识约简中两个重要的概念就是约简( r e d u c t ) 和核( c o r e ) 。在介绍这两个概 念之前，我们首先要了解以下定义： 令r 为一族等价关系，r a l l ，如果i n d ( a ) = i n d ( r - r ) ，则称r 为r 中不必要的，否 则称r 为r 中必要的。 如果每一个r r 都为r 中必要的，就称r 为独立的；否则称r 为依赖的。 定理2 1 嘲如果r 是独立的，p c _ r ，则p 也是独立的。 9 硕士论文基于租糙集的致据约倚技末及应用研究 证： 这里我们采用反证法，假设p _ c r 且p 是依赖的，则存在s o p ，使得 i n d ( s ) - - i n d ( p ) 由此可知：i n d ( s u ( r p ) ) = i n d ( r ) ，s u ( r p ) r - r 因此r 是依赖的，与已知条件矛盾，所以定理得证。 设q p ，如果q 是独立的，且i n d ( q ) - - i u d ( p ) ，则称q 为p 的一仑约简，显然可知p 可以有很多个约简，p 中所有必要关系组成的集合称为p 的核，记作为：c o r e ( p ) 。 定理2 2 嘲c o r e ( p ) - - n r e d ( p ) ，其中r 印( p ) 表示p 的所有约简。 该定理描述了核与约简的关系，它的证明可以参考文献 3 由以上可知核的概念的用处可以从两个方面考虑，首先它可以作为所有约简的计 算基础，因为核包含在所有的约简之中，并且计算可以直接进行；其次可解释为在知 识约简时它是不能消去的知识特征集合。 2 4 2 知识的相对约简和相对核 在平时的应用当中，一个分类相对于另一个分类的关系是非常重要的，因此在这 里将介绍与此相关的两个概念：相对约简( r e l a t i v er e d u c t ) 和相对核( r e l a t i v e c o r e ) 然而在了解这两个概念之前首先应该搞清楚的是一个分类相对于另一个分类 的正域脚： 令p 和q 为u 中的等价关系，q 的p 正域记为p o s p ( q ) ，即 p o s p ( q ) = u 里o o ( 2 4 ) ( x u q ) 对于u p 的分类，u q 的正域是论域中所有通过用分类u p 表达的知识能够确定 地划入u q 类的对象的集合。 p 和q 为u 中的等价关系族，当p o s 一( p ) 汹d ( q ) ) 。p o s _ - p ，j ) ( m d ( q ) ) 时，称r e p 为p 中q 可省略的，否则r 为p 中q 不可省略的 当p 中每一个r 都是q 不可省略的，则称p 为q 独立的( 或者说p 是对于q 独立 的) 。当s 为p 的q 独立族，p o s s ( q ) = p o s p ( q ) ，则族s c p 称为p 的q 简化。 p 中所有q 不可省略原始关系族称为p 的q 核，记为c o r e q ( p ) 定理2 3 加c o r e q ( p ) = n r e d q ( p ) ，其中r e d q ( p ) 是所有p 的q 约简构成的 集合。 2 4 3 知识的依赖性 若要进行知识的简化，并从一给定知识中导出另一知识，就必须研究数据库中函 数之间的依赖性关系。 1 0 硕士论文 基于粗糙集的数据约简技术及应用研究 知识的依赖性可形式化的定义如下“】： 令k _ ( u ，r ) 为一知识库，且p ，q 量r 。 ( 1 ) 当i n d ( p ) i n d ( q ) ，知识q 依赖于知识p ，记作p j q ； ( 2 ) 当p j q 且q 等p ，知识q 和知识p 是等价的，记作p - - o ； ( 3 ) 当p j q 且q j p 均不成立时，称知识q 和知识p 是独立的 定理2 4 【l 下列条件是等价的： ( 1 ) p j q ( 2 ) i n d ( p u q ) = i n d ( p ) ( 3 ) p o $ p ( q ) = u ( 4 ) 对于所有x e u q ，有p x = x ，其6 e p _ x 表示砌口 该定理表明了如果知识q 依赖于知识p ，则在知识库中知识q 是多余的，在此种 情况下，知识p uq 与知识p 提供同样的对象特征。 有时候知识的依赖性可能是部分的，这意味着知识q 仅由部分是由知识p 导出的， 部分可导性可以用知识的正域来定义。 令k = ( u ，r ) 为一知识库，且p ，q r ，当k = 唯( q ) = l p o s p ( q ) i i o i 时，就称知识 q 是七( 0 七s 1 ) 度依赖于知识p 的，记作p 。q 。 当七- - i 时，q 完全依赖于p ；当0 七 1 时q 粗糙( 部分) 依赖于p ；当七= 0 时q 完全独立于p 并且p j q 简记为p q 。 2 5 知识表达系统和决策表 2 5 1 知识表达系统 知识表达在智能数据处理中占有十分重要的地位，为了处理智能数据，需要知识 的符号表达，一个知识表达系统嗍可以表示为一个四元组s ：( u ，a ，v ，) ，其中u 是对象的非空有限集合，称为论域；a 是属性的非空有限集合；v 三uv i ，v 是属性 t a 的值域；，u x a v 是一个信息函数，它为每个对象的每个属性赋予一个信息值， 即v a a ，x u ，f ( 五口) v 口 知识表达系统也称为信息系统，通常用s = ( u ，a ) 来代替s = ( u ，a ，v ，) 。 知识表达系统的数据可以用关系表的形式表示，关系表的行对应要研究的一个对 象，列对应对象的一个属性，对象的信息是通过各个属性值来表达的，另外关系表中 的一个属性对应一个等价关系，整个关系表可以看作是定义的一族等价关系，即一个 硕士论文 基于粗糙集的数据约简技术及应用研究 知识库，这样前面讨论的知识的约简就可以转化为关系表中属性的约简姗 2 5 2 决策表 决策表是一类特殊而重要的知识表达系统，它的定义如下： 设s ( u ，a ，v ，) 是一知识表达系统，a = c u d ，c n d a ，c 称为条件属 性集，d 称为决策属性集。具有条件属性和决策属性的知识表达系统称为决策表。 在决策表中，各个属性的重要性是不一样的，为了找出某些属性或者属性集的重 要性，一般采用的方法是从表中去掉一些属性，然后再分析没有这些属性后分类有什 么变化，若去掉属性后分类变化较大，则证明该属性的强度大，也即重要性高；反之 则说明该属性的重要性低。 令c 和d 分别为条件属性集和决策属性集，属性子集c c 关于d 的重要性定义 为叫： = c d ( c 9 = y c ) 一托c ( d ) 特殊情况下当c = 口 时，属性a c 关于d 的重要性为： o b ( 8 ) = r c f d ) - r c m ( d ) 另外在决策表中最重要的是决策规则的产生设s = ( u ， ，v ，f ) 是一知识表 达系统，a = c u d ，c n d 乃，c 称为条件属性集，d 称为决策属性集。令x 。和y 1 分 别代表u c 与u d 中的各个等价类，d e s ( x i ) 表示对等价类x ，的描述，即等价类x 。对 于各条件属性值的特定取值；d e s ( 一) 表示对等价类x 的描述，即等价类x 对于各决 策属性值的特定取值。 决策规则可以这样表示：d e s ( x 。) 一d 髓( 誓) ，y , n x , g ，规则的确定因子 a ( x 。，i ) = i n k x 。f ，o ( x i ，一) 5 l 当( x l ，y ) - - 1 时，；l 是确定的；当o 4 x 。，x ) 1 时，气是不确定的 另外，当两个决策规则的所有条件属性值都一样，且对应的决策属性值也一样时， 称这两个决策规则是相容的，否则是不相容的；对于决策衷而言，只有当决策表的所 有决策规则都是相容的时候，它本身才是相容的，否则，决策表就是不相容的。 2 6 本章小结 本章的主要内容是粗糙集的基础理论知识。首先介绍了知识与知识库以及粗糙 集理论的一些基础概念，然后主要阐述了知识的约简、知识表达系统与决策表等内容。 1 2 硕士论文基于租糙集的数据约简技术及应用研究 第三章决策表的约简 在制定决策之前首先要明确的问题有是否需要全部的条件属性以及能否进行决 策表的约简。因为约简后的决策表具有与约简前的决策表相同的功能，但是约简后的 决策表具有更少的条件属性。目前决策表的约简在工程应用中是相当重要的，在约简 后的决策表中，同样的决策可以通过基于更少量的条件，使我们通过一些简单的手段 就能够获得同样要求的结果 3 1 决策表的最小化 基于粗糙集理论的知识获取，主要就是通过对原始决策表的约简，在保持决策表 的条件属性和决策属性的依赖关系不变的条件下，消除决策表的冗余知识，从而达到 对决策表的约简蜘约简后的决策表是由一系列的决策规则组成的，通过这些规则可 以比较明了的描述所要研究对象的特征。 决策表的最小化就是一般情况下所讲的对决策表的约简，整个约简过程主要包 括以下两个步骤： ( 1 ) 属性约简：即从原来的决策表中删除冗余的属性，得到原知识表达系统的基 本规则； ( 2 ) 属性值约简：即以属性约简后得到的决策表为基础，对每条决策规则的约简， 删除决策规则中冗余的属性值，得到决策表的最小规则集 在步骤( 1 ) 中还包含了对重复行的约简因为与知识表达系统的一般表达相比， 这里的行不表示对任何实际对象的描述，因此重复行表示的是同样的决策，所以可以 把它消去。 3 2 属性约简算法的研究与分析 3 2 1 属性约简概述 一个决策表就是一个决策信息系统，表中包含了大量样本信息，其中的一个样本 就代表了一条决策规则，所有的规则就组成了一个决策规则集合，但是在实际的应用 中，这种规则集合是没有用的，因为其中的一个基本规则缺乏适应性，只是机械的记 录了一个样本本身的信息，不能适应其他的情况，而约简后决策表的一条记录就代表 了具有相同规律的样本，这样的规则就具备了很强的适应性。 在数据分析中，原始的决策表中的属性并不是同等重要的，那些不必要的关系在 知识库中是多余的，这些冗余属性的存在不仅仅是对资源的浪费，还会干扰人们做出 硕士论文基于粗糙集的数据约简技术及应用研究 正确而简洁的决策。所以决策表的约简就是将这些冗余的信息从知识库中去掉，重要 的是这样的约简并不影响知识库的分类能力。一般来讲，一个决策表的条件属性对于 决策属性的相对约简并不是唯一的，即同一个决策表可能存在多个约简，而约简中属 性的多少直接影响着决策规则的繁简和性能，因此，往往人们都期望能找到具有最少 属性的约简，但是由于属性组合的爆炸问题导致了找出一个决策表的最小约简是一个 n p - h a r d 问题o “目前针对这个问题主要采取的措施就是引入启发信息到属性约减 中，通过启发信息可以减小样本的搜索空间，从而达到提高约简效率的目的。 3 2 2 基于差别矩阵的属性约简算法 3 2 z1 基于差别矩阵的属性约简算法 该算法是由s k o w r o n 教授提出的，它将对属性组合情况的搜索转化为对逻辑公式 的化简，在介绍本算法之前，首先介绍的是差别矩阵的概念 定义3 1 令s = ( u ，a ，v ，) 是一知识表达系统，l u l - - n s 的差别矩阵是一 个1 1 1 1 矩阵，其任一元素是： 口c t 力= 口a l f ( x , a ) c “口)