（计算机应用技术专业论文）基于粗糙集理论的属性约简算法研究(1).pdf

摘要 粗糙集理论是波兰数学家z p a w l a k 于1 9 8 2 年初提出的一种处理不精确、不 完整、不确定性数据的数学工具。粗糙集理论建立在论域中的不可分辨关系之上， 用上、下近似来描述概念，目前该理论己经在很多领域如属性约简、数据挖掘、 机器学习、模式识别、决策分析等取得了成功的应用。 信息系统的属性约简算法是粗糙集理论的核心内容。寻找信息系统的最优约 简或全部约简是n p 问题，而基于属性重要性的启发式算法能够取得较好的约简。 本文首先探讨了基于可辨识矩阵的属性约简算法，针对该算法时问复杂度较 高的问题，( 1 ) 利用命题演算中的吸收律构造可辨识矩阵的过程中，从而去掉了在 可辨识函数中不起作用的重复元素，提高了属性约简的效率进行算法改进；( 2 ) 根 据可辨识矩阵中各个属性出现的频率进行算法改进；( 3 ) 同时也提出了基于信息熵 的属性约简算法，该算法基于信息论的方法，用信息熵来定义属性的重要性。通 过实例分析对提出的三种算法的有效性和可行性进行了验证。 经过属性约简后的信息系统还不是一个最简单的信息系统，它包含着大量的 冗余信息，因此需要进行属性值约简，本文提出了值约简的一般算法并进行了改 进。在大大降低了原有属性约简和值约简算法复杂程度的基础上，最终求取信息 系统的最佳决策规则。 最后，本文将得到的约简算法应用于数据挖掘的方法中，取得了良好的效果。 关键词数据挖掘；粗糙集理论；属性约简；可辨识矩阵；信息系统；决策表 i i a b s t r a c t r o u g hs e t st h e o r y ，p r e s e n t e di n 1 9 8 2b yp o l i s hm a t h e m a t i c i a nzp a w l a k ，i sa p o w e r f u lm a t h e m a t i c a lt o o lt od e a lw i t hi m p r e c i s e ，i n c o m p l e t ea n du n c e r t a i nd a t a i ti s b a s e do nt h ei n d i s c e m i b i l i t yr e l a t i o nt h a td e s c r i b e si n d i s t i n g u i s h a b l eo b j e c t s ，a n d c o n c e p t sa r er e p r e s e n t e db yu s i n gl o w e ra n du p p e ra p p r o x i m a t i o n s r o u g hs e t st h e o r y i sw i d e l yu s e di nm a n yf i e l d ss u c ha sa t t r i b u t er e d u c t i o n ，d a t am i n i n g ，m a c h i n e l e a r n i n g ，p a t t e mi d e n t i f y i n ga n dd e c i s i o n m a k i n g t h ea t t r i b u t er e d u c t i o no fi n f o r m a t i o ns y s t e mi st h em a i nt o p i ci nr o u g hs e t s t h e o r yg e e i n gt h eb e s tr e d u c t i o no ra l lr e d u c t i o ni san pp r o b l e m h e u r i s t i ca l g o r i t t m l b a s e do i lt h ea t t r i b u t ei m p o r t a n c eh a db e e nm a d et og e tb e t t e rr e d u c t i o n i nt h ep r o c e s so fa t t r i b u t er e d u c t i o n ，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 sb a s e do n d i s c e r n i b i l i t ym a t r i xi sp r o p o s e d b e c a u s eo fi t sh i g ht i m ec o m p l e x i t y ，( 1 ) t h e a b s o r p t i v i t yi nt h ep r o p o s i t i o nc a l c u l a t i o ni su s e dt o t h ep r o c e s so fc o n s t r u c t i n gt h e d i s c e r n i b i l i t ym a t r i x ，t h e nt h ee f f e c t l e s sr e p e a t e de l e m e n t sa r ed e l e t e d ，t h u st h ef i r s t e f f i c i e n c yo fa t t r i b u t er e d u c t i o na l g o r i t h mi si m p r o v e d ：( 2 ) t h es e c o n di m p r o v e d a l g o r i t h mw h i c hi sb a s e do nt h ef r e q u e n c yo fa t t r i b u t e i sp r o p o s e d ；( 3 ) t h et h i r d a l g o r i t h m d e f i n e dt h ea t t r i b u t e i m p o r t a n c eu s i n g t h ei n f o r m a t i o n e n t r o p y t h e e f f e c t i v e n e s sa n dt h ef e a s i b i l i t yo ft h et h r e ea l g o r i t h m si n t h i sp a p e ra r ec l e a r l y d e m o n s t r a t e db yt h ee x a m p l ea n a l y s i s ( e x p e r i m e n t r e s u l t s ) t h ei n f o r m a t i o ns y s t e mi s n tas i m p l e s to n ea f t e ra t t r i b u t er e d u c t i o n i ti n c l u d e s s o m er e d u n d a n c yi n f o r m a t i o na n dn e e d sv a l u er e d u c t i o nt h eg e n e r a la l g o r i t h ma n di t s i m p r o v e da l g o r i t h m sa r ep r o p o s e di nt h i sp a p e r u s i n gt h e s ea l g o r i t h m sw ec a nr e d u c et h ec o m p l e x i t yo ft h eo r i g i n 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 ma n dv a l u er e d u c t i o na l g o r i t h mg r e a t l ya n df i n a l l ya c q u i r et h e o p t i m a ld e c i s i o n m a k i n gr u l e so f t h ei n f o r m a t i o ns y s t e m a tl a s t ，t h er e d u c t i o na l g o r i t h m sa r ea p p l i e d ( u s e d ) t ot h em e t h o do fd a t am i n i n g t h ee x p e r i m e n tr e s u l t si n d i c a t et h i sm e t h o di sv e r ye f f i c i e n t k e 5 , w o r d s d a t am i n i n g ；r o u g hs e t st h e o r y ；a t t r i b u t er e d u c t i o n ；d i s c e r n i b i l i t y m a t r i x ；i n f o r m a t i o ns y s t e m ：d e c i s i o nt a b l e i i 独创性声明 本人郑重声明： l 、坚持以“求实和创新”的科学精神从事科学研究工作。 2 、论文是我个人在导师指导下进行的研究工作和取得的研究成 果。 3 、论文中除了引文和致谢的内容外，不包含其他人或其它教育机 构已经发表或撰写过的研究成果和资料。 4 、其他同志对本研究所做的贡献均已在论文中作了明确的声明并 表示了谢意。 签名累声毽日期：2 竺i 兰三! 关于论文使用授权的说明 本人完全了解西北师范大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以 公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保 存论文。 ( 保密的论文在解密后应遵守此规定) 虢累。诧翩签名：堡! ! 渔日期 西北师范大学硕士学位论文基于粗糙集理论的属性约简算法研究 第1 章绪论 随着科学技术的发展，社会已经进入了信息时代，各种数据库规模越来越大， 数据库中数据急剧增加，人们对数据库的应用己不能仅仅限于对数据进行录入、 统计和检索。仅用录入、统计和检索已不能提取数据中有利于用户实现目标的带 有结论性的信息，数据库中蕴含的丰富知识在这种情况下是得不到充分的发掘和 应用。于是急需强有力的数据分析工具来对数据进行分析、推理、发现数据问的 联系、提取有用特征、简化信息处理、减少信息的浪费进而推动社会的发展。因 此，研究不精确、不确定知识的表达、学习、归纳等方法已成为智能信息处理中 的重要研究课题。 1 1 研究目的和意义 当前，智能信息处理已经成为信息科学理论和应用研究中的一个热点领域。 特别是近年来，人工智能从研究内容到研究方法都经历了很大的发展与变化，在 对于高层次智能行为的研究中，大多数研究集中于知识表示和符号推理。由于知 识的含义随着计算机技术的迅速发展被赋予新的意义，知识将与大量观察和实验 数据的处理、归纳、分类相联系，因而如何对不完整数据进行分析、推理，发现 数据间的关系，提取有用特征，简化信息处理以及研究不精确、不确定知识的表 达、学习、归纳方法等已成为智能信息处理中的重要课题。在过去的几十年中， 人们在专家系统、知识工程、人工神经网络、模糊集等领域进行了大量的实践和 探索，并取得了很多很好的成果。 随着信息时代的到来，数据不断增长，并且在很多情况下数据中含有大量的 冗余信息和噪声。那么如何从大量的、杂乱无章的、强干扰的数据( 海量数据) e e 挖掘潜在的、有利用价值的信息( 有用知识) ，这给人类的智能信息处理能力提出 了前所未有的挑战。目前已有很多对数据进行分析的简单统计技术，如传统的统 计学方法、d e m p s t e r - s h a f e r 证据理论以及基于模糊集理论的模糊方法等。但是由 于这些传统方法本身所具有的局限性，使得它们在处理越来越复杂的系统以及信 息量迅速增加等很多问题时显得无能为力。因此我们迫切需要一种能从大量的数 据信息中发现、推理知识的有效方法。上世纪七十年代末到八十年代初，波兰控 制论专家z p a w l a k 及其合作者为解决如何在带有不确定的数据资源上进行知识 获取和知识表示创立了一种全新的数学理论一粗糙集理论( r o u g hs e t st h e o r y ) ”，2 】。 西北师范大学硕士学位论文 基于粗糙集理论的属性约简算法研究 现在，以粗糙集理论为支撑的各种数据分析方法统称为粗糙集数据分析 f r s d a ) ”。粗糙集数据分析( r s d a ) 与传统的方法相比有以下不同，如统计学方法 基于的是数据的概率分布假设，它采用b a y e s 法则进行规则提取。由于该方法在 推导过程中所用的先验概率和条件概率均需要建立在大量的统计资料上，所以它 不适合于数据规模较小的决策问题。而r s d a 则相反，它不是刻意减少数据的不 确定性，而是描述这种不确定性，即使在数据规模较小的情况下，也能最大限度 地导出决策规则。证据理论采用信任函数和取值表示对某个概念的信任程度。通 常信任度和似然度是由专家给出基本概率分配函数( m a s s 函数) 后通过计算得到 的，因而证据理论带有很大的主观性。而在粗糙集理论中，一个待认识的普通概 念是被两个精确概念( 可被认识的、可被现有的信息精确表达的) 从外延的角度近 似表达。根据数据本身，他们被确定的计算出来。这一过程不需要任何关于数据 的外加信息。模糊集理论将不确定性理解可能性，模糊决策类则被描述为一个模 糊子集，然而模糊隶属函数必须事先人为确定。因而模糊集理论也不可避免地带 有主观性。面在粗糙集理论中，对象与决策类之间的隶属关系完全是根据分类知 识客观地计算出来的。正如z p a w l a k 在其最新的文章【3 j 中所总结的，r s d a 有许 多重要的优势( 1 ) p r o v i d e e f f i c i e n ta l g o r i t h m sf o rf i n d i n gh i d d e np a t t e r n si n d a t a ；( 2 ) f i n d sm i n i m a l s e t so f d a t ab yd a t ar e d a t i o n ；( 3 ) e v a l u a t e ss i 鳃i f i c a n c eo f d a t a ；( 4 ) o f f e r ss t r a i g h tf o r w a r di n t e r p r e t a t i o no fo b t a i n e dr e s u l t s ；( 5 ) m o s ta l g o r i t h m s b a s e do i lt h er o u 曲s e t st h e o r ya i ep a r t i c u l a r l ys u i t e df o rp a r a l l e lp r o c e s s i n g ；( 6 ) i ti s e a s y t ou n d e r s t a n d 。正是由于粗糙集理论具有以上这些优势，因而才能够更好地在 带有不确定的数据资源上进行知识表示和知识莸取。 1 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 hs e t s ：t h e o r e t i c a la s p e c t so f r e a s o n i n ga b o u td a t a ”的问世，成为粗糙集 理论发展的一个重要里程碑。1 9 9 5 年a c mc o m m u n i c a t i o n 将粗糙集列为新浮现 的计算机科学的研究课题。近年来粗糙集已成为信息科学最为活跃的研究领域之 一，同时该理论还在医学、化学、管理科学、商业和金融等领域得到了成功的应 2 西北师范大学硕士学位论文基于粗糙集理论的属性约简算法研究 用。我国对粗糙集理论的研究，主要集中在对它的数学性质、有效算法、知识的 发现与数据挖掘、决策支持与分析等研究方面，如粗糙集理论的知识表示、知识 约简算法、粗糙逻辑等。自2 0 0 1 年在重庆成功召开“第一届中国r o w 【g h 集与软 计算学术研讨会( c r s s c 2 0 0 1 ) ”以来，我国每年的c r s s c 系列研讨会在规模和质 量上均呈良好的增长趋势，在此领域的研究工作发展很快。并且“第六届中国 r o u g h 集与软计算学术研讨会( c r s s c 2 0 0 6 1 ”拟定于2 0 0 6 年l o 月在浙江师范大 学举行。目前，粗糙集理论( r o u g hs e t st h e o r y ) n 神经网络( n e u r nn e t w o r k s ) 、演 化计算( e v o l u t i o n a r yc o m p u t i n g ) 、模糊系统( f u z z ys y s t e m ) 及混沌系统( c h a o t i c s y s t e m ) 已被公认为人工智能的五大新兴技术【4 】，其影响已经渗透到信息科学的几 乎所有分支。 自粗糙集理论提出以来，大致从两方面研究粗糙集理论及其应用。一方面是 对粗糙集的理论研究，主要集中在粗糙代数郾 、粗糙集拓扑及其性质“、粗糙 逻辑及近似推理的逻辑工具 1 1 - 1 3 1 等方面。这些研究结果充分论述了粗糙集与模糊 集 1 4 - 1 8 、证据理论与粗糙集理论之间的关系”】，也建立了粗糙集与概率逻辑、粗 糙集与模态逻辑之间的关系 1 1 , 1 3 。另外，有关粗糙集方法的函数研究方面，近年 来出现了不少粗糙数及粗糙隶属函数的研究，发表了不少实数粗糙离散化等方面 的论文【2 0 川。 粗糙集理论在应用方面的研究也在不断涌现，通常这些应用联系于被称为粗 糙集数据分析( r s d a r o u g hs e td a t aa n a l y s i s ) l 构技术。利用粗糙集处理的主要问 题包括数据库中的数据约简、数据相关性的发现、数据意义评估、由数据产生决 策控制算法、数据的近似分类、数据中的相似性或差异性发现、数据中范式的发 现以及因果关系发现等等。特别地，粗糙集方法在医学、药学、银行、金融、市 场研究、工程设计、气象学、振动分析、开关函数、冲突分析、图像处理、声音 识别、并发系统分析、决策分析、字符识别以及其它领域都有重要应用。 因此，r o u g h 集理论与其它一些软计算理论，诸如f u z z y 集、粒计算、神经 网络、遗传算法等均已经成为当前国内计算机及相关专业的研究热点。 本文中，对于粗糙集理论的约简算法研究正是当前粗糙集领域中一个非常重 要的课题。 知识约简是粗糙集理论的核心内容之一，其主要思想是在保持分类能力不变 的前提下，通过知识约简( 消除信息系统或决策表中不必要的知识) ，导出问题最 终的决策或分类规则。目前，静态的属性约简算法主要有两类：一类是基于信息 西北师范大学硕士学位论文 基于粗糙集理论的属性约简算法研究 熵即s h a n n o n 熵的算法 2 2 - 2 4 ，该算法的基本思路是先计算出核，而后根据其它属 性的重要程度依次在核的基础上添加属性或者根据决策属性对条件属性的依赖程 度依次剔除掉那些对分类不产生影响的属性，直到使所得的属性集与原信息系统 ( 或决策表) 的分类能力相同为止，但该算法往往不能得到系统的所有约简。另一 类是基于可辨识矩阵和可辨识函数构造的属性约简算法 2 1 , 2 5 】，这种算法的基本思 路是利用可辨识矩阵导出可辨识函数，然后求解可辨识函数的析取范式，该范式 中的每一个析取项即为系统的一个约简。算法直观，易于理解，能够计算出核与 所有约简。不足之处是在可辨识矩阵中会出现大量的重复元素，降低了属性约简 算法的效率。 1 3 研究内容的提出 众所周知，粗糙集理论是一种处理含糊和不精确问题的新型数学工具f ”。它 从新的角度认识知识，认为知识的粒度性是造成使用已有知识不能精确地表示某 些概念的原因2 6 j 。通过引入不可区分关系作为粗糙集理论的基础，并在此基础上 定义了上、下近似等概念，使得粗糙集理论能够有效地逼近这些概念。在粗糙集 理论的计算问题中，知识约简是核心内容之一，其目的是在保持分类能力不变的 前提下，去掉数据表中冗余的属性和属性值，以便提高系统潜在知识的清晰度。 这在处理大规模数据尤其是海量数据时是非常必要的。否则冗余信息所带来的时 间和空间上的代价将是巨大的。而大家知道，在实际应用中几乎所有的数据库都 是动态的，这样当一个( 或一批) 新的实例进入数据库后如果都要重新计算新数据 库的约简及决策规则，显然是不经济的，是对计算资源的浪费。这样就给人们提 出了一个新的要求，即如何利用原有的约简与极小决策算法求得新系统的约简与 极小决策算法，这是所谓的属性重要性的计算。 正是由于数据规模的增大，因而时间效率就显得尤为重要，本文正是从提高 属性约简效率入手，对基于可辨识矩阵的属性约简算法和基于属性重要性的属性 约简算法以及属性值约简算法进行研究。对于文中提到的约简，除非特别声明， 均指属性约简。 1 4 论文的主要内容 除本章绪论外，本文的主要内容如下： 第2 章中概述了数据挖掘的定义、数据挖掘的过程、数据挖掘的主要任务、 数据挖掘的对象和数据挖掘的主要方法。 4 西北师范大学硕士学位论文 基于粗糙集理论的属性约简算法研究 第3 章介绍粗糙集的基本理论，主要是在属陆约简过程中用到的一些基本概 念：知识与知识库、不可分辨关系( i n d i s c e r n i b i l i t y ) 、近似与粗糙集、下上近似集、 正域、负域和边界域、知识约简、知识的依赖性、信息系统和决策表。 第4 章探讨了规则提取中一个重要步骤即属性约简的几种算法。由于求取信 息系统的最小约简是一个n p 问题。本章对基于可辨识矩阵的属性约简算法的时 间复杂度高的问题做出改进，提出了改进的基于可辨识矩阵的属性约简算法：同 时探讨了基于属性重要性的几种不同的算法；讨论了规则提取中另一个重要步骤 即值约简算法。由于我们所须要的是从论域中提取规则，而不是简单的属性约简， 因此进一步做出值约简。 第5 章粗糙集理论应用研究( 基于粗糙集理论的数据挖掘方法) 。 第6 章总结全文并指出进一步研究的方向。 西北师范大学硕士学位论文 基于粗糙集理论的属性约简算法研究 第2 章数据挖掘概述 数据挖掘是多门学科和多门技术相结合的产物，也是一个非常年轻而又活跃 的研究领域。目前国内外学术界和企业界都非常重视对数据挖掘技术和软件的研 究与开发。本章简要介绍数据挖掘的定义、过程、任务、对象以及方法等。 2 1 数据挖掘的定义 数据挖掘( d a t am i n i n g ) 就是指从大量的、不完全的、有噪声的、模糊的、随 机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和 知识的过程吲。 “数据挖掘”常常和另一个术语“数据库中知识发现( k n o w l e d g ed i s c o v e r yi n d a t a b a s e 或k d d ) ”一起出现。1 9 9 6 年，p a ) - y a d 、p i a t e t s k y s h a p i r o 和s m y t h 对 k d d 和数据挖掘的关系进行了阐述：k d d 是识别出存在于数据库中有效的、新 颖的、具有潜在效用的、最终可理解的模式的j # 平凡过程，而数据挖掘则是该过 程中的一个特定步骤【28 1 。但是，随着该领域的不断发展，研究者们目前趋向认为 k d d 和数据挖掘具有相同的含义，即认为数据挖掘就是从大型数据库中提取人们 感兴趣的知识。“数据挖掘”主要流行于统计界、数据分析、数据库和管理信息系 统( m i s ) 界；而“k d d ”主要流行于人工智能和机器学习界。 数据挖掘的这个定义包括好几层含义： 第一，数据源必须是真实的、大量的、含噪声的，通常也是不完整的； 第二，发现的是用户感兴趣的知识；发现的知识要可接受、可理解、可运用； 第三，并不要求发现放之四海皆准的知识( 真理) ，也不是要去发现崭新的自 然科学定理和纯数学公式，更不是什么机器定理证明，而仅支持特定的发现问题。 数据挖掘是一门来自各种不同领域的研究者关注的交叉性学科，受多个学科 的影响，最主要的包括：数据库技术、统计学、人工智能、机器学习、模式识别、 高性能计算、可视化技术、信启、科学等四 。 2 2 数据挖掘的过程 数据挖掘即k d d 过程是一食由多个步骤相互连接起来的、交互的迭代过程 ( 如图2 一l 所示) ，包括许多由用户参与给出决策的步骤 2 9 。 ( 1 ) 数据清理：消除噪声和不一致数据； ( 2 ) 数据集成：多种数据源可以组合在一起； ( 3 ) 数据的选择：从数据库中检索与分析任务相关的数据i 西北师范丈学硕士学位论文 基于租糙集理论的属性约简算法研究 ( 4 ) 数据的变换：数据变换或统一成适合挖掘的形式； ( 5 ) 数据挖掘：使用智能方法提取数据模式； ( 6 ) 模式评估：根据某种兴趣度度量，识别表示知识的真正有趣的模式 ( 7 ) 知识表示：使用可视化和知识表示技术，向用户提供挖掘的知识。 数据库图2 1数据挖掘的处理过程 2 3 数据挖掘任务 数据挖掘的两个高层目标是描述和预测。描述性挖掘试图刻画数据库中数据 的一般特性；而预测性挖掘则根据当前数据进行推导，以进行预测。根据可以发 现的模式类型，将数据挖掘任务归纳为以下几类： ( 1 ) 概念类描述( c o n c e p t c l a s sd e s c r i p t i o n ) 。 数据库中通常存放大量的细节数据，然而用户往往希望以简洁而精确的描述 形式来观察汇总的数据。这种数据描述可以提供一类数据的概貌，或可将它与其 他类相区别。这种描述性数据挖掘就称为概念描述。 ( 2 ) 分类和 i ) j ( c l a s s i f i c a t i o na n dr e g r e s s i o n ) 分类是寻找描述数据类型或概念的模型或函数的过程，以便能够使用这些模 型来预测类标号未知的对象所属的类。这些模型基于对训练数据集( 即类标号己知 的数据对象) 的分析而得到，可以用多种形式表示，如分类规则、判定树、数学公 式或神经网络等。 回归则是通过具有己知值的变量来预测其他变量的值。和分类方法不同的是， 分类输出的是离散的类别值，而回归输出的则是连续数值。 西北师范大学硕士学位论文基于粗糙集理论的属性约简算法研究 ( 3 ) 聚类分析( c l u s t e ra n a l y s i s ) 与分类和回归不同，聚类在处理数据对象时不考虑类标号，而是根据最大化 类内的相似性、最小化类间的相似性的原则对数据对象进行聚类或分组的。聚类 分析可以建立宏观的概念，发现数据的分布模式，以及可能的数据属性之间的相 互关系。 ( 4 ) 关联分析( a s s o c i a t i o na n a l y s i s ) 关联分析用于发现大量数据中项集之间有意义的关联或相互关系，寻找给定 数据集中项之间的有趣联系。关联规则的支持度和置信度是两个规则兴趣度度量， 它们分别反映发现规则的有用性和确定性。 ( 5 ) 孤立点分析和演变分析( o u t l i e r a n a l y s i sa n de v o l u t i o n a n a l y s i s ) 数据库中可能包含一些数据对象与大部分数据的一般行为或模型不一致，称 为孤立点。大部分数据挖掘方法将孤立点视为噪声或例外而丢弃，然而在一些应 用( 如欺骗检测) 中，罕见的事件可能比正常出现的那些更有趣。针对孤立点的数 据分析称为孤立点挖掘。 数据演变分析描述行为随时间变化的对象的规律或趋势，它包括趋势分析、 相似性查找、序列模式挖掘、周期性模式分析等方面。 2 4 数据挖掘的对象 依据信息存储格式，用于挖掘的对象有关系数据库、面向对象数据库、数据 仓库、文本数据源、多媒体数据库、空间数据库、时态数据库、异质数据库以及 i n t e m e t ( w e b ) 等。目前，关系数据库仍然是最主要的数据挖掘对象。关系数据库中 的关系表通常也称为信息表或信息系统。 2 5 数据挖掘方法 数据挖掘受多个学科的影响，因此根据数据挖掘方法所属领域的不同可以分 为以下几类：数学统计方法 ” ，一般是首先建立一个数学模型或统计模型，然后 根据这种模型提取出有关的知识；机器学习方法 ”1 ，大多数方法是用人类的认识 模型模仿人类的学习方法从数据中提取知识：nr a 7 数据库的方法1 3 2 利用现有的 一些数据库技术和某些专门针对数据库的启发式方法，提取出数据库中的特征知 识；其他方法，如数据可视化技术、知识表示技术等。 具体蜕来，主要有以下几种数据挖掘技术” ( 1 ) 决策树：利用信息论中的互信息( 信息增益) 寻找数据库中具有最大信息量 西北师范大学硕士学位论文 基于粗糙集理论的属性约简算法研究 的字段，建立决策树的一个结点，再根据字段的不同取值建立树的分支，在每个 分支子集中重复建树的下层结点和分支的过程，即可建立决策树。 ( 2 1 神经网络方法：在结构上模拟人脑神经元结构，通过训练来学习，是一个 具有联想记忆功能的非线性模型，可用于分类、回归和聚类等。但用神经网络来 进行数据挖掘存在着以下几个问题：神经网络很难解释；神经网络会学习过度； 除非问题非常简单，训练一个神经网络可能需要相当可观的时间才能完成；建立 神经网络需要做的数据准备工作量很大。 f 3 1 覆盖正例排斥反例方法：利用覆盖所有正例、排斥所有反例的思想来寻找 规则。比较典型的有m i c h a l s k i 的a q l l 方法、洪家荣改进的a q l 5 方法，以及洪 家荣的a e s 方法。 ( 4 ) 粗糙集方法：一种处理含糊和不确定问题的新的数学工具。利用粗糙集可 以处理的问题包括数据约简、数据相关性的发现、数据意义的评估、由数据产生 决策算法、数据中范式的发现及因果关系的发现等，将在后面详细讨论。 ( 5 ) 可视化技术：数据与结果被转化和表达成可视化形式，如图形、图象等， 使用户对数据的剖析更清楚。 ( 6 ) 云模型方法( ”j ：云是统- - n 画语言值和数值间随机性和模糊性的模型，能 够在定性描述的语言值和定量表示的数值间、连续量和离散量间随时转换，较好 地解决了数据挖掘中的知识表示问题。 ( 7 ) 其他方法：概念树方法、遗传算法、模糊论方法、公式发现、s v m ( 支持 向量机1 等等。 西北师范大学硕士学位论文基于粗糙集理论的属性约简算j 击研究 第3 章粗糙集属性约简理论 粗糙集理论是一种处理含糊和不精确问题的新型数学工具。其主要思想是在 保持分类能力不变的前提下，通过知识约简，导出问题的决策或分类规则。本章 主要介绍属性约简理论中经常用到的一些基本概念和理论，作为以后章节的基础。 3 1 粗糙集理论的基础知识 在粗糙集理论中，知识是用信息系统( 即属性一值对表) 来表示的【3 5 。一般情况 下，表中的列标记不同的属性；行标记论域的对象。如果将信息系统中的属性进 一步分为条件属性和决策属性，则称该信息系统为决策表。知识约简的目的是考 察信息系统( 或决策表) 中给出的知识是否都是必要的( 相对于决策而言) 。知识约简 是删除信息系统( 或决策表) 中冗余信息的过程，直到使所得的知识与原信息系统 ( 或决策表) 的分类能力相同为止。知识约简包括属性约简和属性值约简。决策表 的约简又称为知识的相对约简，其最终结果是将决策表中的知识化成少量的决策 规则。 3 1 1 知识与知识库 在粗糙集理论中，“知识”被认为一种将现实或抽象的对象进行分类的能力【“。 如在远古时代，人们为了生存必须能分辨出什么可以食用，什么不可以食用：医 生给病人诊断时，必须辨别出患者是哪一种病。这些根据事物的特征差别将其分 门别类的能力均可以看作是某种“知识”。 设u 由我们感兴趣的对象组成的有限集合，称为论域 3 6 】。任何子集x u ， 称为u 中的一个子集或范畴。u 中的任意概念族称为关于u 的抽象知识，简称知 识。本文主要是对在u 上能形成划分的那些知识感兴趣。对于论域u 中的一族子 集 x l ，x 2 ，x 。 ，如果u x i = u 且x j n x j = 由，x ，由，对于i j ，i ，j = 1 ，2 ， n ，则称 x i ，x 2 ，x 。 为u 的一个划分。 定义3 1u 上的一族划分称为关于u 的一个知识库( k n o w l e d g eb a s e ) 。一个知 识库就是一个关系系统k i ( u ，r 1 ，其中u 是非空有限集，r 为u 上等价关系的 个族集。 u r 表示r 的所有等价类( 或者u 上的分类) 构成的集合， x r 表示的是包含 元素x u 的r 等价类。 定义3 2 若p r ，且p d 】，则p 中所有等价关系的交集也是一个等价关系， 称为p 上的不可分辨关系( i n d i s c e m i b i l i t y ) ，记为i n d ( p ) ，且有【x 】( p ) = n 【x r 西北师范大学硕士学位论文基于租糙集理论的属性约简算法研究 这样，u i n d ( p ) ( 目p 等价关系i n d ( p ) 的所有等价类) 表示与等价关系族p 相关的 知识，称为k 中关于u 的p 基本知识( p 基本集) 。为简单起见，用u f p 代替u i n d ( p ) ， i n d ( p ) 的等价类称为知识p 的基本概念或基本范畴。特别地，如果q e r ，则称q 为k 中关于u 的q 初等知识，q 的等价类为知识r 的q 初等概念或q 初等范畴。 事实上，p 基本范畴是拥有知识p 的论域的基本特征。换句话说，它们是知识的 基本模块。同样，当k = ( u ，r ) 为一个知识库，i n d ( ：k ) 定义为k 中所有等价关系的 族，记作i n d ( k ) = i n d ( p ) 由p r ) 。 现举例刚说明，给定一玩具积木的集合u = x 1 ，x 2 ，。3 ，x 4 ，x 5 ，。6 ，x 7 ，。8 ) ，并假设这 些积木有不同的颜色( 红、黄、蓝) ，形状( 方、圆、三角) ，体积( 小，大) 。因此， 这些积木就可以用颜色、形状、体积这些知识来描述。例如一块积木可以是蓝色、 方而大的，或者黄色、圆而小的等。现在我们根据某一属性描述这些积木的情况， 就可以按颜色、形状、体积分类。 按颜色分类：红( x l ，x 3 ，x 7 ) 、黄( 。5 ，x 6 ，x 8 ) 、蓝( k 2 ，x o ； 按形状分类：方( x 2 ，x 6 ) 、圆( x l ，x 5 ) 、- - n ( x 3 ，x 4 ，x 7 ，。8 ) ； 按大小分类；小( x 1 ，x 3 , x 4 ，x 5 ，。6 ) 、大( x 2 ，x 7 ，x 8 ) 。 换言之，我们定义三个等价关系( 即属性) ：颜色r 1 ，形状，大小r 3 ，通 过这些等价关系，可以得到下面三个等价类： u r 1 2 x 1 ，x 3 ，x 7 ) ， x 5 ，x 6 ，x 8 ) ， x 2 ，x 4 ) ) ， u r 2 2 “x 2 ，x 6 ) ， x 1 ，x 5 ) ， x 3 ，x 4 ，x 7 ，x 8 ) ) ， u r 3 2 x l ，x 3 ，x 4 ，x 5 ，x 6 ) ， x 2 ，x 7 ，x s ) 。 可以看出，这些等价类是由知识库k = ， r 1 ，r 2 ，r 3 ) 0 0 的初等概念( 初等范畴) 构成的。基本范畴是初等范畴的交集构成的，例如下列集合： x 1 ，x 3 ，x 7 ) n x 3 ，x 4 ，x 7 ，x 8 ) = x 3 7 x ) ， x 2 ，x 6 ) n x 2 ，x 4 ) = x 2 ， x 5 ，x 6 ，x s n x 3 ，x 4 ，x 7 ，x 8 ) = x 8 ) ， 它们分别为 r 1 ，r 2 ) 的基本范畴，即红色三角形，蓝色方形，黄色三角形。 下列集合： x i ，x 3 ，x 7 ) n x 3 ，x 4 ，x 7 ，x 8 ) n x 2 ，x 7 ，。8 ) = x 7 ) ， x 2 ，x 6 ) n x 2 ，x 4 ) n x 2 ，x 7 ，。8 = x 2 ) ， x 5 ，x 6 ，x 8 ) n x 3 ，x 4 ，x 7 ，x 8 ) n x 2 ，x 7 ，x 8 ) = x 8 ) 它们分别为 r 。，r 2 ，r 3 的基本范畴，即红色大三角形，蓝色大方形，黄色大三 西北师范大学硕士学位论文 基于粗糙集理论的属性约简算法研究 角形。 下列集合： x i ，x 3 ，x 7 u x 2 ，x 4 - x i ，x 2 ，。3 ，x 4 ，。7 1 ， x 2 ，x 4 u x 5 ，x 6 ，x s 2 x 2 ，x 4 ，x 5 ，x 6 ，x 8 ) ， x i ，x 3 ，x 7 u x 5 ，x 6 ，x s = x l ，x 3 ，x s ，x 6 ，x 7 ，x 8 。 它们分别为 r ，的范畴，即红或蓝( 非黄) ，蓝或黄( 非红) ，红或黄( 非蓝) 。 下面我们讨论两个知识库之间的关系，令k = ( u ，p ) 和k7 = ( u ，q ) 为两个知识 库。若i n d ( p ) 2 i n d ( q ) ，即u p = u q ，则称k 和k7 ( p 和q ) 是等价的。因此，当 k 和k7 有同样的基本范畴集时，知识库k 和k7 中的知识都能使我们确切的表 达关于论域的完全相同的事实。 对于k 2 ( u ，p ) 和k = ( u ，q ) 两个知识库，当i n d ( p ) ci n d ( q ) 时，我们称知识p f 知 识库k ) 比知识q ( 知识库k7 ) 更精细，或者说q 比p 更粗糙。当p 比o 更精细时， 我们也称p 为q 的特化，q 为p 的推广。这意味着，推广是将某些范畴组合在一 起，而特化则是将范畴分割成更小的单元。 3 1 2 近似与粗糙集 粗糙集理论将用于分类的知识嵌入到集合内，作为集合的一个组成部分，根 据现有的知识判断，一个对象a 是否属于集合有三种情况：对象a 肯定属于x ； 对象a 肯定不属于x ：对象a 可能属于集合也可能不属于集合x 。 令x c u ，r 是u 上的一个等价关系。当x 能表达成某些r 基本范畴的并时， 称x 是r 可定义的；否则称x 是r 不可定义的。 r 可定义集是论域的子集，它可以在知识库中精确的定义，而r 不可定义集 不能在这个知识库中定义。r 可定义集也称为r 精确集f 3 8 】，而r 不可定义集也称 为r 非精确集或r 粗糙集f 3 州。 对于粗糙集可以近似地定义，我们使用两个精确集，即粗糙集的上近似( u p p e r a p p r o x i m a t i o n ) 集和下近 以( 1 0 w e ra p p r o x i m a t i o n ) 集来描述。 定义3 3 设集合x c _ u ，r i n d ( k ) ，定义两个子集： 一r x = u y u r l y x ) ， r x = u o u r i y n 爿中 分别称它们为x 的r 下近似集和r 上近似集。 集合b n r ( x ) = e x r x 称为x 的r 边界域；p o sr ( x ) = 星z 称为x 的r 正 域f4 1 1 ；n e g r ( x ) = u 劢称为x 的r 负域40 1 。 根据定义3 3 可知，旦x 或p o sr ( x ) 是指由那些知识r 判断肯定属于x 的u 西北师范大学硕士学位论文基于粗糙集理论的属性约简算法研究 中元素组成的集合；r x 是指由那些知识r 判断可能属于x 的u 中元素组成的集 合：b nr ( x ) 是由那些知识r 既不能判断肯定属于x 又不能判断肯定属于| x 的u 中元素组成的集合；n e gr ( x ) 由那些知识r 判断肯定不属于x 的u 中元素组成的 集合。 下面的性质是显而易见的。 定理3 1 ( 1 ) x 为r 可定义集当且仅当r x = r z ； f 2 ) x 为r 粗糙集当且仅当r x 硝： 我们也可以将堡f 描述为x 中的最大可定义集，将r x 描述为含有x 的最小 可定义集。 根据集合x 的上近似和下近似的不同情况，可以定义四种不同的重要的粗糙 集： ( 1 ) 如果星z 币且r x u ，则称x 为r 粗糙可定义； ( 2 ) 如果= 由且r x u ，则称x 为r 内不可定义： ( 3 ) 如果星并巾且r x = u ，则称x 为r 外不可定义； ( 4 ) 如果曼x = 中且足= u ，则称x 为r 全不可定义。 这种划分的直观意义是这样的： 如果集合x 为r 粗糙可定义，则意味着我们可以确定u 中的某