Как работает дерево?

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

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

Базовая структура дерева

Дерево состоит из трёх типов узлов:

1. Корневой узел (Root Node)

• Самый верхний узел, с которого начинается процесс
• Содержит признак, который максимально хорошо разделяет данные

2. Внутренние узлы (Internal Nodes)

• Содержат условие разделения (например, age > 30)
• Имеют ровно две ветви: левую (true) и правую (false)

3. Листовые узлы (Leaf Nodes)

• Конечные узлы, содержащие предсказание
• Для классификации — класс, для регрессии — числовое значение

Процесс построения дерева

Шаг 1: Выбор лучшего признака для разделения

Алгоритм оценивает каждый признак по критериям информационного выигрыша (Information Gain) или индекса Gini:

from sklearn.tree import DecisionTreeClassifier
import numpy as np

# Создание простого датасета
X = np.array([
    [2.5, 2.4],
    [0.5, 0.7],
    [2.2, 2.9],
    [1.9, 2.2],
    [3.1, 3.0],
    [2.3, 0.2]
])
y = np.array([0, 0, 1, 1, 1, 0])

# Обучение дерева
dt = DecisionTreeClassifier(max_depth=3, criterion='gini')
dt.fit(X, y)

Шаг 2: Рекурсивное разделение

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

• Вычисляет информационный выигрыш для каждого признака
• Выбирает признак с максимальным выигрышом
• Разделяет данные по этому признаку
• Повторяет процесс для каждой ветви

Шаг 3: Остановка

Процесс разделения останавливается при:

• Достижении максимальной глубины дерева (max_depth)
• Когда узел содержит минимальное количество образцов (min_samples_split)
• Когда все объекты в узле принадлежат одному классу (чистота)

Пример работы дерева на реальных данных

from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier, plot_tree
import matplotlib.pyplot as plt

# Загрузка данных
iris = load_iris()
X = iris.data[:, :2]  # Берём только 2 признака для простоты
y = iris.target

# Обучение дерева
dt = DecisionTreeClassifier(max_depth=3, random_state=42)
dt.fit(X, y)

# Визуализация
plt.figure(figsize=(20, 10))
plot_tree(dt, feature_names=iris.feature_names[:2], 
          class_names=iris.target_names, filled=True)
plt.show()

# Предсказание
new_sample = [[5.5, 3.2]]
prediction = dt.predict(new_sample)
print(f"Предсказание: {iris.target_names[prediction[0]]}")

Критерии разделения

Информационный выигрыш (Information Gain)

Основывается на энтропии — мере "запутанности" в узле:

Entropy(S) = -Σ p_i * log2(p_i)

Gain(S, A) = Entropy(S) - Σ (|S_v|/|S|) * Entropy(S_v)

Где:

• p_i — доля образцов класса i
• S_v — подмножество образцов для значения v признака A

Индекс Gini

Другой критерий, быстрее вычисляется:

Gini(S) = 1 - Σ (n_i/n)²

По умолчанию scikit-learn использует Gini.

Пример пошагового разделения

Представим набор данных с 6 образцами (3 класса A, 3 класса B):

Узел 1 (Root)

┌─ 6 образцов: 3 класс A, 3 класс B (Gini = 0.5)
├─ Проверяем feature_1 > 5:
│  ├─ LEFT: 4 образца (2 A, 2 B) → Gini = 0.5
│  └─ RIGHT: 2 образца (1 A, 1 B) → Gini = 0.5
│     (выигрыш = 0)
├─ Проверяем feature_2 > 3:
│  ├─ LEFT: 5 образцов (3 A, 2 B) → Gini = 0.48
│  └─ RIGHT: 1 образец (0 A, 1 B) → Gini = 0
│     (выигрыш = 0.5 - (5/6*0.48 + 1/6*0) = 0.1)
│
└─ Выбираем feature_2 > 3 (максимальный выигрыш)

Преимущества деревьев решений

• Интерпретируемость: Легко объяснить решение — просто следуешь по ветвям
• Универсальность: Работают для классификации и регрессии
• Неалогичность признаков: Не требуют масштабирования признаков
• Нелинейность: Естественно захватывают нелинейные связи
• Категориальные данные: Могут работать с категориями без кодирования

Недостатки

# Переобучение (overfitting)
dt_deep = DecisionTreeClassifier(max_depth=None)  # Глубокое дерево
dt_deep.fit(X_train, y_train)
print(f"Train accuracy: {dt_deep.score(X_train, y_train)}")  # 100%
print(f"Test accuracy: {dt_deep.score(X_test, y_test)}")    # 65%

# Решение: ограничить глубину
dt_shallow = DecisionTreeClassifier(max_depth=5)
dt_shallow.fit(X_train, y_train)
print(f"Train accuracy: {dt_shallow.score(X_train, y_train)}")  # 85%
print(f"Test accuracy: {dt_shallow.score(X_test, y_test)}")    # 82%

• Переобучение: Особенно на малых датасетах
• Нестабильность: Маленькие изменения в данных могут привести к совершенно другому дереву
• Смещение класса: Плохо работает на несбалансированных данных

Регуляризация деревьев

dt = DecisionTreeClassifier(
    max_depth=10,                # Максимальная глубина
    min_samples_split=10,        # Минимум образцов для разделения
    min_samples_leaf=5,          # Минимум образцов в листе
    max_features=None,           # Количество признаков для рассмотрения
    criterion='gini',            # Критерий разделения
    random_state=42
)
dt.fit(X_train, y_train)

Ensemble методы для улучшения

from sklearn.ensemble import RandomForestClassifier, GradientBoostingClassifier

# Random Forest — множество деревьев с усреднением
rf = RandomForestClassifier(n_estimators=100, random_state=42)
rf.fit(X_train, y_train)

# Gradient Boosting — последовательное построение деревьев
gb = GradientBoostingClassifier(n_estimators=100, random_state=42)
gb.fit(X_train, y_train)

print(f"RF accuracy: {rf.score(X_test, y_test)}")
print(f"GB accuracy: {gb.score(X_test, y_test)}")

Визуализация процесса принятия решения

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

plt.figure(figsize=(25, 15))
plot_tree(dt, 
          feature_names=X.columns,
          class_names=['Class 0', 'Class 1'],
          filled=True,
          rounded=True,
          fontsize=10)
plt.show()

Деревья решений — фундамент для понимания более сложных алгоритмов вроде Random Forest, Gradient Boosting и XGBoost. Их простота в интерпретации делает их отличным выбором для объяснения моделей бизнесу.