【机器学习之决策树剪枝处理】(含手动实现代码)
·
前言
决策树是机器学习中经典的分类与回归模型，凭借直观的逻辑结构和易解释性，在实际场景中应用广泛。但决策树天生存在过拟合风险 —— 随着树的深度增加、分支增多，模型会过度学习训练数据中的细节甚至噪声，导致在新数据上的泛化性能下降。剪枝作为解决这一问题的核心手段，通过合理削减决策树的冗余分支，在降低模型复杂度的同时，实现泛化能力的提升。本文将系统拆解剪枝的核心概念与两种主流策略（预剪枝、后剪枝），提供可直接运行的手动实现代码，并通过实验结果分析剪枝的实际效果与适用场景，帮助读者深入理解剪枝的本质与实践逻辑。
一、什么是剪枝？
1.剪枝的概念
通过降低决策树的复杂度来避免过拟合的过程称为剪枝。
可通过"剪枝"一定程度避免因决策分支过多，以致于把训练集自身的一些特点当作所有数据都具有的一般性质而导致的过拟合。
2.剪枝的基本策略
- 预剪枝
- 后剪枝
3.预剪枝
- 步骤：
- 将数据集分为训练集和验证集
- 决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点记为叶结点，其类别标记为训练样例数最多的类别
- 预剪枝的优点：
- 降低过拟合风险
- 显著减少训练时间和测试时间开销
- 预剪枝的缺点：
- 欠拟合风险
4.后剪枝
先从训练集生成一棵完整的决策树，然后自底向上地对非叶节点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点
- 后剪枝的优点：
后剪枝比预剪枝保留了更多的分支，欠拟合风险小，泛化性能优于预剪枝 - 后剪枝的缺点：
训练时间开销大，后剪枝过程是在完成完全决策树之后进行的，需要自底向上对所有非叶节点逐一考察
二、手动代码实现
1.简单的基本函数
- TreeNode类：自定义节点类，用于存储决策树的节点
# 决策树节点类 - 表示决策树中的每个节点
class TreeNode:
# 初始化节点
def __init__(self, feature=None, value=None, children=None):
self.feature = feature # 内部节点
self.value = value # 叶节点
self.children = children if children is not None else {} # 子节点字典
# 判断是否为叶节点
def is_leaf(self):
return self.value is not None
- calculate_gain(data, feature, target) 函数：计算某个特征的信息增益
（具体可以看上一篇文章，有更加详细的解释和代码）
def calculate_gain(data, feature, target):
# 计算原始数据集的熵（分裂前的熵）
total_ENT = calculate_ENT(data[target])
# 创建字典来按特征值分组数据
feature_values = {}
# 遍历数据集的每一行
for index, row in data.iterrows():
# 获取当前行的特征值
value = row[feature]
# 如果特征值不在字典中，创建空列表
if value not in feature_values:
feature_values[value] = []
# 将对应的目标值添加到该特征值的列表中
feature_values[value].append(row[target])
# 初始化条件熵
conditional_ENT = 0
# 遍历每个特征值对应的目标值列表
for value, value_labels in feature_values.items():
# 计算该特征值的概率（该特征值出现的频率）
p = len(value_labels) / len(data)
# 计算该特征值对应的熵，并加权累加到条件熵中
conditional_ENT += p * calculate_ENT(value_labels)
# 信息增益 = 原始熵 - 条件熵
gain = total_ENT - conditional_ENT
# 返回信息增益值
return gain
- evaluate_node(node, val_data, target)函数：给定一个节点（叶节点或子树），计算其在验证集上的预测准确率
这是构造预剪枝决策树的核心，通过对比分裂前后的预测准确率，判断是否要分裂
#计算预测准确率的函数
def evaluate_node(node, val_data, target):
correct = 0
for _, row in val_data.iterrows():
# 预测：从当前节点遍历到叶节点
current_node = node
while current_node.feature is not None: # 不是叶节点，继续遍历
feature_val = row[current_node.feature]
# 若当前特征取值不在子节点中，用当前节点的多数类预测
if feature_val not in current_node.children:
break
current_node = current_node.children[feature_val]
# 对比预测值和真实值
if current_node.value == row[target]:
correct += 1
return correct / len(val_data) if len(val_data) > 0 else 0.0
- predict(tree, sample)函数:使用决策树预测单个样本
def predict(tree, sample):
# 如果当前节点是叶节点，直接返回预测值
if tree.is_leaf():
return tree.value
# 获取样本在当前分裂特征上的值
feature_value = sample[tree.feature]
# 如果特征值在子节点中存在，递归预测
if feature_value in tree.children:
return predict(tree.children[feature_value], sample)
else:
# 如果遇到未知的特征值，返回None
return None
- get_majority_class_from_subtree(tree, validation_data, target)函数：#该内部节点在训练集中 “覆盖” 的所有样本中，出现次数最多的类别。这是后剪枝的关键，是剪枝的"依据提供者"
# 找到当前节点对应的训练集样本中，出现次数最多的类别（用于后剪枝）
def get_majority_class_from_subtree(tree, train_data, target):
"""
tree: 当前要剪枝的节点
train_data: 整个训练集（用于找多数类）
target: 目标列名
"""
# 如果是叶节点，直接返回其值
if tree.is_leaf():
return tree.value
#辅助函数：找到当前结点在训练集当中覆盖的所有样本索引
# 递归找到当前节点覆盖的所有训练集样本索引
def get_covered_samples(node, data, covered_indices):
if node.is_leaf():
return covered_indices
# 遍历当前节点的所有子特征值
for value, child in node.children.items():
# 找到训练集中该特征值对应的样本索引
value_indices = data[data[node.feature] == value].index
# 递归处理子节点，累加覆盖的索引
get_covered_samples(child, data, covered_indices.union(value_indices))
return covered_indices
# 初始化覆盖的样本索引集合
covered_indices = set()
covered_indices = get_covered_samples(tree, train_data, covered_indices)
# 提取当前节点覆盖的训练集样本
covered_samples = train_data.loc[list(covered_indices)]
# 如果没有覆盖到样本，返回训练集整体多数类
if len(covered_samples) == 0:
return train_data[target].mode()[0]
# 返回覆盖样本中的多数类
return covered_samples[target].mode()[0]
2.预剪枝代码实现
本文主要基于信息增益去递归构建决策树，该代码中在构建决策树的过程中包含了剪枝，避免过拟合。
代码输入说明：
- :train_data: 训练数据集，用于构建树的核心数据
- val_data: 验证数据集，用于评估泛化性能，判断是否需要剪枝
- target: 目标列名称，即要预测的类别
- features: 当前可用的特征列表，未被用于划分的特征
-depth: 当前树的深度，仅用于递归跟踪
#预剪枝函数(基于信息增益)
def build_decision_tree_with_pruning(train_data, val_data, target, features, depth=0):
# 原有终止条件1：所有训练样本属于同一类别
# data[target].unique() 获取目标列的所有类别
if len(train_data[target].unique()) == 1:
#取唯一类别作为叶结点的预测值
leaf_val = train_data[target].iloc[0]
#返回叶结点
return TreeNode(value=leaf_val)
# 原有终止条件2：无可用特征
if len(features) == 0:
#采用训练集出现次数最多的类别作为叶结点预测值
majority_class = train_data[target].mode()[0]
return TreeNode(value=majority_class)
# 计算“不分裂”的性能
#用训练集的众数作为叶结点的预测值
current_majority = train_data[target].mode()[0]
#构建临时叶结点(用于性能评估)
no_split_node = TreeNode(value=current_majority)
#计算该临时叶结点在验证集上的准确率
no_split_accuracy = evaluate_node(no_split_node, val_data, target)
# 选择信息增益最大的特征
best_feature = None
best_gain = -1
#遍历可用的所有特征，计算每个特征的信息增益
for feature in features:
gain = calculate_gain(train_data, feature, target)
#更新最大的信息增益和对应的特征
if gain > best_gain:
best_gain = gain
best_feature = feature
# 原有终止条件3：信息增益为0（分裂无意义）
if best_gain == 0:
return TreeNode(value=current_majority)
# 剩余可用特征
remaining_features = [f for f in features if f != best_feature]
# 构建临时节点
temp_node = TreeNode(feature=best_feature)
#遍历最优特征的所有取值
for value in train_data[best_feature].unique():
#筛选当前特征取值对应的子集
subset = train_data[train_data[best_feature] == value]
#如果子集为空，则用训练集众数填充叶结点
if len(subset) == 0:
temp_node.children[value] = TreeNode(value=current_majority)
else:
# 递归构建临时子树
temp_node.children[value] = build_decision_tree_with_pruning(
subset, val_data, target, remaining_features, depth + 1
)
# 计算分裂后临时子树的准确率
split_accuracy = evaluate_node(temp_node, val_data, target)
# 预剪枝判断：分裂后性能是否提升
if split_accuracy <= no_split_accuracy + 1e-6: # 允许微小波动（避免浮点误差）
# 分裂无提升，停止分裂，返回叶节点
return TreeNode(value=current_majority)
else:
# 分裂有提升，正式构建子树并返回
#构建最终的内部节点
node = TreeNode(feature=best_feature)
for value in train_data[best_feature].unique():
#筛选当前特征取值对应的训练集子集
subset = train_data[train_data[best_feature] == value]
if len(subset) == 0:
node.children[value] = TreeNode(value=current_majority)
else:
#递归构建子树
node.children[value] = build_decision_tree_with_pruning(
subset, val_data, target, remaining_features, depth + 1
)
#返回内部节点(包含所有的分支和子树)
return node
代码的关键细节：
- 基础的终止条件：训练集所有样本属于同一类别、无可用特征、最优特征信息增益为 0
- 预剪枝的核心：当分裂后的性能显著高于分裂前的性能时，才继续分裂；否则停止分裂，将当前结点设为叶节点（剪枝操作）
- 最优特征：基于信息增益，计算每个可用特征的信息增益，选择增益最大的特征作为当前节点的划分特征
- 递归构建子树
3.后剪枝代码实现
后剪枝的核心是：先构建完整决策树，再自底向上评估每个内部节点；若将该节点剪枝为叶结点后，验证集性能提升，则保留剪枝结果；否则要保留原节点
该代码输入说明：
- tree:完整的决策树根节点
- validation_data:验证集，用于评估剪枝前后的泛化性能
- target:目标列名称，即要预测的类别
#后剪枝函数
def post_prune(tree, train_data,validation_data, target):
# 如果是叶节点，不需要剪枝
if tree.is_leaf():
return tree
# 先递归剪枝所有子节点，自底向上
for value, child in tree.children.items():
#用剪枝后的子节点替换原子节点
tree.children[value] = post_prune(child, train_data,validation_data, target)
# 计算当前节点作为内部节点时的精度
current_accuracy = evaluate_node(tree, validation_data, target)
# 计算如果剪枝为叶节点时的精度
# 找到训练数据中该节点对应的多数类别
majority_class = get_majority_class_from_subtree(tree, train_data, target)
#创建剪枝后的叶结点
pruned_tree = TreeNode(value=majority_class)
#计算剪枝后叶结点的精度
pruned_accuracy = calculate_tree_accuracy(pruned_tree, validation_data, target)
# 如果剪枝后精度上升，则进行剪枝
if pruned_accuracy > current_accuracy:
return pruned_tree
else:
#否则保留原节点
return tree
代码的关键细节：
-自底向上的核心：要先剪子节点，再剪父节点
-后剪枝的核心准则：若剪枝后性能下降或不变，则不剪枝
三、结果分析
我们给出数据集：
将其映射为数值形式：
计算信息增益：
接着，我们对三种树进行可视化
- 未剪枝树统计：
深度: 3
验证集精度: 1.000
测试集精度: 1.000
- 预剪枝树统计:
深度: 3
验证集精度: 1.000
测试集精度: 1.000
- 后剪枝树统计:
深度: 3
验证集精度: 1.000
测试集精度: 1.000
经观察，我们发现剪枝前后的差异无法体现，且所有模型的精度都达到100%。这是因为： - 数据过于简单且无噪声
- 预剪枝/后剪枝“无枝可剪”：未剪枝树仅3层，本身就不深
建议改进：增加数据复杂度，引入噪声样本，扩大样本量
总结
本文围绕决策树剪枝展开，首先明确了剪枝的核心目标是通过降低模型复杂度避免过拟合，进而介绍了预剪枝 “提前终止分裂” 和后剪枝 “先建全树再剪枝” 的两种核心策略 —— 预剪枝高效且能规避过拟合，但存在欠拟合风险；后剪枝泛化性能更优、欠拟合风险低，却需承担更高的训练开销。
通过手动代码实现，我们具象化了两种剪枝的核心逻辑，实验结果印证了剪枝的适用前提 —— 当数据存在噪声、树结构过度复杂时，剪枝才能充分发挥作用。
总体而言，剪枝是决策树模型优化的关键步骤，实际应用中需根据数据复杂度、训练效率要求选择合适的剪枝策略，后续可通过增加数据复杂度、引入噪声样本等方式，进一步验证剪枝对模型性能的优化效果。
更多推荐
27
0- 0
已为社区贡献4条内容
所有评论(0)