Tuesday, May 3, 2011

Кластерный анализ с примерами на R

Доброго дня, уважаемый читатель! Перед вами очередной опус из серии о data mining. В прошлый раз я рассказал о методе ближайших соседей. Сегодня, как логическое продолжение, поговорим о кластерном анализе или кластеризации. С устоявшейся терминологией тут проблемы, т.к. большинство публикаций на английском и приходится придумывать русский эквивалент английским терминам. Потому и я иногда буду тоже скатываться на англицизмы.

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

А что если у нас есть просто данные и мы ничего не знаем об их структуре? Но зато, у каждого элемента данных есть набор характеристик (например, если речь идет о людях: возраст, пол, образование итп). Так вот, задача кластерного анализа состоит в том, чтобы разбить объекты на группы (кластеры) так чтобы объекты в каждой группе были некоторым образом похожи. Тем самым раскрывается внутренняя структура данных. При этом, нам не требуются тренировочные данные. Такой подход носит название обучения без учителя.

Предварительная работа

Рассмотрим, к примеру, набор данных:

ИмяВозрастГородДоход
Петя25Москва120000
Вася34Киров45000
Маша27Самара15000
Света36Нью-Йорк150000
Катя24Москва30000

Каким образом можно разбить эти данные на кластеры? Можно по зарплате: Петя и Света в один кластер, Вася и Катя во второй, а Маша в третий. Можно по возрасту: Петя, Маша и Катя в один, Вася и Света во второй. Можно еще разбить по месту жительства или полу. И всякий раз результат будет получаться разный. Какой результат лучше? Ответить можно только зная задачу, для чего именно проводится анализ. Данные сами по себе никак не определяют возможные группировки. Чтобы получить однозначный результат нам необходимо ввести понятие расстояния. Причем, мы можем использовать сразу несколько характеристик объектов для определения расстояния между ними, например зарплату, возраст и пол.

Существуют различные меры расстояний, но для нас интуитивно понятным является классическое Евклидово расстояние и, справедливости ради, замечу, что его в большинстве задач более чем достаточно. Важно лишь правильно нормализовать данные. Как в нашем примере: зарплаты измеряются в тысячах, а возраст в годах. Непосредственно сравнивать эти две величины нельзя. А вот если предварительно привести их к диапазону от 0 до 1 то они станут вполне сравнимыми.

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

Алгоритмы Кластерного Анализа

Известно множество алгоритмов кластерного анализа. Далеко не полная и не единственная возможная классификация представлена на рисунке ниже.



Итак, первым делом, все алгоритмы кластерного анализа делятся на две группы: иерархические и неиерархические. Первые строят не просто разбиение на классы, а иерархию разбиений. Результатом их работы, как правило, является дендрограмма, на основе которой, пользователь может сам выбрать желаемое разбиение. Неиерархические алгоритмы, напротив, в результате работы выдают некоторое конкретное разбиение и имеют ряд параметров, позволяющих настраивать алгоритм для имеющихся данных. Естественно, вторые работают быстрее чем первые.

Все методы кластеризации работают с данными в виде векторов в многомерном пространстве. Каждый вектор определяется значениями нескольких направлений, а направления и есть известные нам характеристики (пол, возраст, образование). Характеристики могут быть как количественные, так и качественные и искусство специалиста по data mining состоит в том, чтобы правильно отобрать и нормализовать эти характеристики, а потом выбрать подходящую меру расстояний. И только после этого в игру вступают алгоритмы кластеризации.

К числу наиболее популярных, неиерархических алгоритмов относится алгоритм k-средних. Он особенно популярен в силу простоты реализации и скорости работы. Главным его недостатком является сходимость к локальному минимуму и зависимость результата от начального распределения. Кроме того, требуется заранее знать предполагаемое число кластеров k.

Итак, сам алгоритм:
1) Выбрать k случайных центров в пространстве, содержащем исходные данные
2) Приписать каждый объект из множества исходных данных кластеру исходя из того, какой центр к нему ближе
3) Пересчитать центры кластеров используя полученное распределение объектов
4) Если алгоритм не сошелся, то перейти к п. 2. Типичные критерии схождения алгоритма это либо среднеквадратичная ошибка, либо отсутствие перемещений объектов из кластера в кластер.

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

Иерархическая кластеризация

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

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

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


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

Алгоритмы основанные на теории графов

На практике, в чистом виде, применяются редко, т.к. их вычислительная сложность не позволяет обрабатывать большие графы. Чаще используются в сочетании с другими алгоритмами, такими как k-средних. Классический пример, это алгоритм минимального покрывающего дерева. Идея состоит в том, чтобы представить весь набор данных в виде графа, вершины которого это наши элементы данных, а вес каждого ребра равен расстоянию между соответствующими элементами (помните, здесь тоже нет никаких чудес, сначала придется определить понятие расстояния). Тогда, мы можем построить минимальное покрывающее дерево на данном графе, а затем последовательно удалять ребра с наибольшим весом. Кластером считается множество элементов, соединенных "остатком" дерева. С каждым убранным ребром, количество кластеров увеличивается.

Статистические алгоритмы

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

Пример:


Для примера будет использоваться программная среда R. Что это такое, где взять и как настроить можно почитать тут.

