Wednesday, May 16, 2012

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

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

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

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

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


Thursday, May 10, 2012

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

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


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

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


Thursday, May 3, 2012

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.