决策树C45算法总结.pptx

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,nooutlook,temperature,humidity,windy,play sunny,85,85,FALSE,nosunny,80,90,TRUE,noovercast,83,86,FALSE,yesrainy,70,96,FALSE,yesrainy,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: programs for machine learning》JR Quinlan, 1993分类决策树算法,其核心算法是ID3算法。目前应用在临床决策、生产制造、文档分析、生物信息学、空间数据建模等领域。算法的输入是带类标的数据，输出是树形的决策规则。ID3算法：《Inductio第四n页，共四o十二f页。 decision trees》 C4.5算法简介C4.5比ID3的改进:用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；在树构造过程中进行剪枝；能够完成对连续属性的离散化处理；能够对不完整数据进行处理。C4.5算法优点：产生的分类规则易于理解，准确率较高。C4.5算法缺点：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。第五页，共四十二页。 决策树算法发展二级存储:针对不能完全放入内存的数据集，在确保分类器算法效能的前提下，要做到数据集扫描遍数的极小化。BOAT算法（《 BOAT-optimistic decision tree construction》J Gehrke, V Ganti, R Ramakrishnan… - SIGMOD …, 1999）使用抽样、融合、完整扫描三步得到最终的分类器。RainForest框架（《Rainforest-a framework for fast decision tree construction of large datasets》J Gehrke Ramakrishnan, V Ganti - VLDB, 1998）实现了多种具体的决策树构建方法，适用于大规模数据集的处理。其他基于二级存第六页，储共四十二页设。 备的算法还有SLIQ 算法流程：问题：选择节点分裂属性建立新节点，划分数据集判断节点是否到生长停止条件，如果是，终止生长，如果不是，转到1）选择哪个属性进行节点分裂？何时停止树生长？怎么处理连续型属性？怎么处理缺失值？第七页，共四十二页。 第八页，共四十二页。 选择节点分裂属性的问题 熵（Entropy）：我们把一个事件的不确 定程度叫做“熵”，熵越大表明这个事件的结果越难以预测，同时事件的发生将给我 增们益带（来I越nf多or的mat信io息n G。ain）：在信息增益中，衡量标准是看特征能够为分类系统带来多少信息，带 来的信息越多，该特征越重要。对一个特征而言，系统有它和没它时信息量将发生变化，而前后信 息量的差值就是这个特征给系统带来的信息量。 所谓信息量，就是熵。系统原先的熵是H(X)