Webbc.ru

Веб и кризис
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Кластерный анализ евклидово расстояние

Методы кластерного анализа. Иерархические методы

Меры сходства

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

Квадрат евклидова расстояния .

Для придания больших весов более отдаленным друг от друга объектам можем воспользоваться квадратом евклидова расстояния путем возведения в квадрат стандартного евклидова расстояния .

Манхэттенское расстояние ( расстояние городских кварталов), также называемое «хэмминговым» или «сити-блок» расстоянием.

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

Расстояние Чебышева. Это расстояние стоит использовать, когда необходимо определить два объекта как «различные», если они отличаются по какому-то одному измерению.

Процент несогласия. Это расстояние вычисляется, если данные являются категориальными.

Методы объединения или связи

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

Метод ближнего соседа или одиночная связь. Здесь расстояние между двумя кластерами определяется расстоянием между двумя наиболее близкими объектами (ближайшими соседями) в различных кластерах. Этот метод позволяет выделять кластеры сколь угодно сложной формы при условии, что различные части таких кластеров соединены цепочками близких друг к другу элементов. В результате работы этого метода кластеры представляются длинными «цепочками» или «волокнистыми» кластерами, «сцепленными вместе» только отдельными элементами, которые случайно оказались ближе остальных друг к другу.

Метод наиболее удаленных соседей или полная связь . Здесь расстояния между кластерами определяются наибольшим расстоянием между любыми двумя объектами в различных кластерах (т.е. «наиболее удаленными соседями»). Метод хорошо использовать, когда объекты действительно происходят из различных «рощ». Если же кластеры имеют в некотором роде удлиненную форму или их естественный тип является «цепочечным», то этот метод не следует использовать.

Метод Варда (Ward’s method ). В качестве расстояния между кластерами берется прирост суммы квадратов расстояний объектов до центров кластеров , получаемый в результате их объединения (Ward, 1963). В отличие от других методов кластерного анализа для оценки расстояний между кластерами, здесь используются методы дисперсионного анализа . На каждом шаге алгоритма объединяются такие два кластера, которые приводят к минимальному увеличению целевой функции, т.е. внутригрупповой суммы квадратов. Этот метод направлен на объединение близко расположенных кластеров и «стремится» создавать кластеры малого размера.

Метод невзвешенного попарного среднего (метод невзвешенного попарного арифметического среднего — unweighted pair-group method using arithmetic averages, UPGMA (Sneath, Sokal, 1973)).

В качестве расстояния между двумя кластерами берется среднее расстояние между всеми парами объектов в них. Этот метод следует использовать, если объекты действительно происходят из различных «рощ», в случаях присутствия кластеров «цепочного» типа, при предположении неравных размеров кластеров.

Метод взвешенного попарного среднего (метод взвешенного попарного арифметического среднего — weighted pair-group method using arithmetic averages, WPGM A (Sneath, Sokal, 1973)). Этот метод похож на метод невзвешенного попарного среднего, разница состоит лишь в том, что здесь в качестве весового коэффициента используется размер кластера (число объектов, содержащихся в кластере).

Читать еще:  Типы факторного анализа в экономическом анализе

Этот метод рекомендуется использовать именно при наличии предположения о кластерах разных размеров.

Невзвешенный центроидный метод (метод невзвешенного попарного центроидного усреднения — unweighted pair-group method using the centroid average (Sneath and Sokal, 1973)).

В качестве расстояния между двумя кластерами в этом методе берется расстояние между их центрами тяжести.

Взвешенный центроидный метод (метод взвешенного попарного центроидного усреднения — weighted pair-group method using the centroid average , WPGMC (Sneath, Sokal 1973)). Этот метод похож на предыдущий, разница состоит в том, что для учета разницы между размерами кластеров (числе объектов в них), используются веса. Этот метод предпочтительно использовать в случаях, если имеются предположения относительно существенных отличий в размерах кластеров .

О программировании, алгоритмах и не только

Жена посылает мужа-программиста в магазин и говорит, купи батон колбасы, а если будут яйца — возьми десяток. Он в магазине: У Вас яйца есть? -Есть -Тогда дайте десять батонов колбасы..

Pages

Tuesday, May 3, 2011

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

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

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

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

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

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

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

Читать еще:  Анализ работы с поставщиками

Существуют различные меры расстояний, но для нас интуитивно понятным является классическое Евклидово расстояние и, справедливости ради, замечу, что его в большинстве задач более чем достаточно. Важно лишь правильно нормализовать данные. Как в нашем примере: зарплаты измеряются в тысячах, а возраст в годах. Непосредственно сравнивать эти две величины нельзя. А вот если предварительно привести их к диапазону от 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-ый день

Ссылка на основную публикацию
Adblock
detector