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