决策树之C4.5算法详解.pdf

决策树之C4.5算法详解 决策树之C4.5算法详解 主要内容 C4.5算法简介 分裂属性的选择——信息增益 连续型属性的离散化处理 剪枝——PEP(Pessimistic Error Pruning)剪枝法 缺失属性值的处理 C4.5算法流程 C4.5算法优缺点分析 1. C4.5算法简介   C4.5算法是⽤于⽣成决策树的⼀种经典算法，是ID3算法的⼀种延伸和优化。C4.5算法对ID3算法主要做了⼀下⼏点改进 ：    （1）通过信息增益 选择分裂属性，克服了ID3算法中通过信息增益倾向于选择拥有多个属性值的属性作为分裂属性的不⾜ ；    （2）能够处理离散型和连续型的属性类型，即将连续型的属性进⾏离散化处理 ；    （3）构造决策树之后进⾏剪枝操作 ；    （4）能够处理具有缺失属性值的训练数据。 2. 分裂属性的选择——信息增益   分裂属性选择的评判标准是决策树算法之间的根本区别。区别于ID3算法通过信息增益选择分裂属性，C4.5算法通过信息增益 选择分 裂属性。   属性A的 “分裂信息”(split information) ： 其中，训练数据集S通过属性A的属性值划分为m个⼦数据集， 表⽰第j 个⼦数据集中样本数量， 表⽰划分之前数据集中样本总数量。   通过属性A分裂之后样本集的信息增益 ： 信息增益的详细计算⽅法，可以参考博客 中信息增益的计算。   通过属性A分裂之后样本集的信息增益 ：   通过C4.5算法构造决策树时，信息增益 最⼤的属性即为当前节点的分裂属性，随着递归计算，被计算的属性的信息增益 会变得越 来越⼩，到后期则选择相对⽐较⼤的信息增益 的属性作为分裂属性。 3. 连续型属性的离散化处理   当属性类型为离散型，⽆须对数据进⾏离散化处理 ；当属性类型为连续型，则需要对数据进⾏离散化处理。C4.5算法针对连续属性的 离散化处理，核⼼思想 ：将属性A的N个属性值按照升序排列 ；通过⼆分法将属性A的所有属性值分成两部分 （共有N- 1种划分⽅法，⼆分的 阈值为相邻两个属性值的中间值） ；计算每种划分⽅法对应的信息增益，选取信息增益最⼤的划分⽅法的阈值作为属性A⼆分的阈值。详细 流程如下 ： （1）将节点Node上的所有数据样本按照连续型属性A的具体取值，由⼩到⼤进⾏排列，得到属性A的属性值取值序列。 （2）在序列中共有N- 1种⼆分⽅法，即共产⽣N- 1个分隔阈值。对于第i种⼆分⽅法，其⼆分阈值。它将该节点上的数据集划分为2个⼦数据 集。计算此种⼆分结果下的信息增益。 （3）分别计算N- 1种⼆分结果下的信息增益，选取信息增益最⼤的⼆分结果作为对属性A的划分结果，并记录此时的⼆分阈值。 4. 剪枝——PEP(Pessimistic Error Pruning)剪枝法   由于决策树的建⽴完全是依赖于训练样本，因此该决策树对训练样本能够产⽣完美的拟合效果。但这样的决策树对于测试样本来说过于 庞⼤⽽复杂，可能产⽣较⾼的分类错误 。这种现象就称为过拟合。因此需要将复杂的决策树进⾏简化，即去掉⼀些节点解决过拟合问题， 这个过程称为剪枝。   剪枝⽅法分为预剪枝和后剪枝两⼤类。预剪枝是在构建决策树的过程中，提前终⽌决策树的⽣长，从⽽避免过多的节点产⽣。预剪枝⽅ 法虽然简单但实⽤性不强，因为很难精确的判断何时终⽌树的⽣长。后剪枝是在决策树构建完成之后，对那些置信度不达标的节点⼦树⽤叶 ⼦结点代替，该叶⼦结点的类标号⽤该节点⼦树中频 最⾼的类标记。后剪枝⽅法⼜分为两种，⼀类是把训练数据集分成树的⽣长集和剪枝 集 ；另⼀类算法则是使⽤同⼀数据集进⾏决策树⽣长和剪枝。常见的后剪枝⽅法有CCP(Cost Complexity Pruning)、REP(Reduced Error Pruning)、PEP(Pessimistic Error Pruning)、MEP(Minimum Error Pruning)。   C4.5算法采⽤PEP(Pessimistic Error Pruning)剪枝法。PEP剪枝法由Quinlan提出，是⼀种 ⾃上⽽下的剪枝法，根据剪枝前后的错 误 来判定是否进⾏⼦树的修剪，因此不需要单独的剪枝数据集。接下来详细介绍PEP(Pessimistic Error Prun