决策树C4.5算法总结

c45算法的调研,包括：weka中的实例,算法研讨问题,算法原理,weka代码展示等。

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

c45算法的调研,包括：weka中的实例,算法研讨问题,算法原理,weka代码展示等。

C4.5示例 SPSS Clementine C5.0

c45算法的调研,包括：weka中的实例,算法研讨问题,算法原理,weka代码展示等。

C4.5示例 Weka J48

c45算法的调研,包括：weka中的实例,算法研讨问题,算法原理,weka代码展示等。

C4.5算法简介决策树方法：利用一定的训练样本，从数据中学习出 决策规则自动构造出决策树。 C4.5算法: 《C4. 5: programs for machine learning》 JR Quinlan, 1993 分类决策树算法,其核心算法是ID3算法。目前应用在临 床决策、生产制造、文档分析、生物信息学、空间数 据建模等领域。算法的输入是带类标的数据，输出是 树形的决策规则。 ID3算法：《Induction of decision trees》 JR Quinlan - Machine learning, 1986 ID3算法的原型来自于Hunt等人提出的概念学习系统 (concept learning system, CLS)。

c45算法的调研,包括：weka中的实例,算法研讨问题,算法原理,weka代码展示等。

C4.5算法简介C4.5比ID3的改进: 1) 用信息增益率来选择属性，克服了用信息增 益选择属性时偏向选择取值多的属性的不足； 2) 在树构造过程中进行剪枝； 3) 能够完成对连续属性的离散化处理； 4) 能够对不完整数据进行处理。 C4.5算法优点：产生的分类规则易于理解，准 确率较高。 C4.5算法缺点：在构造树的过程中，需要对数 据集进行多次的顺序扫描和排序，因而导致算 法的低效。

c45算法的调研,包括：weka中的实例,算法研讨问题,算法原理,weka代码展示等。

决策树算法发展二级存储: 针对不能完全放入内存的数据集，在确保分类器算法效能的前提下，要做到数据 集扫描遍数的极小化。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, R Ramakrishnan, V Ganti - VLDB, 1998)实现了多种具体的决策树构

建方法，适用于大规模数据集的处理。其他基于二级存储设备的算法还有SLIQ ( 《SLIQ: A fast scalable classifier 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 tree classifier that integrates building and pruning》R Rastogi, K Shim - VLDB, 1998 - cs.sfu.ca )等。 斜决策树： 斜决策树适用于处理连续型数据，决策准则使用属性的线性组合。采用属性的线 性组合策略的一个典型的决策树分类器是OC1(《A system for induction of oblique decision trees》SK Murthy, S Kasif, S Salzberg - arXiv preprint cs/9408103, 1994 http://) )。 集成方法：装袋法和推举法。(《Popular ensemble methods: An empirical study》 R Maclin, D Opitz - arXiv preprint arXiv:1106.0257, 2011 - http://

c45算法的调研,包括：weka中的实例,算法研讨问题,算法原理,weka代码展示等。

算法流程：1)选择节点分裂属性 2)建立新节点，划分数据集 3)判断节点是否到生长停止条件， 如果是，终止生长，如果不是，转到 1)

问题：1)选择哪个属性进行节点分裂？ 2)何时停止树生长？ 3)怎么处理连续型属性？ 4)怎么处理缺失值？ 5)怎么处理过拟合问题？

c45算法的调研,包括：weka中的实例,算法研讨问题,算法原理,weka代码展示等。

c45算法的调研,包括：weka中的实例,算法研讨问题,算法原理,weka代码展示等。

选择节点分裂属性的问题 熵(Entropy):我们把一个事件的不确定程度叫做 “熵”,熵越大表明这个事件的结果越难以预测， 同时事件的发生将给我们带来越多的信息。 增益(Information Gain):在信息增益中，衡量标准是看特征 能够为分类系统带来多少信息，带来的信息越多，该特征越重 要。对一个特征而言，系统有它和没它时信息量将发生变化， 而前后信息量的差值就是这个特征给系统带来的信息量。所谓 信息量，就是熵。系统原先的熵是H(X),在条件Y已知的情况下 系统的熵(条件熵)为H(X|Y),信息增益就是这两个熵的差值。

c45算法的调研,包括：weka中的实例,算法研讨问题,算法原理,weka代码展示等。

outlook sunny sunny overcast rainy rainy rainy overcast sunny sunny rainy sunny overcast overcast rainy

temperature hot hot hot mild cool cool cool mild cool mild mild mild hot mild

humidity high high high high normal normal normal high normal normal normal high normal high FALSE TRUE FALSE FALSE FALSE TRUE TRUE FALSE FALSE FALSE TRUE TRUE FALSE TRUE

windy no no yes yes yes no yes no yes yes yes yes yes no

