15297 P3200027

wania w pamięci komputera n(n — l)/2 liczb. Dla 100 obiektów wynosi to 4950. dla 200 obiektów już 17400. dlatego metody hierarchiczne można stosować dla niezbyt dużej liczby obiektów.

Algorytm grupowania jest następujący:

1.    Wyznaczamy macierz odległości pomiędzy jednoelemenlowymi skupieniami, jest lo macierz D. Jej wymiar wynosi k = n.

2.    Znajdujemy dwa najbliższe skupienia ij. takie liczby p-q (1 < p,q < k) oraz p>q, dla

których d _m — min^ d_u . Połączone skupienia S_f i S_ę utworzą nowe skupienie i>j

S_pkjS_q. Nadajemy mu numer / = q, wykreślając wiersz p i kolumnę p z macierzy odległości. Następnie zmniejszamy o 1 numery skupień większe niż p. Liczba skupień k zmniejsza się o 1 (<::=£-1).

1. Wyznaczamy nowe elementy kolumny t będące odległościami d_tr nowo powstałego

skupienia od pozostałych skupień.

4. Jeżeli fc>l. to wracamy do punktu 2 i powtarzamy czynności.

Poszczególne metody grupowania różnią się jedynie sposobem wyznaczania odległości między skupieniami (pkt. 3 algorytmu). Znane są różne metody definiowania tych odległości.

Do najczęściej wykorzystywanych metod aglomeracyjnych należą:

1.    Najbliższego sąsiedztwa (SINGLE, Single linkage, Nearest neighbor).

2.    Najdalszego sąsiedztwa (COMPLETE, Complete linkage, Furthest neighbor).

3.    Mediany (MEDIAN, Median elustering, WPGMC).

4.    Środka ciężkości (CENTROID, Centroid elustering, UPGMC).

5.    Średniej odległości wewnątrz skupień (WAYERAGE. Average linkage within groups).

6.    Średniej odległości między skupieniami 'RAVERAGE, Average linkage between groups, UPGMA).

7.    Minimalnej wariancji Warda (WARD, WarcTs method).