Деревья решений: алгоритм, критерии ветвления и управление сложностью

Что такое дерево решений

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

Ключевое достоинство: дерево легко интерпретируемо — его логику можно изложить в виде набора «если... то...» правил. Именно поэтому деревья широко применяются в областях, где важна интерпретируемость: медицинская диагностика, кредитный скоринг, юридические системы.

Алгоритм CART: как строится дерево

Наиболее распространён алгоритм CART (Classification and Regression Trees). На каждом шаге он выбирает признак j и порог t, минимизирующие целевую функцию разбиения:

Разбиение: {X : Xⱼ ≤ t}  и  {X : Xⱼ > t}

Алгоритм перебирает все (j, t) и выбирает пару с
наименьшим взвешенным значением критерия нечистоты.

Критерий Gini (для классификации)

Gini-индекс узла измеряет вероятность случайно выбранного объекта быть неправильно классифицированным, если метку выбирать согласно распределению классов в узле:

Gini(t) = 1 - Σₖ p(k|t)²

где p(k|t) — доля объектов класса k в узле t

Пример: узел с 70% класса A и 30% класса B:
Gini = 1 - (0.7² + 0.3²) = 1 - (0.49 + 0.09) = 0.42

Чистый узел (100% одного класса): Gini = 0
Максимальная нечистота (50/50): Gini = 0.5

Критерий энтропии (Information Gain)

Энтропия — мера неопределённости в узле, пришедшая из теории информации:

H(t) = -Σₖ p(k|t) · log₂ p(k|t)

Пример: узел 70/30:
H = -(0.7·log₂0.7 + 0.3·log₂0.3)
  = -(0.7·(-0.515) + 0.3·(-1.737))
  = -(–0.361 – 0.521) = 0.882 бит

Чистый узел: H = 0
Равные доли (50/50): H = 1.0 бит

Information Gain разбиения — уменьшение энтропии после разбиения:

IG(t, j, threshold) = H(t) - [n_L/n · H(t_L) + n_R/n · H(t_R)]

Переобучение деревьев и методы ограничения сложности

Без ограничений CART растёт до тех пор, пока каждый лист не будет содержать один объект (идеальное разбиение обучающей выборки, нулевая обучающая ошибка). Это классическое переобучение с высокой дисперсией.

Практика: классификация с DecisionTreeClassifier

from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier, export_text
from sklearn.model_selection import train_test_split, cross_val_score
from sklearn.metrics import classification_report
import numpy as np

# Загрузка данных
iris = load_iris()
X, y = iris.data, iris.target

X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.25, random_state=42, stratify=y
)

# Без ограничений — переобучение
dt_overfit = DecisionTreeClassifier(random_state=42)
dt_overfit.fit(X_train, y_train)
print("Train accuracy (no limit):", dt_overfit.score(X_train, y_train))  # ~1.0
print("Test  accuracy (no limit):", dt_overfit.score(X_test, y_test))    # ниже

# С ограничением глубины
dt = DecisionTreeClassifier(
    max_depth=4,
    min_samples_leaf=5,
    criterion='gini',
    random_state=42
)
dt.fit(X_train, y_train)
print("\nTrain accuracy (max_depth=4):", dt.score(X_train, y_train))
print("Test  accuracy (max_depth=4):", dt.score(X_test, y_test))

# Cross-validation для выбора глубины
depths = range(1, 10)
cv_scores = []
for d in depths:
    model = DecisionTreeClassifier(max_depth=d, random_state=42)
    scores = cross_val_score(model, X, y, cv=5, scoring='accuracy')
    cv_scores.append(scores.mean())

best_depth = depths[np.argmax(cv_scores)]
print(f"\nОптимальная глубина по CV: {best_depth}")

Визуализация дерева

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

fig, ax = plt.subplots(figsize=(16, 8))
plot_tree(
    dt,
    feature_names=iris.feature_names,
    class_names=iris.target_names,
    filled=True,
    rounded=True,
    ax=ax
)
plt.title("Дерево решений для набора Iris (max_depth=4)")
plt.tight_layout()
plt.savefig("decision_tree_iris.png", dpi=150)

# Текстовое представление
print(export_text(dt, feature_names=list(iris.feature_names)))

Важность признаков

CART вычисляет важность каждого признака как суммарное взвешенное уменьшение нечистоты по всем разбиениям, где этот признак использовался:

# Важность признаков
importances = dt.feature_importances_
indices = np.argsort(importances)[::-1]

print("Важность признаков:")
for i in range(X.shape[1]):
    print(f"  {iris.feature_names[indices[i]]}: {importances[indices[i]]:.4f}")

Деревья для регрессии

DecisionTreeRegressor работает аналогично, но критерий разбиения — дисперсия (variance) или MAE:

from sklearn.tree import DecisionTreeRegressor

dtr = DecisionTreeRegressor(
    max_depth=5,
    min_samples_leaf=10,
    criterion='squared_error'
)
dtr.fit(X_train, y_train)

# Предсказание листа: среднее значение y объектов в листе
y_pred = dtr.predict(X_test)

От деревьев к ансамблям

Одиночное дерево имеет фундаментальный компромисс: глубокое дерево — низкий bias, высокая variance; мелкое — высокий bias, низкая variance. Решение этого компромисса — ансамблевые методы:

• Random Forest — усредняет предсказания многих независимых деревьев, снижая variance
• Gradient Boosting (XGBoost, LightGBM) — строит деревья последовательно, каждое исправляет ошибки предыдущего, снижая bias

Оба метода используют деревья как базовые алгоритмы, поэтому понимание принципов CART критически важно для работы с этими мощными инструментами.

Итог урока

Дерево решений — интерпретируемый, нелинейный алгоритм, строящий иерархические правила разбиения. Ключевой риск — переобучение без ограничений. Контроль глубины и других гиперпараметров — обязательная часть обучения деревьев. Понимание CART — база для освоения Random Forest и Gradient Boosting.