C4.5决策树算法历史解析：从理论到实践的新手指南

1次阅读

没有评论

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

决策树算法是机器学习中最基础且直观的分类方法之一。C4.5 算法由 Ross Quinlan 在 1993 年提出，作为 ID3 算法的改进版本，它解决了 ID3 的几个关键限制，成为机器学习历史上的重要里程碑。

ID3 算法的局限性 ：ID3 只能处理离散属性，且倾向于选择取值较多的属性（信息增益偏向多值属性）。
C4.5 的突破 ：
引入信息增益比（Gain Ratio）解决属性偏向问题
支持连续属性处理
加入剪枝机制防止过拟合
能够处理缺失值

C4.5 最核心的改进是使用信息增益比而非单纯的信息增益。其计算分为三步：

计算信息增益（Information Gain）
```
IG(S,A) = H(S) - Σ(|Sv|/|S|)*H(Sv)
```
H(S)：数据集 S 的熵
Sv：属性 A 取值为 v 的子集
计算分裂信息（Split Information）
```
SI(S,A) = -Σ(|Sv|/|S|)*log2(|Sv|/|S|)
```
这实质上是按属性 A 分裂时的熵
计算信息增益比
```
GainRatio(S,A) = IG(S,A) / SI(S,A)
```

C4.5 通过对连续属性排序后寻找最佳分裂点（使信息增益最大的分割点），将连续属性转换为二值属性。

import numpy as np
from collections import Counter

class Node:
    def __init__(self, feature=None, threshold=None, left=None, right=None, value=None):
        self.feature = feature  # 分裂特征
        self.threshold = threshold  # 连续属性的分裂阈值
        self.left = left  # 左子树
        self.right = right  # 右子树
        self.value = value  # 叶节点的类别

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

    def _entropy(self, y):
        counts = np.bincount(y)
        ps = counts / len(y)
        return -np.sum([p * np.log2(p) for p in ps if p > 0])

    def _information_gain(self, X, y, feature_idx, threshold=None):
        # 计算父节点熵
        parent_entropy = self._entropy(y)

        if threshold is None:  # 离散属性
            unique_values = np.unique(X[:, feature_idx])
            n = len(y)
            child_entropy = 0
            split_info = 0

            for value in unique_values:
                mask = X[:, feature_idx] == value
                y_child = y[mask]
                weight = len(y_child) / n
                child_entropy += weight * self._entropy(y_child)
                split_info -= weight * np.log2(weight)

            gain = parent_entropy - child_entropy
            return gain / split_info if split_info != 0 else 0

        else:  # 连续属性
            mask = X[:, feature_idx] <= threshold
            y_left = y[mask]
            y_right = y[~mask]

            if len(y_left) == 0 or len(y_right) == 0:
                return 0

            n = len(y)
            weight_left = len(y_left) / n
            weight_right = len(y_right) / n

            child_entropy = weight_left * self._entropy(y_left) + weight_right * self._entropy(y_right)
            split_info = - (weight_left * np.log2(weight_left) + weight_right * np.log2(weight_right))

            gain = parent_entropy - child_entropy
            return gain / split_info

    def _best_split(self, X, y, feature_idxs):
        best_gain = -1
        best_idx, best_threshold = None, None

        for idx in feature_idxs:
            values = X[:, idx]

            if np.issubdtype(values.dtype, np.number):  # 连续属性
                unique_values = np.unique(values)
                thresholds = (unique_values[:-1] + unique_values[1:]) / 2

                for threshold in thresholds:
                    gain = self._information_gain(X, y, idx, threshold)
                    if gain > best_gain:
                        best_gain = gain
                        best_idx = idx
                        best_threshold = threshold
            else:  # 离散属性
                gain = self._information_gain(X, y, idx)
                if gain > best_gain:
                    best_gain = gain
                    best_idx = idx
                    best_threshold = None

        return best_idx, best_threshold

    def _build_tree(self, X, y, depth=0):
        n_samples, n_features = X.shape
        n_labels = len(np.unique(y))

        # 终止条件
        if (depth >= self.max_depth or n_labels == 1 
            or n_samples < self.min_samples_split):
            counter = Counter(y)
            most_common = counter.most_common(1)[0][0]
            return Node(value=most_common)

        # 选择最佳分裂
        feature_idxs = np.random.choice(n_features, n_features, replace=False)
        best_feature, best_threshold = self._best_split(X, y, feature_idxs)

        if best_feature is None:
            counter = Counter(y)
            most_common = counter.most_common(1)[0][0]
            return Node(value=most_common)

        # 递归构建子树
        if best_threshold is None:  # 离散属性
            unique_values = np.unique(X[:, best_feature])
            node = Node(feature=best_feature)

            for value in unique_values:
                mask = X[:, best_feature] == value
                X_child, y_child = X[mask], y[mask]

                if len(y_child) == 0:
                    counter = Counter(y)
                    most_common = counter.most_common(1)[0][0]
                    node.children[value] = Node(value=most_common)
                else:
                    node.children[value] = self._build_tree(X_child, y_child, depth+1)
        else:  # 连续属性
            mask = X[:, best_feature] <= best_threshold
            left = self._build_tree(X[mask], y[mask], depth+1)
            right = self._build_tree(X[~mask], y[~mask], depth+1)
            node = Node(feature=best_feature, threshold=best_threshold, left=left, right=right)

        return node

    def fit(self, X, y):
        self.root = self._build_tree(X, y)

    def _predict(self, x, node):
        if node.value is not None:
            return node.value

        if node.threshold is None:  # 离散属性
            child = node.children.get(x[node.feature], None)
            if child is None:
                return None
            return self._predict(x, child)
        else:  # 连续属性
            if x[node.feature] <= node.threshold:
                return self._predict(x, node.left)
            else:
                return self._predict(x, node.right)

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