（计算机应用技术专业论文）数据挖掘中判定树算法的研究与优化.pdf

卜海师范人学硕j 二研究生学位论文数据挖掘中决策树算法的研究与优化 摘要 数据分类是数据挖掘的一个重要方法。数据分类是通过分析训练集数据，产 生关于类别的精确描述或模式，这种类描述可以用来对未来的数据进行分类，有 着广泛的应用前景。目前常用的分类规则挖掘方法有决策树方法、贝叶斯分类算 法、遗传算法和粗集理论等。 在上述方法中，决策树算法描述较简单，容易转化成分类规则，但同时存在 得不到全局最优解的问题：遗传算法虽然能解决大空间、多峰值和非线性等高复 杂度问题，但也存在算法收敛于局部最小值的过早收敛问题。由此，本文提出了 一种基于混合遗传模拟退火算法的分类决策树方法( g s d a 算法) 。g s d a 算法将 遗传算法引入到已有的分类决策树挖掘算法中，提出了一个新的基于混合遗传模 拟的算法。本算法在决策树的编码上，改进了常用的二进制编码方式，采用了决 策树直接编码的方式，提高了运算的精确性。与此同时，g s d a 算法还引入了混 合优化的思想，弥补了常用算法中局部性最优的问题。提出了相应的适应度函数， 同时提出了适合本文的剪枝操作，使得挖掘出的规则不但正确性更高，而且整体 算法更简洁、更易理解。 在随后的初步实验中，本文使用了四个不同的数据库：天气数据库、c l e v e l 卸d 数据库、h e a nd i s e a s e 数据库和b r e a s tc a n c e r - w 数据库，并将g s d a 算法的实验 结果与经典算法i d 3 算法进行了比较，获得了较优的结果。 关键词：数据挖掘；分类规则；遗传算法；g s d a 算法 a b s t r a c t d a t ac l a s s i f i c a t i o nh a sb e c o m e0 n eo ft h ei m p o r t a n tr e s e a r c ha s p e c t so fd a t a m i n i n g d a t am i n i n gg e n e r a t e sp r e c i s ed e s c r i p t i o n0 rm o d e lo ft h ep r e d e t e r m i n e ds e t o fd a t ac l 弱s e so rc o n c e p t sb y 西v i n gd a t ao b j e c tp a n i t i o na c c o r d i n gt ot h ef e a t u r e so f ag r o u po fd a t ao b j e c t s t h e s em o d e l st h e nc 锄b eu s e dt oc l a s s i f yf u t u r ed a t ao b j e c t s w h i c hh 懿a9 0 1 0 dp r o s p e c ti na p p l i c a t i o n t h em o s tp o p u l 缸d a s s i f i c a t i o nm e t h o d sa t p r e s e n ti n c l u d eg e n e t i ca l g o r i t h m ，d e c i s i o nt r e s s ，n e u r a ln e 觚o r k ，e t c a m o n gt h et h r c em e t h o d sm e n t i o n e da b o v e ，t h ed e c i s i o nt r c ea l g o r i t h mi ss i m p l e i nd e s 谢p t i o n 勰di se a s yt ot r a n s l a t e “i n t oc l a s s i f i c a t i o nm l e s h 0 w e v e fi tc 柚h a r d l y f i n dt h e 舀o b a lo p t i m u ms o l u t i o n t h 咖g l it h eg e n e t i ca l g o r i t h mc a ns o l v et h e p r o b l e mo f h u g es e a r c h i n gs p a c e ，m u l t i p l e - p e a l 【v a l u e ，a n dn o n l i n e 撕t y i ta l s oh a s t h ed r a w b a c ko fe a r l yc o n v e r g e n c e t h e r e f o r e ，ad a s s i f i c a t i o nm l em i n i n gm e t h o d c a l l e dg a d ab a s e d0 nh y b r i dg e n e t i ca n ds i m u l a t e da n n e a l i n ga l g o r i t h mi sp r o p o s e d t h i sa l g o r i t l l l l li n t r o d u c e sd i r e c tt r e e e n c o d i n gm e t h o dt 0i m p r o v et h ea c c u r a c y m e a n w h i l ei ti n t r o d u c e s h y b r i do p t i m i z a t i o n t os o l v et h e p r o b l e mo f l o c a l o p t i m i z a t i o n w ea l s oi m p r 0 v es u c ha s p e c t so ff i t n e s sf u n 州o na n dp n i n i n go p e r a t i o n t om a k et h ea c c u r a c yo ft h em i n i n gm l e sm u c hh i g h e ra n dt h ea l g o r i t h ms i m p l e ra n d e a s i e “0u n d e r s t 柚d 越l t h e s ea r ee x p l a i n e di l lt h ef o l l o w i n ge x p e r i m e n t w eu s ef o u rd i 虢r e n td a t a b a s e s ：w e a t h e rd a t a b a s e ，c l e v e l 卸dd a t a b a s e ，h e a n d i s e 弱ed a t a b a s e 蚰db r e a s tc a n c e 卜wd a t a b a s et oc o m p a r et h er e s u l to fg s d a a 1 9 0 r i t h m 柚dc l a s s i cl d 3a 1 9 0 r j t h m i ti sp r 0 v e dt h a tt h eg s d aa 1 9 0 r i t h mp e 怕衄s b e t t e rt h 卸i d 3a 1 9 0 r i t h m k e y w o r d s ：d a t am i n i n g ；c l a s s i f i c a t i o nm l e ；g e n e t i ca l g o r i t h m ；g s d aa 1 9 0 r i t h m l i l 上海师范大学硕十研究生学位论文数据挖掘中决策树算法的研究与优化 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或机构已经发表或撰写过的研究 成果。其他同志对本研究的启发和所做的贡献均已在论文中做了明确的声明并表 示了谢意。 作者签名：了， 瓦日期：枷口g j 叫 论文使用授权声明 本人完全了解上海师范大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其它手段保存论文。保密的论文在解密后遵守此 规定。 作者签名：了帆导师签名：墨i 勿鹏期：切p 舌s 砷 上海师范人学硕十研究生学位论文数据挖掘中决策树算法的研究与优化 第一章绪论 1 1 研究背景 在过去的数十年中，我们产生和收集数据的能力已经迅速提高。这主要是得 益于条码在大部分商业产品中的广泛使用，许多商务、科学和行政事务的计算机 化，以及文本和图像扫描平台等数据收集工具的进步。此外，作为全球信息系统 的万维网的流行，已经将我们淹没在数据和信息的汪洋大海之中。这些海量数据 中隐藏着许多人们事先不知道、但又是潜在有用的信息和知识。因此，面对“人 们被数据淹没，人们却饥饿于知识 的挑战，从数据库中发现知识( 1 白o w l e d g e d i s c o v e r yi nd a t a b a s e s ，k d d ) 及其核心技术一一数据挖掘( d a t am i n i n g ，d m ) 便应 运而生，并得以蓬勃发展，越来越显示出其强大的生命力。 简单地说，数据挖掘就是从大量数据中提取或“挖掘”知识。一种比较公认 的定义是：数据挖掘是指从数据库的大量数据中揭示出隐含的、先前未知的、潜 在有用的信息的非平凡过程i l l 。它是一门新兴的交叉学科，汇集了来自机器学习、 模式识别、数据库、统计学、人工智能等各领域的研究成剥2 j f 3 1 1 4 l 【5 】【6 】。 数据挖掘的主要任务有分类分析、聚类分析、关联分析、序列模式分析等。 其中的分类分析由于其特殊地位，一直是数据挖掘研究的热点之一，同时，也是 其它诸如人工智能、模式识别、人工神经元网络等学科的重要研究内容。分类是 一种重要的数据挖掘技术。近年来，它已经被有效地用于科学实验、医疗诊断、 气象预报、信贷审核、商业预测、案件侦破等领域，取得了良好的效果。依据所 采用的分类模型，数据分类技术主要有：判定树( 决策树) 归纳、贝叶斯分类和 贝叶斯网络、神经网络方法、遗传算法、粗糙集和模糊逻辑技术等。这些方法各 有优缺点，亦出现了基于这些技术的混合型算法，其中遗传算法与分类技术的结 合在数据挖掘算法中引起了有关学者的重视，占有较为重要的地位。 分类是根据数据集的特点构造一个分类函数或分类模型( 也常常称作分类 器) ，该模型能把未知类别的样本映射到给定类别中的某一个。数据分类是一个 两步过程。第一步，建立一个模型，描述预定的数据类集或概念集。通过分析由 属性描述的数据库元组来构造模型。第二步，使用模型进行分类。通常，模型可 以用分类规则、判定树或数学公式表示【7 】。与其它两种表示方法相比，使用分类 规则的好处在于： ( 1 ) 每条规则能够独立地表示被发现的知识； ( 2 ) 新规则的加入并不影响已经存在的规则集； ( 3 ) 并且易于理解。 在分类模式中，决策树是应用最广泛的分类技术，它具有以下优点： t 海师范大学硕士研究生学位论文数据挖掘中决策树算法的研究与优化 ( 1 ) 决策树方法能够生成可以理解的规则； ( 2 ) 决策树方法的计算量相对其他方法来说比较小，这样可以大大地缩短计 算时间，提高系统的效率； ( 3 ) 决策树方法可以处理连续和离散数据； ( 4 ) 决策树可以清晰地显示出属性的重要程度。即描述简单，分类速度快， 容易转化成分类规则。 当前最有影响的决策树算法是q u i n l 柚于1 9 8 6 年提出的i d 3 【8 l 和1 9 9 3 年提出的 c 4 5 【9 1 。由于采用分而治之的策略，因此获得的决策树可能是局部最优的，但不 一定是全局最优的。 遗传算法在解决大空间、多峰值、非线性、全局优化等高复杂度问题时显示 了独特的优势，它是j h h o i l a l l d 于1 9 7 5 年提出的一种基于进化论的原理发展起 来的高效的随机搜索与优化的方法，其应用范围几乎涉及到用传统的优化方法难 以解决的优化问题。遗传算法具有计算简单、优化效果好的特点，它在处理组合 优化问题方面也有一定的优势。但还存在以下问题：算法较复杂，收敛于局部极 小的过早收敛等难题未得到彻底解决。因此，两者相结合可能会得到精度更高的 决策树。 虽然遗传算法在分类和概念学习方面已有了很广泛的研究。但把它作为改进 决策树的工具方面的研究还是比较少的。大多数情况下，遗传算法和决策树( 以 及其他分类算法) 的结合点在于属性数据的预处理。 为了提高分类规则挖掘效率和准确性，一些研究人员将遗传算法和决策树算 法相结合，运用到分类规则挖掘中去。取得了一些成果。但人仍存在着一些问题， 如早熟、局部搜索能力弱、构建的决策树深度过深，导致导出的规则过多、规则 长度过长，从而影响决策树的预测速度。 1 2 研究现状 遗传算法是模拟自然界进化过程中优胜劣汰原则的计算模型，它是一种全局 最优化算法【1 0 1 【1 1 l 。并且是多学科交叉与结合的产物，已经发展成一种适合于求 解大规模问题并具有自组织、自适应等特征的算法。遗传算法由于其解决问题以 混沌、随机和非线性为典型特征，为其它科学技术无法解决或难以解决的复杂问 题提供了新的计算模型。对于大量数据的嘈杂无序的特征，遗传算法是有效解决 此类问题的方法之一。在遗传算法中，种群规模和遗传算子的控制参数的选取是 影响算法性能的关键所在。同时，遗传算法还存在过早收敛的现象。因此，一些 混合优化策略开始被用以改进算法的性能。 传统的决策树算法在树的构造过程中并不一定能得到最优的决策树，而将两 者相结合可能会得到精度更高的决策树。为了提高数据挖掘的效率，人们自然想 到把遗传算法用于数据挖掘中。遗传算法应用于决策树、分类规则和模糊规则的 2 上海师范人学硕l 研究生学位论文数据挖掘中决策树算法的研究与优化 获取等方面的文献不断涌现。与其他分类方法相比，遗传算法具有很强的处理噪 声、无效和不准确数据的能力。目前研究各种高性能和高可扩展性的分类算法是 数据挖掘面临的主要问题之一。 目前，国内外数据挖掘中有关决策树算法研究的主要进展主要呈现以下几个 方面： ( 1 ) 结合其它算法提高树的精度。其中将遗传算法与决策树算法相结合， 得到精度更高的决策树得到了研究人员比较广泛的关注； k e n n e d v 等人提出了一个决策树系统c a i t r o p ，用遗传算法来构造二叉决 策树。特点：对决策树进行编码。但不同子集产生的决策树的形状、结点个数是 不同的，因此，采用固定长度的位串来表示决策树有时不合适。 z f u 提出一种智能决策树算法g 舢t ，结合了遗传算法、统计抽样和决策树 算法。特点：在一定程度上弥补了基于子集方法的缺陷，但时间代价比较高。 ( 2 ) 数据的概化与约简。针对海量数据集，我们需要先用过滤、约简和概 化等方法对数据进行预处理；此外，对数据集进行压缩或者精简是必要的。因而， 将数据集进行属性约简和数据过滤也是当前比较热门的研究； ( 3 ) 抽样方法。在进行数据挖掘的分类任务时利用抽样方法也可以提高决 策树的效率，当我们对算法的效率要求很高时这种方法特别有效； ( 4 ) 并行机制。在数据挖掘应用中，有很多情况对结果的实时性要求很高， 所以，对决策树算法的并行性研究也是一个热点。 1 3 论文的主要工作 本论文首先介绍总结了分类模式中常用的方法，以及算法。在其基础上，提 出了基于混合模拟遗传算法的分类决策树算法( g s d a 算法) ，并对其做了优化。 最终运用n e t 工具进行了实验论证。具体工作报告如下： ( 1 ) 详细介绍了数据挖掘的产生、发展。总结了目前分类模式中常用的方法； ( 2 ) 介绍了模拟退火算法和遗传算法的基本理论、概念，结合分类规则挖掘 理论，引出了混合遗传模拟算法的思想； ( 3 ) 在对遗传算法和模拟退火算法理论研究的基础上，提出了一种基于混合 模拟遗传算法的分类决策树算法，即g s d a 算法，提高了分类规则挖掘的准 确度； ( 4 ) 介绍、对比分析了常用的剪枝方法，结合本文的算法，引入树剪枝操作， 提高本文提出的分类算法的挖掘效率； ( 5 ) 运用n e t 技术实现了本文提出的g s d a 算法； ( 6 ) 通过三个不同开源数据库的实验数据证明g s d a 算法是较优的。 1 4 论文的创新点 论文的创新点如下： 3 上海师范大学硕l 研究生学位论文 数据挖掘中决策树算法的研究j 优化 ( 1 ) 将模拟退火与遗传算法相结合，提出了g s d a 分类算法； ( 2 ) 改进了适应度函数，使得挖掘出的规则正确性更高，更简洁，更易理解； ( 3 ) 将树剪枝操作引入本算法，提高其挖掘效率； 1 5 论文的组织结构 本文共分为六个章节，具体安排如下： 第一章绪论。讨论了论文的背景意义、国内外研究现状和研究目标： 第二章介绍了数据挖掘的产生背景、定义和模式，并对一些常用的分类规 则挖掘方法进行了分析和比较，同时介绍了常用的决策树剪枝操作； 第三章介绍了遗传算法和模拟退火算法的基本理论，以及混合遗传模拟退 火算法的相关知识； 第四章提出了g s d a 分类决策树算法； 第五章对上述分类规则挖掘算法进行了实例测试， 出性能评价； 第六章总结与展望。在总结本文的工作的基础上， 最后是参考文献、附录和致谢。 4 在实例测试的基础上给 描述了进一步的工作。 上海师范人学硕：卜研究生学位论文数据挖掘中决策树算法的研究j 优化 第二章数据挖掘与分类规则挖掘 2 1 数据挖掘的产生 随着信息技术的快速发展和信息搜集能力的日益提高，产生了海量的数据。 面对如此丰富的海量数据，传统的数据处理方法和能力己远远不能满足实际的需 求。大量的数据未能充分利用这一现象常常被描述为“数据爆炸，但知识贫乏”。 快速增长的海量数据收集、存放在大量数据库中，如果没有强有力的工具的帮助， 理解它们已经远远超出了人的能力。结果，存放在大量数据库中的数据变成了“数 据坟墓 。这样，重要的决策常常不是基于数据库中信息丰富的数据，而是基于 决策者的直觉。此外，相当数量的数据具有很强的时效性，数据的价值随着时间 的推移而迅速降低。为此，人们迫切需要能从海量数据中发现潜在有用的信息和 知识的工具，数据挖掘技术正是为满足这一需求而产生的。目前在国外已有许多 领域成功采用数据挖掘辅助决策，如市场营销、零售业、金融、医疗保险、政府 部门及科学研究等，已充分显示了这一信息技术的优越性，这也促进了应用和研 究的进一步发展。 2 2 数据挖掘的定义和特性 数据挖掘出现于2 0 世纪8 0 年代末期，在9 0 年代有了突飞猛进的发展，是 当前仍十分活跃的前沿领域之一。作为一个新兴的交叉学科，它从多个学科汲取 营养。这些学科包括数据库技术、人工智能、机器学习、神经网络、统计学、模 式识别、知识库系统、知识获取、信息检索、高性能计算和数据可视化。简单地 说，数据挖掘是从大量数据中提取或“挖掘 知识。一种比较公认的定义是：数 据挖掘是指从数据库的大量数据中揭示出隐含的、先前未知的、潜在有用的信息 的非平凡过程f 1 2 】【1 3 】1 1 4 1 。即数据挖掘是要发现那些靠直觉不能发现的信息或知识， 甚至是违背直觉的信息或知识，挖掘出的知识越是出乎意料，可能就越有价值。 这正是数据挖掘与传统的数据分析的本质区别。数据挖掘所得到的信息应具有未 先知、有效和实用三个特征。通过数据挖掘，可以从数据库中提取有趣的知识、 规律或高层信息，并可以从不同角度观察或浏览。发现的知识可以用于决策、过 程控制、信息管理和查询处理等。因此，数据挖掘被产业界认为是数据库系统最 重要的前沿之一，是信息产业最有前途的交叉学科之一。和数据挖掘概念密切相 关的还有数据库中的知识发现( k h 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 所示，知识发现过程主要由以下步骤组成【1 5 】。 ( 1 ) 数据选择； ( 2 ) 数据预处理： 5 一f ：海师范人学硕上研究生学位论文 数据挖掘中决策树算法的研究与优化 ( 3 ) 模式提取； ( 4 ) 模式解释与评价； ( 5 ) 知识表示。 选择目标 教据集 撩处理数据挖掘模式謦释 横式提取)与评价知识 图l 知识发现过程 f i gl1 1 i ep 眦嘲o fl n o w l e d g ed i s c 吖e r y 日厨 2 3 数据挖掘模式 数据挖掘的任务是从数据中发现模式。数据挖掘功能用于指定数据挖掘任务 中要找的模式类型。模式按功能通常可以分为以下两大类：预测型模型和描述型 模型。描述性挖掘任务刻画数据库中数据的一般特性。预测性挖掘任务在当前数 据上进行推断，以进行预测。在实际应用中，常常根据模式的实际作用细分为以 下几种【1 6 】【1 7 l ： 1 分类模式； 能够把数据集中的数据映射到某个给定的类上，从而可以用来预测数据对象 的类标记。它可以用多种形式来表示，如分类规则、判定树、数学公式或神经网 络： 2 回归模式； 使用一系列现有数值来预测因变量的可能值。它与分类模式的最显著差别在 于分类模式的预测值是离散的，回归模式的预测值是连续的： 3 时间序列模式； 根据数据随时间变化的趋势预测将来的值。其中要考虑时间的特殊性质，只 有充分考虑时间因素，利用现有的数据随时间变化的一系列的值，才能更好的预 测将来的值； 4 聚类模式； 识别一组数据对象的内在规则，可以把数据划分到不同的组中，组之间的差别尽 可能大，组内的差别尽可能小与分类模式不同，进行聚类前并不知道将要划分 成几个组和什么样的组，也不知道根据哪些数据项来定义组； 5 关联模式； 描述事物之问同时出现的规律的知识。更确切地说，是通过量化的数字描述a 的 6 上海师范大学硕上研究生学位论文数据挖掘中决策树算法的研究与优化 出现对b 的出现有多大影响； 6 序列模式 与关联分析类似，只是扩展为一段时间的项目集间的关系，常把序列模式看 作由时间变量连接起来的关联。序列模式可对长时期的相关纪录分析，发现经常 发生的模式。 在解决实际问题时，经常要同时使用多种模式。分类模式和回归模式使用最 为普遍。分类模式、回归模式、时间序列模式被认为是受监督知识，因为在建立 模式前数据的结果是已知的可以直接用来检测模式的准确性，模式的产生是在受 监督的情况下进行的。一般在建立这些模式时，使用一部分数据作为样本用另一 部分数据来检验、校正模式。聚类模式、关联模式、序列模式则是非监督知识， 因为其在模式建立前，结果是未知的，模式的产生不受任何监督。 2 4 分类模式的常用研究方法 在数据挖掘的各种方法中，分类是一种主要的分析手段，旨在生成一个分类 函数或分类模型，由该模型把数据库中的数据项映射到某一给定类别中。目前许 多分类方法已被机器学习、专家系统、统计学和神经生物学方面的研究者提出， 如决策树、关联规则、贝叶斯、神经网络、遗传算法、基于案例的推理等。分类 的过程一般分为两个步骤：第一步，通过已知数据集建立概念描述模型；第二步， 就是利用所获得的模型进行分类操作。在训练阶段，分析训练数据集的特点，为 每个类别产生一个对相应数据集的准确描述或模型。在测试阶段，利用类别的描 述或模型对测试数据集进行分类，测试其分类准确度。 对各种分类方法的评估可以根据以下几条标准进行： 1 预测准确率：指模型能够正确预测未知数据类别的能力； 2 速度：指构造和使用模型时的计算效率； 3 鲁棒性：指在数据带有噪声或有数据遗失的情况下，模型仍能进行正确预测 的能力； 4 可扩展性：指对处理大量数据并构造相应有效模型的能力； 5 易理解性：指所获模型提供的可理解程度。 目前有一定影响力的且常用的数据挖掘算法中的分类算法包括：决策树方 法、贝叶斯方法、遗传算法和粗糙集方法等。 2 4 1 决策树法 决策树是一个类似于流程图的树结构，其中每个内部结点表示在一个属性上的测试，每 个分枝代表一个测试输出，而每个树叶结点代表类或类分布。决策树! j 1 纳的基本算法是贪心 算法。它以自顶向下递归的各个击破方式构造决策树，容易转换成分类规则【1 1 。因其易于提 取显式规则、计算量相对较小、可以显示重要的决策属性和较高的分类准确率等优点而得到 广泛的应用l l 刚。它的主要优点是描述简单，分类速度快，特别适合人规模的数据处理。 7 上海师范人学硕1 ：研究生学位论文 数据挖掘中决策树算法的研究与优化 2 4 1 1i d 3 算法 l d 3 在1 9 8 6 年首先由q u i n l a n 提出，算法将信息论引入到了决策树算法中， 把信息熵作为选择测试属性的标准，对训练实例集进行分类并构造决策树，其关 键是选择何种属性作为依据来对整个实例空间进行划分。 决策树生成算法的最终目标是要生成一棵输出决策树，对应的输入的是大量 的类别实例。在生成算法过程中有非叶结点表示属性，而叶结点则代表类别。i d 3 算法采用顶向下的方法来进行学习的。构造过程开始，海量实例结点被放在树的 根结点，再利用公式的计算来判断到底用哪个属性来最先进行分类。公式的设计 引入了s h 砌o n 的信息论，主要目的是要计算信息熵【7 1 。 i d 3 的一个优点是：它的建树时间和任务的困难度( 如样本集样本个数，每 个样本的属性个数，研究概念的复杂程度即决策树的结点数) 呈线性递增关系， 计算量相对较小。描述简单，分类速度快，特别适合大规模的数据处理。但存在 的主要问题有：互信息的计算依赖于属性取值的数目较多的特征，而属性取值较 多的属性不一定最优；i d 3 是非递增学习算法；抗噪性差，训练例子中正例和反 例较难控制。 2 4 1 2c 4 5 算法 c 4 5 使用训练样本估计每个规则的准确率。由于这将导致对规则的准确率的 乐观估计，c 4 5 使用一种悲观估计来补偿偏差。作为选择，也可以使用一组独 立于训练样本的测试样本来评估准确性【。尽管如此，c 4 5 算法仍然有如下的 缺点：c 4 5 采用分而治之的策略所得到的决策树不一定是最优的；决策树的结 构调整、性能改善较困难；仅考虑决策树的错误率，未考虑树的结点和深度；对 属性值分组时逐个搜索，分组效率较低。 2 4 1 3s l i q 算法 由于算法采用了“预排序 和。广度优先”这两种技术使得该算法能够处理 比c 4 5 所能处理的大得多的训练集，因此在一定程度上具有良好的随记录个数 和属性个数增长的可扩展性。然而它仍然存在如下缺点：由于需要将类别列表存 放于内存，而类别列表的长度与训练集的长度是相同的，这就在一定程度上限制 了可以处理的数据集的大小；由于采用了预排序技术，而排序算法的复杂度本身 并不是与记录个数成线性关系，因此使得s u q 算法不可能达到随记录数目增长 的线性可扩展性。 2 4 1 4s p i n t 算法 s p r 矾t 算法进一步改进了决策树算法的数据结构，去掉了在s u q 中需要 驻留于内存的类别列表，将它的类别列合并到每个属性列表中。其优点是在寻找 每个结点的最优分裂标准时变得更简单，其缺点是对非分裂属性的属性列表进行 分裂时变得很困难。 2 4 1 5 决策树系统c a i t r o p 8 j ：海师范人学硕十研究生学位论文数据挖掘中决策树算法的研究与优化 k e n n e d y 等人提出了一个决策树系统c a i t r o p ，用遗传算法来构造二叉决 策树。特点：对决策树进行编码。但不同子集产生的决策树的形状、节点个数是 不同的，因此，采用固定长度的位串来表示决策树有时不合适。 2 4 1 6g 触t 算法 z f u 提出一种智能决策树算法g 舢t ，结合了遗传算法、统计抽样和决策树 算法。特点：在一定程度上弥补了基于子集方法的缺陷，但时间代价比较高。 2 4 1 7 决策树剪枝 决策树方法是数据挖掘中最为重要的分类方法之一。决策树是通过对训练数 据集重复分组来构造的。然而，并非所有的训练数据都能准确地分析对象的本质， 实际问题中存在着许多不确定的因素。因而，当用决策树构造算法对这类数据分 类时，所得到的决策树将会变得大而复杂，由此得到的知识规则集也会变得大而 复杂。然而，研究证明，大而复杂的决策树并不意味着可以得到更准确的规则集 i l 引。因此，对决策树进行剪枝非常必要。 各种文献中也给出了许多的剪枝方法【1 9 】f 2 0 】【2 1 】1 2 2 1 。目前主要有预剪枝和后剪 枝，预剪枝技术主要是限制树的充分生长，因其可能会使树的生长过早停止，应 用就相对较少。而后剪枝技术则是待决策树充分生长后再进行剪枝。其中后剪枝 方法已经得到了广泛的讨论，并在实际中得到了成功的运用。所以本文中仅对当 前主要的几种事后剪枝算法的应用以及它们的特点和存在的问题进行分析。 运用后剪枝算法，输入一个未经剪枝的决策树t ( 我们习惯地称为原始树) ， 输出为对它剪枝之后的决策树t ，t 是运用算法将t 的某一个或某几个子树删除 所得的结果。在剪枝过程中，将这些子树删除，而用叶子结点来取代，这个叶子 结点所属的类用这棵子树中大多数训练实例所属类别末代替。常见的后剪枝算法 有6 种，分别是：r e p ( r e d u c e de 盯o rp 1 1 j n j n 曲、p e p ( p e s s i m i s t i ce n o rp 1 1 l n i n g ) ， m e p ( m i n i m u me n d rp m n i n g ) 、c c p ( c o s t c 0 m p l e x i t yp 姗i n g ) 、c v p ( c r i t i c a lv a l u e p t l l n i n 曲和e b p ( e 玎o r - b a s e dp r u n i n 曲。下面我们将简单介绍几种常见的剪枝方法。 1 r e p ( r e d u c e de 玎o rp r u n i n g ) 方法； r e p 方法由q u i n l 锄首先提出i 翻，它是一种最简单的剪枝方法，需要一个独立 的测试集( 剪枝数据集) 来计算子树的精确度。它将树上的每一个结点作为修剪 的侯选对象，其过程大致如下： 自底向上，对于树t 的每一个子树s ，使它成为叶子结点，生成一棵新树。 如果在测试集上，新树能得到一个较小或相等的分类错误，而且子树s 中不包含 具有相同性质的子树，则s 被删除，用叶子结点替代。重复此过程，直到任意1 个子树被叶子结点替代而不增加其在测试集上的分类错误为止。 运用r e p 方法得到的决策树是关于测试集的具有最高精度的子树，并且是规 模最小的树。另外它的计算复杂性是线性的。再者，由于使用独立的测试集，和 原始决策树相比，修剪后的决策树对未来新事例的预测偏差较小。但是该方法也 存在不足之处，它偏向于过度修剪。 9 上海师范大学硕上研究生学位论文数据挖掘中决策树算法的研究与优化 尽管存在一些缺点，r e p 方法仍常常作为一种基准来评价其他剪枝方法的性 能，它对于了解两阶段决策树方法学习的优点和缺点提供了一个良好的初始切入 剧2 4 1 。由于在剪枝集中的事例没有参与原始决策树的创建，因此，和原始决策树 相比，用r e p 剪枝后的决策树对未来事例的预测偏差较少。 2 p e p ( p e s s i m i s t i ce 玎o rp r u n i n g ) 方法： p e p 方法是q u i n l 觚为了克服r e p 方法需要独立剪枝数据集的缺点而提出 的，它不需要分离的剪枝数据集为了提高对未来事例的预测可靠性，p e p 方法 对误差估计增加了连续性校正( o o n t i n u i t yc 0 1 1 r e c t i o n ) 。 由于p e p 使用的是自顶向下剪枝策略的事后剪枝方法，就会出现与事前剪枝 方法同样的问题，即被过度修剪。另外，p e p 方法有时会剪枝失败。 p e p 方法仍然是当前决策树事后剪枝方法中精度较高的算法之一1 2 5 】虽然有 其局限，但它在实际应用中表现出了较高的精度。另外，p e p 方法不需要分离的 剪枝数据集，这对于事例较少的问题非常有利。而且由于在p e p 方法的剪枝过程 中，树中的每棵子树最多需要访问一次，在最坏的情况下，它的计算时间复杂性 也只和未剪枝树的非叶节点数目成线性关系，因而其剪枝效率和速度也相对较理 想。 3 m e p ( m i n i m u m e o rp 邝n i n g ) 方法； m e p 方法由n i b l e t t 和b r a t k o 【1 8 j 首先提出，该方法使用了拉普拉斯概率估计来 提高i d 3 方法在存在噪音数据问题中的性能。m e p 方法的基本思路是采用自底向 上的方式，对于树中每个非叶节点，首先计算该节点的误差e ( t ) 。然后，计算该 节点每个分枝的误差e r ( 砸) ，并且加权相加，权为每个分枝拥有的训练样本比例， 如果e ( t ) 大于e r ( 币) ，则保留该子树；否则，剪裁它。 在m e p 初始版本中，一个最主要的缺点就是e ( t ) 和训练样本的类数目k 相关。 但若借用c c p 方法的思路，那么m e p 方法的计算费用将明显增加。 4 c c p ( c o s t - c o m p l e x i t yp r u n i n g ) 方法 c c p 方法就是著名的c a r t ( c 1 a s s i f i c a t i o n 柚dr e 酉e s s i o nt r e e s ) 剪枝算法l 捌， 它包含两个步骤：首先自底向上，通过对原始决策树中的修剪得到一系列的树 t 0 ，t l ，t 2 ，t k ，其中t i + 1 是由t i 中的一个或多个子树被替换所得到的，t 0 为未经 任何修剪的原始树，t k 为只有一个结点的树。接着评价这些树，根据真实误差率 来选择一个最优秀的树作为最后被剪枝的树。这一方法的关键在于第一步中用训 练集的n 个实例建立了一棵决策树后，怎么样生成一系列的子树。 决策树剪枝主要涉及决策树的简化和精度两方面的问题。决策树剪枝的目的 就是在不减少精度的前提下，简化原始决策树，从而使获得的知识更加容易理解。 我们用表1 对它们进行了比较。 1 0 上海师范人学硕十研究生学位论文数据挖掘中决策树算法的研究j 优化 i a b i elt h ec o m p a r i s o no fp m n j n gm e t h o d s 表l 常用剪枝方式的比较 r e pp e pm e p c c p 剪枝方式白底向上白顶向下白底向上自底向上 是否需要独立剪需要个焉望不需要不需要 枝集 误差估计剪枝集上的误差使用连续校正基于m 概率估c v 方式或标准 估计计误差 计算复杂度o ( n )o ( n )o ( n )o ( n 2 ) 2 4 2 贝叶斯分类算法 贝叶斯分类算法是利用概率统计知识进行分类的算法，主要利用贝叶斯定理 来预测一个未知类别的样本属于各个类别的可能性，选择其中可能性最大的一个 类别作为该样本的最终类别。在许多场合，朴素贝叶斯( n a v eb a y e s ，n b ) 分类算 法可以与决策树和神经网络分类算法相媲美，该算法能运用到大型数据库中，且 方法简单、分类准确率高、速度快。由于贝叶斯定理假设一个属性值对给定类的 影响独立于其它属性的值，而此假设在实际情况中经常是不成立的，因此其分类 准确率可能会下降。为此，就出现了许多降低独立性假设的贝叶斯分类算法，如 蝌( t f e ea u g i n e n t e db a y e sn e 帆o r k ) 算浏z 7 j 。 2 4 3 遗传算法 遗传算法在解决大空间、多峰值、非线性、全局优化等高复杂度问题时显示 了独特的优势【2 8 儿2 9 1 。它是j h h o l l a n d 于1 9 7 5 年提出的一种基于进化论的原理发 展起来的高效的随机搜索与优化的方法，其应用范围几乎涉及到用传统的优化方 法难以解决的优化问题，在工业工程、经济管理、交通运输、工业设计等许多领 域里获得了广泛的应用。 众所周知，遗传算法( g a ，g e n e t i c 舢g o r i t h m ) 是一种基于生物进化论和遗传学 机理的概率搜索方法。利用复制( 选择) 、交叉( 重组) 和变异( 突变) 3 个基本 算子优化求解的技术。遗传算法类似统计学，模型的形式必须预先确定，在算法 实施的过程中，首先对求解的问题进行编码，产生初始群体，然后计算个体的适 应度，再进行染色体的复制、交换、突变等操作，优胜劣汰，适者生存，直到最 佳方案出现为止。 按照g o l d b e r 一4 j 的观点，遗传算法与其他算法的不同在于： ( 1 ) 运算的是解集编码而非解集本身，可以直接对集合、队列、矩阵、图 表等结构对象进行操作； ( 2 ) 搜索始于解的一个群体，是对问题解的集合而不是单个解进行搜索， 从而避免陷入局部最优，逐步逼近全局最优解； ( 3 ) 遗传算法属于随机搜索范畴，但它使用适值函数( 而不使用导数或其 他辅助知识) 来搜寻那些有希望改善解质量的串，这样，既有的放矢，又不 上海帅范大学硕十研究生学位论文 数据挖掘中决策树算法的研究与优化 至于过于复杂； ( 4 ) 遗传算法采用概率的而不是确定的状态转移规则； ( 5 ) 数据源预先要预处理、编码，使处理的数据全部是整数或实数。 遗传算法具有计算简单、优化效果好的特点，它在处理组合优化问题方面也 有一定的优势。因此，它在数据挖掘领域的研究和应用，引起了人们的广泛关注 i 删【3 1 】1 3 2 】1 3 3 】。但还存在以下问题：算法较复杂，收敛于局部极小的过早收敛等难 题未得到彻底解决【3 0 1 【3 4 1 。 2 4 4 粗集理论 粗糙集从诞生到现在虽然时间很短，但是发展得相当快，并且应用到很多领 域中，这是因为它具有如下特点【3 5 l 。 ( 1 ) 它能处理各种数据，包括不完整( 1 n c o m p l e t e ) 的数据以及拥有众多变量 的数据： ( 2 ) 它能处理不精确性和模棱两可( a m b i g u 伽s ) 的数据，包括确定性和非确 定性的情况； ( 3 ) 它能求得知识的最小( r e d u c e ) 表达和知识的各种不同颗粒。 在数据挖掘领域，粗集方法广泛应用于不精确、不确定、不完全的信息的分 类和知识获取。但存在的不足是：每个属性的离散化过程是相互独立的，忽略了 属性之间的关联，从而使得离散的结果中含有冗余或不合理的分割点。 2 5 本章小结 本章首先介绍了数据挖掘产生的背景、定义和模式，接着阐述了分类的目标 和步骤，给出了评价分类模型的三个尺度，并对一些常用分类规则挖掘方法进行 了分析和比较。最后介绍、分析、比较了决策树的剪枝方法。 1 2 上海师范人学硕士研究生学位论文数据挖掘中决策树算法的研究j 优化 第三章遗传算法优化研究 3 1 遗传算法 本章首先介绍了遗传算法的产生背景及其基本概念和具体操作步骤。接着讨 论了模拟退火算法。比较了两种算法的优缺点，从而引出了能克服以上两种算法 部分缺点的混合遗传模拟算法，讨论了其原理，步骤及特点。 3 1 1 遗传算法的产生与发展 1 9 世纪7 0 年代，h o l l a n d 教授认识到了生物的遗传和自然进化现象与人工 自适应系统的相似关系，提出了遗传算法的基本定理一一模式定理( s c h e m a 1 n h e o r e m ) ，从而奠定了遗传算法的理论基础。模式定理揭示出了群体中的优良个 体( 较好的模式) 的样本数将以指数级规律增长，因而从理论上保证了遗传算法是 一个可以用来寻求最优解的优化过程。1 9 7 5 年，h o l l a n d 出版了第一本系统论述 遗传算法和人工自适应系统的专著自然系统和人工系统的自适应似d a p t a t i o ni n n a t u r a l 柚da n i f i c i a ls y s t e m ) 。 以后，h o l l 卸d 等人将该算法加以推广，应用到 优化及机器学习等问题中，并正式定名为遗传算法。 遗传算法的通用编码技术和简单有效的遗传操为其广泛、成功地应用奠定了 基础。2 0 余年来，遗传算法的应用无论是用来解决实际问题还是建模，其范围 不断扩展，这主要依赖于遗传算法本身的逐渐成熟。根据不同的遗传基因表达方 式，不同的交叉和变异算子，特殊算子的引用，以及不同的再生和选择方法，可 以将改进方法归为一个“算法簇”。它基本划分为四个分支：遗传算法( g a ) 、进 化规划( e p ) 、进化策略( e s ) 和遗传程序设计( g p ) 。 最近1 0 年以来，遗传算法的基础理论研究集中在如何优化和改进遗传算 法。国内外众多学者在参数选择、新型算子、参数自适应、协同进化等各个方面 对算法进行了优化和改进，这些将在后面具体提到。总体来看，遗传算法的应用 多基础理论研究少。而众多的研究单位和频繁的国际学术活动集中反映了遗传算 法的学术意义和应用价值。遗传算法己成为一个多学科、多领域的重要研究方向。 3 1 2 遗传算法的基本概念 遗传算法( g e n e t i c g o r i l h m ，简称g a ) 是一种全局优化随机搜索算法。它应 用位串编码技术，先对问题产生初始种群，再对该种群进行适应度评估，继而进 行选择、交叉和变异等操作，采用基于适应度值比例的选择策略在当前种群中选 择个体，使用交叉和变异产生下一代种群。这样一代代遗传下去，直到满足希望 的条件为止。遗传算法因为利用了种群的方式组织搜索，所以可同时搜索解空间 内的多个区域，而且特别适合于大规模并行处理，遗传算法具有自组织、自适应、 自学习等特征，而且优胜劣汰的自然选择和简单的遗传操作使计算不受其搜索空 1 3 e 海师范大学硕上研究生学位论文 数据挖掘中决策树算法的研究0 优化 间限制性条件(