Оптимизированные реализации алгоритма Random Forest

43

Я заметил , что есть несколько реализаций случайного леса , такие как ALGLIB, вафли и некоторые R пакеты , например randomForest. Кто-нибудь может сказать мне, высоко ли оптимизированы эти библиотеки? Являются ли они в основном эквивалентными случайным лесам, как подробно описано в «Элементах статистического обучения», или добавлено много дополнительных уловок?

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

Генри Б.
источник
Случайные джунгли могут работать на многих серверах параллельно. См .: Schwarz, et al (2010). На сафари в случайные джунгли: быстрая реализация случайных лесов для многомерных данных. Биоинформатики, 26 , 14, с 1752-8, doi.org/10.1093/bioinformatics/btq257 . код: 1 ; 2 ; 3 ; 4 .
Пользователь128525

Ответы:

31

(Обновлено 6 IX 2015 с предложениями от комментариев, также сделано CW)

Для R есть два новых хороших пакета, которые довольно хорошо оптимизированы для определенных условий:

  • Рейнджер - C ++, R пакет, оптимизированный для проблем, параллельно, специальной обработки данных GWAS.p>>n
  • Лесовод - C ++, R и Python привязка, оптимизированная для крупно- проблем, по- видимому планов GPGPU.n

Другие реализации РФ:

  • Original One - автономный код на Фортране, не параллельный, довольно сложный в использовании.
  • randomForest - пакет C, R, вероятно, самый популярный, не параллельный, на самом деле довольно быстрый по сравнению с одноядерной скоростью, особенно для небольших данных.
  • randomForestSRC - C, R пакет, клон randomForest, поддерживающий параллельную обработку и проблемы выживания.
  • партия - C, R пакет, довольно медленный, но задуманный как самолет для экспериментов с RF.
  • bigrf - пакет C + / R, R, созданный для работы с большими данными в рамках структуры памяти ; довольно далеко от завершения.
  • Scikit Learn Ensemble forest - Python, часть параллельной среды Scikit-Learn, реализует множество вариантов RF.
  • молочный рф - питон, часть молочной основы.
  • Вафли - C ++, часть большого набора инструментов ML, параллельные и довольно быстрые.
  • так называемый WEKA rf - Java / WEKA, параллельный.
  • ALGLIB
  • Случайные джунгли - заброшены?
  • рт-ранг - заброшен?
  • PARF - заброшенный?

Бумага Ranger имеет некоторые сравнения скорости / памяти, но нет никакого тщательного теста.

user88
источник
6
Теперь можно добавить sklearn.ensemble из набора инструментов Python scikit-learn.
хл
1
В Milk in Python также есть реализация Random Forest.
JEquihua
3
Случайные джунгли были заменены Рейнджером. Я попробовал версию R (есть другая версия C ++), и она заметно быстрее, чем randomForest (хотя я и не рассчитывал время). Автор провел некоторое тестирование в отдельной статье ( arxiv.org/abs/1508.04409 ).
NoviceProg
11

Насколько я знаю, R-версия randomForest вызывает тот же код на Фортране, что и оригинальная версия. Кроме того, распараллелить функцию randomForest тривиально. На самом деле это один из примеров, представленных в документации foreach .

library(foreach)
library(randomForest)
rf <- foreach(ntree = rep(250, 4), .combine = combine, .packages = "randomForest") %dopar% 
randomForest(x, y, ntree = ntree)

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

Единственная проблема заключается в том, что в комбинированном лесу вы теряете оценку погрешности «вне пакета», но, вероятно, существует простой способ ее вычисления (мне бы очень хотелось узнать, как это сделать).

Zach
источник
7

ELSII используется RandomForest (смотри , например, сноска 3 p.591), который является реализацией R от Breiman и Катлер Fortran код из Salford. Код Энди Лиу находится в C.

Есть еще одна реализация RF, предложенная в пакете party (в C), которая опирается на R / Lapack, который имеет некоторые зависимости от BLAS (см. /include/R_ext/Lapack.hВ вашем базовом каталоге R).

Что касается упаковки, то не должно быть слишком сложно распараллелить ее, но я позволю более специализированным пользователям ответить на этот аспект.

хл
источник
5

Группа разработчиков randomJungle утверждает, что она на порядок быстрее, чем реализация R randomForest, и использует на порядок меньше памяти. Пакет для randomJungle разрабатывается для R, но я пока не могу его собрать.

https://r-forge.r-project.org/projects/rjungler/

GPR
источник
Не уверен, что это все еще вас интересует через 4 года, но автор (ы) randomJungle заменил его на Ranger. Я попробовал R ver, и это действительно заметно быстрее, чем randomForest с некоторыми образцами данных (хотя я не рассчитывал время).
NoviceProg