Wednesday, May 16, 2012

Random Forest с примерами на R

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

В чем же идея такого замечательного алгоритма? Идея проста: допустим у нас есть какой-то очень слабый алгоритм, скажем, дерево принятия решений. Если мы сделаем очень много разных моделей с использованием этого слабого алгоритма и усредним результат их предсказаний, то итоговый результат будет существенно лучше. Это, так называемое, обучение ансамбля в действии. Алгоритм Random Forest потому и называется "Случайный Лес", для полученных данных он создает множество деревьев приятия решений и потом усредняет результат их предсказаний. Важным моментом тут является элемент случайности в создании каждого дерева. Ведь понятно, что если мы создадим много одинаковых деревьев, то результат их усреднения будет обладать точностью одного дерева.

Как он работает? Предположим, у нас есть некие данные на входе. Каждая колонка соответствует некоторому параметру, каждая строка соответствует некоторому элементу данных.

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




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


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

Этот удивительно простой алгоритм и самым сложным шагом в его реализации является построение дерева decision tree. И не смотря на свою простоту он дает очень хорошие результаты в реальных задачах. С практической точки зрения у него есть одно огромное преимущество: он почти не требует конфигурации. Если мы возьмем любой другой алгоритм машинного обучения, будь то регрессия или нейронная сеть, они все имеют кучу параметров и их надо уметь подбирать под конкретную задачу. Алгоритм random forest имеет по-сути лишь один параметр: размер случайного подмножества выбираемого на каждом шаге построения дерева. Этот параметр важен, но даже значения по-умолчанию позволяют получить весьма приемлемые результаты.

Перейдем теперь к примеру на R
В R random forest реализован в пакете под названием randomForest (удивительно). Для сегодняшнего примера я воспользуюсь теми же данными что и в статье про деревья принятия решений. Попробуем предсказать изменения в объемах торгов акциями Газпрома на следующий день.

#Где взять пакет rusquant и как его установить можно посмотреть тут http://www.algorithmist.ru/p/rusquant.html 
library(rusquant)
getSymbols('GAZP', from='2003-05-01', to='2012-05-09', src='Finam')

#для повторяемости результатов
set.seed(1)
label <- (Vo(GAZP) - lag(Vo(GAZP)))/lag(Vo(GAZP))
names(label) <- c('label')
data <- lag(GAZP)

data <-cbind(lag(label), lag(label, k=2), lag(label, k=3), lag(label, k=4), lag(label, k=5), RSI(Cl(data)), MACD(Cl(data)), volatility(data), factor(weekdays(index(label))))
names(data) <- c('Volume1', 'Volume2', 'Volume3', 'Volume4', 'Volume5', 'RSI', 'macd', 'signal', 'volatility', 'weekdays')
data <- cbind(label, data)
data <- data[complete.cases(data),]

# 80% данных используем для тренировки модели, 20% для тестирования
split <- runif(dim(data)[1]) > 0.2
train <- data[split,]
test <- data[!split,]

Код для тренировки random forest в R очень прост:
#random forest
library(randomForest)
rf <- randomForest(label ~ ., train)
predictions <- predict(rf, test)
print(sqrt(sum((as.vector(predictions - test$label))^2))/length(predictions))
В результате получается точность 0.02157 что полностью согласуется с результатами полученными с помощью ансамбля деревьев. Можно ли как-то подкрутить этот алгоритм? Если не считать вопросы скорости работы, есть только один параметр который имеет смысл менять mtry - он определяет, сколько столбцов тестируется при поиске следующего разбиения, для каждого дерева. Но его изменения не сказываются на результате принципиальным образом. Лучшее значение, которое мне удалось выжать, при mtry=3 было 0.02149. Подобрать оптимальное значение mtry поможет функция tuneRF Кроме того, random forest позволяет оценить качество используемых предикторов.
importance(rf)
В нашем примере получилось:
           IncNodePurity
Volume1        136.11990
Volume2         24.80163
Volume3         15.96727
Volume4         19.43955
Volume5         32.80988
RSI             18.90843
macd            18.68504
signal          18.35107
volatility      21.04426
weekdays        13.54460
Т.е. самым значимым предиктором оказалось изменение объема в предыдущий день, все остальные несли гораздо меньше информации. Это функция алгоритма random forest может помочь при выборе предикторов и провести простейший feature selection. Помимо перечисленных возможностей в пакете randomForest есть еще много интересных функций, часть из них позволяют лучше распределять работу при тренировке случайного леса, часть визуализировать данные, вставлять пропущенные значения итп. В следующей статье я расскажу о том, как мы боролись за скорость при использовании случайного леса в последнем соревновании.


