C4.5决策树

前言

C4.5决策树是ID3决策树的改进版本, 总体流程跟ID3差不多, 只是改进了一些缺点

ID3决策树存在几个问题

‍

问题一: ID3信息增益偏好多叉树

ID3找的是信息增益最大的特征, 这种取向会使其偏好取值多的特征

举个例子, 身份证号这类唯一取值的特征, 如果按照它来划分, 那划分后每个子节点的信息熵都是0, 信息增益最大, 这显然是最优的划分, 但这种划分毫无意义

C4.5使用信息增益率来替代信息增益, 算法如下

‍

信息增益

首先还是算信息增益, 算法不变, 还是

$$
Gain(A) = Entropy(S) - Entropy(S|A)
$$

其中

$S$: 当前节点的样本集合
$A$: 某个特征
$S|A$: 按照特征A划分后的子节点样本集合
$Entropy(S)$: 样本集合S的熵
$Entropy(S|A)$: 样本集合S按照特征A划分后的子节点样本集合的熵

‍

分裂信息

然后计算分裂信息, 用于衡量特征本身的混乱度, 取值越多的特征, 分裂信息越大, 公式为

$$
SplitInfo(A) = -\sum_{i=1}^n \frac{|S_i|}{|S|} \log_2 \frac{|S_i|}{|S|}
$$

其中

$|S_i|$: 特征A取值为$i$的样本数
$|S|$: 总样本数

这其实就是熵的计算公式, 不过信息增益里算熵都是针对系统整体$Entropy(S)$或者特征划分后的子系统$Entropy(S|A)$来算, 而这里是针对特征本身的取值分布来算, 是衡量特征的混乱度而非系统的混乱度

‍

信息增益率

最后计算信息增益率, 公式为

$$
Gain_Ratio(A) = \frac{Gain(A)}{SplitInfo(A)}
$$

当特征取值过多时, 分裂信息$SplitInfo(A)$会很大, 导致信息增益率很小, 这就避免了ID3决策树偏好取值多的特征的问题

‍

问题二: ID3决策树只能处理离散特征

ID3决策树只能处理离散特征, 如果特征是连续的(比如年龄), 需要将其离散化(转为young, middle, old等离散类别)

C4.5决策树支持连续特征, 算法如下

对连续特征进行排序, 记为$v_1, v_2, …, v_n$
以每个$v_i$作为划分点, 将数据划分为两部分: 小于等于$v_i$的一部分, 大于$v_i$的一部分, 计算该划分点的信息增益
选择信息增益最大的划分点作为该特征的最佳划分点, 将该连续特征转为二元离散特征(小于等于最优划分点, 大于最优划分点)

注意这里是算信息增益, 不是信息增益率, 原因很简单, 因为划分点只有两个取值, 不存在偏好多叉树的问题

‍

问题三: ID3决策树无法处理缺失值

缺失值处理分为训练时遇到缺失值和预测时遇到缺失值

‍

训练时遇到缺失值

假设有100个样本, 其中80个样本有特征A, 剩下20个样本的特征A为空

计算信息增益率时, 只用80个有特征A的样本来计算
不过最终算出的信息增益率, 需要乘以$\frac{80}{100}$, 以此来反映缺失值的影响

其余流程不变

‍

预测时遇到缺失值

假设训练时年龄字段的最优划分点是30岁, 假设预测时有一个新样本, 年龄字段为空

把样本丢入<=30岁和>30岁两个分支
分别计算两个分支的预测结果, 假设为买和不买
每个分支有各自的权重, 也就是训练集流经该分支的样本数, 假设<=30岁分支有40个样本, >30岁分支有60个样本, 则权重分别为0.4和0.6
最终预测结果为加权结果, 也就是0.4买, 0.6不买, 取值大的为最终预测结果, 即为不买

‍

问题四: ID3决策树容易过拟合

过拟合

过拟合的核心问题是模型把训练集里的噪声(偶然规律)当成了”通用规律”, 给学了进去, 导致在训练集上表现很好, 但在测试集上表现很差

对于决策树来说, 过拟合的典型表现是”树长得太复杂”: 分支极多, 叶子节点极多

举个通俗例子

假设用”年龄、收入、是否学生”预测”是否买电脑”, 训练数据里恰好有1个”29岁、高收入、非学生” 的人没买电脑

如果树长得太细, 会专门为这个样本开一个分支(“年龄≤29且收入高且非学生→不买”)

但这个规律其实是偶然的(可能这个人当天只是不想买)

遇到另一个”29岁、高收入、非学生” 的新样本时, 就会错误预测”不买”——这就是过拟合

‍

后剪枝

剪枝分为预剪枝和后剪枝

预剪枝: 在生成树的过程中, 每次划分前, 先评估划分后的效果, 如果划分后效果变差, 则不划分
后剪枝: 在生成完整棵树后, 再对树进行剪枝

C4.5使用后剪枝, 从倒数第二层开始, 逐层向上遍历每个节点, 对每个节点进行如下操作

‍

场景假设

假设有一个节点S, 他有两个子节点S1, S2

S: 100个样本
S1: 该节点预测为买电脑, 30个样本, 其中5个预测错误
S2: 该节点预测为不买电脑, 70个样本, 其中35个预测错误

‍

计算剪枝前的总错误

首先了解下, C4.5的错误数有一套修正公式

$CorrectedError = 实际错误数 + 2$

接着我们来算下剪枝前S节点的总错误数

S1的修正错误数为$5 + 2 = 7$
S2的修正错误数为$35 + 2 = 37$
剪枝前S节点的总错误数为$7 + 37 = 44$

‍

计算剪枝后的总错误

剪枝就是剪掉S1和S2, 让S变成叶子节点, 叶子节点的预测结果是样本数最多的类别

因为S1里25个买电脑, S2里35个买电脑, 所以S节点里一共60个买电脑, 40个不买电脑, 所以剪枝后S节点的预测结果是买电脑

预测错误数是40, 修正错误数为$40 + 2 = 42$

‍

比较剪枝前后的错误数

剪枝前的修正错误数是44, 剪枝后的修正错误数是42, 剪枝后的修正错误数更少, 所以进行剪枝

以此类推从倒数第二层不断向上剪枝

‍

为什么修正加2

直观来解释, 加2能惩罚小样本, 小样本往往是噪声, 修正后小样本的修正错误数大幅度增加, 更容易被剪掉

而且这里的2并不是拍脑袋定的数字, 而是用卡方分布计算出95%置信度的情况下, 一个节点的错误数最多可能波动多少, 最终工程简化为2这个数字

‍

总结

C4.5决策树是ID3决策树的改进版本, 主要改进了以下几点

使用信息增益率来替代信息增益, 避免偏好多叉树
支持连续特征, 通过寻找最佳划分点将连续特征转为离散特征
支持缺失值, 训练时忽略缺失值样本, 预测时加权多个分支结果
使用后剪枝来避免过拟合

总体并没有对ID3的流程做什么大改动

‍