Решающие деревья

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

Решающее дерево устроено иначе. Оно не считает расстояний и не складывает признаки с весами — оно задаёт последовательность вопросов вида «признак больше порога?», ровно как медицинский протокол сортировки пациентов или детская игра «20 вопросов». Из-за этого дерево:

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

Плата — высокая дисперсия: сдвиньте несколько объектов, и дерево может перестроиться целиком. Именно из этого недостатка вырос следующий раздел трека, так что статья одновременно и про самостоятельную модель, и про фундамент случайного леса, XGBoost, LightGBM и CatBoost.

Формальная постановка

Дерево разбивает признаковое пространство на $M$ непересекающихся областей $R_1, \dots, R_M$, покрывающих его целиком, и приписывает каждой области константу:

$$ \hat{f}(x) = \sum_{m=1}^{M} c_m \cdot \mathbb{1}[x \in R_m] $$

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

Отсюда два следствия. Диагональная граница — плохой случай: правило «выдать кредит, если доход > 3× расходы» линейная модель ловит одним весом, а дерево аппроксимирует «лесенкой» из десятков разбиений. Взаимодействия — хороший случай: правило «если регион = СЗФО И возраст < 25, то отток высокий» дерево находит естественно, а линейной модели нужен явный признак-произведение. Отсюда практический вывод: инженерная работа перед деревом — не масштабирование, а создание признаков-отношений (доход / расходы, сумма_заказа / средний_чек), потому что отношения дерево само построить не может — оно режет по одной оси за раз.

Как дерево строится: жадная рекурсия

Задача «найти дерево минимального размера с минимальной ошибкой» NP-полна (Hyafil & Rivest, 1976, Constructing optimal binary decision trees is NP-complete), поэтому используется жадный алгоритм: на каждом шаге берём локально лучшее разбиение и никогда не пересматриваем прошлые решения.

Псевдокод того же самого (вся содержательная часть спрятана в impurity — мере неоднородности узла):

build(S, depth):
    if stop(S, depth) : return Leaf(summary(S))
    (j*, t*, gain*) = argmax over (j, t) of  impurity(S) - weighted_impurity(split(S, j, t))
    if gain* <= min_gain : return Leaf(summary(S))
    S_L, S_R = split(S, j*, t*)
    return Node(j*, t*, build(S_L, depth+1), build(S_R, depth+1))

Критерии неоднородности

Пусть в узле доля объектов класса $k$ равна $p_k$. Три классических критерия:

$$ G = 1 - \sum_k p_k^2, \qquad H = -\sum_k p_k \log_2 p_k, \qquad E = 1 - \max_k p_k $$

Выигрыш от разбиения (information gain) — разность неоднородности родителя и взвешенной суммы неоднородностей потомков:

$$ \Delta = I(S) - \frac{|S_L|}{|S|} I(S_L) - \frac{|S_R|}{|S|} I(S_R) $$

Джини имеет вероятностный смысл: $G$ — вероятность ошибиться, предсказывая класс вытягиванием метки случайно из распределения в узле; эквивалентно — вероятность того, что два случайно взятых объекта узла принадлежат разным классам. Энтропия — средняя длина оптимального кода в битах для метки класса, а information gain буквально означает «сколько бит информации о таргете даёт ответ на вопрос»; отсюда название критерия в ID3/C4.5.

Ошибка классификации почти не используется для роста дерева, и это принципиально: она кусочно-линейна и потому не различает интуитивно очень разные разбиения. Пример из ESL: узел из 800 объектов, 400/400; разбиение A даёт (300/100) и (100/300), разбиение B — (200/400) и (200/0). По ошибке классификации выигрыш одинаков (0.25), хотя B выделило идеально чистый узел. Джини и энтропия строго вогнуты и такие «чистящие» разбиения предпочитают. Для обрезки ошибка классификации годится — там важна финальная метрика, а не градиент улучшения.

Джини vs энтропия. Разница почти всегда в пределах шума (на графике $H/2$ и Джини почти совпадают): энтропия чуть сильнее наказывает неоднородность и строит чуть более сбалансированные деревья, Джини считается быстрее. Подбирать критерий — потерянное время, лучше настраивать глубину.

Для регрессии — аналоги:

$$ I_{\text{MSE}}(S) = \frac{1}{|S|}\sum_{i \in S}(y_i - \bar{y}_ S)^2, \qquad I_{\text{MAE}}(S) = \frac{1}{|S|}\sum_{i \in S}|y_i - \text{med}(y_S)| $$

