Что такое прунинг (обрезка) деревьев решений?

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

Цель: Улучшить обобщающую способность модели, жертвуя небольшой точностью на обучающей выборке ради большей стабильности и точности на новых, невидимых данных.

Основные виды прунинга:

1. Пре-прунинг (Pre-pruning, "ранняя остановка"): Рост дерева останавливается до того, как оно полностью подгонится под обучающие данные. Контролируется гиперпараметрами.

   • Примеры ограничений: max_depth (максимальная глубина), min_samples_split (минимальное количество образцов для разделения узла), min_samples_leaf (минимальное количество образцов в листе).

2. Пост-прунинг (Post-pruning): Сначала строится полное, потенциально переобученное дерево, а затем его ветви рекурсивно заменяются на листовые узлы. Критерием для замены является сравнение ошибки на отдельной валидационной выборке или с использованием критерия минимальной стоимости-сложности.

Пример пост-прунинга с использованием Cost-Complexity Pruning в scikit-learn:

from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split

# Загрузка данных
X, y = load_breast_cancer(return_X_y=True)
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=42)

# 1. Строим большое дерево (с минимальным пре-прунингом)
clf_full = DecisionTreeClassifier(random_state=42, min_samples_leaf=5)
clf_full.fit(X_train, y_train)

# 2. Вычисляем эффективные альфы для прунинга
path = clf_full.cost_complexity_pruning_path(X_train, y_train)
ccp_alphas, impurities = path.ccp_alphas, path.impurities

# 3. Обучаем серию деревьев с разными ccp_alpha
clfs = []
for ccp_alpha in ccp_alphas:
    clf = DecisionTreeClassifier(random_state=42, ccp_alpha=ccp_alpha)
    clf.fit(X_train, y_train)
    clfs.append(clf)

# 4. Выбираем дерево с лучшей точностью на валидации/тесте
# (На практике нужна отдельная валидационная выборка)
test_accuracies = [clf.score(X_test, y_test) for clf in clfs]
best_alpha = ccp_alphas[test_accuracies.index(max(test_accuracies))]

# 5. Финальная обрезанная модель
clf_pruned = DecisionTreeClassifier(random_state=42, ccp_alpha=best_alpha)
clf_pruned.fit(X_train, y_train)
print(f"Глубина полного дерева: {clf_full.tree_.max_depth}")
print(f"Глубина обрезанного дерева: {clf_pruned.tree_.max_depth}")

Преимущества: Снижение переобучения, уменьшение сложности модели (интерпретируемость), часто — повышение скорости предсказания. Недостатки: Пост-прунинг требует дополнительных вычислительных ресурсов для построения полного дерева, а агрессивная обрезка может привести к недообучению.