提示：机器学习实验–剪枝

---

提示：这里可以添加本文要记录的大概内容：

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、平台

jupyter note
pycharm

二、具体实现

源码

import numpy as np
import pandas as pd
from math import log2
import matplotlib.pyplot as plt

data = {
    'ID': range(1, 17),
    '年龄段': ['青年', '青年', '青年', '青年', '青年', '中年', '中年', '中年', '中年', '中年', 
             '老年', '老年', '老年', '老年', '老年', '老年'],
    '有工作': ['否', '否', '是', '是', '否', '否', '否', '是', '否', '否', 
             '否', '否', '是', '是', '否', '否'],
    '有自己的房子': ['否', '否', '否', '是', '否', '否', '否', '是', '是', '是', 
                  '是', '是', '否', '否', '否', '否'],
    '信贷情况': ['一般', '好', '好', '一般', '一般', '一般', '好', '好', '非常好', '非常好', 
               '非常好', '好', '好', '非常好', '一般', '非常好'],
    '类别(是否给贷款)': ['否', '否', '是', '是', '否', '否', '否', '是', '是', '是', 
                     '是', '是', '是', '是', '否', '否']
}
df = pd.DataFrame(data)

class TreeNode:
    def __init__(self, feature=None, value=None, results=None, children=None):
        self.feature = feature
        self.value = value
        self.results = results
        self.children = children or {}
    
    def is_leaf(self):
        return len(self.children) == 0

def calculate_entropy(labels):
    if len(labels) == 0:
        return 0
    
    value_counts = pd.Series(labels).value_counts()
    entropy_val = 0
    
    for count in value_counts:
        p = count / len(labels)
        entropy_val -= p * log2(p)
    
    return entropy_val

def calculate_information_gain(data, feature, target):
    total_entropy = calculate_entropy(data[target])
    feature_values = data[feature].unique()
    weighted_entropy = 0
    
    for value in feature_values:
        subset = data[data[feature] == value]
        weight = len(subset) / len(data)
        weighted_entropy += weight * calculate_entropy(subset[target])
    
    return total_entropy - weighted_entropy

def build_tree(data, features, target):
    if len(data[target].unique()) == 1:
        return TreeNode(results=data[target].iloc[0])
    
    if len(features) == 0:
        majority_class = data[target].mode()[0]
        return TreeNode(results=majority_class)
    
    best_feature = None
    best_gain = -1
    
    for feature in features:
        gain = calculate_information_gain(data, feature, target)
        if gain > best_gain:
            best_gain = gain
            best_feature = feature
    
    tree = TreeNode(feature=best_feature)
    remaining_features = [f for f in features if f != best_feature]
    
    for value in data[best_feature].unique():
        subset = data[data[best_feature] == value]
        
        if len(subset) == 0:
            majority_class = data[target].mode()[0]
            tree.children[value] = TreeNode(results=majority_class)
        else:
            tree.children[value] = build_tree(subset, remaining_features, target)
    
    return tree

def predict(tree, sample):
    if tree.is_leaf():
        return tree.results
    
    feature_value = sample[tree.feature]
    if feature_value in tree.children:
        return predict(tree.children[feature_value], sample)
    else:
        return None

def evaluate_accuracy(tree, validation_data, target_col):
    correct = 0
    total = len(validation_data)
    
    for i, row in validation_data.iterrows():
        sample = {col: row[col] for col in validation_data.columns if col != target_col}
        prediction = predict(tree, sample)
        if prediction == row[target_col]:
            correct += 1
    
    return correct / total if total > 0 else 0

def get_majority_class(data, target_col):
    return data[target_col].mode()[0] if len(data) > 0 else None

def prune_tree(tree, validation_data, target_col, parent_data=None):
    if tree.is_leaf():
        return tree
    
    if len(validation_data) == 0:
        if parent_data is not None:
            majority_class = get_majority_class(parent_data, target_col)
            if majority_class is not None:
                return TreeNode(results=majority_class)
        return tree
    
    current_accuracy = evaluate_accuracy(tree, validation_data, target_col)
    
    for value, child in list(tree.children.items()):
        subset = validation_data[validation_data[tree.feature] == value]
        if not child.is_leaf() and len(subset) > 0:
            parent_subset = parent_data[parent_data[tree.feature] == value] if parent_data is not None else None
            tree.children[value] = prune_tree(child, subset, target_col, parent_subset)
    
    if parent_data is not None:
        majority_class = get_majority_class(parent_data, target_col)
        if majority_class is not None:
            leaf_tree = TreeNode(results=majority_class)
            leaf_accuracy = evaluate_accuracy(leaf_tree, validation_data, target_col)
            
            if leaf_accuracy >= current_accuracy:
                return leaf_tree
    
    return tree

