【机器学习】机器学习的基本分类-监督学习-决策树-C4.5 算法

C4.5 是由 Ross Quinlan 提出的决策树算法，是对 ID3 算法的改进版本。它在 ID3 的基础上，解决了以下问题：

1. 处理连续型数据：支持连续型特征，能够通过划分点将连续特征离散化。
2. 处理缺失值：能够在特征值缺失的情况下继续构建决策树。
3. 偏好多值特征的问题：采用信息增益比（Gain Ratio）替代信息增益，减少对多值特征的偏好。
4. 生成剪枝后的树：通过后剪枝技术，降低过拟合风险。

---

1. 核心改进

(1) 信息增益比

C4.5 使用**信息增益比（Gain Ratio）**代替 ID3 的信息增益来选择最优特征。

• 信息增益 IG(D, A)：

• 分裂信息 SI(A)：

其中：

• ：特征 AAA 的第 vvv 个取值的样本比例。

• 信息增益比 GR(D, A)：

分裂信息 SI(A) 是一种归一化因子，用于惩罚取值较多的特征，降低它们被优先选择的可能性。

---

(2) 连续型特征处理

• 对连续特征，C4.5 会尝试在特征值的每个分割点（例如两个样本值之间的中点）进行划分。
• 对每个划分点计算信息增益比，选择最佳划分点。

假设某连续特征 A 的值为 ，排序后尝试以下划分点：

划分点 

---

(3) 处理缺失值

对于缺失值，C4.5 使用以下策略：

1. 在计算信息增益比时，只考虑特征值非缺失的样本。
2. 当需要划分含有缺失值的样本时，将这些样本按概率分配到各个子节点。

---

(4) 剪枝

• C4.5 采用**后剪枝（Post-Pruning）**技术，通过校验数据集评估剪枝后的树是否提高性能。
• 剪枝的目标是降低过拟合风险，增强模型泛化能力。

---

2. C4.5 算法流程

1. 输入：训练数据集 D、特征集 A。
2. 递归构造树：
   1. 计算当前数据集 D 的信息熵 H(D)。
   2. 对每个特征 A ∈ A：
      • 若 A 为离散特征，计算信息增益比。
      • 若 A 为连续特征，尝试每个划分点，计算信息增益比。
   3. 选择信息增益比最大的特征 ，作为当前节点的分裂特征。
   4. 根据 的取值（或划分点）划分数据集 D。
   5. 对每个子数据集递归构造子树。
3. 剪枝：
   • 基于校验集对生成的决策树进行剪枝，移除不显著的分支。
4. 输出：剪枝后的决策树。

---

3. 示例

数据示例

假设有以下训练数据集：

天气	温度	湿度	风力	是否运动
晴天	30	高	弱	否
晴天	32	高	强	否
阴天	28	高	弱	是
雨天	24	正常	弱	是
雨天	20	正常	强	否

目标：构造决策树判断是否运动。

步骤

1. 计算根节点的熵：

   

2. 对每个特征计算信息增益比：

   • 天气（离散特征）：

     • 计算天气的条件熵 。
     • 计算信息增益比 。

   • 温度（连续特征）：

     • 尝试划分点：272727、303030、333333。
     • 对每个划分点计算信息增益比，选择最佳划分点。

   • 湿度、风力：

     • 按相同方法计算。

3. 选择信息增益比最大的特征作为分裂特征，生成子节点。

4. 对子节点递归分裂，直至满足停止条件（如样本类别纯度高或无特征可分）。

5. 后剪枝：

   • 对生成的树在校验集上进行性能评估，剪去对性能贡献较小的分支。

---

4. 算法特点

优点

1. 支持离散和连续特征，适用范围更广。
2. 减少对多值特征的偏好，提高选择的公平性。
3. 能处理缺失值，增强算法的鲁棒性。
4. 剪枝减少过拟合，提高泛化能力。

缺点

1. 计算复杂度高，特别是连续特征的划分点尝试增加了计算量。
2. 不支持大规模数据时的并行化。
3. 剪枝过程可能需要额外的校验集。

---

5. 代码实现

以下是一个简单的 Python 实现，用于计算信息增益比并构造 C4.5 决策树：

import numpy as np# 计算熵
def entropy(labels):total = len(labels)counts = {}for label in labels:counts[label] = counts.get(label, 0) + 1return -sum((count / total) * np.log2(count / total) for count in counts.values())# 计算信息增益比
def information_gain_ratio(data, labels, feature_index):total_entropy = entropy(labels)feature_values = [row[feature_index] for row in data]unique_values = set(feature_values)split_info = 0conditional_entropy = 0for value in unique_values:subset = [labels[i] for i in range(len(data)) if data[i][feature_index] == value]proportion = len(subset) / len(data)conditional_entropy += proportion * entropy(subset)split_info -= proportion * np.log2(proportion)info_gain = total_entropy - conditional_entropyreturn info_gain / split_info if split_info != 0 else 0# 示例数据
data = [["晴天", 30, "高", "弱"],["晴天", 32, "高", "强"],["阴天", 28, "高", "弱"],["雨天", 24, "正常", "弱"],["雨天", 20, "正常", "强"]
]
labels = ["否", "否", "是", "是", "否"]# 特征索引（天气、温度、湿度、风力）
for i in range(4):print(f"Feature {i}, Gain Ratio: {information_gain_ratio(data, labels, i):.4f}")

输出结果 

Feature 0, Gain Ratio: 0.3751
Feature 1, Gain Ratio: 0.4182
Feature 2, Gain Ratio: 0.0206
Feature 3, Gain Ratio: 0.4325

---

6. 总结

C4.5 是 ID3 的改进版本，针对实际问题的需求（连续特征、缺失值、多值特征偏好等）做了多项优化。尽管计算复杂度高，但其广泛用于分类问题，成为现代决策树算法的基础之一（如 CART）。