Имя материала: Эконометрика

Автор: В.С. Мхитарян

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

 

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

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

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

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

Большинство программ, реализующих алгоритм иерархической классификации, предусматривает графическое представление результатов классификации в виде дендро-граммы.

 

3.5. Тестовый пример

Провести классификацию п=6 объектов, каждый из которых характеризуется двумя признаками.

Расположение этих точек на плоскости показано на рис. 3.1.

 

А Х І2

1513' 1Г 9

 

 

3

 

1

 

 

-2

 

 

4 5

• •

 

•6

Х

н—I—I—I—I—I—I—I—I—I—I—I—>

1   23456789  10 11 12

Рис. 3.1

Воспользуемся агломеративным иерархическим алгоритмом классификации. В качестве расстояния между объектами примем обычное евклидово расстояние. Тогда согласно (3.1) расстояние между объектами 1 и 2 равно

р12 _V(5-6)2 +(10-12)2 _ 2,24, а между объектами 1 и 3

р

13

V(5 - 5)2 +(10 -13)2 _ 3,

 

очевидно, что

 

Аналогично находим расстояния между всеми шестью объектами и строим матрицу расстояний

 

 

R1 _MXi, xj )} =

( 0

2,24 3

5,10 6,08 v 5,83

 

2,24

3

5,10

6,08

5,83 Л

0

1,41

5

5,83

6,40

1,41

0

6,40

7,21

7,81

5

6,40

0

1

2

5,83

7,21

1

0

2,24

6,40

7,81

2

2,24

0 j

 

Из матрицы расстояний следует, что объекты 4 и 5 наиболее близки d4;5=1,00 и поэтому объединяются в один кластер.

После объединения имеем пять кластеров

 

Номер кластера

1

2

3

4

5

Состав кластера

(1)

(2)

(3)

(4,5)

(6)

 

Расстояние между кластерами будем находить по принципу «ближайшего соседа», воспользовавшись формулой пересчета (3.8). Так, расстояние между объектом s1 и кластером S(4;5) равно

р1,(4,5)=         S (4,5))= 2 р14 + 2 рц " 2 |р14 - рц | = -2 (5Д0 + 6,°8)-

 

(5,10 - 6,08 )= 5,10 .

Мы видим, что расстояние р 1; (4;5) равно расстоянию от объекта 1 до ближайшего к нему объекта, входящего в кластер S(4;5), т.е. р1 (45) = р14 = 5Д0. Тогда матрица расстояний равна

р(4,5),(

 

2,3)

1

^ р(4,5),2

1

+ 2 р(4,5),3

1

2 Р(4,5),2

 

(4,5 ),3

5 6,40 1,40

— + —            -                  = 5 .

2   2 2

Проведя аналогичные расчеты, получим (0        2,24    5,10    5,83 Ї

А =

2,24    0        5 6,40

5,10   5      0 2

v5,83    6,40    2 0

 

Объединенные кластеры s(4,5) и s(6), расстояние между которыми согласно матрице R3 наименьшее: р (4;5);6=2.

В результате этого получим три кластера

sb       s(2,3)    и S(4,5,6>

Матрица расстояний будет иметь вид

R =

 

^0       2,24   5,10^ 2,24   0 5 [5,10   5 0

Объединим теперь кластеры s1 и s2,3, расстояние между которыми равно p1 (2 3) = 2,24 . В результате получим два кластера: s(1;2;3) и s(4;5;6), расстояние между которыми, найденное по принципу «ближайшего соседа», равно

Р(1,2,3); (4,5,6) = 5.

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

 

А р

5,001

 

2,24 2,00'-

1,41 ..

1,00"

 

3

 

Рис. 3.2. Дендрограмма

 

Слева на рисунке приводится расстояние между объединяемыми на данном этапе кластерами (объектами).

В задаче предпочтение следует отдать предпоследнему этапу классификации, когда все объекты объединены в два кластера

s(1,2,3)            и s(4,5,6>

что наглядно видно на рис. 3.1 и 3.2.

Страница: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 |