Как строится дерево

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

Как это работает

Алгоритм построения дерева состоит из трёх основных шагов, которые повторяются для каждого узла:

1. Выбор признака для разделения. На каждом шаге выбирается признак, который наилучшим образом разделяет данные по целевой переменной. Для этого используются метрики качества разделения.
2. Разделение данных. Узел разбивается на дочерние узлы по значениям выбранного признака. Для числовых признаков обычно выбирается порог, для категориальных — группы значений.
3. Рекурсивное повторение. Для каждого дочернего узла процесс повторяется, пока не сработает критерий остановки.

Критерии выбора признака

Выбор признака зависит от типа задачи:

• Классификация:
  • Прирост информации (Information Gain) — уменьшение энтропии после разделения. Энтропия измеряет неопределённость в данных: чем меньше энтропия, тем однороднее классы. Прирост информации = энтропия до разделения − средневзвешенная энтропия после.
  • Коэффициент Джини (Gini Impurity) — вероятность неправильной классификации случайно выбранного элемента, если его метку назначить случайно по распределению классов в узле. Чем меньше Джини, тем чище разделение.
• Регрессия:
  • Снижение дисперсии (Variance Reduction) — выбор признака, который максимально уменьшает дисперсию целевой переменной в дочерних узлах. Дисперсия — мера разброса значений, её снижение означает более однородные подгруппы.

Критерии остановки

Разделение прекращается, если выполняется хотя бы одно из условий:

• Все объекты в узле принадлежат одному классу (или целевая переменная постоянна).
• Не осталось признаков для разделения (все признаки уже использованы или одинаковы).
• Достигнута максимальная глубина дерева (параметр max_depth).
• Число объектов в узле меньше заданного порога (параметр min_samples_split).
• Достигнуто минимальное число объектов в листе (параметр min_samples_leaf).

Пример на Python

Библиотека scikit-learn предоставляет готовую реализацию DecisionTreeClassifier и DecisionTreeRegressor. Пример построения дерева для классификации ирисов:

from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split
from sklearn.tree import plot_tree
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)

# Создание и обучение дерева с ограничением глубины
clf = DecisionTreeClassifier(max_depth=3, random_state=42)
clf.fit(X_train, y_train)

# Визуализация дерева
plt.figure(figsize=(20, 10))
plot_tree(clf, filled=True, feature_names=iris.feature_names, class_names=iris.target_names)
plt.show()

Подводные камни

• Переобучение. Без ограничений дерево может идеально запомнить обучающую выборку, но плохо обобщаться. Используйте max_depth, min_samples_split, min_samples_leaf или обрезку (pruning).
• Неустойчивость. Небольшие изменения в данных могут привести к совершенно другому дереву. Это снижает интерпретируемость и надёжность.
• Смещение к признакам с большим числом значений. Признаки с множеством уникальных значений (например, ID) могут быть выбраны чаще, так как они хорошо разделяют данные, но не несут полезной информации. Это можно компенсировать ограничением глубины или использованием случайных лесов.
• Обработка пропусков. Базовые деревья в scikit-learn не поддерживают пропуски, их нужно предварительно заполнять.

Коротко

• Дерево строится рекурсивным разделением данных по признакам, выбираемым по метрике качества (энтропия, Джини, дисперсия).
• Остановка происходит при однородности узла, исчерпании признаков, достижении максимальной глубины или минимального числа объектов.
• В Python деревья реализованы в sklearn.tree.DecisionTreeClassifier и DecisionTreeRegressor.
• Главные риски — переобучение и неустойчивость; их смягчают ограничением глубины и ансамблевыми методами.