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

第三章决策树决策树 (Decision Tree是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险， 判断其可行性的决策分析方法， 是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。在机器学习中，决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系。Entropy = 系统的凌乱程度，使用算法 ID3, C4.5和 C5.0 生成树算法使用熵。这一度量是基于信息学理论中熵的概念。2.1 决策树模型与学习2.1.1 决策树模型定义 2.1决策树分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点 node和有向边 directed edge组成。决策点， 是对几种可能方案的选择， 即最后选择的最正确方案。 如果断策属于多级决策， 则决策树的中间可以有多个决策点，以决策树根部的决策点为最终决策方案为最终决策方案。状态节点，代表备选方案的经济效果期望值，通过各状态节点的经济效果的比照， 按照一定的决策标准就可以选出最正确方案。由状态节点引出的分支称为概率枝， 概率枝的数目表示可能出现的自然状态数目每个分枝上要注明该状态出现的概率。结果节点，将每个方案在各种自然状态下取得的损益值标注于结果节点的右端。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 20 页2.1.2 决策树学习决策树是以实例为基础的归纳学习算法。它从一组无次序、 无规则的元组中推理出决策树表示形式的分类规则。它采用自顶向下的递归方式， 在决策树的内部结点进行属性值的比较，并根据不同的属性值从该结点向下分支， 叶结点是要学习划分的类。 从根到叶结点的一条路径就对应着一条合取规则，整个决策树就对应着一组析取表达式规则。1986 年Quinlan 提出了著名的 ID3 算法。在 ID3 算法的基础上， 1993年 Quinlan 又提出了 C4.5 算法。为了适应处理大规模数据集的需要，后来又提出了假设干改良的算 法 ， 其 中SLIQ(super-vised learning in quest) 和 SPRINT (scalable parallelizableinduction of decision trees)是比较有代表性的两个算法。2.1.3 决策树分析法决策树分析法是常用的风险分析决策方法。该方法是一种用树形图来描述各方案在未来收益的计算。 比较以及选择的方法， 其决策是以期望值为标准的。它利用了概率论的原理，并且利用一种树形图作为分析工具。它利用了概率论的原理， 并且利用一种树形图作为分析工具。其基本原理是用决策点代表决策问题， 用方案分枝代表可供选择的方案，用概率分枝代表方案可能出现的各种结果， 经过对各种方案在各种结果条件下损益值的计算比较，为决策者提供决策依据。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 20 页决策树分析法是常用的风险分析决策方法。该方法是一种用树形图来描述各方案在未来收益的计算。 比较以及选择的方法， 其决策是以期望值为标准的。人们对未来可能会遇到好几种不同的情况。每种情况均有出现的可能， 人们目前无法确知，但是可以根据以前的资料来推断各种自然状态出现的概率。在这样的条件下，人们计算的各种方案在未来的经济效果只能是考虑到各种自然状态出现的概率的期望值，与未来的实际收益不会完全相等。如果一个决策树只在树的根部有一决策点，则称为单级决策； 假设一个决策不仅在树的根部有决策点，而且在树的中间也有决策点，则称为多级决策。科学的决策是现代管理者的一项重要职责。我们在企业管理实践中， 常遇到的情景是：假设干个可行性方案制订出来了，分析一下企业内、外部环境，大部分条件是己知的， 但还存在一定的不确定因素。 每个方案的执行都可能出现几种结果，各种结果的出现有一定的概率，企业决策存在着一定的胜算，也存在着一定的风险。这时，决策的标准只能是期望值。即，各种状态下的加权平均值。针对上述问题，用决策树法来解决不失为一种好的选择。决策树法作为一种决策技术， 已被广泛地应用于企业的投资决策之中，它是随机决策模型中最常见、 最普及的一种规策模式和方法此方法，有效地控制了决策带来的风险。所谓决策树法，就是运用树状图表示各决策的期望值， 通过计算，最终优选出效益最大、 成本最小的决策方法。 决策树法属于风险型决策方法，不同于确定型决策方法， 二者适用的条件也不同。 应用决策树决策方法必须具备以下条件：1 有决策者期望到达的明确目标；2 存在决策者可以选择的两个以上的可行备选方案；3 存在着决策者无法控制的两种以上的自然状态( 如气候变化、市场行情、经济发展动向等 ) ；4 不同行动方案在不同自然状态下的收益值或损失值(简称损益值 )可以计算出来；5 决策者能估计出不同的自然状态发生概率。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 20 页2.2 特征选择2.2.1 特征选择问题1、为什么要做特征选择在有限的样本数目下， 用大量的特征来设计分类器计算开销太大而且分类性能差。2、特征选择确实切含义将高维空间的样本通过映射或者是变换的方式转换到低维空间，到达降维的目的，然后通过特征选取删选掉冗余和不相关的特征来进一步降维。3、特征选取的原则获取尽可能小的特征子集， 不显著降低分类精度、 不影响类分布以及特征子集应具有稳定适应性强等特点4、特征选择需要考虑的问题a、确定选择算法，在允许的时间内以最小的代价找出最小的、最能描述类别的特征组合， b、确定评价标准，衡量特征组合是否是最优，得到特征获取操作的停止条件。5、特征获取方法a、按照特征子集的形成方式可以分为三种，穷举法exhaustion 、启发法heuristic 和随机法random 。 穷举法需要遍历特征空间中所有的特征组合，所以方法复杂度最大，实用性不强；启发法通过采用期望的人工机器调度规则，重复迭代产生递增的特征子集， 复杂度略低于穷举法， 但是只能获取近似最优解；随即方法分为完全随机方法和概率随机方法两种，对参数设置的依赖性较强。b、按照特征评价标准来分，根据评价函数与分类器的关心，可以分为筛选器和封装器两种， 筛选器的评价函数与分类器无关，封装器采用分类器的错误概率作为评价函数。 筛选器的评价函数可以细分为距离测度、信息测度、 相关性测度和一致性测度。 距离测度用距离来衡量样本之间的相似度，信息测度用利用最小不确定性特征来分类。6、特征获取方法的选取原则a、处理的数据类型精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 20 页b、处理的问题规模c、问题需要分类的数量d、对噪声的容忍能力e、无噪声环境下，产生稳定性好、最优特征子集的能力。特征选择的一般过程可用图1 表示。 首先从特征全集中产生出一个特征子集，然后用评价函数对该特征子集进行评价，评价的结果与停止准则进行比较，假设评价结果比停止准则好就停止， 否则就继续产生下一组特征子集，继续进行特征选择。选出来的特征子集一般还要验证其有效性。综上所述，特征选择过程一般包括产生过程，评价函数，停止准则，验证过程，这 4 个部分。 (1) 产生过程 ( Generation Procedure )产生过程是搜索特征子集的过程， 负责为评价函数提供特征子集。搜索特征子集的过程有多种，将在 2.2 小节展开介绍。 (2) 评价函数 ( Evaluation Function ) 评价函数是评价一个特征子集好坏程度的一个准则。(3) 停止准则 ( Stopping Criterion ) 停止准则是与评价函数相关的， 一般是一个阈值， 当评价函数值到达这个阈值后就可停止搜索。 (4) 验证过程 ( Validation Procedure ) 在验证数据集上验证选出来的特征子集的有效性。2.2.2 信息增益信息增益Kullback Leibler divergence 又称 information divergence ，information gain，relative entropy 或者 KLIC。在概率论和信息论中，信息增益是非对称的，用以度量两种概率分布P和 Q的差异。信息增益描述了当使用Q进行编码时， 再使用 P进行编码的差异。 通常P代表样本或观察值的分布， 也有可能是精确计算的理论分布。 Q代表一种理论，模型，描述或者对P的近似。尽管信息增益通常被直观地作为是一种度量或距离，但事实上信息增益并不是。就比方信息增益不是对称的， 从 P到 Q的信息增益通常不等于从Q到 P的信息增益。信息增益是f 增益 f-divergences的一种特殊情况。在1951 年由Solomon Kullback 和 Richard Leibler首先提出作为两个分布的直接增益精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 20 页directed divergence 。它与微积分中的增益不同，但可以从Bregman 增益Bregman divergence 推导得到。在信息增益中，重要性的衡量标准就是看特征能够为分类系统带来多少信息，带来的信息越多，该特征越重要。因此先回忆一下信息论中有关信息量就是“熵”的定义。说有这么一个变量 X，它可能的取值有n 多种，分别是1,2,XXXn，每一种取到的概率分别是1, 2,P PPn，那么 X的熵就定义为：21()log(21)niiiHXPP意思就是一个变量可能的变化越多反而跟变量具体的取值没有任何关系，只和值的种类多少以及发生概率有关 ，它携带的信息量就越大因此我一直觉得我们的政策法规信息量非常大，因为它变化很多，基本朝令夕改，笑。对分类系统来说，类别C是变量，它可能的取值是1, 2,C CCn，而每一个类别出现的概率是( 1), (2),()P CP CP Cn ，因此 n 就是类别的总数。此时分类系统的熵就可以表示为：21()()log()(22)niiiH CP CP C?信息增益是针对一个一个的特征而言的，就是看一个特征t ，系统有它和没它的时候信息量各是多少， 两者的差值就是这个特征给系统带来的信息量，即增益。系统含有特征 t 的时候信息量很好计算， 就是刚刚的式子， 它表示的是包含所有特征时系统的信息量。问题是当系统不包含t 时，信息量如何计算？我们换个角度想问题，把系统要做的事情想象成这样： 说教室里有很多座位， 学生们每次上课进来的时候可以随便坐，因而变化是很大的无数种可能的座次情况；但是现在有一个座位，看黑板很清楚， 听老师讲也很清楚， 于是校长的小舅子的姐姐的女儿托关系真辗转啊 ，把这个座位定下来了，每次只能给她坐，别人不行，此时情况怎样？对于座次的可能情况来说， 我们很容易看出以下两种情况是等价的： 1教室里没有这个座位；2教室里虽然有这个座位，但其他人不能坐因为反正它也不能参与到变化中来，它是不变的 。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 20 页对应到我们的系统中，就是下面的等价： 1系统不包含特征 t ； 2系统虽然包含特征 t ，但是 t 已经固定了，不能变化。我们计算分类系统不包含特征t 的时候，就使用情况2来代替，就是计算当一个特征 t 不能变化时，系统的信息量是多少。 这个信息量其实也有专门的名称，就叫做“条件熵” ，条件嘛，自然就是指“t 已经固定“这个条件。但是问题接踵而至，例如一个特征 X， 它可能的取值有 n 多种 ( 1, 2,)x xxn ，当计算条件熵而需要把它固定的时候，要把它固定在哪一个值上呢？答案是每一种可能都要固定一下， 计算 n 个值，然后取均值才是条件熵。 而取均值也不是简单的加一加然后除以n，而是要用每个值出现的概率来算平均简单理解，就是一个值出现的可能性比较大， 固定在它上面时算出来的信息量占的比重就要多一些 。因此有这样两个条件熵的表达式：(|)(23)iH CXx这是指特征 X被固定为值 xi 时的条件熵，(|)(24)H C X这是指特征 X被固定时的条件熵， 注意与上式在意义上的区别。 从刚刚计算均值的讨论可以看出来，第二个式子与第一个式子的关系就是：11221(|)(|)(|).(|)(|)(25)nnniiiH CXPH CXxP H CXxP H CXxPH CXx2.2.3 熵在信息论中， 要对符号进行编码， 一个符号的熵就是要表示这个符号所需要的最少二进制数位数；这是一个极限；这也是信息压缩的基础；条件熵，当两个符号之间存在某种关系，或者两个随机变量不互相独立的时候，对于A，B两个随机事件，非独立，知道A的情况， B的不确定性减少。举例来说，假设 S是一个关于布尔概念的有14 个样例的集合，它包括9 个正例和 5 个反例我们采用记号 9+，5- 来概括这样的数据样例 ，那么 S相对于这个布尔样例的熵为：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 20 页22( 9 ,5)9 /14 log (9 /14)(5 /14)log (5 /14)0.940Entropy注意，如果S的所有成员属于同一类，( )0Entropy S， 例如， 如果所有的成员是正的(1)p，那么 p- 就是 0，于是22( )1*log(1)(0)log(0)0Entropy S； 另外 S的正反样例数量相等，( )1Entropy S；S的正反样例数量不等，熵介于0，1 之间，如下列图所示：/ 根据具体属性和值来计算熵double ComputeEntropy(vector vector remain_state, string attribute, string value,bool ifparent) vector count (2,0); unsigned int i,j; bool done_flag = false;/ 哨兵值for(j = 1; j MAXLEN; j+) if(done_flag) break; if(!attribute_rowj pare(attribute)for(i=1;i();i+)if(!ifparent&!remain_stateij pare(value) | ifparent)/ifparen记录是否算父节点if(!remain_stateiMAXLEN - 1 pare(yes) count0+; else count1+; done_flag = true; if(count0 = 0 | count1 = 0 ) return 0;/全部是正实例或者负实例/具体计算熵根据 +count0, -count1,log2 为底通过换底公式换成自然数底数double sum = count0 + count1; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 20 页doubleentropy=-count0/sum*log(count0/sum)/log(2.0) -count1/sum*log(count1/sum)/log(2.0); return entropy; 举个例子：A事件是：季节 春，夏，秋，冬，B事件是：天气 下雨，下雪，晴天，多云；那就可以画出一个二维表格，最直观的是夏天&下雪的概率 冬天&下雪的概率；当我知道天气是下雪的时候， 我就有很大的概率认为季节是冬天；这说明：我知道了 B事件的情况，对 A的不确定性减少了； 如果 A，B是独立的，比方， A事件是季节 春，夏，秋，冬 ，B事件是交通的情况 堵，不堵 ，我知道 B的情况，对 A的不确定性并没影响。 上面说的是概念性的理解， 如果用数学公式对应起来理解，为什么会出现这样的情况？(|)P A B 已知 B的情况，A的概率有没有变化？当A， B独立，(|)( )P A BP A说明 没有变化，当 AB不独立的时候， 即两者存在某种相关性质， 换句话说就是B确定的前提下， A的概率分布与在总体上看不一样。信息论中有熵，用来表示时间的不确定性，这个跟这个事件的可能值数目，还有取每个值的概率，比方有A 事件1,2,3,4每个取值等概，那么熵为2；如果 A1,2 每个取值等概率，熵为1；当取值数目一样的时候A1,2,3,4，(1)(2)(3)1/ 6P AP AP A，(4)1/ 2P A，那么这个熵小于 2；这是为什么？因为在数据压缩方面， 对于小概率事件就要用长的编码，大概率事件用短编码，这样最后平均每个事件的编码就比较小！而对于等概率事件， 这种策略就没法使用，就没法实现数据的压缩；熵说的就是这种下界。反过来，当我们说一个事件熵很大，就意味着1 这个事件的取值范围很多2或者这个事件中每个取值的概率比较均匀以上两者都代表着这个事件的不确定性很大，所以我们又说熵是一种不确定性的度量那么什么是条件熵呢，为什么(|)H A B 小于等于( )H A 呢？精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 20 页上面说了，知道了B，1：首先 A 的取值范围会缩小，为什么？拿上面一个例子来说，我知道了天气是下雪， 那么几乎可以说 A的取值只能从 春天，冬天 里选择； 2： A中每个取值的概率分布会发生变化(|)P A Bb 与( )P A 的概率分布不同；数学证明(|)()( )( )H A BH ABH BH A ；即已知 B的结果， A的不确定性减少；要表述 A这个事件的编码数更少；在决策树中，我们关心的是H结果 | 属性的关系，即已知某属性，结果的不确定性还有多少； 我们需要知道，哪个属性能使得结果的不确定性减少最多。2.3 决策树的生成2.3.1 ID3算法如果学习的任务是对一个大的例子集作分类概念的归纳定义，而这些例子又都是用一些无结构的属性值对来表示，则可以采用例如学习方法的一个变种决策树学习，其代表性的算法是昆兰，1986提出的 ID3。ID3 算法是由 Quinlan 首先提出的。该算法是以信息论为基础，以信息熵和信息增益度为衡量标准， 从而实现对数据的归纳分类。 以下是一些信息论的基本概念：定义：假设存在 n 个相同概率的消息，则每个消息的概率p 是 1/n ，一个消息传递的信息量为2( )Logn定义 2.3 ：假设有 n 个消息，其给定概率分布为( 1, 2)Ppppn ，则由该分布传递的信息量称为P的熵，记为21( )()niiiI pp Logp。定义： 假设一个记录集合 T根据类别属性的值被分成互相独立的类C1C2.Ck，则识别 T 的一个元素所属哪个类所需要的信息量为Info(T)=I(p)，其中P 为C1C2 Ck的概率分布，即(| 1| / |,| /|)(26)PCTCkT。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 20 页定义：假设我们先根据非类别属性X的值将 T分成集合 T1,T2Tn，则确定T 中一个元素类的信息量可通过确定Ti 的加权平均值来得到，即Info(Ti)的加权平均值为：1(,)(| / |)()(27)niInfo X TTiTInfo Ti定义：信息增益度是两个信息量之间的差值，其中一个信息量是需确定T的一个元素的信息量， 另一个信息量是在已得到的属性X的值后需确定的 T 一个元素的信息量，信息增益度公式为：(, )( )(, )(28)Gain X TInfo TInfo X TID3算法计算每个属性的信息增益， 并选取具有最高增益的属性作为给定集合的测试属性。对被选取的测试属性创建一个节点，并以该节点的属性标记， 对该属性的每个值创建一个分支据此划分样本。ID3 的输入是描述各种已知类别实例的列表。例子由预先定义的属性值对来表示。 归纳推理产生的结果不是以往讨论的那种合取表达式，而是一棵决策树也称判别树，并可转而表示为决策规则的一个集合，用它可正确地区分所有给定例子的类属。树中的每一非叶节点对应一个需测试的属性，每个分叉就是该属性可能的取值；树的叶节点则指示一个例子事物的类别。ID3 的显著优点是归纳学习花费的时间和所给任务的困难度 取决于例子个数， 用来描述对象的属性数， 所学习概念的复杂度即决策树的节点数等仅成线性增长关系。当然，ID3 只能处理用属性-值对表示的例子。在 ID3 中, 每一个例子用相同的一组属性来表示， 每一个属性又有自身的属性值集，如 颜色 属性可取值是 红、绿、兰 等。构造决策树的目的是为了对事物作出正确的分类。决策树形式的分类规则适用于任何的对象集。如是空的，那么它无需分类， 对应的决策树也为空； 如中的对象是同一类的， 那么决策树就一个叶节点， 即该类名； 如果集中的对象属于二个不同的类别，那未我们可以选取一个对象的属性，随后按其可能值把划分成一些不相交的子集C1 ，C2， Cn ，其中 Ci 是含有所选属性的第个值的那些对象集。对每一个这样的子集又可以用同样的策略处理，最后的结果是一棵树。ID3 Examples,Target-attrlbute,Attrlbutes 创建树的 root 节点精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 20 页如果 Examples 都为正，返回label=+的单节点输root如果 Examples 都为反，返回label=-的单节点输root如 果Attrlbutes为 空 ， 那 么 返 回 单 节 点 输root ， label=Examples中 最 普 遍 的Target-attributes 值否则开始A Attributes 中分类 examples 能力最好的属性Root 的决策属性A对于 A 的每个可能值vi在 root 下加一个新的分支对应测试A=vi令 Examples 为 Examples 中满足 A 属性值为vi 的子集如果 Examples 为空在这个新分支下加一个叶子结点，节点的label=Examples 中最普遍的Target-attributes 值否则在新分支下加一个子树ID3Examples Target-attribute，Attributes -A 结束返回 root下面给出一个关于人分类的例子对象集，并预先定义了指定的一组属性及其可取值：高度 高，矮 ，发色 ?黑色, 红色，金色 和眼睛 兰色，棕色 。这里，将人分为两类，分别以、来指示。高度发色眼睛类别矮黑色兰色高黑色兰色矮金色兰色高金色棕色高黑色棕色矮金色棕色高金色兰色精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 20 页高红色兰色如我们首先选取 发色 为树的根节点，即可获得图6.11 所示的决策树。相应于 黑色 ， 红色 和 金色三值都有一个对象子集。随后我们再测试金色 这一分支，又按属性 眼睛把其所含的对象集划分成兰色和棕色二类。至此，所有叶结点相应的对象子集只含同一类的对象，我们就可以用相应的类别名本例中的 + 和 - 来取代各子集，得到一决策树。一个对象所属类的判别从决策树的根开始，首先依据根节点指示的属性 发色 ，选择与该对象属性值相应的分支；然后，以同样的方式进行下去, 一直到达叶节点。 有时判别一个对象的类别， 由于从根到叶节点的路径较短，只要测试少量的属性。 如上例中， 假设 发色 的值是 黑色 或 红色 ，则对象就可以直接归属相应的类别， 而不必再去判定其它属性的取值；假设为 金色 ，则再测试一次眼睛 的值而不必考虑 高度 就可以进行判别。假设不存在这样的二个对象:? 它们在每个属性上都具有相同的值， 却属于不同的类别，那么这种生成决策树的过程是可行的。产生这种归纳学习方法的关键在于如何选择一系列有用的属性来测试一个对象集，以使生成的决策树是最小的。ID3 采用了香农 Shannon 信息论中的方法以使分类时期望平均的测试次数最小。一个决策树可看成一个信息源， 即给定一个对象， 可从决策树产生一个该对象所属类别的消息 (比方类别 + 或-) 。 决策树的复杂程度与借助这个消息所传递的信息量密切相关。假设决策树传递的不同类别消息的概率用P+ ( 对应于 +类)和 P-表示(对应于 - 类)，那么这个消息的期望信息量为: 22loglogPPPp对给定的物体集C，我们可以把这概率近似地表示为相对频率, 此时 P+和 P-分别等于 C中类别为 + 和- 的对象所占的比例。从 C集对应的决策树中得到消息的期望信息量记为M(C)，并定义 M()=0 。对于上述例子， C集有八个例子，三个为 + ，五为 - ，则22()(3/ 8)log(3/ 8)(5/ 8)log (5/ 8)0.954M Cbits这是一个局部决策树， A为构造决策树时下一个可能选取的属性，Ai 为属性A的值且是互斥的。 属性 A将集合 C划分为假设干个子集合 C1，C2 ，. ，Cn。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 20 页设 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构造局部决策树后还需要的期望信息量。二者的差越大， 说明测试这个属性所能传递的信息量越大, 则判别的速度也就越快。例如，我们选取的属性为 高度 ，对高度值为 高的分支的所需期望信息量为：22(2 / 5)log (2/ 5)(3/ 5)log (3/ 5)0.971bits同样对值为 矮 的分支为 : 22(1/ 3)log (1/ 3)(2 / 3)log (2/3)0.918bits则以属性 高度 作划分后进一步判别所需的期望信息量为：则测试这属性传递的信息为: bits。如果我们不是选择 高度而选用属性 头发, 则有: bits则测试属性 头发 获取的信息为 M(C)-B(C, 头发) = 0.945 - 0.5 = 0.45 bits 。bits 。根据最大信息量原理 ,ID3 就选取 头发 为决策树的根节点属性。ID3 通过不断的循环处理，逐步求精决策树，直到形成一棵完整的决策树，即树的叶节点所对应的对象例子均属于同一类。2 C4.5 算法继承了 ID3 算法的优点，并在以下几方面对ID3 算法进行了改良： 1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 20 页 2) 在树构造过程中进行剪枝； 3) 能够完成对连续属性的离散化处理； 4) 能够对不完整数据进行处理。C4.5 算法与其它分类算法如统计方法、神经网络等比较起来有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5 只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。C4.5 算法是以信息论为基础，以信息熵和信息增益度为衡量标准，从而实现对数据的归纳分类。1 用信息增益率来选择属性克服了用信息增益来选择属性时偏向选择值多的属性的不足。信息增益率定义为：( ,)( ,)(29)( ,)Gain S AGainRatio S ASplitInfo S A其中 Gain(S,A) 与 ID3 算法中的信息增益相同， 而分裂信息 SplitInfo(S,A)代表了按照属性 A分裂样本集 S的广度和均匀性。21|( ,)(210)|eiiiSSSplitInfo S ALogSS其中， S1到 Sc是 c 个不同值的属性A分割 S而形成的 c 个样本子集。如按照属性 A把 S集含 30 个用例分成了 10 个用例和 20 个用例两个集合则22( ,)(1/3) log (1/3)(2 / 3)log (2/ 3)SplitInfo S A2 可以处理连续数值型属性C4.5 既可以处理离散型描述属性，也可以处理连续性描述属性。在选择某节点上的分枝属性时，对于离散型描述属性，C4.5 的处理方法与ID3 相同，按照该属性本身的取值个数进行计算；对于某个连续性描述属性Ac，假设在某个结点上的数据集的样本数量为total ，C4.5 将作以下处理。(1) 将该结点上的所有数据样本按照连续型描述属性的具体数值，由小到大进行排序，得到属性值的取值序列A1c，A2c， Atotalc。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 20 页(2) 在取值序列中生成total-1个分割点。第i 0itotal个分割点的取值设置为 Vi=Aic+Ai+1 c/2, 它可以将该节点上的数据集划分为两个子集。(3) 从 total-1个分割点中选择最正确分割点。 对于每一个分割点划分数据集的方式， C4.5 计算它的信息增益比，并且从中选择信息增益比最大的分割点来划分数据集。3 采用了一种后剪枝方法防止树的高度无节制的增长，防止过度拟合数据，该方法使用训练样本集本身来估计剪枝前后的误差，从而决定是否真正剪枝。方法中使用的公式如下：Pr(211)(1)/fqzcqqN其中 N是实例的数量， f=E/N 为观察到的误差率其中E 为 N个实例中分类错误的个数，q 为真实的误差率， c 为置信度，z 为对应于置信度c 的标准差，其值可根据 c 的设定值通过查正态分布表得到。通过该公式即可计算出真实误差率 q 的一个置信度上限，用此上限为该节点误差率e 做一个悲观的估计：2222224(212)1zffzfZNNNNezN通过判断剪枝前后 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% 被分配到另一个分支。这些片断样例fractional examples的目的是计算信息增益，另外，如果有第二个缺少值的属性必须被测试，这些样例可以在后继的树分支中被进一步细分。 C4.5 就是使用这种方法处理缺少的属性值。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页，共 20 页优点：产生的分类规则易于理解，准确率较高。缺点：在构造树的过程中， 需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5 只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。2.4 决策树的剪枝通常在实际应用中， 直接生成的完全决策树不能立即用于对未知样本进行分类。由于完全决策树对训练样本的特征描述得“过于精确”，无法实现对新样本的合理分析， 所以此时它不是一棵分析新数掘的最正确决策树。一棵完全决策树能准确地反映训练集中数据特征， 但因失去了一般代表性而无法用于对新数据的分类或预测，这种现象称为“过适应” 。解决过适应问题的主要方法是对决策树进行剪枝。剪枝(Pruning) 方法的主要目的是去掉那些噪声或异常数据，使决策树具有更泛化能力。剪枝常采用统计度量， 剪掉最不可靠的分枝， 从而带来较快的分类，提高树独立于测试数据进行证确分类的能力。剪枝按其实施的时间分为两种方法：事前修剪法和事后修剪法。1事前修剪法该方法通过提前停止树的构造而对树“剪枝”，即通过在当前节点上判断是否需要继续划分该节点所含训练样本集来实现。一旦停止，节点不再继续分裂，当前节点就成为一个叶节点。 该叶节点中可能包含多个不同类别的训练样本，由于该修剪是在分枝之前做出的， 所以称之为事前修剪。 事前修剪法的优点是在树生成的同时进行了剪枝， 因而效率高， 但是它可能剪去了某些有用但还没生成的节点。常用的方法是设定决策树的最大高度( 层数) 来限制树的生长。 还有一种方法是设定每个节点必须包含的最少记录数，当节点中记录的个数小于这个数值时就停止分割。 然而，选择一个适当的阈值是比较困难的，较高的阈值可能导致过分简化的树，而较低的阈值可能会导致多余树枝无法修剪。2事后修剪法精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页，共 20 页该方法是由完全生长的树剪去分枝。通过删除节点的分枝， 剪掉树节点。 它在允许决策树得到最充分生长的基础上，再根据一定的规则， 剪去决策树中的那些不具有一般代表性的叶节点或分枝。修剪后，被修剪的分枝节点就成为一个叶节点，并将其标记为它所包含样本中类别个数最多的类别。事后修剪是一边修剪一边检验的过程，一般规则是：当树建好之后，对每个内部节点，首先计算该节点上的子树被剪枝可能出现的错误率，然后，使用每个分枝的错误率， 结合沿每个分枝观察的权重评估， 计算不对该节点剪枝的期望错误率。如果剪掉该节点能够降低错误率， 那么该节点的所有子节点就被剪掉，该节点成为叶节点。 产生一组逐渐被剪枝的树之后， 使用一个独立的测试集评估每棵树的准确率，就能得到具有最小期望错误率的决策树。当然也可以结合使用事前修剪和事后修剪，形成混合的修剪方法。 事后修剪比事前修剪需要更多的计算时阃，但通常产生的决策树更为可靠。2.5 决策树的建立决策树的建立过程主要由两个阶段组成：第一阶段， 建树阶段。 选取训练数据集进行学习， 导出决策树。 决策树归纳的基本算法是贪心算法，它采用的是自项向下递归的各个击破方式来构建判定树，算法概述如下。第二阶段，剪枝阶段。用测试数据集检验决策树，如果所建立的决策树不能正确答复所研究的问题，我们要对决策树进行剪枝以解决过分适应数据问题，直到建立一棵正确的决策树，目的是降低由于训练集的噪声而产生的起伏。建立决策树的算法可以被描述成一个递归的过程：首先，选择训练样本的一个属性作为节点， 对该属性的每种可能的取值创建一个分枝，并据此将训练样本划分为几个子集。 然后，对每个分枝采取相同的方法，训练样本是其父节点划分的假设干子集中的对应于该分枝取值的那个样本子集。当以下情况出现时停止该节点分枝的分裂，并使其成为叶节点：(1) 给定节点的所有训练样本属于同一类(2) 没有剩余属性可以用来进一步划分样本(3) 该分枝没有样本。建立决策树的算法如下：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页，共 20 页算法： Generate_decision_tree 由给定的训练数据产生一棵判定树。输入：训练样本samples，由离散值属性表示；候选属性的集合attribute_jist 。输出：一棵判定树。方法：(1)创建节点N；(2)If samples 都在同一个类C then(3)返回 N 作为叶节点，以类C 标记：(4)If attribute_list为空。 then(5)返回 N 作为叶节点，标记为samples中最普通的类；(6)选择 attribute_list 中具有最高信息增益的属性test_attribute；(7)标记节点为test_attribute：(8)For each test_attribute 中的已知值ai：(9) 由节点 N 长出一个条件为test_attribute=a的分枝：(10)设 S1是 samples中 test attribute=a 的样本的集合：(1I)If S1 为空， then(12)加上一个树叶，标记为samples 中最普通的类；(13)Else 加上一个由Generate_decision_tree (s1，attribute_1ist_test_attribute) 返回的节点。说明如下：1、决策树开始时，作为一个单个结点( 根节点 )包含所有的训练样本集。2、 假设一个节点的样本均为同一类别， 则该节点就成为叶节点并标记为该类别。3、否则该算法将采用信息熵方法( 信息增益 ) 作为启发信息来帮助选择合适的属性， 以便将样本分为假设干子集。 这个属性就成为该节点的测试属性。 在算法中，所有属性均为离散值，假设有取连续值的属性，就必须首先进行离散化。4、一个测试属性的每个值均对应一个将要被创建的分枝，同时也对应着一个被划分的子集。5、 算法递归使用上述各处理过程， 针对所获得的每个划分均又获得一个决策树。假设一个属性一旦在某个节点出现， 那它就不能再出现在该节点之后所产生的子树节点中。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页，共 20 页6、算法递归操作停止的条件是：(1) 一个节点的所有样本均为同一类别。(2) 假设无属性可用于当的样本集，这里用少数服从多数的原则，将当前节点标记成叶节点，并标记为当前所合样本集中类别个数最多的类别。(3) 没有样本满足条件，则创建一个叶节点并将其标记为当前节点所含样本集中类别个数最多的类别。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 20 页，共 20 页