决策树C45算法总结

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,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:programsformachinelearning,JRQuinlan,1993,分类决策树算法,其核心算法是,ID3,算法,。目前应用在临,床,床决策、生产制,造,造、文档分析、,生,生物信息学、空,间,间数据建模等领,域,域。算法的输入,是,是带类标的数据,，,，输出是树形的,决,决策规则。,ID3,算法：,Induction of decisiontrees,JRQuinlan-Machine learning,1986,ID3,算法的原型来自,于,于,Hunt,等人提出的概念,学,学习系统（,conceptlearning system,CLS,）。,C4.5,算法简介,C4.5,比,ID3,的改进,:,1),用信息增益率,来,来选择属性，,克,克服了用信息,增,增益选择属性,时,时偏向选择取,值,值多的属性的,不,不足；,2),在树构造过程,中,中进行剪枝；,3),能够完成对连,续,续属性的离散,化,化处理；,4),能够对不完整,数,数据进行处理,。,。,C4.5,算法优点,：产生的分类,规,规则易于理解,，,，准确率较高。,C4.5,算法,缺点：,在构造树的过,程,程中，需要对,数,数据集进行多,次,次的顺序扫描,和,和排序，因而,导,导致算法的低,效,效。,决策树算法发,展,展,二级存储,:,针对不能完全,放,放入内存的数,据,据集，在确保,分,分类器算法效,能,能的前提下，要做到数据,集,集扫描遍数的,极,极小化。,BOAT,算法（,BOAT-optimistic decisiontreeconstructionJ Gehrke,VGanti,R Ramakrishnan-SIGMOD,1999,）使用抽样、,融,融合、完整扫,描,描三步得到最,终,终的分类器。,RainForest,框架（,Rainforest-aframeworkfor fast decision tree construction of large datasetsJ Gehrke,RRamakrishnan,V Ganti-VLDB,1998,）实现了多种,具,具体的,决策树构建方,法,法，适用于大,规,规模数据集的,处,处理。其他基,于,于二级存储设,备,备的算法还有,SLIQ,（,SLIQ:Afast scalableclassifier for datamining M Mehta,RAgrawal,JRissanen-Advances in Database Technology,1996,），,SPRINT,（,SPRINT:A scalableparallel classi er fordataminingJShafer,R Agrawal,M Mehta-Proc.1996 Int.Conf.Very Large Data,1996-Citeseer,），,PUBLIC,（,PUBLIC:A decisiontreeclassifier that integrates buildingandpruningRRastogi,K Shim-VLDB,1998-cs.sfu.ca,）等。,斜决策树：,斜决策树适用,于,于处理连续型,数,数据，决策准,则,则使用属性的,线,线性组合。采,用,用属性的线性,组,组合策略的一,个,个典型的决策,树,树分类器是,OC1,（,Asystemforinductionofoblique decisiontreesSKMurthy,S Kasif,SSalzberg-arXivpreprint cs/9408103,1994-arxiv.org,）,）。,集成方法：,装袋法和推举,法,法。（,Popularensemblemethods:An empiricalstudyRMaclin,D Opitz-arXivpreprint 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,Onthe handlingof continuous-valued attributes indecision treegeneration,UMFayyad,KB Irani-Machinelearning,1992-Springer,Multi-intervaldiscretization ofcontinuous-valuedattributes for classificationlearning,UFayyad,KIrani-1993-trs-new.jpl.nasa.gov,处理缺失值,ID3,算法：不能处,理,理缺失值。,C4.5,算法：可以处,理,理缺失值。,Unknownattribute valuesin induction.,JR Quinlan-ML,1989-Citeseer,三种情况：,1,）在具有缺失,值,值的属性上如,何,何计算信息增,益,益率？,解决方案：,a),忽略该类样本,。,。,b)