毕业论文《数据挖掘决策树算法的研究与改进(终稿)》

1、海南师范大学本科生毕业论文（设计）题目:决策树算法的研究与改进1=.si姓 名：学 号：专 业： 计算机科学与技术年 级：系 别：计算机科学与教育技术完成日期：指导教师：讲师目录2. 决策树算法的研究22.1基本定义22. 1. 1.归纳学习的基本概念22. 1.2.信息论的基木概念22. 1.3.决策树的基本概念32. 2.几种常见的决策树算法的简单介绍42. 2. 1. id3 算法42.2. 2. c4. 5 算法简介112. 2. 3.遗传算法 ga (genet i c ai gor i thm)122.3. 决策树的评价标准1132.4. 决策树的进展与发展方向152.4.1. 数

2、据挖掘中决策树算法的主要进展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参考文献29挖掘决策树算法的研究与改进作者：张亚磊 指导老师：徐冬讲师(海南师范大学,海口，571158)摘 要：在大量信

3、息展现给人们的时候，“知识爆炸”给人们带来了极大的困扰，如何有效的利用数据成为人们事 业成败的关键。本论文主要对决策树的常见算法做初步的研究与探讨，并给出决策树的评价标准。并在此基础上利 用最新的决策树算法思想由本人设计实例集验证相关文献中笔者的思想，最后提出自己一点意见和看法。关键词：数据挖掘；决策树；研究；改进the research and improvement of data mining decision-makingtree algorithmauthor:yalei zhang tutor: dong xu lecturer(hainan normal university,h

4、aikou,571158)abstract： nowadays there arc so much information tounfbld in the people at present, which causes our eyes taking out all in, nthe knowledge explosion11 has brought the enormous puzzle to the people, how does the effective use data become the people enteiprise success or failure the key.

5、 this paper mainly discussed the preliminary research and the discussion to the policy-making tree's common algorithm, and produces the policy-making trcc*s evaluation criteria, as well as to policy-making tree future discussion. using the newest policymaking algorithm thought in this foundation

6、 to design in the example collection confirmation coitelation literature after myself authors thought, finally proposes a propose his viewpoint and the viewkey words： data mining; decision-making tree; research; improvement1. 引言随着现代信息技术的飞速发展，在全球范围内掀起了信息化(infonnalion)浪潮。信息产牛的 渠道多而且宽广，更新的频率日益加快，各行业均产牛

7、了大量的信息。回对大量多的数据，人们往 往无法找到口己所需要的知识或信息，这就是所谓“信息爆炸” (information detonation)以及 它给人们带來的困惑。如何有效地利用和处理大量的信息成为当今世界共同关心的问题。随着数据 库技术(database technology) 人酣吉(artificial intelligence)、独用乡计(mathematical statistic) 和并行计算(parallel computation)等技术的发展与融合,数据挖掘(datamining, dm)技术应运 而生。自数据挖掘技术诞生以來，关于数据挖掘技术的研究也就开始了。数据挖