play

只看最后一列我们得到打球的概率是9/14,不打球的概率是5/14。因此在没有任 何先验信息的情况下，系统的熵(不确定性)为：

c45算法的调研,包括：weka中的实例,算法研讨问题,算法原理,weka代码展示等。

outlook yes nosunn y overc ast rainy 2 4 3 3 0 2

temperature yes nohot mild cool 2 4 3 2 2 1 high

humidity yes no3 6 4 1 FALS E TRUE

windy yes no6 3 2 3

play yes no9 5

norm al

如果选outlook作为决策树的根节点，(7)式中的Y为集合{sunny、overcast、 rainy},此时的条件熵为

即选择outlook作为决策树的根节点时，信息增益为0.94-0.693=0.247,然后计算 outlook属性的熵，得增益比。同样方法计算当选择temperature、humidity、 windy作为根节点时系统的信息增益和属性熵，选择增益比最大的作为最终的根 节点。

c45算法的调研,包括：weka中的实例,算法研讨问题,算法原理,weka代码展示等。

选择节点分裂属性的问题 ID3算法：使用信息增益作为选择节点分

裂属性 的指标。增益准则的一个缺陷是它偏向于选择具 有更多取值的属性作为节点分裂属性。 C4.5算法：使用信息增益率作为选择节点分裂属 性的指标，克服了ID3算法的缺点。

增益比(Gain ratio):增益/属性熵

c45算法的调研,包括：weka中的实例,算法研讨问题,算法原理,weka代码展示等。

树停止生长条件1)节点内的数据已经完全属于同一类别。 2)节点内测数据样本数低于某一阈值。 3)所有属性都已经被分裂过。

c45算法的调研,包括：weka中的实例,算法研讨问题,算法原理,weka代码展示等。

处理连续型数据 ID3算法：不能处理连续型数据，只能处 理离散型数据。 C4.5算法：以二值离散的方式处理连续型 数据。二值离散：对连续型属性进行排序，得到多个候选阈值，选取产生最大信息 增益的阈值作为分裂阈值。

Temperature: 40 48 60Play Tennis:

72

80

90

No No Yes Yes Yes Yes

《On the handling of continuous-valued attributes in decision tree generation》 UM Fayyad, KB Irani - Machine learning, 1992 - Springer 《Multi-interval discretization of continuous-valued attributes for classification learning》 U Fayyad, K Irani - 1993 - trs-new.jpl.nasa.gov

c45算法的调研,包括：weka中的实例,算法研讨问题,算法原理,weka代码展示等。

处理缺失值 ID3算法：不能处理缺失值。 C4.5算法：可以处理缺失值。《Unknown attribute values in induction.》 JR Quinlan - ML, 1989 - Citeseer 三种情况： 1)在具有缺失值的属性上如何计算信息增益率？ 解决方案： a) 忽略该类样本。 b) 选择常用值或均值填充。 c ) 依据缺失比例，折算信息增益/信息增益率。 d) 对缺失值赋予独特的值，参与训练。 2)具有缺失值的样本在进行数据分裂时，分配给哪个子数据集？ 解决方案： a) 忽略该类样本。 b) 选择常用值或均值填充。 c ) 根据其他非缺失属性的比例，分配到子数据集中。 d) 为缺失值建立单独分支。 f) 确定最可能的取值，按比例仅分配给一个子数据集。 3)对新样本进行分类时，缺失值导致样本到达叶子节点，怎么处理？ 解决方案： a) 有缺失值单独分支，走单独分支。 b) 走最常见的值的分支。 c ) 确定最可能取值，走相应分支。 d) 走所有分支，根据不同输出结果的概率进行组合。 f) 不进行分类，直接赋给最有可能的值。

c45算法的调研,包括：weka中的实例,算法研讨问题,算法原理,weka代码展示等。

过拟合问题 过拟合：有监督的算法需要考虑泛化能力，在有限样本的 条件下，决策树超过一定规模后，训练错误率减小，但测 试错误率会增加。 剪枝：控制决策树规模的方法称为剪枝，一种是先剪枝， 一种是后剪枝。所谓先剪枝，实际上是控制决策树的生长； 后剪枝是指，对完全生成的决策树进行修剪。 先剪枝： 1) 数据划分法。划分数据成训练样本和测试样本，使用用训练 样本进行训练，使用测试样本进行树生长检验。 2) 阈值法。当某节点的信息增益小于某阈值时，停止树生长。 3) 信息增益的统计显著性分析。从已有

节点获得的所有信息增 益统计其分布，如果继续生长得到的信息增 益与该分布相比 不显著，则停止树的生长。 优点：简单直接； 缺点：对于不回溯的贪婪算法，缺乏后效性考虑，可能导致树 提前停止。