（计算机软件与理论专业论文）基于粒度层次的数据挖掘分类算法研究.pdf

太原理工大学硕士研究生学位论文 基于粒度层次的数据挖掘分类算法研究 摘要 粒度计算作为近年研究领域的热点，为数据挖掘研究的许多方面提供 了概念上的框架。许多学者从不同的视角，不同的概念和模式对粒度计算 进行了研究。近年来，粗糙集理论已经变成了粒度计算研究的主要数学模 式。 分类是数据挖掘和模式识别的主要任务之一。分类有许多不同的表达 方式，如分类规则、判别式、决策树和决策表等。本文在粗糙集理论和粒 度计算理论的基础上，对数据挖掘的分类算法中进行了研究。 本文的主要工作如下： 首先，介绍了数据挖掘的基本概念，数据挖掘的基本过程。数据挖掘 的模式分为以下几种：分类模式、预测模式、关联规则模式、回归模式、聚 类模式、时间序列模式等。不论是哪一种模式，算法都起着非常重要的作 用。分类模式算法包括以下几种：决策树分类、贝叶斯分类、支持向量机、 神经网络、遗传算法、粗糙集方法。 第二章介绍了粗糙集理论和粒度计算理论的相关背景和一些基本概 念。并引入了多粒度层次概念。 在第三章中，首先介绍了属性约简的基本概念，属性约简中的粒度计 算。对粒度计算理论用于分层属性约简进行了研究，并给出粒度计算的属 太原理工大学硕士研究生学位论文 性约简算法。 在接下来的两章中，本文提出一种基于粒度层次的决策树分类算法。 该算法改进了决策树c 4 5 算法并引入了粒度概念层次。每个粒度用( 属性， 值) 去定义。基于粒度层次树模型，我们用搜索粒度策略来提取分类规则。 在一个粒度层次中，每个结点都是数据对象的子集，连接大粒度到小粒度 的弧用一个原子公式( 属性，值) 定义。最终，树模型中所有最小粒度定义的 对象是论域的一个覆盖。在每个粒度层次上的规则都可以从数据集合中导 出，从顶层到底层将推导出一个规则。我们用u c i 数据集验证上述方法，实 验结果表明该算法是非常有效的。 关键词：数据挖掘，决策树，粗糙集，粒度计算，分类算法 太原理工大学硕士研究生学位论文 r e s e a r c ho nd a t aa 皿n i n g c l a s s i f i c a t i o na l g o r n 田b a s e do n g ra n u ，a rh ra r c h y a b s t r a ( 、t g r a n u l a rc o m p u t i n g ，a sa l le m e r g i n gr e s e a r c hf i e l d , p r o v i d e sac o n c e p t u a l f r a m e w o r kf o rs t u d y i n gm a n yi s s u e si nd a t am i n i n g t h ec o n c e p to fg r a n u l a r c o m p u t i n gh a sb e e nd e f i n e da n ds t u d i e db ym a n ya u t h o r sf r o md i f f e r e n tp o i n t s o fv i e w s ，u s i n gd i f f e r e n tn o t i o n s ，b a s e do nd i f f e r e n tc o n c e p t u a lm o d e l s ，a n di n d i f f e r e n t c o n t e x t s r e c e n t l y ，r o u g h s e t t h e o r y h a sb e c o m ea p o p u l a r m a t h e m a t i c a lf r a m e w o r kf o rg r a n u l a rc o m p u t i n g c l a s s i f i c a t i o ni so n eo f t h em a i nt a s k si nm a c h i n e l e a r n i n g ，d a t am i n i n ga n d p a t t e mr e c o g n i t i o n k n o w l e d g ef o rc l a s s i f i c a t i o nc a nb ee x p r e s s e di nd i f f e r e n t f o r m s ，s u c ha sc l a s s i f i c a t i o nr u l e s ，d i s c r i m i n a n tf u n c t i o n s ，d e c i s i o nt r e e sa n d d e c i s i o ng r a p h s o nt h eb a s i so fr o u g hs e tt h e o r ya n dg r a n u l a rc o m p u t e r i n g t h e o r y , t h i s d i s s e r t a t i o n a n a l y z e s t h ed a t a m i n i n ga l g o r i t h m s f o rt h e c l a s s i f i c a t i o n t h em a i nc o n t r i b u t i o n so ft h e s i sc a nb es u m m a t i z e da sb l o w ： f i r s t ，s o m eb a s i cc o n c e p t so fd a t am i n i n ga n dd a t am i n i n gp r o c e s sw e r e i n t r o d u c e d f r o mt h ed i f f e r e n tt a s ko fd m ，t h e r ea r es e v e r a lp a t t e r n sf o l l o w s i 太原理工大学硕士研究生学位论文 c l a s s i f i c a t i o np a t t e r n ，p r e d i c t i o np a t t e r n ，a s s o c i a t i o nr u l ep a t t e r n ，r e g r e s s i o n p a a e m ，c l u s t e r i n gp a t t e r n ，t i m es e r i e sp a t t e r na n ds oo n a l g o r i t h mi sv e r y i m p o r t a n tf o ra n yp a t t e r n t h ea l g o r i t h mo fc l a s s i f i c a t i o np a t t e r ni n c l u d e s ： d e c i s i o nt r e e ，b a y e sc l a s s i f i c a t i o n ，s u p p o f tv e c t o rm a c h i n e ，a r t i f i c i a ln e u r a l n e t w o r k , g e n e t i ca l o g r i t h m ，r o u g hs e tt h e o r y t h es e c o n dc h a p e r , t h eb a c k g r o u n do fr o u g hs e ta n ds o m eb a s i cc o n c e p t o fg r a n u l a rc o m p u t e r i n gw e r ei n t r o d u c e d t h i sp a p e ri n t r o d u c e sm u l t i l a y e r e d g r a n u l a t i o n sc o n c e p t t h et h i r dc h a p e r , t h eb a s i cc o n c e p to fa t t r i b u t er e d u c t i o na n da t t r i b u t e r e d u c t i o nb a s eo ng a r a n u l a rc o m p u t i n gw e r ei n t r o d u c e d l e v e lc o n s t r u c t i o n a t t r i b u t er e d u c t i o na n dt h ea c q u i s i t i o no fd e c i s i o nr u l e s ，t h ek e y p r o c e s s e so ft h e a p p l y i n go fg r a n u l a rc o m p u t e r i n g ，w e r es t u d i e d i nt h ef o l l w i n gt w oc h a p t e r s ，ad e c i s i o nt r e ec l a s s i f i c a t i o na l o r t i t h mb a s e0 1 1 g r a n u l eh i e r a r c h yw a si n t r o d u c e d b a s e do nt h eg r a n u l a rc o m p u t i n gm o d e l ，w e p r o v i d eaf o r m a la n dm o r es y s t e m a t i cs t u d yo fg r a n u l ec e n t e r e ds t r a t e g i e sf o r t h ei n d u c t i o no fc l a s s i f i c a t i o nr u l e s i na g r a n u l eh i e r a r c h y , e a c hn o d ei s l a b e l e db yas u b s e to f o b j e c t s t h ea r cl e a d i n gf r o mal a r g e rg r a n u l et oas m a l l e r g r a n u l ei s l a b e l e db ya na t o m i cf o r m u l a i na d d i t i o n ，t h es m a l l e rg r a n u l ei s o b t a i n e db ys e l e c t i n gt h o s eo b j e c t so ft h el a r g e rg r a n u l et h a ts a t i s f yt h ea t o m i c f o r m u l a t h ef a m i l yo ft h es m a l l e s t g r a n u l e s t h u sf o r m sac o n j u n c t i v e l y d e f i n a b l ec o v e r i n go ft h eu n i v e r s e b a s e do nt h eg r a n u l eh i e r a r c h y , r u l e sf o r e a c hh i e r a r c h i c a ll e v e la r ei n d u c e df r o md a t a t h e n ，f o re a c hg i v e nc l a s s ，r u l e s i v 太原理l ：人学硕+ 研究生学位论文 f o ra l lt h eh i e r a r c h i c a ll e v e l sa r ei n t e g r a t e di n t oo n er u l e t h ep r o p o s e dm e t h o d w a se v a l u a t e do nau c id a t as e t ，t h ee x p e r i m e n t a lr e s u l t so fw h i c hs h o wt h a t t h i sa l g o r i t h m si sm o r ee f f i c i e n c y k e y w o r d s ：d a t am i n i n g ，d e c i s i o nt r e e ，r o u g hs e t s ，g r a n u l a rc o m p u t i n g ， c l a s s i f i c a t i o na l o g r i t h m s v 声明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体。均已在文中以明确方式标明。本声明的 法律责任由本人承担。 论文作者签名：王多、亥 日期：一塑1 2 1 三! ! 关于学位论文使用权的说明 本人完全了解太原理工大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件与复印 件；学校可以采用影印、缩印或其它复制手段复制并保存学位论文； 学校可允许学位论文被查阅或借阅；学校可以学术交流为目的， 复制赠送和交换学位论文；学校可以公布学位论文的全部或部分内 容( 保密学位论文在解密后遵守此规定) 。 签名：至尘耋!日期： ! ! 丑主，堕 导师签名：趔 太原理工大学硕士研究生学位论文 第一章绪论 数据挖掘( d a t am i n i n gd m ) 的研究领域始于2 0 世纪9 0 年代，它是- - 1 7 交叉学科， 涉及到数理统计、人工智能、机器学习、模式识别、数据可视化、数据库等多项技术领 域。经过十几年的研究发展，数据挖掘开始走向成熟，并正朝着更深入的方向发展“1 。 本章主要介绍数据挖掘的概念和过程、分类模式的常用研究方法以及本论文的主要研究 内容和方法。 1 1 数据挖掘概述 随着数据库技术的迅速发展和数据库管理系统的广泛应用，使得各企事业单位积累 了大量的数据。并且人们也意识到在这些大量的数据背后必然隐含着许多重要信息，因 此人们希望能够对这些信息进行更高层次的分析，以便能对决策者提供更好的支持。 但是，目前使用的数据库管理系统通常是用来存储数据和对数据进行简单的操作， 比如增加、删除、查询、修改等，这些操作根本不可能为我们提供隐含在数据背后的重 要信息。因此，我们必须研究出一种新的数据分析手段，数据挖掘正是为了解决传统分 析方法的不足，并针对大规模数据的分析处理而出现的“1 。 数据挖掘是指从大型数据库或数据仓库中提取人们感兴趣的知识，这些知识是隐含 的、事先未知的、潜在有用的信息，提取的知识一般可以表示为概念( c o n c e p t s ) 、规则 ( r u l e s ) 、规律( r e g u l a r i t y ) 、模式( p a t t e r n s ) 等形式。由于数据挖掘能够从大量的数 据中提取出隐藏在数据之后的有用信息，它被越来越多的领域所应用，并取得良好的效 果，为人们做出正确的决策提供了很大的帮助。 数据挖掘被认为是数据库知识发现中最重要的一部分。基于数据库的知识发现 ( k n o w l e d g ed i s c o v e r yi nd a t a b a s ek d d ) 一词，最早是在1 9 8 9 年8 月美国底特律市 召开的第1 1 届国际人工智能学术会议中提出的，其目的是在数据库中发现不被人们所 知道的、潜在的知识和有用的信息。国际k d d 学术会议起初每两年召开一次，1 9 9 3 年后 则每年召开一次。 1 9 9 5 年在加拿大蒙特利尔召开第一届知识发现和数据挖掘国际学术会议，数据挖掘 这一术语被学术界正式提出，它为在海量数据中提取信息带来了新的希望。自1 9 9 5 年 太原理 ：人学硕士研究生学位论文 以来，国外在数据挖掘和知识发现方面的论文非常多，并己经成为了热门研究方向。数 据挖掘的技术历经了数十年的发展，己经形成了一些成熟的技术。这些技术和高性能的 关系数据库引擎以及广泛的数据集成，让数据挖掘技术在当前的数据仓库环境中开始进 入实用阶段。 此外，数据库、人工智能、信息处理、知识工程等领域的国际学术刊物也纷纷开辟 了k d d 专题或专刊。i e e e 的k n o w l e d g ea n dd a t ae n g i n e e r i n g 会刊首先在1 9 9 3 年出版 了k d d 技术专干u ，所发表的5 篇论文代表了当时k d d 研究的最新成果和动态。随后，各 类k d d 会议、研讨会纷纷涌现，许多领域的国际会议也将k d d 列为专题讨论。1 9 9 9 年， i e e e 和a c m 再次推出k d d 专刊，介绍数据挖掘在各个领域的应用成果。 不仅如此在i n t e r n e t 上还有不少k d d 电子出版物，其中以半月刊k n o w l e d g e d i s c o v e r yn u g g e t s 最为权威，在h t t p ：w w w k d n u g g e t s c o m 中，可以下载各种数据 挖掘工具软件和数据挖掘相关的资料。 目前，国外数据挖掘的发展趋势和研究方向主要有：传统的统计学回归法在k d d 中 的应用：数据挖掘( k d d ) 与数据库的紧密结合。在应用方面包括：数据挖掘( k d d ) 商 业软件工具不断产生和完善，注重建立解决问题的整体系统，而不是孤立的过程。用户 主要集中在银行、保险、电信、销售业。国外的许多计算机公司也非常重视数据挖掘的 开发应用，i b m 和m i c r o s o f t 都成立相应的研究中心进行这方面的工作。很多著名的计 算机公司开始尝试开发数据挖掘( k d d ) 方面的软件开发，比较典型的有s a s 公司的 e n t e r p r i s em i n e r 。i b m 公司的i n t e l l i g e n t m i n e r ，s g i 公司的s e t m i n e r ，s p s s 公司 c l e m e n t i n 等等。w e b 数据挖掘产品有n e tp e r c e r p t i o n s ，a c c r u e l n s i g h t 和a c c r u eh i t l is t c o m m e r c et r e n d s 等“) 。 与国外相比，国内对数据挖掘( k d d ) 的研究稍晚，目前进行的大多数研究项目是 由政府资助进行的，如国家自然科学基金、8 6 3 计划等。1 9 9 3 年国家自然科学基金开始 对数据挖掘研究进行支持。1 9 9 4 年4 月在北京召开的第三届亚太地区k d d 国际会议 ( p a k d d 9 9 ) 响应热烈，共收到论文1 5 0 多篇。国内从事数据挖掘的人员主要集中在大学 和研究所。所涉及的研究领域很广，对学习算法的研究和数据挖掘的实际应用及数据挖 掘理论方面的研究占了很大的比重。但是，到目前为止，国内还没有比较成熟的数据挖 掘产品0 1 。 2 太原理t 大学硕十研究生学位论文 1 2 数据挖掘过程 1 2 1 数据清理 数据清理也称为数据清洗，是在数据中消除错误和不一致，识别孤立点，以及消除 噪声的过程。数据清理包括空值处理、噪声数据处理以及不一致数据处理等。数据清理 主要针对多个数据源中数据的不规范性、二义性、重复和不完整性等问题，对有问题的 数据进行相应的清洗操作，去除噪声和干扰数据。 1 2 2 数据集成 在数据挖掘中对数据进行集成，也就是将多个数据源中的数据合并存放在一个统一 的数据存储中。数据集成将多个数据源中的数据进行合并处理，解决语义模糊性并整合 成一致的数据存储。数据集成涉及模式集成、冗余、数据值冲突的检测与处理三个方面。 模式集成就是从多个异构数据库、文件或遗留系统提取并集成数据，解决语义二义性， 统一不同格式的数据，消除冗余、重复存放数据的现象。数据集成往往导致数据冗余，； 对于这种现象可以使用相关分析检测到，然后将其消除。由于表示、比例、编码等不同， 现实世界中的同一实体，在不同数据源中的属性值可能不同，这种数据语义上的歧义性 是数据集成的最大难点。 1 2 3 数据选择 数据挖掘通常并不需要使用所拥有的全部数据，有些数据对象和数据属性对建立模 型获得模式是没有影响的，这些数据的加入会在一定程度上影响数据挖掘的效率，甚至 还会导致挖掘结果的偏差，因此有效地选择数据是很有必要的。 数据选择是在选择目的和数据内容本身特点的基础上，寻找依赖于发现目标的有用 特征，以缩减数据规模，从而在尽可能保持数据原貌的前提下最大限度地精简数据量。 通过数据选择可以使得数据的规律性和潜在特性更加明显。 1 2 4 数据变换 数据变换是把原始数据通过某种变换，转化成为适合挖掘的表达形式。数据变换包 太原理t ：人学硕十研究生学位论文 括数据离散化、转换变量、拆分数据、格式变换等内容。通过数据变换可以把原有的、 难以处理或者难以理解的数据变化成为易于处理，易于挖掘的形式，为进一步的挖掘工 作带来方便。 1 2 5 数据挖掘 数据挖掘算法具体的执行阶段是整个数据挖掘过程的核心环节。它是通过建立模 型，使用智能的方法提取数据的有趣模式。数据挖掘中的建模实际上就是利用已知的数 据和知识建立一种模型，这种模型可以有效地描述已知的数据和其中包含的知识。因此， 数据挖掘步骤就是按照人们预先设计的模型对数据进行处理、分析、预测的过程。 1 2 6 模式评估 数据挖掘发现的模式应该是有用的，可理解的。因此需要解释发现的模式，去除多 余的或者没有应用价值的模式，把结果转化成某个有用的、便于用户理解的形式。模式 评估就是以某种兴趣度为量度，识别表示知识的真正有趣的模式。其中一种评估方法是 使用实际运行环境中的当前数据进行检验，另一种是直接使用原先建立的数据库中的数 据来进行检验，也可另找新的测试数据来进行验证。因此整个挖掘过程实际上是一个不 断反馈的过程。 1 2 7 知识表示 在挖掘出有用的模式后，通过使用可视化和知识表示技术，向用户提供挖掘的知识。 数据挖掘中的可视化方法使数据挖掘的过程能够被用户解，也便于在数据挖掘的过程中 进行人机交互，使用户能够参与指导挖掘过程。数据挖掘的可视化包括数据的可视化、 数据挖掘过程的可视化、数据挖掘结果的可视化。将可视化技术融入数据挖掘的各个步 骤当中，可以使用户直观地的看到数据处理的个过程，检测并控制数据挖掘的整个过程。 这不仅有助于数据挖掘结果表示，也有助于数据挖掘本身的成功进行。 1 3 数据挖掘中分类方法 根据数据挖掘的任务的不同，可以将数据挖掘的模式分为以下几种：分类模式、预 4 太原理工大学硕士研究生学位论文 测模式、关联规则模式、回归模式、聚类模式、时间序列模式等”1 。 本文针对数据的分类问题进行研究，因此重点分析数据挖掘中对分类的研究状况。 分类的目的是提出一个分类函数或分类模型( 即分类器) ，通过分类器将数据对象映射到 一个给定的类别中。数据分类可以分为两步进行。第一步建立模型，用于描述给定的数 据集合。通过分析由属性描述的数据集合来建立反映数据集合特性的模型。这一步也称 作有监督的学习，导出模型是基于训练数据集的，训练数据集是已知类标记的数据对象。 第二步使用模型对数据对象进行分类。首先应该评估模型的分类准确度，如果模型准确 度可以接受，就可以用它来对未知类标记的对象进行分类。现阶段分类模式中比较常用 的方法有以下七种： 1 3 。1 决策树 决策树( d e c i s i o nt r e e ) 学习是以样本为基础的归纳学习方法。将决策树转换成 分类规则比较容易。决策树的表现形式是类似于流程图的树结构，在决策树的内部节点 进行属性值测试，并根据属性值判断由该节点引出的分支，在决策树的叶节点得到结论。 内部节点是属性或属性的集合，叶节点代表样本所属的类或类分布。决策树学习的基本 算法是贪心算法，采用自顶向下的递归方式构造决策树。h u n t 等人于1 9 6 6 年提出的 概念学习系统c l s 是最早的决策树算法，以后的许多决策树算法都是对c l s 算法的改 进或由c l s 衍生而来。q u i n l a n 于1 9 7 9 年提出了著名的i d 3 方法。以i d 3 为蓝本的 c 4 5 是一个能处理连续属性的算法。其他决策树方法还有i d 3 的增量版本i d 4 和i d 5 等。强调在数据挖掘中有伸缩性的决策树算法有s l i q 、s p r i n t 、r a i n f o r e s t 算法等。 s l i q 采用预排序技术来克服将所有数据放入内存的方法，从而能处理更大的数据库， 并用了m d l 剪枝算法，使树更小和精度更高。s p r i n t 引入了并行算法的方式，具有良 好的可扩展性。 1 3 2a 0 1 1 关联规则 m i c h a l s k i 于1 9 8 0 年提出的a q l l 机器学习算法的原理相当简单：它将对样本集 的学习问题变换为逻辑演算，具体地说，令一组具有相同类别的样本作为正样本，其它 样本作为反样本，将所有正样本和反样本构成析取式，并令反样本的析取式为非，再取 它与正样本的合取。考虑一个正样本的情况，使用分配律与吸收律变换上述逻辑公式为 太原理j i ：人学项 ：研究生学位论文 析取式，它就是这个正样本的约简空日j 。对机器学习而言，分配律与吸收律起着重要的 作用，分配律可以使正样本与反样本之问产生互补对，这样的子句可以从逻辑公式中删 除，而不影响逻辑公式的真值，从而获得简化的表示；吸收律更为重要，在逻辑上，约 简的本质就是吸收所有冗余的原子。使用以分配律和吸收律为基础的算法解决海量数据 的学习，将不是一件轻松的事情，为此，1 9 8 6 年洪家荣教授提出了一种重要的改进算法， 他称其为扩展矩阵方法- - a e l l 。a e l l 不使用分配律，而是将正样本与反样本一一比较， 并将属性值不同的反样本的值作为称之为扩展矩阵的一个元素，这个方法和基于分配律 的方法是等价的。王珏研究员指出，利用区分矩阵原理可以描述a q l l 算法和i d 3 算法， 并且进一步提出了基于属性序的算法，给定一个属性序，该算法对p a w l a k 约简完备且 对这个给定的属性序唯一。 1 3 3 贝叶斯分类 贝叶斯分类是一种统计学分类方法，可以预测类成员关系的可能性，如给定样本属 于一个特定类的概率。朴素贝叶斯分类( n a i v eb a y e sc 1 a s s i f i c a t i o n ) 又称为简单贝 叶斯分类( s i m p l eb a y e s i a nc l a s s i f i c a t i o n ) 。它将训练样本1 分解成特征向量x 和 决策类别变量c 。假定一个特征向量的各分量相对于决策变量是独立的，也就是说各分 量独立地作用于决策变量。这一假定叫作类条件独立。作此假定是为了简化计算，所以 称为“朴素的”。一般认为，只有在满足类条件独立的情况下，朴素贝叶斯分类才能获 得精确最优的分类效果；在属性相关性较小的情况下，能获得近似最优的分类效果。这 种假定不仅以指数级降低了贝叶斯网络的复杂性，而且在许多实际应用领域，即使违背 这种假定，朴素贝叶斯分类也表现出相当的健壮性和高效性。在某些领域，朴素贝叶斯 分类的性能与神经网络和决策树的分类性能相当。朴素贝叶斯分类假定类条件独立，这 一假定简化了计算。与其他分类算法相比，当类条件独立假定成立时，朴素贝叶斯分类 是最精确的。 1 3 4 支持向量机 支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 是v a p n i k 根据统计学习理论提出的 一种新的学习方法，支持向量机理论的最大特点是根据v a p n i k 结构风险最小化准则， 尽量提高学习机的泛化能力，即由有限的训练集样本得到的小的误差能够保证对独立的 6 太原理工大学硕士研究生学位论文 测试集仍保持小的误差。 s v m 的基本思想是针对两类分类问题，在高维空间中寻找一个超平面作为两类的划 分，以保证最小的分类错误率。s v m 的一个重要的优点是可以处理线性不可分的情况。 用s v m 实现分类，首先要从原始空间中抽取特征，将原始空间中的样本映射为高维特 征空间中的一个向量，以解决原始空间中线性不可分的问题。不同的实际问题具有不同 的输入空间。用s v m 求解问题，在训练过程中要解一个二次优化问题，因而时间复杂 度较大，但其分类正确率往往高于其它方法。 1 3 5 神经网络 人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k ，简称a n n ) 是指由简单计算单元组 成的广泛并行互联的网络，能够模拟生物神经系统的结构和功能。组成神经网络的单个 神经元的结构简单，功能有限。但是，由大量神经元构成的网络系统可以实现强大的功 能。最早的形式化神经元数学模型是m - p 模型，由美国心理学家m c c u l l o c h 和数理逻 辑学家p i t t s 合作，于1 9 4 3 年提出。1 9 4 9 年，心理学家h e b b 提出通过改变神经元 连接强度，达到学习目的的h e b b 学习规则。1 9 5 8 年，计算机科学家r o s e n b l a t t 提 出感知器( p e r c e p t r o n ) 的概念，掀起人工神经网络研究的第一次高潮。但是，1 9 6 9 年， 人工智能专家m i n s k y 和p a p e r t 在p e r c e p t r o n 一书中表示出对这方面研究的悲观 态度，指出感知器只能用于线性分类问题，甚至连简单的异或运算都无法实现。另外， 冯诺伊曼串行计算机的发展，使多数学者忽视了发展人工智能新途径的必要性。人工 神经网络的研究转入低谷。虽然如此，仍有不少研究者对人工神经网络进行了不懈的研 究。g r o s s b e r g 和c a r p e n t e r 提出了自适应共振理论a r t 网络。k o h o n e n 提出了自组 。织映射网络。f u k u s h i m a 提出了神经认知机模型。1 9 8 2 年，美国加州工学院的生物物理 学家h o p f i e l d 进行了开创性的工作，提出b o p f i e l d 网络模型，该模型可以用电路实 现。这标志着神经网络研究高潮的再次兴起。1 9 8 5 年，r u m e l h a r t 等人提出了b p 算 法。同年，h i n t o n 等人提出了b o l t z m a n 机模型。人工神经网络在模式识别、计算机 视觉、智能控制、信号处理、语音识别、知识处理、机器学习、数据挖掘等领域有着广 泛的应用前景。 7 太原理l ：人学硕十研究生学位论文 1 3 6 基于遗传算法的分类 遗传算法( 6 e n e t i ca l g o r i t h m ，简称6 a ) 是模拟生物进化过程的计算模型，是自 然遗传学与计算机科学相互结合、相互渗透而形成的新的计算方法。遗传学习开始时， 首先创建一个由随机产生的个体组成的初始群体，每个个体可以用一个二进制符号串表 示。根据适者生存原则，形成由当前群体中最优的个体组成的新的群体，并生成这些个 体的后代。个体的优劣由适应度函数给出，后代通过选择算子、交叉算子和变异算子生 成。整个过程直到群体进化到每个个体都满足指定的适应度阈值为止。遗传算法易于并 行，已经广泛应用于分类和优化问题。 1 3 7 基于粗糙集的分类 粗糙集理论是波兰数学家z p a w l a k 在1 9 8 2 年提出的一种分析数据的数学理论。它 是利用上、下近似集来处理不确定性问题0 1 。粗糙集理论用于发现分类规则的基本思想 是：首先根据决策属性的不同取值，将数据分成不同的类别，并且生成判断规则；然后 再利用粗糙集的规则发现算法获取分类规则。基于粗糙集的分类算法简单，易于操作， 但是利用粗糙集的分类算法所生成的规则有可能不完整。 粗糙集作为一种软计算方法，可以克服传统不确定处理方法的不足，并且和其他软 计算方法能有机地结合进一步增强对不确定、不完全信息的处理能力。目前，在国内外 都有学者将粗糙集和其他的学科相结合，如粗糙集和信息论、粗糙集和遗传算法及粗糙 集和神经网络相结合，不过研究的还不是很多“1 。当然对粗糙集理论和其他学科结合的 机构和个人远不止这些，还有许多，在此就不一一列举。 1 3 8 分类方法的评估 对分类法的准确性进行评估是有实际意义的。一方面，有利于评估、比较不同的分 类方法；另一方面，可以估计给定的分类方法对未来的数据正确标号的准确率。分类模 型的评估是一个正在被研究的重要领域，已经成为备受关注的课题。使用训练数据导出 分类法，然后仍然在训练数据集上评估分类法的分类精度，可能导致低估分类法对未来 数据的错误分类率。这是由于模型对训练数据的过分特化造成的。为了解决这一问题， 一种显然的做法是在一个新的样本集中评估分类精度，这个新的样本集称为测试集。常 见的方法有保持方法、留一法、自展法、k _ 折交叉验证等。 太原理工大学硕士研究生学位论文 改进分类法精度的技术主要有两种：装袋( 或引导聚集) 和推进。除精度外，还 可以根据分类法的训练时间、鲁棒性、可伸缩性、可解释性等对分类法进行此较。现在 尚未发现哪一种方法对任何数据都优于其他方法。分类模型的性能只是在选择分类法时 要考虑的一个方面，另一个方面是分类法适合数据的程度。 1 4 本文研究内容 分类算法与分类规则提取是数据挖掘领域中的一个非常重要的研究课题。数据挖掘 的目标是采用有效的算法从大量现有的数据集合中发现并寻找未知的、潜在的有用信 息，并用浅显的语言或者形式来显示出来。而分类模式中关于粒度计算的数据挖掘技术 目前研究的人还不是很多，相应的研究成果也较少。因而基于粒度计算的数据挖掘技术 有待于更加深入的研究。 本文研究的主要内容是在分析粗糙集和粒度计算理论的基础上，提出了一种粒度层 次树的分类算法( ad e c i s i o nt r e e b a s eo ng r a n u l a rh i e r a r c h y ) 一g h d t 。传统的决策 树算法i d 3 和c 4 5 每次在选择属性时仅仅考虑一个不一致节点的信息。因此在传统的决 策树算法中不同的属性会出现在树的同一层中，同一属性也有可能出现在不同的层次 上。粒度层次树算法是在决策树的算法上改进而成的。在该算法中，每次选择属性都要 考虑同一层上所有不一致的节点。粒度层次树也是一个自顶向下，深度优先，基于粒度 层次的决策树。 各章的主要内容如下： 第一章对数据挖掘的产生与发展做出概括，并总结了分类模式的常用研究方法。 第二章介绍粗糙集和粒度计算有关理论和相关算法进行简单的介绍。 第三章介绍粒度计算在数据挖掘中应用，数据预处理阶段属性约简方面的粒度计 算、对基于粒度计算的属性分层约简算法进行简单讨论。 第四章对粒度层次树分类算法进行介绍。并提出了基于粒度层次树的分类规则提 取算法。 第五章实验及结果分析。对本文提出的算法进行验证，与其他的分类算法k n n 分类 算法、支持向量机分类算法、朴素贝叶斯分类算法和决策树算法相比较，并通过u c i 数 据库的若干数据集进行了验证。证明粒度层次树算法的有效性。 第六章对本文工作进行了总结并提出将进行研究的方向和工作展望。 9 太原理1 ：人学硕十研究生学何论文 第二章基于粗糙集的粒度计算理论介绍 粒度计算( g r c ) 是信息处理的一种新的概念和计算范式，它覆盖了所有有关粒度的 理论、方法、技术和工具的研究，主要用于处理不确定的、模糊的、不完整的和海量的 信息。粗略地讲，一方面它是模糊信息粒度理论、粗糙集理论、商空间理论、区间计算 等的超集，另一方面是粒度数学的子集。具体地讲，凡是在分析问题和求解问题中，应 用了分组、分类和聚类手段的一切理论与方法均属于粒度计算的范畴。本章主要是对基 于粗糙集的粒度计算理论进行简单的介绍叫”。 2 1 粗糙集理论 粗糙集作为一种处理不精确、不确定与不完全数据的数学理论，最初是由波兰数学 家z p a w l a k 提出的，它在数据库发现、数据挖掘、故障诊断等领域都得到了广泛的发 展。粗糙集理论是建立在分类机制的基础上的，它将分类理解为特定空间上的等价关系， 而等价关系又构成了对该空间的划分。粗糙集理论将知识理解为对数据的划分，每一个 划分的集合称为概念。粗糙集理论的主要思想是利用已知的知识，将不精确或不确定的 知识用己知的知识库中的知识来( 近似) 刻画。该理论与其他处理不确定或不精确问题理 论的最显著的区别是它无需提供处理数据集合之外的任何先验信息，所以对问题的不确 定性的描述或处理比较客观。粗糙集中的概念是呈现粒度结构的，所以粗糙集理论是粒 度计算的主要构造模型“。 2 1 1 信息系统 定义2 1 信息系统是s = ( c ，a ，圪，c ) ，其中( 厂为非空有限集合，称为全域。全域c 厂 的元素被称为对象或者实例。a = c u d ，c 是条件属性集合，即对象的特征，d 为决 策属性集合，称为对象的分类，c n d = a 。圪属性值的集合，v = ，) ，k 是 属性4 的值域。设4 是任一属性，玉是任一个对象，则厂( t ，口) 表示玉在口属性的取值。 信息系统可以表现为关系数据表的形式，适合在关系数据库中存储。 定义2 2 ( 不可分关系) 设信息系统s = ( u ，a ，k ，c ) ，在任意子集b a 上，如果 l o 太原理工大学硕士研究生学位论文 存在 ( ，咒) i 厂( t ，口) = f ( y j ，口) ，= 乃，口毋，称为不可分关系，记作i n d ( b ) 。 u i n d ( b 1 是指全域【，根据等价关系b 划分的所有等价类的集合。 在信息系统中，数据是以关系表的形式表示的，关系表的行对应研究对象，列对应 对象的属性，对象的信息是通过指定对象的各属性值来表达的。我们将一个属性对应一 个等价类，一个表可以看作是一族等价关系。 2 1 2 近似空间 假设u 是全域，u a ，r 是【，上的一个等价关系，则u r 构成了u 上的一个划分， 称k = ( u ，r ) 为u 中关于r 的近似空间。划分在某种程度上体现了知识分类的存在，它 表明在己知的有限信息条件下，某些对象具有相似性，它们之间是不可分的。 任意的x u 称为【，上的一个概, 念, ( c o n c e p t ) 。u 中的概念族c = 五，五，以) 称 为关于【，的知识( k n o w l e d g e ) ，其中五u ，蜀a ，蜀n 一= a ，i ，f = l ，2 ，n ， u 墨= u 。形式上，空集a 也视为一个概念。一个知识库是指u 上的一个分类族 k = ，r ) ，其中，r 是【，上的等价关系族。 定义2 3 设p r ，且p a ，p 中所有等价关系的交集n p 也是一种等价关系， 我们也记作n d ( p ) ，即 【】，2 _ = l 【x 】 ( 公式2 - 1 ) 其中【x 】，表示由p 所确定的包含有元素x 的等价类。 定义2 4 给定近似空间k = ( u ，r ) ，非空子族集p r 所产生的不可分辨关系 i n d ( p ) 的所有等价类关系的集合即u i n d ( p ) ，称为基本知识，相应的等价类称为基本 概念；特别地，若关系q r ，则关系q 就称为初等知识，相应的等价类就称为初等概念。 定义2 5 设k = ( u ，r ) 和k i - ( u ，q ) 为两个知识库，如果i n d ( p ) = i n d ( q ) ( 或 g p = u q ) ，则称k 和置是等价的，记作k z k 。若i n d ( p ) c i n d ( q ) ，则称知识p 是知识q 的细化。 l l 太原理工人学硕十研究生学位论文 在知识库k 上，有些类是可定义的，有些类是不可定义的，还有些类是可近似定义 的。设x u ，r 是u 上的等价关系，若x 是一些尺基本类的并集，则称x 是r 一可定 义的( r - d e f i n a b l e ) ，否则x 是r 一不可定义( r - u n d e f i n a b l e ) 的。r 一可定义集也称尺一 精确集( r - e x a c ts e t s ) ，r 一不可定义集也称r 一不精确集或r r o u g h 集( r i n e x a c t s e t s ， r - r o u g hs e t s ) 。 定义2 6 设r 是u 上的等价关系，对任意的x 【， 足( x ) = x e 【，： x 】。z ) 或足( x ) = u y e u r ：y 石) ( 公式2 - 2 ) 称为z 关于r 的下近似集( 1 0 w e ra p p r o x i m a t i o n ) ； r - ( 爿) = x u ： z 】。c x m r 一( x ) = u 】，w r ：y n x g ) ( 公式2 - 3 ) 称为x 关于r 的上近似集( u p p e ra p p r o x i m a t i o n ) 。 二元组( 足( x ) ，r 一( z ) ) 构成了一个r o u g h 集。 定理2 1 ( a ) x 是尺一可定义的当且仅当足