Как всегда, пример у меня из области финансовых рынков. Допустим, у нас есть акции большого количества разных компаний. Одни из них растут, другие падают и мы накопили большую историю изменения их цен. Можем ли мы на основе этих данных объединить акции в группы? Логично было бы предположить, что акции из одного сектора рынка растут или падают вместе. И было бы логично если полученные группы это как-то отразили.

Для начала, я выкачал котировки примерно 20 российских компаний из разных областей, за два года с периодом 1 день. Для удобства, все они собраны в одном файле и доступны здесь. Попробуем проанализировать их средствами кластерного анализа. Т.к. цены разных акций отличаются очень сильно, и абсолютная величина цены нам совершенно не интересна, а интересно относительное изменение, приведем все цены к общему знаменателю: а именно, вместо самой цены будем считать логарифмическое изменение цены:
Xi = log(Ci) - log(Ci-1) ,где Ci - цена закрытия в i-ый день

x <- read.table('C:\\prj\\CNSVN\\stats\\stocks.csv', sep=',', header=TRUE) #читаем файл с ценами 
x <- log(x) #логарифмируем цены
x <- x[-1] #отбросим колонку с датой
x <- apply(x, 2, diff) #считаем разницу между последовательными элементами
x <- t(x) #транспонируем таблицу
kmeans(x, 5, 1000000) #будем разбивать на 5 кластеров, максимум 1000000 иттераций
Получаем результат:
12345
RASP AFLT, PMTL, PLZL, MMBM, MTSI, VZRZ GAZP, LKOH, VTBR, URKA, TRNFP, SIBN, SBER, ROSN, GMKN, SNGS OGK1, OGK2, OGK5 KMAZ, AVAZ
Сразу заметна тенденция к группировке в кластеры компаний из одного сектора: автопроизводители попали в пятый кластер, нефтедобывающие компании и крупные банки в третий, все генерирующие компании в четвертый. Если запустить этот алгоритм снова, то результат может получится другой, но тенденция, тем не менее, сохранится. Почему было решено разбивать именно на 5 кластеров, а не 6 или 4? К сожалению, решение вопроса о количестве кластеров не алгоритмизируется, в конечном счете это всегда должен решать пользователь. Но с использованием иерархической кластеризации это решение можно отложить на потом:
x <- read.table('C:\\prj\\CNSVN\\stats\\stocks.csv', sep=',', header=TRUE) #читаем файл с ценами 
x <- log(x) #логарифмируем цены
x <- x[-1] #отбросим колонку с датой
x <- apply(x, 2, diff) #считаем разницу между последовательными элементами
x <- t(x) #транспонируем таблицу

hc <- hclust(dist(x))

plot(hc)

Вот за что я люблю R! Нам понадобилось заменить всего одну строчку в прежнем примере и получилось следующая картинка:


На этой картинке уже гораздо лучше видны традиционные сектора нашей экономики. Видны и выколотые точки. Выколотые точки часто могут стать предметом особого исследования, ведь если компания ведет себя не как все в её отрасли, значит она что-то делает по-другому. Знание подобной информации может дать дополнительное преимущество в торговле.

10 comments:

  1. спасибо огромное за статьи. мега познавательный ресурс. вопрос, что вам больше нравится R or Matlab (не учитывая тот факт, что второй платный)

    ReplyDelete
  2. Пожалуйста!

    Все зависит от задачи. R заточен под статистическую обработку данных, поэтому в такого рода задачах я предпочитаю его (хотя, может быть я просто плохо знаю matlab :) )

    ReplyDelete
  3. спасибо еще раз )

    ReplyDelete
  4. наконец-то! абсолютно понятный пример кластерного анализа!)))
    спасибо!!))

    ReplyDelete
  5. Пытаюсь повторить ваш алгоритм. К сожалению, он выдает ошибку.
    При исполнении строчки
    x <- apply(x, 2, diff)

    Ошибка в r[i1] - r[-length(r):-(length(r) - lag + 1L)] :
    нечисловой аргумент для бинарного оператора
    В чем может быть причина?

    ReplyDelete
    Replies
    1. Подозреваю, что что-то не то с данными, посмотрите ваш файл stocks.csv
      Выведите на экран в R первые три строчки
      x[1:3,]
      Должно быть что-то типа:
      DATE AFLT GAZP KMAZ LKOH VTBR URKA TRNFP SIBN SBER ROSN
      1 20090428 32.32 143.00 25.39 1457.00 0.0307 77.74 12480.00 85.61 26.10 163.67
      2 20090429 32.51 149.00 30.80 1509.00 0.0317 79.35 13599.78 87.96 27.11 177.21
      3 20090430 33.96 147.82 30.23 1481.99 0.0315 79.40 13538.51 88.74 27.80 176.99

      Delete
  6. SergE, спасибо за блог вообще и за этот раздел, в частности!

    ReplyDelete
  7. А как обработать этот файл средствами SPSS?

    ReplyDelete
  8. Очень полезный материал! Спасибо!

    Скажите, почему вы логарифмируете цены, вместо того чтобы смотреть на процентное изменение? Чтобы учитывать эффект масштаба?

    ReplyDelete
  9. Извините пожалуйста,не могли бы Вы пояснить что означают цифры 0.2-1 Height?. Разбираю Ваш пример и не совсем понял суть вашей программы. Не могли бы Вы пояснить

    ReplyDelete