C4.5决策树算法解析：从原理到工程实践

1次阅读

没有评论

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

决策树是一种模仿人类决策过程的树形结构模型，通过递归地选择最优特征进行数据划分。ID3 算法作为早期经典方案，存在两个明显缺陷：

偏向选择取值较多的特征（如 ID 类特征）
无法直接处理连续值和缺失值

C4.5 在 ID3 基础上进行了三大核心改进：

引入信息增益比（Gain Ratio）替代信息增益
增加连续特征离散化处理
支持缺失值处理与剪枝优化

信息增益比通过引入分裂信息（Split Information）来惩罚多值特征，其计算公式为：

GainRatio(A) = Gain(A) / SplitInfo(A)

其中 SplitInfo 的计算方式为：

SplitInfo(A) = -Σ(|D_v|/|D|) * log2(|D_v|/|D|)

实际计算示例（天气特征）：

计算原始数据集的信息熵：H(D) = 0.971
计算天气特征的条件熵：H(D| 天气) = 0.551
信息增益：Gain(天气) = 0.420
分裂信息：SplitInfo(天气) = 1.577
最终增益比：0.420/1.577 ≈ 0.266

import numpy as np
from collections import Counter

class C45Node:
    def __init__(self, feature=None, threshold=None, value=None):
        self.feature = feature  # 分裂特征
        self.threshold = threshold  # 连续特征划分阈值
        self.children = {}  # 子节点
        self.value = value  # 叶节点预测值

class C45DecisionTree:
    def __init__(self, min_samples_split=2, max_depth=None):
        self.min_samples_split = min_samples_split
        self.max_depth = max_depth

    def _entropy(self, y):
        counts = np.bincount(y)
        ps = counts / len(y)
        return -np.sum([p * np.log2(p) for p in ps if p > 0])

    def _information_gain_ratio(self, X, y, feature_idx):
        # 计算信息增益比的核心逻辑
        parent_entropy = self._entropy(y)

        # 处理连续特征
        if isinstance(X[0, feature_idx], float):
            thresholds = sorted(set(X[:, feature_idx]))
            best_gain = -1
            best_threshold = None

            for threshold in thresholds:
                left_idxs = X[:, feature_idx] <= threshold
                right_idxs = X[:, feature_idx] > threshold

                if len(y[left_idxs]) == 0 or len(y[right_idxs]) == 0:
                    continue

                # 计算信息增益
                n = len(y)
                n_l, n_r = len(y[left_idxs]), len(y[right_idxs])
                e_l, e_r = self._entropy(y[left_idxs]), self._entropy(y[right_idxs])
                child_entropy = (n_l/n)*e_l + (n_r/n)*e_r
                gain = parent_entropy - child_entropy

                # 计算分裂信息
                split_info = -((n_l/n)*np.log2(n_l/n) + (n_r/n)*np.log2(n_r/n))
                gain_ratio = gain / split_info if split_info != 0 else 0

                if gain_ratio > best_gain:
                    best_gain = gain_ratio
                    best_threshold = threshold

            return best_gain, best_threshold
        else:
            # 离散特征处理...
            pass

排序后取相邻值中点作为候选划分点
计算每个划分点的信息增益比
选择最优划分点作为决策节点

训练阶段：将缺失值样本按不同取值比例分配到子节点
预测阶段：根据特征分布概率选择分支路径

def prune(self, node, X_val, y_val):
    if node.value is not None:
        return  # 叶节点不剪枝

    # 递归处理子节点
    for child in node.children.values():
        self.prune(child, X_val, y_val)

    # 计算当前节点的验证集准确率
    original_acc = self._accuracy(X_val, y_val)

    # 尝试替换为叶节点
    temp_value = self._most_common_label(y_val)
    original_value = node.value
    node.value = temp_value

    # 计算剪枝后准确率
    pruned_acc = self._accuracy(X_val, y_val)

    # 决定是否剪枝
    if pruned_acc >= original_acc:
        node.feature = None
        node.children = {}
    else:
        node.value = original_value