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

1次阅读

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

决策树是机器学习中最直观的分类工具之一，它的结构就像人类做决策时的思考过程，非常适合新手理解分类问题的本质。今天我们就来拆解它的经典算法——C4.5，这个在 ID3 基础上进化而来的算法，解决了关键的特征选择问题。

ID3 算法使用信息增益选择特征，但会偏向取值更多的特征。C4.5 引入信息增益比来改进这一点：

信息增益比 = 信息增益 / 固有值（分裂信息）

分裂信息 计算方式：

def split_info(feature_values):
    _, counts = np.unique(feature_values, return_counts=True)
    proportions = counts / counts.sum()
    return -np.sum(proportions * np.log2(proportions))

这样既能衡量特征区分度，又避免了 ID3 的偏向性问题。

连续值处理是 C4.5 的特色，我们通过二分法离散化：

def discretize_continuous(feature, target):
    unique_vals = np.sort(np.unique(feature))
    thresholds = (unique_vals[:-1] + unique_vals[1:]) / 2
    best_gain_ratio = -1
    for thresh in thresholds:
        discrete_feature = (feature >= thresh).astype(int)
        current_gain_ratio = calc_gain_ratio(discrete_feature, target)
        if current_gain_ratio > best_gain_ratio:
            best_thresh = thresh
            best_gain_ratio = current_gain_ratio
    return best_thresh

class TreeNode:
    def __init__(self, feature_name=None, threshold=None, leaf_class=None):
        self.feature = feature_name  # 分裂特征
        self.threshold = threshold   # 连续值阈值
        self.children = {}           # 子节点
        self.leaf_class = leaf_class # 叶节点类别

def build_tree(X, y, features):
    if len(np.unique(y)) == 1:  # 终止条件 1：纯节点
        return TreeNode(leaf_class=y[0])

    if not features:             # 终止条件 2：无特征
        return TreeNode(leaf_class=np.argmax(np.bincount(y)))

    best_feature, best_thresh = select_best_feature(X, y, features)

    if best_feature is None:     # 终止条件 3：无法提升
        return TreeNode(leaf_class=np.argmax(np.bincount(y)))

    node = TreeNode(feature_name=best_feature, threshold=best_thresh)

    if best_thresh is not None:  # 连续特征处理
        left_idx = X[:, best_feature] < best_thresh
        right_idx = ~left_idx
        node.children['left'] = build_tree(X[left_idx], y[left_idx], features)
        node.children['right'] = build_tree(X[right_idx], y[right_idx], features)
    else:                        # 离散特征处理
        for value in np.unique(X[:, best_feature]):
            subset_idx = X[:, best_feature] == value
            node.children[value] = build_tree(X[subset_idx], y[subset_idx], 
                                            [f for f in features if f != best_feature])
    return node

使用 graphviz 输出直观的树结构：

from graphviz import Digraph

def visualize_tree(node, dot=None, parent_name='', edge_label=''):
    if dot is None:
        dot = Digraph(comment='Decision Tree')
        dot.attr('node', shape='box')

    node_name = f"node_{id(node)}"
    if node.leaf_class is not None:
        dot.node(node_name, f'Class: {node.leaf_class}')
    else:
        label = f"{node.feature}"
        if node.threshold is not None:
            label += f"< {node.threshold:.2f}?"
        dot.node(node_name, label)

    if parent_name:
        dot.edge(parent_name, node_name, label=edge_label)

    for value, child in node.children.items():
        visualize_tree(child, dot, node_name, str(value))

    return dot

预剪枝：在建树时设置停止条件
最大树深度 max_depth
节点最小样本数 min_samples_split

后剪枝：建树后合并冗余分支

def prune(node, X_val, y_val):
    if node.leaf_class:
        return

    for child in node.children.values():
        prune(child, X_val, y_val)

    # 尝试替换为叶节点
    original_acc = evaluate(X_val, y_val)
    old_children = node.children
    node.children = {}
    node.leaf_class = np.argmax(np.bincount(y_val))
    new_acc = evaluate(X_val, y_val)

    if new_acc <= original_acc:  # 剪枝无效则恢复
        node.leaf_class = None
        node.children = old_children