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

 

1) 0≤ <1 для Х_i ¹ Х_j

2) = 1

3) =

 

Пары значений мер сходства можно объединить в матрицу сходства:

 

Величину S_ij называют коэффициентом сходства.

 

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

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

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

1. Итеративный метод. Предполагается, что каждый рассматриваемый объект относится к одному из k классов. Некоторые авторы (например, А. И. Орлов) считают, что данная группа вовсе не относится к кластеризации и противопоставляют её под названием «дискриминация», то есть выбор отнесения объектов к одной из известных групп (обучающих выборок).

• K-средних (K-means)

• K-medians
• EM-алгоритм
• Алгоритмы семейства FOREL
• Дискриминантный анализ

 

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

• Метод нечеткой кластеризации C-средних (C-means)

• Нейронная сеть Кохонена
• Генетический алгоритм

 

3. Логический метод. Построение дендрограммы осуществляется с помощью дерева решений.
4. Теоретико-графовый метод.

• Графовые алгоритмы кластеризации

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

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

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

6. Другие методы. Не вошедшие в предыдущие группы.

• Статистические алгоритмы кластеризации
• Ансамбль кластеризаторов
• Алгоритмы семейства КRAB
• Алгоритм, основанный на методе просеивания
• DBSCAN и др.

Подходы 4 и 5 иногда объединяют под названием структурного или  геометрического подхода, обладающего  большей формализованностью понятия  близости. Несмотря на значительные различия между перечисленными методами все  они опираются на исходную «гипотезу  компактности»: в пространстве объектов все близкие объекты должны относиться к одному кластеру, а все различные  объекты соответственно должны находиться в различных кластерах.

На практике чаще всего  применяют два подхода: вероятностный и иерархический.

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

 

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

Как было сказано выше иерархический  подход делится на агломеративные и дивизимные методы.

Повторим, что сущность агломеративной кластеризации (agglomerative clustering) заключается в том, что на первом шаге каждый объект рассматривается как отдельный кластер. Процесс объединения кластеров происходит последовательно: на основании матрицы расстояний или матрицы сходства объединяются наиболее близкие объекты. Если матрица сходства первоначально имеет размерность n×n, то полностью процесс кластеризации завершается за n-1 шагов, в итоге все объекты будут объединены в один кластер. Разделяющая, или дивизимная, кластеризация (divisive clustering) являются логической противоположностью агломеративным методам и начинается со всех объектов, сгруппированных в единственном кластере. Кластеры делят (расщепляют) до тех пор, пока каждый объект не окажется в отдельном кластере (см. рис. 1).

В общем виде алгоритм иерархического кластерного анализа можно представить  в виде последовательности процедур:

1. Значения исходных переменных нормируются.
2. Рассчитывается матрица расстояний или матрица мер близости.
3. Находится пара самых близких кластеров. По выбранному алгоритму объединяются эти два кластера. Новому кластеру присваивается меньший из номеров объединяемых кластеров.
4. Пункты 2, 3 и 4 повторяются до тех пор, пока все объекты не будут объединены в один кластер или до достижения заданного "порога" близости.

При использовании кластерного анализа оператор может априорно задать число кластеров, но чаще всего это число определяется в процессе агломерации (разделения) множества объектов.

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

Рис.1 Принцип работы агломеративных и дивизимных методов.

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

Преимуществом данных методов кластеризации является их наглядность.

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

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

Существует много способов построения дендрограмм. В дендрограмме объекты могут располагаться  вертикально или горизонтально. Ниже приведен пример вертикальной дендрограммы (см. рис. 2).

 

Рис. 2 Пример дендрограммы.

Буквы N, M, C и т.д. соответствуют номерам объектов или наблюдений исходной выборки. Видно, что на первом шаге каждое наблюдение представляет один кластер (вертикальная линия), на втором шаге наблюдаем объединение таких наблюдений: N и M; C, D и E; G и K; B и F. На втором шаге продолжается объединение в кластеры: наблюдения N, M, C, D, E и G, K, L. Данный процесс продолжается до тех пор, пока все наблюдения не объединятся в один кластер.

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

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

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

 

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

 

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

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

● Невзвешенный центроидный метод. В этом методе расстояние между двумя кластерами определяется как расстояние между их центрами тяжести.

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

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

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

 

2.2. Итеративные методы кластерного анализа. Метод k – средних.

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

В отличие от иерархических  методов, которые требуют вычисления и хранения матрицы сходств между объектами размерностью n×n, итеративные методы работают непосредственно с первичными данными.

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

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