基于信息熵的决策树（C4.5）算法：分裂属性选择、信息增益率计算与连续属性离散化
字数 3384 2025-12-23 13:12:26

基于信息熵的决策树（C4.5）算法：分裂属性选择、信息增益率计算与连续属性离散化

题目描述

决策树是一种经典的监督学习算法，用于分类和回归任务。ID3算法是决策树的一个早期代表，它使用信息增益作为分裂属性的选择标准。然而，ID3存在两个主要局限：1. 对取值数目多的属性有偏好（易产生过细划分）；2. 无法直接处理连续型属性。C4.5算法是ID3的改进，它通过引入信息增益率 来克服对多值属性的偏好，并提出了将连续属性离散化 的方法。本题将详细讲解C4.5算法如何计算信息增益率、如何选择最佳分裂属性，以及如何对连续属性进行二分处理。

解题过程

第一步：回顾信息熵与信息增益（ID3的基础）

  1. 信息熵：度量样本集合纯度的指标。对于一个包含K个类别的样本集合D，其信息熵定义为：
    \(Ent(D) = -\sum_{k=1}^{K} p_k \log_2 p_k\)
    其中 \(p_k\) 是D中第k类样本的比例。\(Ent(D)\) 越小，D的纯度越高。

  2. 信息增益：使用某个属性a对集合D进行划分后，所带来的纯度提升。假设属性a有V个可能的取值，将D划分为V个子集 \(\{D^1, D^2, ..., D^V\}\)。则信息增益为：
    \(Gain(D, a) = Ent(D) - \sum_{v=1}^{V} \frac{|D^v|}{|D|} Ent(D^v)\)
    信息增益越大，意味着用属性a划分后，纯度提升越多。ID3直接选择信息增益最大的属性作为当前节点的分裂属性。

第二步：分析ID3的局限性与C4.5的改进思路

  1. 问题1：对多值属性的偏好

    • 原因：如果一个属性的取值数目V特别多（例如“编号”或“身份证号”），那么每个子集 \(D^v\) 很可能只包含一个样本，其 \(Ent(D^v) = 0\)。这会导致信息增益 \(Gain(D, a)\) 非常大，接近 \(Ent(D)\)。
    • 后果：算法会倾向于选择这种对分类无实际意义、只是过拟合数据的属性，生成庞大且泛化能力差的树。
    • C4.5的解决方案：引入信息增益率。它在信息增益的基础上，除以一个关于属性a自身取值的“固有值”或“分裂信息”，用以惩罚取值多的属性。这个“固有值”称为属性a的固有值 或分裂信息。

  2. 问题2：无法处理连续属性

    • ID3只能处理离散（分类）属性。
    • C4.5的解决方案：采用二分法 将连续属性离散化。将属性a的所有取值从小到大排序，取相邻两个值的中间点作为候选分割点，然后像离散属性一样评估每个分割点，选择最优的一个。

第三步：C4.5核心计算——信息增益率

  1. 计算属性a的固有值：
    \(IV(a) = -\sum_{v=1}^{V} \frac{|D^v|}{|D|} \log_2 \frac{|D^v|}{|D|}\)

    • 这里的 \(IV(a)\) 衡量的是按照属性a划分后，各个子集大小的分布均匀程度。
    • 如果属性a的取值非常分散（每个子集大小差不多），\(IV(a)\) 会较大。
    • 如果属性a的取值高度倾斜（例如某个取值包含了绝大多数样本），\(IV(a)\) 会较小。

  2. 计算信息增益率：
    \(Gain\_ratio(D, a) = \frac{Gain(D, a)}{IV(a)}\)

    • 目的：用 \(IV(a)\) 对信息增益 \(Gain(D, a)\) 进行“归一化”或“惩罚”。
    • 效果：一个属性如果取值很多且分布均匀（导致 \(IV(a)\) 很大），即使它的信息增益 \(Gain(D, a)\) 不低，其信息增益率 \(Gain\_ratio\) 也会被拉低，从而降低了被选中的概率。
    • 注意：C4.5并非直接选择信息增益率最大的属性。它采用了一种启发式策略：先从候选属性中找出信息增益高于平均水平的那些属性，然后从这些属性中选择信息增益率最高的。这避免了在 \(IV(a)\) 非常小（导致增益率异常大）时产生的选择偏差。

