Деревья решений и случайные леса

Дерево решений — это всего лишь блок-схема. Но лес из таких деревьев — один из самых мощных инструментов в ML.

Тип: Практика Язык: Python Предварительные требования: Фаза 1 (уроки 09 «Теория информации», 06 «Вероятность») Время: ~90 минут

Цели обучения

• Реализовать вычисления неоднородности Джини, энтропии и информационного выигрыша, чтобы находить оптимальные разбиения дерева решений
• Построить с нуля классификатор на дереве решений с контролем предварительного отсечения (максимальная глубина, минимальное число примеров)
• Построить случайный лес с помощью бутстреп-выборки и рандомизации признаков и объяснить, почему это снижает дисперсию
• Сравнить важность признаков MDI с важностью перестановки и определить, когда MDI даёт смещённую оценку

Проблема

У вас есть табличные данные. Строки — это примеры, столбцы — признаки, а также есть целевой столбец, который нужно предсказать. Можно применить к ним нейросеть. Но на табличных данных модели на основе деревьев (деревья решений, случайные леса, деревья с градиентным бустингом) стабильно превосходят глубокое обучение. В соревнованиях Kaggle со структурированными данными доминируют XGBoost и LightGBM, а не трансформеры.

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

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

Концепция

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

Дерево решений делит пространство признаков на прямоугольные области, задавая последовательность вопросов «да/нет».

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

Дерево строится сверху вниз: в каждом узле выбираются признак и порог, которые лучше всего разделяют данные. Понятие «лучше всего» задаётся критерием разбиения.

Критерии разбиения: измерение неоднородности

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

Неоднородность Джини (Gini impurity) измеряет вероятность неверной классификации случайно выбранного примера, если его метку назначать в соответствии с распределением классов в этом узле.

Gini(S) = 1 - sum(p_k^2)

where p_k is the proportion of class k in set S.

Для чистого узла (все примеры относятся к одному классу) Gini = 0. Для бинарного разбиения с классами в пропорции 50/50 Gini = 0.5. Меньше — лучше.

Example: 6 cats, 4 dogs

Gini = 1 - (0.6^2 + 0.4^2) = 1 - (0.36 + 0.16) = 0.48

Энтропия (entropy) измеряет информационное содержание (беспорядок) в узле. Она рассмотрена в уроке 09 фазы 1.

Entropy(S) = -sum(p_k * log2(p_k))

Для чистого узла энтропия = 0. Для бинарного разбиения 50/50 энтропия = 1.0. Меньше — лучше.

Example: 6 cats, 4 dogs

Entropy = -(0.6 * log2(0.6) + 0.4 * log2(0.4))
        = -(0.6 * -0.737 + 0.4 * -1.322)
        = 0.442 + 0.529
        = 0.971 bits

Информационный выигрыш (information gain) — это уменьшение неоднородности (энтропии или Джини) после разбиения.

IG(S, feature, threshold) = Impurity(S) - weighted_avg(Impurity(S_left), Impurity(S_right))

where the weights are the proportions of samples in each child.

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

Как работает разбиение

Для набора данных с n признаками и m примерами в текущем узле:

1. Для каждого признака j (j = 1 до n):
   • Отсортируйте примеры по признаку j
   • Рассмотрите в качестве порога каждую середину между последовательными различными значениями
   • Вычислите информационный выигрыш для каждого порога
2. Выберите признак и порог с наибольшим информационным выигрышем
3. Разделите данные на левую часть (feature <= threshold) и правую часть (feature > threshold)
4. Рекурсивно повторите процедуру для каждого дочернего узла

Этот жадный подход не гарантирует глобально оптимальное дерево. Поиск оптимального дерева является NP-трудной задачей. Но на практике жадное разбиение работает хорошо.

Условия остановки

Без условий остановки дерево растёт, пока каждый лист не станет чистым (по одному примеру в листе). Оно идеально запоминает обучающие данные и очень плохо обобщает.

Предварительное отсечение (pre-pruning) останавливает дерево до его полного роста:

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

Последующее отсечение (post-pruning) сначала выращивает полное дерево, а затем сокращает его:

• Отсечение по соотношению стоимости и сложности (используется scikit-learn): добавляет штраф, пропорциональный числу листьев. Увеличивайте штраф, чтобы получать меньшие деревья
• Отсечение по уменьшению ошибки: удаляйте поддерево, если ошибка валидации не возрастает

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

Деревья решений для регрессии

В регрессии предсказание листа — среднее целевых значений в этом листе. Меняется и критерий разбиения:

Уменьшение дисперсии (variance reduction) заменяет информационный выигрыш:

VR(S, feature, threshold) = Var(S) - weighted_avg(Var(S_left), Var(S_right))

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

Случайные леса: сила ансамблей

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

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

Бэггинг (bagging, bootstrap aggregating): каждое дерево обучается на бутстреп-выборке — случайной выборке с возвращением из обучающих данных. В каждом бутстрепе появляется около 63% исходных примеров (остальные — примеры out-of-bag, которые можно использовать для валидации).

