Почему деревья сильнее переобучаются?

Почему деревья сильнее переобучаются?

Краткий ответ: Деревья переобучаются потому, что они могут без ограничений расти в сложности и идеально запоминать каждый пример. У них нет встроенного механизма регуляризации как у линейных моделей.

Основная причина: неограниченная сложность

from sklearn.tree import DecisionTreeClassifier
import numpy as np

X = np.random.randn(100, 10)
y = np.random.randint(0, 2, 100)

# Дерево без ограничений
tree_no_limit = DecisionTreeClassifier(max_depth=None)
tree_no_limit.fit(X, y)
print(f"Деревья без ограничений: {tree_no_limit.get_depth()} слоёв")

# Дерево с ограничениями
tree_limited = DecisionTreeClassifier(max_depth=5)
tree_limited.fit(X, y)

# На тренировочных данных
train_score_unlimited = tree_no_limit.score(X, y)  # Часто ~1.0
train_score_limited = tree_limited.score(X, y)     # ~0.95

print(f"Точность на train (unlimited): {train_score_unlimited:.3f}")
print(f"Точность на train (limited): {train_score_limited:.3f}")

# На тестовых данных
X_test = np.random.randn(100, 10)
y_test = np.random.randint(0, 2, 100)

test_score_unlimited = tree_no_limit.score(X_test, y_test)  # ~0.5
test_score_limited = tree_limited.score(X_test, y_test)     # ~0.6

print(f"Точность на test (unlimited): {test_score_unlimited:.3f}")
print(f"Точность на test (limited): {test_score_limited:.3f}")

Четыре главных причины переобучения деревьев

1. Способность идеально разделять примеры

# Дерево может создавать листья с одним примером
tree = DecisionTreeClassifier(min_samples_leaf=1)  # Опасно!
tree.fit(X_train, y_train)

# Каждый лист запомнит свой пример
# Лист с 1 примером класса 1 всегда предскажет класс 1

2. Отсутствие штрафа за сложность

# Линейная модель: Loss = MSE + lambda * ||w||^2
# Регуляризация штрафует за большие веса

# Дерево: Loss = только ошибка, без штрафа за глубину
# Дерево хочет расти глубже для минимизации ошибки

from sklearn.tree import DecisionTreeClassifier

tree = DecisionTreeClassifier(
    max_depth=10,              # Ограничиваем глубину
    min_samples_split=5,       # Минимум примеров для разбиения
    min_samples_leaf=2,        # Минимум примеров в листе
    max_features='sqrt',       # Случайное подмножество признаков
    ccp_alpha=0.01            # Cost-complexity pruning
)

3. Отсутствие обобщающих предположений

# Линейная модель предполагает: зависимость линейна
# Это ограничивает сложность

# Дерево предполагает: может быть любая зависимость
# Это позволяет адаптироваться к шуму

X = np.random.randn(50, 1)
y_true = (X[:, 0] > 0).astype(int)
y_noisy = y_true.copy()
y_noisy[0:5] = 1 - y_noisy[0:5]  # Добавим шум

tree = DecisionTreeClassifier(max_depth=None)
tree.fit(X, y_noisy)

# Дерево создаст сложные правила для отделения шума

4. Отсутствие встроенной кросс-валидации

from sklearn.model_selection import cross_val_score

tree = DecisionTreeClassifier(max_depth=None)
scores = cross_val_score(tree, X_train, y_train, cv=5)
print(f"CV scores: {scores}")

# Разница между CV и обучающей точностью покажет переобучение

Как измерить переобучение

from sklearn.model_selection import learning_curve

tree_limited = DecisionTreeClassifier(max_depth=5)
tree_unlimited = DecisionTreeClassifier()

train_sizes, train_scores, val_scores = learning_curve(
    tree_unlimited, X, y, cv=5, train_sizes=np.linspace(0.1, 1.0, 10)
)

# Дерево без ограничений:
# - train_scores близко к 1.0
# - val_scores намного ниже
# Это переобучение!

Практические решения

1. Ограничить глубину (самое важное)

# Плохо: max_depth=None
tree_bad = DecisionTreeClassifier()

# Хорошо: max_depth=5-15
tree_good = DecisionTreeClassifier(max_depth=10)

2. Требовать минимум примеров для разбиения

# Плохо: min_samples_split=2
# Хорошо: min_samples_split=10-50
tree = DecisionTreeClassifier(min_samples_split=20)

3. Требовать минимум примеров в листе

# Плохо: min_samples_leaf=1 (запоминание)
# Хорошо: min_samples_leaf=5-10
tree = DecisionTreeClassifier(min_samples_leaf=10)

4. Использовать ансамбли

from sklearn.ensemble import RandomForestClassifier, GradientBoostingClassifier

rf = RandomForestClassifier(n_estimators=100, max_depth=10)
gb = GradientBoostingClassifier(max_depth=5, learning_rate=0.01)

# Ансамбли борются с переобучением через усреднение

5. Pruning (обрезка дерева)

tree = DecisionTreeClassifier(ccp_alpha=0.01)
# ccp_alpha контролирует обрезку после обучения

Сравнение: Дерево vs Линейная модель

Итоговые рекомендации

# 1. Всегда ограничивай глубину
tree = DecisionTreeClassifier(max_depth=10)

# 2. Используй GridSearch для подбора параметров
from sklearn.model_selection import GridSearchCV

param_grid = {
    'max_depth': [5, 10, 15],
    'min_samples_split': [5, 10, 20],
    'min_samples_leaf': [1, 2, 5]
}

grid_search = GridSearchCV(DecisionTreeClassifier(), param_grid, cv=5)
grid_search.fit(X_train, y_train)

# 3. Используй Random Forest вместо одиночных деревьев
from sklearn.ensemble import RandomForestClassifier
rf = RandomForestClassifier(n_estimators=100, max_depth=10)

# 4. Мониторь разницу между train и test ошибкой
train_score = model.score(X_train, y_train)
test_score = model.score(X_test, y_test)
gap = train_score - test_score

if gap > 0.1:
    print("Переобучение! Уменьши сложность")

Деревья переобучаются сильнее из-за способности расти в произвольной сложности без встроенной регуляризации, позволяя им идеально запомнить даже случайный шум.