Для чего полезна обрезка дерева решений

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

Понимаете ли вы, откуда у дерева переобучение и какими рычагами оно лечится на практике. Следом почти всегда просят объяснить разницу между пред- и постобрезкой и показать, как подобрать параметр в scikit-learn.

Как отвечать

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

Два подхода:

• предобрезка (early stopping): не даём дереву вырасти. В DecisionTreeClassifier это max_depth, min_samples_split, min_samples_leaf, max_leaf_nodes, min_impurity_decrease. Дёшево, но можно остановиться раньше времени: слабое разбиение иногда открывает сильное на следующем уровне;
• постобрезка: растим полное дерево, затем срезаем ветви. Классика CART это cost-complexity pruning: минимизируется ошибка плюс alpha, умноженная на число листьев. В scikit-learn это параметр ccp_alpha, а метод cost_complexity_pruning_path(X, y) возвращает набор значений alpha, среди которых лучшее выбирают кросс-валидацией. Есть и reduced error pruning по отложенной выборке, и пессимистическая обрезка из C4.5.

Кроме качества, обрезка даёт интерпретируемость: дерево в пять уровней можно показать бизнесу набором правил, а в тридцать уже нет.

Хороший ответ связывает тему с ансамблями. В случайном лесе деревья обычно не обрезают: дисперсию снижает усреднение. В градиентном бустинге деревья мелкие, а в XGBoost есть свой механизм: параметр gamma задаёт минимальный прирост для разбиения, и ветви с меньшим приростом срезаются после построения.

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

Называют обрезкой только ограничение глубины и не знают про постобрезку и ccp_alpha.

Подбирают alpha или max_depth по тестовой выборке. Тогда тест перестаёт быть честной оценкой, подбирать нужно кросс-валидацией на обучающей части.

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