Случайный лес: алгоритм Random Forest простыми словами

Случайный лес (Random Forest) - один из самых устойчивых алгоритмов машинного обучения, который стабильно показывает высокую точность без долгой настройки гиперпараметров. Его идея проста: вместо одного дерева решений строится несколько сотен, каждое на своей случайной подвыборке данных, а ответ получают голосованием большинства. Благодаря этому ансамбль оказывается значительно точнее и устойчивее любого из деревьев по отдельности. Ниже разберём математику метода, принцип бэггинга, Out-of-Bag оценку, важность признаков и типичные ошибки при решении задач. Чтобы сразу почувствовать, как число деревьев влияет на точность, - покрути калькулятор ниже.

Как устроен случайный лес

Случайный лес принадлежит к классу ансамблевых методов, а конкретно к технике бэггинга (Bootstrap AGGregating). Алгоритм строит $N$ независимых деревьев решений, каждое из которых обучается на своей бутстрап-выборке - случайной выборке с возвращением того же размера, что и исходный датасет. Примерно 37% объектов при этом не попадают в конкретное дерево - они называются Out-of-Bag (OOB) объектами и используются для оценки точности без отдельной тестовой выборки.

Рассчитать для своей задачи

Ключевое отличие случайного леса от простого бэггинга деревьев - случайный отбор признаков при каждом разбиении узла. Вместо того чтобы искать лучшее разбиение по всем $p$ признакам, алгоритм в каждом узле случайно выбирает только $m$ признаков (по умолчанию $m = \sqrt{p}$ для классификации и $m = p/3$ для регрессии) и ищет лучшее разбиение только среди них. Это снижает корреляцию между деревьями и уменьшает дисперсию ансамбля.

Математика ансамбля: почему точность растёт

Пусть каждое дерево имеет точность $b$ (base accuracy) и принимает решения с ошибкой $\varepsilon = 1 - b$, при этом ошибки деревьев независимы. Вероятность ошибки ансамбля из $N$ деревьев при голосовании большинством выражается через биномиальное суммирование:

$P_{\text{ошибка}} = \sum_{k=\lceil N/2 \rceil}^{N} \binom{N}{k} \varepsilon^k (1-\varepsilon)^{N-k}.$

При $b = 0{,}72$ и $N = 50$ деревьях ансамбль достигает точности около $80\%$ - прирост более 8 п.п. Практически точность насыщается по экспоненциальному закону:

$\text{acc}(N) = \text{acc}_{\max} \cdot \left(1 - e^{-N/\tau}\right),$

где $\tau$ - постоянная насыщения, зависящая от числа признаков в сплите (меньше признаков - деревья коррелируют - насыщение медленнее), а $\text{acc}_{\max} = b \cdot (1 + 0{,}38\,(1-b))$ - предельная точность ансамбля. После $N \approx 3\tau$ прирост точности падает ниже 0,1 п.п. - дальше наращивать лес бессмысленно.

Рассчитать для своей задачи

График показывает типичную картину: уже при 20-30 деревьях ансамбль собирает основной выигрыш, при 50-100 кривая выходит на плато. Оранжевая пунктирная линия - точность одного дерева; зелёная площадь - зона выигрыша ансамбля.

Out-of-Bag оценка

Поскольку каждое дерево обучается на бутстрап-выборке, примерно $1/e \approx 36{,}8\%$ объектов остаются вне обучения конкретного дерева. Для любого объекта $x_i$ существует подмножество деревьев, которые его не видели при обучении. OOB-прогноз для $x_i$ - это голосование только этих деревьев:

$\hat{y}_i^{\text{OOB}} = \text{majority}\left(\{T_j(x_i) : x_i \notin D_j\}\right),$

где $D_j$ - бутстрап-выборка $j$-го дерева. OOB-ошибка оказывается несмещённой оценкой ошибки обобщения - практически эквивалентной кросс-валидации, но вычисляется «бесплатно» в процессе обучения.

Важность признаков

Случайный лес предоставляет два основных способа оценки важности признаков:

Gini importance (MDI): на сколько в среднем каждый признак уменьшает примесь (Gini или энтропию) при разбиениях по всем деревьям. Быстро считается, но смещена в сторону признаков с большим числом уникальных значений.

Permutation importance (MDA): важность признака $j$ оценивается как падение OOB-точности после случайного перемешивания значений $x_j$ при фиксированной модели:

$\text{Imp}(j) = \overline{\text{acc}}^{\text{OOB}} - \overline{\text{acc}}^{\text{OOB}}_{\text{permuted}(j)}.$

Permutation importance более надёжна, особенно при коррелированных признаках, но требует дополнительных вычислений. В scikit-learn первый метод доступен через feature_importances_, второй - через отдельную функцию permutation_importance.

На практике оба метода используют вместе: MDI быстро отсекает явно неважные признаки, а MDA даёт надёжный рейтинг топ-10 для интерпретации. Признаки с нулевой или отрицательной MDA можно безболезненно удалить - они только добавляют шум и замедляют обучение.

