决策树C算法总结课件

1、C4.5示例 数据：weka中的weather数据（字符型、数值型）outlook,temperature,humidity,windy,playsunny,hot,high,FALSE,nosunny,hot,high,TRUE,noovercast,hot,high,FALSE,yesrainy,mild,high,FALSE,yesrainy,cool,normal,FALSE,yesrainy,cool,normal,TRUE,noovercast,cool,normal,TRUE,yessunny,mild,high,FALSE,nosunny,cool,normal,FALSE,y

2、esrainy,mild,normal,FALSE,yessunny,mild,normal,TRUE,yesovercast,mild,high,TRUE,yesovercast,hot,normal,FALSE,yesrainy,mild,high,TRUE,nooutlook,temperature,humidity,windy,playsunny,85,85,FALSE,nosunny,80,90,TRUE,noovercast,83,86,FALSE,yesrainy,70,96,FALSE,yesrainy,68,80,FALSE,yesrainy,65,70,TRUE,noove

3、rcast,64,65,TRUE,yessunny,72,95,FALSE,nosunny,69,70,FALSE,yesrainy,75,80,FALSE,yessunny,75,70,TRUE,yesovercast,72,90,TRUE,yesovercast,81,75,FALSE,yesrainy,71,91,TRUE,no决策树C算法总结C4.5示例 SPSS Clementine C5.0决策树C算法总结C4.5示例 Weka J48决策树C算法总结C4.5算法简介决策树方法：决策树方法：利用一定的训练样本，从数据中学习出决策规则自动构造出决策树。C4.5算法算法: C4. 5:

4、 programs for machine learningJR Quinlan, 1993分类决策树算法,其核心算法是ID3算法。目前应用在临床决策、生产制造、文档分析、生物信息学、空间数据建模等领域。算法的输入是带类标的数据，输出是树形的决策规则。ID3算法算法：Induction of decision treesJR Quinlan - Machine learning, 1986 ID3算法的原型来自于Hunt等人提出的概念学习系统（concept learning system, CLS）。决策树C算法总结C4.5算法简介C4.5比比ID3的的改进改进:1) 用信息增益率来选择属性

5、，克服了用信息增益选择属性时偏向选择取值多的属性的不足；2) 在树构造过程中进行剪枝；3) 能够完成对连续属性的离散化处理；4) 能够对不完整数据进行处理。C4.5算法优点算法优点：产生的分类规则易于理解，准确率较高。C4.5算法算法缺点：缺点：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。决策树C算法总结决策树算法发展二级存储二级存储:针对不能完全放入内存的数据集，在确保分类器算法效能的前提下，要做到数据集扫描遍数的极小化。BOAT算法（ BOAT-optimistic decision tree constructionJ Gehrke, V Ganti, R

6、 Ramakrishnan - SIGMOD , 1999）使用抽样、融合、完整扫描三步得到最终的分类器。RainForest框架（Rainforest-a framework for fast decision tree construction of large datasetsJ Gehrke, R Ramakrishnan, V Ganti - VLDB, 1998）实现了多种具体的决策树构建方法，适用于大规模数据集的处理。其他基于二级存储设备的算法还有SLIQ（ SLIQ: A fast scalable classifier for data mining M Mehta, R A

7、grawal, J Rissanen - Advances in Database Technology , 1996 ），SPRINT（SPRINT: A scalable parallel classi er for data miningJ Shafer, R Agrawal, M Mehta - Proc. 1996 Int. Conf. Very Large Data , 1996 - Citeseer），PUBLIC（ PUBLIC: A decision tree classifier that integrates building and pruningR Rastogi,

8、K Shim - VLDB, 1998 - cs.sfu.ca）等。斜决策树：斜决策树：斜决策树适用于处理连续型数据，决策准则使用属性的线性组合。采用属性的线性组合策略的一个典型的决策树分类器是OC1（A system for induction of oblique decision treesSK Murthy, S Kasif, S Salzberg - arXiv preprint cs/9408103, 1994 - ）。集成方法：集成方法：装袋法和推举法。（Popular ensemble methods: An empirical studyR Maclin,

9、D Opitz - arXiv preprint arXiv:1106.0257, 2011 - 决策树C算法总结算法流程：1）选择哪个属性进行节点分裂？2）何时停止树生长？3）怎么处理连续型属性？4）怎么处理缺失值？5）怎么处理过拟合问题？问题：1）选择节点分裂属性2）建立新节点，划分数据集3）判断节点是否到生长停止条件，如果是，终止生长，如果不是，转到1）决策树C算法总结决策树C算法总结选择节点分裂属性的问题 熵（Entropy）：我们把一个事件的不确定程度叫做“熵”，熵越大表明这个事件的结果越难以预测，同时事件的发生将给我们带来越多的信息。增益（Information

10、Gain）：在信息增益中，衡量标准是看特征能够为分类系统带来多少信息，带来的信息越多，该特征越重要。对一个特征而言，系统有它和没它时信息量将发生变化，而前后信息量的差值就是这个特征给系统带来的信息量。所谓信息量，就是熵。系统原先的熵是H(X)，在条件Y已知的情况下系统的熵（条件熵）为H(X|Y)，信息增益就是这两个熵的差值。决策树C算法总结outlooktemperaturehumiditywindyplaysunnyhothighFALSEnosunnyhothighTRUEnoovercasthothighFALSEyesrainymildhighFALSEyesrainycoolnorm