8、掘是一门新兴的交叉 学科，白提出以来，引起了众多专家学者的广泛关注，数据开采(data mining)、数据采掘(data excavation)> 知识发现(knowledge discovery)和信息抽取(information extracts)等许多同义词相 继出现。目前，普遍采用的主要有数据挖掘(dm)和数据库中的知识发现(knowledge discovery in database,简称kdd）。数据挖掘有广义和狭义z分，广义的数据挖掘，指从大量的数据中发现 隐藏的、内在的和有用的知识或信息的过程。狭义的数据挖掘是指知识发现中的一个关键步骤，是 一个抽取有用模式或建立模型

9、的重要环节。数据挖掘是在对数据实例集全而而深刻认识的基础上, 对数据内在利本质的高度抽象与概括，也是对数据从感性认识到理性认识的升华2。如今有多种数据挖掘技术方法，可以分为两大类。决策树就是其中的-种，决策树主要是基于 数据的属性值进行归纳分类，常用于分类的层次方法有“ifthenl”规则。决策树方法的最大优 点就是可理解性，比较直观。它与神经网络（另外一种数据挖掘技术方法）最大的区别是，决策树 可以解释如何得出结果的决策过程。其缺点是处理复杂性的数据吋，分支数目非常多，管理难度大。 同时，还存在数据的“缺值”处理问题。其经典算法有id3、c4.5、cart、chaid、sliq和sprint

10、 等。本论文主要对决策树的常见算法（id3算法、c4.5算法）做初步的研究与探讨，（由于遗传算 法与决策树的构造类型相似，这里也有涉及。）并给出决策树的评价标准以及决策树的发展现状和 以后的发展方向。并在此基础上利用最新的决策树算法思想山本人设计实例集验证相关文献中笔者 的思想，最后提出自己一点意见和看法。2. 决策树算法的研究2. 1.基本定义2. 1. 1.归纳学习的基本概念归纳学习（induction learning）是符号学习屮研究最为广泛的一种方法。给定关于某个概念的 一系列已知的正例和反例，从屮归纳出一个通用的概念描述。归纳学习能够获得新的概念，创立新 的规则，发现新的理论。它的

11、一般操作是泛化（generalization）和特化（specialization）。泛化用 来扩展一假设的语义信息，以使其能够包含更多的正例，应川于更多的情况。特化是泛化的相反操 作，用丁限制概念描述的应用范围。2. 1.2.信息论的基本概念信息论在决策树学习中有着重要的意义，1948年sharmonl提出并发展了信息论，研究以数学 的方法度量并研究信息。通过通信后对信源中各种符号岀现的不确定程度的消除来度量信息量的大 小。他提出了一系列概念：（1）口信息量。在收到z前，收信者对信源发出的不确定性定义为信息符号的口信息量。即, 其中为信源发出的概率。（2）信息炳。自信息量只能反映符号的不确定

12、性，i何信息嫡可以用來度量信源x整体的不确定 性，定义如下：h （x） =p（a.） i （ai） +p （色）i（偽）+ +p（%）i（坷）r二-工/?（q）lo g（aj/=!其屮t为信源x所有可能的符号数，即川信源每发一个符号所提供的平均自信息童来定义信息 爛。（3）条件嫡。如果信源x与随机变量y不是相互独立的，收信者收到信息y。那么，用条件爛h （x/y）來度量收信者在收到随机变彊y之后，対随机变量x仍然存在的不确定性。设x対应信源符号,y对应信源符号，为当y为时x为的概率，则有：h （x/y）二心小0*生 /bj/=! j=l（4）平均互信息量。川它来表示信号y所能提供的关于x的信息

13、良的人小，川i （x, y）表示:h （x, y） = h （x） -h （x/y）信息论的这些基本概念，对决策树来说是非常虫要的，是决策树算法的设计与实现基础。2. 1.3.决策树的基本概念决策树是定义布尔函数的一种方法，其输入是一组属性描述的对彖,输出为yes/ no决策。它代 表一个假设，可以写成逻辑公式。其表达能力限丁命题逻辑，该对象的任一个属性的任一次测试均是 一个命题。在命题逻辑范围内，决策树的表达能力是完全的。一棵决策树可以代表一个决定训练实 例集分类的决策过程，树的每个结点对应于一个属性名或一个特定的测试，该测试在此结点根据测 试的可能结果对训练实例集进行划分。划分出的每个部分

14、都对应于相应训练实例集子空间的一个分 类子问题，该分类子问题可以由一棵决策树来解决。因此，一棵决策树可以看作是一个对目标分类的 划分和获取策略。-棵决策树的內部结点是属性或属性的集合（乂称测试属性），叶结点是所要学习划分的类。 根据决策树各种不同的属性，可分为以下儿种：（1）决策树的内结点的测试属性可能是单变量的，即每个内结点只包含一个属性。也可能是 多变量的。（2）根据测试属性的不同属性值的个数，可能使得每个内结点有两个或多个分支。如果每个lw内结点只有两个分支则称z为二叉决策树。（3）每个属性可能是值类型，也可能是枚举类型。（4）分类结果既可能是两类有可能是多类，如果只有两类则称为布尔决策

15、树。因为决策树有不同的等价农示形式，所以会有不同的算法来实现与决策树学习相同的功能。例 如:id3、c4.5、cart、ch aid > sliq 和 sprint 等等。2. 2.几种常见的决策树算法的简单介绍2.2.1. id3 算法2.2.1.1. id3算法简介上面讲到决策树学习是一种归纳学习方法，这电介绍决策树学习的核心算法一1d3算法，1d3 算法是在所有可能的决策树空间中一种自顶向下、贪婪的搜索方法。id3算法的关键是确定屈性表 as中可对训练实例集es进行的最佳分类的属性a ,即在树的每一个节点上确定一个候选属性，它的 测试对训练例的分类最有利。id3搜索的假设空间是对能

16、的决策树的集合，而id3搜索目的是构造为 训练数据一致的一棵决策树。id3的搜索策略是爬山法，在构造决策树时从简单到复杂，用信息赢取 作为指导爬山法的评价函数。td3是基于信息爛的决策树分类算法。自从quinlan描述和分析了td3算法以來，有大量的学者 围绕该算法作了丁分广泛的研究。该算法是根据属性集的取值选择实例的类别。它的核心是在决策 树中各级结点上选择属性,川信息增益率作为属性选择标准，使得在每一非叶结点进行测试时，能获 得关于被测试例子最人的类别信息。使丿u该属性将例子集分成了集后，系统的爛值最小，期槊该非叶 结点到达各后代叶节点的平均路径最短，使生成的决策树平均深度较小，提高分类速

17、度和准确率。td3的基木原理如下：设e = f1 xf2 x-xfn是n维有穷向量空间，其中巧是有穷离散符号 集，e中的元素e = <vh v2,-, v>叫做例子，其中片丘耳,j二1,2,，n。设pe和ne是e的 f两个例了集，分别叫正例集和反例集。假设向屋空间e中的正例集pe和反例集ne的人小分别为p和n , jld3基于下列两个假设：（1）在向 量空间e上的一棵正确决策树，对任意例子的分类概率同e屮的正、反例的概率一致;（2）-棵决策 树能対一-例子做出正确类别判断所需的信息量为：i （p, n） = log2 log2-p+np+斤p+n如果以属性a作为决策树的根，a具有v

18、个值（%,匕，匕），它将e分为v个子集（ee?,ev)，假设e；中含有pi个正例和耳个反例，子集&的信息爛为i(pi, 72,.),以属性a为根分类后的信 息爛为:/=! p + n因此，以a为根的信息增益是gain (a) = t (p, n) - e(a)。id3选择使gain (a)最大(即e(a) 最小)的属性力作为根结点。对月的不同的取值对应的e的v个子集耳递归调用上述过程，生成 /的子结点,b, b?,by 0id3的基本原理是基于两类分类问题，但很容易扩展到多类。设样本集s共有c类样本，每类样 本数为pi , ( i = 1 ,2 ,3 ,c) o若以属性a作为决策树的根

