Иерархический алгоритм кластерного анализа и графическое представление его результатов. Метод k-средних.

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

Они бывают двух типов: агломеративные и дивизимные.

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

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

Результаты классификации представляются графически в виде дендрограммы Преимущества иерархических КП

1.Дают более полный и тонкий анализ структуры исследуемого множества наблюдений; 2.Возможность наглядной интерпретации результатов анализа

Недостатки иерархических КП

1.Громоздкость вычислительной реализации (на каждом шаге необходимо вычислять матрицу расстояний D 2.При n>100 дендрограмма теряет наглядность

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

Идея метода к-средних состоит в разбиении множества объектов на заранее известное число к-кластеров так, чтобы минимизировать функционал качества – сумму внутриклассовых дисперсий

- вектор средних (центр тяжести) для s_l группы

Пусть наблюдения требуется разбить на заданное число к однородных (в смысле некоторой метрики расстояний) классов.

Алгоритм состоит в последовательном уточнении эталонных точек ( - номер итерации, =0,1,2...) с соответствующим пересчетом приписываемых «весов»

Случайно выбирают р - точек (например, первых) исследуемой совокупности, которые принимаются за центры классов. Таким образом:

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

Пересчет центров тяжести к – кластеров и их весов на - м шаге после извлечения наблюдения происходит для i-го кластера по следующей формуле

При достаточно большом числе итераций или при достижении большой совокупности (n –велико), дальнейший пересчет центров тяжести практически не приводит к изменению, то есть имеет место сходимость к некоторому пределу.