Как работает случайный лес и строятся деревья в ансамбле

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

Понимаете ли вы, откуда в лесу берётся разнообразие деревьев и почему усреднение снижает ошибку. Раз категория coding, будьте готовы набросать построение на псевдокоде или numpy, а следом услышать вопрос про важность признаков или про то, переобучается ли лес при росте числа деревьев.

Как отвечать

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

• бутстрэп: из n объектов выбираем n с возвращением. В выборку попадает около 63% уникальных объектов, остальные около 37% становятся out-of-bag;
• случайные признаки в каждом узле: для разбиения рассматриваются не все признаки, а случайные max_features. В scikit-learn для классификации по умолчанию берётся корень из числа признаков, для регрессии все;
• жадное разбиение: среди выбранных признаков и порогов ищем то, что сильнее всего снижает неоднородность: Джини или энтропию для классов, MSE для регрессии;
• глубина: деревья растят почти до конца (max_depth=None), без обрезки. Смещение у каждого маленькое, дисперсия большая, её и гасит ансамбль.

Предсказание: для регрессии среднее по деревьям, для классификации голосование. В scikit-learn это мягкое голосование, усредняются вероятности классов. Деревья независимы, поэтому обучение параллелится (n_jobs=-1).

Объясните, зачем случайные признаки: без них все деревья поставят один сильный признак в корень и станут похожими, а усреднение коррелированных моделей почти не снижает дисперсию. OOB-объекты дают бесплатную оценку качества без отложенной выборки (oob_score=True).

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

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

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

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