19、，a具有v个值, v2,-匕， 它将e分成v个子集厶，疋2,，& ，假设&中含有j类样本的个数为心，j二1,2,c那么， 子集ej的信息量是i(£,.)o/(£,)=y-*iog-'台i&i 1毘1以a为根分类的信息爛为：e(a)£*(eji=l i 匕 i选择属性必使e(a)最小,信息增益也将增大。理想的决策树分成3种：(1)叶节点数最小，(2)叶节点深度最小；(3)叶节点数量最少且叶子结 点深度最小。决策树的好坏，不仅影响分类的效率,而冃还影响分类的准确率。因而许多学者致力于 寻找更优的启发式函数和评价函数，洪家荣、pei -

20、lei tu等人分别证明了要找到这种最优的决策 树是np难题。因此人们为了寻求较优的解，不得不寻求各种启发式的方法。有的采用基于属性相关 性的启发式函数;有的对生成的决策树进行剪枝处理;有的则扩充决策树,形成决策图。如今普遍采用的是优化算法，基本思想:首先用id3选择属性f1,建立树t1,左、右子树的属性分 别为f2, f3,再以f2, f3为根,重建树t2, t3;较tl, t2, t3的结点个数，选择结点最少的树。对于选择定 树的儿子结点采用同样的方法递归建树。尽管作者用一个实验证明能建立理想的决策树，但算法有 较大的弱点：时间开销太尢因为每选择一个新的属性，算法都需要建立3棵决策树，从中

21、选优。2. 2. 1.2. id3算法实例例子一：这里我们通过考察不同的人群购买手机的状况为例,来展示id3算法的实际流程。此例假定耍 按是否买手机对一个集合进行分类，该集合中用来描述人郡的属性有age. income, student和 credit-ratingo age 的取值为 youth、middle-aged, old； income 的取值为 high medium 和 low；student的取值为no和yes； credit-rating的取值为fair和excel 1 ento例子集中共有14个人， 如表1所示。在类别一栏，将正例即“买手机”的人用“y”标出，反例即“不买手

22、机”的人用“n” 标出。表1idageincomestudentcredit-ratingclass1vouthhighnofairn2youthhighnoexcellentn3middle-agedhighnofairy4oldmediumnofairy5oldlowyesfairy6old1 owyesexcellentn7middle-agedlowyesexcellenty8youthmediumnofairn9youthlowyesfairy10oldmediumyesfairy11youthmediumyesexcel lenty12middle-agedmediumnoexce

23、llenty13middle-agedhighyesfairy14oldmediumnoexcellentn首先利用公式i（p,n）二-一匕-log2-log2-计算样本分类所需要的期望信息：p+np+np+n99551（ kp ） = t （9, 5）二-一log2log.=0. 940,然后计算每个属性的炳。从且ge属性1214“14 14 t4开始。需要观察age的每个样木值的y和n的分布。对每个分布计算期槊信息。对于age= "middleaged”对于age二"old”杳 3 分 25, 丫23)=0-971如果样木按age划分，对一个给定的样木分类所需的期望信息

