（管理科学与工程专业论文）基于遗传算法的知识发现算法研究及应用.pdf

西安建筑科技大学硕士学位论文 基于遗传算法的知识发现算法研究及应用 专业：管理科学与工程 硕士生：赵玉秀 指导教师：云庆夏教授 摘要 随着数据在日常决策中的重要性越来越显著，人们对数据处理技术的要求也不断提 高，需要对数据进行更深层次的处理，以得到关于数据的总体特征以及对发展趋势的预 测。然而数据量爆炸性的增长使得现有的知识发现算法存在着一定的局限性，因此必须 对现有的算法进行改进或创建新的算法以适应时代之需。 遗传算法是模拟自然进化的通用全局搜索算法，它具有简单、通用、鲁棒性强和适 于并行处理的特点，为其他科学技术无法解决或难以解决的复杂问题提供了新的计算模 型。而今，交易数据库在不断地增大，花费在扫描整个数据库的时问会越来越长，效率 的低下促使我们必须寻找新的关联规则挖掘算法。因此，本文提出了a r m g a 算法， 并针对矿山事故数据库进行了简单的计算和分析，取得了很好的效果。 大家普遍认可：在数据挖掘技术中，决策树是在数据集上发现有价值模式的最高效 的方法之一。然而，当需要在大规模数据集上进行规则挖掘时，可比例缩放性和准确率 问题却无时不困扰着决策树算法，使它力不从心。为了在有限的计算能力内构建出高质 量的决策树、挖掘出实用的规则，本文提出了d t g a ( d e c i s i o nt r e eo ng e n e t i c a l g o r i t h m ) 算法，它是将随机采样技术、遗传算法和标准的决策树算法集成在一起而 生成的。该算法是使传统决策树算法的质量得到提高的一种有力方法。 本文分别对交叉和变异算予给出了新的定义，并取决策树在测试集上的分类准确度 作为种群中各树个体的适应值。通过在矿山数据集上进行试验研究，主要对平均计算时 间和分类准确度这两个指标进行了考察和分析，发现d t - g a 算法：即使在较低的采样水 平上也能获得标准决策树算法一样的分类准确度；无论初始种群质量如何，该算法都能 产生高准确度的决策规则，且结果具有一致性；该算法具有很好的比例缩放性，对大型 数据集的挖掘很有效。为更加适应实际的需求，本文还提出了d t _ g a 算法可做的改进， 并给出了改造后的c a 算法的大致描述。 关键词：知识发现，遗传算法，关联规则，决策树，采样技术 西安建筑科技大学硕士学位论文 r e s e a r c h & a p p h c a f i o no f a l g o r i t h m o f k d db a s e d0 1 1g a s p e c i a l t y ：m a n a g e m e n ts c i e n c ea n de n g i n e e r i n g p o s t g r a d u a t e ：z h a oy u x i u c o n d u c t o r ：p r o f y u nq i n g x i a a b s t r a c t w i t ht h ed e v e l o p m e n to fi m p o r t a n c eo fd a t ai no b rd a i l yd e c i s i o n s ，p e o p l ew i l ld e e p l y t h i r s tf o rb e t t e rm e t h o d so fd e a l i n gd a t a ，w h i c hc a nd e a lt h e s ed a t a si nd e e p e r1 e v e l sa n d o b t a i nt h eg l o b a lc h a r a c t e r sa sw e l la st h ep r e d i c t i o no fd e v e l o p m e n tt r e n d so nd a t a s e t s s i n c e a c c u m u l a t e dd a t aa r ee x p l o s i v ei n c r e a s i n g ，t h ee x i s t e da l g o r i t h m si nk d dh a v et h el i m i t a t i o n s a n di n s u f f i c i e n c i e s ，s of o rs a t i s f y i n gt h en e e d so ft h i sa r e aw em u s tt a k ea c t i o n st om e n d e x i s t e da l g o r i t h m so rt oc r e a t en e wo n e s g e n e t i ca l g o r i t h m st h a ts i m u l a t en a t u r a lo p t i m i z a t i o np r o c e s s e si sag l o b a ls e a r c h i n g m e t h o di nt h ep r o b l e ms p a c ew i t hm a n ya d v a n t a g e s ，s u c ha ss i m p l i t y 、u n i v e r s a l i t y 、 r o b u s t i o u s n e s sa n dt h ea b i l i t yo fp a r a l l e ld e a l i n g g ap r o v i d en o v e lc o m p u t i n gm o d e lf o r t h e s ec o m p l i c a t e dp r o b l e m st h a tc a nn o tb es o l v e do rh a r d l ys o l v e df o ro t h e rt e c h n o l o g y t h e s ed a y s ，a sd a t a si nd e a l i n gd a t a b a s e sa r es k y r o c k e t i n g ，t h eg l o b a lt i m eo fs c a n n i n gt h e w h o l ed a t a b a s ew i l lb e c o m el o n g e ra n dl o n g e r i tl e a d st ol o w e ra n dl o w e re f f i c i e n c y i ti s n e c e s s a r yt of m dn o v e la l g o r i t h mt om i n er e l a t i o n a lr e g u l a t i o n s i nt h i sa r t i c l e ，a r m g a a l g o r i t h mh a v eb e e nc o n s t r u c t e da n da p p l i c a t e dt ot h ea c c i d e n t i a ld a t a b a s ei nm i n e s t h r o u g h s i m p l ec o m p u t a t i o n a n da n a l y s i s ，w ef i n dt h a tt h er e s u l t sa r eg o o d d e c i s i o nt r e ea l g o r i t h m sh a v eb e e nw i d e l yr e c o g n i z e da so n eo ft h em o s te f f i c i e n tw a y s t of i n dv a l u a b l ep a t t e m si nl a r g ed a t as e t sf o rd a t am i n i n ga p p l i c a t i o n s h o w e v e r , s c a l a b i l i t y a n da c c u r a c yh a v eb e c o m em a j o rb u r d e n si nl a r g e s c a l ed a t am i n i n gw i t hr e s p e c tt od e c i s i o n t r e ea l g o r i t h m s i no r d e rt oc o n s t r u c th i g h - q u a l i t yd e c i s i o nt r e e sa n dm i n eu s e f u lr u l e sw i t h i n al i m i t e da n dr e a s o n a b l ea n l o u n to fc o m p u t i n gc a p a c i t y , i nt h i sd i s s e r t a t i o nw ep r o p o s ean e w a p p r o a c h ( c a l l e dd t _ g a ) t h a ti n t e g r a t e ss t a t i s t i c a ls a m p l i n g ，g e n e t i ca l g o r i t h ma n dd e c i s i o n t r e ea l g o r i t h m st og e n e r a t eh i 曲一q u a l i t yd e c i s i o nt r e e s o u ra p p r o a c hi sap o w e r f u la l g o r i t h m n 西安建筑科技大学硕士学位论文 t h a tc a r lb eu s e dt oi m p r o v et h eq u a l i t yo f t r a d i t i o n a ld e c i s j o nt r e ea l g o r i t h m s i nt h i sp a p e r , t h en e wc r o s s o v e ra n dm u t a t i o no p e r a t i o n sh a v eb e e nd e f i n e d ，a tt h es a m e t i m ec l a s s i f i c a t i o na c c u r a c yo fd e c i s i o nt r e e so nt e s td a t a s e ti su s e da st h e i rf i t n e s s e s r e s p e c t i v e l y w ec o n d u c ts o m ec o m p u t a t i o n a le x p e r i m e n t sa n da n a l y z et h e mo nd a t a s e t so f m i n ea c c i d e n t st ot e s tt h ep e r f o r m a n c eo f d t _ g a ( 、i t l lr e s p e c tt oc l a s s i f i c a t i o na c c u r a c ya n d a v e r a g ec o m p u t i n gs p e e d ) w ef i n dt h a to u ra p p r o a c ha c h i e v e st h es a l t l el e v e lo f c l a s s i f i c a t i o n a c c u r a c ya sas t a n d a r dd e c s i o nt r e ea l g o r i t h ma tl o w e rs a m p l i n gl e v e l s r e g a r d l e s so ft h e q u a l i t yo f t h es t a r t i n gt r e e s ，o u ra p p r o a c h p r o d u c e su n i f o r m l yh i # y a c c u r a t ed e c i s i o nr u l e s o u ra p p r o a c hi sl i k e l yt os c a l ew e l la n de f f e c t i v ef o rl a r g e - s c a l ed a t am i n i n g t os u i tt om o r e a c t u a ld e m a n d s ，t h i sa r t i c l em a k es o m es u g g e s t i o n sa b o u ti m p r o v i n gd t g aa n dp r o v i d e r o u g hd e s c r i p t i o no f r e c o n s t r u c t i v ec a m ma l g o r i t h m k e yw o r d 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 e s ，g e n e t i ca l g o r i t h m ，a s s o c i a t i o nr u l e s ， d e c i s i o nt r e e ，s a m p l i n gt e c h n i q u e i i 声明 本人郑重声明我所呈交的论文是我个人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果：也不包含本人或其他 人在其它单位已申请学位或为其它用途使用过的成果。与我一同工作的同 志对本研究所做的所有贡献均已在论文中作了明确的说明并表示了致谢。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 论文作者签名：起玉秀 日期：2 以寥、上、3 关于论文使用授权的说明 本人完全了解西安建筑科技大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布 论文的全部或部分内容，可以采用影印、缩印或者其它复制手段保存论文。 ( 保密的论文在论文解密后应遵守此规定) 论文作者签名：起玉季导师签名：侈么了日期：翮，f ) 注：请将此页附在论文首页。 窒耋至丝墼苎盔兰至圭茎堡篁圣 1 1 课题研究的目的和意义 1 绪论 随着数据在日常决策中的重要眭越来越显著，人们对数据处理技术的要求也不 断提高，需要能够对数据进行更深层次的处理，以得到关于数据的总体特征以及对 发展趋势的预测。过去，人们依靠经验、大量的计算和人脑的智慧来处理这些深层 次的信息，为决策提供技术支持。然而数据量爆炸性的增长使得传统的手工处理方 法逐渐变得不切实际了，现在的用户很难再像从前那样，自己根据数据的分布找出 规律，并根据此规律进行分析决策。而且对于象超市商品的销售记录、保险公司的 客户记录、医学上的成于上万份病历等等的这些天体数据来说，如果由手工处理的 话需要几十个人年，而且由于数据的繁杂，在由人工对数据进行处理过程中，很难 找出关于数据较为全面的信息，这样许多有用的信息仍然隐含在数据中而不能被发 现和利用，造成数据资源的浪费，更无法体现出信息的时间效应。由此便迫切需要 采用自动化程度高、效率好的数据处理方法来帮助人们更高效地进行数据分析，自 动发现数据中隐藏的规律或模式，为决策提供支持。知识发现( k n o w l e d g ed is c o v e r y i nd a t a b a s e s ，简称k d d ) 就是为迎合这种要求而产生并迅速发展起来的一门技术， 它是用于开发信息资源的一种新的数据处理技术。 数据挖掘技术是解决机器学习、模式识别、数据库技术等各种领域中的大型实 际应用问题而提出的一些工程性方法的集合，是知识发现过程中最重要的一环，主 要是为了从大型数据库中高效地发现隐含在其中的知识或规律，并为人类专家的决 策提供支持。其中关联规则发现、决策树分类和遗传算法是三种重要的数据挖掘技 术，本文主要是对这三种算法进行研究、构造新的混合算法。 在国外，一些专家开启了知识发现领域研究的先河，使得数据挖掘技术虽然起 步较晚，但是其发展速度却非常惊人，而近些年的研究就更加火热，可以说是硕果 累累、层出不穷，这引起了全世界科研界的注意，同时也影响到了我国。就国内而 言在这领域的研究开始于近几年，虽然在应用方面已取得了一定的成果，但在算法 和理论研究方面还大大落后于国外，需要进步的发展。因此需要我们共同的努力， 将国内智能化科技推向一个新的高潮，本人正是怀着这样的激情来工作的。 1 2 国内外研究的现状及水平 1 2 国内外研究的现状及水平 西安建筑科技大学硕士学位论文 一、遗传算法的研究现状及水平 遗传算法既是一种自然进化系统的计算模型，也是一种通用的求解优化问题的 适应性搜索方法。从整体上来讲，遗传算法是进化算法中产生最早、影响最大、应 用也比较广泛的一个研究方向和领域，经过3 0 多年的发展，己成为个多学科、多 领域的重要研究方向。众多的研究单位和频繁的国际学术活动集中反映了遗传算法 的学术意义和应用价值。按照生物学上可进化性的概念，遗传算法所追求的是当前 群体产生比现有个体更好个体的能力，即遗传算法的可进化性或称群体可进化性。 因此，遗传算法的理论和方法研究也就围绕着这一目标展开。关于下面五个问题的 回答，就成为g a 理论研究的主要方向： 1 ) 遗传算法如何更好地模拟复杂系统的适应性过程和进化行为? 2 ) 遗传算法在优化问题求解中怎样才能具备全局收敛性? 3 ) 遗传算法的搜索效率如何评价? 4 ) 遗传策略的设计与参数控制的理论基础是什么? 5 ) 遗传算法与其他算法的如何结合? 其中，遗传策略包括g a 流程设计、群体设定、群体初始化、g a 算子、终止条 件等，广义上的遗传策略还包括遗传算法与其他算法结合形成的混合算法。目前， 还没有一种通用的方法，可以根据要解决的问题自动地设置高效的控制参数，只能 根据经验和多次运行遗传算法的结果进行人工设置和修正。需要指出的是，关于遗 传算法的第1 ) 个问题的研究主要是h o l l a n d 的团队和s a n t af ei n s t i t u t e 的e v c a 研究组等少数单位。大部分研究机构的研究主要集中于遗传算法和进化算法作为优 化问题通用求解算法的一系列问题。 遗传算法的基础理论主要以收敛性分析为主，即群体收敛到优化问题的全局最 优解的概率。从整体上讲，可以分为基于随机过程的收敛性研究和基于模式理论的 收敛性分折，我们将前者称为遗传算法的随机模型理论( s t o c h a s t i cm o d e l i n g ) ， 后者称为遗传算法的进化动力学理论( e v o l u t i o nd y n a m i c s ) 。 作为一种算法，遗传算法在各种问题的求解和应用中展示了它的特点和魅力。 从产生至今它不断扩展应用领域，比如工程设计、制造业、人工智能、计算机科学、 生物工程、自动控制、社会科学、商业和金融等，同时应用实践又促进了遗传算法 的发展和完善，使其成为2 1 世纪有关智能计算中的关键技术之一。随着应用领域的 扩展，遗传算法的研究出现了几个引入注目的新动向： 一是基于遗传算法的机器学习，这一新的研究课题把遗传算法从历来离散的搜索空 间的优化搜索算法扩展到具有独特的规则生成功能的机器学习算法，这一新的 西安建筑科技大学硕士学位论文 学习机制对予解决人工智能中知识获取和知识优化精练的瓶颈难题带来了希 望； 二是遗传算法正日益和神经网络、模糊推理以及混沌理论等其它智能计算方法相互 渗透和结合，这对开拓2 1 世纪中新的智能技术将具有重要的意义： 三是并行处理的遗传算法的研究十分活跃。这一研究对遗传算法本身的发展，而且 对于新一代智能计算机体系结果的研究都是十分重要的； 四是遗传算法和另一个称为人工生命的崭新研究领域正不断渗透； 五是遗传算法和进化规划以及进化策略等进化计算理论日益结合。 二、决策树技术的研究现状及水平 决策树的研究主要体现在以下几方面： 1 、属性评价标准 决策树方法的核心是如何构造决策树，构造决策树一般采用自上而下的递归方 法，其关键是找出表示内部节点的最佳扩展属性。寻找最佳扩展属性过程中需要不 断地对扩展属性进行评价，评价属性的方法称为属性评价标准。早期的研究者认为 决策树的性能主要由属性评价标准决定，于是提出了各种各样的标准，归纳起来大 致可分为：基于信息论的标准、基于距离度量的标准、基于相关度量的标准和其它 类型的标准：后来通过实验发现，属性评价标准对决策树的精度影响不大。目前这 方面的研究较少。 2 、多元树的构造 扩展属性有单属性和联合属性，所有节点的扩展属性为单属性的决策树称为单 元树，所有节点的扩展属性为联合属性的决策树称为多元树。由单属性形成的扩展 属性集小，可以容易地找出最佳扩展属性，构造单元树速度快，但是单元树规模大， 并可导致子树复制和一个属性的多次测试等问题；用联合属性作为扩展属性，形成 的多元树规模小，能有效地克服单元树存在的问题，但是，联合属性形成的扩展属 性集大，很难找出最佳扩展属性，一般用启发式方法找出次优的扩展属性。 多元树中研究得最多的是斜决策树，它的内部节点是线性联合属性。寻找最佳 线性联合属性分为两步：一、选择属性；二、确定属性的系数。选择属性的方法有逐 步向后排除法、逐步向前选择法等；确定属性系数的方法有爬山搜索法、模拟退火 法、最小二乘法、口袋算法等等。目前这方面的工作仍是研究更好的优化系数方法。 3 剪枝算法 剪枝是剪去影响分类精度的分枝，分为向前剪枝和向后剪枝。向前剪枝的方法 是，在生成树的同时决定是继续对不纯的子集进行划分还是停机：向后剪枝是一种 西安建筑科技大学硕士学位论文 两阶段法：拟合一一化简，首先生成与训练数据完全拟合的一棵树，然后从树的叶子 开始，逐步向根的方向剪。目前使用得较多的是m d l 剪枝法。 4 、联合学习 为了提高分类的精度，许多研究者对联合学习进行了研究。对于决策树而言， 其主要思想是先生成多个树，然后把这些树联合起来进行分类，实验表明用联合学 习构造的多棵决策树较单棵决策树的分类精度高。目前研究得较多的是b a g g i n g 和 b o o s t i n g 。 5 、其它方面 处理大数据集、交互式构造决策树、增量式构造决策树、决策树的表示等方面 都有人作过研究，不过，这些方面还有待更深入的进行。 三、关联规则发现的研究现状及水平 由于关联规则挖掘可以发现用传统的人工智能和统计方法所无法发现的规则或 规律，因此具有重要的研究价值。且由于其处理的数据量十分巨大( 从几m 到几百m ， 甚至更大的数据量) ，所得的规则往往数量大，因此也迎合了人们从当今日益增长的 电子化数据中获取知识的迫切需求。目前世界上知名大学的研究机构和各大i t 公司 的研究部门都投入了大量精力对其进行研究，并取得了诸多的研究成果。美国斯坦 福大学智能数据库系统实验室开发出了大量的商用化数据挖掘系统，如d b m i n e r 挖 掘系统，该系统包含了许多先进的挖掘算法，并有很多优秀的特点：用户无需具有高 级的统计知识和培训即可使用该软件，因为底层的挖掘细节对于用户是不透明的； 挖掘的知识类型多种多样，从关联规则、序列模式( s e q u e n c ep a t t e r n ) 到发现驱动 ( d i s c o v e r y d r i v e n ) 的分类等；并且由于采用了许多先进的研究成果，因此该产品 的速度声称是其同类竞争者的2 0 倍；此外该系统可以在多种平台上运行，并与许多 主流的数据库系统( 如：s q l s e r v e r ，o r a c l e 等) 结合紧密；同时还引入了在线分析 挖掘技术，使得系统更能充分发挥数据仓库的分析优势。i b m 的a l m a d e n 实验室所 进行的q u e s t 项目同样也是数据挖掘研究领域中的佼佼者，该项研究包含了对关联 规则、序列模式、分类及时间序列聚类( t i m es e r i e sc l u s t e r i n g ) 的研究，其代表 性的产品有：d b 2i n t e l l i g e n tm i n e rf o rd a t a ，该产品是在i b md b 2 平台下的系 统，当然也有w i n d o w sn t 下的类似产品。此外，美国的宾西法尼亚大学的数据挖掘 研究小组也在这些方面取得了显著成果，其主要研究包括：利用注释和文本对数以百 万计的文章进行聚类和分析；从多家医院的病人数据库中发现可以提高医疗质量和 降低医疗费用的模式；在构建一个模型中选择合适的变量：基于d n a 序列预测基因模 式等等。目前世界上比较知名的数据库公司，如o r a c l e ，s y b a s e 等都已经在不同程度 西安建筑科技大学硕士学位论文 上将数据挖掘的有关技术结合到其对应的数据库产品中来，使得大型数据库的功能 向智能化的方向迈进了重要的一步。除了上面提到的世界上比较知名的公司和研究 机构外，其他还有很多大学的研究机构和学者也对该领域的发展做出了重要贡献， 如加拿大的s i m o nf r a s e r 大学的j i a w e ih a n ，比利时赫尔辛基大学的m a n n i l a ， t o i v o n n e n 等都是享誉世界的数据挖掘研究的顶尖学者，它们的许多工作都是该领 域中具有奠基性的。总之，目前美国、欧洲及日本等发达国家在这方面的研究投入 巨大，主要的研究成果也集中于这些国家的研究机构和大学。通过关联规则的研究 可以发现数据库项目间的一定的内在联系，有效地提高应用系统的决策支持能力， 对市场策略、商业经营、目标设计、仓储规划等有很大的现实意义。在国内，数据 挖掘研究的起步只是最近几年的事，主要的研究机构有：中科院、清华大学、西安交 大、上海交大及国防科大等少数几所院校和研究机构，在国内外权威刊物上发表的 有关文章也寥寥无几。尽管如此，由于数据挖掘技术的广泛应用前景，和其具有的 强大功能，促使我们必须迅速展开对其深入的研究。 四、目前研究存在的问题 遗传算法、关联规则挖掘、决策树技术在各自的研究和应用领域都取得了长足 的发展，虽表现出了优势，同时也显现了不足之处。 首先，就遗传算法丽言，它具有若干独特的性能： 在求解问题时，遗传算法首先要选择编码方式，它直接处理的对象是参数 的编码集而不是问题参数本身，搜索过程既不受优化函数连续性的约束， 也没有优化函数导数必须存在的要求。通过优良染色体基因的重组，遗传 算法可以有效地处理传统上非常复杂的优化函数求解问题； 若遗传算法在每一代对群体规模为n 的个体进行操作，实际上相当于处理 了大约0 ( n 3 ) 个模式，具有很高的隐并行性，因而具有显著的搜索效率； 遗传算法具有很强的鲁棒性，在所求解问题为非连续、多峰以及有噪声的 情况下，能够以很大的概率收敛到最优解或满意解，因而具有较好的全局 最优解求解能力； 对函数的性态无要求，针对某一问题的遗传算法经简单修改即可适应于其 他问题，或者加入特定问题的领域知识，或者与已有算法相结合，能够较 好地解决一类复杂问题，因而具有较好的普适性和易扩充性： 遗传算法的基本思想简单，运行方式和实现步骤规范，便于具体使用。 但是同时它对于多峰函数等可能存在模式欺骗问题，有时还会出现早熟现象。 其次，对于决策树技术而言，它与其它分类技术相比，有以下优点： 西安建筑科技大学硕士学位论文 决策树结果更易被用户理解： 生成决策树的效率更高、更适合大训练集； 决策树的生成算法不需要除训练集之外的额外信息： 它可以提供更好的精确度。 但是决策树技术也有它的缺点：一方面，它无法删除带噪声的不相关的属性； 另一方面，大多数决策树被限制在每个节点上只检验单个属性。再则，针对分类规 则挖掘来说，虽然国内外在这方面的研究已经取得了较大的进步，但是在针对海量 数据集的规则挖掘方面仍然存在着不足，需要进一步研究和提出更好的解决方案。 再有，对于关联规则的挖掘虽然已经有了各种成熟的算法存在，但是它们都仅 是适用于小型数据集，而对于大数据集中关联规则的快速挖掘算法方面研究还远远 不够。 本文通过把遗传算法的特点与关联规则挖掘的要求巧妙地结合起来，建立起一 个a r m g a ( a s s o c i a t i o nr u l em i n i n gu s i n gg e n e t i ca l g o r i t h m ) 算法，主要用 于解决大型数据集中关联规则的发现问题，并针对近些年来我国矿山事故持续不下， 给国民经济和人民生命财产带来了巨大的破环的情况，收集了国内近年来矿山事故 的数据，利用该算法对诱发事故的因素进行了分析，取得了很好的效果，这就对分 析诱发事故的因素提供了可贵的素材，为将来制定合理的矿山管理方案提供了理论 基础。 针对决策树技术和遗传算法各自的优缺点，本文将这两者结合起来，取长补短， 发挥各自的优势，建立起一个新的混合算法，即d t g a ( d e c i s i o nt r e eo ng e n e t i c a l g o r i t h m ) 算法，并将其程序化、运用到矿山事故分析问题中，通过与其他算法的 比较，充分证实了程序的高效性和健壮性，它可以通过简单的修改应用到其他领域 的分类问题中，这将在推动数据挖掘技术于国内进一步发展和应用的道路上添一砖 一瓦。 1 3 本文的主要内容安排 由于决策树技术和现在关联规则挖掘方面存在着不足，再加之遗传算法的理论 研究愈发地充实和遗传算法在所涉及的领域中表现出的良好的隐并行性、鲁棒性和 适应于大数据集的处理等特征，本文将它们分别进行有机的结合，构造出新的算法， 并将其用于矿山事故分析中。本文就是在这样一种构思的前提下进行的，其主要内 容安排大致如下： 第一章绪论，主要介绍课题研究的目的和意义、该课题国内外研究的现状、本文的 6 西安建筑科技大学硕士学位论文 主要内容安排； 第二章简单介绍了知识发现的产生背景、基本概念、一般实施过程和其应用领域， 文中还对数据挖掘技术给以概述性的描述； 第三章对遗传算法的产生、基本术语、基本特点、理论基础和具体的实施技术给了 较为全面的介绍，主要是为新算法的构建奠定了坚实的理论基础； 第四章介绍了遗传算法用于关联规则挖掘模型的分析和构造，构建a r 卅g a 算法并 将它程序实现后应用于矿山事故分析中，最后对执行的结果进行简单的分析和 评价； 第五章首先简单介绍了决策树的相关技术，然后分析与构造d t - g a 算法并给出该算 法的描述，将其程序化后应用在第四章总结的矿山事故数据库中，并设置了一 系列相关试验，与现有决策树算法进行分类准确度和计算时间指标的比较，得 到一系列结论，最后对新算法进行了相关方面的扩展； 第六章总结与展望 西安建筑科技大学硕士学位论文 2 1k b d 的产生背景 2 知识发现概述 在今天这个信息和知识经济时代，信息技术的高速发展使得商业管理、政府部 门、科学和工业数据处理等领域都收集并存储了海量数据，特别是i n t e r n e t 的迅猛 发展使得网络上的各种信息资源异常丰富。随着数据的飞速增长和数据在日常决策 中的重要性越来越显著，人们对数据处理技术的要求也不断提高，需要能够对数据 进行更深层次的处理，以得到关于数据的总体特征以及对发展趋势的预测。过去， 人们依靠经验、大量的计算和人脑的智慧来处理这些深层次的信息，为决策提供技 术支持。然而数据量的爆炸性增长使得传统的手工处理方法逐渐变得不切实际了， 现在的用户很难再像从前那样，自己根据数据的分布找出规律，并根据此规律进行 分析决策。而且对于象超市商品的销售记录、保险公司的客户记录、医学上的成千 上万份病历等等的这些海量数据来说，如果由手工处理的话需要几十个人年，而且 由于数据的繁杂，在由人工对数据进行处理过程中，很难找出关于数据较为全面的 信息，这样许多有用的信息仍然隐含在数据中而不能被发现和利用，造成数据资源 的浪费，更无法体现出信息的时间效应。由此人们就更加追切地需要一种新的技术 和工具以便从大量的数据中自动地、智能地抽取隐藏于这些数据中的有价值的知识 和信息，k d d 正是迎合这种要求而产生并快速发展起来的一种用于信息资源开发的 数据处理新技术，并很快成为了一种决策支持的新手段。 k d d 这个术语首先出现在1 9 8 9 年8 月在美国底特律召开的第1 l 届国际人工智 能联合会议的专题讨论会上，1 9 9 1 、1 9 9 3 和1 9 9 4 年又相继举行了k d d 专题讨论会。 随着参加会议人数的增多，从1 9 9 5 年开始，每年举办一次k d d 国际会议，从1 9 9 7 年起，k d d 拥有了自己的杂志( k n o w l e d g ed i s c o v e r ya n dd a t am i n i n g 。“1 目前，在很多领域，k d d 都是一个很时髦的词，尤其是在诸如银行、电信、保 险、交通、零售( 如超级市场) 等商业领域。k d d 的研究非常活跃，吸引了大量的 各个领域的专家和研究机构从事该领域的研究。许多公司也纷纷推出了自己的数据 挖掘系统。k d d 已经成为了一个具有广阔应用前景的新兴领域。 2 2k d d 的基本概念 许多专家都给出了k d d 的定义，最新的、在k d d 领域一致认可的描述性定义是 f a y y a d 等人给出的”! 。 西安建筑科技大学硕士学位论文 定义1 1k d d 是从塑塑塞中识别出直鏊鲍、堑题盟、鲎垄直旦的，以及量堡卫 堡鲢煎搓式的非平凡过猩。 为了更好地理解k d d 的定义，我们将此定义中的关键词的含义列出如下： 数据集是一组事实f ： 模式是一个用语言l 表达的一个表达式e ，它可用来描述数据集f 的某个子集 f 。，e 作为一个模式要求它比对数据子集f 。的枚举要简洁( 所用的描述信息量要 少) ； 过程在k d d 中通常指多阶段的处理，涉及数据准备、模式搜索、知识评价以及 反复的修改求精； 非平凡的是指要有一定程度的智能性、自动性； 有效性是指发现的模式对于新的数据仍保持有一定的可信度： 新颖性是要求发现的模式应该是新的、用户未知的或未预料到的； 潜在有用性是指发现的知识将来有实际效用； 最终可理解性是要求所发现的模式能被用户理解，目前体现在简洁性上。1 2 3k d i ) 的过程 k d d 过程是一个与用户不断交互的循环往复过程。一般地说，在业务需求已经 清楚的前提下，完成从大型源数据中发现有价值知识的过程( 如图2 1 所示) 可以简 单地划分为：数据准备、数据挖掘和结果的解释与评价三个环节。 确定 问题 图2 1k d d 过程 数据准备阶段的工作包括3 个方面的内容：数据选取，主要是确定目标数据 一一根据用户需要从原始数据库中抽取一组感兴趣的数据，并将其组织成适合挖掘 的数据组织形式；数据预处理，也叫数据清洗，主要包括如下工作要做：消除噪 9 西安建筑科技大学硕士学位论文 音数据( 这里提及的噪音数据是指那些明显不符合逻辑的偏差数据，如某雇员2 0 0 岁，这样的数据往往影响挖掘结果的正确性。目前讨论最多的处理噪音数据的方法 是数据平滑( d a t a s m o o t h i n g ) 技术) 、推导计算缺值数据、消除重复记录、完成数据 类型转换等；数据变换，主要是指对数据进行降维处理。 数据挖掘阶段是根据挖掘的任务或目的使用具体的挖掘算法对准备好的数据集 进行知识发现。这些知识是隐含的、先前未知的、对决策有潜在价值的，提取的知 识表示为概念( ( c o n c e p t s ) 、规则( ( r u l e s ) 、规律( r e g u l a r i t i e s ) 和模式( p a t t e r n s ) 等形式。这些规则蕴含了数据库中一组对象之间的特定关系，揭示出一些有用的信 息，为经营决策、市场策划和金融预测等提供依据。例如，从超级商场的大量交易 数据中发现，顾客购买牛奶时通常也同时会购买面包，如果将这两种食品放在同一 货架上或同时进行广告宣传，肯定会大大提高销售量。通过数据挖掘技术，有价值 的知识、规则或高层次的信息就能从数据库的相关数据集合中抽取出来，并从不同 角度显示，从而使大型数据库作为一个丰富可靠的资源为知识归纳服务。 最后一阶段是对于挖掘出来的模式进行解释和评价，剔除冗余或无关的模式， 将结果展现给用户。”1 数据挖掘和k d d 密切相关，一般的观点认为数据挖掘是k d d 过程的一个环节， 但也有少数人认为两个概念等同。本文认同第一种观点，并且由于时间的关系，重 点放在数据挖掘算法的构造，至于数据准备和模式评价两阶段不作太过详细的介绍。 2 4k i ) d 的应用 数据库知识发现的应用：在科学实验中的应用；数据挖掘在零售行业上的 应用，通常也称为货篮分析；典型的金融分析领域有投资评估和股票交易市场预 测，分析方法一般采用模型预测法，例如使用神经网络模型选择投资；识别银行 或商业上经常发生的诈骗行为，如恶性透支等。数据库知识发现可以用于探测可疑 的信用卡交易，或识别与洗钱有关的金融交易；在电话销售和直接销售行业的应 用。其主要方法是根据客户的采购历史数据对客户进行商品销售定位，有针对性地 向客户发送商品目录，或打电话，提高直接销售或电话销售的成功率；在制造行 业也有数据库知识发现技术的应用。目前，在制造行业上的主要应用方面是控制生 产流程；在电信行业的应用：在交通管理及车流状态预测方面的应用。 2 5 数据挖掘技术简介 数据挖掘是一个多学科交叉研究领域，它融合了数据库技术、人工智能、机器 - 1 0 西安建筑科技大学硕士学位论文 学习、统计学、知识工程、面向对象方法、信息检索、高性能计算以及数据可视化 等最新技术的研究成果。数据挖掘技术是懈决机器学习、模式识别、数据库技术等 各种领域中的大型实际应用问题而提出的一些工程性方法的集合，主要是为了从大 型数据库中高效地发现隐含在其中的知识或规律，并为人类专家的决策提供支持。3 。 一、目前，比较流行的数据挖掘技术有： 统计分析方法主要用于完成知识总结和关系型知识挖掘。对关系表中各属 性进行统计分析，找到它们之间存在的关系； 决策树方法：利用信息论中的信息增益寻找数据库中具有最大信息量的字 节，建立决策树的一个结点，再根据字段的不同取值建立树的分支。在每 个分支子集中重复建立决策树的一个结点和分支，这样便生成一棵决策树。 决策树可应用于监督式数据挖掘上，尤其是数据分类： 人工神经网络：用于分类、群集、特征挖掘、预测和模式识别。它仿真生 物神经网络，本质上是一个分散型或矩阵结构，它通过对训练数据的挖掘， 逐步计算网络连接的加权值； 遗传算法：用于分类、关系型规则挖掘等。他模仿人工选择培育良种的思 路，从一个初始规则集合( 知识基因) 开始，逐代地通过进化对象成员( 杂 交、基因突变) 产生群体( 繁殖) ，评估并择优复制( 物竞天择、适者生存、 不适应者淘汰) ，优胜劣败，逐代积累计算，最终得到最优化的知识集； 粗糙集方法：用于数据简化、数据意义评估、对象相似性或共性分析、因 果关系及范式挖掘等。其主要思路如下：把对象的属性分为条件属性和决 策属性，按各个属性值相同的划分成等价类。条件属性上的等价类e 与决 策属性上的等价类y 之间有3 种情况：下近似( y 包含e ) 、上近似( y 和e 的交集并非空集合) 、无关( y 和e 的交集为空集合) ； 联机分析处理技术( o l a p ) ：用具体的图形将信息模式、数据的关联或趋势 呈现给决策者，使用户能交互式地分析数据的关系，而o l a p 技术将人的观 察力和智力融入挖掘系统中，极大地改善了系统挖掘的速度和深度； 关联规则方法：找出一组对象之间存在的联系和规律，其形式通常为“一 个( 组) 对象j 另一个( 或一组) 对象”，说明这两个( 或两组) 对象倾 向于同时发生、同时出现或存在有其它的联系； 模糊论方法：利用模糊集合理论对实际问题进行模糊评判、模糊决策、模 糊模式识别和模糊聚类分析。模糊性是客观存在的。系统的复杂性越高， 精确化能力就越低，即模糊性越强( 这是z a d e h 总结出的互克性原理) 。 硬安建筑科技大学硕士学位论文 另外还有归纳逻辑程序、b a y e s i a n 网络和隐马尔科夫过程等等方法。 二、数据挖掘的任务( 也叫挖掘知识的类型) “： 总结规则挖掘：他所要做的是从客户指定的数据中挖掘出( 从不同的角度或 在不同的层次上) 平均值极大值、总和、百分比等。挖掘结果运用交叉表、 特征规则和统计的曲线图等表示。 关联规则挖掘：他所要做的是从客户指定的数据库中挖掘出满足一定条件的 依赖性关系。 分类规则挖掘：他所做的是在已知训练信息的特征和分类结果的基础上，为 每一种类别找到一个合理的描述或模型，然后再用这些分类的描述或模型来 对未知的新数据进行分类。 群集规则挖掘( 又称无监督式的分类) ：其目的在于实事求是地、即客观地 按被处理对象的特征分类，有相同特征的对象被归为一类。 预测分析：当分类的工作偏向于插入漏掉的数据、预测数据分类或发展的趋 势时，此时的工作即为预测分析。 趋势分析( 又称时间序列分析) ：它是从相当长时间的发展中发现规律与趋 势。 偏差分析( 又称比较分析) ：它找出一系列判别式的规则，以区别客户设置 的两个不同类别。 三、数据挖掘的对象 随着数据挖掘技术的进一步研究和发展，数据挖掘的对象己远远超出了数 据库的范围，数据源还可以是：数据仓库、文本数据集合，h t m l ( h y p e r t e x t m a r k u pl a n g u a g e ) 数据集、w e b 文档