Алгоритм иерархической кластеризации

Ниже представлен алгоритм восходящей иерархической кластеризации. В данном алгоритме на первом шаге рассчитывается матрица сходства объектов выборки, т.е. выполняется оценка по метрике d расстояний между всеми парами объектов. Эта же матрица используется для отображения сходства между кластерами. Затем выполняется 1-1 итераций объединений пар объектов кластеров. На каждой итерации данного алгоритма выполняется операция объединения для двух максимально похожих кластеров, которые еще не были объединены в больший кластер. Обнаруженные кластеры записываются в виде пар их идентификаторов в список D. В строках 3.1—3.2 выполняется пересчет метрик для кластера j и нового объединенного кластера < i, т >.

Различные алгоритмы иерархической кластеризации отличаются друг от друга алгоритмом расчета близости пар кластеров - Sim.

Вход:

  • • Множество объектов X = {xvx2, х3,Х}, мощности L
  • • Метрика d и алгоритм расчета близости кластеров Sim.

Выход:

• Дендрограмма D (последовательность объединений в кластеры).

Алгоритм:

1. Для всех i,j е L проинициализировать матрицу близости кластеров S[i] [/] =Sim (xifXj), а также индикатор активности кластера /

w=i-

  • 2. D = [ ].
  • 3. Для всех k g 1,2,L—1:
  • 3.1. Выбрать пару из 5 с максимальным значением 5ш,

так что И = т и / [ /] = / [ т) = 1.

  • 3.2. D + = < i, m >.
  • 3.3. Для всех У € 1,2,..., L:
  • 3.3.1. S [i] j] = Sim (i, m,j).
  • 3.3.2. S [/I [/] = (t, m,;).
  • 3.3.3. /[m] = 0.
  • 4. Вернуть D. [1] [2]
Схемы расчета расстояний между кластерами в восходящей иерархической кластеризации

Рис. 63- Схемы расчета расстояний между кластерами в восходящей иерархической кластеризации:

а — метол одиночной связи; 6 — метод полной связи; в — метод средней связи; г — метод центроидов

Примеры дендрограмм для схем расчета расстояний между кластерами

Рис. 6.4. Примеры дендрограмм для схем расчета расстояний между кластерами:

а — метод одиночной связи; б — метод полной связи; в — метод средней связи; г — метод центроидов

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

  • [1] Для завершения разговора о методе иерархической кластеризации приведем несколько примеров реализаций метода Sim: • кластеризация методом одиночной связи. Данный методпредполагает вычисление сходства двух кластеров на основе самыхблизких элементов двух кластеров; • кластеризация методом полной связи. В этом методе расстояние между кластерами считается но самым удаленным другот друга элементам; • кластеризация методом средней связи. Метод основанна вычислении среднего расстояния между всеми парами — объектами двух кластеров;
  • [2] кластеризация методом центроидов. Как видно из названия, расстояние между кластерами высчитывается как расстояниемежду их центроидами. Очевидно, что первые два метода являются менее ресурсоемкими,так как расстояния по этим методам считаются как min (5 [i] [т],S [т [/]) и max (S [i] [т], S [т] [г]) соответственно. Однако локальность метода оценки расстояния между кластерами можно считатьих недостатком, так как они не учитывают все содержание кластераи таким образом могут порождать цепочки связанных друг с другомобъектов или захватывать нежелательные объекты-выбросы. На рис. 6.3 показаны схемы расчета по данным методам,а на рис. 6.4 отображены процессы объединения объектов в кластеры для каждого из методов.
 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >