Random Forest

Сначала случайные подпространства, потом Random Forest

В 1995 году Тин Кам Хо из Bell Labs предложила метод случайных подпространств: обучать каждое дерево не на всех признаках, а на случайном их подмножестве. Это снижало корреляцию между деревьями и позволяло ансамблю улучшаться без переобучения - идея, шедшая вразрез с тогдашней интуицией. В 2001 году Лео Брейман объединил случайность признаков с бутстрэп-выборкой данных и опубликовал работу «Random Forests». Рецепт оказался простым и на редкость устойчивым - и быстро стал одним из самых востребованных алгоритмов в прикладном машинном обучении, моделью по умолчанию для табличных данных на два десятилетия вперёд.

Одно дерево решений - нестабильный классификатор: убрали пару наблюдений из обучающей выборки, и дерево перестроилось полностью, выдав совсем другие предсказания. А что если обучить не одно, а 500 деревьев на разных подвыборках и дать им проголосовать? Именно эта простая идея сделала Random Forest одним из самых надёжных алгоритмов в машинном обучении - он побеждает на Kaggle, работает "из коробки" без сложного тюнинга и до сих пор используется в продакшене банков, больниц и технологических компаний.

• **Банковский скоринг** - Random Forest оценивает кредитоспособность, анализируя десятки признаков (доход, история, возраст), и feature importance объясняет клиенту причину отказа, что требуется законодательством (GDPR, FCRA)
• **Медицинская диагностика** - ансамбль из 1000 деревьев классифицирует опухоли по 30 биомаркерам с точностью 96%+, а permutation importance показывает врачу какие маркеры решающие для конкретного пациента
• **Рекомендательные системы** - Random Forest предсказывает, понравится ли пользователю товар, обрабатывая сотни признаков (история покупок, демография, время суток) параллельно на всех ядрах сервера за миллисекунды

Предварительные знания

• Decision Trees

Bagging: Bootstrap Aggregating

Одно дерево решений легко переобучается: оно запоминает шум в данных и выдаёт нестабильные предсказания. Убрали одно наблюдение из обучающей выборки - дерево может полностью перестроиться. Это высокий **variance**. Идея **bagging** (Bootstrap AGGregatING) проста: вместо одного дерева обучим **N деревьев на разных подвыборках** и возьмём среднее (регрессия) или голосование большинства (классификация). Каждое дерево ошибается по-своему, но в среднем ошибки компенсируются.

Откуда взять N разных подвыборок, если датасет один? Техника **bootstrap**: из N наблюдений выбираем N наблюдений **с возвращением**. Некоторые наблюдения попадут дважды, трижды, а некоторые не попадут вообще. Вероятность НЕ попасть в выборку для одного наблюдения: (1 - 1/N)^N. При N -> infinity это стремится к 1/e = 0.368. Значит, каждая bootstrap-выборка содержит примерно **63.2% уникальных** наблюдений и **36.8% дубликатов** (а 36.8% исходных данных вообще не попали в выборку).

Почему это работает? Аналогия: **мудрость толпы**. В 1906 году на ярмарке 787 человек угадывали вес быка. Индивидуальные оценки сильно разнились, но *среднее* всех оценок отличалось от реального веса менее чем на 1%. Каждый человек ошибался по-своему (случайный шум), но в среднем шум компенсировался. Bagging работает так же: каждое дерево переобучается на своём подмножестве данных, но **агрегация уменьшает variance** без увеличения bias.

**Bias-Variance trade-off и bagging:** - Одно глубокое дерево: **низкий bias, высокий variance** (запоминает шум) - Bagging N деревьев: **низкий bias, низкий variance** (шум усредняется) Математически: если деревья некоррелированы и каждое имеет variance = v, то variance ансамбля = v/N. Чем больше деревьев, тем стабильнее предсказания. На практике после 100-300 деревьев улучшение становится минимальным.

Случайный выбор признаков