def deep_copy_tree(node):
    if node.is_leaf():
        return TreeNode(results=node.results)
    
    new_node = TreeNode(feature=node.feature)
    for value, child in node.children.items():
        new_node.children[value] = deep_copy_tree(child)
    
    return new_node

target_col = '类别(是否给贷款)'
feature_cols = ['年龄段', '有工作', '有自己的房子', '信贷情况']
decision_tree = build_tree(df, feature_cols, target_col)
print("决策树构建完成！")

from sklearn.model_selection import train_test_split

train_data, validation_data = train_test_split(df, test_size=0.3, random_state=42)

print(f"训练集大小: {len(train_data)}")
print(f"验证集大小: {len(validation_data)}")

train_tree = build_tree(train_data, feature_cols, target_col)
print("基于训练集的决策树构建完成！")

train_accuracy = evaluate_accuracy(train_tree, train_data, target_col)
val_accuracy_before = evaluate_accuracy(train_tree, validation_data, target_col)

print(f"\n剪枝前准确率:")
print(f"训练集准确率: {train_accuracy:.4f}")
print(f"验证集准确率: {val_accuracy_before:.4f}")

pruned_tree = prune_tree(deep_copy_tree(train_tree), validation_data, target_col, train_data)
print("决策树剪枝完成！")

train_accuracy_after = evaluate_accuracy(pruned_tree, train_data, target_col)
val_accuracy_after = evaluate_accuracy(pruned_tree, validation_data, target_col)

print(f"\n剪枝后准确率:")
print(f"训练集准确率: {train_accuracy_after:.4f}")
print(f"验证集准确率: {val_accuracy_after:.4f}")

print(f"\n准确率变化:")
print(f"训练集准确率变化: {train_accuracy_after - train_accuracy:.4f}")
print(f"验证集准确率变化: {val_accuracy_after - val_accuracy_before:.4f}")

def count_nodes(tree):
    if tree.is_leaf():
        return 1
    count = 1
    for child in tree.children.values():
        count += count_nodes(child)
    return count

def print_tree_structure(node, indent=""):
    if node.is_leaf():
        print(indent + f"叶子节点: {node.results}")
    else:
        print(indent + f"特征: {node.feature}")
        for value, child in node.children.items():
            print(indent + f"├── {node.feature} = {value}")
            print_tree_structure(child, indent + "│   ")

print("剪枝前决策树结构:")
print("=" * 40)
print_tree_structure(train_tree)
print(f"\n节点总数: {count_nodes(train_tree)}")

print("\n\n剪枝后决策树结构:")
print("=" * 40)
print_tree_structure(pruned_tree)
print(f"\n节点总数: {count_nodes(pruned_tree)}")

分析

剪枝原理

决策树剪枝是减少决策树复杂度、防止过拟合的重要方法。本实现采用后剪枝（Post-pruning）方法，也称为REP（Reduced Error Pruning）剪枝。

剪枝策略

1. 先构建完整决策树：使用训练集数据构建完整的决策树
2. 使用验证集评估：对每个节点，比较剪枝前后的验证集准确率
3. 自底向上剪枝：从叶子节点向上，如果剪枝后验证集准确率不降低，则执行剪枝
4. 递归处理：对所有子树递归执行剪枝操作

核心函数

prune_tree(tree, validation_data, target_col, parent_data)

功能：对决策树进行后剪枝

参数：

• tree: 要剪枝的决策树节点
• validation_data: 验证集数据
• target_col: 目标列名
• parent_data: 父节点的训练数据（用于获取多数类）

返回：剪枝后的决策树
算法流程：

1. 如果是叶子节点或验证集为空，直接返回
2. 递归剪枝所有子树
3. 尝试将当前节点替换为叶子节点（使用父节点的多数类）
4. 比较剪枝前后的验证集准确率
5. 如果剪枝后准确率不降低，执行剪枝并返回叶子节点