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

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

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

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

 

2. Методы кластерного анализа

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

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

Сегодня существует достаточно много  методов кластерного анализа. Все методы можно разделить на две группы - иерархические и неиерархические.

Каждая из групп включает множество подходов и алгоритмов.

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

Рассмотрим иерархические и  неиерархические методы подробно.

 

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

Суть иерархической  кластеризации состоит в последовательном объединении меньших кластеров  в большие или разделении больших  кластеров на меньшие.

Иерархические методы кластерного  анализа используются при небольших  объемах наборов данных. Преимуществом иерархических методов кластеризации является их наглядность.

Иерархические алгоритмы связаны  с построением дендрограмм (от греческого dendron - «дерево»), которые являются результатом иерархического кластерного анализа. Дендрограмма описывает близость отдельных точек и кластеров друг к другу, представляет в графическом виде последовательность объединения (разделения) кластеров.

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

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

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

На данном рисунке показан один из примеров  дендограммы. Этот рисунок соответствует случаю шести объектов (n=6) и k характеристик (признаков). Объекты А и С наиболее близки и поэтому объединяются в один кластер на уровне близости, равном 0,9. Объекты D и Е объединяются  при уровне 0,8. Теперь имеем 4 кластера:(А, С), (F), (D, E), (B).

Далее образуются кластеры (А, С, F) и (E, D, B), соответствующие уровню близости, равному 0,7 и 0,6. Окончательно все объекты группируются в один кластер при уровне 0,5.

Вид дендограммы зависит  от выбора меры сходства  или расстояния между объектом  и кластером  и метода кластеризации. Наиболее важным моментом является выбор меры сходства или меры расстояния между объектом и кластером.

В настоящее время  различают следующие иерархические методы кластерного анализа:

1. Иерархические агломеративные методы (Agglomerative Nesting, AGNES)

Эта группа методов характеризуется последовательным объединением исходных элементов и соответствующим уменьшением числа кластеров.

В начале работы алгоритма  все объекты являются отдельными кластерами. На первом шаге наиболее похожие  объекты объединяются в кластер. На последующих шагах объединение продолжается до тех пор, пока все объекты не будут составлять один кластер.

2. Иерархические дивизимные (делимые) методы (DIvisive ANAlysis, DIANA)

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

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

Число алгоритмов кластерного анализа велико. В таблице 2 рассмотрены некоторые из них.

Таблица 2- Методы кластерного  анализа

Метод	Суть метода
1	2
Меры сходства	Для вычисления расстояния между объектами используются различные  меры сходства (меры подобия), называемые также метриками или функциями  расстояний. В начале лекции мы рассмотрели евклидово расстояние, это наиболее популярная мера сходства.
Квадрат евклидова расстояния.	Для придания больших  весов более отдаленным друг от друга  объектам можем воспользоваться  квадратом евклидова расстояния путем возведения в квадрат стандартного евклидова расстояния.
Манхэттенское расстояние (расстояние городских кварталов), также называемое «хэмминговым» или «сити-блок» расстоянием.	Это расстояние рассчитывается как среднее разностей по координатам. В большинстве случаев эта мера расстояния приводит к результатам, подобным расчетам расстояния евклида. Однако, для этой меры влияние отдельных выбросов меньше, чем при использовании евклидова расстояния, поскольку здесь координаты не возводятся в квадрат.
Расстояние Чебышева.	Это расстояние стоит  использовать, когда необходимо определить два объекта как "различные", если они отличаются по какому-то одному измерению.
Процент несогласия.	Это расстояние вычисляется, если данные являются категориальными.
Методы объединения или связи	Когда каждый объект представляет собой отдельный кластер, расстояния между этими объектами определяются выбранной мерой. Возникает следующий  вопрос - как определить расстояния между кластерами? Существуют различные  правила, называемые методами объединения или связи для двух кластеров.
Метод ближнего соседа или  одиночная связь.	Здесь расстояние между  двумя кластерами определяется расстоянием  между двумя наиболее близкими объектами (ближайшими соседями) в различных  кластерах. Этот метод позволяет выделять кластеры сколь угодно сложной формы при условии, что различные части таких кластеров соединены цепочками близких друг к другу элементов. В результате работы этого метода кластеры представляются длинными «цепочками» или «волокнистыми» кластерами, "сцепленными вместе" только отдельными элементами, которые случайно оказались ближе остальных друг к другу.

 

Продолжение таблицы 2.

1	2
Метод наиболее удаленных  соседей или полная связь.	Здесь расстояния между  кластерами определяются наибольшим расстоянием между любыми двумя объектами в различных кластерах (т.е. «наиболее удаленными соседями»). Метод хорошо использовать, когда объекты действительно происходят из различных «рощ». Если же кластеры имеют в некотором роде удлиненную форму или их естественный тип является «цепочечным», то этот метод не следует использовать.
Метод Варда (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)).	Этот метод похож  на предыдущий, разница состоит в  том, что для учета разницы между размерами кластеров (числе объектов в них), используются веса. Этот метод предпочтительно использовать в случаях, если имеются предположения относительно существенных отличий в размерах кластеров.

Программная реализация алгоритмов кластерного анализа широко представлена в различных инструментах Data Mining, которые позволяют решать задачи достаточно большой размерности. Например, агломеративные методы реализованы в пакете SPSS, дивизимные методы - в пакете Statgraf.

Для более лучшего  понимания методов иерархической кластеризации рассмотрим алгоритм последовательной кластеризации схема которой может быть описана следующим образом. Рассмотрим Ι = (Ι1, Ι2, … Ιn) как множество кластеров {Ι1}, {Ι2},…{Ιn}. Выберем два из них, например, Ι i и Ι j, которые в некотором смысле более близки друг к другу и объединим их в один кластер. Новое множество кластеров, состоящее уже из n-1 кластеров, будет:

{Ι1}, {Ι2}…, {Ι i , Ι j}, …, {Ιn}.

Повторяя процесс, получим  последовательные множества кластеров, состоящие из (n-2), (n-3), (n–4) и т.д. кластеров. В конце процедуры можно получить кластер, состоящий из n объектов и совпадающий с первоначальным множеством Ι = (Ι1, Ι2, … Ιn).

В качестве меры расстояния возьмем квадрат евклидовой метрики di j2. и вычислим матрицу D = {di j2}, где di j2  - квадрат расстояния между Ι i и Ι j³:

	Ι1	Ι2	Ι3	….	Ιn
Ι1	0	d122	d132	….	d1n2
Ι2		0	d232	….	d2n2
Ι3			0	….	d3n2
….				….	….
Ιn					0

Пусть расстояние между  Ι i и Ι j будет минимальным:

di j2 = min {di j2, i ¹ j}. Образуем с помощью Ι i и Ι j новый кластер

{Ι i , Ι j}. Построим новую ((n-1), (n-1)) матрицу расстояния

 

	{Ι i , Ι j}	Ι1	Ι2	Ι3	….	Ιn
{Ι i ; Ι j}	0	di j21	di j22	di j23	….	di j2n
Ι1		0	d122	d13	….	d12n
Ι2			0	di j21	….	d2n
Ι3				0	….	d3n
Ιn						0