24、为：545e (age) t (乙,) + t () + t (,乙q)=。 694141112142122141323计算其信息增益为：gaincr, §)二1(匕，y2)- v. (age) =0.246类似地，计算gain (income) =0. 029, gain (student) =0. 151 和gain (credit-rating) =0. 048o（1此可知age在屈性中的信息增益最高，故选它做为测试屈性。创建根结点，用age标记，并对每个属值得引出一个分支。依次类推可得出决策树如下图:这些例了一开始全部包含在根结点屮，为了找出当前的最佳划分属性，先须根据前述公

25、式计算studentstudent生成如卜决策树分类规则:if age= “youth” and student = “no”then cl ass二 “n”if age= "middleaged”then class= “y”if age= “youth” and student = "yes”then class= “y”then class= “y”then class= “n”if age= "old" and credit-rating二 “fair”if age= "old" and credit-ratings &quo

26、t;excellent”例子二:这里我们通过考察海口某校学牛的学习状况为例，来展示id3算法的实际流程。此例假定要按 某校学生学习成绩好坏这个概念对一个集合进行分类,该集合小用来描述学生的屈性有性格、父母 教育程度和性别。性格的取值为外向、内向。父母教育程度取值为良好、中等和差。性别的取值为 男牛、女牛。例子集中共有12名学牛，如表2所示。在类别一栏，将正例即“学习成绩好”的学生用 “好”标出，反例即“学牛成绩差”的学牛用“差”标出。表2 某学校学牛的例子集性格父母教育程度性别类别内向良女生好外向良男生好外向中女生差内向差女生差外向中男生好内向良男生好外向差女生好外向差男生差外向良女生好内向中

27、女生差内向中男生差内向差男生差这些例子一开始全部包含在根结点中，为了找出当前的最佳划分属性，先须根据信息论中的公 式计算训练实例集es的炳值。则根节点的炳值为：曲"2)"善log 2卷一善log 2議下而分别计算例子集中各个属性的信息赢取值。对属性“性格”来说，分外向和内向两个分支。 当v二“外向”时，有4名“外向”小学生是“学习成绩好”的，有2名“外向”小学生是“学习成绩差”的。因此,4422entropy（es 性格外向）=一 $ log 2 帀-log 2 币= 0.9183当v二“内向”时，有2名“内向”小学生是“学习成绩好”的，有4名“内向”小学生是“学习成绩差”

28、的。因此,4422entropye 内向）二石log 2帀-log 2 = 0.9183所以根据“性格”属性來进行例子集分类的信息赢取值为：gain （es,性格）=entropy （es）-entropy （esv,格）=1 -（*0.9183+丄*0.9183）=0.08172 2同理，对“父母教育程度”来说:gain（es,父母教育程度）=0. 4591 ;对"性别”来说:gain（ es,性别）=0。因为gain （ es ,性别） gain （ es ,性格）gain （ es ,父母教育程度）可以看出以“父 母教冇程度”这个属性进行例子集分类的信息赢取值最大，于是“父母教

29、冇程度”就被选为用于划 分的属性，得到如卜图所示的决策树。r好好妹 4:1:也生 女男男女 , , , , 良良良、li , , , , 向向向向 帀外内厂丙向, 外向, 内向,中，女生：粵 中，男生：好i中，男生:差 中,女生:差丿f向, 外向, 内向, 外向,差, 差, 差, 差,按“父母教育程度”划分后的决策树现在必须根据所提供的信息进一步分析“父母教育程度”为“中”或“差”的小学牛的“学习 成绩好坏”，因此必须对“中”和“差”两个分支的实例组成的例子集（共8个例子）重复上述计算 过程。这里简化计算过程，算出：gain（es,性格）=0.3113和gain（es,性别）二0.2045。因

30、为gain （ es，性别） gain （ es ,性格），所以用属性“性格”作第二步划分，于是得到如 下图所示的决策树。向向向向向向男生:女生:父母教育程度4:4:生虫 女男男女 , , , 良良良良生生 女男 f f性格外向内向'石向，'差，女生：斥:”向，差，男生：差外向，差，女生：好 外向，差，男生：差按“性格”作第二次划分后的决策树现在只有“父母教育程度”为“屮”和“差”的“外向”小学生还没有明确类别，它们要川属 性“性别”来进一步划分。最终得到的决策树如下图所示。r良良良 , , , , 向向向向内向，中，女生: 内向，中，男牛:性别性格父母教育程度电也生牝 女男男

31、女性格性别男生"女生外向，中，男牛：好外向，中，女生一男生女生:差外向,差,男生:差外向,差，女生:好then学习成绩二“好”then学习成绩二“差”then学习成绩二“差”then学习成绩二“差”then学习成绩二“好”then学习成绩二“好”then学习成绩二“差”最终得到的决策树if父母教育程度二“良”if父母教育程度二“中” and性格二“内向”if父母教育程度二“差” and性格二“内向”if父母教育程度二“中” and性格二“外向” and性别二“女生”if父母教育程度二“中” and性格二“外向” and性别二“男生”if父母教育程度二“差” and性格二“外向” an

