（计算机应用技术专业论文）基于粒度计算和遗传算法的数据挖掘算法研究.pdf

一 蠹i量i-g， 学位论文版权使用授权书 江苏大学、中国科学技术信息研究所、国家图书馆、中国学术期刊( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件和电子文档，可以采用影印、 缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一致， 允许论文被查阅和借阅，同时授权中国科学技术信息研究所将本论文编入中国 学位论文全文数据库并向社会提供查询，授权中国学术期刊( 光盘版) 电子杂 志社将本论文编入中国优秀博硕士学位论文全文数据库并向社会提供查询。 论文的公布( 包括刊登) 授权江苏大学研究生处办理。 本学位论文属于不保密 学位论文作者签名j 墩老 2 0 年6 只| 瞻 指导教师签名 象夕l | 年6 只l ( b 分类号卫隍窆兰 u d c 鲤垒 密级 公五 编号 ! q 垫窆s q 婴鲤垫 江薄大擎 硕士学位论文 基于粒度计算和遗传算法的数据挖掘算法研究 t h er e s e a r c ho nd a t am i n i n ga l g o r i t h mb a s e do ng r a n u l a r c o m p u t i n g a n dg e n e t i c a l g o r i t h m 指导教师挞麽 研究生姓名工塞童 申请学位级别亟专业名称i 土篡扭应用撞苤 论文提交日期2 q ! ! 生且论文答辩日期2 q ! ! 生鱼月 学位授予单位和日期 江菱太堂2 q ! ! 生鱼县 答辩委员会主席 詹丞照 评阅人 位论文 摘要 随着数据库技术的成熟和知识发现等领域技术的不断发展，数据 挖掘技术应运而生，并在越来越广阔的领域得到应用和发展。粗糙集 方法是一种重要的数据挖掘方法，是由波兰科学家z p a w l a k 教授于 1 9 8 2 年提出的一种处理不精确、不一致、不完整等各种不确定信息的 强有力的数学工具。其主要思想是在保持分类能力不变的前提下，通 过知识约简，导出问题的决策或分类规则，而且在没有提供任何先验 信息的前提下，其也能有效地处理和分析各种不确定数据信息，并从 中发现隐含的知识，揭示潜在的规律。近年来，粗糙集理论已经在数 据挖掘、决策分析、人工智能、模式识别等诸多领域都得到了成功的 应用。进一步探索更加高效的分类和属性约简算法是目前国内外研究 的热点。 本文将数据挖掘理论、粒度计算理论以及遗传算法理论三者有效 结合，对于如何改进决策树分类算法和属性约简算法进行了深入地研 究，主要工作包括以下几个方面： ( 1 ) 对数据挖掘( d a t am i n i n g ) 技术进行了总体上的概述，包括数据挖 掘的定义、研究的现状以及当前存在的问题、一般过程、主要研究方 法和技术，为在这一领域进行更深入的研究打下了良好的基础。在此 基础上对现有决策树分类算法和属性约简算法进行了综述，并对各种 现有算法进行了比较和分析。 ( 2 ) 提出一种基于属性支持度的决策树算法( d t b a s 算法) ，该算法首 先在粒度计算理论基础上提出了属性支持度的概念，然后将其作为决 策树构造中选取测试属性的标准。实验结果表明d t b a s 算法较i d 3 算法、c 4 5 算法分类精度更高、计算量更小。 ( 3 ) 提出一种基于改进的自适应遗传算法的属性约简算法( m g a a r 算法) ，该算法主要做了三点改进，引入了属性核以对随机产生的二进 基于粒度计算和遗传算法的数据挖掘算法研究 制初始种群加以限制，在适应度函数中引入了条件属性对决策属性的 支持度，并对交叉概率和变异概率进行了新的设定。通过实验分析表 明该算法大大减少了迭代次数。 关键词：数据挖掘，决策树，属性约简，属性支持度，自适应遗传算 法 t e c h n o l o g y a n d k n o w l e d g ed i s c o v e r y , t h ed a t am i n i n gt e c h n o l o g ye m e r g ea st h et i m e s r e q u i r e sa n do b t a i n st h ea p p l i c a t i o na n dd e v e l o p m e n ti nm o r ea n dm o r e a r e a s t h er o u g hs e tt h e o r yi sa ni m p o r t a n td a t am i n i n gm e t h o d ，i tw a s p r o v i d e db yt h ep r o f e s s o rz p a w l a ki n19 8 2 ，w h i c hi sas t r o n gd a t aa n a l y s i s t o o lt oh a n d l eu n c e r t a i n i n f o r m a t i o n ，s u c ha si m p r e c i s e ，i n c o n s i s t e n t ， i n c o m p l e t ea n ds oo n i t sm a i ni d e ai si n d u c i n gd e c i s i o n so rc l a s s i f i c a t i o n r u l e st h r o u g hk n o w l e d g er e d u c t i o nb yk e e p i n gt h ec l a s s i f y a b i l i t y n o t n e e d i n go t h e ri n f o r m a t i o n o r p r e v i o u sk n o w l e d g e ，t h i st h e o r y c a n e f f e c t i v e l yp r o c e s s a n d a n a l y z e a l lu n c e r t a i n d a t a ，t h e nm i n e l a t e n t k n o w l e d g ea n du n c o v e rl a t e n c yr u l e i nr e c e n ty e a r s ，t h er o u g hs e tt h e o r y h a sa c h i e v e ds u c c e s s f u l a p p l i c a t i o ni nd a t am i n i n g ，d e c i s i o na n a l y s i s ， a r t i f i c i a l i n t e l l i g e n c e ，p a t t e r nr e c o g n i t i o n t oe x p l o r e m o r ee f f i c i e n t c l a s s i f i c a t i o na n da t t r i b u t er e d u c t i o na l g o r i t h m sa r eh o tr e s e a r c hd i r e c t i o n i nf u t u r e f o c u so nd a t am i n i n ga n dg r a n u l a r c o m p u t i n gt h e o r y , t h et h e s i s m a i n l ym a d et h ef o l l o w i n gc o n t r i b u t i o n s f i r s t l y , t h ed e f i n i t i o ni nd a t am i n i n g ，c u r r e n tr e s e a r c hs t a t u s ，m a i n p r o b l e m s ，b a s i cp r o c e s s ，m a i nr e s e a r c hm e t h o d sa n dt e c h n o l o g ya n ds oo n a r ed e s c r i p t e di nt h et h e s i s ，w h i c hl a y sat h e o r e t i c a lf o u n d a t i o nf o rf u r t h e r r e s e a r c h t h e n e x i s t i n ga l g o r i t h m so fd e c i s i o nt r e e c o n s t r u c t i o na n d a t t r i b u t er e d u c t i o na r ea n a l y z e di nd e t a i l s e c o n d l y , b a s e do nr 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 i n gt h e o r y , t h ep a p e r p r o p o s e sac o n c e p to fa t t r i b u t es u p p o r td e g r e e ，a n dt a k e si ta st h e c r i t e r i af o rc h o o s i n gr e a s o n a b l ea t t r i b u t e s ，a n dt h e nan o v e ld e c i s i o nt r e e c o n s t r u c t i o na l g o r i t h m ，n a m e l y , d t b a si sp r e s e n t e d t h ee x p e r i m e n t s i i l 基于粒度计算和遗传算法的数据挖掘算法研究 s h o wt h a t ，c o m p a r e dw i t hi d 3a n dc 4 5m e t h o d s ，t h ea l g o r i t h mh a sb e t t e r a c c u r a c ya n dl e s sc o m p u t a t i o n t h i r d l y , t h et h e s i sp r e s e n t sa ni m p r o v e da t t r i b u t er e d u c t i o na l g o r i t h m t h e r ea r et h r e e i m p r o v e m e n t so ft h ea l g o r i t h m ，i nw h i c ht h e i n i t i a l p o p u l a t i o no fb i n a r yc o d ei sr e s t r i c t e db ya t t r i b u t ec o r eo fd e c i s i o nt a b l e ， t h ef i t n e s sf u n c t i o ni nt h ea l g o r i t h mi sd e f i n e da c c o r d i n gt ot h ea t t r i b u t e s u p p o r td e g r e et h a tc o n d i t i o na t t r i b u t ef o rd e c i s i o na t t r i b u t e ，t h ea d a p t i v e c r o s s o v e rp r o b a b i l i t ya n da d a p t i v em u t a t i o np r o b a b i l i t ya r ea l s oi m p r o v e d t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h em e t h o d g r e a t l yr e d u c e st h en u m b e r o fi t e r a t i o n k e yw o r d s ：d a t a m i n i n g ，d e c i s i o nt r e e ，a t t r i b u t e sr e d u c t i o n ，a t t r i b u t e s u p p o r td e g r e e ，s e l f - a d a p t i v eg e n e t i ca l g o r i t h m 第1 章绪论。 1 1 研究的背景及意义1 1 2 国内外研究现状2 1 3 数据挖掘的任务及常用的技术3 1 3 1 数据挖掘的任务3 1 3 2 数据挖掘的常用技术4 1 3 3 数据挖掘技术实施的步骤5 1 4 本文的工作5 1 5 本文的组织6 第2 章粗糙集和粒度计算理论。8 2 1 粗糙集理论8 2 1 1 基本概念8 2 1 2 知识的分类1 1 2 1 3 算例1 2 2 2 粒度计算理论1 4 2 2 1 粒度计算的定义1 4 2 2 2 粒度计算的基本概念1 4 2 2 3 粒度计算的基本成分1 5 2 2 4 粒度计算的基本问题1 7 2 3 本章小结一1 8 第3 章遗传算法2 0 3 1 遗传算法的发展和现状2 0 3 2 遗传算法的基本概念2 1 3 3 遗传算法的基本操作2 1 3 3 1 选择操作2 1 3 3 2 交叉操作2 3 3 3 3 变异操作2 3 3 4 适应度函数2 4 3 5 基本遗传算法的实现2 4 3 5 1 遗传算法的基本框架2 4 3 5 2 遗传算法的算法描述2 5 3 6 本章小结2 6 第4 章基于改进的自适应遗传属性约简算法2 7 4 1 属性约简的一般方法2 7 v 基于粒度计算和遗传算法的数据挖掘算法研究 4 1 1 基于分辨矩阵的属性约简算法2 7 4 1 2 基于信息熵的属性约简算法2 9 4 1 3 基于属性依赖度的属性约简算法3 0 4 1 4 基于遗传算法的属性约简算法3 1 4 1 5 属性约简算法的比较3 1 4 2m g a a r 算法的设计3 2 4 2 1 属性支持度的提出。3 2 4 2 2 编码方法3 2 4 2 3 适应度函数的设计3 3 4 2 4 选择算予的选取3 3 4 2 5 交叉算子的选取3 4 4 2 6 变异算子的选取3 4 4 2 7 交叉概率和变异概率的自适应确定3 4 4 2 8m g a a r 算法描述3 5 4 2 9 实验分析3 5 4 3 本章小结3 8 第5 章基于粒度计算理论的决策树学习新方法4 0 5 1 决策树算法4 0 5 1 1 决策树算法的基本思想4 0 5 1 2 决策树算法的基本流程4 1 5 1 3 决策树算法的性能评价4 2 5 2 经典决策树算法分析与比较4 2 5 2 1i d 3 算法4 2 5 2 2c 4 5 算法4 3 5 2 - 3 其他决策树算法4 3 5 2 4 决策树算法比较4 5 5 3 基于属性支持度的决策树学习算法( d t b a s 算法) 4 5 5 3 1 属性选择原理4 5 5 3 2d t b a s 算法描述4 6 5 3 3 实验分析4 7 5 4 本章小结4 9 第6 章总结与展望5 0 6 1 总结5 0 6 2 展望5 1 致谢5 2 参考文献5 3 攻读硕士期间发表的论文及所取得的研究成果 v i 5 6 学位论文 绪论 8 0 年代末开始逐步发展起来的一个新 的研究领域，它是一门交叉学科，其汇聚了数据库、数理统计、机器学习、人工 智能、数据可视化、并行计算等不同学科和领域。经过近2 0 年的研究发展，数据 挖掘开始逐渐走向成熟，并正向着更深入的方向发展。 1 1 研究的背景及意义 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们利用信息 技术生产和搜集数据的能力大幅度提高，无数个数据库被用于商业管理、科学研 究和工程开发、政府办公等领域，超级市场中的交易数据、加油站罩的汽油销售 数据、旅行社的旅游信息等等，均构成了数据库系统的信息来源。近些年来，数 据库所管理的数据量急剧增大，人们积累的数据越来越多。例如，美国n a s a 的 地球观测系统( e o s ) 每小时向地面发回约5 0 g b 的图像数据；美国沃尔玛零售系统 每天产生约2 亿条交易数据。人们希望能够对这些数据进行更深层次的分析，以 便更好地利用这些数据，挖掘出隐藏在其中的许多重要的信息。目前的数据库系 统可以高效地实现数据的录入、查询、统计等功能，但无法发现数据中存在的关 系和规则，无法根据现有的数据预测未来的发展趋势。缺乏挖掘数据背后隐藏的 知识的手段导致了“数据富有但知识缺乏 的现象【。而从这些数据中找出有用信 息又是人力所不能及的，因此，人们急切需要一种能够智能地、自动地把数据转 成有用信息和知识的技术和工具，通过对信息系统进行深入分析，以便从海量的 数据中智能地、自动地抽取出有价值的知识或信息来帮助人们进行商业分析和科 学研究，这一过程即是数据挖掘，当然还有许多与其相近似的术语，如从数据库 中发现知识( 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 d d ) 、数据融合( d a t af u s i o n ) 、数据 分析以及决策支持等等。数据挖掘技术是解决数据丰富而知识缺乏的有效方法， 相关方面的研究以及应用极大提升了决策支持的能力，已被公认为数据库与数据 仓库应用研究中一个新兴的具有广阔应用前景的研究领域。 数据挖掘技术从一开始就是面向应用的，它要对这些数据进行微观乃至宏观 的统计、分析、综合和推理，以指导实际问题的求解，发现事件间的相互关联， 然后利用已掌握的信息对未来的活动进行预测，必须说明的是，数据挖掘所发现 的知识都是相对的，具有特定前提和条件约束，同时还应易于理解，所以发现的 基于粒度计算和遗传算法的数据挖掘算法研究 结果最好能用自然语言进行表达。 作为数据挖掘的数据预处理阶段，连续属性的离散化、属性的约简等操作都 会对最终的数据挖掘和知识发现产生重要的影响。正是由于数据库的数据量巨大、 记录繁杂，导致许多重要的有价值的知识隐藏其中，难以被发现。因此，如果能 通过一种方法将数据源中的数据进行约简，略除那些重复的、不重要的、不精确 的冗余属性，只保留其中能够说明问题的、重要的、简明的属性，就可以拨开云 雾，使知识相对明了，易于被挖掘出来。这正是人们所期望的、具有重要意义的 事情。 1 2 国内外研究现状 数据库中的知识发现和数据挖掘技术是随着数据库和人工智能技术的发展而 产生的，它首次出现于1 9 8 9 年8 月在美国举行的第1 1 届国际人工智能联合学术 会议上，随后知识发现和数据挖掘逐渐成为计算机领域的一个热门课题。1 9 9 5 年， 数据挖掘界在加拿大召开了第一届知识发现与数据挖掘国际学术会议，并在1 9 9 8 年建立了一个新的学术组织a c m s i g k d d 。数据挖掘界的专业学术期刊“d a t a m i n i n ga n dk n o w l e d g ed i s c o v e r y ”在1 9 9 7 年出版发行。还有众多国际学术期刊也 开始刊载知识发现与数据挖掘的论文。如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 会刊，a c m 数据库系统汇刊，a c m 杂志，信息系统，v l d b 杂志，数据与知识 工程，智能与信息系统国际杂志等【2 】。 当今，数据挖掘面临的问题与挑战主要有以下几个方面： 数据库：数据库可能是动态的，也可能是巨大的。 困难的训练集：无代表性的数据，无边界的例子，有限的信息。 噪音：可能由于数据丢失，属性值为空值、测试错误等原因所致。 到目前为止，数据挖掘的国际会议主要有：“a c m s i g m o d 数据管理国际会 议”( s i g m o d ) ，“超大型数据库国际会议( v l d b ) ，“a c m s i g m o d s i g a r t 数 据库原理研讨会 ，“数据工程国际会议 ，“扩展数据库国际会议 ，“数据库理论 国际会议 ，“信息与知识管理国际会议 ，“数据库与专家系统应用国际会议 ，“数 据仓库与知识发现国际会议 ，“数据库系统高级应用国际会议 ，“知识发现与数 据挖掘太平洋亚洲会议 ，“数据库中的知识发现原理与实践欧洲会议，“机器学 习国际会议”，“a c m 计算学习理论会议 ，“人工智能国际联合会议 ，“美国人工 智能学会会议 等。数据挖掘和知识发现已成为当前计算机领域的一大研究热点。 目前，世界上比较有影响的典型数据挖掘系统有：i b m 公司的i n t e l l i g e n t 2 江苏大学硕士学位论文 m i n e r ，s a s 公司的e n t e r p r i s em i n e r ，s g i 公司的s e tm i n e r ，s p s s 公司的c l e m e n t i n e ， s y b a s e 公司的w a r e h o u s es t u d i o ，r u l eq u e s tr e s e a r c h 公司的s e e s ，b u s i n e s so b j e c t s 公司的b o ，f o r d s y s t e m s 公司的c a r t ，此外还有c o v e rs t o r y ，e x p l o r a ， k n o w l e d g ed i s c o v e r yw o r k b e n c h ，d bm i n e r ，q u e s t 等【引。 与国外相比，国内对数据库中知识发现的研究比较晚，1 9 9 3 年国家自然科学 基金首次支持该领域的研究项目，目前8 6 3 ，9 7 3 以及地方自然科学基金都开始支 持数据挖掘项目，国内的许多科研单位和高等院校竞相开展知识发现的基础理论 及其应用研究，其中比较著名的有中科院计算所史忠植研究团队，复旦大学朱杨 勇开发团队，大量的研究单位也投入到知识发现与数据挖掘中来，如清华大学、 南京大学、四川大学、中科院自动化所、上海交通大学、西安交通大学、东北大 学等。知识发现和数据挖掘起步虽晚，但现在已经进入了空前高涨的研究氛围： 在知识发现与数据挖掘领域已经有多篇硕士、博士论文发表；国内目前虽没有专 业的知识发现与数据挖掘杂志，但计算机学报、软件学报、计算机研究与发展、 模式识别、控制与决策等杂志上均刊登有数据挖掘方面的论文；国内的知识发现 会议主要有“数据库学术会议 ，“计算机应用联合学术会议”，“中国机器学习学 术会议”等。 1 3 数据挖掘的任务及常用的技术 1 3 1 数据挖掘的任务 数据挖掘的任务是从数据中发现知识，这些知识按功能可分为两大类：预测 型和描述型。前者可以根据数据项的值精确预测某种结果；后者是对数据中存在 的规则作一种描述，或者根据数据的相似性将数据分组。根据发现知识的不同， 可以将数据挖掘的任务总结为以下几类【4 嗣。 1 ) 概念描述：概念描述是对某类对象的内涵进行概括，并对这类对象的相关 特征进行提取。概念描述分为两类：特征性描述和区别性描述，前者用于描述某 类对象的共同特征，后者用于描述对象之间的区别。 2 ) 关联规则挖掘：一组数据可能存在某种相关性或规律性，这种关系就成为 关联。关联分为以下几种：简单关联、时序关联和因果关联。关联规则分析就是 找出数据中的关联性。当两个或多个数据项的取值重复出现且概率较高时，它就 存在某种关联，可以建立这些数据项之间的关联规则。 3 ) 分类：根据已知的训练数据集建立模型，并用该模型对数据库中的数据进 行分类。分类是找出一个类别的概念描述，它代表了这类数据的整体信息。 3 基于粒度计算和遗传算法的数据挖掘算法研究 4 ) 聚类：数据库中的数据按照一定的距离或相似性把数据划分为若干子集， 它的目的是尽量减小相同类别的数据之间的差异，尽可能增大不同类别数据的差 异。其与分类方法的差异在于建立分类模型所用到的数据是已知其归属类别的， 而聚类则不然。 5 ) 趋势分析：利用历史数据找出变化规律，评估给定样本可能具有的属性值 或值区间，来预测未来数据的种类特征等。 6 ) 偏差检测：探测数据现状、历史记录或标准之间的显著变化和偏离。偏差 包括很大一类潜在的有用的知识。 1 3 2 数据挖掘的常用技术 为了完成数据挖掘的任务，人们常借助基础知识的研究成果和工具，提出了 很多的技术和方法，以下几种方法【6 】使用较为普遍。 1 ) 粗糙集理论：波兰数学家z p a w l a k 在1 9 8 2 年首次提出了粗糙集理论的概 念，这是一种研究不精确性和不确定性知识的数学工具。它不仅能够在缺少关于 数据的先验知识的情况下，仅仅以对观测数据的分类能力为基础，解决模糊或不 确定性数据的分析和处理，算法简单且易于操作。 2 ) 决策树方法：决策树是一种简单的知识表示方法，它首先利用训练集生成 一个函数，该函数根据不同的取值建立相应的分支，形成一棵决策树，最后再通 过剪枝技术把决策树转化为相应的规则。决策树算法的优点在于可以生成易于理 解的规则，计算量相对较小，可以处理联系和分类型的数据，并且能清晰的显示 出重要属性，缺点在于当类别过多时，错误会相应增多。 3 ) 遗传算法：遗传算法融合了自然进化的思想。二十世纪七十年代由美国的 j h o l l a n d 首先提出。其思想是创建一个由随机产生的规则组成的初始群体，模拟 生物进化的过程，将其中与现实情况最适合的规则组成新的群体，在这个群体中 用交叉和变异等手段产生新的规则，并继续对这个群体进行进化，直至满足设定 的阈值终止。这样就得到了许多可用于分类的规则，并使用这些规则对数据进行 分类。 4 ) 统计分析方法：统计分析方法利用概率、统计学原理对数据库中的数据进 行分析，从而得出它们之间的关系。 5 ) 神经网络方法：神经网络方法是根据人脑特征，模仿神经系统发展起来的 信息处理系统，以b p 网络为代表的前馈式神经网络。b p 算法的特点是信号单向 传输，相同神经元间不传递信息，神经元与其邻层神经元联系，其能够大规模实 4 江苏大学硕士学位论文 现信息的并行处理。善于分类和推理，但神经网络需要大量参数，需要人为地干 预，因此其适应性较差。 6 ) 可视化技术：这是一类辅助方法，它采用比较直观的图形图表方式将挖掘 出来的模式表现出来，数据可视化大大发展了数据的表达能力从而易于为人们所 理解，这在数据挖掘中非常重要。可视化技术正逐渐受到人们广泛的关注。 7 ) 此外，数据挖掘的常用技术还有数据库方法、模糊神经网络、关联规则、 联机分析处理、模糊逻辑、公式发现等。 1 3 3 数据挖掘技术实施的步骤 数据挖掘不仅能对过去的数据进行查询和遍历，而且能够发现这些数据之间 的潜在联系，从而促进信息的传递。数据挖掘的一般过程包括以下五个步骤如图 1 1 f 4 l ： 1 ) 预处理数据：收集和净化来自数据源的信息，并加以存储，将其存放于数 据仓库之中。 2 ) 模糊搜索模型：利用数据挖掘工具在数据中查找模型，这个搜索过程可以 由系统自动执行，从上至下搜索原始数据以发现它们之间的某种联系，也可以加 入用户交互过程中，有分析人员主动发问，从上至下寻找已验证假设的正确性。 3 ) 评价输出结果：通常数据挖掘的搜索过程需要反复多次，在分析人员评价 输出结果后，他们可能会形成一些新的问题或要求对某一方面做更精细的查询。 4 1 生成最后的结果报告。 5 ) 解释结果报告：对结果进行解释，依据此结果采取相应的商业措施，这是 一个人工过程。 1 4 本文的工作 图1 1 数据挖掘的一般过程 f i g u r e l 1t h ep r o c e s so fd a t am i n i n g 数据挖掘技术是一种新的知识获取工具，已成功应用于社会生活的各个领域。 5 基于粒度计算和遗传算法的数据挖掘算法研究 随着信息资源的与同俱增，积累的数据量越来越大，使用单一的数据挖掘方法来 完成数据挖掘任务变得越来越不易，因此，探寻多方面知识和多方法的融合技术 已成为人们研究的重点。本文的工作就是在结合粒度计算理论、遗传算法等多方 面理论知识的基础上去探寻数据挖掘的新方法，具体内容如下： ( 1 ) 综述了数据挖掘的研究现状、目的及意义，讨论分析了数据挖掘的研究任 务、常用技术以及实施的步骤等。 ( 2 ) 深入分析了几种经典的决策树分类算法，详细介绍了各种算法的思想，并 在属性选择技术、并行性、伸缩性等方面对它们进行了分析比较。 ( 3 ) 详细介绍了现有的几种属性约简算法：基于分辨矩阵的约简算法、基于信 息熵的约简算法、基于属性依赖度的约简算法以及基于遗传算法的约简算法，深 入分析了各种算法的思想和时间复杂度，并对它们之间的优缺点进行了比较。 “) 基于条件属性和决策属性之间的依赖关系，提出了属性支持度的概念，并 将其作为决策树分裂属性的选择标准，继而提出了一种新的决策树构造算法 基于属性支持度的决策树构造算法( d t b a s ) ，并用实例和实验证明了其可行性。 ( 5 ) 提出了一种自适应遗传属性约简算法，该算法将粒度计算、遗传算法和属 性约简进行了有效的结合。首先，给出了各类遗传算子的设计和实现方法，并通 过引入属性核限制初始种群的生成，避免了盲目随机产生种群，大大减少了遗传 算法的搜索空间，并提高属性约简结果的准确性。然后给出了算法的基本思想， 最后通过实验证明了该算法能对各种数据集进行有效处理，并且优于其它遗传约 简算法。 1 5 本文的组织 本文章节及内容的安排如下： 第一章绪论。首先简要介绍了数据挖掘、粗糙集、粒度计算等理论研究的背 景、意义以及国内外研究的现状，然后论述了数据挖掘的任务、常用技术以及技 术实施的步骤，最后介绍了本课题研究的主要内容及组织结构。 第二章粗糙集和粒度计算理论。该章分为两部分，第一部分主要介绍了粗糙 集理论的相关概念如知识的定义、不可分辨关系、上下近似、正域、负域、边界、 约简、核、近似精度、知识的依赖性等。并通过对一个实例的分析、求解使得对 这些概念有更深入地理解；第二部分论述了粒度 计算的定义、相关概念、基本成分和基本问题等。 第三章遗传算法。首先介绍了遗传算法的研究现状和一些基本概念，然后论 6 位论文 最后又对遗传算法的实现进行了 第四章基于粒度计算理论的决策树学习新算法。本章将粒度计算理论应用于 决策树构造算法中，提出了d t b a s 算法，并进行了仿真实验验证。 第五章基于改进的自适应遗传属性约简算法。对提出的改进算法进行了详细 的描述和分析。首先，给出了各类算子的设计和实现方法，并通过引入属性核限 制初始种群的生成，然后给出了算法的基本思想，最后通过实验证明了该算法的 可行性。 第六章总结与展望。总结了本文的主要研究内容和研究工作中的重点、难点、 创新点，并指出了下一步研究工作的目标。 7 基于粒度计算和遗传算法的数据挖掘算法研究 第2 章粗糙集和粒度计算理论 粗糙集理论( r o u g hs e tt h e o r y ) 7 】是由波兰科学家z p a w l a k 在1 9 8 2 年首先提出 的，该理论是一种研究模糊、不精确、不确定知识的新型数学工具，它不仅能够 在缺少有关数据的先验知识的情况下，仅仅依对观测数据的分类能力为基础，进 行模糊或不确定性数据的分析和处理，而且算法简单，易于操作。粗糙集理论处 理的问题主要包括数据库中的数据约简、数据相关性的发现、数据中范式的发现 以及因果关系的发现。经过近三十年的研究，粗糙集理论已经在理论和实际应用 上取得了长足的发展。目前，它已经在医疗诊断、决策分析、信息检索、近似推 理、机器学习、图像处理等领域得到了较为成功的应用，成为数据挖掘与知识发 现的重要工具。 粒度计算( g r a n u l a rc o m p u t i n g ，缩写为g r c ) t 8 】是信息处理的一种新的概念和计 算范式，覆盖了所有有关粒度的理论、方法、技术和工具的研究，现己成为人工 智能领域研究的热点之一。2 0 世纪6 0 年代，美国著名数学家z a d e h 提出模糊集合 论，在此基础上，又于1 9 7 9 年首次提出并讨论了模糊信息粒度化问题，推动了模 糊逻辑理论及其应用的发展，但在当时未引起人们足够的重视。接着，z a d e h 在 1 9 9 6 年提出“词计算理论”【9 】这标志着模糊粒度化理论的诞生。其旨在解决利 用自然语言，进行模糊推理和判断，以实现模糊智能控制。随后，美国多特蒙德 大学的h e l m u tt h i e l e 教授于1 9 9 8 年发表了“词计算理论的语义模型”【1 0 1 ，促进了 词计算理论的发展。词计算理论对因特网上的海量信息资源的高效利用有着深远 的影响。基于z a d e h 的模糊集理论，进行粒度计算理论和方法的研究，已成为“粒 度计算”的重要研究方向之一。 2 1 粗糙集理论 2 1 1 基本概念 1 信息系统 定义2 1 馆息系统【1 1 1 ) ：有序四元组s = ( 叫，w ) 是一个知识表达系统，又称为 信息系统，其中，u 为一个有限非空对象的集合即论域；a 称为属性集，它是一个 有限非空属性集合；y = u k ，k 表示属性口的值域，= u xa y 的映射，对 a e a 8 学硕士学位论文 于v u 以ae a , ， 力吃，对于给定对象z ，f ( x , a ) 赋予对象x 在属性a 下的属性 值；通常我们称厂为信息函数或者是描述函数。若a 中的属性可分为两个不相交子 集的析取，即条件属性集c 和决策属性集d ，d 通常只有一个属性。如果对信息 系统s = ( 叫，v , f ) 满足有a = c u d ，c f q d 翊，则称该信息系统为决策信息系统，表 达决策信息系统的信息表称为决策表。 2 上近似与下近似 由于现有知识库中的知识的粒度，使得模糊概念无法用已有知识精确表示。 例如：集合( 概念) x 2 ，x 2 , x 3 在所给出的知识库k = u 尺 中是一个模糊的概念。虽然 该集合不能用k 中的知识精确表示，但可以通过定义k 中的一对精确概念近似地 表示i 这就是上近似集和下近似集。由于【形r = 物，x s ， x 2 , x 3 ， 拗 ， 对模糊概 念 x l ，场，均) 来说， x 2 , x 3 是包含于该集合的最大可定义集，f f i x l ，x 2 , x 3 , x s = x i ，奶) t j x 2 , x 3 是包含该集合的最小可定义集。 定义2 2 ( 上近似【1 1 】) ：设论域为u ，尺是u 上的一个等价关系，x 是u 的一 个子集，则上近似r x = 扛ui 【z knx f 2 j ，当且仅当【z 】rf lx a ，z 似。 显然r x 是根据知识r 、u 中一定能和可能归入x 的元素集合。 定义2 3 ( 下近似【1 1 】) ：设论域为u ，尺是u 上的一个等价关系，x 是u 的一 个子集，则下近似r x = 扛ui 【工k x ) ，当且仅当【工k x ，石丛。显然蟹 是根据知识r 、u 中一定能归入x 的元素集合。 3 正域、负域和边界域f 1 1 】 由上近似和下近似，可以得到正域( p o s i t i v er e # o n ) 、负域( n e g a t i v er e g i o n ) 和边界域( b o u n d a r yr e # o n ) 的概念。 定义2 4 ( 正域) ：集合x 相对于尺的正区域就是x 的下近似，即： p o s 月( x ) = 丛( 2 1 ) 定义2 5 ( 负域) ：集合x 相对于尺的负区域为： n e g 尺( x ) = u r x ( 2 2 ) 定义2 6 ( 边界域) ：集合x 相对于r 的边界域为： b n d 矗( x ) = r x 一蚪( 2 3 ) 由下近似和上近似的定义可知，在依据知识尺判断时，r x 是由必定属于x 的对象组成的集合；r x 是由可能属于x 的对象组成的集合；b n d r ( x ) 是由既不能 明确判断属于x ，也不能明确判断属于坝即u - x ) 的对象组成的集合； 7 ：j e 保则 是由一定不属于x 的对象组成的集合。 9 基于粒度计算和遗传算法的数据挖掘算法研究 一个集合x 互u 的下近似和上近似，将论域u 划分为三个不相交的区域：正 区域p o s ( x ) 、负区域鹏( x ) 和边界区域鹏( x ) ，如图2 1 所示。 ，一 、 、 、 、 h _ _ h _ 一 z? 三三 | | j | | l 一一_ l ? 江苏大学硕士学位论文 定义2 8 瞅立) 【1 2 j ：设i - - - ( u , a ) 是一个信息系统，如果每一个aca 都为a 中 必要的，则称a 为独立的；否则称a 为依赖的。 定义2 9 ( 依赖度) 1 2 1 ：数据归约中，属性p 对尺的依赖程度用( p ) 表示： ( p ) = i _ 麟l i u i ( 2 6 ) 定义2 1 0 ( 约简) 【1 2 】：设仁( 叫) 是一个信息系统，p ca 。如果尸是独立的， i ji n d ( p ) = n d 似) ，则称p 是a 的一个约简。 定义2 1 1 ( 核) 1 2 】：设，= ( 叫) 是一个信息系统，a 中所有必要关系组成的集合 称为a 的核，记作c o r e ( a ) ，它是表达知识必不可少的重要的属性集。即c o r e ( p ) = n r e d i p ) o 定义2 1 2 ( 知识的粗