在机器学习中，决策树是一种直观且强大的分类模型，但未经处理的决策树容易因过度生长出现过拟合问题 —— 模型在训练集上表现优异，却在新数据上泛化能力差。剪枝是解决决策树过拟合的核心手段，主要分为  预剪枝（Pre-pruning）和后剪枝（Post-pruning）两种策略。本文将详细介绍这两种剪枝方法的原理，并基于testset.txt数据文件实现完整的代码案例，对比其效果。

一、决策树剪枝基础：预剪枝 vs 后剪枝

1.1 预剪枝（先剪枝）

预剪枝的核心思想是在决策树的构建过程中提前停止生长。简单来说，就是在每个节点分裂前进行判断：如果分裂后无法提升模型性能，或满足预设的停止条件，就直接将当前节点设为叶节点，不再继续分裂。

常见预剪枝策略：

• 限制树的最大深度（max_depth）
• 限制节点分裂所需的最小样本数（min_samples_split）
• 限制叶节点的最小样本数（min_samples_leaf）
• 分裂的信息增益 / 增益比低于阈值则不分裂

优缺点：

• ✅ 优点：计算效率高，无需构建完整的树，训练速度快。
• ❌ 缺点：容易因 “过早停止” 导致欠拟合，对停止条件的参数较为敏感。

1.2 后剪枝（后剪枝）

后剪枝的核心思想是先构建完整的决策树，再从下往上回溯剪枝。首先不施加任何限制，生成一棵 “满树”，然后从叶节点向上遍历每个非叶节点，判断将该节点替换为叶节点后，模型在验证集上的性能是否提升（或不变）。如果是，则剪枝（删除子节点，设为叶节点）。

常见后剪枝策略：

• REP（错误率降低剪枝）：用验证集判断剪枝后错误率是否降低（本文实现此方法）
• CCP（代价复杂度剪枝）：引入复杂度惩罚项，寻找最优剪枝点（sklearn 默认使用）

优缺点：

• ✅ 优点：泛化能力更强，不易欠拟合，剪枝效果更稳定。
• ❌ 缺点：计算成本高，需要先构建完整树，且需多次遍历验证集。

二、基于自定义数据集的代码实现

2.1 实现思路

1. 读取dataset.txt（训练集）和testset.txt（测试集），处理逗号分隔的格式，分离 4 个特征和 1 个标签。
2. 定义TreeNode类，存储决策树节点的分裂特征、阈值、左右子树和叶节点值。
3. 实现决策树的基础功能（熵计算、信息增益比、最优分裂查找）。
4. 在树的构建过程中加入预剪枝的停止条件（最大深度、最小样本数、叶节点最小样本数、增益比阈值）。
5. 用训练集训练模型，测试集评估效果。

1.读取训练集和测试集

import numpy as np

def load_data(file_path):
    """读取逗号分隔的txt数据，返回X（前4列特征）和y（最后1列标签）"""
    # 处理逗号分隔，指定数据类型为float32
    data = np.loadtxt(file_path, delimiter=',', dtype=np.float32)
    X = data[:, :4]  # 前4列是特征（固定4个特征）
    y = data[:, 4]   # 最后1列是标签
    return X, y

2.定义TreeNode类，存储决策树节点的核心属性，包括分裂特征索引、分裂阈值、左右子树和叶节点类别值。

class TreeNode:
    def __init__(self, feature_idx=None, threshold=None, left=None, right=None, value=None):
        self.feature_idx = feature_idx  # 分裂特征索引（0-3，对应4个特征）
        self.threshold = threshold      # 分裂阈值（数值型）
        self.left = left                # 左子树（样本<=阈值）
        self.right = right              # 右子树（样本>阈值）
        self.value = value              # 叶节点的类别值（分类结果）

3.定义DecisionTreePrePruning类，实现熵计算、信息增益、分裂信息、信息增益比等基础功能，为决策树分裂提供依据。

