C4.5算法决策树：从原理到实战的机器学习入门指南

1次阅读

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

C4.5 是 ID3 算法的改进版本，两者均属于决策树算法家族。它们的核心区别主要体现在以下方面：

处理连续属性 ：ID3 无法直接处理连续值属性，需要预先离散化；而 C4.5 通过寻找最佳分割点自动处理连续属性。
分支标准 ：ID3 使用信息增益作为分支标准，倾向于选择取值较多的属性；C4.5 引入信息增益比（Gain Ratio）来校正这一偏差。

信息增益比的计算分为两步：

计算信息增益（与 ID3 相同）：

Gain(S, A) = Entropy(S) - Σ(|Sv|/|S|)*Entropy(Sv)

计算分裂信息（Split Information）：

SplitInfo(S, A) = -Σ(|Sv|/|S|)*log2(|Sv|/|S|)

最终的信息增益比：

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

下面是一个简化版的 C4.5 决策树实现，包含主要功能模块：

import numpy as np
import math

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

def entropy(y):
    # 计算熵
    _, counts = np.unique(y, return_counts=True)
    probabilities = counts / counts.sum()
    return -np.sum(probabilities * np.log2(probabilities))

def information_gain(X, y, feature_idx, threshold):
    # 计算信息增益
    parent_entropy = entropy(y)
    left_mask = X[:, feature_idx] <= threshold
    right_mask = ~left_mask

    n = len(y)
    n_left, n_right = sum(left_mask), sum(right_mask)

    if n_left == 0 or n_right == 0:
        return 0

    child_entropy = (n_left/n)*entropy(y[left_mask]) + (n_right/n)*entropy(y[right_mask])
    return parent_entropy - child_entropy

def gain_ratio(X, y, feature_idx, threshold):
    # 计算信息增益比
    gain = information_gain(X, y, feature_idx, threshold)

    left_mask = X[:, feature_idx] <= threshold
    n = len(y)
    n_left, n_right = sum(left_mask), sum(~left_mask)

    if n_left == 0 or n_right == 0:
        return 0

    split_info = -((n_left/n)*math.log2(n_left/n) + (n_right/n)*math.log2(n_right/n))
    return gain / split_info if split_info != 0 else 0

def find_best_split(X, y):
    # 寻找最佳分割点
    best_gain_ratio = -1
    best_feature, best_threshold = None, None

    for feature_idx in range(X.shape[1]):
        thresholds = np.unique(X[:, feature_idx])
        for threshold in thresholds:
            current_gain_ratio = gain_ratio(X, y, feature_idx, threshold)
            if current_gain_ratio > best_gain_ratio:
                best_gain_ratio = current_gain_ratio
                best_feature = feature_idx
                best_threshold = threshold

    return best_feature, best_threshold

def build_tree(X, y, max_depth=5, min_samples_split=2):
    # 构建决策树
    if len(np.unique(y)) == 1 or len(y) < min_samples_split or max_depth == 0:
        return TreeNode(leaf_value=np.bincount(y).argmax())

    feature, threshold = find_best_split(X, y)
    if feature is None:
        return TreeNode(leaf_value=np.bincount(y).argmax())

    left_mask = X[:, feature] <= threshold
    right_mask = ~left_mask

    left_subtree = build_tree(X[left_mask], y[left_mask], max_depth-1, min_samples_split)
    right_subtree = build_tree(X[right_mask], y[right_mask], max_depth-1, min_samples_split)

    return TreeNode(feature=feature, threshold=threshold, left=left_subtree, right=right_subtree)

def predict_sample(tree, x):
    # 单样本预测
    if tree.leaf_value is not None:
        return tree.leaf_value

    if x[tree.feature] <= tree.threshold:
        return predict_sample(tree.left, x)
    else:
        return predict_sample(tree.right, x)

C4.5 算法的时间复杂度主要取决于以下因素：