Случайный лес

Случайный лес (англ. Random Forest) — это ансамблевый метод машинного обучения, предназначенный для задач классификации, регрессии и кластеризации, основанный на построении множества решающих деревьев и объединении их прогнозов. Метод сочетает в себе две ключевые идеи: «бэггинг» (bootstrap aggregating) и случайный подбор признаков при построении каждого дерева, что позволяет существенно повысить точность и устойчивость модели по сравнению с одиночным решающим деревом, а также снизить склонность к переобучению. Случайный лес считается одним из наиболее эффективных и широко применяемых алгоритмов машинного обучения общего назначения.

История

Метод случайного леса был предложен Лео Брейманом, американским статистиком, в 2001 году. Первая публикация, в которой был формализован алгоритм, вышла в журнале Machine Learning под названием «Random Forests» (Брейман, 2001). В своей работе Брейман обобщил и развил более ранние идеи: использование «бэггинга» (предложенного им же в 1996 году) и случайного подпространства признаков, введённого Тин Кам Хо в 1998 году. Брейман экспериментально показал, что случайный лес не склонен к переобучению при увеличении числа деревьев и демонстрирует высокую точность на многих задачах.

До появления случайного леса решающие деревья (например, C4.5, CART) были популярны благодаря интерпретируемости, но страдали от высокой дисперсии — небольшие изменения в данных приводили к существенному изменению дерева. Ансамблевые методы, такие как бэггинг, частично решали эту проблему, но не использовали декорреляцию деревьев за счёт случайного выбора признаков. Случайный лес стал естественным развитием, объединив оба подхода.

Основные принципы

Случайный лес строится как ансамбль решающих деревьев, каждое из которых обучается на случайной подвыборке исходных данных. Итоговое предсказание для нового объекта определяется путём голосования деревьев (в задачах классификации — по большинству голосов) или усреднения их прогнозов (в задачах регрессии).

Бэггинг

Бэггинг (Bootstrap Aggregating) заключается в создании \( N \) обучающих выборок путём случайного извлечения с возвращением (бутстреп) из исходного набора данных. Каждое решающее дерево обучается на своей бутстреп-выборке. Использование бутстрепа приводит к тому, что примерно 63% уникальных объектов исходного набора попадают в каждую выборку, а оставшиеся 37% (так называемые «out-of-bag», OOB-объекты) не участвуют в обучении данного дерева. OOB-объекты используются для оценки ошибки модели без необходимости отдельной тестовой выборки.

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

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

Алгоритм обучения

1. Выбрать количество деревьев \( T \) и количество признаков \( m \) для каждого узла.
2. Для \( i \) от 1 до \( T \):

• Сформировать бутстреп-выборку размером \( n \) (равным размеру исходного набора).
• Построить решающее дерево (обычно CART) на этой выборке, при этом на каждом узле:
• Выбрать случайным образом \( m \) признаков из всех \( p \).
• Найти наилучшее разбиение по одному из этих \( m \) признаков (порог и индекс признака), минимизирующее критерий неопределённости (например, примеси Джини для классификации или среднеквадратичную ошибку для регрессии).
• Разбить узел на два дочерних.
• Дерево строится до полного исчерпания (листья содержат один объект или один класс), без процедуры отсечения ветвей (pruning).

1. Сохранить все построенные деревья.

Предсказание

• Классификация: каждый объект «опускается» по каждому из \( T \) деревьев. Дерево выдаёт метку класса, соответствующую листу. Итоговая метка определяется большинством голосов деревьев.
• Регрессия: каждое дерево выдаёт числовое значение (среднее целевой переменной в листе). Итоговое предсказание — среднее арифметическое всех \( T \) значений.
• Оценка вероятностей (для классификации): доля деревьев, предсказавших данный класс, может интерпретироваться как вероятность принадлежности объекта этому классу. Такие оценки, однако, являются грубыми и часто требуют калибровки.

Ключевые параметры

• n_estimators (\( T \)) — число деревьев в лесу. Чем больше, тем точнее модель (до определённого предела) и тем выше вычислительные затраты. На практике часто используют 100–1000 деревьев.
• max_features (\( m \)) — количество признаков, случайно выбираемых для поиска наилучшего разбиения. Может быть задано как доля, число, корень, логарифм от общего числа признаков.
• max_depth — максимальная глубина деревьев. Если не задана (None), деревья строятся до полного исчерпания.
• min_samples_split — минимальное число объектов для разделения узла.
• min_samples_leaf — минимальное число объектов в листе.
• bootstrap — флаг, указывающий, использовать ли бутстреп. Если False, каждое дерево обучается на всём наборе данных (что повышает риск переобучения).
• oob_score — флаг, указывающий, нужно ли вычислять оценку на OOB-объектах для контроля качества.

Преимущества и недостатки

