C4.5决策树算法解析：从信息增益到剪枝优化

1次阅读

没有评论

共计 2128 个字符，预计需要花费 6 分钟才能阅读完成。

决策树是一种基于树结构的分类模型，通过递归划分数据空间实现决策。在众多决策树算法中，ID3 和 C4.5 是最具代表性的两种算法：

ID3 算法：
使用信息增益作为属性选择标准
仅支持离散型特征
没有剪枝机制，容易过拟合
C4.5 算法改进：
引入信息增益比解决 ID3 的属性偏向问题
支持连续值特征处理
加入剪枝机制控制模型复杂度

信息增益比是 C4.5 改进 ID3 的核心所在，其计算分为两步：

信息增益计算（同 ID3）：
```
Gain(S,A) = Entropy(S) - Σ(|S_v|/|S|)*Entropy(S_v)
```
其中 S_v 表示特征 A 取值为 v 的样本子集
固有值 (IV) 计算：
```
IV(A) = -Σ(|S_v|/|S|)*log2(|S_v|/|S|)
```
信息增益比公式：
```
GainRatio(S,A) = Gain(S,A)/IV(A)
```

这个改进有效缓解了 ID3 对取值数目较多特征的偏好问题。

C4.5 处理连续特征的创新方法：

排序与候选点生成：
对连续特征值排序
取相邻样本的中点作为候选划分点

最优划分点选择：

对于每个候选点 t，计算：Gain(S,A,t) = Entropy(S) - |S_left|/|S|*Entropy(S_left) - |S_right|/|S|*Entropy(S_right)

选择使 Gain 最大的 t 作为划分阈值

二分法处理：
将连续特征转换为二元特征：A≤t 和 A >t
仅在选择该特征时进行二分

import numpy as np
from collections import Counter

class C45Node:
    def __init__(self, feature=None, threshold=None, left=None, right=None, value=None):
        self.feature = feature  # 分裂特征
        self.threshold = threshold  # 连续特征划分阈值
        self.left = left  # 左子树
        self.right = right  # 右子树
        self.value = value  # 叶节点类别

def entropy(y):
    """计算信息熵"""
    hist = np.bincount(y)
    ps = hist / len(y)
    return -np.sum([p * np.log2(p) for p in ps if p > 0])

def information_gain(X, y, feature_idx, threshold=None):
    """计算信息增益"""
    parent_entropy = entropy(y)

    if threshold is None:  # 离散特征
        unique_values = np.unique(X[:, feature_idx])
        child_entropy = 0
        split_info = 0

        for value in unique_values:
            mask = X[:, feature_idx] == value
            child_y = y[mask]
            if len(child_y) > 0:
                p = len(child_y) / len(y)
                child_entropy += p * entropy(child_y)
                split_info -= p * np.log2(p)
    else:  # 连续特征
        mask = X[:, feature_idx] <= threshold
        left_y, right_y = y[mask], y[~mask]

        p_left = len(left_y) / len(y)
        p_right = len(right_y) / len(y)
        child_entropy = p_left * entropy(left_y) + p_right * entropy(right_y)
        split_info = - (p_left * np.log2(p_left) + p_right * np.log2(p_right))

    gain = parent_entropy - child_entropy
    gain_ratio = gain / split_info if split_info > 0 else 0

    return gain_ratio