3.4. иерархические кластер-процедуры
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.
Обсуждение Эконометрика
Комментарии, рецензии и отзывы