MSE-критерий эквивалентен максимизации уменьшения суммы квадратов и считается инкрементально через префиксные суммы $\sum y$ и $\sum y^2$ — поэтому он в разы быстрее MAE, где на каждый порог нужна медиана: criterion="absolute_error" в scikit-learn заметно медленнее.

Реализация с нуля

Наивный перебор порогов стоит $O(n^2)$ на признак; правильная реализация сортирует значения один раз и идёт по ним слева направо, инкрементально обновляя счётчики классов — $O(n \log n)$.

import numpy as np

# Узел — обычный dict: лист хранит только "value", внутренний узел ещё и правило.

def gini(counts, n):
    p = counts / n
    return 1.0 - np.dot(p, p)


def best_split(X, y, n_classes, min_samples_leaf):
    """Лучшее осевое разбиение по уменьшению Джини. O(d * n log n)."""
    n, d = X.shape
    parent = np.bincount(y, minlength=n_classes).astype(np.float64)
    base = gini(parent, n)
    best = (0.0, None, None)                       # (выигрыш, признак, порог)

    for f in range(d):
        order = np.argsort(X[:, f], kind="mergesort")
        xs, ys = X[order, f], y[order]
        left, right = np.zeros(n_classes), parent.copy()

        for i in range(n - 1):                     # i — последний объект, уходящий налево
            left[ys[i]] += 1.0
            right[ys[i]] -= 1.0
            if xs[i] == xs[i + 1]:
                continue                           # порог между равными значениями бессмыслен
            n_left, n_right = i + 1, n - i - 1
            if n_left < min_samples_leaf or n_right < min_samples_leaf:
                continue
            child = (n_left * gini(left, n_left) + n_right * gini(right, n_right)) / n
            if base - child > best[0]:
                best = (base - child, f, 0.5 * (xs[i] + xs[i + 1]))

    return best


def build(X, y, n_classes, n_total, depth=0,
          max_depth=8, min_samples_split=2, min_samples_leaf=1, min_gain=0.0):
    n = len(y)
    counts = np.bincount(y, minlength=n_classes).astype(np.float64)
    node = {"value": counts / n}                       # предсказание узла

    # стоп-критерии: узел чист, слишком мал или достигнута максимальная глубина
    if depth >= max_depth or n < min_samples_split or counts.max() == n:
        return node

    gain, f, t = best_split(X, y, n_classes, min_samples_leaf)
    # sklearn взвешивает выигрыш долей выборки в узле — делаем так же
    if f is None or (n / n_total) * gain < min_gain:
        return node

    mask = X[:, f] <= t
    kw = dict(max_depth=max_depth, min_samples_split=min_samples_split,
              min_samples_leaf=min_samples_leaf, min_gain=min_gain)
    node["feature"], node["threshold"] = f, t
    node["left"] = build(X[mask], y[mask], n_classes, n_total, depth + 1, **kw)
    node["right"] = build(X[~mask], y[~mask], n_classes, n_total, depth + 1, **kw)
    return node


def predict_proba(root, X):
    out = []
    for x in np.asarray(X, dtype=np.float64):
        node = root
        while "feature" in node:                       # спуск до листа
            node = node["left"] if x[node["feature"]] <= node["threshold"] else node["right"]
        out.append(node["value"])
    return np.array(out)

