C4.5决策树算法实战：从原理到Python实现与调优指南

1次阅读

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

决策树算法自 1986 年 ID3 算法问世以来，经历了多次迭代升级。ID3 算法虽然简单易懂，但存在两个主要缺陷：无法处理连续值特征，以及倾向于选择取值较多的特征（即容易过拟合）。为了解决这些问题，Ross Quinlan 在 1993 年提出了 C4.5 算法，它引入了信息增益比和连续值处理等改进措施。

信息增益比 ：解决了 ID3 偏向选择取值多特征的问题
连续值处理 ：通过二分法将连续特征离散化
剪枝机制 ：引入后剪枝减少过拟合

C4.5 使用信息增益比替代 ID3 的信息增益，公式为：

 信息增益比 = 信息增益 / 固有值 (IV)

其中固有值 IV 的计算方式为：

IV = -Σ(p_i * log2(p_i))

p_i 表示第 i 个子集占总样本的比例。

对连续特征进行排序
计算相邻值的中点作为候选划分点
对每个候选点计算信息增益比
选择信息增益比最大的点作为划分点

import numpy as np
from collections import Counter

class DataPreprocessor:
    def __init__(self):
        self.continuous_threshold = 10

    def is_continuous(self, feature):
        return len(set(feature)) > self.continuous_threshold

class TreeNode:
    def __init__(self, feature_name=None, threshold=None, left=None, right=None, value=None):
        self.feature_name = feature_name  # 分裂特征
        self.threshold = threshold      # 分裂阈值 (连续特征)
        self.left = left                # 左子树
        self.right = right              # 右子树
        self.value = value              # 叶节点预测值

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

    def fit(self, X, y, feature_names):
        self.feature_names = feature_names
        self.n_classes = len(set(y))
        self.tree = self._grow_tree(X, y)

    def _grow_tree(self, X, y, depth=0):
        # 递归终止条件
        if (depth >= self.max_depth or 
            len(y) < self.min_samples_split or
            len(set(y)) == 1):
            return TreeNode(value=self._most_common_label(y))

        # 选择最佳分裂特征
        best_feature, best_threshold = self._best_split(X, y)

        # 无法找到有效分裂
        if best_feature is None:
            return TreeNode(value=self._most_common_label(y))

        # 递归构建子树
        left_idx = X[:, best_feature] <= best_threshold
        right_idx = ~left_idx

        left = self._grow_tree(X[left_idx], y[left_idx], depth+1)
        right = self._grow_tree(X[right_idx], y[right_idx], depth+1)

        return TreeNode(feature_name=self.feature_names[best_feature],
                        threshold=best_threshold,
                        left=left, right=right)

max_depth：控制树的最大深度
值过小可能导致欠拟合
值过大会导致过拟合
min_samples_split：节点分裂的最小样本数
较大值可以防止过拟合
较小值可以让树更复杂

def prune(self, X_val, y_val):
    self.tree = self._prune_tree(self.tree, X_val, y_val)

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

    # 递归剪枝子树
    feature_idx = self.feature_names.index(node.feature_name)
    left_idx = X_val[:, feature_idx] <= node.threshold
    right_idx = ~left_idx

    node.left = self._prune_tree(node.left, X_val[left_idx], y_val[left_idx])
    node.right = self._prune_tree(node.right, X_val[right_idx], y_val[right_idx])

    # 尝试剪枝
    if node.left.value is not None and node.right.value is not None:
        # 计算剪枝前后的准确率
        before_acc = self._accuracy(X_val, y_val)

        # 临时保存子树
        left_subtree, right_subtree = node.left, node.right

        # 尝试剪枝
        node.left = node.right = None
        node.value = self._most_common_label(y_val)
        after_acc = self._accuracy(X_val, y_val)

        # 如果剪枝后准确率不下降，则保留剪枝
        if after_acc >= before_acc:
            return node
        else:
            # 恢复子树
            node.left, node.right = left_subtree, right_subtree
            node.value = None
            return node

    return node