Как выполняется pruning в деревьях?

Pruning в деревьях решений

Pruning (обрезка) — это техника, которая уменьшает размер дерева решений путём удаления узлов, которые не улучшают качество предсказаний. Это ключевой метод борьбы с переобучением.

Почему pruning нужен?

Без pruning дерево может разрастись до огромных размеров:

• Переобучение — модель запоминает шум в тренировочных данных
• Плохая обобщаемость — слабые результаты на тестовых данных
• Медленные предсказания — большое дерево требует много операций
• Сложность интерпретации — трудно объяснить решение

# Пример переобучения без pruning
from sklearn.tree import DecisionTreeClassifier
import numpy as np
from sklearn.metrics import accuracy_score

# Маленький набор данных
X_train = np.random.rand(50, 5)
y_train = (X_train[:, 0] > 0.5).astype(int)

# Без ограничений — вырастет огромное дерево
tree_no_limit = DecisionTreeClassifier(
    min_samples_split=1,  # Разрешаем узлы с 1 образцом
    min_samples_leaf=1    # Листья с 1 образцом
)
tree_no_limit.fit(X_train, y_train)

print(f"Дерево без ограничений: {tree_no_limit.tree_.node_count} узлов")
# Вывод: Дерево без ограничений: 89 узлов (сильное переобучение)

Тип 1: Cost Complexity Pruning (CCP)

Математически формулируется так:

C(T) = Error(T) + α × |листья|

Где:

• Error(T) — ошибка на валидационном наборе
• α (alpha) — параметр сложности дерева
• |листья| — количество листьев

По мере увеличения α мы удаляем всё больше узлов.

from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import cross_val_score
import matplotlib.pyplot as plt

# Обучаем полное дерево
tree = DecisionTreeClassifier(random_state=42)
tree.fit(X_train, y_train)

# Вычисляем alphas для разных уровней pruning
path = tree.cost_complexity_pruning_path(X_train, y_train)
ccp_alphas = path.ccp_alphas
impurities = path.impurities

print(f"Найдено {len(ccp_alphas)} различных альфа-значений")
print(f"Альфа варьируется от {ccp_alphas[0]:.4f} до {ccp_alphas[-1]:.4f}")

# Для каждого альфа обучаем дерево и оцениваем на кросс-валидации
trees = []
scores = []

for ccp_alpha in ccp_alphas:
    tree = DecisionTreeClassifier(random_state=42, ccp_alpha=ccp_alpha)
    score = cross_val_score(tree, X_train, y_train, cv=5, scoring='accuracy')
    trees.append(tree)
    scores.append(score.mean())

# Находим лучший альфа
best_alpha_idx = np.argmax(scores)
best_alpha = ccp_alphas[best_alpha_idx]

final_tree = DecisionTreeClassifier(random_state=42, ccp_alpha=best_alpha)
final_tree.fit(X_train, y_train)

print(f"Лучший alpha: {best_alpha:.4f}")
print(f"Узлов в исходном дереве: {tree.tree_.node_count}")
print(f"Узлов в pruned дереве: {final_tree.tree_.node_count}")
print(f"Лучший скор CV: {scores[best_alpha_idx]:.3f}")

Тип 2: Reduced Error Pruning (REP)

Это более простой и интуитивный метод:

1. Разделяем данные на 2 части: обучение и валидацию
2. Обучаем полное дерево на обучающем наборе
3. Проходим по каждому узлу начиная снизу вверх
4. Пробуем удалить узел и заменить его листом класса большинства
5. Если точность на валидации не падает — удаляем узел навсегда
6. Иначе — оставляем узел

def reduced_error_pruning(tree, X_train, y_train, X_val, y_val):
    """
    Simplified REP для демонстрации
    """
    from sklearn.metrics import accuracy_score
    
    # Исходная точность
    y_pred = tree.predict(X_val)
    baseline_accuracy = accuracy_score(y_val, y_pred)
    
    def prune_node(node_id):
        """Удаляет поддерево в узле и заменяет листом класса большинства"""
        # Это демонстрация логики — реальная реализация сложнее
        pass
    
    # Проходим по узлам в обратном порядке (листья → корень)
    nodes_to_check = list(range(tree.tree_.node_count - 1, -1, -1))
    
    for node_id in nodes_to_check:
        # Пытаемся удалить узел
        # Если точность не падает — удаляем
        # Иначе оставляем
        pass
    
    return tree

Тип 3: Minimal Error Pruning (MEP)

Удаляет узлы на основе вероятности ошибки, которая может быть связана с шумом:

# Проще всего — использовать параметры при создании дерева
# Это автоматический pruning

tree = DecisionTreeClassifier(
    min_samples_split=5,      # Минимум 5 образцов для разделения
    min_samples_leaf=2,       # Минимум 2 в листе
    max_depth=10,             # Максимальная глубина
    max_leaf_nodes=20         # Максимум листьев
)

Сравнение: до и после pruning

import matplotlib.pyplot as plt
from sklearn.tree import plot_tree

fig, axes = plt.subplots(1, 2, figsize=(16, 6))

# Без pruning
tree_full = DecisionTreeClassifier(min_samples_split=1, min_samples_leaf=1)
tree_full.fit(X_train, y_train)
plot_tree(tree_full, ax=axes[0], feature_names=[f'Feature {i}' for i in range(X_train.shape[1])])
axes[0].set_title(f'Full Tree ({tree_full.tree_.node_count} узлов)')

# С pruning
tree_pruned = DecisionTreeClassifier(ccp_alpha=0.01)
tree_pruned.fit(X_train, y_train)
plot_tree(tree_pruned, ax=axes[1], feature_names=[f'Feature {i}' for i in range(X_train.shape[1])])
axes[1].set_title(f'Pruned Tree ({tree_pruned.tree_.node_count} узлов)')

plt.tight_layout()
plt.show()

Практический пример: выбор правильной глубины

from sklearn.model_selection import learning_curve
import matplotlib.pyplot as plt

# Варьируем глубину дерева
max_depths = range(1, 20)
train_scores = []
test_scores = []

for depth in max_depths:
    tree = DecisionTreeClassifier(max_depth=depth, random_state=42)
    tree.fit(X_train, y_train)
    
    train_acc = tree.score(X_train, y_train)
    test_acc = tree.score(X_test, y_test)
    
    train_scores.append(train_acc)
    test_scores.append(test_acc)

plt.figure(figsize=(10, 6))
plt.plot(max_depths, train_scores, 'o-', label='Training accuracy')
plt.plot(max_depths, test_scores, 's-', label='Test accuracy')
plt.axvline(x=max_depths[np.argmax(test_scores)], color='red', linestyle='--')
plt.xlabel('Max Depth')
plt.ylabel('Accuracy')
plt.legend()
plt.title('Выбор оптимальной глубины через pruning')
plt.grid(True)
plt.show()

# Оптимальная глубина — где тест-скор максимален
optimal_depth = max_depths[np.argmax(test_scores)]
print(f"Оптимальная глубина: {optimal_depth}")

Когда использовать какой метод?

Ключевые выводы

• Pruning предотвращает переобучение — оставляет только значимые узлы
• CCP (Cost Complexity Pruning) — стандарт в scikit-learn
• Alpha параметр контролирует размер — выше alpha = меньше дерево
• Cross-validation помогает выбрать alpha — тестируем на кросс-валидации
• В production обычно ограничивают параметры (max_depth, min_samples_leaf) вместо post-hoc pruning