Иерархические кластер-процедуры

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

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

К недостаткам иерархических процедур следует отнести громоздкость их вычислительной реализации.

Наиболее употребительными расстояниями и мерами близости между классами объектов являются:

– расстояние, измеряемое по принципу “ближайшего соседа” – Этот метод известен также под названием метод одиночной связи.

Иерархические кластер-процедуры - student2.ru

– расстояние, измеряемого по принципу “дальнего соседа” – его называют метод полной связи

Иерархические кластер-процедуры - student2.ru

– расстояние, измеряемое по “центрам тяжести” групп –

Иерархические кластер-процедуры - student2.ru

– расстояние, измеряемое по принципу “средней связи”, определяется как среднее арифметическое всех попарных расстояний между представителями рассматриваемых групп

Иерархические кластер-процедуры - student2.ru

При этом расстояние между классами sl и s(m,q), являющиеся объединением двух других классов sm и sq, можно определить по формуле:

Иерархические кластер-процедуры - student2.ru

где, Иерархические кластер-процедуры - student2.ru

Иерархические кластер-процедуры - student2.ru коэффициенты определ. специфику структуры классификации

Например, при Иерархические кластер-процедуры - student2.ru приходим к расстоянию, построенному по принципу “ближайшего соседа”. Если Иерархические кластер-процедуры - student2.ru то расстояние измеряется по принципу дальнего соседа

Иерархические кластер-процедуры - student2.ru

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

Метод К-средних(метод динамических сгущений): Если кол-во наблюдений n достаточно велико(n>100), то трудно вычислять на каждой итерации расстояние между всеми объектами, а в k-средних на каждой итерации опр-ся лишь часть расстояний. Здесь предполагается, что заранее известно число кластеров Р. Алгоритм: Пусть требуется разбить n-наблюдений на заранее известное число однородных кластеров Р (p<=n). Алгоритм состоит в последовательном уточнении эталонных точек: Иерархические кластер-процедуры - student2.ru ), где n- номер итерации. Эталонные (.) хар-ют центр тяжести кластеров на соответствующей итерации. n=1,2…

Каждому кластеру на итерации n соответствуют веса Иерархические кластер-процедуры - student2.ru , равные числу наблюдений, попавших в данный кластер. Первоначально случайно выбирают Р-точек: Иерархические кластер-процедуры - student2.ru , и принимаем каждое наблюдение за центр класса 0-ой итерации: Иерархические кластер-процедуры - student2.ru . На 1-ом шаге извлекается наблюдение Иерархические кластер-процедуры - student2.ru и выясняется, какому из центров Иерархические кластер-процедуры - student2.ru оно оказалось ближе всего. Именно этот самый близкий Иерархические кластер-процедуры - student2.ru центр заменяется центром тяжести кластера, состоящего из 2-х объектов, включая Иерархические кластер-процедуры - student2.ru , с увеличением на 1 веса этого кластера. Пересчет центра тяжести Р-классов и весов на n-и шаге после извлечения Иерархические кластер-процедуры - student2.ru наблюдение: Иерархические кластер-процедуры - student2.ru ,

(1)-если Иерархические кластер-процедуры - student2.ru ,(2)- в противном случае.

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

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

содержание

Наши рекомендации