决策树C45算法总结课件(PPT 41)

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2013/10/30,#,C4.5,示例,数据：,weka,中的,weather,数据（字符型、数值型）,outlook,temperature,humidity,windy,play,sunny,hot,high,FALSE,no,sunny,hot,high,TRUE,no,overcast,hot,high,FALSE,yes,rainy,mild,high,FALSE,yes,rainy,cool,normal,FALSE,yes,rainy,cool,normal,TRUE,no,overcast,cool,normal,TRUE,yes,sunny,mild,high,FALSE,no,sunny,cool,normal,FALSE,yes,rainy,mild,normal,FALSE,yes,sunny,mild,normal,TRUE,yes,overcast,mild,high,TRUE,yes,overcast,hot,normal,FALSE,yes,rainy,mild,high,TRUE,no,outlook,temperature,humidity,windy,play,sunny,85,85,FALSE,no,sunny,80,90,TRUE,no,overcast,83,86,FALSE,yes,rainy,70,96,FALSE,yes,rainy,68,80,FALSE,yes,rainy,65,70,TRUE,no,overcast,64,65,TRUE,yes,sunny,72,95,FALSE,no,sunny,69,70,FALSE,yes,rainy,75,80,FALSE,yes,sunny,75,70,TRUE,yes,overcast,72,90,TRUE,yes,overcast,81,75,FALSE,yes,rainy,71,91,TRUE,no,C4.5,示例,SPSS Clementine C5.0,C4.5,示例,Weka J48,C4.5,算法简介,决策树方法：,利用一定的训练样本，从数据中学习出决策规则自动构造出决策树,。,C4.5,算法,:,C4.5:programsformachine learning,JR,Quinlan, 1993,分类,决策树算法,其核心算法是,ID3,算法,。目前应用在临床决策、生产制造、文档分析、生物信息学、空间数据建模等领域。算法的输入是带类标的数据，输出是树形的决策规则。,ID3,算法,：,Induction of decision trees,JR,Quinlan- Machine learning, 1986,ID3,算法的原型来自于,Hunt,等人提出的概念学习系统（,concept learning system, CLS,）,。,C4.5,算法简介,C4.5,比,ID3,的,改进,:,1),用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；,2,),在树构造过程中进行剪枝；,3,),能够完成对连续属性的离散化处理；,4,),能够对不完整数据进行处理。,C4.5,算法优点,：产生的分类规则易于理解，准确率较高,。,C4.5,算法,缺点：,在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。,决策树算法发展,二级存储,:,针对不能完全放入内存的数据集，在确保分类器算法效能的前提下,，要做到数据集扫描遍数的极小化,。,BOAT,算法（,BOAT-optimistic decision tree construction,J Gehrke, V Ganti, R Ramakrishnan - SIGMOD , 1999,）使用抽样、融合、完整扫描三步得到最终的分类器。,RainForest,框架（,Rainforest-a frameworkfor fast decision tree construction of large datasets,J Gehrke, R Ramakrishnan, V Ganti - VLDB, 1998,）实现了多种具体的,决策树构建方法，适用于大规模数据集的处理。其他基于二级存储设备的算法还有,SLIQ,（,SLIQ: Afast scalableclassifier for data mining, M Mehta, R Agrawal, J Rissanen - Advances in Database Technology , 1996,），,SPRINT,（,SPRINT,: A scalable parallel classi er for data,mining,J,Shafer, R Agrawal, M Mehta - Proc. 1996 Int. Conf. Very Large Data , 1996 -,Citeseer,），,PUBLIC,（,PUBLIC,:A decision treeclassifier that integrates building and,pruning,R,Rastogi, K Shim - VLDB, 1998 - cs.sfu.ca,）等。,斜决策树：,斜决策树适用于处理连续型数据，决策准则使用属性的线性组合。采用属性的线性组合策略的一个典型的决策树分类器是,OC1,（,A,systemforinductionof oblique decision,trees,SK,Murthy, S Kasif, S Salzberg - arXiv preprint cs/9408103, 1994 -,arxiv.org,）,）,。,集成方法：,装袋法和推举法,。（,Popular,ensemblemethods: An empirical,study,R,Maclin, D Opitz - arXiv preprint arXiv:1106.0257, 2011 - arxiv.org,算法流程：,1,）选择哪个属性进行节点分裂？,2,）何时停止树生长？,3,）怎么处理连续型属性？,4,）怎么处理缺失值？,5,）怎么处理过拟合问题？,问题：,1,）选择节点分裂属性,2,）建立新节点，划分数据集,3,）判断节点是否到生长停止条件，如果是，终止生长，如果不是，转到,1,）,选择节点分裂属性的问题,熵（,Entropy,）：,我们把一个事件的不确定程度叫做“熵”，熵越大表明这个事件的结果越难以预测，同时事件的发生将给我们带来越多的信息,。,增益（,InformationGain,）：,在信息增益中，衡量标准是看特征能够为分类系统带来多少信息，带来的信息越多，该特征越重要。对一个特征而言，系统有它和没它时信息量将发生变化，而前后信息量的差值就是这个特征给系统带来的信息量。所谓信息量，就是熵,。,系统原先的熵是,H(X),，在条件,Y,已知的情况下系统的熵（条件熵）为,H(X|Y),，信息增益就是这两个熵的,差值。,outlook,temperature,humidity,windy,play,sunny,hot,high,FALSE,no,sunny,hot,high,TRUE,no,overcast,hot,high,FALSE,yes,rainy,mild,high,FALSE,yes,rainy,cool,normal,FALSE,yes,rainy,cool,normal,TRUE,no,overcast,cool,normal,TRUE,yes,sunny,mild,high,FALSE,no,sunny,cool,normal,FALSE,yes,rainy,mild,normal,FALSE,yes,sunny,mild,normal,TRUE,yes,overcast,mild,high,TRUE,yes,overcast,hot,normal,FALSE,yes,rainy,mild,high,TRUE,no,只看最后一列我们得到打球的概率是,9/14,，不打球的概率是,5/14,。因此在没有任何先验信息的情况下，系统的熵（不确定性）,为：,outlook,temperature,humidity,windy,play,yes,no,yes,no,yes,no,yes,no,yes,no,sunny,2,3,hot,2,2,high,3,4,FALSE,6,2,9,5,overcast,4,0,mild,4,2,normal,6,1,TRU,E,3,3,rainy,3,2,cool,3,1,如果选,outlook,作为决策树的根节点，（,7,）式中的,Y,为集合,sunny,、,overcast,、,rainy,，此时的条件熵为,即选择,outlook,作为决策树的根节点时，信息增益为,0.94-0.693=0.247,，然后计算,outlook,属性的熵，得增益比。同样,方法计算当选择,temperature,、,humidity,、,windy,作为根节点时系统的信息,增益和属性熵，选择增益比最大,的作为最终的根节点。,选择节点分裂属性的问题,ID3,算法：使用信息增益作为选择节点分裂属性的指标。增益准则的一个缺陷是它偏向于选择具有更多取值的属性作为节点分裂属性。,C4.5,算法：使用信息增益率作为选择节点分裂属性的指标，克服了,ID3,算法的缺点。,增益,比（,Gain ratio,）：增益,/,属性熵,树停止生长条件,1,）节点内的数据已经完全属于同一类别。,2,）节点内测数据样本数低于某一阈值。,3,）所有属性都已经被分裂过。,处理连续型数据,ID3,算法：不能处理连续型数据，只能处理离散型数据。,C4.5,算法：以二值离散的方式处理连续型数据。,二值,离散：对连续型属性进行排序，得到多个候选阈值，选取产生最大信息增益的阈值作为分裂阈值。,Temperature,：,40 48,60,72 80 90,Play Tennis: No,No Yes Yes Yes Yes,On,the handling of continuous-valued attributes in decision tree,generation,UMFayyad, KB Irani - Machine learning, 1992 - Springer,Multi-interval,discretization of continuous-valued attributes for classification,learning,UFayyad, K Irani - 1993 - trs-new.jpl.nasa.gov,处理缺失值,ID3,算法：不能处理缺失值。,C4.5,算法：可以处理缺失值。,Unknown,attribute valuesin induction,.,JR Quinlan - ML, 1989 - Citeseer,三种情况：,1,）在具有缺失值的属性上如何计算信息增益率？,解决方案：,a),忽略该类样本。,b),选择常用值或均值填充。,c,),依据缺失比例，折算信息增益,/,信息增益率。,d),对缺失值赋予独特的值，参与训练。,2,）具有缺失值的样本在进行数据分裂时，分配给哪个子数据集？,解决,方案：,a),忽略该类样本。,b),选择常用值或均值填充。,c,),根据其他非缺失属性的比例，分配到子数据集中。,d),为缺失值建立单独分支。,f),确定最可能的取值，按比例仅分配给一个子数据集。,3,）对新样本进行分类时，缺失值导致样本到达叶子节点，怎么处理？,解决,方案：,a),有缺失值单独分支，走单独分支。,b),走最常见的值的分支。,c,),确定最可能取值，走相应分支。,d),走所有分支，根据不同输出结果的概率进行组合。,f),不,进行分类，直接赋给最有可能的值。,过拟合问题,过拟合：,有监督的算法需要考虑泛化能力，在有限样本的条件下，决策树超过一定规模后，训练错误率减小，但测试错误率会增加。,剪枝,：,控制决策树规模的方法称为剪枝，一种是先剪枝，一种是后剪枝。所谓先剪枝，实际上是控制决策树的生长；后剪枝是指，对完全生成的决策树进行修剪,。,先,剪枝：,1),数据划分法。划分数据成训练样本和测试样本，使用用训练样本进行训练，使用测试样本进行树生长检验。,2),阈值法。当某节点的信息增益小于某阈值时，停止树生长。,3),信息增益的统计显著性分析。从已有节点获得的所有信息增益统计其分布，如果继续生长得到的信息增,益与该分布相比不显著，则停止树的生长。,优点：,简单直接；,缺点：,对于不回溯的贪婪算法，缺乏后效性考虑，可能导致树提前停止,。,过拟合问题,后剪枝：,减少分类错误修剪法。使用独立的剪枝集估计剪枝前后的分类错误率，基于此进行剪枝。,最小代价与复杂性折中的剪枝。对剪枝后的树综合评价错误率和复杂性，决定是否剪枝。,最小描述长度准则。最简单的树就是最好的树。对决策树进行编码，通过剪枝得到编码最小的树。,规则,后剪枝。将训练完的决策树转换成规则，通过删除不会降低估计精度的前件修剪每一条规则。,优点,:,实际应用中有效,缺点：,数据量大时，计算代价较大。,C4.5,的剪枝方法,C4.5,采用悲观剪枝法，它使用训练集生成决策树又用它来进行剪枝，不需要独立的剪枝集,。,C4.5,的剪枝方法,C4.5,的剪枝方法,Weka J48,算法参数,是否对离散属性进行二元分裂,剪枝过程中的置信因子，值越小剪枝越多,设置为,true,，控制台会输出调试信息,叶节点的最小实例数,定义用来剪枝的样本比例,是否使用减少误差剪枝法,是否保存训练样本数据,使用减小误差剪枝法中的随机种子参数,修剪时是否考虑子树上升,是否剪枝,是否在对叶子计数时使用拉普拉斯平滑,Weka J48,算法源码解析,Weka J48,算法源码解析,高级类,J48,Weka J48,算法源码解析,可剪枝的,C4.5,分类器,Weka J48,算法源码解析,分类树,Weka J48,算法源码解析,分类树,Weka J48,算法源码解析,C4.5,分裂模式,Weka J48,算法源码解析,C4.5,分裂模式,Weka J48,算法源码解析,C4.5,分裂模式,Weka J48,算法源码解析,选择分裂属性,Weka J48,算法源码解析,处理离散属性,Weka J48,算法源码解析,计算增益,Weka J48,算法源码解析,计算增益率,Weka J48,算法源码解析,熵和条件熵,Weka J48,算法源码解析,属性熵,Weka J48,算法源码解析,处理连续属性,Weka J48,算法源码解析,处理连续属性,Weka J48,算法源码解析,处理所有可能的分裂点,Weka J48,算法源码解析,剪枝算法,Weka J48,算法源码解析,剪枝算法,Weka J48,算法源码解析,计算错误率,