第四步：C4.5对连续属性的处理——二分法

  1. 候选分割点生成：

    • 假设连续属性a在数据集D上共有m个不同的取值，将其从小到大排序为 \(\{a_1, a_2, ..., a_m\}\)。
    • 候选分割点集合T为相邻值的中点：\( T = \{ \frac{a_i + a_{i+1}}{2} | i=1,2,...,m-1 \}\)。

  2. 评估最佳分割点：

    • 对于每个候选分割点 \(t \in T\)，将数据集D划分为两个子集：
      • \(D_t^-\)：满足 \(a \le t\) 的样本集合。
      • \(D_t^+\)：满足 \(a > t\) 的样本集合。
    • 此时，可以将属性a在分割点t处视为一个二元离散属性，其取值为“≤t”和“>t”。
    • 计算使用这个二元属性进行划分的信息增益 \(Gain(D, a, t)\)：
      \(Gain(D, a, t) = Ent(D) - [\frac{|D_t^-|}{|D|}Ent(D_t^-) + \frac{|D_t^+|}{|D|}Ent(D_t^+)]\)
    • 选择使 \(Gain(D, a, t)\) 最大的分割点 \(t_{best}\) 作为属性a的最佳分割点。这个最大的增益值记为 \(Gain(D, a)\)，用于后续的信息增益率计算。

  3. 与离散属性统一处理：

    • 确定了最佳分割点 \(t_{best}\) 后，我们就“创造”了一个新的二元离散属性，用于当前节点的划分。
    • 在后续的子树构建中，这个连续属性在子节点上可以继续被划分，即在子节点的样本子集上，重新执行上述二分法寻找新的、更细的分割点。

第五步：C4.5算法的构建流程

  1. 输入：训练集D，属性集A，停止条件（如节点样本全属同一类、样本数小于阈值、无属性可用等）。
  2. 生成节点：
    • 若D中所有样本属于同一类C，则将当前节点标记为C类叶节点，返回。
    • 若属性集A为空，或D在所有属性上取值相同，则将当前节点标记为D中样本数最多的类叶节点，返回。
    • 若D中样本数小于预定阈值，则标记为D中样本数最多的类叶节点，返回。
  3. 选择最优分裂属性：
    • 对A中的每一个属性a（无论离散还是连续）：
      • 若a是离散属性，按第一步和第三步计算其信息增益 \(Gain(D, a)\) 和信息增益率 \(Gain\_ratio(D, a)\)。
      • 若a是连续属性，按第四步找到其最佳分割点 \(t_{best}\) 及对应的最大信息增益 \(Gain(D, a)\)，然后计算其信息增益率（此时的IV(a)是基于二元划分计算的）。
    • 找出所有属性中，信息增益高于平均增益的子集。
    • 从该子集中，选择信息增益率最大的属性 \(a_*\) 作为当前节点的分裂属性。
  4. 划分子集：
    • 若 \(a_*\) 是离散属性，则按每个取值生成分支，得到子集 \(D^v\)。
    • 若 \(a_*\) 是连续属性，则按最佳分割点 \(t_{best}\) 生成两个分支（≤ \(t_{best}\) 和 > \(t_{best}\)），得到子集 \(D_t^-\) 和 \(D_t^+\)。
  5. 递归建树：
    • 对每个分支（每个子集），以该子集为新的训练集，以 \(A \setminus \{a_*\}\) 为新的属性集（注意：对于连续属性， \(a_*\) 不会被移除，因为可以在子节点继续划分），递归调用步骤2-4，生成子树。
  6. 输出：以当前节点为根节点的决策树。

第六步：总结与评价

C4.5算法通过信息增益率有效缓解了对多值属性的偏好，通过二分法实现了对连续属性的直接处理，是决策树发展史上的一个重要里程碑。其生成的树模型可解释性强，且通常比ID3树的泛化能力更好。后续的决策树算法（如CART）和集成方法（如随机森林、梯度提升树）都从C4.5中汲取了思想。C4.5的缺点包括计算效率（尤其是对连续属性排序和寻找分割点）以及容易过拟合（通常需要进行剪枝）。

