C4.5算法决策树：从原理到工程实践的关键技术解析

1次阅读

没有评论

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

决策树算法是机器学习中最直观的算法之一，它通过一系列规则对数据进行分类或回归。C4.5 算法作为 ID3 算法的改进版本，在实际工程中应用广泛，尤其是在需要高可解释性的场景。

ID3 的不足：ID3 算法只能处理离散特征，无法直接处理连续值；它对取值较多的特征有偏好，容易导致过拟合。
C4.5 的改进：引入了信息增益比（Gain Ratio）来替代信息增益，减少了偏向多值特征的倾向；支持连续值处理；增加了剪枝策略来防止过拟合。

C4.5 算法的核心在于特征选择和树的构建。

信息增益比：信息增益比是对信息增益的一种归一化处理，它考虑了特征本身的熵值。公式为：
```
GainRatio(S, A) = Gain(S, A) / SplitInfo(S, A)
```
其中，SplitInfo(S, A)是特征 A 的熵值。
连续值处理：C4.5 通过二分法将连续值离散化。具体步骤是：
对连续特征的所有取值排序
计算相邻值的中间点作为候选划分点
选择信息增益比最高的划分点
剪枝策略：C4.5 采用悲观剪枝（Pessimistic Pruning），通过统计方法估计子树的错误率，决定是否剪枝。

以下是一个基于 Python 的 C4.5 算法实现示例，使用了 numpy 和pandas库。

import numpy as np
import pandas as pd

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 fit(self, X, y):
        self.tree = self._build_tree(X, y, depth=0)

    def _build_tree(self, X, y, depth):
        # 终止条件
        if len(np.unique(y)) == 1 or len(y) < self.min_samples_split or (self.max_depth is not None and depth >= self.max_depth):
            return np.argmax(np.bincount(y))

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

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

        left_subtree = self._build_tree(X[left_indices], y[left_indices], depth + 1)
        right_subtree = self._build_tree(X[right_indices], y[right_indices], depth + 1)

        return (best_feature, best_threshold, left_subtree, right_subtree)

    def _choose_best_feature(self, X, y):
        best_gain_ratio = -1
        best_feature = None
        best_threshold = None

        for feature in range(X.shape[1]):
            if np.issubdtype(X[:, feature].dtype, np.number):  # 连续值
                thresholds = self._get_candidate_thresholds(X[:, feature])
                for threshold in thresholds:
                    gain_ratio = self._calculate_gain_ratio(X[:, feature], y, threshold)
                    if gain_ratio > best_gain_ratio:
                        best_gain_ratio = gain_ratio
                        best_feature = feature
                        best_threshold = threshold
            else:  # 离散值
                gain_ratio = self._calculate_gain_ratio_discrete(X[:, feature], y)
                if gain_ratio > best_gain_ratio:
                    best_gain_ratio = gain_ratio
                    best_feature = feature
                    best_threshold = None

        return best_feature, best_threshold

    def _get_candidate_thresholds(self, feature_values):
        sorted_values = np.sort(np.unique(feature_values))
        return (sorted_values[:-1] + sorted_values[1:]) / 2

    def _calculate_gain_ratio(self, feature_values, y, threshold):
        # 计算信息增益比
        pass  # 实现略

    def _calculate_gain_ratio_discrete(self, feature_values, y):
        # 计算离散特征的信息增益比
        pass  # 实现略

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

    def _predict_single(self, x, tree):
        if isinstance(tree, (int, np.integer)):
            return tree
        feature, threshold, left, right = tree
        if x[feature] <= threshold:
            return self._predict_single(x, left)
        else:
            return self._predict_single(x, right)