Thursday, April 14, 2011

Метод поиска ближайшего соседа с примерами на R

Продолжаю серию про методы и алгоритмы data mining. Предыдущая статья была посвящена линейной регрессии. Эта статья посвящается методу ближайшего соседа. Идея метода ближайшего соседа очень проста на интуитивном уровне. Давайте рассмотрим простой пример.

Простой пример метода ближайшего соседа

Рассмотрим зарплаты людей, в зависимости от их места жительства. Предположим, что вы живете в центре Москвы и что рядом с вами живут люди с зарплатой 150 тыс рублей. Тогда, можно предположить, что и ваша зарплата близка к этой величине. Если же вы проживаете в поселке Новотагилка Челябинской области, и зарплаты ваших соседей около 3 тыс рублей, то скорее всего и ваша зарплата близка к 3 тыс рублей. Естественно, что здесь нет 100% точной зависимости, кто-то может жить в центре Москвы на пенсию в 6 тыс, а кто-то в Новотагилке зарабатывать 50. Но если единственная информация, которой мы владеем о человеке является его место жительства, то мы можем воспользоваться приведенным подходом для оценки его доходов.

Аналогично работает и метод ближайшего соседа, разница лишь в том, что вместо коллег ищутся некоторым образом схожие элементы, причем схожесть определяется множеством различных факторов. Если, как и в нашем примере, речь идет о зарплатах, то могут быть использованы так же данные о профессии, образовании, стаже работы, поле и возрасте. Дополнительные данные, с одной стороны, усложняют задачу вводя дополнительные измерения. С другой стороны, они позволяют гораздо более точно предсказать результат. Например, если вы знаете что данный человек программист, работает и живет в москве, имеет опыт около 10 лет, то предсказать его зарплату можно значительно точнее.

А в попугаях я гораздо длиннее

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

Основная сложность в применении этого метода состоит в том, что нам необходимо четко определить понятие «близости». Это, в свою очередь, приводит нас к понятию расстояния между элементами. На практике можно использовать различные виды расстояний, но чаще всего достаточно простого евклидова. При выборе мерила расстояний важно учитывать единицы измерения. Ведь нам, возможно, придется включить в одну величину свойства разной природы, например доход (деньги), возраст (годы), вес (кг) итд. Кроме того, например деньги можно мерить в рублях, копейках, долларах, золотых слитках и много чем еще, в зависимости от единицы измерения расстояния между элементами будут получаться разные. Выбор единиц измерения невозможно автоматизировать, эта задача остается за пользователем алгоритма и зависит от конкретной области применения и имеющихся данных.

А если нет элемента?

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

Обычно эта проблема решается следующим образом, выбирается некоторое последовательное число котировок. Например 10, первые 9 из них объявляются предикторами, а последнее искомым значением. Получается что-то вроде движущегося окна. Например, если у нас есть 100 последовательных значений, мы можем сначала взять значения 1-9 для тренировки, 10 — как искомое. Потом значения 2-10 для тренировки, 11 — искомое. Естественно, что при таком разбиении часть данных будет перекрываться, но искомое значение, каждый раз новое.

Метод k ближайших соседей

Главная проблема метода ближайшего соседа это его чувствительность к выбросам (outliers) в тренировочных данных. Возьмем пример на картинке:

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

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

Метод k ближайших соседей, так же, позволяет оценить точность прогноза. Если все k ближайших соседей имеют одно и то же значение, то шансы что проверяемый объект будет иметь такое же значение очень высоки. Если же среди этих объектов 40% имеют одно, а 60% другое значение, то вероятность правильного прогноза существенно снижается. Таким образом мы можем использовать распределение голосов между соседями для оценки точности прогноза.

Пример


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

Итак, задача: предсказать движения индекса S&P500 по его изменениям за прошлые 4 дня. Изменения считаем от закрытия к закрытию. К счастью для нас, ничего кроме R и нескольких дополнительных модулей к нему не нужно:

#раскоментировать если библиотека knnflex или quanmod не установлена
#install.packages("knnflex")
#install.packages("quantmod")

library(knnflex)
library(quantmod)

#получаем данные по индексу S&P500 с 2007 года
getSymbols("^GSPC", from="2007-10-01")

