《毕业设计论文数据挖掘决策树算法的研究与改进.doc》由会员分享，可在线阅读，更多相关《毕业设计论文数据挖掘决策树算法的研究与改进.doc（32页珍藏版）》请在三一办公上搜索。
1、海南师范大学本科毕业论文海 南 师 范 大 学 本科生毕业论文（设计）题目：决策树算法的研究与改进姓 名： 学 号： 专 业： 计算机科学与技术 年 级： 05专升本 系 别： 计算机科学与教育技术 完成日期： 2007年5月20日 指导教师： 29本科生毕业论文（设计）独创性声明 本人声明所呈交的毕业论文（设计）是本人在导师指导下进行的研究工作及取得的研究成果，除了文中特别加以标注和致谢的地方外，本论文中没有抄袭他人研究成果和伪造数据等行为 。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。论文（设计）作者签名： 日期：2007年5月21日本科生毕业论文（设计）
2、使用授权声明海南师范大学有权保留并向国家有关部门或机构送交毕业论文（设计）的复印件和磁盘，允许毕业论文（设计）被查阅和借阅。本人授权海南师范大学可以将本毕业论文（设计）的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或其他复印手段保存、汇编毕业论文（设计）。论文（设计）作者签名： 日期：2007年5月21日指 导 教 师 签 名： 日期： 目录1.引言12.决策树算法的研究22.1.基本定义22.1.1.归纳学习的基本概念22.1.2.信息论的基本概念22.1.3.决策树的基本概念32.2.几种常见的决策树算法的简单介绍42.2.1.ID3 算法42.2.2.C4.5算法简介112.
3、2.3.遗传算法GA(Genetic Algorithm)122.3.决策树的评价标准1132.4.决策树的进展与发展方向152.4.1.数据挖掘中决策树算法的主要进展152.4.2.决策树技术面临的挑战及目前研究方向153.关于决策树算法的改进153.1.基于样本离散度6的特征选择方法163.1.1.基本概念163.1.2.基于离散度的改进算法173.1.3.分析与比较183.1.4.小结183.2.利用条件概率的思想来改进决策树算法183.2.1.算法的理论基础与基本思想193.2.2.举例分析193.2.3.分析与比较273.2.4.小结274.总结285.结束语286.致谢28参考文献
4、29挖掘决策树算法的研究与改进作者： 指导老师：（海南师范大学，海口，571158）摘 要：在大量信息展现给人们的时候，“知识爆炸”给人们带来了极大的困扰，如何有效的利用数据成为人们事业成败的关键。本论文主要对决策树的常见算法做初步的研究与探讨，并给出决策树的评价标准。并在此基础上利用最新的决策树算法思想由本人设计实例集验证相关文献中笔者的思想，最后提出自己一点意见和看法。关键词：数据挖掘；决策树；研究；改进 The Research and Improvement Of Data Mining decision-making tree algorithm Author: Tutor: (Ha
5、inan Normal University,HaiKou,571158)Abstract: Nowadays there are so much information tounfold in the people at present, which causes our eyes taking out all in, the knowledge explosion has brought the enormous puzzle to the people, how does the effective use data become the people enterprise succes
6、s or failure the key. This paper mainly discussed the preliminary research and the discussion to the policy-making trees common algorithm, and produces the policy-making trees evaluation criteria, as well as to policy-making tree future discussion. Using the newest policy-making algorithm thought in
7、 this foundation to design in the example collection confirmation correlation literature after myself authors thought, finally proposes a Propose his viewpoint and the view.Key words: Data Mining; decision-making tree; Research; Improvement1.引言随着现代信息技术的飞速发展，在全球范围内掀起了信息化（Information）浪潮。信息产生的渠道多而且宽广，更
8、新的频率日益加快，各行业均产生了大量的信息。面对大量多的数据，人们往往无法找到自己所需要的知识或信息，这就是所谓“信息爆炸3”（Information detonation）以及它给人们带来的困惑。如何有效地利用和处理大量的信息成为当今世界共同关心的问题。随着数据库技术（Database technology）、人工智能（Artificial intelligence）、数理统计（Mathematical statistic）和并行计算（Parallel computation）等技术的发展与融合，数据挖掘（data mining，DM）技术应运而生。自数据挖掘技术诞生以来，关于数据挖掘技术的
9、研究也就开始了。数据挖掘是一门新兴的交叉学科，自提出以来，引起了众多专家学者的广泛关注，数据开采（Data mining）、数据采掘（Data excavation）、知识发现（Knowledge discovery）和信息抽取（Information extracts）等许多同义词相继出现。目前，普遍采用的主要有数据挖掘（DM）和数据库中的知识发现（Knowledge Discovery in Database，简称KDD）。数据挖掘有广义和狭义之分，广义的数据挖掘，指从大量的数据中发现隐藏的、内在的和有用的知识或信息的过程。狭义的数据挖掘是指知识发现中的一个关键步骤，是一个抽取有用模式或建
10、立模型的重要环节。数据挖掘是在对数据实例集全面而深刻认识的基础上，对数据内在和本质的高度抽象与概括，也是对数据从感性认识到理性认识的升华2。如今有多种数据挖掘技术方法，可以分为两大类。决策树就是其中的一种，决策树主要是基于数据的属性值进行归纳分类，常用于分类的层次方法有“if-then1”规则。决策树方法的最大优点就是可理解性，比较直观。它与神经网络（另外一种数据挖掘技术方法）最大的区别是，决策树可以解释如何得出结果的决策过程。其缺点是处理复杂性的数据时，分支数目非常多，管理难度大。同时，还存在数据的“缺值”处理问题。其经典算法有ID3、C4.5、CART、CHAID、SLIQ和SPRINT等
11、。本论文主要对决策树的常见算法（ID3算法、C4.5算法）做初步的研究与探讨，（由于遗传算法与决策树的构造类型相似，这里也有涉及。）并给出决策树的评价标准以及决策树的发展现状和以后的发展方向。并在此基础上利用最新的决策树算法思想由本人设计实例集验证相关文献中笔者的思想，最后提出自己一点意见和看法。2.决策树算法的研究2.1.基本定义2.1.1.归纳学习的基本概念归纳学习(induction Learning) 是符号学习中研究最为广泛的一种方法。给定关于某个概念的一系列已知的正例和反例，从中归纳出一个通用的概念描述。归纳学习能够获得新的概念，创立新的规则，发现新的理论。它的一般操作是泛化（ge
12、neralization）和特化（specialization）。泛化用来扩展一假设的语义信息，以使其能够包含更多的正例，应用于更多的情况。特化是泛化的相反操作，用于限制概念描述的应用范围。2.1.2.信息论的基本概念信息论在决策树学习中有着重要的意义，1948年Shannon1提出并发展了信息论，研究以数学的方法度量并研究信息。通过通信后对信源中各种符号出现的不确定程度的消除来度量信息量的大小。他提出了一系列概念：（1）自信息量。在收到之前，收信者对信源发出的不确定性定义为信息符号的自信息量。即，其中为信源发出的概率。（2）信息熵。自信息量只能反映符号的不确定性，而信息熵可以用来度量信源X整
13、体的不确定性，定义如下： H（X）=p()I（）+P（）I（）+P（）I（） = -其中r为信源X所有可能的符号数，即用信源每发一个符号所提供的平均自信息量来定义信息熵。（3）条件熵。如果信源X与随机变量Y不是相互独立的，收信者收到信息Y。那么，用条件熵H（X/Y）来度量收信者在收到随机变量Y之后，对随机变量X仍然存在的不确定性。设X对应信源符号，Y对应信源符号，为当Y为时X为的概率，则有： H（X/Y）= -（4）平均互信息量。用它来表示信号Y所能提供的关于X的信息良的大小，用I（X，Y）表示： H（X，Y）= H（X）-H（X/Y）信息论的这些基本概念，对决策树来说是非常重要的，是决策树算
14、法的设计与实现基础。2.1.3.决策树的基本概念决策树是定义布尔函数的一种方法,其输入是一组属性描述的对象,输出为yes/ no 决策。它代表一个假设,可以写成逻辑公式。其表达能力限于命题逻辑,该对象的任一个属性的任一次测试均是一个命题。在命题逻辑范围内,决策树的表达能力是完全的。一棵决策树可以代表一个决定训练实例集分类的决策过程,树的每个结点对应于一个属性名或一个特定的测试,该测试在此结点根据测试的可能结果对训练实例集进行划分。划分出的每个部分都对应于相应训练实例集子空间的一个分类子问题,该分类子问题可以由一棵决策树来解决。因此,一棵决策树可以看作是个对目标分类的划分和获取策略。一棵决策树的
15、内部结点是属性或属性的集合（又称测试属性），叶结点是所要学习划分的类。根据决策树各种不同的属性，可分为以下几种：（1）决策树的内结点的测试属性可能是单变量的，即每个内结点只包含一个属性。也可能是多变量的。（2）根据测试属性的不同属性值的个数，可能使得每个内结点有两个或多个分支。如果每个内结点只有两个分支则称之为二叉决策树。（3）每个属性可能是值类型，也可能是枚举类型。（4）分类结果既可能是两类有可能是多类，如果只有两类则称为布尔决策树。因为决策树有不同的等价表示形式，所以会有不同的算法来实现与决策树学习相同的功能。例如：ID3、C4.5、CART、CHAID、SLIQ和SPRINT等等。2.2
16、.几种常见的决策树算法的简单介绍2.2.1.ID3 算法2.2.1.1.ID3 算法简介上面讲到决策树学习是一种归纳学习方法,这里介绍决策树学习的核心算法ID3 算法，ID3 算法是在所有可能的决策树空间中一种自顶向下、贪婪的搜索方法。ID3 算法的关键是确定属性表As中可对训练实例集Es进行的最佳分类的属性A ,即在树的每一个节点上确定一个候选属性,它的测试对训练例的分类最有利。ID3搜索的假设空间是可能的决策树的集合,而ID3搜索目的是构造与训练数据一致的一棵决策树。ID3的搜索策略是爬山法,在构造决策树时从简单到复杂,用信息赢取作为指导爬山法的评价函数。ID3是基于信息熵的决策树分类算法
17、。自从Quinlan描述和分析了ID3算法以来, 有大量的学者围绕该算法作了十分广泛的研究。该算法是根据属性集的取值选择实例的类别。它的核心是在决策树中各级结点上选择属性,用信息增益率作为属性选择标准,使得在每一非叶结点进行测试时,能获得关于被测试例子最大的类别信息。使用该属性将例子集分成子集后,系统的熵值最小,期望该非叶结点到达各后代叶节点的平均路径最短,使生成的决策树平均深度较小,提高分类速度和准确率。ID3 的基本原理如下:设E = F1 F2 Fn 是n 维有穷向量空间,其中是有穷离散符号集, E中的元素e = 叫做例子,其中, j = 1 ,2 , , n。设PE 和NE 是E 的F
18、 两个例子集,分别叫正例集和反例集。假设向量空间E中的正例集PE和反例集NE 的大小分别为p和n ,ID3基于下列两个假设: (1)在向量空间E 上的一棵正确决策树,对任意例子的分类概率同E 中的正、反例的概率一致;(2)一棵决策树能对一例子做出正确类别判断所需的信息量为:I（p,n）=如果以属性A作为决策树的根, A具有v个值(,) ,它将E分为v个子集(, ) ,假设中含有Pi个正例和个反例,子集的信息熵为I(Pi,) ,以属性A为根分类后的信息熵为：因此,以A 为根的信息增益是Gain (A) = I (p,n) - E(A) 。ID3 选择使Gain (A) 最大(即E(A) 最小)的
19、属性作为根结点。对的不同的取值对应的E 的v个子集递归调用上述过程,生成的子结点,， 。ID3 的基本原理是基于两类分类问题,但很容易扩展到多类。设样本集S 共有C类样本,每类样本数为pi ,( i = 1 ,2 ,3 , c) 。若以属性A 作为决策树的根, A 具有V 个值, ,它将E 分成V 个子集, ,假设中含有j类样本的个数为,j = 1,2,c那么,子集的信息量是I()。 以A 为根分类的信息熵为: 选择属性使E( A) 最小,信息增益也将增大。理想的决策树分成3种: (1)叶节点数最小, (2)叶节点深度最小; (3)叶节点数量最少且叶子结点深度最小。决策树的好坏,不仅影响分类的
20、效率,而且还影响分类的准确率。因而许多学者致力于寻找更优的启发式函数和评价函数,洪家荣、Pei - Lei Tu等人分别证明了要找到这种最优的决策树是NP难题。因此人们为了寻求较优的解,不得不寻求各种启发式的方法。有的采用基于属性相关性的启发式函数;有的对生成的决策树进行剪枝处理;有的则扩充决策树,形成决策图。如今普遍采用的是优化算法,基本思想:首先用ID3选择属性F1,建立树T1,左、右子树的属性分别为F2,F3,再以F2,F3为根,重建树T2，T3;较T1,T2,T3的结点个数,选择结点最少的树。对于选择定树的儿子结点采用同样的方法递归建树。尽管作者用一个实验证明能建立理想的决策树,但算法
21、有较大的弱点:时间开销太大,因为每选择一个新的属性,算法都需要建立3 棵决策树,从中选优。2.2.1.2.ID3 算法实例例子一：这里我们通过考察不同的人群购买手机的状况为例,来展示ID3 算法的实际流程。此例假定要按是否买手机对一个集合进行分类,该集合中用来描述人群的属性有age、income、student和credit-rating。age的取值为youth、Middle-aged、old；Income的取值为high、medium和low；student的取值为no和yes；credit-rating的取值为fair和excellent。例子集中共有14个人,如表1 所示。在类别一栏,
22、将正例即“买手机”的人用“Y”标出,反例即“不买手机”的人用“N”标出。表1IDageincomestudentCredit-ratingClass1youthhighnofairN2youthhighnoexcellentN3Middle-agedhighnofairY4oldmediumnofairY5oldlowyesfairY6oldlowyesexcellentN7Middle-agedlowyesexcellentY8youthmediumnofairN9youthlowyesfairY10oldmediumyesfairY11youthmediumyesexcellentY12M
23、iddle-agedmediumnoexcellentY13Middle-agedhighyesfairY14oldmediumnoexcellentN首先利用公式I（p,n）=计算样本分类所需要的期望信息：I（，）= I（9，5）=-=0.940，然后计算每个属性的熵。从age属性开始。需要观察age的每个样本值的Y和N的分布。对每个分布计算期望信息。对于age=“youth”： =2 =3 I（，）=0.971对于age=“middleaged” =4 =0 I（,）=0对于age=“old” =3 =2 I（，）=0.971如果样本按age划分，对一个给定的样本分类所需的期望信息为：E（
24、age）= I（，）+ I（,）+ I（，）=0.694计算其信息增益为：Gain（，）= I（，）- E（age）=0.246类似地，计算Gain（income）=0.029，Gain（student）=0.151和Gain（credit-rating）=0.048。由此可知age在属性中的信息增益最高，故选它做为测试属性。创建根结点，用age标记，并对每个属值得引出一个分支。依次类推可得出决策树如下图：这些例子一开始全部包含在根结点中,为了找出当前的最佳划分属性,先须根据前述公式计算训练例集Es的熵值。则根节点的熵值为:生成如下决策树分类规则： IF age=“youth” AND stu
25、dent = “no” THEN Class=“N”IF age=“Middleaged” THEN Class=“Y”IF age=“youth” AND student = “yes” THEN Class=“Y”IF age=“old” AND credit-rating=“fair” THEN Class=“Y”IF age=“old” AND credit-rating=“excellent” THEN Class=“N”例子二：这里我们通过考察海口某校学生的学习状况为例,来展示ID3 算法的实际流程。此例假定要按某校学生学习成绩好坏这个概念对一个集合进行分类,该集合中用来描述学生的
26、属性有性格、父母教育程度和性别。性格的取值为外向、内向。父母教育程度取值为良好、中等和差。性别的取值为男生、女生。例子集中共有12 名学生,如表2所示。在类别一栏,将正例即“学习成绩好”的学生用“好”标出,反例即“学生成绩差”的学生用“差”标出。表2 某学校学生的例子集性格父母教育程度性别类别内向外向外向内向外向内向外向外向外向内向内向内向良良中差中良差差良中中差女生男生女生女生男生男生女生男生女生女生男生男生好好差差好好好差好差差差这些例子一开始全部包含在根结点中,为了找出当前的最佳划分属性,先须根据信息论中的公式计算训练实例集Es的熵值。则根节点的熵值为: = 1下面分别计算例子集中各个属
27、性的信息赢取值。对属性“性格”来说,分外向和内向两个分支。当v =“外向”时,有4 名“外向”小学生是“学习成绩好”的,有2 名“外向”小学生是“学习成绩差”的。因此, 当v =“内向”时,有2 名“内向”小学生是“学习成绩好”的,有4 名“内向”小学生是“学习成绩差”的。因此, 所以根据“性格”属性来进行例子集分类的信息赢取值为:Gain(Es,性格)=Entropy(Es)-Entropy(Esv,格)=同理,对“父母教育程度”来说:Gain(Es, 父母教育程度)=0.4591 ;对“性别”来说:Gain( Es,性别) = 0 。因为Gain ( Es ,性别) Gain ( Es ,
28、性格) Gain ( Es , 父母教育程度) 可以看出以“父母教育程度”这个属性进行例子集分类的信息赢取值最大,于是“父母教育程度”就被选为用于划分的属性,得到如下图所示的决策树。按“父母教育程度”划分后的决策树现在必须根据所提供的信息进一步分析“父母教育程度”为“中”或“差”的小学生的“学习成绩好坏”,因此必须对“中”和“差”两个分支的实例组成的例子集(共8个例子) 重复上述计算过程。这里简化计算过程,算出:Gain(Es,性格)=0.3113 和Gain(Es,性别) =0.2045。因为Gain ( Es ,性别) Gain ( Es ,性格) ,所以用属性“性格”作第二步划分,于是得
29、到如下图所示的决策树。按“性格”作第二次划分后的决策树现在只有“父母教育程度”为“中”和“差”的“外向”小学生还没有明确类别,它们要用属性“性别”来进一步划分。最终得到的决策树如下图所示。最终得到的决策树IF 父母教育程度=“良” THEN 学习成绩 =“好”IF 父母教育程度=“中”AND 性格=“内向” THEN学习成绩 =“差”IF 父母教育程度=“差”AND 性格=“内向” THEN学习成绩 =“差”IF 父母教育程度=“中”AND 性格=“外向”AND 性别=“女生” THEN学习成绩 =“差”IF 父母教育程度=“中”AND 性格=“外向”AND 性别=“男生” THEN学习成绩
30、=“好”IF 父母教育程度=“差”AND 性格=“外向”AND 性别=“女生” THEN学习成绩 =“好”IF 父母教育程度=“差”AND 性格=“外向”AND 性别=“男生” THEN学习成绩 =“差”但是不能保证ID3算法对任何问题总能做出最佳选择,只能说它在一般情况下能够找出最优决策树。这是ID3算法的最大缺点。2.2.1.3.ID3 算法的优缺点这里对ID3算法作一些总结:ID3通过不断的循环处理,逐步求精决策树,直到找到一个完全正确的决策树。ID3算法构造的决策树是从顶向下归纳形成了一组类似IF THEN的规则。其最原始的程序只是用来区分象棋中的走步,所以区分的类别只有两种T或F ,
31、其属性值也是一些离散有限的值,而今ID3算法已发展到允许多于两个类别,而其属性值可以是整数或实数。下面归纳总结出ID3算法的优缺点如下:优点:搜索空间是完全的假设空间,目标函数必在搜索空间中,不存在无解的危险;全盘使用训练数据,而不是像候选剪除算法一个一个地考虑训练例。这样做的优点是可以利用全部训练例的统计性质进行决策,从而抵抗噪音。缺点:搜索中只维持一个解,不能像候选剪除算法那样返回所有可能的与练例集一致的假设,并优化地查询新例以获得收敛于目标函数的解;其搜索无回溯它可能收敛于局部最优解而丢失全局最优解,因为一个一个地考虑训练例,不容易象剪除算法那样使用新例步进式地改进决策树。2.2.1.4
32、.ID3 算法的发展ID3算法在实际应用中解决了许多问题,对于非增量式学习任务, ID3算法常常是建立决策树的很好的选择。但对于增量式学习任务来说,由于ID3不能增量地接受训练例,这就使得每增加一次实例都必须抛弃原有决策树,重新构造新的决策树,造成了极大的开销。于是ID3 算法被Quinlan1自己扩充为C4.5法,C4.5算法每接受一个新的训练例就更新一次决策树。在C4.5的决策树中,每个结点都保存了可用于计算E值的属性的信息,这些信息由属性的每个取值所对应的正例、反例计数组成。根据放在结点的信息,就可以判断出哪个属性的训练例集Es值最小,从而确定当前用哪一个属性来进行划分。C4.5算法使用
33、了一个适合小数据量的方法:基于训练例自身的性能估计。当然训练例进行估计很可能产生偏向于规则的结果,为了克服这一点,C4.5算法采用了保守估计。它采用的具体方法是:计算规则对其使用的各个训练例分类的精度a ,然后计算这个精度的二项分布的标准差s ,最后对给定信任度(95 %)，取下界(a-1.96)为该规则的性能度量pa；在有大量数据的情况下,s接近于0,pa接近于a ；随着数据量的减少,pa与a的差别将会增大。C4.5算法使用更复杂的方法是为属性A 的各种取值赋以概率,具有未知属性A 值的实例x 按概率值分为大小不等的碎片,沿相应属性A 值的分支向树的下方分布,实例的碎片将用于计算信息赢取。这
34、个实例碎片在学习后,还可以用来对属性值不全的新实例进行分类。下面就C4.5算法的基本思想做简要的概述。2.2.2.C4.5算法简介C4.5算法是在ID3的基础上改进而成的，它继承了ID3的全部优点，更好地修正了ID3的剪枝算法并对高分支属性、数值型属性和含空值属性地整理有了系统地描述。例如CN4.5中也采用“窗口”( Windows ) 的概念,先从所有的事例中选取一部分用做构造决策树,再利用剩余的事例测试决策树并对它进行调整。CN4.5算法能处理连续值类型的属性,它还能对属性的取值集合进行等价类划分,划分在同一类的属性值在属性值判断时将走到同一分支上。再加上CN4.5算法的思想简单,实现高效
35、,结果可靠,使CN4.5在归纳学习中的地位更加显著。但是CN 4.5算法也有如下不足之处:第一, CN4.5采用的是分而治之的策略,在构造树的内部结点的时候是局部最优的搜索方式。所以它所得到的最终结果尽管有很高的准确性,仍然得不到全局最优的结果。第二,在CN4.5评价决策最主要的依据是决策树的错误率,而对树的深度,结点的个数等不进行考虑,而树平均深度直接对应着决策树的预测速度,树的结点个数则代表树的规模。第三,一边构造决策树,一边进行评价,决策树构造出来之后,很难再调整树的结构和内容,决策树性能的改善十分困难。第四, CN4.5在进行属性值分组时逐个试探,没有一种使用启发搜索的机制,分组时的效
36、率较低。2.2.3.遗传算法GA(Genetic Algorithm)遗传算法是一种通用搜索算法。它通过模拟自然界进化的过程来演化出解决问题的较优方法。它把一些解决方案用一定的方式来表示,放在一起称为群体(population) 。每一个方案的优劣程度即为适应性(fit2ness),根据自然界进化的“优胜劣汰”的原则,逐步产生出它们的后代,使后代具有更强的适应性。这样不断演化下去,就能得到更优的解决方案。它具有思想简明、健壮性好等特点。在工农业、经济政治、科研方面应用极为广泛。在计算机科学领域中的机器学习领域更是大有用武之地。群体搜索策略和个体之间的信息交换是遗传算法的两大特点,主要表现在全局
37、最优性和潜在的并行性。CN4.5在构造决策树时并不一定得到最优的决策树,那么是不是能用遗传算法的思想能够得到解决呢,回答是肯定的。虽然遗传算法的进发结果并不能保证得到理论意义上的最佳的决策树,但是它提供了一种试探的过程。由于适者生存的特点,使得适应性较优的决策树能尽量保留,又由于它提供了对决策树的调整和重新组合的机制,使得有更优适应性的决策树在进发过程中出现。那么如何应用遗传算法,如何基于决策树的结构和性质定义遗传算子呢?遗传算子主要有三种:复制(reproduction) 、重组(crossover) 、算子和变异(mutation) 算子。一般的算子都是对特征串进行操作的。针对决策树的结构
38、和特性,我们定义遗传算子:首先定义适应函数(fitness function) 。遗传算法是一个探索过程,它对树的评价是在树完全作成以后进行的,可以将树的深度、结点数等因素都考虑在内。复制算子的定义与常用的复制算子的定义一致。重组算子的定义就要用到决策树结构特点。我们有以下几种重组方式: (1) 用后代结点代替祖先结点,类似于书的剪枝操作。(2) 同一棵树的两个结点互相交换。(3) 两个树之间结点交换,这里所说的结点交换就是交换以这些结点为根的子树。变异是产生全局最优的重要原因,尽管大多数的变异不能产生良好的效果,对于决策树,我们定义的变异算子是改变树的结构或者改变树中结点内的信息。针对内部结
39、点和叶节点,属性值的分组与否这些不同情况,变异的处理是不一样的。对于内部结点内,变异操作可能产生下面的结果:(1) 改变结点上判断的属性。(2) 改变属性值的分组情况。(3) 改变该结点下的子树的分支情况,改变属性值与分支子树的对应。(4) 改变该结点的分支数。这样经过重组、变异算子运算得到的新的决策树需要进行结构上的完整性和一致性处理。调整变异结点及其子结点的树结构使之为一棵完整的正确的决策树;去除从树根到叶节点路径上重复的属性判断等。决策树的构造分为以下几步:(1) 第一代群体的产生；(2) 产生下一代；(3) 产生最优决策树。2.3.决策树的评价标准1以上讨论了一些决策树构造算法，并且对
40、这些算法的优缺点进行了分析。下面，给出评价决策树的一些标准。1过学习在由决策树学习的过程中，我们必须在一组假设中选择一个，使得它与训练实例集相匹配。我们已经看到不可能在没有任何偏置（bias）的情况下学习。如果预先字段所要学习的函数属于整个假设空间中一个很小子集，那么即使在训练实例不完整的情况下，我们也有可能从训练实例集丧钟学习有用的假设，来使得它能够对未知的实例进行正确分类。即使如此，我们还是希望有一个大的训练实例集。因为训练实例集越大，关于分类的信息越多。在这种情况下，即使我们随机地从与训练实例集相一致的假设集中选择一个，它也能对未知实例的分类进行预测。相反，即使在有偏置的情况下，如果训练
41、实例集与整个假设空间相比过小，仍有过多的与训练实例相一致的假设供我们选择，我们做出假设的泛化能力将很差。当有过多的假设与训练实例集相一致的时候，则成为过学习。过学习是所有机器学习都要考虑的问题。过学习将导致我们所做出的假设泛化能力过差。所以，也可以如下定义过学习。假设h对所有的训练实例分类的错误率为，对整个实例空间D分类的错误率为。如果存在另一个假设使得：并且 一般将成为重替换（resubstitution）错误率，在本书中将其简记为r错误率。而在此一般将在测试集中的错误率成为错误。Cohen和Jensen提出了一个有用的理论来解释为何会出现过学习的情况。他们提出，当一个算法过高估计增加树的复
42、杂性对于分类的正确性的贡献，那么就会出现过学习现象。主要有三种原因使得算法过高估计这些贡献：（1）检测模型的数目：算法检测模型数目与出现过学习的可能性是正相关的。（2）不同的正确性估计：小的训练实例集更不可能代表数据的内在分布，更有可能产生过学习的现象。而大一些的训练实例集产生过学习问题的可能性更小。（3）选择最优树：通过极大化某个特定评价函数来选择最优决策树增加了过学习的可能性。Cohen和Jensen利用事后剪枝的方法验证了他们的理论。2有效性最为直接的估计一棵决策树在测试实例集合上的性能的方法是，将它在测试实例集合上进行实际测试，这样就可以选中在测试集合中表现最好的一棵决策树。但是这种方
43、法等价于在测试实例集中训练决策树，这在大多数情况下是不现实的。所以一般并不采用这种方法，而是采取用训练实例集本身来估计训练算法的有效性。一种最简便的方法是用训练实例集的一部分（例如3/4的训练实例）对决策树进行训练，而用另外一部分（例如1/4的训练实例）对决策树检测其有效性。但是，这样做将会减小训练实例空间，而增大过学习的可能性，所以这种方法也不可取。3交叉有效性在此方法中，我们将训练实例集T分为互不相交且大小相等的k个子集，.。对于任意子集，用T-训练决策树，之后用对生成的决策树进行测试，得到错误率，然后估计整个算法的错误率：e=可以看出随着k的增加，所生成的树的数目也随之增加，算法的复杂度
44、也会变大。4余一有效性（leave-one-out validation）这种有效性的度量与交叉有效性类似，不同之处在于将每个的大小定为1。假设|T|=n，则错误率为：e=显然，这种有效性测量算法的复杂度过高，但是它的准确程度也是最高的。5决策树的复杂程度决策树的复杂程度也是度量决策树学习效果的一个重要标准。对于给定的描述语言，如果决策树是单变量（univariate）的，那么决策树的复杂程度主要由树的结点个数决定；如果是多变量（multivariare）的，则主要是由结点中属性的总个数决定。2.4.决策树的进展与发展方向2.4.1.数据挖掘中决策树算法的主要进展传统的决策树算法主要是针对小数
45、据集的,大都要求训练集常驻内存,这使得在处理数据挖掘任务时,传统决策树算法在可伸缩性、精度和效率方面受到了很大的限制。而在实际的数据挖掘应用中我们面临的数据集往往是容量巨大的数据库或者数据仓库,在构造决策树时需要将庞大的数据在主存和缓存中不停的导入导出,使得运算效率大大降低。针对以上问题,许多学者提出了处理大型数据集的决策树算法。其中主要在以下四个方面的应用：1、数据预处理；2、抽样方法；3、数据的重构；4、结合上述的遗传算法等其他算法。2.4.2.决策树技术面临的挑战及目前研究方向目前决策树技术的主要研究方向8有以下几点:1 决策树算法的并行性研究2 寻找新的构造决策树的方法3 寻找更好的简化决策树的方法4 研究产生决策树的训练和检验数据的大小及特性与决策树特性之间的关系5 不确定环境下决策树研究6 将决策树用于多智能体控制并不多见7 决策树时间复杂度与准确性之间的矛盾8 决策树技术的软件实现3.关于决策树算法的改进由以上讨论可知：ID3算法存在种种缺陷，如：算法的计算时间是例子个数、特征个数、节点个数之积的线性函数。另外大量实验