Сложность. Поиск разбиения в узле — $O(d \cdot n_{\text{node}} \log n_{\text{node}})$; на каждом уровне обрабатываются все $n$ объектов, уровней у сбалансированного дерева $O(\log n)$, итого обучение $O(d \cdot n \log^2 n)$. Если отсортировать признаки один раз заранее и переносить порядок в потомков (presorting, как в старом CART) — $O(d \cdot n \log n)$ ценой $O(d \cdot n)$ памяти. Предсказание одного объекта — $O(\text{depth})$, то есть $O(\log n)$: десятки наносекунд, одна из самых быстрых инференс-моделей вообще. Память под модель — $O(#\text{узлов})$, а число узлов у нерегуляризованного дерева пропорционально $n$.

Категориальные признаки

Здесь реализации расходятся сильнее всего. Полный перебор невозможен: для признака с $k$ уровнями существует $2^{k-1} - 1$ бинарных разбиений на подмножества — при $k = 20$ полмиллиона на узел.

Трюк Бреймана. Для бинарной классификации (и регрессии с MSE) есть точное решение за $O(k \log k)$: отсортировать уровни по доле положительного класса $p(y=1 \mid \text{level})$ и перебрать только $k-1$ разрез в этом порядке — оптимальное разбиение гарантированно окажется среди них (CART, 1984, теорема 4.5). Так работает rpart в R и категориальная обработка LightGBM; для многоклассовой задачи гарантии нет, применяются эвристики.

scikit-learn категориальные признаки не поддерживает — регулярный источник ошибок. Кодируем сами:

Про механику утечек и схему out-of-fold-кодирования — в статье Данные и признаки; упорядоченное target-кодирование, свободное от утечки по построению, — центральная идея CatBoost из следующей статьи.

Пропуски

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

• Суррогатные разбиения (CART, rpart). Для узла ищется запасное разбиение по другому признаку, максимально повторяющее основное; если основной признак пропущен, используется суррогат. Дорого, зато суррогаты — готовая диагностика мультиколлинеарности.
• Дробление веса (C4.5). Объект с пропуском идёт в обе ветви с весами, пропорциональными долям обучающих объектов; предсказание становится взвешенным по листьям.
• Default direction / MIA (XGBoost, LightGBM, scikit-learn ≥ 1.3). Для каждого узла выучивается направление по умолчанию: пробуются оба варианта («все пропуски налево» / «направо») и берётся тот, что даёт больший выигрыш — sparsity-aware split finding из XGBoost: A Scalable Tree Boosting System; он же бесплатно обрабатывает разреженные данные.

Нюанс: если пропуск информативен («поле не заполнено, потому что клиент отказался»), добавляйте явный индикатор is_missing — тогда дерево использует сам факт пропуска как признак.

Переобучение и обрезка

Нерегуляризованное дерево доводит обучающую выборку до нулевой ошибки: в пределе один объект на лист — идеальный пример модели с почти нулевым смещением и огромной дисперсией (про этот баланс — Переобучение, bias-variance и регуляризация).

Pre-pruning (ранняя остановка) — гиперпараметры max_depth, min_samples_split, min_samples_leaf, max_leaf_nodes, min_impurity_decrease. Дёшево, но близоруко: разбиение с нулевым выигрышем может открывать дорогу отличному разбиению уровнем ниже (классический пример — XOR: любое одиночное разбиение бесполезно, пара решает задачу).

Post-pruning (cost-complexity pruning) — вырастить дерево целиком, а потом минимизировать штрафованный функционал:

$$ R_\alpha(T) = R(T) + \alpha \cdot |\tilde{T}| $$

где $R(T)$ — ошибка дерева (для классификации обычно взвешенная неоднородность листьев), $|\tilde{T}|$ — число листьев, $\alpha \ge 0$ — цена одного листа.

Алгоритм «слабейшего звена» (weakest link pruning): для каждого внутреннего узла $t$ считаем

$$ g(t) = \frac{R(t) - R(T_t)}{|\tilde{T_t}| - 1} $$

— во сколько обходится каждый лист поддерева $T_t$ с корнем в $t$. Узел с минимальным $g(t)$ и есть слабейшее звено: срезаем его поддерево, повторяем. Получается вложенная последовательность $T_0 \supset T_1 \supset \dots \supset {root}$ и возрастающая последовательность $\alpha$; доказано (CART, гл. 3), что она содержит оптимальное дерево для любого $\alpha$ — кросс-валидация по одному скаляру исчерпывает весь поиск.

На практике комбинируют: ставят разумный max_depth (чтобы дерево построилось за адекватное время), а тонкую настройку делают через ccp_alpha. Ниже X_tr / y_tr — обычный стратифицированный train-часть сплита (пример проверялся на датасете credit-g из OpenML).

import numpy as np
from sklearn.model_selection import cross_val_score
from sklearn.tree import DecisionTreeClassifier, export_text

# 1. Растим полное дерево и получаем путь обрезки (alpha, схлопывающую дерево в корень, отбрасываем)
full = DecisionTreeClassifier(random_state=42).fit(X_tr, y_tr)
alphas = full.cost_complexity_pruning_path(X_tr, y_tr).ccp_alphas[:-1]

# 2. Кросс-валидация по единственному скалярному параметру
scores = [cross_val_score(DecisionTreeClassifier(random_state=42, ccp_alpha=a),
                          X_tr, y_tr, cv=5, scoring="roc_auc").mean() for a in alphas]
best_alpha = alphas[int(np.argmax(scores))]

# 3. Финальная модель
tree = DecisionTreeClassifier(random_state=42, ccp_alpha=best_alpha).fit(X_tr, y_tr)
print(f"alpha* = {best_alpha:.5f}, листьев {full.get_n_leaves()} -> {tree.get_n_leaves()}")
print(export_text(tree, feature_names=list(X_tr.columns), max_depth=3))

Типичный исход: полное дерево — несколько сотен листьев и ROC-AUC на тесте около 0.6, обрезанное — десяток листьев и 0.70–0.73. Обрезка здесь не «немного помогает», а принципиально меняет результат. Про схему валидации и выбор метрики — Оценка моделей.

Важность признаков и её главная ловушка

Атрибут feature_importances_ (MDI, Mean Decrease in Impurity) суммирует по всем узлам, где признак использовался, взвешенные уменьшения неоднородности. Это удобно и систематически смещено: признак с большим числом уникальных значений даёт больше кандидатов-порогов, а значит с большей вероятностью «случайно» найдёт хорошее разбиение на шуме. Демонстрация в одну строку: добавьте колонку np.random.rand(n) — она займёт верхние строчки важности. Строгий разбор — Strobl et al., 2007, Bias in random forest variable importance measures. Второй источник смещения: MDI считается на обучающей выборке, то есть измеряет вклад в переобучение не меньше, чем вклад в качество.

from sklearn.inspection import permutation_importance

r = permutation_importance(tree, X_te, y_te,   # ВАЖНО: на отложенной выборке, не на train
                           n_repeats=30, random_state=42, scoring="roc_auc")
for i in r.importances_mean.argsort()[::-1][:10]:
    print(f"{X.columns[i]:>28}: {r.importances_mean[i]:.4f} ± {r.importances_std[i]:.4f}")

Перестановочная важность отвечает на честный вопрос «насколько упадёт метрика на новых данных, если разрушить связь признака с таргетом». Её слабость — коррелированные признаки: если два признака дублируют друг друга, перестановка одного ничего не ломает и оба выглядят бесполезными. Лечится группировкой по корреляции Спирмена (готовый рецепт есть в документации scikit-learn). Третий уровень — SHAP: вклад признака для конкретного объекта. Для деревьев есть точный алгоритм TreeSHAP полиномиальной сложности (Lundberg et al., 2018), поэтому в продовых пайплайнах с деревьями SHAP — стандарт де-факто.

Семейство алгоритмов: чем они отличаются

Три отличия, реально влияющие на выбор. Gain ratio vs information gain: ID3 предпочитал признаки с большим числом значений (в пределе — идентификатор объекта: идеально чистые листья и нулевая обобщающая способность), C4.5 исправил это, поделив выигрыш на собственную энтропию разбиения ($\text{GainRatio} = \Delta H / H(\text{split})$) — первая историческая попытка решить проблему смещения важности признаков.

Множественные vs бинарные разбиения: CHAID и ID3 создают ветвь на каждое значение категории, что быстро дробит выборку и лишает признак возможности участвовать ниже по дереву; CART строит только бинарные — деревья глубже, но статистически надёжнее. Современные реализации все бинарные.

Условный вывод (CTree): вместо «взять разбиение с максимальным выигрышем» — сначала статистический тест на независимость признака и таргета с поправкой на множественные сравнения, и только потом поиск точки разбиения. Выбор признака не смещён в пользу многозначных, а остановка роста идёт по p-value, без отдельной обрезки. Если дерево нужно как объект интерпретации, а не как предиктор, это правильный выбор (Unbiased Recursive Partitioning).

Где дерево — правильный выбор, а где нет

Дерево уместно, когда нужно правило, которое читает и утверждает человек (медицина, кредитный комитет, комплаенс); когда нужен пятиминутный baseline, чтобы понять, есть ли в данных сигнал; когда надо разведочно найти взаимодействия признаков перед построением линейной модели; когда инференс живёт в среде без ML-рантайма — дерево тривиально экспортируется в if/else, SQL CASE WHEN или правило в BPM-системе.

Дерево неуместно, когда:

• нужны калиброванные вероятности: листья дают грубые ступенчатые оценки вида «7 из 9 объектов»;
• зависимость гладкая или линейная — дерево аппроксимирует её ступеньками с большой ошибкой;
• нужна экстраполяция: вне диапазона обучения дерево вернёт константу крайнего листа, а на трендовом ряде физически не может предсказать значение выше обучающего максимума — отсюда практика предсказывать разности, а не уровни (Временные ряды);
• признаков много и они плотно коррелированы — одиночное дерево крайне нестабильно.

Типичные ошибки

1. Одиночное дерево там, где нужен лес. Дефолтное DecisionTreeClassifier() без ограничений почти всегда переобучено. Если интерпретируемость не требование — берите лес или бустинг, разница в качестве обычно 5–15 процентных пунктов.
2. Верить feature_importances_ вместо permutation importance на отложенной выборке.
3. «Дерево устойчиво, ведь оно логично выглядит». Переобучите на бутстрап-выборке — структура может измениться до неузнаваемости при том же качестве. Интерпретировать конкретные пороги как найденные законы природы нельзя.
4. Масштабировать признаки перед деревом. Бесполезно (дерево инвариантно к монотонным преобразованиям) — лишний шаг пайплайна и лишний источник расхождения train/serving.
5. One-hot на признаке с 500 категориями. Каждое разбиение отделяет одну категорию — дерево вырожденно глубокое и слабое.
6. Настраивать max_depth по обучающей ошибке. Она монотонно падает с глубиной — критерий бессмыслен. Только кросс-валидация.
7. Игнорировать class_weight на несбалансированных данных. Джини оптимизирует общую чистоту; при соотношении 1:100 дерево может честно выдать корень-лист «всегда 0».
8. Забыть random_state. При равных выигрышах scikit-learn выбирает признак случайно, так что без фиксации сида результат не воспроизводится.

Деревья в продакшене

Экспорт в правила. export_text даёт человекочитаемый дамп, export_graphviz — картинку, а рекурсивный обход tree_ (children_left/right, feature, threshold) превращает дерево во вложенный CASE WHEN: скоринг идёт прямо в хранилище, без сервиса моделей — живая практика в банковском риск-менеджменте и аналитических витринах.

Монотонные ограничения. Регуляторное требование «при росте дохода вероятность одобрения не падает» выражается напрямую: monotonic_cst в scikit-learn (с 1.4), monotone_constraints в XGBoost/LightGBM. Реализуется ограничением допустимых значений в потомках при поиске разбиения; обычно чуть снижает метрику на валидации и заметно повышает приёмку модели бизнесом. Асимметричная цена ошибок задаётся через class_weight или явные веса объектов.

Мониторинг. Распределение объектов по листьям (decision_path) — готовый детектор дрейфа: если доля трафика в конкретном листе изменилась вдвое, входное распределение сдвинулось, даже когда метрика ещё не просела (MLOps).

Оптимальные деревья. С 2019 года практичны точные методы (GOSDT, OSDT, Optimal Classification Trees на MIP): глобально оптимальное дерево заданного размера находится за минуты на десятках тысяч объектов, и на табличных данных дерево из 7–10 листьев часто не уступает лесу. Аргументация «в задачах с высокой ценой ошибки нужен не объяснённый чёрный ящик, а изначально прозрачная модель» — Cynthia Rudin, Stop Explaining Black Box Models.

Источники

• Breiman L., Friedman J., Olshen R., Stone C. Classification and Regression Trees, 1984 — первоисточник CART: критерии, обрезка, суррогаты, теорема об оптимальном порядке категорий.
• Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning, гл. 9.2 — бесплатный PDF.
• Hyafil L., Rivest R. Constructing optimal binary decision trees is NP-complete, 1976.
• Документация scikit-learn: Decision Trees — разделы про сложность и практические советы.
• Louppe G. Understanding Random Forests: From Theory to Practice, 2014 — лучший разбор математики важности признаков.
• Chen T., Guestrin C. XGBoost: A Scalable Tree Boosting System, 2016 — sparsity-aware split finding и приближённый поиск порогов.
• Hothorn T., Hornik K., Zeileis A. Unbiased Recursive Partitioning: A Conditional Inference Framework, JCGS 15(3), 2006.

Мини-итог

Решающее дерево — кусочно-постоянная функция, заданная рекурсивным осевым разбиением пространства. Строится жадно, потому что точная задача NP-полна; на каждом шаге максимизируется уменьшение неоднородности (Джини или энтропия для классификации, MSE для регрессии). Обучение — $O(d \cdot n \log^2 n)$, предсказание — $O(\text{depth})$. Главная практическая ось — регуляризация: нерегуляризованное дерево бесполезно, правильный рецепт — вырастить полностью и обрезать по ccp_alpha, подобранной кросс-валидацией. Второй рефлекс — не доверять feature_importances_, а перепроверять permutation importance на отложенной выборке. Третий вывод стратегический: у дерева низкое смещение и огромная дисперсия, а такие модели идеально усредняются — это ровно тот рычаг, за который взялись бэггинг и бустинг.

Что дальше

Ансамбли: бэггинг, случайный лес, градиентный бустинг — как из нестабильных деревьев собирается сильнейший на сегодня класс моделей для табличных данных: бутстрап и усреднение против дисперсии, последовательная коррекция остатков против смещения, и что делают XGBoost, LightGBM и CatBoost поверх того дерева, которое мы только что разобрали.