#считаем доходность по дням от закрытия до закрытия
roc <- ROC(Cl(GSPC)) 

# записываем в каждый ряд x изменения за прошедшие 4 дня
x <- cbind(lag(roc), lag(roc, k=2), lag(roc, k=3), lag(roc, k=4))

# в у записываем то, что нам надо предсказать
y <- roc

#тренировочные данные - это все данные за исключением последних 30 дней
train <- 1:(length(roc)-30)

#проверочные данные это все остальные данные, т.е. данные за последние 30 дней.
test <- (1:(length(roc)))[-train]

#Это самая важная строчка! 
#Считаем расстояние между каждой парой точек, в нашем случае это просто Евклидово расстояние 
#в 4-х мерном пространстве 
kdist <- knn.dist(x)

#считаем методом k-ближайших соседей результат
#первый параметр – индексы тренировочных данных
#второй параметр – индексы тестовых данных
#третий параметр – вектор с результатами для тренировочных данных
#четвертый параметр – матрица расстояний посчитаная строчкой выше
#k=3 – используем 3 ближайших соседа
preds <- knn.predict(train,test,y,kdist, k=3)

#связываем результат с исходными данными
results <- cbind(preds, y[test])

#считаем доходность за месяц
last(cumprod(1+ results[,2] * ifelse(results[,1]< 0, -1, 1)))
Результат работы:
2011-04-12      1.024020
Т.е. доходность за 30 дней составила 2.4%.

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

7 comments:

  1. Сергей, к сожалению не нашел, как с Вами связаться. Я очень интересуюсь темой data mining и алгоритмами и предполагаю, что Вы изучили достаточно материала по этим темам. Можете ли вы подсказать отправные точки в изучении данных областей? Это могут быть полезные книги, ресурсы и т.п.

    ReplyDelete
  2. kidopt, спасибо Ваш за комментарий, контакты обязательно добавлю.

    По алгоритмам, на мой взгляд лучшей является книга: Кормена "Алгоритмы. Построение и анализ" Если есть возможность - читайте в оригинале, на английском.

    Что касается data mining, по-моему его лучше изучать отталкиваясь от области применения (финансы, маркетинг, медицина...) Тема очень большая и стремительно развивается. Я собираю информацию по кусочкам из разных источников (научные статьи, блоги, лекции - все на английском). Более-менее цельную картину можно найти в курсе лекций stanford machine learning - видео можно скачать http://see.stanford.edu/see/courseinfo.aspx?coll=348ca38a-3a6d-4052-937d-cb017338d7b1 Из книжек пока, к сожалению, ничего посоветовать не могу. Если найдете хорошую, дайте, пожалуйста, знать.

    ReplyDelete
  3. Я бы порекомендовал книжку Сиенны (http://algorist.com), которая учит как решать алгоритмические задачи.

    ReplyDelete
  4. > Из книжек пока, к сожалению, ничего посоветовать не могу. Если найдете хорошую, дайте, пожалуйста, знать.

    Есть книга Меркова (на основе его лекций, они в сети доступны) - http://urss.ru/cgi-bin/db.pl?lang=Ru&blang=ru&page=Book&id=116135

    Есть лекции Воронцова - http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%BD%D0%BE%D0%B5_%D0%BE%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%28%D0%BA%D1%83%D1%80%D1%81_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D0%B9,_%D0%9A.%D0%92.%D0%92%D0%BE%D1%80%D0%BE%D0%BD%D1%86%D0%BE%D0%B2%29

    ReplyDelete
  5. Сергей, я попробовал прогнать пример, но при попытке загрузки пакета получил:
    package ‘knnflex’ is not available (for R version 2.15.2)
    Нашел этот пакет в архиве - knnflex_1.1.1.tar.gz, но как его скомпилировать и вставить в R - не знаю.
    Не могли бы Вы как-нибудь помочь старику?

    ReplyDelete
    Replies
    1. Действительно этот пакет удалили из репозитория по неизвестной мне причине.
      Из архива его можно установить такой командой:
      install.packages('[путь к файлу]/knnflex_1.1.tar.gz', repos=NULL, type="source")

      Delete
    2. Благодарю за точный и быстрый ответ.
      Кстати, таких удаленных пакетов далеко не один, еще, например, FSelector...

      Delete