32、d性别二“女生”if父母教育程度二“差” and性格=“外向” and性别二“男生”但是不能保证1d3算法对任何问题总能做出最佳选择，只能说它在一般情况下能够找出最优决 策树。这是1d3算法的最人缺点。2. 2. 1.3. id3算法的优缺点这里対id3算法作一些总结：id3通过不断的循环处理，逐步求精决策树，直到找到一个完全止确 的决策树。id3算法构造的决策树是从顶向下归纳形成了一组类似if -then的规则。其最原始的程 序只是用來区分象棋中的走步，所以区分的类别只有两种t或f ,其属性值也是一些离散有限的值， 而今1d3算法已发展到允许多于两个类别，而其属性值可以是整数或实数。下面归纳

33、总结出1d3算法 的优缺点如卞：优点:搜索空间是完全的假设空间，忖标函数必在搜索空间中，不存在无解的危险;全盘使用训 练数据，而不是像候选剪除算法一个一个地考虑训练例。这样做的优点是可以利用全部训练例的统 计性质进行决策，从而抵抗噪音。缺点:搜索中只维持一个解，不能像候选剪除算法那样返冋所有口 j能的与练例集一致的假设，并 优化地杏询新例以获得收敛于目标函数的解;其搜索无冋溯它可能收敛于局部最优解而丢失全局最 优解，因为一个一个地考虑训练例,不容易象剪除算法那样使用新例步进式地改进决策树。2.2. 1.4. id3算法的发展11)3算法在实际应用中解决了许多问题，对于非增量式学习任务，id3算

34、法常常是建立决策树的 很好的选择。但对于增暈式学习任务来说，h于id3不能增量地接受训练例，这就使得每增加一次实 例都必须抛弃原有决策树，匝新构造新的决策树,造成了极大的开销。于是id3算法被quinlanel 自己扩充为c4. 5法,c4. 5算法每接受一个新的训练例就更新一次决策树。在c4. 5的决策树屮，每个结 点都保存了可用于计算e值的屈性的信息，这些信息由属性的每个取值所对应的正例、反例计数组 成。根据放在结点的信息,就可以判断出哪个属性的训练例集es值最小，从而确定当前用哪一个属性 來进行划分。c4. 5算法使用了一个适合小数据量的方法:基于训练例口身的性能估计。当然训练例进行估计

35、 很可能产牛偏向于规则的结果，为了克服这一点,c4. 5算法采用了保守佔计。它采用的具体方法是： 计算规则对其使用的各个训练例分类的精度a ,然后计算这个秸度的二项分布的标准差s ,最后对给 定信任度(95 %),取下界(a-1.96)为该规则的性能度量pa；在有大量数据的情况下,s接近于0, pa 接近于a ;随着数据量的减少,pams的差别将会增大。c4. 5算法使用更复杂的方法是为属性a的各 种取值赋以概率,具有未知屈性a值的实例x按概率值分为大小不等的碎片，沿相应属性a值的分 支向树的下方分布，实例的碎片将用于计算信息赢取。这个实例处片在学习后,还可以用来对属性值 不全的新实例进行分类

36、。下而就c4. 5算法的基木思想做简要的概述。2.2.2. c4. 5算法简介c4.5算法是在1d3的基础上改进而成的，它继承了jld3的全部优点，更好地修正了 1d3的剪枝算 法并对高分支属性、数值型属性和含空值属性地整理有了系统地描述。例如cn4. 5屮也采川“窗口” (windows )的概念，先从所有的雷例屮选取一部分川做构造决策树，再利川剩余的事例测试决策树 并对它进行调整。cn4. 5算法能处理连续值类型的屈性，它还能对属性的取值集合进行等价类划分， 划分在同一类的属性值在属性值判断时将走到同一分支上。再加上cn4. 5算法的思想简单，实现高效, 结杲可靠，使cn4. 5在归纳学习

37、中的地位更加显著。但是cn 4. 5算法也有如卞不足之处：笫一，cn4. 5采用的是分而治z的策略，在构造树的内部结点的时候是局部最优的搜索方式。所 以它所得到的最终结杲尽管有很高的准确性，仍然得不到全局最优的结果。第二，在cn4. 5评价决策最主要的依据是决策树的错误率，而対树的深度,结点的个数等不进行 考虑，而树平均深度直接对应着决策树的预测速度，树的结点个数则代表树的规模。第三，一边构造决策树,一边迓行评价，决策树构造出來之后,很难再调整树的结构和内容，决策 树性能的改善十分困难。笫四，cn4. 5在进行屈性值分组时逐个试探，没有一种使川启发搜索的机制，分组时的效率较 低。2. 2. 3