Преимущества

• Высокая точность и устойчивость. Благодаря ансамблированию и декорреляции случайный лес часто является одним из лучших «из коробки» (без глубокой настройки) алгоритмов для табличных данных.
• Устойчивость к переобучению. При увеличении числа деревьев ошибка обобщения обычно сходится к некоторому пределу, а не растёт.
• Работа с разнотипными признаками: числовыми, категориальными, бинарными (встроенная обработка пропущенных значений в некоторых реализациях).
• Отсутствие необходимости в масштабировании признаков (нормализации, стандартизации).
• Интерпретируемость. Хотя случайный лес не так прост для интерпретации, как одиночное дерево, существует множество инструментов для объяснения предсказаний: важность признаков, частичные зависимости (partial dependence plots).
• Встроенная перекрёстная проверка через OOB-оценку, что снижает потребность в дополнительной отложенной выборке.
• Параллелизация: обучение каждого дерева можно выполнять независимо, что позволяет эффективно использовать многоядерные процессоры.

Недостатки

• Вычислительная сложность. Для больших объёмов данных (миллионы объектов, тысячи признаков) обучение случайного леса может быть ресурсоёмким, хотя в современных реализациях (например, scikit-learn, XGBoost) применяются оптимизации.
• Недостаточная интерпретируемость по сравнению с линейными моделями или одиночным деревом. Модель часто рассматривается как «чёрный ящик».
• Проблемы с экстраполяцией. Для регрессии случайный лес не может выдавать значения за пределами диапазона целевых переменных, присутствовавших в обучающих данных.
• Смещённость в задачах с несбалансированными классами: стандартный случайный лес может игнорировать редкие классы. Для решения применяются модификации (например, Weighted Random Forest или Balanced Random Forest).
• Отсутствие гарантии сходимости к глобальному оптимуму, хотя на практике модель часто работает хорошо.

Применение

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

• Биоинформатика: классификация генов, предсказание структуры белков, выявление биомаркеров.
• Банковское дело: кредитный скоринг, обнаружение мошенничества (fraud detection), определение кредитоспособности клиентов.
• Маркетинг: сегментация клиентов, прогнозирование оттока, рекомендательные системы (для этапа отбора кандидатов).
• Медицина: диагностика заболеваний по медицинским показателям (например, выявление рака по биопсии).
• Промышленность: прогнозирование отказов оборудования (predictive maintenance), контроль качества.

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

Одной из ценных особенностей случайного леса является возможность оценить важность (значимость) каждого признака. Два основных подхода:

• Уменьшение примеси (Mean Decrease Impurity, MDI): для каждого признака суммируется уменьшение примеси (impurity) по всем узлам всех деревьев, где этот признак был использован для разбиения. Чем больше суммарное уменьшение, тем признак важнее.
• Уменьшение точности (Permutation Importance, Mean Decrease Accuracy, MDA): для каждого признака оценивается, как изменяется точность модели (или R² для регрессии) при случайном перемешивании значений этого признака (permutation). Если точность падает сильно — признак важен.

Оба подхода реализованы в большинстве библиотек машинного обучения.

Реализации

Наиболее популярные реализации случайного леса:

• scikit-learn (Python) — sklearn.ensemble.RandomForestClassifier и RandomForestRegressor. Широко используется в исследовательских и производственных задачах.
• RandomForest в пакете randomForest для R (автор первоначальной реализации Лео Брейман и Рэйлинг, поддерживается А. Лиау и М. Винером).
• Apache Spark MLlib — распределённая реализация для работы с большими данными (в модуле ml.classification.RandomForestClassifier и ml.regression.RandomForestRegressor).
• H2O — платформа машинного обучения, также включает собственную высокопроизводительную реализацию случайного леса.
• XGBoost, LightGBM, CatBoost — хотя эти библиотеки относятся к градиентному бустингу, они также поддерживают построение случайных лесов (с небольшими отличиями).

Связь с другими методами

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

Критика и ограничения

Несмотря на широкую популярность, случайный лес подвергается критике за сложность интерпретации в высокоразмерных пространствах и за неспособность моделировать сложные нелинейные зависимости столь же эффективно, как нейронные сети (особенно глубокие) на задачах с изображениями, текстом или временными рядами. Кроме того, метод может требовать значительных ресурсов памяти при сохранении большого числа деревьев (каждое дерево — отдельная структура данных).

Источники

• Breiman L. Random Forests // Machine Learning. — 2001. — Vol. 45, No. 1. — P. 5–32.
• Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning. — 2nd ed. — Springer, 2009. — Chapter 15.
• Louppe G. Understanding Random Forests: From Theory to Practice. — PhD Thesis, University of Liège, 2014.
• Документация scikit-learn: «1.11. Ensemble methods» (scikit-learn.org/stable/modules/ensemble.html).