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

3.4. иерархические кластер-процедуры: Эконометрика, В.С. Мхитарян, 2008 читать онлайн, скачать pdf, djvu, fb2 скачать на телефон Рекомендовано Учебно-методическим объединением по образованию в области статистики в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальности 061700 «Статистика» и другим экономическим специальностям.

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.

Эконометрика

Эконометрика

Обсуждение Эконометрика

Комментарии, рецензии и отзывы

3.4. иерархические кластер-процедуры: Эконометрика, В.С. Мхитарян, 2008 читать онлайн, скачать pdf, djvu, fb2 скачать на телефон Рекомендовано Учебно-методическим объединением по образованию в области статистики в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальности 061700 «Статистика» и другим экономическим специальностям.