本站原创文章，转载请说明来自《老饼讲解-机器学习》www.bbbdata.com
C4.5算法也是经典的决策树算法之一，它是ID3算法的延续，是对ID3算法的补充
本文讲解决策树C4.5算法的思想，是决策树模型相关知识的补充
通过本文，可以了解C4.5决策树是什么，以及它与ID3、CART决策树的区别
备注：本文需建立在CART决策树、ID3决策树的认识上再进行阅读，阅读时注意CART、ID3、C4.5的区别
本节先理解为什么有C4.5算法，及C4.5算法是什么
决策树C4.5算法简介
C4.5就是对ID3的补充，就是对ID3打补丁
因此，C4.5并不是一个新算法，而是对ID3添加的一系列补丁后得到的算法
由于C4.5算法是ID3算法的改进，
因此我们必须了解，ID3算法有什么缺点，才知道C4.5算法的重心在哪
ID3决策树的缺陷
ID3算法的缺陷主要有4个，如下：
1. 变量偏好多枚举值
2. ID3容易过拟合
3. ID3不支持连续变量
4. 不支持数据有缺失值
✍️如何理解“ID3选择变量偏好多枚举值”
ID3更偏好优先分叉枚举值多的变量
因为ID3用信息增益评估分叉质量，该评估函数会更偏好枚举值多的变量
例如：如果变量A有2个枚举，B有10个枚举，肯定就偏好B了，
因为B把节点分叉成10个子节点，而A只分成2个子节点，分成10个子节点的确定性肯定比2个会更强些
本节讲解C4.5算法具体是什么，和它具体如何改进ID3算法
C4.5算法-基于ID3的改进
C4.5算法主要就是改进上面所说的ID3算法的4个缺点, 它相当于给ID3打上补丁
要掌握C4.5算法，其实就是在ID3的基础上，掌握C4.5对ID3的4个缺点的改进
下面描述C4.5是如何改进ID3的四个缺点的
1.变量偏好纠正
变量偏好纠正：使用信息增益比
C4.5用信息增益比替代信息增益
即信息增益/变量的熵,对枚举值多的变量进行了一定的惩罚：
信息增益比：
分子就是ID3中的信息增益， 分母则是全体样本中变量v的熵
分母符号说明：
: 全体样本（划重点，是全体样本）变量v的枚举个数
: 全体样本个数
：全体样本变量v第k个枚举值的样本个数
2.过拟合处理
过拟合处理：添加剪枝
C4.5在ID3的基础上，加入了剪枝，来处理过拟合的问题
先定义整棵树的评估函数（每个叶子节点质量的加权和与叶子个数的惩罚项）：
然后自下而上，缩回式剪枝，
先判断叶子剪前和剪后的损失函数，如果能让损失函数变小，则剪
3.连续变量处理
C4.5对连续变量处理如下：
设有n个样本，排序，在变量相邻值中间切割（n-1个割点）
每个割点将变量割成两类，计算这n-1种切法，
哪种切法分成的两类得到的信息增益比更大，则取该切法
分叉时，则按该切法，进行二分叉
注：连续变量分叉后，后续还可以继续 使用该变量进行分叉
因此，与ID3不同，C4.5树的层数可能多于变量数
4.缺失值的处理
变量有缺失值时，有三个地方要处理，大概的思路如下：
1. 选择变量时，只用非缺失样本计算熵，
再乘以系数 非缺失量/总样本量。
2. 分派样本到子节点时，每个子节点都包含所有缺失值样本，
但需要加上权重，权重为该子节点的样本量(非缺失)占比
3. 评估时若有缺失值，则走所有子节点，多条路线并存，
最后把所有叶子节点的结果评估，
哪个叶子节点更可靠，就选哪个叶子节点
备注
缺失值的处理细节极为复杂，作者只能告诉你，忽略它是最好的作法
如果你一定要纠结，可以阅读《机器学习笔记（7）——C4.5决策树中的缺失值处理》
如果还纠结，直接读C4.5作者原文《Programs for Machine Learning》
笔者语
可以看到，C4.5就是对ID3的改进，而C4.5的很多处理则延伸到了CART上
例如剪枝、连续变量的处理等等，都被CART延用了~
因此，在理解ID3和CART之后，再看C4.5就非常容易理解了，它就相当于ID3与CART之间的过渡版本
而C4.5由于基于ID3进行打补丁，很多处理非常复杂 ，这些复杂处理就被CART摒弃了
最后，笔者也没有太多去纠结C4.5的每一个细节，干脆就跟CART一样，直接把C4.5复杂内容抛弃就算了
好了，以上就是决策树C4.5算法的全部内容了~
End