38、.遗传算法 ga (genet ic al gor i thm)遗传算法是一种通用搜索算法。它通过模拟自然界进化的过程來演化出解决问题的较优方法。 它把一些解决方案用一定的方式來表示，放在一起称为群体(population)。每-个方案的优劣程度 即为适应性(fit2ness),根据自然界进化的“优胜劣汰”的原则，逐步产生出它们的后代，使后代具 有更强的适应性。这样不断演化下去,就能得到更优的解决方案。它具有思想简明、健壮性好等特 点。在工农业、经济政治、科研方而应用极为广泛。在计算机科学领域中的机器学习领域更是人有 用武z地。群体搜索策略和个体z间的信息交换是遗传算法的两大特点，主要表现在全

39、局最优性和潜在的 并行性。cn4. 5在构造决策树时并不一定得到最优的决策树，那么是不是能用遗传算法的思想能够得 到解决呢，回答是肯定的。虽然遗传算法的进发结果并不能保证得到理论意义上的最佳的决策树， 但是它提供了一种试探的过程。由丁适者牛存的特点，使得适应性较优的决策树能尽量保留，乂由于 它捉供了对决策树的调整和車新组合的机制,使得有更优适应性的决策树在进发过程中岀现。那么 如何应用遗传算法,如何基于决策树的结构和性质定义遗传算子呢？遗传算子主要有三种：复制(reproduction)、重组(crossover)、算子和变异(mutation)算 子。一般的算子都是对特征串进行操作的。针对决

40、策树的结构和特性，我们定义遗传算子:首先定义 适应函数(fitness function)。遗传算法是一个探索过程,它对树的评价是在树完全作成以后进行 的，可以将树的深度、结点数等因素都考虑在内。复制算子的定义与常用的复制算子的定义一致。重组算子的定义就要用到决策树结构特点。我 们有以下儿种重组方式：(1)用后代结点代替祖先结点，类似于书的剪枝操作。(2)同一棵树的两 个结点互相交换。(3)两个树z间结点交换,这里所说的结点交换就是交换以这些结点为根的子树。变异是产生全局最优的重要原因，尽管大多数的变异不能产生良好的效果，对于决策树，我们定 义的变异算子是改变树的结构或者改变树中结点内的信息。

41、针对内部结点和叶节点,属性值的分组 与否这些不同情况，变异的处理是不一样的。对于内部结点内，变异操作可能产牛下血的结果：(1) 改变结点上判断的属性。(2) 改变属性值的分组情况。(3) 改变该结点下的子树的分支情况，改变属性值与分支子树的对应。(4) 改变该结点的分支数。这样经过重组、变异算子运算得到的新的决策树需要迓行结构上的完整性和一致性处理。调整 变异结点及其子结点的树结构使z为一-棵完整的正确的决策树;去除从树根到叶节点路径上重复的 屈性判断等。决策树的构造分为以下儿步：(1) 第一-代群体的产生；(2) 产生下一代；(3) 产牛最优决策树。2. 3.决策树的评价标准1以上讨论了一些

42、决策树构造算法，并且对这些算法的优缺点进行了分析。下而，给出评价决策 树的一些标准。1. 过学习在由决策树学习的过程屮，我们必须在一组假设屮选择一个，使得它与训练实例集相匹配。我 们已经看到不可能在没有任何偏置(bias)的情况下学习。如果预先字段所要学习的函数属于整个 假设空间中一个很小子集，那么即使在训练实例不完整的情况下，我们也有可能从训练实例集丧钟 学习有用的假设，來使得它能够对未知的实例进行止确分类。即使如此，我们还是希望有一个大的训练实例集。因为训练实例集越大，关于分类的信息越多。 在这种情况下，即使我们随机地从与训练实例集相一致的假设集中选择一个，它也能对未知实例的 分类进行预测

43、。和反，即使在有偏置的情况下，如果训练实例集与整个假设空间相比过小，仍有过 多的与训练实例相一致的假设供我们选择，我们做出假设的泛化能力将很差。当有过多的假设与训 练实例集相一致的时候，则成为过学习。过学习是所冇机器学习都要考虑的问题。过学习将导致我们所做出的假设泛化能力过差。所以，也可以如下定义过学习。假设h对所有 的训练实例分类的错误率为errorliainh,对整个实例空间d分类的错误率为errord(h)。如果存在 另一个假设力使得：并且errord (/z) < errord (/?)一般将errortrain(/?)成为重替换(resubstitution)错误率，在木书屮将

