决策树
CART
ID3
C4.5
对比三种算法
以下是 C4.5、ID3 和 CART 对回归任务和连续值特征的支持对比：
| 特性 | ID3 | C4.5 | CART |
|---|---|---|---|
| 任务类型 | 仅分类 | 仅分类 | 分类 + 回归 |
| 连续特征支持 | 需手动分箱 | 自动二分 | 自动二分 |
| 分裂标准 | 信息增益 | 信息增益比 | 分类：基尼系数 回归：MSE |
| 缺失值处理 | 不支持 | 支持 | 支持 |
| 树结构 | 多叉树 | 多叉树 | 二叉树 |
如何选择算法？
- 分类任务：
- 优先选 C4.5（支持连续值和缺失值，避免ID3的多值偏好问题）。
- 若需二叉树或兼容回归，选 CART。
- 回归任务：只能选 CART。
- 简单需求：若数据全是离散值且无缺失值，可用 ID3（但实际很少单独使用）。
特征选择
计算信息增益/比都可以进行特征筛选，后者更优
特征增益没有绝对含义，通过相对熵来归一化尺度得到特征增益比（类多，相对熵大影响其绝对值的含义），实际上归一化系数常使用分裂信息计算，即某个属性Ag划分概率比例得到的熵
ID3步骤
步骤1，2分别处理标签全相同和没有数据集的情况，用于迭代终止
需要选择一个阈值，找到最大信息增益的特征，最大信息增益小于阈值的设置为单结点树，使用最多类作为预测值，结束迭代；大于阈值的则继续迭代，对于每个特征的值都划分成子树，并将数据集y去除那个划分特征、X根据划分特征Ag取值划分为多份到不同子结点，重复训练。
C4.5
根据《统计学习方法》， 只是将信息增益替换成信息增益比；但是有别的说法
C4.5 正规说法：
算法步骤
C4.5算法是ID3算法的改进版本，主要用于生成决策树，核心思想是通过信息增益比（Gain Ratio）选择最优划分属性。以下是C4.5算法的详细步骤：
1. 数据准备
- 输入：训练数据集$D )，包含类别标签的样本。
- 属性集：所有候选属性$A = {A_1, A_2, …, A_m} )（包括离散和连续属性）。
- 标签：类别集合$C = {C_1, C_2, …, C_k} )。
2. 递归构建决策树
递归终止条件
- 当前节点所有样本属于同一类别，标记为叶子节点并返回该类。
- 属性集为空，或样本在所有属性上取值相同，标记为叶子节点并返回多数类。
- 样本集为空（极少发生），返回父节点多数类。
未终止时步骤
- 计算信息增益比：
信息熵（Entropy）：
$\text{Entropy}(D) = -\sum_{i=1}^{k} p_i \log_2(p_i)$
其中$p_i$是类别$C_i$在数据集$D$中的比例。信息增益（Gain）：
对属性$A_j$，按取值将$D$划分为子集${D_1, D_2, …, D_v} )，计算：
$\text{Gain}(D, A_j) = \text{Entropy}(D) - \sum_{i=1}^{v} \frac{|D_i|}{|D|} \text{Entropy}(D_i)$分裂信息（Split Information）：
$\text{SplitInfo}(D, A_j) = -\sum_{i=1}^{v} \frac{|D_i|}{|D|} \log_2 \left( \frac{|D_i|}{|D|} \right)$
衡量属性$A_j$的分支数量均匀性。信息增益比（Gain Ratio）：
$\text{GainRatio}(D, A_j) = \frac{\text{Gain}(D, A_j)}{\text{SplitInfo}(D, A_j)}$
选择增益比最大的属性作为划分属性。
- 处理连续属性（C4.5新增）：
- 对连续属性$A_j$，将样本按取值排序，计算相邻值中点作为候选划分点。
- 选择使信息增益最大的划分点，将其转化为二元分裂（如“$A_j \leq a$”），计算信息增益比
- 处理缺失值（C4.5改进）：
- 按非缺失样本上该属性值的比例随机分配权重到子节点。
- 计算信息增益时，忽略缺失该属性的样本。
- C4.5 在处理 连续属性（数值型特征） 时，默认会将其 二分（Binary Split），生成 二叉树结构。
- 生成子树：
- 用选择的属性$A_j$划分数据集$D$为子集$D_1, D_2, …, D_v$。
- 对每个非空子集递归调用C4.5算法生成子树。
3. 决策树剪枝（后剪枝）
- 目的：避免过拟合，提升泛化能力。
- 方法：用验证集评估剪枝前后的性能，若剪枝后误差降低，则替换子树为叶子节点。
4. 输出决策树
- 返回生成的决策树模型，可用于对新样本分类。
关键改进（对比ID3）
- 信息增益比：解决ID3偏向多值属性的问题。
- 连续属性处理：支持数值型数据。
- 缺失值处理：通过权重分配提高鲁棒性。
- 剪枝机制：后剪枝优化树结构。
[[决策树剪枝]]
C4.5 与 ID3 的区别对比
C4.5 是 ID3 算法的改进版本，由 Ross Quinlan 提出，主要解决了 ID3 的几个关键缺陷。以下是两者的核心区别：
1. 特征选择标准
| 算法 | 标准 | 说明 |
|---|---|---|
| ID3 | 信息增益 (Information Gain) | 选择信息增益最大的特征分裂节点，但对取值多的特征有偏好（容易过拟合）。 |
| C4.5 | 信息增益比 (Gain Ratio) | 通过除以特征的固有信息（Split Information）来惩罚取值多的特征，更平衡分裂选择。 |
公式对比：
- 信息增益：
$\text{Gain}(S, A) = \text{Entropy}(S) - \sum_{v \in A} \frac{|S_v|}{|S|} \text{Entropy}(S_v) ) - 信息增益比：
$\text{GainRatio}(S, A) = \frac{\text{Gain}(S, A)}{\text{SplitInformation}(S, A)} )
其中$\text{SplitInformation}(S, A) = -\sum_{v \in A} \frac{|S_v|}{|S|} \log_2 \frac{|S_v|}{|S|} )。
示例：
- 若某特征有唯一ID（每个样本值不同），ID3会优先选择它（信息增益最大），但C4.5会因Split Information过高而降低其增益比。
2. 处理连续型特征
| 算法 | 支持连续特征？ | 处理方法 |
|---|---|---|
| ID3 | ❌ 不支持 | 只能处理离散型特征，需手动分箱预处理。 |
| C4.5 | ✅ 支持 | 自动对连续特征排序并找到最佳分裂点（如“年龄>30”），无需人工干预。 |
实现方式：
C4.5 遍历连续特征的所有可能分割点，选择信息增益比最高的阈值。
3. 缺失值处理
| 算法 | 支持缺失值？ | 处理方法 |
|---|---|---|
| ID3 | ❌ 不支持 | 需提前填充或删除缺失值。 |
| C4.5 | ✅ 支持 | 1. 按已知值的比例分配样本到子节点； 2. 分裂时调整信息增益计算，忽略缺失样本。 |
4. 剪枝策略（防止过拟合）
| 算法 | 剪枝方法 | 说明 |
|---|---|---|
| ID3 | ❌ 无剪枝 | 生成完全生长的树，容易过拟合。 |
| C4.5 | ✅ 悲观剪枝（Pessimistic Pruning） | 通过统计显著性检验（如卡方检验）剪除对泛化性能无益的分支，提升模型简洁性。 |
剪枝示例：
若某子树在训练集上准确率提升不显著（可能因噪声导致），C4.5会将其替换为叶子节点。
CART VS C4.5
| 特征 | CART | C4.5 |
|---|---|---|
| 任务类型 | 分类 + 回归 | 仅分类（后续扩展支持回归） |
| 分裂标准 | 基尼系数（Gini Index）或均方差（MSE） | 信息增益比（Gain Ratio） |
| 树结构 | 二叉树（每个节点只有两个分支） | 多叉树（根据特征取值数量分支） |
| 剪枝方法 | 代价复杂度剪枝（Cost-Complexity Pruning） | 悲观剪枝（Pessimistic Pruning） |
| 缺失值处理 | 通过替代分裂（Surrogate Splits） | 直接处理缺失值（加权信息增益） |
| 连续特征处理 | 自动二分（寻找最佳分割点） | 自动二分（类似CART） |
| 适用场景 | 更通用（支持回归任务） | 主要用于分类 |
2. 详细对比
总结：C4.5 对 ID3 的改进
- 更公平的特征选择：用信息增益比替代信息增益，减少对多值特征的偏好。
- 支持连续特征和缺失值：直接处理现实数据中的复杂情况。
- 引入剪枝：通过后剪枝降低过拟合风险。
- 工程友好性：无需手动分箱或处理缺失值，更适合实际应用。
附加对比：C4.5 与 CART
虽然问题未提及，但常有人混淆C4.5与CART（Classification and Regression Trees）：
- C4.5：生成多叉树，基于信息增益比，仅支持分类任务。
- CART：生成二叉树，基于基尼系数，支持分类和回归。