Что такое критерий ветвления в деревьях?
Что проверяют
Понимаете ли вы, по какому правилу дерево решений выбирает разбиение и почему это правило влияет на итоговое качество куда слабее, чем ограничения роста. Вопрос отделяет тех, кто вызывал обучение, от тех, кто понимает, что внутри.
Как отвечать
В каждом узле перебираются пары признак и порог, выбирается та, что сильнее уменьшает неоднородность. Считается не чистота потомков сама по себе, а выигрыш: неоднородность родителя минус взвешенная по размерам сумма неоднородностей потомков.
gain = imp(parent) - (n_l / n) * imp(left) - (n_r / n) * imp(right)В роли imp для классификации выступают критерий Джини (вероятность ошибки случайного отнесения, основа CART) и энтропия (ID3, C4.5). На практике они дают близкие деревья, Джини считается быстрее, потому что обходится без логарифма. Для регрессии критерий другой: уменьшение дисперсии, то есть MSE в листьях, либо MAE, когда нужна устойчивость к выбросам. Отдельно стоит назвать gain ratio: обычный прирост информации тянет дерево к признакам с большим числом значений, вплоть до разбиения по идентификатору, и нормировка на собственную энтропию признака это лечит.
Сильный ответ заканчивается практикой: выбор между Джини и энтропией меняет мало, а глубина, минимальный размер листа и обрезка меняют многое.
Где спотыкаются
Говорят, что берётся признак с минимальным Джини у потомков, забывая про взвешивание по числу объектов. Без него лучшим на каждом шаге будет разбиение, отрезающее один объект в идеально чистый лист.
Считают критерий ветвления средством против переобучения. Он только ранжирует кандидатов, а переобучение ограничивают глубиной, минимальным числом объектов в узле, обрезкой и ансамблем: дерево без ограничений доведёт любой критерий до листьев из одного объекта.
Переносят критерии классификации на регрессию. Джини и энтропия определены для распределения классов, для непрерывного отклика нужен другой функционал, и фраза про энтропию цены сразу показывает заученный ответ.