Как работают решающие деревья

Что проверяют

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

Как отвечать

Самый распространённый алгоритм это CART, его реализует scikit-learn. Дерево строится жадно сверху вниз:

• перебор разбиений: для каждого признака и порога вида x_j <= t считается, насколько уменьшится неоднородность потомков, взвешенная по их размеру. Берётся лучшее разбиение, и процесс повторяется для каждой половины;
• критерии: для классификации индекс Джини или энтропия, для регрессии среднеквадратичная ошибка;
• предсказание: в листе классификатора лежит доля классов, в листе регрессора среднее значение цели. Получается кусочно-постоянная функция, которая не экстраполирует за диапазон обучающих данных;
• остановка: max_depth, min_samples_split, min_samples_leaf, min_impurity_decrease. Без ограничений дерево растёт до чистых листьев и запоминает шум.

Ещё есть обрезка по сложности: параметр ccp_alpha, его подбирают кросс-валидацией.

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

Где спотыкаются

Говорят, что дерево само работает с категориальными признаками. Классический DecisionTreeClassifier из sklearn ждёт числа, категории кодируют заранее, а нативно их понимают LightGBM, CatBoost и HistGradientBoostingClassifier.

Доверяют feature_importances_ как истине. Важность по уменьшению неоднородности завышена у признаков с большим числом уникальных значений, надёжнее permutation importance.

Называют критерием остановки «минимальную глубину». Ограничивают максимальную глубину, а минимальным задают число объектов в листе или в узле перед разбиением.