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

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

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

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

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

Деревья принятия решений с примерами на R

Деревья принятия решения это алгоритм из серии "для домохозяек", обычно в том или ином виде с ним встречались все. Мое начальство очень любит такого рода картинки, наверняка и вам доводилось видеть подобное.

Это и есть дерево принятия решений. В силу своей наглядности этот алгоритм часто используется для визуализации данных. И тем не менее, несмотря на свою простоту, алгоритм является чрезвычайно важным в data mining и лежит в основе многих продвинутых методов, таких как random forest, boosted trees итп.

Итак, как же работает дерево принятия решений? Каждая вершина представляет собой точку разбиения данных. Вершина определяет некоторый простой критерий по которому мы делим данные на части. Далее я буду рассматривать только бинарные деревья, где каждая вершина делит данные на две части, именно они используются на практике. Кроме того, я буду рассматривать только простые критерии разбиения данных на части, а именно разбиение по единственному параметру. Таким образом, в каждой вершине дерева мы разбиваем данные на две части согласно значению одного из параметров:

Kaggle.com мы третьи!

И вот, наконец, закончилось мое первое соревнование в kaggle.com с неожиданным для меня результатом: третье место. Это, пожалуй, были самые лучшие два месяца с точки зрения изучения data mining-а и я постараюсь в ближайшее время поделиться своими находками.

Цель соревнования заключалась в том, чтобы предсказать цену бондов (или облигаций, если совсем по-русски) на основе некоторых данных, среди которых: цены последних 10 сделок, объемы сделок, типы сделок, тип бонда, и некая загадочная curve_based_price посчитанная компанией организатором и учитывающая множество фундаментальных факторов, но при этом абсолютно неопределенная для участников соревнования. Вот пример поведения цен и этой загадочной curve_based_price взятый из презентации организаторов.

Сложности добавляла низкая ликвидность на рынке бондов. Некоторые контракты не торговались неделями и, понятно, что ни о каком High Frequency Trading тут и речи идти не может.

Моя первая идея была использовать random forest, благо что и пример организаторов использовал его и в целом было понятно что при такой неопределенности данных эта модель должна как-минимум работать неплохо. Поэтому, первым, что я сделал, это нормализовал цены относительно curve_based_price так, чтобы избавиться насовсем от абсолютных значений в долларах США. Это простое изменение в тот момент подняло меня на 5-ую строчку в рейтинге и мотивировало на дальнейшие исследования. Следующим существенным изменением было разбить тренировочные данные на несколько множеств (по типу сделки и по типу бонда). Основной эффект этого разбиения заключался в том, что эффективное время обучения random forest на большом множестве данных упало многократно. Это изменение подняло меня на первое место где я и находился около месяца. За это время успев получить приглашение от организаторов и посетить Stanford Conference of Quantitative Finance.

А дальше был творческий кризис, я пробовал добавлять различные предикторы, пробовал оптимизировать модель, удалять outliers и даже переписал реализацию random forest на Java надеясь что оптимизировав функцию оценки смогу получить лучший результат. Но тщетно, некоторые изменения давали мне небольшое улучшение, но большинство не влияли на результат либо влияли негативно. Постепенно участники стали формировать команды и я потерял свое первое место и рисковал оказаться в районе 5-го места в финале. Что было бы весьма обидно ведь денежный приз дается только за первые три места. Но в последние три дня нам удалось объединить усилия с участником VikP, посчитать арифметическое среднее наших моделей и выйти на третье место.

Немного разочаровало то, что модели победителей это просто смесь большого количества не самых лучших индивидуальных моделей. Т.е. рецепт победы в общем случае прост: натренируйте кучу разных моделей а потом с помощью линейной регресси найдите оптимальную комбинацию. Такой подход мне кажется немного ущербным. Ведь в основе часто лежат модели типа random forest и GBM которые уже сами по себе являются ансамблями большого числа еще более слабых моделей. Но, видимо, в настоящее время, этот подход является лучшим из известного, достаточно например посмотреть на описания решений победителей промежуточных туров Heritage Health Prize.

Моя новая жизнь

Вот собственно и всё. 17-ти часовой перелет позади, Россия осталась за океаном. А в окно уютной 2-ух спальной квартиры на нас смотрит Сан-Франциско, знаменитая Кремниевая долина, Калифорния, США. Да, это и есть та самая причина, по которой я практически не писал последнее время. Мы переехали.

Всё это началось еще в апреле 2011 года, когда я проходил телефонное интервью в компании Zynga. Тогда это все казалось какой-то игрой не имеющей отношения к реальности и я и представить себе не мог, во что это выльется. В июне 2011 года Zynga приехали в Москву и провели серию собеседований, рассматривалось около 60 кандидатов прошедших телефонное интервью и из них было отобрано около 15 человек (точное число не знаю, кто-то потом передумал, кто-то сразу отказался). Интервью оказалось неожиданно простым. Ни тебе задачек на программирование, ни заковыристых вопросов про форму люков, в основном проверялись способности болтать. А знания, на мой взгляд, оценивались лишь поверхностно.

А дальше началась канитель. Сначала мы ждали результатов, потом офера, потом одобрение LCA, потом одобрения петиции на визу, потом документы из США, потом очередь в посольстве, потом дополнительную проверку, потом визу. Временами мне казалось, что я готов все бросить и забить. Временами я сомневался, а нужна ли нам эта Америка ведь и в России не плохо. Весь процесс занял где-то около полугода, в итоге, в середине декабря мы получили визы и начали готовиться к отъезду.

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

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

Дивиденды rusquant 0.3.3

Выкатил очередное обновление rusquant, помимо мелких фиксов, теперь стали доступны дивиденды по множеству отечественных бумагам. Значения выкачиваются с сайта компании Тройка Диалог.
Дивиденды за последний год можно получить командой:

library(rusquant)
divs <-  getAllDividends()

Все дивиденды, можно получить командой getAllDividends(allYears = TRUE)
Возвращаемый объект содержит следующие данные:

Symbol - id акции на бирже
Name - полное название эмитента
BoardDate - дата собрания совета директоров
RegistryDate - дата закрытия реестра
RecommendedDivs - рекомендуемые дивиденды
Divs - выплаченные дивиденды

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

result <- NULL
    for(i in (1:length(divs[,1]))){
       d <- divs[i,]
       if (d$Divs>0){
          try({
              quotes <- getSymbols(d$Symbol, src="Finam", from="2010-01-01", auto.assign=FALSE)
             if (!is.nan(quotes)){ 
                 price <- Cl(quotes[d$RegistryDate])
                 if (length(price)>0){
                      dd <- d$Divs
                      result <- rbind(result, data.frame(d$Symbol, d$Name, d$RegistryDate, as.numeric(dd)/as.numeric(price), stringsAsFactors=FALSE))
                 }
             }
          }, silent=TRUE)
       }
    }
colnames(result) <- c('Symbol', 'Name', 'RegistryDate', 'Divs')
result[with(result, order(Divs, decreasing=TRUE)),c('Symbol','RegistryDate','Divs')]

Аналогично можно построить статистику для прошлых лет.