55294 P3200166

--4. Analizasku^

Przyjmując więc, że stan wyjściowy to uznanie wszystkich n obiektów zbioru Q za jednoelementowe skupienia, należy w procesie grupowania hierarchicznego wykonać n— 1 kroków, aby osiągnąć stan końcowy, jakim jest jedno skupienie obejmujące wszystkie grupowane elementy. W każdym kroku łączą się tylko dwa skupienia na określonym poziomie h (według najmniejszej odległości lub największego podobieństwa), na skutek czego ich liczba zmniejsza się o jeden, według schematu:

Krok	o	^1	2		k		n-1
Partycja	P,	P2	P3		P*.i		P„=n
Liczba skupień	n	n- 1	n-2		n - k		1
Poziom łączenia ; ho - 0		/i,	hi		h		fyi-i

Każdy krok (iteracja) obejmuje dwie czynności: łączenie dwóch obiektów najbardziej podobnych (tj. najbliższych sobie) oraz przeliczenie odległości od nowego skupienia. Ciąg takich kroków tworzy hierarchię klasyfikacji. W następstwie zmniejszającej się liczby skupień, każdemu kolejnemu krokowi towarzyszy nowa, zredukowana o jeden wymiar macierz odległości D^U). Wyjściową macierz odległości będziemy oznaczali przez D " .

Poziomy łączenia (ang. splitting lub jusion levels) tworzą ciąg liczb rzeczywistych /i₀ <    <.. < h_n i wskazują poziom podobieństwa, na którym się pojawia

dana partycja l\ Liczbami tymi można indeksować kolejne partycje. Wykaz kolejnych partycji wraz z poziomami łączenia może być elementem programów komputerowych.

Aby sformalizować problem przekształcania macierzy odległości poprzez przeliczanie odległości między nowo utworzoną grupą a pozostałymi grupami, wprowadźmy następujące oznaczenia, r, s — łączone grupy (jedno- lub wieloelementowe), p — grupa, którą otrzymujemy w wyniku połączenia grup r i s (p = r U s), d_ir,d_u — odległości między grupą i (i = 1,2,..., rc — k) a grupami łączonymi, odpowiednio r i s {k oznacza liczbę wykonanych już połączeń), d. — wyznaczana odległość między grupą i a nowo utworzoną grupą p.

Przeliczanie polega na określeniu nowych odległości d. jako funkcji odległości d_k id_is

Ąp^fWir^is)    (4.91)

Powoduje to, że w efekcie łączenia znika w macierzy odległości D jeden wiersz i jedna kolumna, powiedzmy s, zaś inny wiersz i kolumna, powiedzmy r, zmieni swe wartości zgodnie z przyjętą zasadą przeliczania. Gdy dwa skupienia połączą się i zostaną przeliczone odległości od innych skupień, to nowo powstałe

skupienie traktujemy jako całość. Odległości między grupami, które na danym etapie nie łączą się, pozostają niezmienione.

Grupowanie hierarchiczne jest postępowaniem niejednolitym Istnieje kilka różnych zasad (metod, kryteriów czy strategii) przeliczania odległości, czyli róz nie określonych funkcji d , z których najbardziej znane są metoda najbliższego sąsiada, metoda najdalszego sąsiada, metoda średniej grupowej, metoda centro idalna, metoda mediany, metoda elastyczna oraz metoda Warda W połowie lat sześćdziesiątych M. Lance i W T. Williams opracowali ogólny schemat uogol niający te zasady, który następnie został zmodyfikowany przez M Jambu' Nie jednolitość aglomeracyjnego grupowania hierarchicznego tkwi także w różnych sposobach wyjściowego pomiaru odległości lub podobieństwa Zderzenie tych dwóch elementów: przeliczania odległości i pomiaru podobieństwa daje ogromną różnorodność postępowań, a tym samym utrudnia ocem ich popraw nosa

Istotę aglomeracyjnego grupowania hierarchicznego przedstawimy szczegółowo na przykładzie metody najbliższego sąsiada, co oczywiście me przesądza ojej wartości. Następnie omówimy inne popularne metody tego iypu grupowania zwracając jednocześnie uwagę na ich własności

4.6.2. Metoda najbliższego sąsiada

Metoda najbliższego sąsiada (ang. single linkage, nearest neighbour ⁴ aglomeracyjnego grupowania hierarchicznego polega na przeliczaniu odległości między obiektami jednego skupienia a obiektami innego skupienia według kryterium nai mniejszej odległości. Oznacza to. że odległości między nowym skupieniem a m nymi skupieniami i (jednoelementowymi lub na dalszych etapach łączenia juz wieloelementowymi) wyznaczane są przez najbliższe obiekty w tym nowym skupieniu w stosunku do pozostałych skupień (zob rysunek 4.3).

Wyjściowo każdy obiekt traktuje się jako odrębną grupę Ponieważ zgodnie z ogólną zasadą na każdym etapie łączą się te dwa obiekty lub skupienia, między którymi odległość jest najmniejsza (na pierwszym etapie - odległość wyjściowa, na kolejnych - odległość przeliczona), to szuka się w pierwszej (wyjściowej) ma cierzy D^<01 odległości najkrótszej

min{</_B} i = r, i* 1,2,... ,n-,r*s    (4.92)

⁷³ Do schematu Lancca i Williamsa oraz modyfikacji Jambu powrócimy w dalszej części tego roz działu (punkt 4.6.8).

* Pod nazwą metody dend ryt owej jest ona przypisywana polskim uczonym Florkowi, hukaszewi czowi, Perkalowi, Steinhausowi i Zubrzyckiemu (1951 W tym ujęciu, pod nazwą sirgle linkage me zaproponował ją później Sncath (1957) oraz niezależnie McQuitty (1957) leszcze później. Johnson (1967) użył na jej określenie nazwy minimum method