机器学习算法总结-决策树

第三章决策树决策树(DecisionTree〕是在各种情况发生概率的根底上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价工程风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。在机器学习中，决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系。Entropy=系统的凌乱程度，使用算法ID3,C4.5和C5.0生成树算法使用熵。这一度量是基于信息学理论中熵的概念。2.1决策树模型与学习2.1.1决策树模型定义2.1〔决策树〕分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点〔node〕和有向边〔directededge〕组成。□——决策点，是对几种可能方案的选择，即最后选择的最正确方案。如果断策属于多级决策，那么决策树的中间可以有多个决策点，以决策树根部的决策点为最终决策方案为最终决策方案。○——状态节点，代表备选方案的经济效果〔期望值〕，通过各状态节点的经济效果的比照，按照一定的决策标准就可以选出最正确方案。由状态节点引出的分支称为概率枝，概率枝的数目表示可能出现的自然状态数目每个分枝上要注明该状态出现的概率。△——结果节点，将每个方案在各种自然状态下取得的损益值标注于结果节点的右端。2.1.2决策树学习决策树是以实例为根底的归纳学习算法。它从一组无次序、无规那么的元组中推理出决策树表示形式的分类规那么。它采用自顶向下的递归方式，在决策树的内部结点进行属性值的比拟，并根据不同的属性值从该结点向下分支，叶结点是要学习划分的类。从根到叶结点的一条路径就对应着一条合取规那么，整个决策树就对应着一组析取表达式规那么。1986年Quinlan提出了著名的ID3算法。在ID3算法的根底上，1993年Quinlan又提出了C4.5算法。为了适应处理大规模数据集的需要，后来又提出了假设干改良的算法，其中SLIQ(super-visedlearninginquest)和SPRINT(scalableparallelizableinductionofdecisiontrees)是比拟有代表性的两个算法。2.1.3决策树分析法决策树分析法是常用的风险分析决策方法。该方法是一种用树形图来描述各方案在未来收益的计算。比拟以及选择的方法，其决策是以期望值为标准的。它利用了概率论的原理，并且利用一种树形图作为分析工具。它利用了概率论的原理，并且利用一种树形图作为分析工具。其根本原理是用决策点代表决策问题，用方案分枝代表可供选择的方案，用概率分枝代表方案可能出现的各种结果，经过对各种方案在各种结果条件下损益值的计算比拟，为决策者提供决策依据。决策树分析法是常用的风险分析决策方法。该方法是一种用树形图来描述各方案在未来收益的计算。比拟以及选择的方法，其决策是以期望值为标准的。人们对未来可能会遇到好几种不同的情况。每种情况均有出现的可能，人们目前无法确知，但是可以根据以前的资料来推断各种自然状态出现的概率。在这样的条件下，人们计算的各种方案在未来的经济效果只能是考虑到各种自然状态出现的概率的期望值，与未来的实际收益不会完全相等。如果一个决策树只在树的根部有一决策点，那么称为单级决策；假设一个决策不仅在树的根部有决策点，而且在树的中间也有决策点，那么称为多级决策。科学的决策是现代管理者的一项重要职责。我们在企业管理实践中，常遇到的情景是：假设干个可行性方案制订出来了，分析一下企业内、外部环境，大局部条件是己知的，但还存在一定的不确定因素。每个方案的执行都可能出现几种结果，各种结果的出现有一定的概率，企业决策存在着一定的胜算，也存在着一定的风险。这时，决策的标准只能是期望值。即，各种状态下的加权平均值。针对上述问题，用决策树法来解决不失为一种好的选择。决策树法作为一种决策技术，已被广泛地应用于企业的投资决策之中，它是随机决策模型中最常见、最普及的一种规策模式和方法此方法，有效地控制了决策带来的风险。所谓决策树法，就是运用树状图表示各决策的期望值，通过计算，最终优选出效益最大、本钱最小的决策方法。决策树法属于风险型决策方法，不同于确定型决策方法，二者适用的条件也不同。应用决策树决策方法必须具备以下条件：1有决策者期望到达的明确目标；2存在决策者可以选择的两个以上的可行备选方案；3存在着决策者无法控制的两种以上的自然状态(如气候变化、市场行情、经济开展动向等)；4不同行动方案在不同自然状态下的收益值或损失值(简称损益值)可以计算出来；5决策者能估计出不同的自然状态发生概率。2.2特征选择2.2.1特征选择问题1、为什么要做特征选择在有限的样本数目下，用大量的特征来设计分类器计算开销太大而且分类性能差。2、特征选择确实切含义将高维空间的样本通过映射或者是变换的方式转换到低维空间，到达降维的目的，然后通过特征选取删选掉冗余和不相关的特征来进一步降维。3、特征选取的原那么获取尽可能小的特征子集，不显著降低分类精度、不影响类分布以及特征子集应具有稳定适应性强等特点4、特征选择需要考虑的问题a、确定选择算法，在允许的时间内以最小的代价找出最小的、最能描述类别的特征组合，b、确定评价标准，衡量特征组合是否是最优，得到特征获取操作的停止条件。5、特征获取方法a、按照特征子集的形成方式可以分为三种，穷举法〔exhaustion〕、启发法〔heuristic〕和随机法〔random〕。穷举法需要遍历特征空间中所有的特征组合，所以方法复杂度最大，实用性不强；启发法通过采用期望的人工机器调度规那么，重复迭代产生递增的特征子集，复杂度略低于穷举法，但是只能获取近似最优解；随即方法分为完全随机方法和概率随机方法两种，对参数设置的依赖性较强。b、按照特征评价标准来分，根据评价函数与分类器的关心，可以分为筛选器和封装器两种，筛选器的评价函数与分类器无关，封装器采用分类器的错误概率作为评价函数。筛选器的评价函数可以细分为距离测度、信息测度、相关性测度和一致性测度。距离测度用距离来衡量样本之间的相似度，信息测度用利用最小不确定性特征来分类。6、特征获取方法的选取原那么a、处理的数据类型b、处理的问题规模c、问题需要分类的数量d、对噪声的容忍能力e、无噪声环境下，产生稳定性好、最优特征子集的能力。特征选择的一般过程可用图1表示。首先从特征全集中产生出一个特征子集，然后用评价函数对该特征子集进行评价，评价的结果与停止准那么进行比拟，假设评价结果比停止准那么好就停止，否那么就继续产生下一组特征子集，继续进行特征选择。选出来的特征子集一般还要验证其有效性。综上所述，特征选择过程一般包括产生过程，评价函数，停止准那么，验证过程，这4个局部。(1)产生过程(GenerationProcedure)产生过程是搜索特征子集的过程，负责为评价函数提供特征子集。搜索特征子集的过程有多种，将在2.2小节展开介绍。(2)评价函数(EvaluationFunction)评价函数是评价一个特征子集好坏程度的一个准那么。(3)停止准那么(StoppingCriterion)停止准那么是与评价函数相关的，一般是一个阈值，当评价函数值到达这个阈值后就可停止搜索。(4)验证过程(ValidationProcedure)在验证数据集上验证选出来的特征子集的有效性。2.2.2信息增益信息增益〔Kullback–Leiblerdivergence〕又称informationdivergence，informationgain，relativeentropy或者KLIC。在概率论和信息论中，信息增益是非对称的，用以度量两种概率分布P和Q的差异。信息增益描述了当使用Q进行编码时，再使用P进行编码的差异。通常P代表样本或观察值的分布，也有可能是精确计算的理论分布。Q代表一种理论，模型，描述或者对P的近似。尽管信息增益通常被直观地作为是一种度量或距离，但事实上信息增益并不是。就比方信息增益不是对称的，从P到Q的信息增益通常不等于从Q到P的信息增益。信息增益是f增益〔f-divergences〕的一种特殊情况。在1951年由SolomonKullback和RichardLeibler首先提出作为两个分布的直接增益〔directeddivergence〕。它与微积分中的增益不同，但可以从Bregman增益〔Bregmandivergence〕推导得到。在信息增益中，重要性的衡量标准就是看特征能够为分类系统带来多少信息，带来的信息越多，该特征越重要。因此先回忆一下信息论中有关信息量〔就是“熵”〕的定义。说有这么一个变量X，它可能的取值有n多种，分别是，每一种取到的概率分别是，那么X的熵就定义为：意思就是一个变量可能的变化越多〔反而跟变量具体的取值没有任何关系，只和值的种类多少以及发生概率有关〕，它携带的信息量就越大〔因此我一直觉得我们的政策法规信息量非常大，因为它变化很多，根本朝令夕改，笑〕。对分类系统来说，类别C是变量，它可能的取值是，而每一个类别出现的概率是，因此n就是类别的总数。此时分类系统的熵就可以表示为：信息增益是针对一个一个的特征而言的，就是看一个特征t，系统有它和没它的时候信息量各是多少，两者的差值就是这个特征给系统带来的信息量，即增益。系统含有特征t的时候信息量很好计算，就是刚刚的式子，它表示的是包含所有特征时系统的信息量。问题是当系统不包含t时，信息量如何计算？我们换个角度想问题，把系统要做的事情想象成这样：说教室里有很多座位，学生们每次上课进来的时候可以随便坐，因而变化是很大的〔无数种可能的座次情况〕；但是现在有一个座位，看黑板很清楚，听老师讲也很清楚，于是校长的小舅子的姐姐的女儿托关系〔真辗转啊〕，把这个座位定下来了，每次只能给她坐，别人不行，此时情况怎样？对于座次的可能情况来说，我们很容易看出以下两种情况是等价的：〔1〕教室里没有这个座位；〔2〕教室里虽然有这个座位，但其他人不能坐〔因为反正它也不能参与到变化中来，它是不变的〕。对应到我们的系统中，就是下面的等价：〔1〕系统不包含特征t；〔2〕系统虽然包含特征t，但是t已经固定了，不能变化。我们计算分类系统不包含特征t的时候，就使用情况〔2〕来代替，就是计算当一个特征t不能变化时，系统的信息量是多少。这个信息量其实也有专门的名称，就叫做“条件熵”，条件嘛，自然就是指“t已经固定“这个条件。但是问题接踵而至，例如一个特征X，它可能的取值有n多种，当计算条件熵而需要把它固定的时候，要把它固定在哪一个值上呢？答案是每一种可能都要固定一下，计算n个值，然后取均值才是条件熵。而取均值也不是简单的加一加然后除以n，而是要用每个值出现的概率来算平均〔简单理解，就是一个值出现的可能性比拟大，固定在它上面时算出来的信息量占的比重就要多一些〕。因此有这样两个条件熵的表达式：这是指特征X被固定为值xi时的条件熵，这是指特征X被固定时的条件熵，注意与上式在意义上的区别。从刚刚计算均值的讨论可以看出来，第二个式子与第一个式子的关系就是：2.2.3熵在信息论中，要对符号进行编码，一个符号的熵就是要表示这个符号所需要的最少二进制数位数；这是一个极限；这也是信息压缩的根底；条件熵，当两个符号之间存在某种关系，或者两个随机变量不互相独立的时候，对于A，B两个随机事件，非独立，知道A的情况，B的不确定性减少。举例来说，假设S是一个关于布尔概念的有14个样例的集合，它包括9个正例和5个反例〔我们采用记号[9+，5-]来概括这样的数据样例〕，那么S相对于这个布尔样例的熵为：注意，如果S的所有成员属于同一类，，例如，如果所有的成员是正的，那么p-就是0，于是；另外S的正反样例数量相等，；S的正反样例数量不等，熵介于0，1之间，如下列图所示：//根据具体属性和值来计算熵doubleComputeEntropy(vector<vector<string>>remain_state,stringattribute,stringvalue,boolifparent){vector<int>count(2,0);unsignedinti,j;booldone_flag=false;//哨兵值for(j=1;j<MAXLEN;j++){if(done_flag)break;if(!attribute_row[j]pare(attribute)){for(i=1;i<remain_state.size();i++){if((!ifparent&&!remain_state[i][j]pare(value))||ifparent){//ifparen记录是否算父节点if(!remain_state[i][MAXLEN-1]pare(yes)){count[0]++;}elsecount[1]++;}}done_flag=true;}}if(count[0]==0||count[1]==0)return0;//全部是正实例或者负实例//具体计算熵根据[+count[0],-count[1]],log2为底通过换底公式换成自然数底数doublesum=count[0]+count[1];doubleentropy=-count[0]/sum*log(count[0]/sum)/log(2.0)-count[1]/sum*log(count[1]/sum)/log(2.0);returnentropy;}举个例子：A事件是：季节{春，夏，秋，冬}，B事件是：天气{下雨，下雪，晴天，多云}；那就可以画出一个二维表格，最直观的是夏天&下雪的概率<冬天&下雪的概率；当我知道天气是下雪的时候，我就有很大的概率认为季节是冬天；这说明：我知道了B事件的情况，对A的不确定性减少了；如果A，B是独立的，比方，A事件是季节{春，夏，秋，冬}，B事件是交通的情况{堵，不堵}，我知道B的情况，对A的不确定性并没影响。上面说的是概念性的理解，如果用数学公式对应起来理解，为什么会出现这样的情况？B的情况，A的概率有没有变化？当A，B独立，说明没有变化，当AB不独立的时候，即两者存在某种相关性质，换句话说就是B确定的前提下，A的概率分布与在总体上看不一样。信息论中有熵，用来表示时间的不确定性，这个跟这个事件的可能值数目，还有取每个值的概率，比方有A事件{1,2,3,4}每个取值等概，那么熵为2；如果A{1,2}每个取值等概率，熵为1；当取值数目一样的时候A{1,2,3,4}，，，那么这个熵小于2；这是为什么？因为在数据压缩方面，对于小概率事件就要用长的编码，大概率事件用短编码，这样最后平均每个事件的编码就比拟小！而对于等概率事件，这种策略就没法使用，就没法实现数据的压缩；熵说的就是这种下界。反过来，当我们说一个事件熵很大，就意味着1这个事件的取值范围很多2〔或者〕这个事件中每个取值的概率比拟均匀以上两者都代表着这个事件的不确定性很大，所以我们又说熵是一种不确定性的度量那么什么是条件熵呢，为什么小于等于呢？上面说了，知道了B，1：首先A的取值范围会缩小，为什么？拿上面一个例子来说，我知道了天气是下雪，那么几乎可以说A的取值只能从{春天，冬天}里选择；2：A中每个取值的概率分布会发生变化与的概率分布不同；数学证明；即B的结果，A的不确定性减少；要表述A这个事件的编码数更少；在决策树中，我们关心的是H〔结果|属性〕的关系，即某属性，结果的不确定性还有多少；我们需要知道，哪个属性能使得结果的不确定性减少最多。2.3决策树的生成2.3.1ID3算法如果学习的任务是对一个大的例子集作分类概念的归纳定义，而这些例子又都是用一些无结构的属性值对来表示，那么可以采用例如学习方法的一个变种──决策树学习，其代表性的算法是昆兰〔，1986〕提出的ID3。ID3算法是由Quinlan首先提出的。该算法是以信息论为根底，以信息熵和信息增益度为衡量标准，从而实现对数据的归纳分类。以下是一些信息论的根本概念：定义2.2：假设存在n个相同概率的消息，那么每个消息的概率p是1/n，一个消息传递的信息量为定义2.3：假设有n个消息，其给定概率分布为，那么由该分布传递的信息量称为P的熵，记为。定义2.4：假设一个记录集合T根据类别属性的值被分成互相独立的类C1C2..Ck，那么识别T的一个元素所属哪个类所需要的信息量为Info(T)=I(p)，其中P为C1C2…Ck的概率分布，即。定义2.5：假设我们先根据非类别属性X的值将T分成集合T1,T2…Tn，那么确定T中一个元素类的信息量可通过确定Ti的加权平均值来得到，即Info(Ti)的加权平均值为：定义2.6：信息增益度是两个信息量之间的差值，其中一个信息量是需确定T的一个元素的信息量，另一个信息量是在已得到的属性X的值后需确定的T一个元素的信息量，信息增益度公式为：ID3算法计算每个属性的信息增益，并选取具有最高增益的属性作为给定集合的测试属性。对被选取的测试属性创立一个节点，并以该节点的属性标记，对该属性的每个值创立一个分支据此划分样本。ID3的输入是描述各种类别实例的列表。例子由预先定义的属性值对来表示。归纳推理产生的结果不是以往讨论的那种合取表达式，而是一棵决策树〔也称判别树，并可转而表示为决策规那么的一个集合〕，用它可正确地区分所有给定例子的类属。树中的每一非叶节点对应一个需测试的属性，每个分叉就是该属性可能的取值；树的叶节点那么指示一个例子事物的类别。ID3的显著优点是归纳学习花费的时间和所给任务的困难度〔取决于例子个数，用来描述对象的属性数，所学习概念的复杂度即决策树的节点数等〕仅成线性增长关系。当然，ID3只能处理用属性-值对表示的例子。在ID3中,每一个例子用相同的一组属性来表示，每一个属性又有自身的属性值集，如"颜色"属性可取值是{红、绿、兰}等。构造决策树的目的是为了对事物作出正确的分类。决策树形式的分类规那么适用于任何的对象集Ｃ。如Ｃ是空的，那么它无需分类，对应的决策树也为空；如Ｃ中的对象是同一类的，那么决策树就一个叶节点，即该类名；如果Ｃ集中的对象属于二个不同的类别，那未我们可以选取一个对象的属性，随后按其可能值把Ｃ划分成一些不相交的子集C1，C2，…，Cn，其中Ci是含有所选属性的第ｉ个值的那些对象集。对每一个这样的子集又可以用同样的策略处理，最后的结果是一棵树。ID3〔Examples,Target-attrlbute,Attrlbutes〕创立树的root节点如果Examples都为正，返回label=+的单节点输root如果Examples都为反，返回label=-的单节点输root如果Attrlbutes为空，那么返回单节点输root，label=Examples中最普遍的Target-attributes值否那么开始AAttributes中分类examples能力最好的属性Root的决策属性A对于A的每个可能值vi在root下加一个新的分支对应测试A=vi令Examples为Examples中满足A属性值为vi的子集如果Examples为空在这个新分支下加一个叶子结点，节点的label=Examples中最普遍的Target-attributes值否那么在新分支下加一个子树ID3〔ExamplesTarget-attribute，Attributes-{A}〕结束返回root下面给出一个关于人分类的例子〔对象〕集，并预先定义了指定的一组属性及其可取值：高度{高，矮}，发色{黑色,红色，金色}和眼睛{兰色，棕色}。这里，将人分为两类，分别以＋、－来指示。高度发色眼睛类别矮黑色兰色－高黑色兰色－矮金色兰色＋高金色棕色－高黑色棕色－矮金色棕色－高金色兰色＋高红色兰色＋如我们首先选取"发色"为树的根节点，即可获得图6.11所示的决策树。相应于"黑色"，"红色"和"金色"三值都有一个对象子集。随后我们再测试"金色"这一分支，又按属性"眼睛"把其所含的对象集划分成兰色和棕色二类。至此，所有叶结点相应的对象子集只含同一类的对象，我们就可以用相应的类别名〔本例中的+和-〕来取代各子集，得到一决策树。一个对象所属类的判别从决策树的根开始，首先依据根节点指示的属性〔发色〕，选择与该对象属性值相应的分支；然后，以同样的方式进行下去,一直到达叶节点。有时判别一个对象的类别，由于从根到叶节点的路径较短，只要测试少量的属性。如上例中，假设"发色"的值是"黑色"或"红色"，那么对象就可以直接归属相应的类别，而不必再去判定其它属性的取值；假设为"金色"，那么再测试一次"眼睛"的值〔而不必考虑"高度"〕就可以进行判别。假设不存在这样的二个对象:它们在每个属性上都具有相同的值，却属于不同的类别，那么这种生成决策树的过程是可行的。产生这种归纳学习方法的关键在于如何选择一系列有用的属性来测试一个对象集，以使生成的决策树是最小的。ID3采用了香农〔Shannon〕信息论中的方法以使分类时期望〔平均〕的测试次数最小。一个决策树可看成一个信息源，即给定一个对象，可从决策树产生一个该对象所属类别的消息(比方类别"+"或"-")。决策树的复杂程度与借助这个消息所传递的信息量密切相关。假设决策树传递的不同类别消息的概率用P+(对应于"+"类)和P-表示(对应于"-"类)，那么这个消息的期望信息量为:对给定的物体集C，我们可以把这概率近似地表示为相对频率,此时P+和P-分别等于C中类别为"+"和"-"的对象所占的比例。从C集对应的决策树中得到消息的期望信息量记为M(C)，并定义M({})=0。对于上述例子，C集有八个例子，三个为"+"，五为"-"，那么这是一个局部决策树，A为构造决策树时下一个可能选取的属性，Ai为属性A的值且是互斥的。属性A将集合C划分为假设干个子集合{C1，C2，...，Cn}。设M(Ci)是值为Ai的子集Ci所对应决策树的期望信息量，那么确定以属性A作为树根的决策树的期望信息量B(C,A)可通过权值平均而得到:B(C,A)＝∑(A值为Ai的概率)*M(Ci)同样我们把Ai的概率用相比照例来代替，即在所有对象中具有Ai值所占的相比照例。我们希望待选的测试属性能使决策树获得最大的信息增益即M(C)-B(C,A)为最大值。因为M(C)为判别一个对象的类属所要求的总的期望信息量，B(C,A)为按属性A构造局部决策树后还需要的期望信息量。二者的差越大，说明测试这个属性所能传递的信息量越大,那么判别的速度也就越快。例如，我们选取的属性为"高度"，对高度值为"高"的分支的所需期望信息量为：同样对值为"矮"的分支为:那么以属性"高度"作划分后进一步判别所需的期望信息量为：B(C,"高度")=5/8*0.971+3/8*0.918=0.951那么测试这属性传递的信息为:M(C)-B(C,"高度")=0.954-0.951=0.003bits。如果我们不是选择"高度"而选用属性"头发",那么有:B(C,"头发")=3/8*0+1/8*0+4/8*1=0.5bits那么测试属性"头发"获取的信息为M(C)-B(C,"头发")=0.945-0.5=0.45bits。同样对属性"眼睛"测试，获得信息为0.347bits。根据最大信息量原理,ID3就选取"头发"为决策树的根节点属性。ID3通过不断的循环处理，逐步求精决策树，直到形成一棵完整的决策树，即树的叶节点所对应的对象〔例子〕均属于同一类。2.3.2C4.5的生成算法C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改良：1)用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的缺乏；2)在树构造过程中进行剪枝；3)能够完成对连续属性的离散化处理；4)能够对不完整数据进行处理。C4.5算法与其它分类算法如统计方法、神经网络等比拟起来有如下优点：产生的分类规那么易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行屡次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。C4.5算法是以信息论为根底，以信息熵和信息增益度为衡量标准，从而实现对数据的归纳分类。1用信息增益率来选择属性克服了用信息增益来选择属性时偏向选择值多的属性的缺乏。信息增益率定义为：其中Gain(S,A)与ID3算法中的信息增益相同，而分裂信息SplitInfo(S,A)代表了按照属性A分裂样本集S的广度和均匀性。其中，S1到Sc是c个不同值的属性A分割S而形成的c个样本子集。如按照属性A把S集〔含30个用例〕分成了10个用例和20个用例两个集合那么2可以处理连续数值型属性C4.5既可以处理离散型描述属性，也可以处理连续性描述属性。在选择某节点上的分枝属性时，对于离散型描述属性，C4.5的处理方法与ID3相同，按照该属性本身的取值个数进行计算；对于某个连续性描述属性Ac，假设在某个结点上的数据集的样本数量为total，C4.5将作以下处理。(1)将该结点上的所有数据样本按照连续型描述属性的具体数值，由小到大进行排序，得到属性值的取值序列{A1c，A2c，……Atotalc}。(2)在取值序列中生成total-1个分割点。第i〔0<i<total〕个分割点的取值设置为Vi=〔Aic+A〔i+1〕c〕/2,它可以将该节点上的数据集划分为两个子集。(3)从total-1个分割点中选择最正确分割点。对于每一个分割点划分数据集的方式，C4.5计算它的信息增益比，并且从中选择信息增益比最大的分割点来划分数据集。3采用了一种后剪枝方法防止树的高度无节制的增长，防止过度拟合数据，该方法使用训练样本集本身来估计剪枝前后的误差，从而决定是否真正剪枝。方法中使用的公式如下：其中N是实例的数量，f=E/N为观察到的误差率〔其中E为N个实例中分类错误的个数〕，q为真实的误差率，c为置信度〔C4.5算法的一个输入参数，默认值为0.25〕，z为对应于置信度c的标准差，其值可根据c的设定值通过查正态分布表得到。通过该公式即可计算出真实误差率q的一个置信度上限，用此上限为该节点误差率e做一个悲观的估计：通过判断剪枝前后e的大小，从而决定是否需要剪枝。4对于缺失值的处理在某些情况下，可供使用的数据可能缺少某些属性的值。假设〈x，c(x)〉是样本集S中的一个训练实例，但是其属性A的值A(x)未知。处理缺少属性值的一种策略是赋给它结点n所对应的训练实例中该属性的最常见值；另外一种更复杂的策略是为A的每个可能值赋予一个概率。例如，给定一个布尔属性A，如果结点n包含6个A=1和4个A=0的实例，那么A(x)=1的概率是0.6，而A(x)=0的概率是0.4。于是，实例x的60%被分配到A=1的分支，40%被分配到另一个分支。这些片断样例〔fractionalexamples〕的目的是计算信息增益，另外，如果有第二个缺少值的属性必须被测试，这些样例可以在后继的树分支中被进一步细分。C4.5就是使用这种方法处理缺少的属性值。5C4.5算法的优缺点优点：产生的分类规那么易于理解，准确率较高。缺点：在构造树的过程中，需要对数据集进行屡次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。2.4决策树的剪枝通常在实际应用中，直接生成的完全决策树不能立即用于对未知样本进行分类。由于完全决策树对训练样本的特征描述得“过于精确”，无法实现对新样本的合理分析，所以此时它不是一棵分析新数掘的最正确决策树。一棵完全决策树能准确地反映训练集中数据特征，但因失去了一般代表性而无法用于对新数据的分类或预测，这种现象称为“过适应”。解决过适应问题的主要方法是对决策树进行剪枝。剪枝(Pruning)方法的主要目的是去掉那些噪声或异常数据，使决策树具有更泛化能力。剪枝常采用统计度量，剪掉最不可靠的分枝，从而带来较快的分类，提高树独立于测试数据进行证确分类的能力。剪枝按其实施的时间分为两种方法：事前修剪法和事后修剪法。〔1〕事前修剪法该方法通过提前停止树的构造而对树“剪枝”，即通过在当前节点上判断是否需要继续划分该节点所含训练样本集来实现。一旦停止，节点不再继续分裂，当前节点就成为一个叶节点。该叶节点中可能包含多个不同类别的训练样本，由于该修剪是在分枝之前做出的，所以称之为事前修剪。事前修剪法的优点是在树生成的同时进行了剪枝，因而效率高，但是它可能剪去了某些有用但还没生成的节点。常用的方法是设定决策树的最大高度(层数)来限制树的生长。还有一种方法是设定每个节点必须包含的最少记录数，当节点中记录的个数小于这个数值时就停止分割。然而，选择一个适当的阈值是比拟困难的，较高的阈值可能导致过分简化的树，而较低的阈值可能会导致多余树枝无法修剪。〔2〕事后修剪法该方法是由完全生长的树剪去分枝。通过删除节点的分枝，剪掉树节点。它在允许决策树得到最充分生长的根底上，再根据一定的规那么，剪去决策树中的那些不具有一般代表性的叶节点或分枝。修剪后，被修剪的分枝节点就成为一个叶节点，并将其标记为它所包含样本中类别个数最多的类别。事后修剪是一边修剪一边检验的过程，一般规那么是：当树建好之后，对每个内部节点，首先计算该节点上的子树被剪枝可能出现的错误率，然后，使用每个分枝的错误率，结合沿每个分枝观察的权重评估，计算不对该节点剪枝的期望错误率。如果剪掉该节点能够降低错误率，那么该节点的所有子节点就被剪掉，该节点成为叶节点。产生一组逐渐被剪枝的树之后，使用一个独立的测试集评估每棵树的准确率，就能得到具有最小期望错误率的决策树。当然也可以结合使用事前修剪和