Decision Trees на собеседовании Data Scientist

Зачем разбирать на собесе

Decision tree — фундамент Random Forest, gradient boosting. Без понимания одного дерева не разобрать ансамбли. На собесе DS обязательно: «как считается Gini», «зачем pruning», «почему RF не переобучается, а одно глубокое — да». Senior — нюансы регрессионных деревьев, splitting on continuous features.

Главная боль без понимания — DS говорит «использую XGBoost», на вопрос «как gradient boosting улучшает дерево» отвечает «магия». Это junior-ответ.

Идея decision tree

Дерево — иерархия if-else правил. Каждый внутренний узел — вопрос про одну фичу («age > 30?»). Каждый лист — предсказание (класс или число).

            [age > 30?]
            /         \
          yes          no
          /             \
[income > 50k?]      class=0
    /      \
  yes       no
  /          \
class=1   class=0

Алгоритм построения (greedy):

1. На каждом узле выбрать лучший split — фичу и порог, которые максимально снижают «нечистоту».
2. Рекурсивно строить subtree для левой и правой ветки.
3. Остановиться по stopping criteria.

«Жадный» — на каждом шаге выбираем локально оптимум, не глобально. Не гарантирует оптимальное дерево, но на практике работает.

Критерии разбиения

Gini impurity. Для классификации.

Gini(node) = 1 - Σ pᵢ²

pᵢ — доля класса i в узле. Для бинарной задачи Gini = 2p(1-p) ∈ [0, 0.5].

Чисто (все класса 1): Gini = 0
50/50:                Gini = 0.5

Entropy.

H(node) = -Σ pᵢ · log₂(pᵢ)

Для бинарной задачи [0, 1].

Information Gain для split:

IG = H(parent) - Σ (|childᵢ|/|parent|) · H(childᵢ)

Best split — максимизирует IG (или минимизирует weighted impurity детей).

Gini vs Entropy. На практике почти одинаковые. Gini быстрее (не требует log). В sklearn criterion='gini' (default) или 'entropy'. Можно ещё 'log_loss' (≈ entropy).

Continuous features. Отсортировать значения, проверить все пороги (между соседними) или их подмножество. Для каждого — посчитать impurity. Выбрать лучший. O(N · log N · features).

Stopping criteria и pruning

Без ограничений дерево растёт, пока каждый лист не содержит один объект — переобучение.

Pre-pruning (stopping during growth):

• max_depth — максимальная глубина.
• min_samples_split — минимум объектов в узле для split.
• min_samples_leaf — минимум в листе.
• max_leaf_nodes — общее число листьев.
• min_impurity_decrease — минимальное улучшение impurity для split.
• max_features — сколько случайных фич рассматривать на split (это уже Random Forest territory).

Post-pruning (cost-complexity pruning). Сначала строим полное дерево, потом удаляем поддеревья с минимальным «вкладом».

R_α(T) = R(T) + α · |leaves(T)|

α — коэффициент сложности. С ростом α дерево упрощается. Подбор через CV.

В sklearn — ccp_alpha параметр. Reasonable approach для одного дерева. Для ансамблей обычно достаточно pre-pruning.

Регрессия через деревья

Регрессионное дерево предсказывает число (среднее в листе). Критерий разбиения — снижение MSE или MAE.

Var(node) = (1/N) Σ (yᵢ - ȳ)²

Best split минимизирует weighted variance детей.

В листе — среднее y обучающих объектов попавших в этот лист. Для MAE — медиана.

Поэтому регрессионное дерево даёт piecewise constant функцию. Не умеет экстраполировать за пределы trainsamples.

Плюсы и минусы

Плюсы:

• Не требует масштабирования фич.
• Естественно работает с numeric + categorical (с правильной поддержкой).
• Интерпретируемо — можно нарисовать.
• Robust к outliers (split, не среднее).
• Не требует много гиперпараметров.

Минусы:

• Высокая variance — небольшое изменение train сильно меняет дерево.
• Склонность к переобучению при большой глубине.
• Не умеет улавливать линейные зависимости элегантно — нужна piecewise approximation.
• Не экстраполирует.
• Greedy split — не глобально оптимально.

От одного дерева к ансамблю

Главное применение деревьев в 2026 — внутри ансамблей.

Random Forest — bagging + random subset features на каждом split. Снижает variance. На табличных задачах — отличный baseline.

Gradient Boosting (XGBoost / LightGBM / CatBoost) — последовательно строит деревья, каждое исправляет residuals предыдущих. Снижает bias. На табличных — обычно SOTA.

Extra Trees — Random Forest + случайный split вместо лучшего. Ещё больше variance reduction, чуть выше bias.

Один decision tree редко используют в проде. Иногда для интерпретации (regulator-friendly, простое объяснение клиенту), для quick baseline или внутри Streamlit-демки.

Частые ошибки

Не ставить random_state. Дерево детерминировано, но если есть ties в split — выбор зависит от random seed. Без seed — невоспроизводимость.

Глубокое дерево без CV. На train accuracy 100%, на val 60% — классический overfit. Проверяй через CV.

Считать важность через feature_importances_ без оговорок. Эта метрика смещена в пользу high-cardinality features. Используй permutation importance или SHAP.

Pre-process категории. Sklearn до 1.0 не поддерживал native categorical. Делали one-hot. Сейчас есть HistGradientBoostingClassifier с native cat. CatBoost — тоже native.

Не ограничивать глубину. Для одного дерева — overfit. Для RF — глубину можно не ограничивать (bagging компенсирует), для GB — обязательно (3-10).

Использовать на time series без учёта. Дерево не видит времени — нужны lag-features.

Pruning при бусте. В GB обычно не делают post-pruning одиночного дерева (дерево короткое и слабое by design).

Игнорировать missing values. Sklearn до недавнего не работал с NaN — нужен imputer. CatBoost / LightGBM / XGBoost поддерживают native — лучше использовать.

Связанные темы

• Bagging vs Boosting на собесе DS
• Bias-variance trade-off на собесе DS
• Hyperparameter tuning на собесе DS
• SHAP и interpretability на собесе DS
• Подготовка к собесу Data Scientist

FAQ

Чем дерево хуже линейной модели?

На линейных зависимостях линейная модель выигрывает (1 коэффициент vs много splits). Дерево — на нелинейных и interactions.

Можно ли использовать дерево для feature selection?

Да, через feature_importances_. Но Lasso даёт более чистый отбор (зануляет коэффициенты).

Что такое Decision Stump?

Дерево с одним split (depth=1). Используется как weak learner в AdaBoost.

Деревья поддерживают NaN?

XGBoost, LightGBM, CatBoost — да, native. Sklearn HistGradientBoosting — да. Старый DecisionTreeClassifier — нет (с 1.4+ есть).

Как ускорить обучение глубокого дерева?

max_features (рандомизация на split), min_samples_leaf (огрубление), histogram-based методы (LightGBM, HistGradientBoosting). Полные пробежки по всем порогам — медленно.

Это официальная информация?

Нет. Статья основана на классических работах (Breiman 1984 «CART», Quinlan 1993 «C4.5»), документации scikit-learn.

Тренируйте Data Science — откройте тренажёр с 1500+ вопросами для собесов.