Random forest (англ. случайный лес ) — алгоритм машинного обучения, предложенный Лео Брейманом [1][2] и Адель Катлер, заключающийся в использовании комитета (ансамбля) решающих деревьев. Алгоритм сочетает в себе две основные идеи: метод бэггинга Бреймана, и метод случайных подпространств, предложенный Tin Kam Ho. Алгоритм применяется для задач классификации, регрессии и кластеризации.
Алгоритм обучения классификатора[]
Пусть обучающая выборка состоит из N примеров, размер пространства признаков равен M, и задан параметр m (в задачах классификации обычно ).
Все деревья комитета строятся независимо друг от друга по следующей процедуре:
- Сгенерируем случайную подвыборку с повторением размером N из обучающей выборки. (Таким образом, некоторые примеры попадут в неё несколько раз, а примерно N/3 примеров не войдут в неё вообще)
- Построим решающее дерево, классифицирующее примеры данной подвыборки, причём в ходе создания очередного узла дерева будем выбирать признак, на основе которого производится разбиение, не из всех M признаков, а лишь из m случайно выбранных. Выбор наилучшего из этих m признаков может осуществляться различными способами. В оригинальном коде Бреймана используется критерий Гини, применяющийся также в алгоритме построения решающих деревьев CART. В некоторых реализациях алгоритма вместо него используется критерий прироста информации. [3]
- Дерево строится до полного исчерпания подвыборки и не подвергается процедуре прунинга (в отличие от решающих деревьев, построенных по таким алгоритмам, как CART и ID3).
Классификация объектов проводится путём голосования: каждое дерево комитета относит классифицируемый объект к одному из классов, и побеждает класс, за который проголосовало наибольшее число деревьев.
Оптимальное число деревьев подбирается таким образом, чтобы минимизировать ошибку классификатора на тестовой выборке. В случае её отсутствия, минимизируется оценка ошибки 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.
Примечания[]
- ↑ Breiman, Leo (2001). "Random Forests". Machine Learning 45 (1): 5–32. DOI:10.1023/A:1010933404324. (англ.) (Проверено 7 июня 2009)
- ↑ Описание алгоритма на сайте Лео Бреймана(англ.) (Проверено 7 июня 2009)
- ↑ Описание процедуры построения деревьев, применяющейся в Apache Mahout(англ.) (Проверено 7 июня 2009)
- ↑ Caruana R., Niculescu-Mizil A., An Empirical Comparison of Supervised Learning Algorithms Using Different Performance Metrics(англ.) (Проверено 7 июня 2009)
- ↑ 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)