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

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

Понимаете ли вы, откуда в лесу берётся случайность и почему усреднение многих переобученных деревьев работает лучше одного. Следом обычно спрашивают про out-of-bag оценку, важность признаков или чем лес отличается от бустинга.

Как отвечать

Случайный лес это бэггинг над деревьями решений плюс случайный выбор признаков в каждом узле. Обучение для классификации:

• бутстрэп: для каждого дерева из n объектов выборки берётся n с возвращением. В подвыборку попадает примерно 63% уникальных объектов, остальные около 37% становятся для этого дерева out-of-bag;
• случайные признаки: при каждом разбиении перебирается не весь набор из p признаков, а случайное подмножество, обычно √p. В RandomForestClassifier это max_features="sqrt" по умолчанию;
• рост дерева: разбиения выбираются по критерию Джини или энтропии, деревья по умолчанию растут до чистых листьев (max_depth=None) без прунинга;
• предсказание: голосование деревьев. В sklearn голосование мягкое: усредняются вероятности классов из листьев и берётся класс с максимумом.

Главная мысль: глубокое дерево имеет низкое смещение и высокую дисперсию. Усреднение снижает дисперсию, но только если деревья слабо коррелированы, для этого и нужен случайный выбор признаков. Без него все деревья начинали бы с одного сильного признака и ошибались бы одинаково.

Ещё назовите: OOB-оценка (oob_score=True) заменяет отдельную валидацию, обучение параллелится по деревьям, масштабировать признаки не нужно, дисбаланс закрывается class_weight="balanced".

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

Говорят, что лес «не переобучается». Добавление деревьев действительно не ухудшает качество, но на шумных данных лес из глубоких деревьев всё равно переобучается, и min_samples_leaf с max_depth приходится подбирать.

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

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