Рандомизация признаков: при каждом разбиении рассматривается только случайное подмножество признаков. Для классификации по умолчанию это sqrt(n_features). Для регрессии — n_features/3. Это не позволяет всем деревьям разбиваться по одному и тому же доминирующему признаку.

Главная идея: усреднение множества декоррелированных деревьев уменьшает дисперсию, не увеличивая смещение. Каждое отдельное дерево может быть посредственным. Ансамбль получается сильным.

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

Случайные леса естественным образом предоставляют оценки важности признаков. Наиболее распространённый метод:

Среднее уменьшение неоднородности (Mean Decrease in Impurity, MDI): для каждого признака суммируйте общее уменьшение неоднородности по всем деревьям и всем узлам, где используется этот признак. Признаки, дающие большее уменьшение неоднородности на ранних разбиениях, важнее.

importance(feature_j) = sum over all nodes where feature_j is used:
    (n_samples_at_node / n_total_samples) * impurity_decrease

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

Важность перестановки (permutation importance) — альтернатива: перемешайте значения одного признака и измерьте, насколько упала точность модели. Этот способ надёжнее, но медленнее.

Когда деревья превосходят нейронные сети

Деревья и леса превосходят нейронные сети на табличных данных. На это есть несколько причин:

Фактор	Деревья	Нейронные сети
Смешанные типы (числовые + категориальные)	Нативная поддержка	Нужно кодирование
Малые наборы данных (< 10k строк)	Работают хорошо	Переобучаются
Взаимодействия признаков	Находятся разбиениями	Нужно проектировать архитектуру
Интерпретируемость	Полная прозрачность	Чёрный ящик
Время обучения	Минуты	Часы
Чувствительность к гиперпараметрам	Низкая	Высокая

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

decision-tree-depth

Соберите это

Шаг 1: неоднородность Джини и энтропия

Постройте оба критерия разбиения с нуля и убедитесь, что они согласуются в оценке хороших разбиений.

import math

def gini_impurity(labels):
    n = len(labels)
    if n == 0:
        return 0.0
    counts = {}
    for label in labels:
        counts[label] = counts.get(label, 0) + 1
    return 1.0 - sum((c / n) ** 2 for c in counts.values())

def entropy(labels):
    n = len(labels)
    if n == 0:
        return 0.0
    counts = {}
    for label in labels:
        counts[label] = counts.get(label, 0) + 1
    return -sum(
        (c / n) * math.log2(c / n) for c in counts.values() if c > 0
    )

Шаг 2: найдите лучшее разбиение

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

def information_gain(parent_labels, left_labels, right_labels, criterion="gini"):
    measure = gini_impurity if criterion == "gini" else entropy
    n = len(parent_labels)
    n_left = len(left_labels)
    n_right = len(right_labels)
    if n_left == 0 or n_right == 0:
        return 0.0
    parent_impurity = measure(parent_labels)
    child_impurity = (
        (n_left / n) * measure(left_labels) +
        (n_right / n) * measure(right_labels)
    )
    return parent_impurity - child_impurity

Шаг 3: постройте класс DecisionTree

Рекурсивное разбиение, предсказание и отслеживание важности признаков.

class DecisionTree:
    def __init__(self, max_depth=None, min_samples_split=2,
                 min_samples_leaf=1, criterion="gini",
                 max_features=None):
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.min_samples_leaf = min_samples_leaf
        self.criterion = criterion
        self.max_features = max_features
        self.tree = None
        self.feature_importances_ = None

    def fit(self, X, y):
        self.n_features = len(X[0])
        self.feature_importances_ = [0.0] * self.n_features
        self.n_samples = len(X)
        self.tree = self._build(X, y, depth=0)
        total = sum(self.feature_importances_)
        if total > 0:
            self.feature_importances_ = [
                fi / total for fi in self.feature_importances_
            ]

    def predict(self, X):
        return [self._predict_one(x, self.tree) for x in X]

Шаг 4: постройте класс RandomForest

Бутстреп-выборка, рандомизация признаков и голосование большинством.

class RandomForest:
    def __init__(self, n_trees=100, max_depth=None,
                 min_samples_split=2, max_features="sqrt",
                 criterion="gini"):
        self.n_trees = n_trees
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.max_features = max_features
        self.criterion = criterion
        self.trees = []

    def fit(self, X, y):
        n = len(X)
        for _ in range(self.n_trees):
            indices = [random.randint(0, n - 1) for _ in range(n)]
            X_boot = [X[i] for i in indices]
            y_boot = [y[i] for i in indices]
            tree = DecisionTree(
                max_depth=self.max_depth,
                min_samples_split=self.min_samples_split,
                max_features=self.max_features,
                criterion=self.criterion,
            )
            tree.fit(X_boot, y_boot)
            self.trees.append(tree)

    def predict(self, X):
        all_preds = [tree.predict(X) for tree in self.trees]
        predictions = []
        for i in range(len(X)):
            votes = {}
            for preds in all_preds:
                v = preds[i]
                votes[v] = votes.get(v, 0) + 1
            predictions.append(max(votes, key=votes.get))
        return predictions

