Thursday, August 18, 2011

Feature selection с примерами на R

В серии постов о data mining я уже описал несколько различных методов и алгоритмов. Они все разные, но у них есть одна неизбежная общая черта: на вход подается некоторый набор "входных параметров" (в англоязычной литературе используется слово feature) и уже дальше начинаются все чудеса и преобразования. В случае с финансовыми данными, этими параметрами могут быть цены, объемы торгов, день недели, технические индикаторы и много чего еще. Но откуда берутся эти параметры и почему они именно такие? До сих пор, этот вопрос я не рассматривал.

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



Проблема отбора параметров решается в большой области знаний, под названием Dimensionality Reduction (уменьшение размерности). В свою очередь, эта область знаний делится на две части Feature Selection (выбор параметров) и Feature Extraction (преобразование параметров). Сегодня мы поговорим о Feature Selection.

Что же из себя представляет Feature Selection? Предположим, что у нас есть некие данные, скажем цены на все акции на бирже и мы хотим по ним спрогнозировать движение рынка в целом (ничего себе задачка...). Что с этим делать? Понятно, что у нас может быть сотни тысяч акций и никакой метод опорных векторов или нейронная сеть не переварит это, а если даже и переварит, то неизбежно произойдет оверфитинг. Стало быть, нам надо часть данных отбросить. Какие именно? Можно, конечно, воспользоваться знаниями предметной области и вручную отобрать значимые параметры, которые, как нам кажется, должны играть наибольшую роль. На самом деле, этот подход является одним из лучших, если в наличии есть специалист глубоко понимающий предметную область. В случае финансов, это проблематично. В других областях, вроде анализа ДНК или обработки текста ситуация аналогична. Стало быть, процесс отбора параметров следует автоматизировать.

Решим задачу на коленке


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

Очевидно, что по каждому из параметров значения не разделимы. Но при этом, если рассматривать связку (x,y), то данные очень легко разделить на две группы. Т.е. даже в системах где параметры по одному не несут никакой дополнительной информации, в совокупности они могут привести к хорошим результатам.

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

Таких методов можно придумать очень много. Все они классифицируются по двум характеристикам. Рассматриваем ли мы параметры по одному или группами и каким образом мы оцениваем удачность подборки параметров.

Классификация методов отбора


По количеству рассматриваемых параметров, методы делятся на:

1) Методы ранжирования параметров.

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

2) Методы работающие с множествами параметров.

На каждом шаге анализируется некоторая комбинация параметров. Вся разница состоит в том, как именно подбираются комбинации. Самый простой вариант, как уже упомяналось выше, это полный перебор всех комбинаций параметров. К сожалению, на практике параметров слишком много и этот подход не работает. Поэтому используется один из менее точных алгоритмов: жадный алгоритм (начать с одного параметра и последовательно добавлять другие, или наоборот начать со всех параметров и последовательно удалять до тех пор пока результат улучшается), генетический алгоритм, simulated annealing, метод градиентного спуска итп.


По способу отбора алгоритмы делятся на:

1) Фильтры.
Название говорит за себя. Очень распространены в совокупности с ранжированием параметров. Идея состоит в том, чтобы отобрать интересующие нас параметры по какому-то критерию. Часто используются стандартные статистические тесты. Этот подход полностью независимы от модели, которая используется для классификации.


2) Обертки.
В этих алгоритмах используется один из методов классификации для оценки качества подбора параметров. Например, мы можем взять набор параметров, натренировать на нем нейронную сеть, а потом оценить качество полученной нейронной сети. Таким образом мы можем поступить многократно с разными наборами параметров и в итоге выбрать лучший. Многие считают что такой подход хорош потому что он подбирает параметры работающие с данной конкретной моделью. Напомню однако, опять же, что если данных мало, то вероятность оверфитинга резко возрастает.


3) Встроенные методы.

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

Пример



Перейдем к примеру, думаю, сразу все станет понятней. Допустим мы хотим узнать какие внешние факторы влияют на поведение индекса РТС. Не секрет, что Россия сырьевая страна и, наверное, можно было бы предположить, что влияет на нас более всего цена на нефть и курс доллара. Но как это проверить? Для проверки, предлагается взять значения индекса РТС и некоторое количество потенциальных параметров: курс доллара, цена на нефть brent, цена на нефть light, цена на золото, американский индекс s&p500, европейский индекс ftse100, цена на серебро и просто некоторая случайная величина, для проверки на вшивость.

