python决策树之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个⼦数据集，|Sj|表⽰第j个⼦数据集中样本数量，|S|表⽰划分之前数据集中样本总数量。 激光扫描显微镜 通过属性A分裂之后样本集的信息增益：
信息增益的详细计算⽅法，可以参考博客“”中信息增益的计算。
通过属性A分裂之后样本集的信息增益率：
通过C4.5算法构造决策树时，信息增益率最⼤的属性即为当前节点的分裂属性，随着递归计算，被计算的属性的信息增益率会变得越来越⼩，到后期则选择相对⽐较⼤的信息增益率的属性作为分裂属性。
3. 连续型属性的离散化处理
当属性类型为离散型，⽆须对数据进⾏离散化处理；当属性类型为连续型，则需要对数据进⾏离散化处理。C4.5算法针对连续属性的离散化处理，核⼼思想：将属性A的N个属性值按照升序排列；通过⼆分法将属性A的所有属性值分成两部分（共有N-1种划分⽅法，⼆分的阈值为相邻两个属性值的中间值）；计算每种划分⽅法对应的信息增益，选取信息增益最⼤的划分⽅法的阈值作为属性A⼆分的阈值。详细流程如下：
（1）将节点Node上的所有数据样本按照连续型属性A的具体取值，由⼩到⼤进⾏排列，得到属性A的属性值取值序
列(xA1,...,xAN)。
（2）在序列(xA1,...,xAN)中共有N-1种⼆分⽅法，即共产⽣N-1个分隔阈值。对于第i种⼆分⽅法，其⼆分阈
值θi=xAi+xAi+12。它将该节点上的数据集划分为2个⼦数据集(xA1,...,xAi)(xAi+1,...,xAN)。计算此种⼆分结果下的信息增益。（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 Pruning)剪枝法。
对于⼀个叶⼦节点，它覆盖了n个样本，其中有e个错误，那么该叶⼦节点的错误率为(e+0.5)/n，其中0.5为惩罚因⼦（惩罚因⼦⼀般取值为0.5）。
对于⼀棵⼦树，它有L个叶⼦节点，那么该⼦树的误判率为：
其中，ei表⽰⼦树第i个叶⼦节点错误分类的样本数量，ni表⽰表⽰⼦树第i个叶⼦节点中样本的总数量。
假设⼀棵⼦树错误分类⼀个样本取值为1，正确分类⼀个样本取值为0，那么⼦树的误判次数可以认为是⼀个伯努利分布，因此可以得到该⼦树误判次数的均值和标准差：
德国哈芬把⼦树替换成叶⼦节点后，该叶⼦节点的误判率为：
其中，e′=∑Li=1ei，n′=∑Li=1ni。
同时，该叶⼦结点的误判次数也是⼀个伯努利分布，因此该叶⼦节点误判次数的均值为：
美国阳光地带
剪枝的条件为：
满⾜剪枝条件时，则将所得叶⼦节点替换该⼦树，即为剪枝操作。
5. 缺失属性值的处理
训练样本集中有可能会出现⼀些样本缺失了⼀些属性值，待分类样本中也会出现这样的情况。当遇到这样的样本集时该如何处理呢？含有缺失属性的样本集会⼀般会导致三个问题：
（１）在构建决策树时，每⼀个分裂属性的选取是由训练样本集中所有属性的信息増益率来决定的。⽽在此阶段，如果训练样本集中有些样本缺少⼀部分属性，此时该如何计算该属性的信息増益率；
（２）当已经选择某属性作为分裂属性时，样本集应该根据该属性的值来进⾏分⽀，但对于那些该属性的值为未知的样本，应该将它分⽀到哪⼀棵⼦树上；
（３）在决策树已经构建完成后，如果待分类样本中有些属性值缺失，则该样本的分类过程如何进⾏。
arcpad
针对上述因缺失属性值引起的三个问题，C4.5算法有多种解决⽅案。
⾯对问题⼀，在计算各属性的信息増益率时，若某些样本的属性值未知，那么可以这样处理：计算
某属性的信息増益率时忽略掉缺失了此属性的样本；或者通过此属性的样本中出现频率最⾼的属性值，賦值给缺失了此属性的样本。
⾯对问题⼆，假设属性Ａ已被选择作为决策树中的⼀个分⽀节点，在对样本集进⾏分⽀的时候，对于那些属性Ａ的值未知的样本，可以送样处理：不处理那些属性Ａ未知的样本，即简单的忽略它们；或者根据属性Ａ的其他样本的取值，来对未知样本进⾏赋值；或者为缺失属性Ａ的样本单独创建⼀个分⽀，不过这种⽅式得到的决策树模型结点数显然要増加，使模型更加复杂了。
⾯对问题三，根据⼰经⽣成的决策树模型，对⼀个待分类的样本进⾏分类时，若此样本的属性Ａ的值未知，可以这样处理：待分类样本在到达属性Ａ的分⽀结点时即可结束分类过程，此样本所属类别为属性Ａ的⼦树中概率最⼤的类别；或者把待分类样本的属性Ａ赋予⼀个最常见的值，然后继续分类过程。
6. C4.5算法流程
7. C4.5算法优缺点分析
优点：
（1）通过信息增益率选择分裂属性，克服了ID3算法中通过信息增益倾向于选择拥有多个属性值的属性作为分裂属性的不⾜；
（2）能够处理离散型和连续型的属性类型，即将连续型的属性进⾏离散化处理；
（3）构造决策树之后进⾏剪枝操作；
（4）能够处理具有缺失属性值的训练数据。
韩素音缺点：
（1）算法的计算效率较低，特别是针对含有连续属性值的训练样本时表现的尤为突出。
（2）算法在选择分裂属性时没有考虑到条件属性间的相关性，只计算数据集中每⼀个条件属性与决策属性之间的期望信息，有可能影响到属性选择的正确性。
以上就是本⽂的全部内容，希望对⼤家的学习有所帮助，也希望⼤家多多⽀持。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议