Лекция 7. Деревья решений

Цель лекции. Изучить устройство и принцип обучения деревьев решений, критерии выбора разбиений, способы прогнозирования для задач классификации и регрессии. Рассмотреть переобучение, ограничение сложности дерева и практическое применение в Python.

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

1. Понятие и структура дерева решений

Дерево решений (Decision Tree) — алгоритм машинного обучения с учителем, который последовательно разделяет данные на группы по значениям признаков. Его можно представить как последовательность вопросов, ответы на которые приводят к итоговому прогнозу.

Например, при прогнозировании одобрения кредита дерево может сначала проверять доход клиента, затем наличие задолженности и в конце выдавать решение.

Структура дерева включает:

•             Корневой узел — первый вопрос, с которого начинается прогноз.

•             Внутренние узлы — проверки условий по признакам.

•             Ветви — результаты проверок.

•             Листья — конечные узлы, содержащие прогноз.

Для числового признака проверка обычно имеет вид:

Здесь  — значение выбранного признака, а  — порог разделения.

Объекты, удовлетворяющие условию, переходят в одну ветвь, остальные — в другую. Процесс повторяется до достижения листа.

Главное преимущество дерева — интерпретируемость: путь от корня к листу можно прочитать как набор логических правил.

2. Построение дерева и критерии разбиения

При обучении алгоритм выбирает признак и порог, позволяющие получить более однородные группы объектов. Для классификации однородность означает преобладание одного класса.

Индекс Джини

Индекс Джини (Gini Impurity) оценивает неоднородность распределения классов в узле:

где  — количество классов, а  — доля объектов класса  в рассматриваемом узле.

Если все объекты принадлежат одному классу, индекс Джини равен нулю. Для двух классов с равными долями он равен 0,5.

Например, если в узле 80% объектов класса 1 и 20% класса 0:

Энтропия

Другой критерий — энтропия (Entropy):

При вычислении принято считать слагаемое  равным нулю.

Чем меньше энтропия, тем однороднее узел. Для бинарного узла с равными долями классов энтропия равна 1 биту.

Прирост информации

Качество разбиения можно оценить через уменьшение энтропии:

Здесь  — исходный узел,  и  — его дочерние узлы,  и  — числа объектов в дочерних узлах, .

Алгоритм стремится выбирать разбиения, уменьшающие неоднородность. В scikit-learn для классификации доступны, в частности, критерии gini, entropy и log_loss.

3. Деревья классификации и регрессии

Дерево классификации прогнозирует категориальную метку. В листе обычно выбирается класс, наиболее часто встречающийся среди обучающих объектов этого листа. Также можно получить оценки вероятностей классов на основе их долей.

Дерево регрессии прогнозирует числовое значение. В стандартном варианте с критерием квадратичной ошибки прогноз листа равен среднему значению целевой переменной объектов этого листа:

где  — число объектов в листе.

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

Разные критерии регрессии могут приводить к другим способам вычисления прогнозов. В частности, при использовании абсолютной ошибки оптимальным значением листа является медиана.

Характеристика

Классификация

Регрессия

Целевая переменная

Категория

Число

Типичный прогноз листа

Наиболее частый класс

Среднее значение

Пример

Одобрить кредит или отказать

Прогнозировать стоимость жилья

Пример критерия

Джини, энтропия

Квадратичная ошибка

4. Глубина дерева и проблема переобучения

Если не ограничивать рост дерева, оно может запомнить отдельные обучающие объекты и случайный шум. Такое состояние называется переобучением (Overfitting).

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

Основные параметры управления сложностью:

•             max_depth — максимальная глубина дерева.

•             min_samples_split — минимальное число объектов, необходимое для разбиения узла.

•             min_samples_leaf — минимальное число объектов в листе.

•             max_leaf_nodes — максимальное количество листьев.

•             ccp_alpha — параметр обрезки дерева по стоимости сложности.

Например, при max_depth=3 дерево не сможет строить цепочки разбиений глубже трёх уровней.

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

5. Обрезка дерева и интерпретация решений

Обрезка дерева (Pruning) — уменьшение его сложности путём удаления части ветвей.

Различают два подхода:

1.          Предварительное ограничение роста — обучение дерева сразу с ограничениями на глубину, размер узлов или количество листьев.

2.          Последующая обрезка — сначала строится дерево, затем удаляются ветви, вклад которых не оправдывает увеличение сложности.

В scikit-learn применяется минимальная стоимостно-сложностная обрезка (Minimal Cost-Complexity Pruning), управляемая параметром ccp_alpha. Упрощённо её цель можно записать так:

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

Увеличение  обычно приводит к более компактному дереву.

Интерпретация

Деревья позволяют визуализировать условия, ведущие к прогнозу. Это удобно для объяснения решений пользователям и экспертам предметной области.

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

6. Практическая реализация на Python

Рассмотрим классификацию цветов ириса с помощью DecisionTreeClassifier из библиотеки scikit-learn.

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier, plot_tree
from sklearn.metrics import accuracy_score, classification_report
import matplotlib.pyplot as plt

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.2,
    random_state=42,
    stratify=y
)

model = DecisionTreeClassifier(
    criterion="gini",
    max_depth=3,
    random_state=42
)

model.fit(X_train, y_train)
predictions = model.predict(X_test)

print("Accuracy:", accuracy_score(y_test, predictions))
print(classification_report(y_test, predictions))

plt.figure(figsize=(12, 7))
plot_tree(
    model,
    feature_names=iris.feature_names,
    class_names=iris.target_names,
    filled=True,
    rounded=True
)
plt.tight_layout()
plt.show()

Объяснение примера. Данные Iris разделяются на обучающую и тестовую выборки с сохранением пропорций классов. Создаётся дерево с критерием Джини и ограничением глубины до трёх уровней. После обучения рассчитываются метрики классификации и строится визуальная схема дерева.

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

Эксперимент с глубиной дерева

Чтобы сравнить глубины без подбора по тестовой выборке, используем перекрёстную проверку на обучающих данных:

from sklearn.model_selection import cross_val_score

for depth in [1, 2, 3, 5, None]:
    candidate = DecisionTreeClassifier(
        max_depth=depth,
        random_state=42
    )
    scores = cross_val_score(
        candidate, X_train, y_train,
        cv=5, scoring="accuracy"
    )
    print(f"Глубина {depth}: {scores.mean():.3f}")

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

7. Практическое значение и выводы

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

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

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