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

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

В алгомеративныхпроцедурах начальным является разбиение, состоящий из n одноэлементных классов, а конечным – из одного класса; в дивизимныхнаоборот

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

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

Приведем пример алгомеративного иерарического алгоритма. На первом шаге каждое наблюдение X_i (i=1,2,…,n) рассматривается как отдельный кластер. В дальнейшем на каждом шаге работы алгоритма происходит объединение двух самых близких кластеров, и, с учетом принятого расстояния, по формуле пересчитывается матрица расстояний, размерность которой, очевидно, снижается на единицу. Работа алгоритма заканчивается, когда все наблюдения объединены в один класс. Большинство программ, реализующих алгоритм иерархической классификации, предусматривают графическое представление классификации в виде дендрограммы.