Полная реализация со всеми вспомогательными методами находится в code/trees.py.

Используйте это

В scikit-learn обучение случайного леса занимает три строки:

from sklearn.ensemble import RandomForestClassifier
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split

X, y = load_iris(return_X_y=True)
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=42)

rf = RandomForestClassifier(n_estimators=100, random_state=42)
rf.fit(X_train, y_train)
print(f"Accuracy: {rf.score(X_test, y_test):.4f}")
print(f"Feature importances: {rf.feature_importances_}")

На практике деревья с градиентным бустингом (XGBoost, LightGBM, CatBoost) часто сильнее случайных лесов, потому что строят деревья последовательно: каждое следующее дерево исправляет ошибки предыдущего. Но случайные леса сложнее неверно настроить, и им почти не требуется подбор гиперпараметров.

Внедрите это

Этот урок создаёт outputs/prompt-tree-interpreter.md — промпт, который интерпретирует разбиения дерева решений для бизнес-заинтересованных сторон. Передайте ему структуру обученного дерева (глубину, признаки, пороги разбиения, точность), и он переведёт модель в правила на понятном языке, ранжирует важность признаков, отметит переобучение или утечку и порекомендует следующие шаги. Используйте его всякий раз, когда нужно объяснить модель на основе деревьев человеку, который не читает код.

Упражнения

1. Обучите одно дерево решений на двумерном наборе данных с тремя классами. Вручную проследите разбиения и нарисуйте прямоугольные границы решений. Сравните границы при max_depth=2 и max_depth=10.

2. Реализуйте разбиение по уменьшению дисперсии для регрессионных деревьев. Сгенерируйте y = sin(x) + noise для 200 точек и обучите своё регрессионное дерево. Постройте график кусочно-постоянных предсказаний дерева вместе с истинной кривой.

3. Постройте случайный лес с 1, 5, 10, 50 и 200 деревьями. Постройте график точности на обучении и тесте в зависимости от числа деревьев. Заметьте, что точность на тесте выходит на плато, но не снижается (леса устойчивы к переобучению).

4. Сравните неоднородность Джини и энтропию как критерии разбиения на 5 разных наборах данных. Измерьте точность и глубину дерева. В большинстве случаев они дают почти одинаковые результаты. Объясните почему.

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

Ключевые термины

Термин	Как обычно говорят	Что это на самом деле означает
Дерево решений	«Блок-схема для предсказаний»	Модель, которая делит пространство признаков на прямоугольные области, изучая последовательность разбиений if/else
Неоднородность Джини	«Насколько смешан узел»	Вероятность ошибочно классифицировать случайный пример в узле. 0 = чистый; 0.5 = максимальная неоднородность для бинарного случая
Энтропия	«Беспорядок в узле»	Информационное содержание узла. 0 = чистый; 1.0 = максимальная неопределённость для бинарного случая. Происходит из теории информации
Информационный выигрыш	«Насколько хорошо разбиение»	Уменьшение неоднородности после разбиения. Жадный критерий выбора разбиений
Предварительное отсечение	«Остановить дерево рано»	Ранняя остановка роста дерева установкой порогов максимальной глубины, минимального числа примеров или минимального выигрыша
Последующее отсечение	«Обрезать дерево после»	Выращивание полного дерева с последующим удалением поддеревьев, не улучшающих качество на валидации
Бэггинг	«Обучать на случайных подмножествах»	Bootstrap aggregating: обучение каждой модели на отдельной случайной выборке с возвращением
Случайный лес	«Куча деревьев»	Ансамбль деревьев решений, каждое из которых обучено на бутстреп-выборке со случайными подмножествами признаков в каждом разбиении
Важность признаков (MDI)	«Какие признаки важны»	Общее уменьшение неоднородности, вносимое каждым признаком; суммируется по всем деревьям и узлам
Важность перестановки	«Перемешать и проверить»	Падение точности, когда значения признака случайно перемешиваются. Для шумовых признаков надёжнее MDI
Уменьшение дисперсии	«Регрессионная версия информационного выигрыша»	Аналог информационного выигрыша для регрессионного дерева. Выбирает разбиение, сильнее всего уменьшающее дисперсию цели
Бутстреп-выборка	«Случайная выборка с повторами»	Случайная выборка с возвращением из исходного набора данных. Того же размера, но с дубликатами

Дополнительное чтение

• Breiman: Random Forests (2001) — оригинальная статья о случайных лесах
• Grinsztajn et al.: Why do tree-based models still outperform deep learning on tabular data? (2022) — строгое сравнение деревьев и нейронных сетей на табличных задачах
• Документация scikit-learn: деревья решений — практическое руководство с инструментами визуализации
• XGBoost: A Scalable Tree Boosting System (Chen & Guestrin, 2016) — статья о градиентном бустинге, который доминирует в Kaggle

---

Источник: Decision Trees and Random Forests 02.03 — Логистическая регрессия · Фаза 2 — Основы машинного обучения · Полный каталог · 02.05 — Метод опорных векторов