Итак, запускаем R, собираем данные (нам потребуется последняя версия модуля rusquant (как его можно установить написано тут). Т.к. все эти параметры торгуются на разных рынках в разных часовых поясах, придется немного поработать над тем, чтобы выровнять их значения по времени. Собственно, я взял все значения в 18 вечера по Москве.

library(rusquant)
"select.hours" <-
function(data, hour){
    return(data[format(index(data), format="%H")==hour])
}


from <- "2007-10-01"
hour <- "18"
period <- "hour"

RTSI <- select.hours(getSymbols("RTSI", src="Finam", from=from, auto.assign=FALSE, period=period), hour)
BRENT <- select.hours(getSymbols("ICE.BRN", src="Finam", from=from, auto.assign=FALSE, period=period), hour)
LIGHT <- select.hours(getSymbols("NYMEX.CL", src="Finam", from=from, auto.assign=FALSE, period=period), hour)
USDRUB <- select.hours(getSymbols("USDRUB", src="Finam", from=from, auto.assign=FALSE, period=period), hour)
GOLD <- select.hours(getSymbols("comex.GC", src="Finam", from=from, auto.assign=FALSE, period=period), hour)
SP500 <- select.hours(getSymbols("SP500", src="Finam", from=from, auto.assign=FALSE, period=period), hour)
FTSE <- select.hours(getSymbols("FTSE", src="Finam", from=from, auto.assign=FALSE, period=period), hour)
SILVER <- select.hours(getSymbols("comex.SI", src="Finam", from=from, auto.assign=FALSE, period=period), hour)

data <- cbind(Cl(RTSI), Cl(USDRUB), Cl(BRENT), Cl(LIGHT), Cl(GOLD), Cl(SP500), Cl(FTSE), Cl(SILVER))

data <- ROC(data[complete.cases(data)])
data <- data[complete.cases(data)][-1]

#добавим случайное значение
data <- cbind(data, rnorm(length(data$RTSI.Close), mean(data$RTSI.Close), sd(data$RTSI.Close)))

names(data) <- c("RTS", "SI", "BRENT", "LIGHT", "GOLD", "SP500", "FTSE", "SILV", "RND")


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

panel.cor <- function(x, y, digits=2, prefix="", cex.cor)
{
    usr <- par("usr"); on.exit(par(usr))
    par(usr = c(0, 1, 0, 1))
    r <- abs(cor(x, y, use="complete.obs"))
    txt <- format(c(r, 0.123456789), digits=digits)[1]
    txt <- paste(prefix, txt, sep="")
    if(missing(cex.cor)) cex <- 0.8/strwidth(txt)
    text(0.5, 0.5, txt, cex = cex * r)
}

pairs(~RTS+SI+BRENT+LIGHT+GOLD+SP500+FTSE+RND, data=data, lower.panel=panel.smooth, upper.panel=panel.cor)


Видно, что все наши параметры, кроме случайной величины, сильно коррелируют между собой и с индексом РТС. Какие-то параметры коррелируют сильнее, какие-то слабее. В целом, картина кажется заслуживающей дальнейшего исследования. Множество алгоритмов feature selection реализовано в пакете FSelector. Попробуем, для начала, самый простой фильтр: посчитаем корреляцию между каждым из параметров и индексом РТС.
library(FSelector)
linear.correlation(RTS~SI+BRENT+LIGHT+GOLD+SP500+FTSE+SILV+RND, data=data)
Результат:
SI         0.54385755
BRENT      0.53846199
LIGHT      0.43151621
GOLD       0.26078314
SP500      0.61501880
FTSE       0.64300959
SILV       0.36046822
RND        0.06929931
В этом тесте наибольшую значимость показали европейский ftse100, американский s&p500, доллар и нефть. Вполне ожидаемо, что наименьшую значимость имеет случайное число. В принципе, на этом можно было бы и остановиться, выбрав 3-4 самых значимых параметров и передав их в модель. Но кто сказал, что это будет оптимальное решение? Другой метод сортировки параметров основан на энтропии. Все кто изучали физику помнят, что энтропия системы это мера беспорядка. В данном случае, мы говорим о информационной энтропии, которая, как ни странно, тоже является, своего рода, мерой беспорядка в системе.
information.gain(RTS~SI+BRENT+LIGHT+GOLD+SP500+FTSE+SILV+RND, data=data)
Результат:
SI         0.32154920
BRENT      0.21683641
LIGHT      0.09690079
GOLD       0.03985278
SP500      0.35216883
FTSE       0.38601392
SILV       0.07476571
RND        0.00000000
Мы получили другие значения, но при этом порядок в котором отсортированы наши параметры не изменился. Перейдем к более сложным методам оценки. Мы продолжим работать с пакетом FSelector и т.к. дальнейшие примеры будут основаны на методах обертках, нам нужна какая-то модель. Для простоты возьмем простейшую модель линейной регрессии.
evaluator <- function(subset) {
    #k-fold cross validation
    k lt;- 5
    splits lt;- runif(nrow(data))
    results = sapply(1:k, function(i) {
      test.idx lt;- (splits >= (i - 1) / k) & (splits lt; i / k)
      train.idx lt;- !test.idx
      test lt;- data[test.idx, , drop=FALSE]
      train lt;- data[train.idx, , drop=FALSE]
      model lt;- glm(as.simple.formula(subset, "RTS"), data=train, family = gaussian)
      delta lt;- test$RTS - predict(model, test)
      error.rate = sum(delta*delta) / nrow(test)
      return(1 - error.rate)
    })
    return(mean(results))
}

На самом деле, у нас не так много параметров и мы можем просто перебрать все возможные комбинации решений. Это конечно занимает несколько минут на моем стареньком ноутбуке, но в данном случае, можно подождать.
exhaustive.search(names(data)[-1], evaluator)
Результат: SI,BRENT,FTSE Здесь у нас уже нет никаких цифр, нам выдается лучший из найденных наборов параметров. И т.к. мы решали методом полного перебора, то мы можем быть уверенными, что это вообще лучшее возможное решение для данной модели. Как видим, оно вполне соответствует нашим изначальным прогнозам. Индекс РТС более всего определяется значениями курса доллара, цены на нефть марки brent и европейским фондовым индексом. Честно говоря, я предполагал что здесь еще будет индекс S&P500, но его не оказалось. Возможно, отчасти потому, что наши биржи слишком сильно разнесены по времени. Возможно если бы мы взяли время отсечки не 18 часов, а 23 часа, то S&P500 играл бы существенно большую роль. Но вернемся к нашим алгоритмам. В данном случае, на входе было всего 8 параметров и нам пришлось ждать ответа несколько минут. Что если параметров было бы 100 или 1000 или еще больше? В таком случае мы можем воспользоваться алгоритмом градиентного спуска или одним из жадных алгоритмов:
> hill.climbing.search(names(data)[-1], evaluator)
[1] "SI"    "BRENT" "SP500" "FTSE"  "SILV" 
> forward.search(names(data)[-1], evaluator)
[1] "SI"    "BRENT" "GOLD"  "FTSE"  "SILV" 
> backward.search(names(data)[-1], evaluator)
[1] "SI"    "BRENT" "SP500" "FTSE"  "SILV"  "RND" 

Результаты другие, тем не менее, они не далеки от оптимальных.

Конечно же это далеко не все возможные подходы, и далеко не все, что можно сделать. Здесь еще можно рассмотреть много интересных вопросов, и к теме feature selection я еще обязательно вернусь.

5 comments:

  1. Спасибо за еще одну доступную и понятную статью!

    Сергей, посоветуйте учебник с введением в data mining / machine learning. Пробовал осилить Elements of Statistical Learning, но тамошняя математика оказалось выше моего текущего уровня.

    ReplyDelete
  2. Посоветую вот этот курс
    http://academicearth.org/courses/machine-learning
    с книжками, к сожалению, ситуация печальная. По отдельным темам еще можно найти материал, а вот с общим введением совсем всё грустно, обычно всё сводится к куче формул, за которыми теряется весь смысл.

    ReplyDelete
  3. Кстати, этот курс в этом году будут преподавать онлайн: http://ml-class.org.
    (заодно: http://ai-class.org от самого Питера Норвига).

    ReplyDelete
  4. Отличная новость! Спасибо :) Тут теперь главное не разорваться.

    ReplyDelete
  5. ОЧЕНЬ МНОГО пунктуационных ошибок - из-за которых не просто тяжело читается, а иногда ещё и ТЕРЯЕТСЯ СМЫСЛ! (ну и ещё: почему ничего нового нет?)

    ReplyDelete