Bagging уменьшает variance, но есть проблема: если в данных есть один очень сильный признак (например, «возраст» при предсказании смертности), то **все деревья будут сплитить по нему первым**. Деревья получатся похожими - **коррелированными**. А усреднение коррелированных предсказаний даёт гораздо меньшее уменьшение variance, чем усреднение независимых.

Решение Random Forest: **на каждом сплите** (не на каждом дереве, а именно на каждом узле!) случайно выбирать подмножество из m признаков и искать лучший сплит только среди них. Если всего p признаков, типичные значения: **m = sqrt(p)** для классификации и **m = p/3** для регрессии. Это единственное, но принципиальное отличие Random Forest от обычного bagging.

**Почему именно sqrt(p)?** Это эмпирическое правило, найденное Лео Брейманом (создателем Random Forest, 2001). Интуиция: - Слишком мало признаков (m=1): деревья слабые, высокий bias - Слишком много признаков (m=p): деревья коррелированы, высокий variance - **sqrt(p) - баланс** между силой каждого дерева и разнообразием ансамбля При p=100 признаков каждый сплит видит только 10 случайных признаков. Сильный признак попадает в выборку с вероятностью 10%, поэтому большинство деревьев вынуждены находить альтернативные паттерны.

Два источника случайности в Random Forest создают **двойное разнообразие**: 1. bootstrap - каждое дерево видит разные наблюдения 2. feature sampling - каждый сплит видит разные признаки. Именно комбинация этих двух рандомизаций делает Random Forest одним из самых надёжных алгоритмов "из коробки" - он редко сильно проигрывает, даже без тюнинга гиперпараметров.

OOB-score: бесплатная валидация

Вспомним: при bootstrap каждое дерево обучается на ~63.2% данных. Оставшиеся ~36.8% - **Out-of-Bag (OOB)** наблюдения - дерево никогда не видело. Это естественный тестовый набор! Для каждого наблюдения x_i мы можем собрать предсказания только тех деревьев, в чьи bootstrap-выборки x_i **не попало**, и посчитать accuracy по этим предсказаниям. Это и есть **OOB-score**.

Каждое наблюдение в среднем попадает в OOB примерно **N/e = N * 0.368** деревьев. При 500 деревьях каждое наблюдение оценивается ~184 деревьями, которые его не видели. Этого достаточно для надёжной оценки. Исследования показывают, что **OOB-score практически совпадает с cross-validation** (разница обычно < 1%), но вычисляется бесплатно - без дополнительного обучения.

**Когда OOB-score особенно полезен:** - **Большие датасеты** - cross-validation на миллионах наблюдений дорогая (5-fold = обучить 5 моделей), OOB-score - бесплатно - **Быстрый подбор гиперпараметров** - сравнивать n_estimators, max_depth, max_features по OOB без разбиения на train/test - **Мониторинг** - OOB-score растёт с числом деревьев и стабилизируется, показывая когда добавлять деревья бессмысленно

**OOB-score - не замена test set в финальной оценке.** OOB-score отлично подходит для подбора гиперпараметров и мониторинга, но для итоговой оценки модели всё равно нужен отдельный held-out test set, который не участвовал ни в обучении, ни в подборе параметров. Иначе есть риск информационной утечки через выбор гиперпараметров.

Feature Importance

Random Forest не только классифицирует, но и показывает, **какие признаки важны** для предсказания. Это критически важно на практике: заказчик хочет знать не только "клиент уйдёт", но и **почему**. Есть два основных метода: **MDI (Mean Decrease Impurity)** - встроенный в sklearn, и **Permutation Importance** - более надёжный, но медленнее.

**MDI (Mean Decrease Impurity):** для каждого признака суммируем, насколько он уменьшил Gini impurity (или entropy) во всех сплитах, по всем деревьям. Признак, который часто используется для сплитов и сильно уменьшает impurity - считается важным. Значения нормализуются так, что сумма = 1. Этот метод быстрый (вычисляется при обучении), но имеет серьёзный недостаток.

