Python实战：从零实现C4.5决策树算法及避坑指南

1次阅读

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

决策树是一种模仿人类决策过程的树形结构模型，广泛应用于分类和回归任务。与 ID3 算法相比，C4.5 有以下核心改进：

使用信息增益比替代信息增益，解决 ID3 对取值较多属性的偏好问题
支持连续属性的自动离散化处理
加入剪枝机制降低过拟合风险

信息增益比是 C4.5 的核心改进点，计算公式为：

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

其中固有值的计算方式：

def _calc_intrinsic_value(self, feature_values):
    """计算特征的固有值"""
    _, counts = np.unique(feature_values, return_counts=True)
    probabilities = counts / counts.sum()
    return -np.sum(probabilities * np.log2(probabilities))

对于连续值属性，C4.5 会先排序并尝试所有可能的分割点：

将连续值按升序排列
计算相邻值的中间点作为候选分割点
选择信息增益比最大的分割点

实现代码片段：

def _handle_continuous_feature(self, X, y, feature_idx):
    """处理连续值特征的最佳分割点选择"""
    values = X[:, feature_idx]
    unique_values = np.unique(values)

    if len(unique_values) <= 1:
        return None

    sorted_values = np.sort(unique_values)
    split_points = (sorted_values[:-1] + sorted_values[1:]) / 2

    best_gain_ratio = -1
    best_split = None

    for point in split_points:
        # 计算当前分割点的信息增益比
        current_ratio = self._calc_gain_ratio(...)
        if current_ratio > best_gain_ratio:
            best_gain_ratio = current_ratio
            best_split = point

    return best_split

递归终止条件需要处理以下情况：

当前节点所有样本属于同一类别
没有剩余特征可供划分
样本数量小于预设阈值

核心递归函数框架：

def _build_tree(self, X, y, features):
    """递归构建决策树"""
    # 终止条件 1：所有样本同类别
    if len(np.unique(y)) == 1:
        return Node(is_leaf=True, class_label=y[0])

    # 终止条件 2：无剩余特征或样本数过少
    if len(features) == 0 or len(y) < self.min_samples_split:
        majority_class = self._get_majority_class(y)
        return Node(is_leaf=True, class_label=majority_class)

    # 选择最佳划分特征
    best_feature, split_point = self._choose_best_feature(X, y, features)

    # 创建内部节点
    node = Node(is_leaf=False, 
               feature_index=best_feature,
               split_value=split_point)

    # 递归构建子树
    left_idx = ... # 根据分割点筛选样本
    right_idx = ...

    node.left = self._build_tree(X[left_idx], y[left_idx], 
                                [f for f in features if f != best_feature])
    node.right = self._build_tree(X[right_idx], y[right_idx],
                                 [f for f in features if f != best_feature])

    return node

以下是面向对象封装的完整实现框架：

import numpy as np
from collections import Counter

class Node:
    """决策树节点类"""
    def __init__(self, is_leaf=False, class_label=None, 
                 feature_index=None, split_value=None):
        self.is_leaf = is_leaf
        self.class_label = class_label  # 叶节点的类别
        self.feature_index = feature_index  # 内部节点的划分特征
        self.split_value = split_value  # 连续值特征的分割点
        self.left = None  # 左子树
        self.right = None  # 右子树

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

    def fit(self, X, y):
        """构建决策树"""
        self.root = self._build_tree(X, y, list(range(X.shape[1])))

    # 前面介绍过的各个方法实现...

    def predict(self, X):
        """预测新样本"""
        return np.array([self._predict_single(x) for x in X])

    def _predict_single(self, x, node=None):
        """递归预测单个样本"""
        if node is None:
            node = self.root

        if node.is_leaf:
            return node.class_label

        if x[node.feature_index] <= node.split_value:
            return self._predict_single(x, node.left)
        else:
            return self._predict_single(x, node.right)

常见处理方法包括：