Tuesday, July 12, 2011

Метод опорных векторов с примерами на R


Друзья, после продолжительного затишься, я продолжаю тему "data mining с примерами на R". И эта статья посвящается методу опорных векторов (в английской литературе support vector machines или, сокращенно, svm). В интернете масса информации по этому методу и, как всегда, она изобилует сложными математическими формулами, за которыми теряется общая идея. Поэтому я решил написать эту статью без единой формулы, в конце концов, если кому-то нужны формулы, он всегда может обратиться в википедию, скриншот из которой вы можете увидеть слева.


Итак, в чем же состоит идея метода опорных векторов? Давайте, сначала рассмотрим очень простой случай. Предположим, что у нас есть множество точек на плоскости, часть которых относится к классу A, а другая часть к классу B и есть точки класс которых нужно определить. Задачу такого рода, по-научному можно определить как задачу классификации, причем, для её решения, нужен алгоритм обучения "с учителем". Метод опорных векторов как раз подходит именно для таких задач.



Рассмотрим, для начала, упрощенный случай. Пусть точки, принадлежащие разным классам, можно разделить с помощью прямой линии:
Очевидный способ решения задачи в таком случае провести прямую так, чтобы все точки одного класса лежали по одну сторону от этой прямой, а все точки другого класса были на противоположной стороне. Тогда чтобы классифицировать неизвестные точки нам нужно просто посмотреть с какой стороны прямой они окажутся. Халява? Отнюдь, ведь можно провести бесконечное множество прямых удовлетворяющих нашему условию
Какую из них выбрать? Интуитивно понятно, что нам бы хотелось прямую где-нибудь по центру. Такая вот прямая, очевидно, не является лучшим выбором:

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

Геометрически это выглядит так, как будто мы пытаемся провести прямую строго по центру между двумя множествами. Оказывается, что такая прямая существует лишь одна. И её не так уж сложно найти. Ближайшие к этой прямой точки из множеств называются опорными векторами.

В простейшем случае, именно такую прямую и находит метод опорных векторов. Как именно он её находит? Чтобы ответить на этот вопрос пришлось бы привести кучу математических выкладок, которые в итоге сводятся к некоторой системе уравнений, которая, в свою очередь решается методами квадратичного программирования.

А если всё не так гладко?


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

Очевидно, что красная точка справа является выбросом и было бы лучше её игнорировать. Что делать в таком случае? В этом случае на помощь к нам приходит, так называемый, алгоритм с мягким зазором (soft marging). Математически это выражается введением дополнительных параметров в систему уравнений, а по сути, мы просто назначаем некий штраф, за каждую точку, оказавшуюся на чужой стороне. Используя такой подход мы можем работать даже с линейно неразделимыми данными.

Естественно, прямыми на плоскости все дело не ограничивается. Вместо плоскости могут быть сколь-угодно многомерные пространства, а вместо прямых гиперплоскости в этих пространствах. Сам алгоритм, при этом не меняется.

А если все-таки нет прямой?


Если бы это было всё, метод опорных векторов не был бы таким мощным. Действительно, в чем радость разделять данные линейно? С этим отлично могла бы справиться и простая линейная регрессия. На практике, мы не знаем структуру данных и очень редко их можно разделить прямой линией или плоскостью. Что если у нас на входе, например, такая картинка?
Оказывается, что система уравнений составляющая метод опорных векторов содержит только скалярные произведения координат различных точек. И с точки зрения математики, можно заменить каждое скалярное произведение на некоторую функцию (ядро) отвечающую определенным требованиям. Замена скалярного произведения ядром позволяет перевести проблему в пространство с другими измерениями. И в этом пространстве данные могут оказаться разделяемыми. Для примера, предлагаю посмотреть ролик, в котором все наглядно показано.


Таким образом, метод опорных векторов позволяет работать не только с линейно-разделяемыми данными, но и с более общими случаями. Кроме того, на практике, в отличии от, например, нейронных сетей, метод опорных векторов меньше страдает от перетренировки(overfitting): ситуаций, в которых алгоритм выявляет какие-то частные закономерности в тренировочных данных, в результате чего хорошо работает с тренировочным набором, но показывает очень плохой результат на новых и неизвестных данных.

Пример:

