Random forest

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

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

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

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

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

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

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

Достоинства

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

Недостатки

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

Реализации

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

Примечания

1. ↑ Breiman, Leo (2001). «Random Forests». Machine Learning 45 (1): 5–32. DOI:10.1023/A:1010933404324. (англ.) (Проверено 7 июня 2009)
2. ↑ Описание алгоритма на сайте Лео Бреймана (англ.) (Проверено 7 июня 2009)
3. ↑ Описание процедуры построения деревьев, применяющейся в Apache Mahout (англ.) (Проверено 7 июня 2009)
4. ↑ Caruana R., Niculescu-Mizil A., An Empirical Comparison of Supervised Learning Algorithms Using Different Performance Metrics (англ.) (Проверено 7 июня 2009)
5. ↑ Segal, Mark R. (2004), «Machine Learning Benchmarks and Random Forest Regression», Center for Bioinformatics & Molecular Biostatistics, <http://repositories.cdlib.org/cbmb/bench_rf_regn/>  (англ.) (Проверено 7 июня 2009)

Литература

• Hastie, T., Tibshirani R., Friedman J. Chapter 15. Random Forests // The Elements of Statistical Learning: Data Mining, Inference, and Prediction. — 2nd ed. — Springer-Verlag, 2009. — 746 p. — ISBN 978-0-387-84857-0.