Python实战：C4.5决策树算法从原理到实现

1次阅读

没有评论

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

C4.5 是决策树算法中的经典代表，由 ID3 算法改进而来。它的核心思想是通过递归地选择最优特征对数据进行划分，直到满足停止条件。与 ID3 相比，C4.5 主要做了以下改进：

使用信息增益比而非信息增益：信息增益比可以避免 ID3 倾向于选择取值较多的特征的问题。
支持连续值处理：C4.5 能够自动对连续属性进行离散化处理。
支持缺失值处理：C4.5 可以处理数据中存在的缺失值。
引入剪枝策略：通过预剪枝或后剪枝来防止过拟合。

虽然 ID3 和 C4.5 都是决策树算法，但它们在多个方面存在差异：

特征选择标准：ID3 使用信息增益，C4.5 使用信息增益比。
特征类型支持：ID3 只能处理离散特征，C4.5 可以处理连续特征。
缺失值处理：ID3 不能处理缺失值，C4.5 可以。
剪枝策略：ID3 没有剪枝，容易过拟合；C4.5 支持剪枝。

下面是一个简化版的 C4.5 决策树 Python 实现。完整代码可在 GitHub 上找到。

import numpy as np
from collections import Counter

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

    def fit(self, X, y):
        self.n_features = X.shape[1]
        self.tree = self._grow_tree(X, y)

    def _grow_tree(self, X, y, depth=0):
        # 停止条件
        if (self.max_depth is not None and depth >= self.max_depth) or len(y) < self.min_samples_split:
            return Counter(y).most_common(1)[0][0]

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

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

        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 (best_feature, best_threshold, left, right)

    def _best_split(self, X, y):
        # 计算信息增益比
        best_gain_ratio = -1
        best_feature, best_threshold = None, None

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

        return best_feature, best_threshold

    def predict(self, X):
        return np.array([self._predict_one(x, self.tree) for x in X])

    def _predict_one(self, x, node):
        if not isinstance(node, tuple):
            return node

        feature_idx, threshold, left, right = node
        if x[feature_idx] <= threshold:
            return self._predict_one(x, left)
        else:
            return self._predict_one(x, right)

在实际应用中，C4.5 决策树需要注意以下几个性能问题：