决策树（2）C4-5

发表于 2022-02-25 更新于 2023-04-22 分类于算法，机器学习，决策树阅读次数：本文字数： 1.3k 阅读时长 ≈ 2 分钟

一、C4.5

C4.5 算法最大的特点是克服了 ID3 对特征数目的偏重这一缺点，引入信息增益率来作为分类标准。

C4.5 相对于 ID3 的缺点对应有以下改进方式：

引入悲观剪枝策略进行后剪枝；
引入信息增益率作为划分标准；
将连续特征离散化，假设 n 个样本的连续特征 A 有 m 个取值，C4.5 将其排序并取相邻两样本值的平均数共 m-1 个划分点，分别计算以该划分点作为二元分类点时的信息增益，并选择信息增益最大的点作为该连续特征的二元离散分类点；
对于缺失值的处理可以分为两个子问题：
问题一：在特征值缺失的情况下进行划分特征的选择？（即如何计算特征的信息增益率）
- C4.5 的做法是：对于具有缺失值特征，用没有缺失的样本子集所占比重来折算；
问题二：选定该划分特征，对于缺失该特征值的样本如何处理？（即到底把这个样本划分到哪个结点里）
- C4.5 的做法是：将样本同时划分到所有子节点，不过要调整样本的权重值，其实也就是以不同概率划分到不同节点中。

利用信息增益率可以克服信息增益的缺点，其公式为:

\[ \operatorname{Gain}_{\text {ratio }}(D, A) =\frac{\operatorname{Gain}(D, A)}{H_{A}(D)} \\ \]

\[ H_{A}(D)=-\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} \log _{2} \frac{\left|D_{i}\right|}{|D|} \]

信息增益率对可取值较少的特征有所偏好（分母越小，整体越大），因此 C4.5 并不是直接用增益率最大的特征进行划分，而是使用一个启发式方法：先从候选划分特征中找到信息增益高于平均值的特征，再从中选择增益率最高的。

为什么要剪枝：过拟合的树在泛化能力的表现非常差。

预剪枝和悲观剪枝

在节点划分前来确定是否继续增长，及早停止增长的主要方法有：

预剪枝不仅可以降低过拟合的风险而且还可以减少训练时间，但另一方面它是基于“贪心”策略，会带来欠拟合风险。

在已经生成的决策树上进行剪枝，从而得到简化版的剪枝决策树。

C4.5 采用的悲观剪枝方法，用递归的方式从低往上针对每一个非叶子节点，评估用一个最佳叶子节点去代替这课子树是否有益。如果剪枝后与剪枝前相比其错误率是保持或者下降，则这棵子树就可以被替换掉。C4.5 通过训练数据集上的错误分类数量来估算未知样本上的错误率。

后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但同时其训练时间会大的多。

剪枝策略可以再优化；
C4.5 用的是多叉树，用二叉树效率更高；
C4.5 只能用于分类；
C4.5 使用的熵模型拥有大量耗时的对数运算，连续值还有排序运算；
C4.5 在构造树的过程中，对数值属性值需要按照其大小进行排序，从中选择一个分割点，所以只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时，程序无法运行。