16 comments:

  1. Сергей, отличная статья!

    Позволю себе лишь несколько "реплик":

    1) "Случайное подмножество выбираемое на каждом шаге построения дерева" - пожалуй, самый важный, но не единственный важный параметр для настройки RF. Часто важным является также количество выращиеваемых деревьев, от которого может зависеть достигаемый уровень ошибки классификации. Кроме того, при резко несбалансированных классах (например, очень много 0 и лишь небольшое количество 1) важно выполнять страцифицированный сэмплинг для выравнивания уровней ошибки классификации в каждом из этих классов.

    2) По поводу "важности" предикторов: я бы упомянул, что функция randomForest считает два показателя - Gini index и Mean Decrease in Accuracy, и сказал бы, какой именно рассчитан в примере. Первый из этих индексов часто "ругают" за то, что дает смещенные оценки значимости, особенно при наличии сильно кореллирующих предикторов. Второй - лучше, но тоже есть ньюансы - рекомендуется его приводить в unscaled форме (scale = FALSE).

    Но все это так - "размышления вслух"... Спасибо за блог!

    ReplyDelete
    Replies
    1. Сергей, огромное спасибо за "реплики"! Именно ради таких комментариев я и веду блог, буду рад новым комментариям и общению.

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

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

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

    3. Производить отбор переменных по значению их важностей в модели, для меня является сомнительным шагом. Таким образом, мы подгоняем нашу модель под обучающую выборку, и теряется ее обобщающая способность. В тех задачах, с которыми я работаю, мне не удалось добиться заметного повышения точности прогноза независимой тестовой выборки при отборе переменных таким способом. А вот ухудшить получилось.

    А вообще сам метод очень хорош. Несколько лет назад реализовал его на Делфи (сайт в почти заброшенном состоянии http://qsar4u.com), с некоторыми наворотами для внутренних нужд (внутренней оценкой вкладов переменных по типу регрессионных коэффициентов для интерпретации моделей; есть модуль, в котором реализовано построение моделей без загрузки в память всего набора данных, для анализа очень больших датасетов и др). Алгоритм идеально параллелится, в R в том числе. Можно хоть на кластерах Амазона запускать. Сейчас сам в основном пользуюсь версией RandomForest реализованной в R.

    ReplyDelete
  3. Сергей, привет!
    Прочитал статью про деревья решений и эту - супер!
    Теперь логично было бы еще написать о самом ансамбле, а то как то не ясно что потом после построения набора деревьев происходит. Ведь, насколько я помню, результаты деревьев не просто тупо усредняются, а (в простейшем случае) у каждого дерева есть свой весовой коэффициент с которым он входит в конечный результат.
    Кстати, с помощью чего ты картинки рисуешь ?

    ReplyDelete
    Replies
    1. Привет, Владимир!
      В том то и прелесть random forest что результаты деревьев просто усредняются. Никаких весов, никаких регрессий, просто и элегантно. Есть другие алгоритмы, вроде GBM, но их намного сложней использовать и не всегда результат оправдывает ожидания.

      Картинки рисую в маковском Paintbrush.

      Delete
  4. Вы что-нибудь слышали о методе прогнозирования временных рядов "гусеница"? В сети есть материалы с примерами на R. У вас очень хороший стиль изложения. Может "забабахаете" пост на эту тему?

    ReplyDelete
    Replies
    1. Спасибо за идею. Слышал но очень мало, для того чтобы писать пока явно не достаточно, хорошо бы попробовать на практике в какой-нибудь реальной задаче.

      Delete
  5. Присоединяюсь. R великолепный пакет. вот пример использования R для построения логрегрессии. может кому-то пригодится
    http://gewissta.livejournal.com/9010.html

    ReplyDelete
  6. Жаль, что нет продолжения

    ReplyDelete
  7. This comment has been removed by the author.

    ReplyDelete
  8. не работает rusquant. такое выдает This message is shown once per session and may be disabled by setting
    options("getSymbols.warning4.0"=FALSE). See ?getSymbol for more details
    Ошибка в names(res) <- unlist(names) :
    атрибут 'names' [10973] должен быть той же длины, что и вектор [10972]

    ReplyDelete
  9. Всем добрый день. Прежде всего хочу поблагодарить за статью и за сам сайт. Я только погружаюсь в тематику machine learning и у меня есть вопрос - просьба. Не мог бы кто нибудь объяснить метод на конкретном примере, так сказать на пальцах? У меня есть база данных по кредитному скорингу, нужно применить данный метод, более того, результаты данного расчета измерить на аккуратность, применить percentage correctly classified или partial Gini Index. Может кто либо мне помочь? Я не хочу, чтобы кто то это сделал за меня, просто на нормальном языке показывать все шаги расчета? Пожалуйста ответье на find.me.hereСОБАКА.ru Артем

    ReplyDelete
  10. У randomforest есть очень нехорошая черта -- он по сути хорошо интерполирует данные, с экстраполяцией у него весьма плохо обстоят дела. Если какой то участок пространства состояния изучаемой системы показателей не покрыт экспериментальными точками, то в этой зоне алгоритм дает крайне слабое предсказание. Очевидно, что причиной служит лежащее в его основе дерево решений, оно просто проводит сечения переменных, и в зоне отстутвия экспериментальных точек это просто "горизонтали" и "вертикали" (ну и соответственно их усреднение по ансамблю в виде "горизонталей" и "вертикалей").

    ReplyDelete
  11. Про то, что «дерево решений строится очень быстро» — неправда. Я на компьютере с 32-я ядрами строил одно дерево решений, и процесс занял 2 недели. Трудно представить, сколько бы строился целый лес…

    ReplyDelete
  12. Сергей, как с вами связаться? В профиле не нашел, сайт давно не обновлялся

    ReplyDelete