**Проблема MDI:** он смещён в пользу **высококардинальных признаков** - тех, у которых много уникальных значений. ID пользователя (100000 уникальных значений) получит высокий MDI, хотя никакой предсказательной силы не имеет. Дата, случайный шум с большим разбросом - тоже завышены. Поэтому для надёжных выводов используют **Permutation Importance**.

**Permutation Importance:** берём обученную модель, случайно **перемешиваем** значения одного признака (разрушаем его связь с целевой переменной) и смотрим, насколько **упала accuracy**. Если признак важен - accuracy упадёт сильно. Если нет - останется прежней. Этот метод не зависит от кардинальности и работает с любой моделью, не только с Random Forest.

**Random Forest: итоговый чек-лист** **Плюсы:** - Работает "из коробки" - мало гиперпараметров, дефолты почти всегда хороши - Устойчив к выбросам и шуму - Не требует нормализации признаков - Параллелизм: n_jobs=-1 использует все ядра CPU - OOB-score - бесплатная валидация - Feature importance - понимание данных **Минусы:** - Медленнее одного дерева (обучение и предсказание) - Менее интерпретируем, чем одно дерево (нельзя нарисовать) - Не экстраполирует: если в обучении цены были 100-500, модель не предскажет 1000 - Уступает gradient boosting (XGBoost, LightGBM) на табличных данных в соревнованиях

Ключевые идеи

• **Bagging (Bootstrap Aggregating):** обучаем N деревьев на bootstrap-выборках (с возвращением, ~63.2% уникальных), агрегируем голосованием/средним - variance падает, bias остаётся низким
• **Feature sampling** - ключевое отличие RF от bagging: на каждом сплите доступны только sqrt(p) случайных признаков, что декоррелирует деревья и усиливает эффект ансамбля
• **OOB-score** - бесплатная валидация: ~36.8% данных, не попавших в bootstrap, служат тестовым набором для каждого дерева, результат сопоставим с cross-validation
• **Feature importance:** MDI (быстрый, но смещён к высококардинальным признакам) vs Permutation Importance (надёжный, но медленнее) - именно поэтому Random Forest ценят в банках и медицине, где нужно не только предсказать, но и объяснить решение, как мы обсуждали в начале

Связанные темы

Random Forest - точка входа в мир ансамблевых методов. Bagging - лишь один из подходов к комбинированию моделей, и дальше мы разберём альтернативы:

• Деревья решений — Базовый строительный блок Random Forest - одно дерево, его устройство, Gini impurity, критерии сплита и проблема переобучения
• Bagging и Boosting — Два фундаментальных подхода к ансамблям: bagging (параллельный, уменьшает variance) vs boosting (последовательный, уменьшает bias) - Random Forest использует первый
• Gradient Boosting — Главный конкурент Random Forest: XGBoost, LightGBM, CatBoost - последовательно строят деревья, каждое исправляя ошибки предыдущих, обычно точнее RF, но сложнее в настройке
• Feature Engineering — Feature importance из Random Forest помогает отбирать признаки, понимать данные и направлять feature engineering - какие признаки создавать, какие убрать

Вопросы для размышления

• Random Forest не может экстраполировать - он предсказывает только в диапазоне значений, которые видел при обучении. Как это ограничение влияет на задачи прогнозирования временных рядов (цены акций, температура, продажи)?
• Если OOB-score примерно равен cross-validation score, зачем вообще нужна cross-validation? В каких ситуациях OOB-score может быть ненадёжен?
• Random Forest работает хорошо "из коробки", а Gradient Boosting требует тщательного тюнинга, но обычно точнее. Какой подход вы бы выбрали для первого прототипа модели и почему?

Связанные уроки

• ml-11-decision-trees — Random Forest - bagging-ансамбль деревьев решений
• ml-21-bagging-boosting — Random Forest - специализированный bagging с feature subsampling
• ml-22-gradient-boosting — Gradient Boosting строит деревья последовательно (vs параллельно в RF)
• alg-13-dfs