（运筹学与控制论专业论文）规则约简及属性约简算法研究.pdf

i i i i 1li lli l lirl l i lllll y 18 4 1912 r e s e a r c ho n a l g o r i t h m so f r u l er e d u c t i o n a n da t t r i b u t er e d u c t i o n b y y u a nj u n y a n s u p e r v i s o r ：p r o f e s s o rz h a n gx u e f e n g n o r t h e a s t e r nu n i v e r s i t y j a n u a r y2 0 0 8 _i一rilo 1|一1 1 j 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的 研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的 研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献都己经在论文中作了明确的说明并表示谢 = 亡己 思。 学位论文作者签名：瘩辱蠡 日期：2 0o 器、； 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师不同意网上交流，请在下方签名；否则视为同意。) 学位论文作者签名： 签字日期： 导师签名： 签字日期： t，-1flpfl k， 舭m墙j重 东北大学硕士学位论文摘要 规则约简及属性约简算法研究 摘要 数据库的广泛应用，大量数据的积累，使得数据挖掘引起了信息产业界的极大关注。 粗糙集理论在机器学习、知识获取、智能控制、决策分析、知识发现、专家系统和模式 识别等领域取得了一些成功的应用。 本文以粗糙集理论为工具，对数据挖掘的方法和过程进行详细的研究。介绍了数据 挖掘的概况，粗糙集理论的基本内容及粗糙集在知识表达系统和决策表中一些应用，研 究了粗糙集理论的知识发现、规则约简及属性约简问题。 本文主要研究内容如下： 第1 章介绍了研究的目的和意义，阐述了国内外的研究发展现状，概括了文章的 研究内容和结构安排。 第2 章介绍了数据挖掘和粗糙集的基本理论，知识表达系统和决策表。包括数据 挖掘的理论和方法，及数据挖掘的步骤，集合的近似与粗糙集，规则约简与知识的依赖 性，知识表达系统及决策表的约简，决策规则，研究了粗糙集理论在知识表达系统与决 策表中的应用情况。 第3 章研究了确定性规则约简集的发现问题。首先介绍了一些相关的概念，提出 了规则集优化的问题，给出了一个找出确定性规则约简集的算法，并证明了该算法具有 可靠的理论基础，用一个算例验证了算法的可行性和有效性。 第4 章研究了不完备信息系统规则优化问题。在完备信息系统的基础上，提出了 不完备信息系统描述子的约简，用描述子描述了优化决策规则的求法，进一步研究了 不完备信息系统的g 约简和d s 约简，可以看出它是完备决策表下定义的近似约简的推 广。 第5 章研究了无核简化差别函数及其求解方法。在简化差别函数的基础上，给出 了基于无核简化差别函数的概念。通过无核简化差别函数求解决策表的约简，可以解决 求解辨别函数时需要消耗很大的时间和空间开销的问题。 第6 章总结与展望对全文的研究工作进行了总结，同时，对下一步的研究工作进 行展望。 i i - 一二j，k ， 东北大学硕士学位论文摘要 关键词： 数据挖掘；粗糙集；规则优化；规则约简；g s 约简；d s 约简； 不完备信息 系统 - i i i y， r e s e a r c ho na l g o r i t h m so fr u l er e d u c t i o na n d a t t r i bu t er e d u c t i o n a b s t r a c t m o r ea n dm o r ep e o p l ep a ya t t e n t i o nt od a t am i n i n g ( d m ) a st h ea p p l i c a t i o no fd a t a b a s e s y s t e ma n dt h ea c c u m u l a t i o no fp l e n t yd a t a t h ea p p l i c a t i o na n dt h et h e o r yo fr o u g hs e th a v e ag r e a ts u c c e s s ，e s p e c i a l l yi nt h ea r e ao fm a c h i n el e a r n i n g , k n o w l e d g ea c q u i s i t i o n ，i n t e l l i g e n t c o n t r o ls y s t e m ，d e c i s i o na n a l y s i s ，e x p e r ts y s t e ma n dp a t t e r nr e c o g n i t i o n i nt h i st h e s i s ，ad e t a i ls t u d yo fm e t h o d sa n dp r o c e s s e so fd a t am i n i n gw i t ht h et o o lo f r o u g hs e tt h e o r yi sc a r r i e do u t t h ep r o b l e mo fk n o w l e d g ed i s c o v e r y ，r u l eo p t i m i z a t i o na n d r e d u c t i o ni ss t u d i e db a s e do nt h eb a s i ct h e o r yo fr o u g hs e t t h em a i nr e s e a r c hi sa sf o l l o w s ： i nc h a p t e r1 ，t h em e a n i n ga n dt h ea i mo ft h er e s e a r c ha n dt h es t a t u si nq u oi n l a n da n d o v e r s e a sa r er e p r e s e n t e d i nc h a p t e r2 ，f i r s t l yt h ed mi si n t r o d u c e d ，a n dt h eb a s i ct h e o r yo ft h er o u g hs e ti ss t u d i e d ， i nw h i c hi n c l u d e st h ea p p r o x i m a t es e ta n dr o u g hs e t ，a t t r i b u t er e d u c t i o na n dd e p e n d e n c e ，t h e c h a r a c t e r i s t i co fr o u g hs e tt h e o r y , t h ea p p l i c a t i o no fr o u g hs e tt h e o r yi nd a t am i n i n g t h e nt h e i n f o r m a t i o ns y s t e ma n dt h ed e c i s i o nt a b l ea r ei n t r o d u c e d ，i nw h i c hi n c l u d e st h eb a s i cc o n c e p t o fr o u g hs e ta n dt h ed i s c r i m i n a t i o nf u n c t i o n ，d e c i s i o nr u l e sa n dt h ea p p l i c a t i o nr o u g hs e ti n t h ei n f o r m a t i o ns y s t e ma n dd e c i s i o nt a b l e i nc h a p t e r3 ，t h ed i s c o v e r ya l g o r i t h m so ft h ec e r t a i nr u l er e d u c t i o ns e ti ss t u d i e d f i r s t l y , s o m ei n t e r r e l a t e dc o n c e p t sa r ei n t r o d u c e d ，a n dt h e na na p p r o a c ho ff i n d i n go u tc a t a i l lr u l e r e d u c t i o ns e ti sg i v e n i th a sar e l i a b l eb a s i ct h e o r e t i c s i nc h a p t e r4 ，t h ea t t r i b u t er e d u c t i o na n dr u l eo p t i m i z a t i o no fi n c o m p l e t ei n f o r m a t i o n s y s t e ma r es t u d i e d t h ed e s c r i p t i o nr e d u c t i o n ，g s r e d u c t i o na n d d sr e d u c t i o na r eb r o u g h t f o r w a r d ，a n dt h e ya r et h eg e n e r a lc o n d i t i o no f t h ea p p r o x i m a t er e d u c t i o n i nc h a p t e r5 ，t h es i m p l i f i e dd i s c r i m i n a t i o nf u n c t i o nw i t h o u tc o r ea n dt h ea p p r o a c ho f c o m p u t i n g a r es t u d i e d ；a na t t r i b u t er e d u c t i o nb a s e do nt h es i m p l i f i e dd i s c r i m i n a t i o nf u n c t i o n i v t，li，t、 东北大学硕士学位论文 a b st r a c t w i t h o u tr e l a t i v ec o r ei sg i v e n ，b yw h i c ht h ep r o b l e m so ft h ee x p e n d i t u r eo ft i m ea n ds p a c ei n c a l c u l a t i n gt h ed i s c r i m i n a t i o nf u n c t i o na r ef i g u r e do u t i nc h a p t e r6 ，t h es t u d yw o r ki ss u m e du pa n dt a s kt h a tw ew i l ld oi nt h ef u t u r ei sp u t f o r w a r d k e yw o r d s ：d a t am i n i n g ；r o u g hs e t ；o p t i m i z a t i o no fr u l e s ；r e d u c t i o no fr u l e s ；g r e d u c t i o n ；d sr e d u c t i o n ；i n c o m p l e t ei n f o r m a t i o ns y s t e m v h 东北大学硕士学位论文目录 目录 独创性声明i 摘要；。i i f 1 ia b s t r a c t 鼍 第1 章引言1 1 1 研究的目的和意义1 1 2 国内外研究现状2 1 3 本文的研究内容及结构安排3 第2 章数据挖掘及粗糙集基本理论5 2 1 数据挖掘与知识发现简介5 2 1 1 数据挖掘与知识发现的基本概念5 。2 1 2 数据挖掘的理论和方法o 。5 2 1 3 数据挖掘的步骤7 2 2 粗糙集8 2 2 1 集合的近似与粗糙集8 2 2 2 属性约简与知识的依赖性1 1 2 2 3 粗糙集的特点。1 3 2 2 4 粗糙集方法在数据挖掘中的应用。1 3 。2 3 知识表达系统与决策表1 4 矗， 2 3 1 基本概念一1 4 点2 3 2 决策表的约简1 7 2 3 3 决策规则一1 7 2 4 本章小结1 8 第3 章确定性规则约简集的发现算法2 0 3 1 基本概念2 0 3 2 算法理论依据2 1 v 1 东北大学硕士学位论文 目录 3 3 确定性规则约简集的发现算法2 3 3 4 算例一2 5 3 5 本章小结2 6 第4 章不完备信息系统的规则约简2 7 4 1 基本概念。2 7 4 2 描述子的约简。2 9 4 3 不完备信息系统的呸约简和d 叠约简。3 1 4 4 本章小结3 4 第5 章基于无核简化辨别函数的属性约简3 5 5 1 无核简化差别函数3 5 5 2 简化差别函数的算法3 6 5 3 简化差别矩阵3 6 5 4 无核简化差别函数的算法一3 7 5 5 算法复杂度分析。3 8 5 6 算1 8 i 4 ：；9 5 7 仿真4 0 5 8 本章小结4 1 第6 章结论与展望4 2 参考文献4 3 致谢4 6 作者攻读硕士学位期间主要成果4 7 v l i 蔫0扩 东北大学硕士学位论文第1 章 引言 第1 章引言 人类社会己经步入一个信息化时代，在人们的日常活动中也在不断地获取信息、分 析信息，并以此来决策自我行为。面对如此繁杂的数据，仅靠数据库的查询机制和统计 方法远远不能满足现实的需要，它迫切需要能自动、智能地将待处理的数据转化为有用 的信息或知识，从而达到加以利用的目的。数据挖掘【1 3 1 j 下是为迎合这种需要而产生并 迅速发展起来的用于开发信息资源的一种新的数据处理技术。 1 1 研究的目的和意义 随着计算机、网络和通讯等信息技术的高速发展，信息处理在整个社会规模上迅速 产业化，在技术上表现为整个社会对大规模数据操作的产业化。这使得人们所积累的数 据越来越多，并且数据与信息系统中的不确定性更加显著。海量杂乱的数据背后隐藏着 许多重要的信息，人们希望能够对其进行深入分析，以便更好地利用这些数据所隐藏的 信息。目前的数据库系统可以高效地实现数据的录入、查询、统计等功能，但无法发现 数据中存在的关系和规则，无法根据现有的数据预测未来的发展趋判1 1 。缺乏挖掘数据 背后隐藏的知识的手段，导致了“数据爆炸但知识贫乏”的现象。 传统上，很大一部分的数据分析与处理工作是由具有专业知识的专家利用简单的数 据表示工具( 电子表格、电子图表等) 和分析方法( 统计) 来完成。这种做法费时费力，效 率较低，且只能获得这些数据的表层信息，而不能获得数据属性的内在关系和隐含信息。 所以，一种能自动分析数据、并提取出隐藏的能够被人所理解的知识的数据挖掘( d a t a m i n i n g ，d m ) 【4 】算法是非常有用的。它的出现为自动和智能地把海量数据转化为有用的 知识提供了有力的手段【1 ，5 1 。数据挖掘是一门广义交叉学科，它汇聚了不同领域的学者， 尤其是数据库技术、人工智能、数理统计、模式识别、数据可视化、高性能计算等方面 的学者和工程技术人员。 数据挖掘技术从一开始就是面向应用的，它要对这些数据进行微观乃至宏观的统 计、分析、综合和推理，以指导实际问题的求解，发现事件间的相互关联，然后利用已 有的数据对未来的活动进行预测。需要指出的是，数据挖掘所发现的知识都是相对的， 具有特定前提和约束条件，同时还要易于理解，所以最好能用自然语言表达出来发现的 结果。 - 1 j一，i?， 东北大学硕士学位论丈第1 章引言 进行数据挖掘的方法有很多，其中粗糙集方法是主要方法之一。粗糙集理论是上世 纪8 0 年代初由波兰数学家z p a w l a k 教授提出的，用于研究不完整数据和不精确知识的 表达、学习和归纳的数学分析理论【6 】。其特点是算法简单，无需提供数据之外的任何先 验信息，可直接从给定问题的描述集合出发，通过不可分辨关系和等价类确定给定问题 的近似域，从而找出该问题的规律。属性约简是粗糙集理论中的一个重要课题【7 1 。 盛 1 2 国内外研究现状 j 数据库中的知识发现技术( k n o w l e d g ed i s c o v e r yi nd a t a b a s e s ，k d d ) 是随着数据库和 人工智能技术的发展而产生的。它首次出现于1 9 8 9 年在美国举行的第十一届国际人工 智能联合学术会议上。随后k d d 及其核心技术数据挖掘得到了广泛的发展。1 9 9 5 年，数据挖掘界召开了第一届知识发现与数据挖掘国际学术会议。该会议是由1 9 8 9 至 1 9 9 4 年举行的四次数据库中知识发现国际研讨会发展起来的。随着参与人员的不断增 多，k d d 国际会议发展成为年会。1 9 9 8 年，在美国纽约举行的第四届知识发现与数据 挖掘国际学术会议上不仅仅进行了学术讨论，而且有3 0 多家软件公司展示了他们的数 据挖掘软件产品，其中的一些软件产品已在北美、欧洲等国得到应用。其它内容的专题 会议也把数据挖掘和知识发现列为重要议题之一。数据挖掘和知识发现已成为当前计算 机科学界的一大研究热点。 今天，数据挖掘面临的主要问题与挑战有以下三个方面： ( 1 ) 噪音：可能由于数据丢失，属性值为空值、测试错误等原因造成。 ( 2 ) 困难的训练集：无代表性的数据，无边界的例子，有限的信息。 ( 3 ) 数据库：数据库是动态的，可能是巨大的。 数据挖掘的方法主要有：贝叶斯方法、决策树方法、粗糙集方法等。数据挖掘的评 价标准是：学习集的消耗、学习期间时间和存储的限制、正确的预测、预测有噪音的训 练集、被学习知识的有效性、结论的句法及语法的简单性。i l z p a w l a k 教授利用粗糙集把那些无法确认的个体都归于边界区域，这个区域被定 y 义为上近似集和下近似集之差集，由于上近似集和下近似集都可以通过等价关系给出确 定的数学描述，所以含糊元素数目可以被计算出来，从而真假二值之间的含糊程度可以 计算。这套方法与统计方法处理不确定问题不同，它不是采用概率方法描述数据的不确 定性；与这一领域传统的模糊集合论处理不精确数据的方法也不相同。最初关于粗糙集 理论的研究主要集中在波兰，当时并没有引起国际计算机界和数学界的重视。直到1 9 9 0 2 东北大学硕士学位论文第1 章引言 年前后，由于该理论在数据的决策与分析、模式识别、机器学习与知识发现等方面的成 功应用，才逐渐引起了世界各国学者的广泛关注。1 9 9 1 年，z p a w l a k 的专著粗糙集 关于数据推理的理论【6 】问世标志着粗糙集理论及其应用的研究进入了活跃时期。 1 9 9 2 年，在波兰召开了关于粗糙集理论的第一届国际学术会议。1 9 9 5 年，国际计算机 协会( a s s o c i a t i o nf o rc o m p u t i n gm a c h i n e r y , a c m ) c o m m u n i c a t i o n 将粗糙集列为新浮现 的计算机科学研究课题。目前粗糙集理论己经成为计算机科学最为活跃的研究领域之 一，在许多应用领域已得到发展，如医疗数据分析、水泥窑生产控制算法、地理学、振 动分析、飞行员技能评定、开关电路综合、语言识别、近似分类、故障诊断、成本预测 等【8 】。1 9 9 8 年、2 0 0 0 年和2 0 0 2 年，分别召开了三届r s c t c ( r o u g hs e t sa n dc u r r e n tt r e n d s i nc o m p u t i n g ) 国际会议，表明粗糙集的研究已步入发展期。 与国外相比，国内研究稍晚，没有形成整体力量。国内对粗糙集理论的研究始于上 世纪9 0 年代中期，1 9 9 3 年国家自然科学基金首次对数据库中知识发现领域的研究项目 给予资助。目前，许多科研单位和高等院校竞相开展相关领域的基础理论及应用研究， 取得了令人鼓舞的成果。2 0 0 1 年5 月重庆邮电学院举办了首届中国粗糙集和软计算学 术研讨会( c r s s c ，2 0 0 1 ) ，2 0 0 2 年1 0 月在苏州大学举办了第二届中国粗糙集和软计算学 术研讨会。2 0 0 3 年5 月重庆邮电学院同时举办第三届中国粗糙集和软计算学术研讨会 和第九届粗糙集、模糊集、数据挖掘与粒度计算国际学术会议( r s f d g r c ，2 0 0 3 ) ，这些 会议的举办表明我国粗糙集理论和数据挖掘研究的队伍正在不断壮大，已经得到国际同 行的重视和认可。粗糙集理论逐渐应用于数据挖掘( d a t am i n i n g ，d m ) 领域中，并在对大 型数据库中不完整数据进行分析和学习方面取得了显著的成果，使得粗糙集理论及数据 挖掘的研究成为热点领域。 1 3 本文的研究内容及结构安排 第1 章介绍了研究的目的和意义，论述国内外研究现状，叙述本文的研究内容及 结构安排。 第2 章介绍了数据挖掘和粗糙集的基本理论，信息系统和决策表。包括集合的近 似与粗糙集，知识约简与知识的依赖性，粗糙集的特点，粗糙集方法在数据挖掘中的应 用。知识表达系统及决策表的约简，决策规则，研究了粗糙集理论在知识表达系统与决 策表中的应用情况。 第3 章首先介绍了完备信息系统一些相关的概念，提出了规则集优化的问题，提 - 3 - 东北大学硕士学位论文第1 章引言 出了一个找出最佳确定性规则集的一个算法，并证明了该算法具有可靠的理论基础，用 一个算例证明了算法的可行性和有效性。 第4 章研究了不完备信息系统属性约简，提出了描述子的约简，用描述子描述了 优化决策规则的求法，进一步研究了不完备信息系统的g 。约简和d 。约简，可以看出它 是完备信息系统下定义的相对约简的推广。 第5 章研究了完备信息系统无核简化差别函数及其求解方法，提出了基于无核简 化差别函数的约简问题。通过提出的无核简化差别函数求解决策表的约简，可以解决求 解辨别函数种所需要消耗很大的时间和空间开销的问题。 第6 章对全文的研究工作进行了总结，同时对下一步的研究工作进行展望。 4 义 l 东北大学硕士学位论文第2 章粗糙集基本理论 第2 章数据挖掘及粗糙集基本理论 数据挖掘是信息技术发展的自然结果，它是从大量数据中挖掘出隐含的、先前未知 的但却具有潜在价值的信息或知识。粗糙集理论是建立在分类机制基础上的，将知识理 解为对数据的划分，每一被划分的集合称为概念。其主要思想是利用已有的知识库，将 含糊知识用已知知识库中的知识来刻画。给出粗糙集理论的一些基本概念，介绍了知识 表达系统和决策表的约简。 2 1 数据挖掘与知识发现简介 2 1 1 数据挖掘与知识发现的基本概念 所谓的基于数据库的知识发现是指从就是从大量的、不完全的、有噪声的、模糊的、 随机的数据中，提取有效的、新颖的、潜在有用的、最终可被理解的模式的非平凡过程。 其中，数据集：指一个有关事实f 的集合，用以描述事物的基本信息；模式：用语言三 表示的表达式e ，它所描述的数据是集合f 的一个子集疋，疋表明数据集f 中的数据 具有特性e ；有效性：从数据中发现的模式必须有一定的可信度，通过函数将表达式映 射到度量空间；新颖性：提取出的模式必须是新颖的，通常用一个函数来表示模式的新 颖程度n ( e ，f ) ，函数的返回值是逻辑值或是对模式e 的新颖程度的一个判断数值；潜 在作用：指提取出的模式将来回被实际运用，可以通过函数来表示有作用的程度；可理 解性：发现的模式应该能够被用户理解，以帮助人们更好的了解和使用数据库中的信息， 这主要体现在简洁性上。 2 1 2 数据挖掘的理论和方法 目前，应用于数据挖掘的主要有以下的理论和方法： 2 1 2 1 概率论 概率论( p r o b a b i l i t yt h e o r y ) 根据随机概率挖掘含有不确定性的空间数据库，发现的知 识被表示成给定条件下某一假设为真的条件概率，常用作背景知识。在用误差矩阵描述 遥感分类结果的不确定性时，可以用这种背景知识表示不确定性的置信度9 1 。 2 1 2 2 证据理论 _ 气 东北大学硕士学位论文 第2 章粗糙集基本理论 证据理论( e v i d e n c et h e o r y ) 是概率论的一个扩展( 又称d e m p s t e r - s h a f e r 理沦) ，是由可 信度函数( 度量己有证据对假设支持的最低程度) 和可能函数( 衡量根据己有证据不能否 定假设的最高程度) 所确定的一个区间。当证据未支持部分为空时，证据理论等同于传 统概率论。证据理论将实体分为确定部分和不确定部分，可以用于基于不确定性的数据 挖掘。利用证据理论的结合规则，可以根据多个带有不确定性的属性进行决策挖掘【l o 1 1 1 。 两两比较法也用于属性不确定性的知识发现。证据理论发展了更一般性的概率论，却不 能解决矛盾证据或微弱假设支持等问题。 2 1 2 3 统计学 统计学( s t a t i s t i c s ) 是依靠有序的模型描述无序事件，根据不确定性和有限信息分析、 评价和预测数据。它主要运用自协方差结构、变异函数或与其相关的自协变量或局部变 量值的相似程度实现基于不确定性的数据挖掘【1 2 】。统计学是基本的数据挖掘技术，特别 是多元统计分析，如判别分析，主成分分析，因子分析，相关分析，多元回归分析掣1 3 】。 2 1 2 4 规则归纳 规则归纳( r u l e si n d u c t i o n ) 是在一定的知识背景下，对数据进行概括和综合，在数据 库或数据仓库中搜索和挖掘以往不知道的规则和规律，得到以概念树形式给出的高层次 的模式或特征，如地理信息系统( g e o g r a p h i c a li n f o r m a t i o ns y s t e m ，简称g i s ) 的属性概 念树和空间关系概念树。背景知识可以由数据挖掘的用户提供，也可以作为数据挖掘的 任务之一自动提取【1 4 1 。关联规则发现是数据挖掘的重要内容，目前的研究重要集中在提 高算法的效率和发现多种形式的规则两个方面，并以逻辑语言或类结构化查询语言 ( s 缸u c t u r e dq u e r yl a n g u a g e ，简称s q l ) 语言方式描述规则，以使数据挖掘趋于规范化和 工程化。 2 1 2 5 聚类分析 聚类分析( c l u s t e r i n ga n a l y s i s ) 主要是根据实体的特征对其进行聚类或分类，按一定的 距离或相似测度在大型数据集中标识出聚类或稠密分布的区域，将数据分成一系列相互 区分的组，以期从中发现数据集的整个分布规律和典型模式。聚类分析是统计学的一个 分支，与规则归类不同的是聚类算法无需背景知识就直接从数据库中发现有意义的聚类 结构。已有的聚类算法多为模式识别设计，用特征表示的目标为特征空间的一个点，在 特征空间中聚类【1 5 1 。 2 1 2 6 决策树 决策树根据不同的特征，以树型结构表示分类或决策集合，产生规则和发现规律。 6 、，广 东北大学硕士学位论文 第2 章粗糙集基本理论 在数据挖掘时，首先利用训练实体集生成测试函数；其次根据不同取值建立树的分支， 在每个分支子集中重复建立下层结点和分支，最终形成决策树；然后对决策树进行剪枝 处理，把决策树转化为据以对新实体进行分类的规则【1 0 1 。i d 3 ( i n t e r a c t i v ed i c h o t o m i z e r3 ) 方法是利用信息论中的互信息( 信息增益) 建立决策树或决策规则树。 2 1 2 7 模糊数学 模糊集( f u z z ys e t ) 用隶属函数确定的隶属度来描述不精确的属性数据，是一种用精 确的数学语言对模糊性进行描述的方法。模糊方法可用于模糊评判、模糊决策、模糊聚 类分析、证据合成和计算置信度等【1 1 1 。 2 1 2 8 粗糙集 粗糙集( r o u g hs e t ) 又称粗集，由上近似集和下近似集组成，是一种处理不精确、不 确定和不完备信息的智能数据决策分析工具，它建立在知识粒度的基础上，利用逼近的 思想来刻画未知的知识。它既可以用于分类，也可以用于约简冗余数据及提取规则 1 6 】。 2 1 2 9 神经网络 神经网络( n e u r a ln e t w o r k ) 是由大量神经元通过极其丰富和完善的连接而构成的自 适应非线性动态系统，并具有分布存储、联想记忆、大规模并行处理、自学习、自组织、 自适应等功能。神经网络由输入层、中间层和输出层组成。大量神经元集体通过训练来 学习待分析数据中的模式，形成描述复杂非线性系统的非线性函数，适于从环境信息复 杂、背景知识模糊、推理规则不明确的非线性空间系统中挖掘分类知识。神经网络对计 算机科学、人工智能、认知科学以及信息技术等都产生了重要而深远的影响，在数据挖 掘中可用来进行分类、聚类、特征挖掘等操作17 1 。 2 1 2 1 0 遗传算法 遗传算法是模拟生物进化过程的算法，由选择、交叉和变异三个基本算子组成。在 数据挖掘中，把数据挖掘任务表达为一种搜索问题，利用遗传算法的空间搜索能力，经 过若干代的遗传，就能求得满足适应度值的最优解规则。遗传算法通过种群遗传产生优 良的后代。遗传算法已在优化计算和分类机器学习方面发挥了显著的效果【1 8 】。 2 1 3 数据挖掘的步骤 数据挖掘的实施大体可分为以下三步： ( 1 ) 数据准备( d a t ap r e p a r a t i o n ) 这个阶段包括两步： 东北大学硕士学位论文 第2 章粗糙集基本理论 数据集成：从操作型环境中提取数据并加以集成，解决语义的二义性问题，消除脏 数据。 数据选择和预分析：进一步缩小数据范围，提高数据挖掘的质量。 ( 2 ) 数据挖掘( d a t am i n i n g ) 这个阶段实际的挖掘工作，包括： 先决定如何产生假设：是让数据挖掘系统为用户产生假设，还是对于数据库中可能 l 包含矍茎兰霎兰等兰：前一种称为发现型的数据挖掘，后一种称为验证型的数据挖掘； iii 选择合适的工具； r 利用前面提到的数据挖掘方法挖掘数据库中的知识； 证实发现的知识。 ( 3 ) 规则表述( r u l ep r e s e n t a t i o n ) 数据挖掘将获得的信息以方便用户理解和观察的方式反映给用户，这些基于不同数 据集合的分析结果除了通过可视化工具提供给用户外，还可以存储在知识库中，供日后 进一步分析和比较。 2 2 粗糙集 2 2 1 集合的近似与粗糙集 p a w l a k 教授提出的经典粗糙集理论是建立在不可分辨关系( 即等价关系) 基础上的。 定义2 1 1 1 9 , 2 0 l 若u 是论域( 既我们感兴趣的对象的集合) ，等价关系r 就是满足下面 三个条件的关系： ( 1 ) 自反性：对v x u ，有( x ，x ) r ； ( 2 ) 对称性：x 寸v ( x ，y ) r ，有，z ) r ； 岔 ( 3 ) 传递性：对v ( x ，j ，) r ，( y ，z ) r ，则有( x ，z ) r 。 二 若u 是论域，尺是一族等价关系，则称关系系统k = ( u ，r ) 为一个知识库。易知一 族等价关系的交集仍然是一个等价关系，并记为i n d ( r ) 。在不引起混淆的情况下，本文 用r 来代替i n d ( r ) 。 定义2 2 【1 9 , 2 0 1 设k = 缈，r ) 为一知识库，其中u 是论域，r 是不可区分关系，u r 东北大学硕士学位论文第2 章粗糙集基本理论 表示论域u 在尺下的所有等价类构成的集合，【工 r 表示包含元素x u 的尺等价类，对 于v x u ，定义两个子集： 堡( x ) = u p r ye _ x ， 页( x ) = u p l y nx 矽 ， 分别称它们为知识库中对象集合x 在r 下的下近似集和集合x 在r 下的上近似集，简 称为集合x 的r 下近似集和集合x 的r 上近似集。 集合b n r ( x ) = r ( x ) 一星( x ) 称为集合x 在r 下的边界域；集合p o s r ( x ) = 墨( 工) 称 为集合x 在r 下的正域；集合n e g r ( x ) = u 一尺( x ) 称为集合x 在r 下的负域。如图2 1 所示，图中椭圆为模糊集，外面的大矩形表示论域u ，在等价关系尺下，论域被划分成 多个小矩形，其中每一个小矩形表示一个等价类。 也可以从元素出发定义集合的下近似、上近似，可以表示为 ； 星( x ) = k v t x r x ) ， 页( x ) = & u b 】rn x 痧 。 图2 1 粗糙集及集合的上、下近似 f i g u r e2 1r o u g hs e tx a n dt h eu p p e ra n dl o w e ra p p r o x i m a t i o no f xa b o u tr 星( x ) 或p o s 置( x ) 是根据不可区分关系r 判断肯定属于x 的u 中的元素组成的集 合；页( x ) 是根据不可区分关系r 判断可能属于x 的u 中的元素组成的集合；b n 矗( ) 根 东北大学硕士学位论文第2 章粗糙集基本理论 定义2 3 囝1 设k = 缈，r ) 是一个知识库，v xc u ，如果x 等于2 么的某些元素的 羔：- 掣芝l 耋三：定义集，也称x 为尺精确集或分明集；否则称x 为尺不可定义集 龋= x 筹r 纛且蛳r ( x 瑚；x 为r 当一r ( x 瑚。鼽j 显然，为精确集当且仅当 ) = 星( x ) ；为粗糙集当且仅当 ) 星( x ) 。 ， 东北大学硕士学位论文第2 章粗糙集基本理论 如果垦( x ) = 矽且g ( x ) = u ，则称集合x 为r 全不可定义，简称为r 不可定义： 这四类粗糙集具有明显的直观意义。集合x 为r 粗糙可定义，这意味着能够应用 关系尺确定u 中的一些元素是属于x 或；集合x 为r 内不可定义，这意味着能够 应用关系r 确定u 中的一些元素是属于耐，但却不能确定u 中的任何元素是否属于 x ；集合x 为尺外不可定义，这意味着能够应用关系r 确定u 中的一些元素属于x ， 但却不能确定u 中的任何元素是否属于耐；集合x 为r 全不可定义，这意味着应用关 系尺不能确定u 中的任何元素是否属于x 或材。 集合的不精确性是由边界域的存在而引起的。集合的边界域越大，其精确性越低。 定义2 4 1 9 , 2 0 1 设k = ( u ，尺) 是一个知识库，x u ，定义 = 嚣怒 则称参数口且( x ) 为x 的近似精度，其中x 矽，c a r d ( * ) 表示集合“孝 的基数或称势。 显然，0 口置( x ) 1 。如果口矗( x ) = 1 ，有r ( x ) = 8 ( x ) ， 进一步有 b n 足伍) = r ( x ) 一8 ( x ) = 矽，集合x 是关于尺的分明集；如果( x ) 1 ，集合x 是关于 尺的粗糙集。 2 2 2 属性约简与知识的依赖性 一般情况下，知识库中的知识存在着一定的冗余。知识库的约简就是删除冗余的知 识。约简是粗糙集理论在重要内容。所谓的属性约简，就是在保持知识库分类能力不变 的条件下，删除其中不相关或不重要的属性。 定义2 5 【1 9 , 2 0 1 设k = ( u ，r ) 是一个知识库，p r ，如果满足： ( 1 ) i n d ( p ) = i n d ( r ) ； ( 2 ) 不存在qcp ，使得i n d ( q ) = i n d ( r ) 成立，即对于v qcp ，有i n d ( q ) i n d ( r ) ； 则称p 为r 的一个约简。r 的所有约简的集合记为r e d ( r ) 。 定义2 6 【1 9 , 2 0 设k = ( u ，r ) 是一个知识库，pc _ r ，如果满足： ( 1 ) 对于v ，p ，i n d ( r 一 ，) ) i n d ( r ) ； 1 1 - 东北大学硕士学位论文 一 箜! 主塑垫釜墨查垩丝 ( 2 ) 对于w r p ，i n d ( r p ) ) = 砌d ( r ) 成立； 则称p 为r 的核，记为c o r e ( r ) 。 定理2 1 0 9 ，2 0 r 的核为r 的所有约简的交集，& pc o r e ( r ) = a r e d ( r ) 。 设p 和q 为论域u 中的等价关系，q 的p 正域记为p o s p ( q ) ，即 p o s p ( q ) 2x 觇( x ) q 的p 正域是u 中所有根据分类叫尸的信息可以准确地划分到关系q 的等价类中去的 对象的集合。 定义2 7 1 9 ，2 0 设k ：( u ，r ) 是一个知识库，p cr , q 冬r 为论域u 中的等价关系， s 互p ，如果满足： ( 1 ) p o s 。 ) = p o s ，( q ) ； ( 2 ) 不存在tcs ，使得p o s rq ) = p o s p ) 成立，即对于v t cs ，都有 p o s r ) p o s p ) ； 则称s 为p 的一个q 约简，简称为相对约简。所有p 的q 约简构成的集合记为旭如。 定义2 8 1 9 ，2 0 设k ：，尺) 是一个知识库，p _ c 尺，qc _ r 为论域【厂中的等价关系， s p ，如果满足： ( 1 ) 对于v r s ，p o $ 卜 ， ( q ) p 傩尸 ) ； ( 2 ) 对于v ，ep s ，有p p - r ( q ) = p o s 尸( q ) 成立； 则s 为p 的q 的核，简称为相对核，记为c o r e q ( p ) 。 定理2 2 1 9 ，2 0 】相对核为所有相对约简的交集，臣 jc o r e q ( e ) = o r e d q p ) 。 显然，p 的q 约简是不唯一的，但p 的q 核c d 吻( 尸) 是唯一的。 定义2 9 1 9 ，2 0 设置：( r ) 是一个知识库，p ，a r ，知识q 依赖于知识p ( 记作 尸jq ) 当且仅当觑d ( 竹冬i n d ( q ) ；知识p 与知识q 等价( 记作p 兰q ) 当且仅当p