Уже по сложившейся традиции, я приведу пример из области финансовых рынков. Идея напрашивается сама собой, раз уж метод опорных векторов так хорошо классифицирует данные и способен работать как черный ящик с очень большим объемом входных параметров, то давайте скормим ему на вход как можно больше технических индикаторов и посмотрим, как хорошо он нам предскажет изменение цены.
Для анализа, мы возьмем индекс S&P500, его значения могут быть загружены автоматически в программу на R с помощью модуля quantmod. А реализацию метода опорных векторов мы найдем в пакете e1071.

В своих прошлых статьях я уже писал о том, как настроить R и как устанавливать требуемые пакеты. Поэтому перейдем сразу к делу.

Сначала нам предстоит провести подготовительную работу с данными, а именно, преобразовать их в удобоваримую форму:

library(quantmod)
library(e1071)

#Будем исследовать индекс S&P500
getSymbols("^GSPC", from='2005-01-01')
data <- GSPC

#Накидаем в нашу модель побольше разных индикаторов
atr <- ATR(data)[,'atr']
ema7 <- EMA(Cl(data), n=7)[,1]
ema14 <- EMA(Cl(data), n=14)[,1]
ema50 <- EMA(Cl(data), n=50)[,1]
macd <- MACD(Cl(data))[,'macd']
macd.signal <- MACD(Cl(data))[,'signal']
rsi <- RSI(Cl(data))
cmo <- CMO(Cl(data))
dc.high <- DonchianChannel(Cl(data))[,'high']
dc.low <- DonchianChannel(Cl(data))[,'low']
adx <- ADX(data)[,'ADX']

#определим модель, здесь важно сдвинуть либо предсказываемые значения на день вперед либо предикторы на день назад
model <- specifyModel(Next(Delt(Cl(data))) ~ atr + ema7 + ema14 + ema50 + macd + macd.signal + rsi + cmo + dc.high + dc.low + adx)

#разделим данные на две части - тренировочные и тестовые
train.window <- c('2005-01-01','2009-01-01')
validate.window <- c('2009-01-01', '2011-06-29')

train <- na.omit(as.data.frame(modelData(model, data.window=train.window)))
validate <- na.omit(as.data.frame(modelData(model, data.window=validate.window)))

#мы хотим покупать или продавать, когда индекс изменяется как минимум на 0.5% в ту или иную сторону, остальные случаи нас не интересуют
signals<-function(x) {

	if(x >= -0.005 && x<=0.005) { result<-"none" } else
	if(x > 0.005) { result<-"buy" } else
	if(x < -0.005) { result<-"sell" }

	result
}

#классифицируем имеющиеся данные, не забыв при этом выбросить из них сами цены, чтобы алгоритм не подсматривал ;)
class<-sapply(train$Next.Delt.Cl.data,signals)
train<-cbind(train,class)
train$Next.Delt.Cl.data <- NULL

class<-sapply(validate$Next.Delt.Cl.data,signals)
validate<-cbind(validate,class)
validate$Next.Delt.Cl.data <- NULL

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

#подготовка данных закончилась, можно запускать SVM на тренировочных данных
sv<-svm(class~.,train,gamma=0.01,cost=5,kernel="radial")

#а теперь посмотрим, насколько точно наш алгоритм предсказывает тестовые данные
table(actual=validate$class,predicted=predict(sv,newdata=validate,type="class"))

Полученные результаты оказываются лишь немного лучше, чем бросание монетки:
predicted
actual  buy none sell
  buy   60  136    3
  none  39  227    3
  sell  52  102    4

Что делать? Попробуем оптимизировать параметры, в конце концов, в документации к svm английским по белому сказано "Parameters of SVM-models usually must be tuned to yield sensible results! " Попробуем подобрать более оптимальные значения. К счастью для нас, нет никакой необходимости делать это вручную, модуль e1071 содержит метод tune который сделает всю работу. Для этого он применит кросс-валидацию. В процессе кросс-валидации тренировочные данные разбиваются на две части, модель тренируется на одной части, а тестируется на другой и так многократно. В итоге, выбираются лучшие параметры и модель с лучшими параметрами тренируется снова уже на полном наборе тренировочных данных. Все просто. Приступим:
#попробуем подобрать оптимальные параметры для алгоритма методом кросс-валиадации, эта строчка может выполняться несколько часов перебирая все возможные 

