Дерево решений. Вопросы к собеседованию.

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

Это модель, которая рекурсивно разбивает пространство признаков на регионы, в каждом из которых делается прогноз. Для задач классификации модель прогнозирует класс, для задач регрессии – числовое значение.

Какие критерии использует дерево решений для разбиения данных в задачах классификации и регрессии?

Для задачи классификации

• Критерий Джини
• Энтропия Шэннона

Для задачи регрессии

• MSE
• MAE

Как выглядит переобучение дерева решений?

Как и любое переобучение в алгоритмах ML – модель запоминает шум в данных и на обучающих данных показывает высокие метрики, а на тестовых – более низкие.

Как бороться с переобучением дерева решений?

• Ограничить глубину дерева (max_depth)
• Ограничить количество примеров для разбиения в каждом узле (min_samples_split)
• Отрегулировать количество примеров в листьях дерева (min_samples_leaf)
• Отрегулировать максимальное количество признаков для поиска лучшего разбиения (max_features)
• Сменить алгоритм на бустинг или бэггинг (Random Forest)

Какие гиперпараметры наиболее важны в дереве решений?

• max_depth – ограничивает дерево в глубину
• min_samples_split – минимальное количество примеров для разбиения в узле
• min_samples_leaf – минимальное количество примеров в листьях дерева
• max_features – максимальное количество примеров для поиска лучшего разбиения

Как в дереве решений обрабатываются категориальные признаки?

В реализации Scikit Learn – категориальные признаки необходимо кодировать (One Hot Encoding, Ordinal Encoding)

В Catboost и подобных алгоритмах бустинга категориальные признаки обрабатываются нативно. Под капотом они кодируются методом Target Encoding – http://csnotes.ru/?p=2206#:~:text=%D0%BF%D1%80%D0%B8%D0%BC%D0%B5%D0%BD%D0%B8%D1%82%D1%8C%20%D1%86%D0%B5%D0%BB%D0%B5%D0%B2%D0%BE%D0%B5%20%D0%BA%D0%BE%D0%B4%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5%20%E2%80%93-,Target%20Encoding,-.%20%D0%95%D0%B3%D0%BE%20%D1%81%D1%83%D1%82%D1%8C%20%E2%80%93%20%D0%B7%D0%B0%D0%BC%D0%B5%D0%BD%D0%B0

Чем отличаются критерий Джини и энтропия Шэннона?

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

Критерий Джини – для задачи классификации

Gini(t) = 1 - \sum_{i=1}^{C} p_i^2

Где:

• p_i — доля объектов класса i в узле t
• CCC — число классов

Энтропия Шеннона – для задачи классификации

Entropy(t) = - \sum_{i=1}^{C} p_i \log_2(p_i)

Где:

• p_i — вероятность (доля) появления класса i в узле t
• Энтропия измеряет уровень неопределенности — чем она выше, тем более “смешанным” является узел.

График показывает, как зависит значение критерия от вероятности наличия объектов определенного класса в выборке. Также виден взаимный масштаб изменения критерия Джини и энтропии Шеннона.

Пример:

Если в узле представлены оба класса с вероятностями 50% на 50%:

Entropy = − (0.5⋅log⁡2(0.5) + 0.5⋅log⁡2(0.5)) = 1

Если только один класс: Entropy = 0

В чём разница между деревом решений и случайным лесом?

Если смотреть в контексте ансамблей, то дерево – это один слабый классификатор.

Случайный лес – это множество деревьев, работающих параллельно. Здесь делается бутстрэп выборка сэмплов и случайная выборка признаков. Это в целом увеличивает устойчивость результатов и обобщающую способность.

Какова временная сложность построения дерева в О-нотации?

O(M * N * logN)

Где M – число признаков, N – число сэмплов.

Можно ли использовать дерево решений для данных с пропущенными значениями?

В Sclearn – нет, требуется предварительная обработка пропусков в данных.

В некоторых реализациях бустинга (LightGBM, XGBoost) пропуски обрабатываются нативно.

Как понять, важен ли признак?

Воспользоваться атрибутом feature_importance – он показывает суммарный вклад признака в улучшение разбиения.

Основные преимущества дерева решений

Интерпретируемость

Не требуется масштабирование признаков

Способность захватывать нелинейные зависимости

Основные недостатки дерева решений

Склонность к переобучению

Высокая вычислительная сложность, если нет ограничений

Нестабильность при малых изменениях данных