C4.5决策树构建全流程解析：从数据预处理到模型优化

1次阅读

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

决策树作为经典的机器学习算法，因其可解释性强、训练效率高、对数据分布假设少等优势，在分类问题中广泛应用。C4.5 算法作为 ID3 的改进版本，通过引入信息增益率和剪枝策略，有效解决了 ID3 算法倾向于选择取值较多的属性、无法处理连续值和缺失值等问题。

C4.5 算法使用信息增益率而非 ID3 的信息增益来选择分裂属性，避免了偏向取值多的属性的问题。

计算步骤如下：

计算数据集 D 的信息熵：

def entropy(D):
    _, counts = np.unique(D, return_counts=True)
    probabilities = counts / len(D)
    return -np.sum(probabilities * np.log2(probabilities))

计算属性 A 的信息增益：

def information_gain(D, A):
    original_entropy = entropy(D)
    values, counts = np.unique(A, return_counts=True)
    weighted_entropy = np.sum([(counts[i]/len(D)) * entropy(D[A == values[i]]) 
                              for i in range(len(values))])
    return original_entropy - weighted_entropy

计算属性 A 的分裂信息：

def split_information(A):
    values, counts = np.unique(A, return_counts=True)
    probabilities = counts / len(A)
    return -np.sum(probabilities * np.log2(probabilities))

计算信息增益率：

def gain_ratio(D, A):
    gain = information_gain(D, A)
    split_info = split_information(A)
    return gain / split_info if split_info != 0 else 0

C4.5 算法通过二分法将连续属性离散化：

对连续属性值进行排序
计算相邻值的中间值作为候选划分点
选择使信息增益率最大的划分点

def discretize_continuous(D, A):
    sorted_values = np.sort(np.unique(A))
    split_points = [(sorted_values[i] + sorted_values[i+1])/2 
                    for i in range(len(sorted_values)-1)]

    best_gain_ratio = 0
    best_split = None

    for split in split_points:
        A_discrete = np.where(A <= split, f'<={split}', f'>{split}')
        current_ratio = gain_ratio(D, A_discrete)
        if current_ratio > best_gain_ratio:
            best_gain_ratio = current_ratio
            best_split = split

    return best_split

C4.5 算法处理缺失值的策略：

计算信息增益率时，只使用属性值已知的样本
样本划分时，将缺失值样本按权重分配到各子节点

C4.5 采用悲观剪枝策略：

计算子树在训练集上的错误率
计算剪枝后节点在训练集上的错误率
比较两者，决定是否剪枝

import numpy as np
import pandas as pd

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

    def fit(self, X, y):
        self.tree = self._build_tree(X, y, depth=0)

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

        # 选择最佳分裂属性
        best_attr, best_split = None, None
        best_gain_ratio = -1

        for attr in X.columns:
            if np.issubdtype(X[attr].dtype, np.number):  # 连续属性
                split = discretize_continuous(y, X[attr])
                if split is None: continue
                temp_attr = np.where(X[attr] <= split, f'<={split}', f'>{split}')
                current_ratio = gain_ratio(y, temp_attr)
            else:  # 离散属性
                current_ratio = gain_ratio(y, X[attr])
                split = None

            if current_ratio > best_gain_ratio:
                best_gain_ratio = current_ratio
                best_attr = attr
                best_split = split

        if best_attr is None:  # 无法继续分裂
            return {'label': np.argmax(np.bincount(y))}

        # 构建子树
        tree = {'attribute': best_attr, 'split': best_split, 'children': {}}

        if best_split is not None:  # 连续属性
            left_mask = X[best_attr] <= best_split
            right_mask = X[best_attr] > best_split

            tree['children']['<='+str(best_split)] = self._build_tree(X[left_mask], y[left_mask], depth+1)
            tree['children']['>'+str(best_split)] = self._build_tree(X[right_mask], y[right_mask], depth+1)
        else:  # 离散属性
            for value in np.unique(X[best_attr]):
                mask = X[best_attr] == value
                tree['children'][value] = self._build_tree(X[mask], y[mask], depth+1)

        return tree

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

    def _predict_single(self, x, node):
        if 'label' in node:
            return node['label']

        attr_value = x[node['attribute']]

        if node['split'] is not None:  # 连续属性处理
            if attr_value <= node['split']:
                child_key = '<='+str(node['split'])
            else:
                child_key = '>'+str(node['split'])
        else:  # 离散属性处理
            child_key = attr_value

        if child_key in node['children']:
            return self._predict_single(x, node['children'][child_key])
        else:
            # 处理未见过的类别，返回多数类
            return self._get_most_common_label(node)

    def _get_most_common_label(self, node):
        labels = []
        for child in node['children'].values():
            if 'label' in child:
                labels.append(child['label'])
            else:
                labels.extend(self._get_all_labels(child))
        return np.argmax(np.bincount(labels)) if labels else 0

    def _get_all_labels(self, node):
        labels = []
        if 'label' in node:
            return [node['label']]
        for child in node['children'].values():
            labels.extend(self._get_all_labels(child))
        return labels

对于取值数量特别多的分类特征，考虑：
合并低频类别
使用目标编码 (Target Encoding)
限制树的最大深度

关键参数：
max_depth: 限制树的最大深度
min_samples_split: 节点分裂所需最小样本数
min_samples_leaf: 叶节点最小样本数
建议使用交叉验证调优这些参数

使用采样方法处理大数据集
考虑使用增量学习
对于分布式环境，可以使用 Spark MLlib 的实现

算法	优点	缺点	适用场景
C4.5	可处理连续值和缺失值，可解释性强	计算复杂度较高，容易过拟合	中小规模数据，需要可解释性
CART	可处理回归问题，计算效率较高	只能生成二叉树	大规模数据，回归问题
随机森林	抗过拟合能力强，准确率高	可解释性较差，计算资源消耗大	大规模数据，高精度要求