（计算机应用技术专业论文）基于粗糙集的分类算法研究.pdf

摘要 数据挖掘是利用分析工具从大量的、 数据中，提取出隐含在其中、事先未知、 不完全的、有噪声的、模糊的、随机的 但又潜在有用的信息和知识。数据分类 是数据挖掘的重要内容之一，目前用于分类的方法有很多，如粗糙集、决策树、 贝叶斯网络、遗传算法等。 粗糙集理论是波兰数学家z p a w l a k 于1 9 8 2 年提出的一种新的处理模糊和不 确定性知识的数学工具。其主要思想就是在保持分类能力不变的前提下，通过知 识约简，导出问题的决策或分类规则。决策树是通过一组无次序、无规则的实例 推理出树表现形式的分类规则，它有易理解、易训练、易实施和通用性强等优点。 粗糙集和决策树都是常用的分类方法，本文将两者相结合，取长补短，对数据进 行分类挖掘，主要研究内容包括： 1 ) 对属性约简算法进行研究。大多数情况下，知识库存在冗余的属性，冗余 属性既是对计算机资源的浪费( 需要大量的存储空间) ，也会干扰人们做出正确而 简洁的决策，所以有必要对属性进行约简。本文首先介绍了粗糙集中有关约简的 相关概念，然后分析了几种典型的属性约简算法，最后提出了一种基于遗传算法 的粗糙集属性约简算法，给出了算法的基本思想、详细设计过程、基本框架，并 通过实例证明了本文算法能够快速有效地进行属性约简。 2 ) 对决策树分类方法进行研究。根据何种度量准则选择属性作为节点是决策 树构造的一个关键问题。本文对现有的决策树算法进行研究，在原i d 3 算法的基 础上，结合粗糙集理论和决策树基本原理，提出使用粗糙集理论选择属性作为节 点来构造决策树，然后利用p e p 后剪枝方法的优点，选择其为树剪枝，最后得出 最简分类规则。 关键词：数据挖掘；分类；粗糙集；属性约简；决策树 a b s t r a c t d a t am i n i n gi sam e t h o do f u s i n ga n a l y t i ct o o l sf r o mt h ed a t a ，w h i c ha r em a s s i v c ， i n c o m p l e t e ，n o i s y 如z z ya n dr a n d o m u s i n gt h i sm e t h o d ，w ec a nf i n dt h el a t e n tu s e 如l i n f o m a t i o na n dk n o w l e d g ew h i c hu s e dt ob ec o n c e a l e da n du n k n o w n b e f o r e h a n d d a t a c l a s s i f i c a t i o ni so n eo ft h ei m p o r t a n tc o n t e n t sf r o md a t am i n i n g a tp r e s e n t ，t h e r ea r e m a n ym e t h o d sf o rd a t ac l a s s i f l i c a t i o n ，s u c h 嬲r o u g hs e t ，d e c i s i o nt r e e ，b a y e sn e t ， g e n e t i ca l g o r i t h m se t c r o u g hs e tt h e o r yp u tf o r w a r db yp o l ez p a w l a ki nl9 8 2i san e wt o o lf o r p r o c e s s i n gv a g u ea n du n d e f i n e dk n o w l e d g e u n d e rt h ep r e m i s eo fk e e p i n gt h ec o n s t a n t a b i l i t yo fc a t e g o r i z e ，t h em a i ni d e ao ft h et h e o r yi st oo u t p u tt h ed e c i s i o no ft h e p r o b l e mo rt h ec a t e g o r i z e dr u l et h r o u g ht h er e d u c t i o no fk n o w l e d g e d e c i s i o nt r e ei s t h ec l a s s if y i n gr u l et h a ti n f e r st h ed e c i s i o nt r e em a n if e s t a t i o nt h r o u 曲g r o u po f o u t - o f 二o r d e r s ， t h en o n r u l e e x a m p l e s i ti s c o m p r e h e n s i b l e ， e a s yt r a i n i n g ，e a s y i m p l e m e n t a r ya n dv e r s a t i l e r o u g hs e t a n dd e c i s i o nt r e ea r e c o m m o n l yu s e d c l a s s i f i c a t i o nm e t h o d s i nt h i sp a p e r t h ec l a s s i f i c a t i o no fd a t am i n i n gi sr e s e a r c h e db y ac o m b i n a t i o no f r o u g hs e ta n dd e c i s i o nt r e e t h em a i nc o n t e n t sa r cl i s t e da sf o l l o w ： 1 )r e s e a r c ho nt 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 m i nm o s tc a s e s ，t h e r ei s r e d u n d a n ta t t r i b u t ei nt h ek n o w l e d g eb a s e o no n eh a n d ，t h er e d u n d a n ta t t r i b u t ei sa w a s t eo f r e s o u r c e s ( r e q u i r i n gal a r g e 锄o u n to fs t o r a g es p a c e ) ；o nt h eo t h e rh a n d ，i t i n t e r f e r e sw i t hp e o p l et om a k ec o r r e c ta n dc o n c i s ed e c i s i o n ，t h e r e f o r ei ti sn e c e s s a r yt o r e d u c ea t t r i b u t e t h ep a p e rf i r s ti n t r o d u c e st h er o u g hs e to nr e l a t e dc o n c e p t so f f e d u c t i o n ，a n dt h e na n a l y z e ss e v e r a lt y p i c a la t t r i b u t er e d u c t i o na l g o r i t h m s ，a n df i n a l l y p r o p o s e sag e n e t i ca l g o r i t h mb a s e do nr o u g hs e ta t t r i b u t er e d u c t i o n t h ea l g o r i t h m g i v e st h eb a s i ci d e a s ，d e t a i l e dd e s i g nm e t h o d ，b a s i cf r a m e w o r ka n dp r o v e st h e q u i c k n e s sa n de f n c i e n c yo fa t t r i b u t er e d u c t i o nt h r o u g he x a m p l e 2 ) i 乇e s e a r c ho nc l a s s i f i c a t i o nm e t h o do fd e c i s i o nt r e e s e l e c t i n ga t t r i b u t en o d e b a s e do nw h a tm e a s u r e m e n tc r i t e r i ai sak e yq u e s t i o no fd e c i s i o nt r e es t r u c t u r e t h i s p a p e rr e s e a r c h e st h ee x i s t i n gd e c i s i o nt r e ea l g o r i t h m ，i na c c o r d a n c ew i t hr o u g hs e t t h e o r ya n dt h ed e c i s i o nt r e eb a s i cp r i n c i p l e ，p r o p o s e st h a tt h ei o u g hs e tt h e o r yc h o o s e t h ea t t r i b u t et oc o n s t l l l c tt h ed e c i s i o nt r e en o d eb a s e dt h ei d 3a 1g o r i t h m ，t h e nt h ep a p e r c h o o s e sp e pt op 1 1 j n et h ed e c i s i o nt r e ed u et ot h ea d v a n t a g e so f p e p ；f i n a l l yt h ep a p e r o b t a i n st h es i m p l e s tc l a s s i f i c a t i o nr u l e sf r o mt h et f e e k e yw o r d s ： d a t a m i n i n g ；c l a s s i f i c a t i o n ；r o u g hs e t ； a t t r j b u t er e d u c t j o n ； d e c i s i o nt r e e i i 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含 任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本 声明的法律后果由本人承担。 作者签名：钎浙生 日期：2 0 0 9 年多月多日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存和汇编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“) 作者签名： 钾晦乏 导师签名： 写丁 日期：2 0 0 9 年多月岁日 日期：2 0 0 9 年月多日 1 1 研究背景和意义 第一章绪论 随着科学技术的不断发展与进步，人们面临着越来越多的数据，这些激增的 数据背后隐藏着许多有用的信息。目前的数据库系统对数据可以进行录入、查询、 统计等等，却不能发现数据中存在的关系和规则，更不能依据现有的数据对未来 的发展趋势进行预测，因此，导致了“数据爆炸但知识贫乏力的现象【1 1 。 如何在丰富的数据面前发现有用的信息? 数据挖掘技术应运而生。数据挖 掘【2 4 】( d a t am i n i n g ，简称d m ) 是随着数据库技术和人工智能技术一起发展地一 门交叉学科。数据挖掘是在没有明确假设的前提条件之下来挖掘数据、发现其中 有用的知识。从数据挖掘中所得到的数据应该有效的、可实用的，而且是先前未 知的。数据应该有效和可实用，这是显而易见地，在这里不做解释。解释一下所 谓的先前未知，是指那些信息或者知识是事先未曾预料到的，也就是说数据挖掘 是要发现那些我们无法用直觉来发现的信息或知识。在数据挖掘中，挖掘出来的 信息越是出其不意，那么这信息就可能越是价值。数据挖掘的出现，为海量数据 可以转化为有用的知识提供了手段。 分类【5 _ 6 】方法是数据挖掘领域中非常主要的研究课题之一。分类对数据进行分 析，它可以从复杂的数据中提取出重要的数据类，也可以预测未来的数据以及数 据的发展趋势，因此研究发展各种分类技术是非常必要的。 粗糙集【7 。9 】( r o u g hs e t ，简称r s ) 理论起始于2 0 世纪8 0 年代初，它是由波兰 华沙理工大学z p a w l a k 教授提出的，粗糙集理论是一种处理模糊和不确定性知识 的数学工具。粗糙集理论的主要思想是在保持知识库的分类能力不变的前提下， 对知识库进行知识约简【1 0 1 1 1 ，导出问题的决策或分类规则。粗糙集理论不同于其 它处理不确定性问题的理论，最大的区别是它不需要任何先验知识，粗糙集理论 可以直接从给定问题的描述集合出发，运用粗糙集理论中的不可区分关系和等价 关系确定问题的近似域，从而找出给定问题的规律。 粗糙集理论是数据挖掘领域的一种重要方法，受到了广泛关注和青睐。粗糙 集理论可成为数据挖掘方法的依据：第一，数据挖掘研究的对象大部分为关系型 数据库，而关系型数据库的关系表可被看作是粗糙集理论中的决策表，这对粗糙 集理论的应用是非常方便的。第二，数据库中的数据可能含有噪声，而去除数据 中的噪声也是粗糙集理论的特长之一。第三，利用粗糙集的约简理论去除高维数 据中的冗余属性，达到降维的目的，可提高数据挖掘的效率。第四，数据库中的 规则有确定的，也有不确定的潜规则。从数据库中挖掘不确定的知识，为数据挖 掘提供了用武之地。第五，运用粗糙集理论的数据挖掘方法可并行执行，这样极 大地提高大规模数据库的挖掘效率。第六，由粗糙集方法处理得到的决策规则和 推理比神经网络、模糊理论等工具更容易证明和检测。粗糙集理论经过最近几年 的研究与发展，已经比较成功地应用在人工智能及应用、信息系统分析、知识与 数据发现、决策支持系统等方面。 决策树( d e c i s i o nt r e e ) 【1 2 】是一种直观的知识表示方法，同时也是高效的分类 器。决策树在人工智能、机器学习、数据挖掘等领域被广泛地应用，它的优点有： 第一，决策树不仅可以处理离散数据也可以处理连续数据；第二，决策树的构造 计算量不大；第三，决策树产生的规则可以很容易地转化为“i f t h e n ”规则【1 3 j4 1 ， 也可以被翻译成自然语言或s q l 语句；第四，决策树可以指出对决策最重要的数 据域。 目前，粗糙集理论和决策树方法的应用得到了快速的发展，把粗糙集理论与 决策树方法相结合进行分类模式的数据挖掘研究，取长补短、充分发挥粗糙集理 论和决策树的优点，为分类寻找新方法是我们面临的一个新的课题。 1 2 数据挖掘概述 1 2 1 数据挖掘的基本概念 数据挖掘的定义在学术界一直存在一定的争议，本文对数据挖掘的定义是：数 据挖掘是在数据库大量的、有噪声的、不完全的、随机的、模糊的数据中提取出 我们以前并不知道的、但又隐含在数据中的、对我们潜在有用的知识和规则的一 个过程。有时候数据挖掘也称作为知识挖掘，知识发现等等。在数据挖掘的定义 中要求数据源是真实的、大量的、含有噪声的信息；通过数据挖掘所发现的知识 和规则是潜在的并隐藏在丰富的数据背后，用户对这些知识是感兴趣的，并且希 望能够理解、运用这些知识。 在许多时候，人们将知识发现【1 5 1 ( 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 ，简称k k d ) 与数据挖掘不加区分。知识发现是指对数据库中的数据进行有效地识别，发现一 些新颖的、具有潜在价值的信息并最终将数据转化为可理解的模式的一个不平凡 2 过程。由于现在的工作大部分是基于数据库的，所以在实际研究与应用过程中人 们提得更多的是知识发现。知识发现是从数据库中发现知识的整个过程，数据挖 掘只是发现知识全过程的一个关键地步骤，它指运用特定的算法从数据中提取模 式。一个知识发现的完整过程是由很多个挖掘过程组成的，但是在工业、数据库、 媒体等等研究领域中，“数据挖掘 一词被人们广泛地使用和普遍地接受，已经不 加区分地表示整个数据挖掘过程。 1 2 2 数据挖掘的过程 数据挖掘的过程通常地可以划分成三个主要地步骤：数据准备、数据挖掘和 结果解释评估。 ( 1 ) 数据准备：没有数据，数据挖掘也就无从作起，数据准备是数据挖掘的 首要步骤。首先根据用户需要从原始数据库或者数据仓库中提取数据集，然后数 据预处理，对数据进行加工，如去噪声，删除或填补数据，最后数据变换，在原 始数据的基础上得到较为丰富的数据信息，进而便于下一步数据挖掘。 。( 2 ) 数据挖掘：根据确定的挖掘任务或者挖掘目的，选择合适的挖掘模型或 挖掘算法对数据进行处理。有两个因素需要考虑：第一不同的数据有不同的特点， 需要用相应的算法来挖掘；第二根据用户或实际运行系统的要求来挖掘。选择了 挖掘模型或算法后，就可以实施数据挖掘操作了。 ( 3 ) 结果解释和评估：数据挖掘的结果有些是有实际意义的，而有些是与实 际情况相违背的，这就需要进行评估。如果评估出来的数据模式存在冗余或无关 的信息，这时需要去除这些信息；也有可能评估出来的数据模式根本不满足用户 的要求，这时需要重新选取数据，运用新的数据变换，或者变换一种挖掘算法重 新进行数据挖掘等。评估可以根据用户多年的经验，也可以直接用实际数据来验 证模型的正确性，进而调整挖掘模型，不断重复进行数据挖掘。 1 2 3 数据挖掘的功能 数据挖掘的功能与用户进行挖掘的数据类型有联系，数据挖掘的有些功能只 能用在一个它们特定的类型的数据库上，而有些功能就能够应用在几个不同类型 的数据库上。数据挖掘功能的任务一般可以分为两类：描述型和预测型。描述型挖 掘任务对数据库中数据的一般特性进行刻画。预测型挖掘任务用来预测数据的未 来趋势或者行为。下面介绍数据挖掘的六大主要功能：关联分析、分类、聚类、 偏差检测、序列模式和预测等。 3 ( 1 ) 关联分析( a s s o c i a t i o na n a l y s i s ) ：从数据库中挖掘出满足一定条件的依赖 关系。如果两个或多个数据项之间，它们的取值重复出现而且概率很高时，那么 这些数据项之间就将存在某种关联，可以对它们建立起一定的关联规则。关联分 析是从数据库中进行数据挖掘的一种重要方法。 ( 2 ) 分类( c l a s s i f i c a t i o n ) ：分类是数据挖掘中一个十分重要的课题，许多数 据挖掘问题本质上都可以等价或转化为分类问题。分类在已知数据库的数据特征 和分类结果的基础上，为数据库中的每一个数据类别找到一个合理的描述或模型， 然后再利用找到的描述或模型对新数据进行分类。常见的分类模型有线性回归模 型、神经网络模型、决策树模型等等。 ( 3 ) 聚类( c l u s t e r i n g ) ：是指依据某一规则，把一组个体归成不同的类别，即 物以类聚，并用显示或隐性的方法描述不同的类别。聚类的目的是使得属于同 一类别的个体之间的距离尽可能的小，而属于不同类别的个体之间的距离尽可能 的大。常见的聚类方法有统计方法、机器学习方法、神经网络方法等等。许多适 用于分类的算法同样也适用于聚类。 ( 4 ) 偏差检测( d e v i a t i o nd e t d c t i o n ) ：又称为比较分析。指通过数据分析，发 现异常情况的过程。偏差检测的基本方法就是找出数据的观察结果与参照物之间 的差别。偏差包括很多有用的规则和知识，如标准类外的特例，数据聚类外的离 群值等等。偏差检测的数据模型有拐点、极值点、断点以及边界等不同的偏差对 象。 ( 5 ) 序列模式( s e q u e n c ep a t t e m ) ：是指搜索出业务现有数据和历史数据之间 重复发生且概率较高的模式。这种模式与上面的关联分析有点相似，它们都是要 找出数据之间的相互联系，不同点是，序列分析更加注重于研究数据之间的前因 后果关系，也就是说序列分析有时间上的概念。 ( 6 ) 预测( p r e d i c t i o n ) ：是指从历史数据和当前数据之中寻找规律，建立模型 去推测未来的数据，通常认为是以时间为关键属性的关联知识。时间序列预测方 法有经典的统计方法、神经网络和机器学习等等。 1 2 4 数据挖掘的发展趋势和方向 数据挖掘技术的应用领域正不断扩大，发展趋势主要有以下几个方面： ( 1 ) 随着数据挖掘的广泛应用和深入开展，数据挖掘将成为企业信息系统的 一种能力，为企业提供更多有用的信息，提升企业竞争力。 ( 2 ) 数据挖掘将走向可视化。经过全面的可视化，数据挖掘工具更加易于使 4 用，帮助人们理解所挖掘的知识。 ( 3 ) 数据挖掘过程将走向标准化成为类似关系型数据库一样的工业标准技术， 这样有助于大规模的分工开发，也更有利于企业的使用。 ( 4 ) 数据挖掘将在复杂数据面前大显身手，处理多媒体数据、文本数据、地 理空间数据等复杂数据。 ( 5 ) 与互联网技术相结合，互联网络日益普及，研究基于网络的数据挖掘技 术日益紧迫。 ( 6 ) 设计具有动态性的数据挖掘方法。目前，数据挖掘出来的知识，只是相 对于某一时间的某些数据的，新的数据可能使发现的新知识与原来的知识冲突， 动态的数据挖掘方法是其实用化的一个基本要求。 1 3 国内外研究发展现状 1 9 8 9 年在美国举行的第十一届国际人工智能联合学术会议【l6 】上首次出现了 知识发现技术，之后知识发现和数据挖掘得到了广泛地发展。1 9 9 5 年，数据挖掘 界召开了第一届知识发现与数据挖掘国际学术会议【1 7 】。随着参与人员的不断增多， 知识发现国际会议发展成为年会。19 9 8 年，在美国纽约举行了第四届知识发现与 数据挖掘国际学术会议，这次会议不仅进行了学术讨论，而且有3 0 多家软件公 司展示了他们的数据挖掘软件产品，其中的一些软件产品已在北美、欧洲等国得 到广泛地应用。其它内容的专题会议也把数据挖掘和知识发现列为重要议题之一， 数据挖掘和知识发现已成为当前计算机科学界的一大研究热点。 进行数据挖掘的方法有很多，粗糙集理论是主要地方法之一。1 9 8 2 年波兰数 学家z p a w l a k 首次提出了粗糙集理论。当时，关于粗糙集理论的研究主要集中在 波兰，因此粗糙集理论的诞生并没有引起国际计算机界和数学界的重视，直到2 0 世纪8 0 年代末它才慢慢地引起其他学者的关注。在近十年，粗糙集理论已经成功 应用于模式识别、决策与分析、知识发现以及机器学习等方面，这也逐渐引起了 世界各国学者的广泛关注。1 9 9 1 年，z p a w l a k 教授发表了第一本关于粗糙集的专 著r o u 曲s 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 【l 引，奠定了粗糙集理 论的基础。1 9 9 2 年，第一届关于粗糙集理论的国际学术会议在波兰召开了，重点 讨论了粗糙集理论的基本思想以及它的应用。从此以后，每年都有以粗糙集理论 为主题的国际研讨会 1 9 】。1 9 9 3 年，第二届国际粗糙集与知识发现研讨会在加拿大 召开，有力地推动了粗糙集理论应用的研究。恰好这次会议是知识发现最为热门 5 地时候，所以一些知识发现学者也参与了会议，于是，知识发现、粗糙集理论以 及数据挖掘三者联系到了一起。1 9 9 4 年，第三届国际粗糙集与软计算研讨会在美 国召开，深入探讨了粗糙集与神经网络、模糊逻辑、进化计算等的结合问题。1 9 9 5 年，a c mc o m m u n i c a t i o n 【2 0 】将粗糙集列入新浮现的计算机科学的研究课题。1 9 9 9 年，第七届粗糙集、模糊集、数据挖掘和粒度一一软计算国际会议在日本召开， 主要介绍了当时粗糙集和模糊集的研究与发展。2 0 0 0 年：第二届粗糙集和计算的 当前趋势学术会议在加拿大召开。现在，粗糙集理论的研究已经成为世界重要学 术会议的热点。 9 0 年代中期，在我国开始了对粗糙集理论的研究，到目前，很多科研院所和 高等院校专家学者对粗糙集进行了一系列的研究，并取得了丰硕的成果。2 0 0 1 年， 首届中国粗糙集和软计算学术研讨会在重庆邮电学院举行。2 0 0 2 年，第二届中国 粗糙集和软计算学术研讨会在苏州大学举行。之后，第三届再次在重庆邮电学院 召开，2 0 0 4 年，在浙江舟山举行了第四届，之后，由鞍山科技大学举办了第五届粗 糙集和软计算学术研讨会和第九届粗集、模糊集、数据挖掘与粒度计算国际学术 会议。所有这些会议使我国的粗糙集研究不断深入，同时，也使研究的队伍不断 壮大，也得到了国际同行地肯定与认可。 决策树是在人工智能技术之后兴起的，在2 0 世纪9 0 年代，决策树成为构造人 工智能系统的重要方法之一。现阶段，数据挖掘技术越来越被人们重视，决策树 技术也随之发展得越来越快，并发挥出强大的作用。i d 3 算法是最著名的决策树学 习方法，它是由著名学者q u i n l a n 在l9 8 6 年成功开发的，后来q u i n l a n 又开发出了改 进版本c 4 5 ，c 5 o 。i d 3 算法基于s h a n n o n 的信息统计理论，用信息熵函数来判断基 于对象特征的不确定性分类。i d 3 算法不能处理不精确信息，并且这个算法对训练 数据集不能进行有效地训练，大规模数据库也不能有效地处理，为了解决上面那 些缺陷，i b ma l m a d e n 研究中心开发出了s l i q 【2 l 】分类方法和j o h ns h a f e r 等人提出 了s p r i n t 算法，这两种分类方法分别使用了不同的数据结构，具有很好的伸缩性， 和良好的并行性。另外，还有剪枝与建树合并的方法p u b l c 【2 2 1 ，大数据集决策树 快速生成框架r a i n f o r e s t f 2 3 】等等决策树的改进算法。近年来，决策树研究的内容多 种多样，如：决策树技术和神经网络技术、模糊集合原理相结合。最近，c o l a r u 【2 4 】 提出了一种新的模糊决策树方法一一软决策树，决策树技术与进化算法相结合【2 5 1 ， 基于进化算法的决策树系统具有较好的抗噪声能力，同时进化算法容易在并行计 算机上运行；决策树技术与多智能体的结合，将决策树用于多智能体控制并不多 见，p s t o n e 和m v e l o s o 发表了一些这方面的文章，他们提出了基于c 4 5 算法中置信 6 度下的多智能体控制，并将此用于机器人足球控制；最近，m a n k e r s t 等提出了基 于多维可视化下的交互式的决策树构造，此方法在决策树构造阶段加入了专家知 识，这样便于用户更深地理解产生决策树的数据及最终产生的决策树。 1 4 本文的研究内容与组织安排 本文的研究内容与组织安排如下： 第一章绪论。阐述了本文研究背景和意义；介绍了数据挖掘的基本内容，包 括数据挖掘的概念、过程、功能及发展趋势；最后简要介绍了本文的研究内容和 组织结构。 第二章粗糙集理论概述。对粗糙集的基本理论进行了介绍，包括：知识与知 识库的定义、讨论了近似与粗糙集的关系，知识约简与知识依赖度的关系，知识 表达系统与决策表的关系，为后面的章节打下基础。 第三章基于粗糙集的属性约简算法。分析了多种属性约简方法的实现原理以 及各方法的优缺点，然后提出了一种基于遗传算法的属性约简方法，从算法思想、 实现过程、时间复杂度等方面进行较为深入地研究。 第四章基于粗糙集的决策树分类方法。对几种常见的决策树算法进行了研 究，并结合粗糙集理论和决策树基本原理，提出了一种基于粗糙集理论的决策树 分类方法，本方法运用粗糙集理论中的近似精确度来选择属性构造决策树，并用 p e s s i m i s t i ce r r o rp r u n i n g 方法进行剪枝，最后提取出分类规则。 第五章总结与展望。对论文进行了总结，并对下一步的工作进行了展望。 7 第二章粗糙集理论概述 粗糙集理论是一门研究人类认识知识的数学学科，是一种处理含糊和不精确 问题的新型工具。粗糙集理论可以在保持知识库的分类能力不发生改变的条件下， 通过知识约简，得到所求问题的决策或者分类规则。本章主要介绍粗糙集理论f 2 6 。2 9 j 属性约简的相关概念，作为以后章节的基础。 2 1 知识与不可辨识关系 知识被认为是人类和其它物种所固有的分类能力。例如，医生给病人诊断， 会根据患者的病症从中辨别出病人得的是哪一种病；我们能够分辨出哪种食物可 以吃哪种不可以吃。这些将事物分门别类的能力都可以看作是某种“知识 。 这里的事物在粗糙集中称为“对象一，它可以是任何事物，比如实物、抽象概 念、状态、过程和时刻等等。“知识 必须与特定部分的某种分类联系在一起，这 种特定部分称为所讨论的论域，也就是我们感兴趣的对象组成的有限集合。任何 论域中的子集j u ，称为u 中的一个子集或范畴。知识是指u 中的任意一个概 念族。本文主要讨论在u 上能形成划分的那些知识。对于论域u 中的一个族 x l ， x 2 ，x n ) ，假设ux i = u ，置nx ，= o ，x ，a ，那么对于f j f ，i ，j 2 l ，2 ， n ，就说( x i ，x 2 ，x n ) 为u 上的一个划分。 定义2 1u 上的一个划分称为关于u 的一个知识库，也就是一个关系系统( 或 二元组) k = ( u ，r ) 其中，【厂a ，是一个所有要讨论的个体的集合，r 为u 上等价关系的一个族集。 u r 表示r 的所有等价类构成的集合，【x 】r 表示的x u 所有元素的r 等价 类。 定义2 2 如果尸冬尺，并有p a ，那么p 中所有等价关系的交集称为p 上的 不可分辨关系( i n d i s c e m i b i l i t y ) ，也称不可区分关系，记为i n d ( p ) ，并且 m 坝尸) = f1 足。 r e j p u i n d ( p ) 表示与等价关系p 相关的知识，称为k 中关于u 的p 基本知识。通 常，用u p 代替u i n d ( p ) ，知识p 的基本概念也就是i n d ( p ) 的等价类，有时也叫 作基本范畴。若q r ，则称q 为k 中关于u 的q 初等知识，q 相应的等价类就 称为知识r 的q 初等概念或q 初等范畴。概念也就是对象的集合，族集或者说分 8 类就是u 上的知识。 下面举一个例子，一个玩具积木的集合u = x l ，x2 ，x 8 ) ，这些积木有不同 的颜色( 红、蓝、黄) ，体积( 小、大) ，形状( 圆、方、三角) 。所以，可以用颜 色、体积、形状来描述这些积木。 这些积木按颜色，可以分为：红 x l ，x 3 ，x 7 ) ；蓝( x 2 ，x 4 ) ；黄 x 5 ，x 6 ，x 8 ) ；按体积 可以分为：小 x i ，x 3 ，x 4 ，x 5 ，x 6 ) ；大 x 2 ，x 7 ，x 8 ；按形状，可以分为：圆 x l ，x 5 ) ；方 x 2 ，x 6 ) ； 三角 x 3 ，x 4 ，x 7 ，x 8 ) 。 也就是说，可以给出由颜色、形状、体积三个属性定义的三个等价关系：颜 色r l ，体积r 2 以及形状r 3 如下： u r l = x l ，x 3 ，x 7 ) ， x 2 ，x 4 ) ， x 5 ，x 6 ，x 8 ) ) ；u r 2 = x l ，x 3 ，x 4 ，x 5 ，x 6 ， x 2 ，x 7 ，x 8 ) ) ； u r 3 = x l ，x 5 ) ， x 2 ，x 6 ) ， x 3 ，x 4 ，x 7 ，x 8 ) ) ， 也就是说，以上等价类是由知识库k = ( u ， r 1 ，r 2 ，r 3 ) ) 中的初等概念所构成的。 基本范畴是所有初等概念的交集组成的，本例可以得到 r l ，r 3 ) 的基本范畴， 即：红色三角形，黄色三角形，蓝色方形，也即如下三个集合： x l ，x 3 ，x 7 ) n x 3 ，x 4 ，x 7 ，x 8 ) = x 3 ，x 7 ) ； x 5 ，x 6 ，x 8 ) n x 3 ，x 4 ，x 7 ，x 8 ) = x 8 ) ； x 2 ，x 6 ) n x 2 ，x 4 ) = x 2 ) ， r l ，r2 ，r 3 ) 的基本范畴，即：红色大三角形，黄色大三角形，蓝色大方形， 也即如下三个集合： x l ，x 3 ，x 7 ) n x 3 ，x 4 ，x 7 ，x 8 ) n x 2 ，x 7 ，x 8 ) = x 7 ) ； x 5 ，x 6 ，x 8 ) n x 3 ，x 4 ，x 7 ，x 8 ) n x 2 ，x 7 ，x 8 ) = x 8 ) ； x 2 ，x 4 ) n x 2 ，x 6 ) n x 2 ，x 7 ，x 8 ) = x 2 ) 。 2 2 近似与粗糙集 粗糙集理论将分类知识嵌入到粗糙集理论的集合内，根据分类知识可以判断 一个对象a 是否属于集合：对象a 一定不属于集合x ；对象a 一定属于集合x ； 对象a 可能属于也可能不属于集合x 。 令x 至u ，r 是u 上的一个等价关系。如果x 是r 上可定义的，那么就是说 x 能表达成某些r 的基本范畴；否则称x 是r 不可定义的。 粗糙集可以近似地定义，为达到这个目的，使用两个精确集，一个是上近似 ( u p p e ra 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 ) 来对粗糙集进行描 述。 定义2 3 给定知识库k = ( u ，k ) ，设集合x u ，一个等价关系r i n d ( k ) ， 定义两个子集： 9 天又= u 】，u ri 】，nx g ) 些= u 】，u 尺i 】，x ) ， 它们分别为x 的r 上近似集和x 的r 下近似集。 如果有p o ( x ) = 型，那么称p d s 足( x ) 为x 的r 正域； 如果锄晨( x ) = 厨一烈那么称钿矗( x ) 为x 的r 边界域； 如果有疗昭足( x ) = u 一面，那么称以昭足( x ) 为x 的r 负域。 在粗糙集理论中，通过知识r 判断肯定属于x 的u 中元素由烈或p d j 月( x ) 表示；通过知识r 判断可能属于x 的u 中元素由肘表示；通过知识r 既不能判 断可能属于x 又不能判断肯定属于x 的u 中元素由b n r ( x ) 表示；通过知识r 判 断肯定不属于x 的u 中元素由n e g r ( x ) 表示。 可以得到下面两条性质： ( 1 ) x 为r 粗糙集心新； ( 2 ) x 为r 可定义集当且仅当墼= 冠； 粗糙集理论与传统的集合论很类似，不同是，传统集合论认为，一个元素要 么属于，要么不属于一个集合，即它的隶属函数i ix ( x ) 0 ，l 。模糊集合为每个 集合元素赋予一个隶属度，即l ix ( x ) o ，l 】，这样就使得模糊集合能够方便地处理 一些不确定的数据，由于这个隶属度一般人为的设定，所以应用起来也怎么方便。 在粗糙集理论中，隶属关系不需要人为的设定，所以不会有主观因素的影响。 集合x 的不精确是因为边界域而引起的，也就是说集合x 是一个粗糙集。对 应于一个粗糙概念，只能通过上面讨论的上近似集和下近似集这对精确概念来“近 似地描述。 定义2 4 定义集合x 的近似精确度为 州剐= 矧 亿1 ) x 为非空集合，l x l 表示集合x 的基数。 通过近似精确度口异( x ) 我们可以比较方便地对集合x 进行了解。对每一个 等价关系r 和彳u ，近似精确度口矗( x ) 值存在于0 和1 之间，o 口r ( z ) l 。 l o 当口置( x ) = l 时，也就是说x 的r 边界域为a ，集合x 为等价关系r 可定义的； 当口。( x ) ，e 4 = x 4 ，x 8 ) ， e 5 2 x 7 ，x i o 。 集合x l = x o ，x l ，x 4 ，x 8 ) 为r 可定义集，因为： 基x 。= 页x i = e iue 4 集合x 2 = x o ，x 3 ，x 4 ，x 5 ，x 8 ，x l o 为r 粗糙可定义集，因为： 斟匕= eu 日= x 3 ，x 4 ，x 5 ，x 8 ) ， 豆x 2 = 局ub ue 4ub = x o ，x l ，x 3 ，x 4 ，x 5 ，x 7 ，x 8 ，x i o 6 玎胄( 爿r 2 ) = 巨u 毛= x o ，x l ，x 7 ，x l o ) 口置( x 2 ) = 4 8 = 1 2 。 集合x 3 = ) 【o ，x 2 ，x 3 ) 为r 内不可定义，因为： 甄= a 更x 3 = e lue 2u 岛= x o ，x l ，x 2 ，x 3 ，x 5 ，x 6 ，x 9 ) u 。 集合) ( 4 = x o ，x l ，x 2 ，x 3 ，x 4 ，x 7 ) 为r 外不可定义，因为： 墨l = e l = x o ，x l 畏x 4 枷， 6 刀置( x 4 ) = e 2ue 3ue 4u 也= x 2 ，x 3 ，x 4 ，x 5 ，x 6 ，x 7 ，x 8 ，x 9 ，x l o ) ( x 3 ) = 2 1 1 。 集合x 5 = x o ，x 2 ，x 3 ，x 4 ，x 7 ) 为r 全不可定义，因为： r x 。= 仍r x 。= u 一 ，o 2 3 知识约简、知识依赖度和属性重要度 2 3 1 知识约简 在一个知识库里，希望同样的问题用较少的知识表达出来，但又不失其原有 的表达能力，在粗糙集理论中，可用约简来达到这个目的。知识约简是粗糙集理 论的核心内容之一。知识库中知识( 属性) 并不是同等重要的，知识约简的目标 就是要从知识库中发现部分必要的知识( 属性) ，在保持知识库的分类能力不发生 改变的前提下，删除知识库中不相关或不重要的知识( 属性) 。 约简( r e d u c t ) 和核( c o r e ) 是知识( 属性) 约简中两个重要的基本概念。 定义2 5 令p 为等价关系的一个族集，r p ，如果i n d ( p - r ) ) = i n d ( p ) ，则称 关系r 在族集p 中是可省略的( 不必要的) ：否则称关系r 在族集p 中是不可省 略的( 必要的) 。 可省略的( 不必要的) 关系在知识库中是多余的，如果将它删除掉，不会改 变知识库的分类能力；如果从知识库中去掉一个不可省略的( 必要的) 关系，那 么一定会破坏这个知识库的分类能力。 定义2 6 令p 为一个等价关系的族集，r p ，如果所有等价关系r p 都为p 中必要的，那么称族集p 是独立的；否则，就称族集p 是依赖的。 对于是独立关系的等价类族集，是不能对它进行知识( 属性) 约简的，而对 于是依赖关系的等价类族集，由于其中包含有多余的关系，因此可以对它进行知 识( 属性) 约简。 定理2 1 如果一族等价关系p 是独立的，并且q p ，则称q 也是独立的。 证明：用反证法。假设q p 而且q 是依赖的，那么就有scq ，使得i n d ( s ) = i n d ( q ) ，同时 ， i n d ( su ( p q ) ) = i n d ( p ) ，而su ( p q ) c p 则p 是依赖的，与前提条件相矛盾，所以证明了定理的成立。 定义2 7 设p 、q 是论域u 上的两个等价关系族，有q s p ，如果下面两式成 立： ( 1 ) i n d ( p ) = i n d ( q ) ；( 2 ) q 是独立的。 那么称q 是p 的一个约简。 定义2 8 设p 为论域u 上的一个等价关系族，p 中所有必要的关系称为核， 记作c o r e ( p ) 。 对于核与约简有：c o r e ( p ) = nr e d ( p ) r e d ( p ) 表示族集p 的所有约简族。 核的用处主要体现在作为所有约简计算的基础，因为核包含在所有的约简之 中，并且计算可以直接进行；其次核可以解释为在知识约简时它是不能消去的知 识特征集合。 通常，逐个向核中添加不必要的关系产生约简，并每加一个不必要的关系就 检查一次。在计算约简时，不必要的关系集合的幂集的基数是多少，就会有多少 1 2 种添加不必要关系的方式。最好的情况是当所有的必要关系的集