комбинации параметров
tuned <- tune(svm, class~., data = train,ranges = list(gamma = c(0.0001,0.001,0.05,0.1,0.2,0.3), cost = c(1,5,10,20,50,100,120,130)),tunecontrol = tune.control(sampling = "cross"),cross=3)

tuned


Дальше мы просто копируем найденные оптимальные значения и запускаем наш алгоритм снова

#подготовка данных закончилась, можно запускать SVM на тренировочных данных
sv<-svm(class~.,train,gamma=0.05,cost=10,kernel="radial")

#а теперь посмотрим, насколько точно наш алгоритм предсказывает тестовые данные
table(actual=validate$class,predicted=predict(sv,newdata=validate,type="class"))

Результаты, конечно не идеальны, но очевидно, что стали намного лучше.
predicted
actual buy none sell
  buy   73  123    3
  none  46  215    8
  sell  48   99   11

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

12 comments:

  1. Отличная статья! Спасибо!
    Не могли бы вы рассмотреть в следующих статьях конкретные методики http://en.wikipedia.org/wiki/Feature_selection и http://en.wikipedia.org/wiki/Feature_extraction - ведь это именно та самая интересная часть этого подхода классификации, которая позволяет добиваться впечатляющих результатов. Было бы чертовски интересно почитать!

    ReplyDelete
  2. Михаил, спасибо за комментарий. Полностью согласен с Вами, это очень важная и интересная тема, и мы до нее обязательно доберемся!

    ReplyDelete
  3. Таблички показывают, насколько хорошо мы прогнозируем тестовые данные, а как посмотреть сам прогноз по текущим данным? т.е. как начать ту систему использовать?

    ReplyDelete
  4. Вроде понял:

    > predicted=predict(sv,newdata=validate,type="class")

    > predicted

    ReplyDelete
  5. В ML-class мы наконец добрались до SVM'ов (давно уже не терпелось попробовать). Гениальный алгоритм. Там где нейросеть тренировалась несколько часов, и все равно не быо уверернности что она нашла глобальный оптимум, SVM через libsvm за минуту конвергирует к глобальному оптимуму.

    Сергей, если вы еще не забросили этот блог, предлагаю для обсуждения такие темы:
    - трансляция предсказаний модели в торговые тактики
    - использование времени в качестве признака
    - какие есть варианты алгоритмов назначения target output'ов
    -

    ReplyDelete
  6. * - обучение без учителя

    Конечно, все применительно к биржевой торговле. :)

    ReplyDelete
  7. Добрый день, Матвей, спасибо за комментарий.
    В связи с происходящими в моей жизни событиями, о которых я непременно напишу, если все сложится и стыдливо умолчу, если все провалится :) испытываю пока чудовищную нехватку времени. Тем не менее, я рассчитываю продолжить графоманскую деятельность и продолжить написание статей в ближайшем будущем. Спасибо за подсказанные темы, подумаю, что можно сделать.

    ReplyDelete
  8. Сергей, день добрый!
    Подскажите, пжлст, не могу разобраться с командами:
    sv<-svm(class~.,train,gamma=0.05,cost=10,kernel="radial") и
    table(actual=validate$class,predicted=predict(sv,newdata=validate,type="class"))

    А именно, как устроены "svm", "class!." и почему "type="class""

    Заранее благодарен за пояснения.

    с уважением, Дмитрий

    ReplyDelete
  9. Сергей, еще хотел бы уточнить:
    1. какие еще есть параметры у SMV? Нигде не могу найти документацию по нему..

    2. как-то возможно графически показать, какие именно результаты были получены:
    Т.е. таблицу
    Наблюдение / Модельные данные / Фактические данные

    ReplyDelete
  10. Очень интересная статья! К сожалению на тему машинного обучения и нейронных сетей на русском языке очень мало информации. Спасибо за ваш труд!

    ReplyDelete
  11. Отличная статья, большое спасибо!

    ReplyDelete
  12. Отличная статья, но есть один вопрос.. Если метод опорных векторов применяется в банковской практике оценки кредитоспособности заемщика, как работает этот метод, как его можно объяснить?

    ReplyDelete