Thursday, May 10, 2012

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

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


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

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




Дальше для каждой части мы повторяем операцию и в итоге получаем дерево. Для простоты реализации часто используют рекурсию. Здесь неочевидными остаются только три вещи:
1. Как выбирается параметр по которому происходит разбиение
2. Как выбирается пороговое значения параметра
3. Когда алгоритм должен остановиться

Ответы на эти вопросы зависят от реализации. Существует несколько популярных реализаций со странными названиями типа ID3, C4.5, CARD. Возьмем, к примеру, CARD, как он отвечает на эти вопросы? Параметр по которому происходит разбиение и пороговое значение этого параметра находятся методом полного перебора. Т.е. мы просто пробуем все возможные способы разбиения данных по каждому из параметров и оцениваем, насколько разбиение было удачным. А как оценить удачность разбиения? Очень просто, выполняя каждое разбиение мы получаем некоторое промежуточное дерево и его возможности классификации или регрессии нужно оценить. Вот тут то на помощь приходят понятия вроде информационной энтропии и коэффициентов Джини. В моей практике, степень удачности разбиения часто определялась условиями задачи, а именно, критерием, который мы пытаемся оптимизировать.

Когда алгоритму остановиться? Есть два варианта: когда дальнейшие разбиения не способны улучшить дерево, например если в текущей вершине все элементы имеют одинаковое значение. Либо когда мы достигли определенного уровня, например в вершине 5 или меньше элементов (этот критерий используется по-умолчанию в реализации random forest в R)

Существует несколько модулей в R которые реализуют деревья принятия решений, мне доводилось работать с tree и rpart. Они чрезвычайно похожи, в основе обоих лежит один и тот же алгоритм, но rpart предоставляет больше возможностей и быстрее работает. tree это реализация CART из языка программирования S, этот модуль был реализован для поддержки других пакетов и если вы не являетесь фанатом S, то стоит остановиться на rpart.

Мы плавно пришли к примеру. Для примера попробуем предсказывать изменения в объемах торгов акциями Газпрома на рынке ММВБ на следующий день (цены предсказывать дело не благодарное, поэтому объемы). В качестве предикторов будем использовать изменения в объемах торгов за предыдущие 5 дней, несколько стандартных технических индикаторов и день недели. Итак, скачаем и сформируем данные:

#Где взять пакет 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,]

Для начала проведем небольшую проверку на адекватность (sanity check) чтобы понимать, будет ли наш алгоритм вообще предсказывать что-то или нет. Предположим, что объемы торгов вообще не меняются и посмотрим, какую ошибку даст это предположение:
#бенчмарк
print(sqrt(sum((as.vector(test$label))^2))/length(test$label))
В результате получаем: 0.02397 Теперь посмотрим что способно предсказать одно единственное дерево:
library(rpart)

#тренируем дерево принятия решений
tree <- rpart(label ~ ., train)
predictions <- predict(tree, test)
print(sqrt(sum((as.vector(predictions - test$label))^2))/length(predictions))

Результат: 0.02442 - чуть-чуть хуже чем бенчмарк. Не очень то оптимистично. Как можно улучшить этот результат? Как я уже писал, тенденция последнего времени, если одна модель работает плохо, надо объединить много моделей. Поступим следующим образом, будем из наших данных выбирать подмножества: примерно 70% столбцов и примерно 70% рядов, и потом для этих подмножеств генерить деревья. Дальше, получив много таких деревьев для разных подмножеств мы просто посчитаем арифметическое среднее для результатов их предсказаний. Смысл генерации подмножеств в том, чтобы как-то рандомизировать деревья, ведь если просто сгенерить много одинаковых деревьев и усреднить их предсказания то результаты никак не улучшатся. Здесь есть очень важный момент в вызове функции rpart следует передавать параметр control=rpart.control(cp=.0), он необходим для того чтобы алгоритм строил полные деревья не удаляя вершины, которые не приводят к существенному улучшению результата. Без этой опции деревья будут получаться слишком похожими и усреднение ничего не даст.
ntrees <- 300
res <- numeric(ntrees)
prd <- numeric(nrow(test))
for(i in 1:ntrees){
    #выберем 70% рядов и колонок из множества данных
    x <- runif(nrow(train))>0.3;
    y <- runif(ncol(train))>0.3;
    #обязательно включим label
    y[1] <- TRUE
    traindata <- train[x,y]
    #генерим полное дерево не оптимизируя процесс
    tree <- rpart(label ~ ., traindata, control=rpart.control(cp=.0))
    #усредняем предсказание со всеми предыдущими деревьями
    prd <- prd + predict(tree, test)
    predictions <- prd / i
    #оцениваем ошибку
    res[i] <- sqrt(sum((as.vector(predictions - test$label))^2))/length(predictions)
    print(res[i])
}

plot(res, type='l')

В результате для 300 деревьев мы получаем ошибку: 0.02170 что намного лучше чем одно дерево и бенчмарк. Теперь результаты стали гораздо интересней. Посмотрим как изменяется ошибка в зависимости от количества деревьев:
На графике видно типичное поведение ошибки при тренировке ансамбля. Видно что где-то к 30 деревьям результат стабилизируется и дальнейшее добавление деревьев слабо влияет на ошибку. По-сути мы только что построили подобие алгоритма random forest для регрессии. Аналогичным образом можно построить алгоритм для классификации. Когда я запускал эти же алгоритмы на предварительно обработанных данных для kaggle.com, первый дал результат 0.85076, что принесло бы примерно 100-ое место, а второй всего лишь с десятью деревьями дал бы 0.73623 очков и 10-ое место. Что не сильно хуже полноценного random forest, но об этом в следующий раз.



6 comments:

  1. Очень интересные статьи! Спасибо!

    ReplyDelete
  2. Большое спасибо. Рад что вернулись и продолжаете писать)

    ReplyDelete
  3. Всегда пожалуйста! Постараюсь больше не исчезать :)

    ReplyDelete
  4. Спасибо! Попутно с мануалом по rpart статья помогла разобраться.

    ReplyDelete
  5. Спасибо, только единственный вопрос: как именно увидеть предсказанное значение?

    Алекс

    ReplyDelete
  6. SergE, существуют ведь более интересные подходы, чем просто среднее арифметическое, позволяющие объединить результаты нескольких алгоритмов. Как вариант, метод Байеса (статистический подход) или попытаться выделить наилучший алгоритм для отдельно взятой точки (учитываем локальные свойства алгоритмов, т.е. что каждый их них работает с переменным успехом с разными точками). Я говорю не только про решающие деревья, в других ваших статьях вы тоже усредняете.

    ReplyDelete