class DecisionTreePrePruning:
    def __init__(self, max_depth=5, min_samples_split=2, min_samples_leaf=1, gain_threshold=0.0):
        # 预剪枝参数初始化
        self.max_depth = max_depth                # 树的最大深度
        self.min_samples_split = min_samples_split  # 节点分裂的最小样本数
        self.min_samples_leaf = min_samples_leaf    # 叶节点的最小样本数
        self.gain_threshold = gain_threshold      # 信息增益比阈值
        self.root = None                          # 树的根节点

    def _compute_leaf_value(self, y):
        """计算叶节点值：返回出现次数最多的类别（分类任务）"""
        unique_classes, counts = np.unique(y, return_counts=True)
        return unique_classes[np.argmax(counts)]

    def _entropy(self, y):
        """计算香农熵：衡量样本的纯度"""
        unique_classes, counts = np.unique(y, return_counts=True)
        probabilities = counts / len(y)
        # 处理概率为0的情况（log2(0)无意义，直接跳过）
        entropy = -np.sum([p * np.log2(p) for p in probabilities if p > 0])
        return entropy

    def _information_gain(self, X, y, feature_idx, threshold):
        """计算信息增益：父节点熵 - 子节点加权平均熵"""
        parent_entropy = self._entropy(y)
        # 根据特征和阈值划分左右样本
        left_indices = X[:, feature_idx] <= threshold
        right_indices = ~left_indices

        # 若划分后某一侧无样本，信息增益为0（无分裂意义）
        if np.sum(left_indices) == 0 or np.sum(right_indices) == 0:
            return 0.0

        total_samples = len(y)
        # 计算左右子节点的熵
        left_entropy = self._entropy(y[left_indices])
        right_entropy = self._entropy(y[right_indices])
        # 子节点的加权平均熵（按样本数加权）
        child_entropy = (np.sum(left_indices)/total_samples)*left_entropy + (np.sum(right_indices)/total_samples)*right_entropy

        return parent_entropy - child_entropy

    def _split_info(self, X, feature_idx, threshold):
        """计算分裂信息：用于信息增益比的归一化，避免偏向取值多的特征"""
        left_indices = X[:, feature_idx] <= threshold
        right_indices = ~left_indices
        total_samples = len(X)
        left_samples = np.sum(left_indices)
        right_samples = np.sum(right_indices)

        # 若划分后某一侧无样本，分裂信息为0
        if left_samples == 0 or right_samples == 0:
            return 0.0

        p_left = left_samples / total_samples
        p_right = right_samples / total_samples
        # 分裂信息的计算公式与熵一致
        return -p_left * np.log2(p_left) - p_right * np.log2(p_right)

    def _information_gain_ratio(self, X, y, feature_idx, threshold):
        """计算信息增益比：信息增益 / 分裂信息"""
        info_gain = self._information_gain(X, y, feature_idx, threshold)
        split_info = self._split_info(X, feature_idx, threshold)

        # 避免除以0，返回0
        if split_info == 0:
            return 0.0
        return info_gain / split_info

5.实现模型的训练（初始化根节点）和预测（单样本 / 样本集）方法。

    def fit(self, X, y):
        """训练决策树：初始化根节点，触发递归构建"""
        self.root = self._build_tree(X, y)
        return self

    def _predict_single(self, x, node):
        """预测单个样本：递归遍历决策树，直到叶节点"""
        # 叶节点：返回类别值
        if node.value is not None:
            return node.value
        # 非叶节点：根据特征和阈值走向左/右子树
        if x[node.feature_idx] <= node.threshold:
            return self._predict_single(x, node.left)
        else:
            return self._predict_single(x, node.right)

    def predict(self, X):
        """预测样本集：遍历每个样本，调用单样本预测"""
        return np.array([self._predict_single(x, self.root) for x in X])

6.加载训练集和测试集，初始化并训练预剪枝决策树，评估模型准确率。

if __name__ == "__main__":
    # 1. 加载数据（独立的训练集和测试集）
    X_train, y_train = load_data("dataset.txt")
    X_test, y_test = load_data("testset.txt")
    print(f"训练集：样本数={len(X_train)}，特征数={X_train.shape[1]}（固定4个）")
    print(f"测试集：样本数={len(X_test)}，特征数={X_test.shape[1]}（固定4个）")

    # 2. 初始化并训练预剪枝决策树（可调整参数）
    pre_tree = DecisionTreePrePruning(
        max_depth=5,          # 树的最大深度
        min_samples_split=3,  # 节点分裂的最小样本数
        min_samples_leaf=2,   # 叶节点的最小样本数
        gain_threshold=0.01   # 信息增益比阈值
    )
    pre_tree.fit(X_train, y_train)

    # 3. 预测并计算准确率
    y_pred_train = pre_tree.predict(X_train)
    y_pred_test = pre_tree.predict(X_test)
    train_accuracy = np.sum(y_pred_train == y_train) / len(y_train)
    test_accuracy = np.sum(y_pred_test == y_test) / len(y_test)

    print(f"\n预剪枝决策树 - 训练集准确率：{train_accuracy:.4f}")
    print(f"预剪枝决策树 - 测试集准确率：{test_accuracy:.4f}")

7.测试结果

未剪枝决策树测试集精度：0.8571
预剪枝决策树（max_depth=2）测试集精度：0.8571
后剪枝决策树（最优α=0.0192）测试集精度：0.8571

三、总结与思考

预剪枝通过提前停止树的生长避免过拟合，后剪枝通过回溯剪枝优化完整树的结构。两种方法各有优劣，在实际项目中需根据数据规模和性能要求选择：

• 小规模数据：可使用后剪枝，追求更高的泛化能力。
• 大规模数据：优先使用预剪枝，保证训练效率。