44、其简记为r错误率。而在 此一般将在测试集屮的错误率errors 成为错误。cohen和jensen捉出了一个有用的理论來解禅为何会出现过学习的情况。他们捉出，当一个算 法过高估计增加树的复杂性对于分类的正确性的贡献，那么就会出现过学习现象。主要有三种原因 使得算法过高估计这些贡献：（1）检测模型的数目：算法检测模型数目与出现过学习的可能性是正相关的。（2）不同的正确性估计：小的训练实例集更不可能代表数据的内衣分布，更有可能产生过学 习的现彖。而大一些的训练实例集产生过学习问题的可能性更小。（3）选择最优树：通过极大化某个特定评价函数來选择最优决策树增加了过学习的可能性。 cohen和jense

45、n利用事后剪枝的方法验证了他们的理论。2. 有效性最为直接的估计一棵决策树在测试实例集合上的性能的方法是，将它在测试实例集合上进行实 际测试，这样就可以选中在测试集合中表现最好的-棵决第树。但是这种方法等价于在测试实例集 屮训练决策树，这在人多数情况下是不现实的。所以一般并不采川这种方法，而是采取川训练实例 集本身来估计训练算法的有效性。一种最简便的方法是川训练实例集的一部分（例如3/4的训练实 例）对决策树进行训练，而川另外一部分（例如1/4的训练实例）对决策树检测其有效性。但是， 这样做将会减小训练实例空间，而增人过学习的可能性，所以这种方法也不可取。3. 交叉有效性在此方法中，我们将训练

46、实例集t分为互不相交且大小相等的k个子集7；, t2.tk.对于任 意子集7；,用t-7；训练决策树，z后用7；对牛成的决策树进行测试，得到错误率耳，然后估计整 个算法的错误率:可以看出随着k的增加，所生成的树的数【也随之增加，算法的复朵度也会变人。4. 余一-有效性（leave-one-out validation）这种有效性的度量与交叉有效性类似，不同z处在于将每个的人小定为1。假设|t|=n,则 错误率为:显然，这种有效性测量算法的复杂度过高，但是它的准确程度也是故高的。5. 决策树的复杂程度决策树的复杂程度也是度量决策树学习效果的一个重要标准。対于给定的描述语言，如果决策 树是旳变量（

47、univariate）的，那么决策树的复杂程度主要山树的结点个数决定；如果是多变量(multivariare)的，则主要是由结点中属性的总个数决定。2. 4.决策树的进展与发展方向2. 4. 1 数据挖掘中决策树算法的主要进展传统的决策树算法主要是针对小数据集的，大都要求训练集常驻内存，这使得在处理数据挖掘 任务吋，传统决策树算法在可伸缩性、精度和效率方而受到了很大的限制。而在实际的数据挖掘应 用中我们面临的数据集往往是容量匕大的数据库或者数据仓库,在构造决策树时需要将庞大的数据 在主存和缓存中不停的导入导出，使得运算效率大大降低。针对以上问题，许多学者提出了处理大型 数据集的决策树算法。其中

48、主要在以下四个方面的应用：1、数据预处理；2、抽样方法；3、数据的重构；4、结合上述的遗传算法等其他算法。2. 4. 2.决策树技术面临的挑战及目前研究方向目前决策树技术的主要研究方向8有以下儿点：1决策树算法的并行性研究2寻找新的构造决策树的方法3寻找更好的简化决策树的方法4研究产生决策树的训练和检验数据的人小及特性与决策树特性之间的关系5不确定环境下决策树研究6将决策树用于多智能体控制并不多见7决策树时间复杂度与准确性z间的矛盾8决策树技术的软件实现3. 关于决策树算法的改进由以上讨论可知：1d3算法存在种种缺陷，女口：算法的计算时间是例子个数、特征个数、节点 个数z积的线性函数。另外大量

49、实验证明，id3算法在预测止确率和效果上是令人满意的。用互信息作为特征选择量,要求训练例子集中的正、反例比例应与实际领域里正、反例比例相同。但在一般情况下不能保证相 同，因而计算训练集的互信息就有偏差。互信息的计算依赖于特征值数h较多的特征，这样不太合 理。另外id3在建树时，每个节点仅含一个特征，特征间的相关性强调不够。下血针xjid3算法的第 二个不足之处，捉出-些决策树改进意见。3. 1 基于样本离散度的特征选择方法3. 1. 1.基本概念1 样本均值(1)表示第i类在第j维特征处的样本均值。其中，si表示第i类总的样本数，x/表示第i类第k个 样木在第j维特征处的取值。2.样本归一化样