11、alFALSEyesrainycoolnormalTRUEnoovercastcoolnormalTRUEyessunnymildhighFALSEnosunnycoolnormalFALSEyesrainymildnormalFALSEyessunnymildnormalTRUEyesovercastmildhighTRUEyesovercasthotnormalFALSEyesrainymildhighTRUEno只看最后一列我们得到打球的概率是9/14，不打球的概率是5/14。因此在没有任何先验信息的情况下，系统的熵（不确定性）为：决策树C算法总结outlooktemperaturehu

12、miditywindyplay yesno yesno yesno yesnoyesnosunny23hot22high34FALSE6295overcast40mild42normal61TRUE33 rainy32cool31 如果选outlook作为决策树的根节点，（7）式中的Y为集合sunny、overcast、rainy，此时的条件熵为即选择outlook作为决策树的根节点时，信息增益为0.94-0.693=0.247，然后计算outlook属性的熵，得增益比。同样方法计算当选择temperature、humidity、windy作为根节点时系统的信息增益和属性熵，选择增益比最大的作

13、为最终的根节点。决策树C算法总结选择节点分裂属性的问题 ID3算法：使用信息增益作为选择节点分裂属性的指标。增益准则的一个缺陷是它偏向于选择具有更多取值的属性作为节点分裂属性。 C4.5算法：使用信息增益率作为选择节点分裂属性的指标，克服了ID3算法的缺点。增益增益比（比（Gain ratio）：增益）：增益/属性熵属性熵决策树C算法总结树停止生长条件1）节点内的数据已经完全属于同一类别。2）节点内测数据样本数低于某一阈值。3）所有属性都已经被分裂过。决策树C算法总结处理连续型数据 ID3算法：不能处理连续型数据，只能处理离散型数据。 C4.5算法：以二值离散的方式处理连续型数据。二值离散：对

14、连续型属性进行排序，得到多个候选阈值，选取产生最大信息增益的阈值作为分裂阈值。Temperature： 40 48 60 72 80 90Play Tennis: No No Yes Yes Yes YesOn the handling of continuous-valued attributes in decision tree generationUM Fayyad, KB Irani - Machine learning, 1992 - SpringerMulti-interval discretization of continuous-valued attributes for c

15、lassification learningU Fayyad, K Irani - 1993 - 决策树C算法总结处理缺失值ID3算法：不能处理缺失值。C4.5算法：可以处理缺失值。Unknown attribute values in induction.JR Quinlan - ML, 1989 - Citeseer三种情况：1）在具有缺失值的属性上如何计算信息增益率？解决方案：a) 忽略该类样本。b) 选择常用值或均值填充。c ) 依据缺失比例，折算信息增益/信息增益率。d) 对缺失值赋予独特的值，参与训练。2）具有缺失值的样本在进行数据分裂时，分

16、配给哪个子数据集？解决方案：a) 忽略该类样本。b) 选择常用值或均值填充。c ) 根据其他非缺失属性的比例，分配到子数据集中。d) 为缺失值建立单独分支。 f) 确定最可能的取值，按比例仅分配给一个子数据集。3）对新样本进行分类时，缺失值导致样本到达叶子节点，怎么处理？解决方案：a) 有缺失值单独分支，走单独分支。b) 走最常见的值的分支。c ) 确定最可能取值，走相应分支。d) 走所有分支，根据不同输出结果的概率进行组合。 f) 不进行分类，直接赋给最有可能的值。决策树C算法总结过拟合问题过拟合：过拟合：有监督的算法需要考虑泛化能力，在有限样本的条件下，决策树超过一定规模后，训练错误率减小

17、，但测试错误率会增加。剪枝剪枝：控制决策树规模的方法称为剪枝，一种是先剪枝，一种是后剪枝。所谓先剪枝，实际上是控制决策树的生长；后剪枝是指，对完全生成的决策树进行修剪。先先剪枝：剪枝：1) 数据划分法。划分数据成训练样本和测试样本，使用用训练样本进行训练，使用测试样本进行树生长检验。2) 阈值法。当某节点的信息增益小于某阈值时，停止树生长。3) 信息增益的统计显著性分析。从已有节点获得的所有信息增益统计其分布，如果继续生长得到的信息增 益与该分布相比不显著，则停止树的生长。优点：优点：简单直接；缺点：缺点：对于不回溯的贪婪算法，缺乏后效性考虑，可能导致树提前停止。决策树C算法总结过拟合问题 后

18、剪枝：后剪枝：1) 减少分类错误修剪法。使用独立的剪枝集估计剪枝前后的分类错误率，基于此进行剪枝。2) 最小代价与复杂性折中的剪枝。对剪枝后的树综合评价错误率和复杂性，决定是否剪枝。3) 最小描述长度准则。最简单的树就是最好的树。对决策树进行编码，通过剪枝得到编码最小的树。4) 规则后剪枝。将训练完的决策树转换成规则，通过删除不会降低估计精度的前件修剪每一条规则。 优点优点: 实际应用中有效 缺点：缺点：数据量大时，计算代价较大。决策树C算法总结C4.5的剪枝方法 C4.5采用悲观剪枝法，它使用训练集生成决策树又用它来进行剪枝，不需要独立的剪枝集。决策树C算法总结C4.5的剪枝方法决策树C算法总结C4.5的剪枝方法决策树C算法总结Weka J48算法参数是否对离散属性进行二元分裂剪枝过程中的置信因子，值越小剪枝越多设置为true，控制台会输出调试信息叶节点的最小实例数定义用来剪枝的样本比例是否使用减少误差剪枝法是否保存训练样本数据使用减小误差剪枝法中的随机