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

Двувходовое объединение

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

Так, возвращаясь к предыдущему  примеру, можно предположить, что  медицинскому исследователю требуется  выделить кластеры пациентов, сходных  по отношению к определенным кластерам  характеристик физического состояния. Трудность с интерпретацией полученных результатов возникает вследствие того, что сходства между различными кластерами могут происходить из (или быть причиной) некоторого различия подмножеств переменных. Поэтому получающиеся кластеры являются по своей природе неоднородными. Возможно это кажется вначале немного туманным; в самом деле, в сравнении с другими описанными методами кластерного анализа (см. Объединение (древовидная кластеризация) и Метод K средних), двувходовое объединение является, вероятно, наименее часто используемым методом. Однако некоторые исследователи полагают, что он предлагает мощное средство разведочного анализа данных (за более подробной информацией вы можете обратиться к описанию этого метода у Хартигана (Hartigan, 1975)).

В начало

 
 

 

Метод K средних

• Пример
• Вычисления
• Интерпретация результатов

Общая логика

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

Пример

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

Вычисления

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

Интерпретация результатов

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

 

http://www.zadachi.org.ru/?n=9723

 

В задачах социально-экономического прогнозирования весьма перспективно сочетание кластерного анализа  с другими количественными методами (например, с регрессионным анализом). Как и любой другой метод, кластерный анализ имеет определенные недостатки и ограничения: В частности, состав и количество кластеров зависит  от выбираемых критериев разбиения. При сведении исходного массива  данных к более компактному виду могут возникать определенные искажения, а также могут теряться индивидуальные черты отдельных объектов за счет замены их характеристиками обобщенных значений параметров кластера. При  проведении классификации объектов игнорируется очень часто возможность  отсутствия в рассматриваемой совокупности каких-либо значений кластеров. В кластерном анализе считается, что: а) выбранные  характеристики допускают в принципе желательное разбиение на кластеры; б) единицы измерения (масштаб) выбраны  правильно. Выбор масштаба играет большую  роль. Как правило, данные нормализуют  вычитанием среднего и делением на стандартное отклоненение, так что дисперсия оказывается равной единице. 2. Задача кластерного анализа. Задача кластерного анализа заключается в том, чтобы на основании данных, содержащихся во множестве Х, разбить множество объектов G на m (m – целое) кластеров (подмножеств) Q1, Q2, , Qm, так, чтобы каждый объект Gj принадлежал одному и только одному подмножеству разбиения и чтобы объекты, принадлежащие одному и тому же кластеру, были сходными, в то время, как объекты, принадлежащие разным кластерам были разнородными. Например, пусть G включает стран, любая из которых характеризуется ВНП на душу населения (F1), числом М автомашин на 1 тысячу человек (F2), душевым потреблением электроэнергии (F3), душевым потреблением стали (F4) и т.д. Тогда Х1 (вектор измерений) представляет собой набор указанных характеристик для первой страны, Х2 - для второй, Х3 для третьей, и т.д. Задача заключается в том, чтобы разбить страны по уровню развития. Решением задачи кластерного анализа являются разбиения, удовлетворяющие некоторому критерию оптимальности. Этот критерий может представлять собой некоторый функционал, выражающий уровни желательности различных разбиений и группировок, который называют целевой функцией. Например, в качестве целевой функции может быть взята внутригрупповая сумма квадратов отклонения: где xj - представляет собой измерения j-го объекта. Для решения задачи кластерного анализа необходимо определить понятие сходства и разнородности. Понятно то, что объекты (-ый и j-ый попадали бы в один кластер, когда расстояние (отдаленность) между точками Х( и Хj было бы достаточно маленьким и попадали бы в разные кластеры, когда это расстояние было бы достаточно большим. Таким образом, попадание в один или разные кластеры объектов определяется понятием расстояния между Х( и Хj из Ер, где Ер - р- мерное евклидово пространство. Неотрицательная функция d(Х( , Хj) называется функцией расстояния (метрикой), если: а) d(Хi , Хj) ( 0, для всех Х( и Хj из Ер б) d(Хi, Хj) = 0, тогда и только тогда, когда Х( = Хj в) d(Хi, Хj) = d(Хj, Х() г) d(Хi, Хj) ( d(Хi, Хk) d(Хk, Хj), где Хj; Хi и Хk - любые три вектора из Ер. 
 
Соответственно они могут быть представлены в качестве точек в 31-мерном пространстве. Такое пространство обычно называется пространством свойств изучаемых объектов. Сравнение расстояния между этими точками будет отражать степень близости рассматриваемых стран, их сходство друг с другом. Социально-экономический смысл подобного понимания сходства означает, что страны считаются тем более похожими, чем меньше различия между одноименными показателями, с помощью которых они описываются. Первый шаг подобного анализа заключается в выявлении пары народных хозяйств, учтенных в матрице сходства, расстояние между которыми является наименьшим. Это, очевидно, будут наиболее сходные, похожие экономики. В последующем рассмотрении обе эти страны считаются единой группой, единым кластером. Соответственно исходная матрица преобразуется так, что ее элементами становятся расстояния между всеми возможными парами уже не 65, а 64 объектами – 63 экономики и вновь преобразованного кластера – условного объединения двух наиболее похожих стран. Из исходной матрицы сходства выбрасываются строки и столбцы, соответствующие расстояниям от пары стран, вошедших в объедение, до всех остальных, но зато добавляются строка и столбец, содержащие расстояние между кластером, полученным при объединении и прочими странами. Расстояние между вновь полученным кластером и странами полагается равным среднему из расстояний между последними и двумя странами, которые составляют новый кластер. Иными словами, объединенная группа стран рассматривается как целое с характеристиками, примерно равными средним из характеристик входящих в него стран. Второй шаг анализа заключается в рассмотрении преобразованной таким путем матрицы с 64 строками и столбцами. Снова выявляется пара экономик, расстояние между которыми имеет наименьшее значение, и они, так же как в первом случае, сводятся воедино. При этом наименьшее расстояние может оказаться как между парой стран, так и между какой-либо страной и объединением стран, полученным на предыдущем этапе. Дальнейшие процедуры аналогичны описанным выше: на каждом этапе матрица преобразуется так, что из нее исключаются два столбца и две строки, содержащие расстояние до объектов (пар стран или объединений – кластеров), сведенных воедино на предыдущей стадии; исключенные строки и столбцы заменяются столбцом и строкой, содержащими расстояния от новых объединений до остальных объектов; далее в измененной матрице выявляется пара наиболее близких объектов. Анализ продолжается до полного исчерпания матрицы (т. е. до тех пор, пока все страны не окажутся сведенными в одно целое). Обобщенные результаты анализа матрицы можно представить в виде дерева сходства (дендограммы), подобного описанному выше, с той лишь разницей, что дерево сходства, отражающее относительную близость всех рассматриваемых нами 65 стран, много сложнее схемы, в которой фигурирует только пять народных хозяйств. Это дерево в соответствии с числом сопоставляемых объектов включает 65 уровней. Первый (нижний) уровень содержит точки, соответствующие каждых стране в отдельности. Соединение двух этих точек на втором уровне показывает пару стран, наиболее близких по общему типу народных хозяйств. На третьем уровне отмечается следующее по сходству парное соотношение стран (как уже упоминалось, в таком соотношении может находиться либо новая пара стран, либо новая страна и уже выявленная пара сходных стран). 
 
Наличие резкого скачка в значении E можно интерпретировать как характеристику числа кластеров, объективно существующих в исследуемой совокупности. Итак, второй способ определения наилучшего числа кластеров сводится к выявлению скачков, определяемых фазовым переходом от сильно связанного к слабосвязанному состоянию объектов. 1.6 Дендограммы. Наиболее известный метод представления матрицы расстояний или сходства основан на идее дендограммы или диаграммы дерева. Дендограмму можно определить как графическое изображение результатов процесса последовательной кластеризации, которая осуществляется в терминах матрицы расстояний. С помощью дендограммы можно графически или геометрически изобразить процедуру кластеризации при условии, что эта процедура оперирует только с элементами матрицы расстояний или сходства. Существует много способов построения дендограмм. В дендограмме объекты располагаются вертикально слева, результаты кластеризации – справа. Значения расстояний или сходства, отвечающие строению новых кластеров, изображаются по горизонтальной прямой поверх дендограмм. Рис1 На рисунке 1 показан один из примеров дендограммы. Рис 1 соответствует случаю шести объектов ( =6) и k характеристик (признаков). Объекты А и С наиболее близки и поэтому объединяются в один кластер на уровне близости, равном 0,9. Объекты D и Е объединяются при уровне 0,8. Теперь имеем 4 кластера: (А, С), (F), (D, E), (B). Далее образуются кластеры (А, С, F) и (E, D, B), соответствующие уровню близости, равному 0,7 и 0,6. Окончательно все объекты группируются в один кластер при уровне 0,5. Вид дендограммы зависит от выбора меры сходства или расстояния между объектом и кластером и метода кластеризации. Наиболее важным моментом является выбор меры сходства или меры расстояния между объектом и кластером. Число алгоритмов кластерного анализа слишком велико. Все их можно подразделить на иерархические и неиерархические. Иерархические алгоритмы связаны с построением дендограмм и делятся на: а) агломеративные, характеризуемые последовательным объединением исходных элементов и соответствующим уменьшением числа кластеров; б) дивизимные (делимые), в которых число кластеров возрастает, начиная с одного, в результате чего образуется последовательность расщепляющих групп. Алгоритмы кластерного анализа имеют сегодня хорошую программную реализацию, которая позволяет решить задачи самой большой размерности. 1.7 Данные Кластерный анализ можно применять к интервальным данным, частотам, бинарными данным. Важно, чтобы переменные изменялись в сравнимых шкалах. Неоднородность единиц измерения и вытекающая отсюда невозможность обоснованного выражения значений различных показателей в одном масштабе приводит к тому, что величина расстояний между точками, отражающими положение объектов в пространстве их свойств, оказывается зависящей от произвольно избираемого масштаба. Чтобы устранить неоднородность измерения исходных данных, все их значения предварительно нормируются, т.е. выражаются через отношение этих значений к некоторой величине, отражающей определенные свойства данного показателя.

 

 

 

http://www.smartcat.ru/Referat/ntyeeramnz/moreA.shtml

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

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

Современный экономический  словарь 
Райзберг Б.А., Лозовский Л.Ш., Стародубцева Е.Б

 

 

http://www.algorithmist.ru/2011/05/clustering-with-example-in-r.html

Кластерный анализ с примерами на 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 день. Для удобства, все они собраны в одном файле и доступны здесь. Попробуем проанализировать их средствами кластерного анализа. Т.к. цены разных акций отличаются очень сильно, и абсолютная величина цены нам совершенно не интересна, а интересно относительное изменение, приведем все цены к общему знаменателю: а именно, вместо самой цены будем считать логарифмическое изменение цены: 
X_i = log(C_i) - log(C_i-1) ,где C_i - цена закрытия в i-ый день