基于信息熵的决策树（C4.5）算法：分裂属性选择、信息增益率计算与连续属性离散化 题目描述 决策树是一种经典的监督学习算法，用于分类和回归任务。ID3算法是决策树的一个早期代表，它使用 信息增益 作为分裂属性的选择标准。然而，ID3存在两个主要局限：1. 对取值数目多的属性有偏好（易产生过细划分）；2. 无法直接处理连续型属性。C4.5算法是ID3的改进，它通过引入 信息增益率 来克服对多值属性的偏好，并提出了将 连续属性离散化 的方法。本题将详细讲解C4.5算法如何计算信息增益率、如何选择最佳分裂属性，以及如何对连续属性进行二分处理。 解题过程 第一步：回顾信息熵与信息增益（ID3的基础） 信息熵 ：度量样本集合纯度的指标。对于一个包含K个类别的样本集合D，其信息熵定义为： \( Ent(D) = -\sum_ {k=1}^{K} p_ k \log_ 2 p_ k \) 其中 \( p_ k \) 是D中第k类样本的比例。\( Ent(D) \) 越小，D的纯度越高。 信息增益 ：使用某个属性a对集合D进行划分后，所带来的 纯度提升 。假设属性a有V个可能的取值，将D划分为V个子集 \(\{D^1, D^2, ..., D^V\}\)。则信息增益为： \( Gain(D, a) = Ent(D) - \sum_ {v=1}^{V} \frac{|D^v|}{|D|} Ent(D^v) \) 信息增益越大，意味着用属性a划分后，纯度提升越多。ID3直接选择信息增益最大的属性作为当前节点的分裂属性。 第二步：分析ID3的局限性与C4.5的改进思路 问题1：对多值属性的偏好 原因：如果一个属性的取值数目V特别多（例如“编号”或“身份证号”），那么每个子集 \( D^v \) 很可能只包含一个样本，其 \( Ent(D^v) = 0 \)。这会导致信息增益 \( Gain(D, a) \) 非常大，接近 \( Ent(D) \)。 后果：算法会倾向于选择这种对分类无实际意义、只是过拟合数据的属性，生成庞大且泛化能力差的树。 C4.5的解决方案 ：引入 信息增益率 。它在信息增益的基础上，除以一个关于属性a自身取值的“固有值”或“分裂信息”，用以惩罚取值多的属性。这个“固有值”称为 属性a的固有值 或 分裂信息 。 问题2：无法处理连续属性 ID3只能处理离散（分类）属性。 C4.5的解决方案 ：采用 二分法 将连续属性离散化。将属性a的所有取值从小到大排序，取相邻两个值的中间点作为候选分割点，然后像离散属性一样评估每个分割点，选择最优的一个。 第三步：C4.5核心计算——信息增益率 计算属性a的固有值 ： \( IV(a) = -\sum_ {v=1}^{V} \frac{|D^v|}{|D|} \log_ 2 \frac{|D^v|}{|D|} \) 这里的 \( IV(a) \) 衡量的是 按照属性a划分后，各个子集大小的分布均匀程度 。 如果属性a的取值非常分散（每个子集大小差不多），\( IV(a) \) 会较大。 如果属性a的取值高度倾斜（例如某个取值包含了绝大多数样本），\( IV(a) \) 会较小。 计算信息增益率 ： \( Gain\_ratio(D, a) = \frac{Gain(D, a)}{IV(a)} \) 目的 ：用 \( IV(a) \) 对信息增益 \( Gain(D, a) \) 进行“归一化”或“惩罚”。 效果 ：一个属性如果取值很多且分布均匀（导致 \( IV(a) \) 很大），即使它的信息增益 \( Gain(D, a) \) 不低，其信息增益率 \( Gain\_ratio \) 也会被拉低，从而降低了被选中的概率。 注意 ：C4.5并非直接选择信息增益率最大的属性。它采用了一种 启发式策略 ：先从候选属性中找出信息增益 高于平均水平 的那些属性，然后 从这些属性中 选择信息增益率 最高 的。这避免了在 \( IV(a) \) 非常小（导致增益率异常大）时产生的选择偏差。 第四步：C4.5对连续属性的处理——二分法 候选分割点生成 ： 假设连续属性a在数据集D上共有m个不同的取值，将其从小到大排序为 \(\{a_ 1, a_ 2, ..., a_ m\}\)。 候选分割点集合T为相邻值的中点：\( T = \{ \frac{a_ i + a_ {i+1}}{2} | i=1,2,...,m-1 \}\)。 评估最佳分割点 ： 对于每个候选分割点 \( t \in T \)，将数据集D划分为两个子集： \( D_ t^- \)：满足 \( a \le t \) 的样本集合。 \( D_ t^+ \)：满足 \( a > t \) 的样本集合。 此时，可以将属性a在分割点t处视为一个 二元离散属性 ，其取值为“≤t”和“>t”。 计算使用这个二元属性进行划分的 信息增益 \( Gain(D, a, t) \)： \( Gain(D, a, t) = Ent(D) - [ \frac{|D_ t^-|}{|D|}Ent(D_ t^-) + \frac{|D_ t^+|}{|D|}Ent(D_ t^+) ] \) 选择使 \( Gain(D, a, t) \) 最大的分割点 \( t_ {best} \) 作为属性a的最佳分割点。这个最大的增益值记为 \( Gain(D, a) \)，用于后续的信息增益率计算。 与离散属性统一处理 ： 确定了最佳分割点 \( t_ {best} \) 后，我们就“创造”了一个新的二元离散属性，用于当前节点的划分。 在后续的子树构建中，这个连续属性在子节点上 可以继续被划分 ，即在子节点的样本子集上，重新执行上述二分法寻找新的、更细的分割点。 第五步：C4.5算法的构建流程 输入 ：训练集D，属性集A，停止条件（如节点样本全属同一类、样本数小于阈值、无属性可用等）。 生成节点 ： 若D中所有样本属于同一类C，则将当前节点标记为C类叶节点，返回。 若属性集A为空，或D在所有属性上取值相同，则将当前节点标记为D中样本数最多的类叶节点，返回。 若D中样本数小于预定阈值，则标记为D中样本数最多的类叶节点，返回。 选择最优分裂属性 ： 对A中的 每一个属性a （无论离散还是连续）： 若a是离散属性，按第一步和第三步计算其信息增益 \( Gain(D, a) \) 和信息增益率 \( Gain\_ratio(D, a) \)。 若a是连续属性，按第四步找到其最佳分割点 \( t_ {best} \) 及对应的最大信息增益 \( Gain(D, a) \)，然后计算其信息增益率（此时的IV(a)是基于二元划分计算的）。 找出所有属性中，信息增益 高于平均增益 的子集。 从该子集中，选择 信息增益率最大 的属性 \( a_* \) 作为当前节点的分裂属性。 划分子集 ： 若 \( a_* \) 是离散属性，则按每个取值生成分支，得到子集 \( D^v \)。 若 \( a_* \) 是连续属性，则按最佳分割点 \( t_ {best} \) 生成两个分支（≤ \( t_ {best} \) 和 > \( t_ {best} \)），得到子集 \( D_ t^- \) 和 \( D_ t^+ \)。 递归建树 ： 对每个分支（每个子集），以该子集为新的训练集，以 \( A \setminus \{a_ \} \) 为新的属性集（ 注意 ：对于连续属性， \( a_ \) 不会被移除，因为可以在子节点继续划分），递归调用步骤2-4，生成子树。 输出 ：以当前节点为根节点的决策树。 第六步：总结与评价 C4.5算法通过 信息增益率 有效缓解了对多值属性的偏好，通过 二分法 实现了对连续属性的直接处理，是决策树发展史上的一个重要里程碑。其生成的树模型可解释性强，且通常比ID3树的泛化能力更好。后续的决策树算法（如CART）和集成方法（如随机森林、梯度提升树）都从C4.5中汲取了思想。C4.5的缺点包括计算效率（尤其是对连续属性排序和寻找分割点）以及容易过拟合（通常需要进行剪枝）。