Параметры и настройка

Основные гиперпараметры случайного леса и их влияние:

• n_estimators (число деревьев): чем больше, тем лучше, но отдача убывает. Практически 100-500 деревьев достаточно для большинства задач. Ориентир - когда OOB-ошибка стабилизировалась.
• max_features ($m$, число признаков в сплите): уменьшение снижает корреляцию деревьев и дисперсию, но увеличивает смещение. По умолчанию sqrt для классификации - хороший старт.
• max_depth / min_samples_split: контролируют глубину деревьев. Для Random Forest деревья обычно выращивают до конца (max_depth=None), так как бэггинг сам справляется с переобучением.
• class_weight: при дисбалансе классов стоит поставить class_weight='balanced' - каждое дерево учтёт дисбаланс на своей бутстрап-выборке.

Случайный лес vs. одно дерево: разбор задачи

Разберём типичную постановку: есть датасет из 1000 объектов, 20 признаков. Одно дерево решений без ограничений глубины даёт точность 71% на тестовой выборке. Построен случайный лес: 100 деревьев, max_features=sqrt(20)=4, max_depth=None. Какой прирост ожидать?

Используем формулу насыщения: $b = 0{,}71$, $\tau = 40 - 4 \cdot 1{,}2 = 35{,}2$, $\text{acc}_{\max} = 0{,}71 \cdot (1 + 0{,}38 \cdot 0{,}29) \approx 0{,}788$. При $N=100$:

$\text{acc}(100) = 0{,}788 \cdot (1 - e^{-100/35{,}2}) \approx 0{,}788 \cdot 0{,}943 \approx 0{,}743.$

Практически прирост составит около $7$-$8$ п.п. - от 71% до 78-79%. Это согласуется с эмпирической закономерностью: чем ниже базовая точность, тем значительнее выигрыш от ансамблирования. Слабые деревья разнообразнее (меньше коррелируют), и большинство голосующих деревьев в сумме устойчивее.

Обрати внимание: если одно дерево уже даёт 95%+ точности, прирост от ансамбля будет минимальным - деревья будут почти одинаковыми и их голоса не добавят новой информации. В этом случае переусложнённый Random Forest без нужды увеличивает время предсказания.

Частые ошибки

• Увеличение n_estimators за точкой насыщения. Точность не растёт, время обучения линейно растёт. Проверяй OOB-ошибку: она стабилизировалась - добавлять деревья незачем.
• Игнорирование дисбаланса классов. Случайный лес без class_weight='balanced' на дисбалансированных данных смещён в сторону мажоритарного класса. Не забудь корректировку.
• Путаница Gini importance и permutation importance. При коррелированных признаках MDI завышает важность числовых признаков с большим числом уникальных значений. Для интерпретации предпочтительнее MDA.
• Забыть про случайность (random_state). Без фиксации random_state результаты каждого запуска разные - это мешает отладке и сравнению моделей.
• Сравнивать n_estimators без учёта max_features. Меньшее max_features требует большего числа деревьев для достижения того же качества - нельзя сравнивать леса с разными max_features при одинаковом n_estimators.

FAQ

Почему случайный лес не переобучается при большом числе деревьев? В отличие от одного дерева, ансамбль усредняет прогнозы: каждое новое дерево добавляет чуть иной взгляд на данные. Дисперсия усреднённого прогноза убывает как $1/N$, тогда как смещение ансамбля примерно равно смещению одного дерева. Из-за этого добавление деревьев монотонно улучшает (или не ухудшает) качество, но не переобучает.

Можно ли использовать случайный лес для регрессии? Да. В регрессионном Random Forest каждое дерево возвращает числовой прогноз, ансамбль усредняет их. Формула насыщения сохраняется, но вместо точности отслеживают RMSE или MAE. Параметр max_features по умолчанию равен $p/3$ для регрессии вместо $\sqrt{p}$ для классификации.

Чем случайный лес отличается от градиентного бустинга? Бэггинг (Random Forest) строит деревья независимо и усредняет их - снижает дисперсию. Градиентный бустинг строит деревья последовательно, каждое следующее исправляет ошибки предыдущего - снижает смещение. В итоге бустинг обычно точнее, но переобучается при большом числе деревьев и требует тщательного подбора learning rate. Случайный лес быстрее в обучении и надёжнее без тонкой настройки.

Коротко

Случайный лес строит $N$ деревьев на бутстрап-выборках с случайным отбором $m = \sqrt{p}$ признаков в каждом узле, голосует большинством и усредняет прогнозы. Точность ансамбля насыщается по кривой $\text{acc}(N) = \text{acc}_{\max}(1 - e^{-N/\tau})$: при 50-100 деревьях собирается 90% прироста относительно одного дерева. OOB-оценка заменяет кросс-валидацию, важность признаков через permutation importance устойчива к коррелированным предикторам.