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

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

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

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

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

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

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

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

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

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

где,

коэффициенты определ. специфику структуры классификации

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

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

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

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

(1)-если ,(2)- в противном случае.

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

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

содержание