50、本归一化就是将属性取值范围投影到一个特定的范围z内，以消除数值型属性因大小不一而 造成挖掘结果的偏差。对丁基丁距离计算的挖掘,数值归一化可以帮助消除因属性取值范围不同而 影响挖掘结果的公正性。我们按照下式刈离散的数据进行归一化处理，归一化后的结果将限制在0 ,1 范围之内。v. = (2)vmax -其中©为第j维某个数据的归一化值；怙沏为第j维该数据的实际值；为第j维数据的最 小值；叫唤为第j维数据的最大值。连续数据的归一化处理,首先应该对数据进行离散化,(有关连续数据离散化处理方法这里暂吋 不做介绍，请读者参考上述决策树算法的研究中的相关内容)，然后再述行数据的归一化。3. 样本

51、总类内离散度离散度的定义:一个在d维空间山n个点组成的聚类，其散布的程度口j以用离散度來衡量。离散度 的计算和我们规定的中心点有关。设方是d维空间中所选的中心点，从聚类的n个点中取出d个点，以 a为引点，作一个超平行四边形。对所有n中的d个点求出相应的u个超平行四边形的体积平方和 対n个点的均值，就是该聚类刈于中心点方的离散度。假使取聚类的均值点作为引点，则离散度为：s = |c|（3）式中c是聚类的协方差矩阵，即离散度矩阵s。总离散度st定义为：石=万工（x厂"）（疋-兀）2n /=i根据离散度的概念，推导出样本类内离散度定义:样木与样木均值的方差，若考虑先验概率，可 以定义如下：

52、/=1k=门表示第i类的先验概率，即p.s表示训练集的总的样本数。$4. 归一化后的样本分布设样木各维数据已经归一化到0 ,1 区间，贝将所有类在第j维的均值按从小到 大的升序排列，记为：“丿二 “ j 9 “2 丿，“v (6)理想情况下的特征分布应当为从= 1,并口任意两个相邻的均值间的距离为:叽一如172 1d“ j =工心£+1 -“)一1=1市于所提取的特征的均值并非完全理想分布，因此，我们定义一个函数来度量实际分布与理想 分布之间的距离。(8)7°越小，a+1/-a:/越接近于占，即各均值点在°，1区间越接近理想分布。5. 距离函数定义一个距离函数，希

53、望投影后，各类样本尽可能分得开些，即希望dui越小越好；同时希望 各类样本内部尽量密集，即希望类内离散度st越小越好.山式（5）和（8）定义距离函数。dj = s + 出口 j总之，希望dj越小越好,这样特征越理想.因此，在式（6）中选择一个较小的dj值所对应的 一个特征作为形成决策树的分类特征。3. 1.2.基于离散度的改进算法根据上述特征选择方法，在id3算法的基础上，捉出一种改进的决策树建树算法，算法步骤如下:1）将训练集窗口中的全部数据，选择一种归一化方法，归一化到0 ,1 区间，形成训练集d。2）对训练集d ,利用上述特征选择方法，利川式、（9）求出£，d厂。3）选择较小的

54、值所对应的那一个特征4作为分类特征，对数据集d进行分割，a,取儿个值就 得儿个子集。4）对不含同一类样木的子集,递归调用建树算法。5）若各子集中的样本为同一类样本，则对应分枝为叶子节点，作相应的类标记,返回调用处。3. 1.3.分析与比较此算法是根据离散数学的基础知识来讨论实现的，与id3的利用的信息论知识一样含概了大量 的数学公式，在第3.2节中即将讨论的基于概率论的算法也用是一样。利用数学公式计算并构建决 策树是众多决策树算法中的优先选择。淌泽学院计算机与信息工程学系的郭玉滨讲师6已经证明 基于离散度的改进算法有以下几点好处：（1）基于离散度的改进算法cpu的耗时远小于td3的cpu耗吋。

55、（2）分类的错误率:这种基于离散度的改迓算法分类的错谋率要低于td3算法分类的错误率。3. 1.4.小结基于离散度的改进算法的儿个问题：（1）建树步骤1中：如何将训练集窗口中的全部数据通过选择-种归一化方法，归一化到0,1 区间，形成训练集do在众多的归一化方法中找到一种合适的方式是很耗费的事，如果事先为计算 机选择好归一化方法可以减轻计算机的负担，但这却给设计者带來了负担。（2）建树步骤1中：要将归-化后的数据进行从小到大的升序排序，这乂要选样一种排序方 法。在排序算法中最好情况卜-就是快速排序算法，其时间复杂度为：0 （nlogn） o在不知情的情况 下设计者要对众多的排序算法进行研究以求最快。（3）建树步骤2中：对训练集d,要利用式、（8）、（9）等三个公式來求岀每一个训练实例 的距离函数。这乂是一项复杂的计算。（4）建树步骤3中：若要选择距离函数最小的训练实例就要进行排序。这个虽然可以用上面 问题（2）中的排序算法解决。但也盂要花费计算机的时间来做。（5）循坏递归调川也