Random forest (англ. случайный лес) — алгоритм машинного обучения, предложенный Лео Брейманом^[1][2] и Адель Катлер, заключающийся в использовании комитета (ансамбля) решающих деревьев. Алгоритм сочетает в себе две основные идеи: метод бэггинга Бреймана, и метод случайных подпространств, предложенный Tin Kam Ho. Алгоритм применяется для задач классификации, регрессии и кластеризации.

Алгоритм обучения классификатора

Пусть обучающая выборка состоит из N примеров, размерность пространства признаков равна M, и задан параметр m (в задачах классификации обычно ).

Все деревья комитета строятся независимо друг от друга по следующей процедуре:

1. Сгенерируем случайную подвыборку с повторением размером N из обучающей выборки. (Таким образом, некоторые примеры попадут в неё несколько раз, а примерно N/3 примеров не войдут в неё вообще)
2. Построим решающее дерево, классифицирующее примеры данной подвыборки, причём в ходе создания очередного узла дерева будем выбирать признак, на основе которого производится разбиение, не из всех M признаков, а лишь из m случайно выбранных. Выбор наилучшего из этих m признаков может осуществляться различными способами. В оригинальном коде Бреймана используется критерий Гини, применяющийся также в алгоритме построения решающих деревьев CART. В некоторых реализациях алгоритма вместо него используется критерий прироста информации.^[3]
3. Дерево строится до полного исчерпания подвыборки и не подвергается процедуре прунинга (в отличие от решающих деревьев, построенных по таким алгоритмам, как CART или C4.5).

Классификация объектов проводится путём голосования: каждое дерево комитета относит классифицируемый объект к одному из классов, и побеждает класс, за который проголосовало наибольшее число деревьев.

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

Достоинства

• Высокое качество получаемых моделей, сравнимое с SVM и бустингом, и лучшее, чем у нейронных сетей.^[4]
• Способность эффективно обрабатывать данные с большим числом признаков и классов.
• Нечувствительность к масштабированию (и вообще к любым монотонным преобразованиям) значений признаков.
• Одинаково хорошо обрабатываются как непрерывные, так и дискретные признаки. Существуют методы построения деревьев по данным с пропущенными значениями признаков.
• Существует методы оценивания значимости отдельных признаков в модели.
• Внутренняя оценка способности модели к обобщению (тест out-of-bag).
• Высокая параллелизуемость и масштабируемость.

Недостатки

• Алгоритм склонен к переобучению на некоторых задачах, особенно на зашумленных задачах.^[5]
• Большой размер получающихся моделей. Требуется памяти для хранения модели, где  — число деревьев.

Реализации

• Авторская реализация Бреймана и Катлер на языке Fortran 77
• Пакет randomForest для R — портированная версия оригинального авторского кода в R
• Пакет party для R, содержит модификацию алгоритма
• Существуют реализации алгоритма в системах Weka и RapidMiner
• Реализация модификации алгоритма на alglib.sources.ru
• FastRandomForest
• Планируется реализовать алгоритм в Apache Mahout в ходе Summer of Code 2009.

Примечания