P3200175

278 4. Analiza skupici

W metodzie Warda nie ma gwarancji, że dla wszystkich zbiorów danych otrzymywać będziemy optymalne (w sensie sumy kwadratów) grupy tworzone hierarchicznie. Połączenie hierarchizacji z optymalizacją powodować może zniekształcenie struktury danych (zob. Gordon, 1981) .

Mimo swoistego kryterium łączenia obiektów metoda Warda mieści się w schemacie Lance a i Williamsa, pod warunkiem że punktem wyjścia do procesu aglomeracji jest macierz kwadratowych odległości euklidesowych⁹⁰, a wówczas algorytm przeliczania odległości na każdym etapie łączenia jest następujący

n. + n

n. + n. + n

■d.. +

n, + n. + n

fi; + n. 4- n

(4.105)

gdzie: d_jr == (<i^.²⁾)², podobnie jak d_is, i nie może to być jakakolwiek inna miara odległości, jak tylko kwadratowa odległość euklidesowa⁹¹.

Metoda Warda wykazuje tendencję do tworzenia skupień o tej samej w przybliżeniu liczbie obiektów (Pielou, 1984). Jeżeli pojedynczy obiekt ma jednakową odległość od centroidów dwóch skupień o różnej liczbie obiektów, to ten punkt połączy się ze skupieniem o mniejszej liczbie obiektów. W wyniku tego małe skupienia przyłączają nowe obiekty szybciej niż skupienia duże i nie ma możliwości, aby tworzyły się łańcuchy. Tę własność metody Warda można w niektórych okolicznościach traktować jako pożyteczną.

Można mieć wątpliwości, czy metoda ta powinna być klasyfikowana w tej samej klasie co metody poprzednie. Jednak mimo odmiennego kryterium włączania obiektu do skupienia lub łączenia skupień, zaliczana jest do metod hierarchicznych (zob. Ludwig i Reynolds, 1988). Jeżeli obiekty stanowią próbę losową, to istnieje możliwość stosowania statystycznych testów homogeniczności lub hetero-geniczności skupień, w zależności z jakiej populacji pochodzą.

Przykład 4.8. (grupowanie hierarchiczne - metoda Warda)

Również metodę Warda zastosowano do macierzy odległości D⁽⁰⁾ z przykładu 4.3, z tym że odległości podniesiono do kwadratu. Kierując się wzorem (4.105), przeliczano odległości od nowo tworzonych skupień. Na pierwszym oraz na dru-** Techniki minimum wariancji są łatwe do przeprowadzenia i efektywne, jeśli grupowanie wyko-nuje się po analizie głównych składowych, a klasyfikowane obiekty są lokowane według swych współrzędnych na pierwszej osi układu składowych (zob. l^ebart, 1984). W takim ujęciu grupowanie jest sprowadzone do jednego (zbiorczego) wymiaru.

Odpowiedź na pytanie, dlaczego punktem wyjścia dla metody Warda może być macierz kwadratowych odległości euklidesowych, kryje się w twierdzeniu F.dwardsa i Cavalli-Sforzy (zob. punkt 4.7 2).

⁹¹ W przykładzie, który towarzyszy kolejnym przedstawianym metodom, pierwsze dwa obiekty o numerach 2 i 7 połączyły się na poziomie 2,17 i jest to pierwszy najmniejszy przyrost sumy kwa dratów odchyleń od centroidu tego pierwszego skupiska {Z 7). Formalnie rzecz biorąc, przyrost ten jest dwa razy mniejszy (zob. wzór 4.104).

4,6. Grupowanie hierarchiczne

-------— ²⁷⁹

gim etapie połączyły się pojedyncze obiekty w skupienia dwuelementowe na po ziomachd_rł z wyjściowej macierzy l)¹¹ Dendrogram narysowano, uwzględniając poziomy łączenia w pierwszej potędze (zob. rysunek 4.14j.

Poziomy

			-c.
	—<	*)_ 4,6226	_r-<	>—| Ml

4    5    6    2    7    1    3 ^0biel“y

Rysunek 4.14. Dendrogram (metoda Warda)

Na wyższych etapach łączenia, gdy korzystamy już z odległości przeliczonych, poziomy łączenia skupień w metodzie W arda są znacznie większe od odległości w innych metodach, z wyjątkiem metody najdalszego sąsiada (tu są one porównywalne). Hierarchia połączeń w tej metodzie jest identyczna jak w meto dzie elastycznej (zob. przykład 4.9), choć poziomy łączenia są tu nieco wyższe

4.6.8. Strategia elastyczna oraz schemat Lance’a i Wilłiamsa

Powróćmy jeszcze na chwilę do wspomnianego na wstępie ogólnego schematu Lancea i Wilłiamsa - liniowego kombinatorycznego równania, zapisywanego w postaci

d_¥ = a_xd_ir + a₂d_is + fid_n + y\d_it -</J    (4.106)

Identyfikacja parametrów a, ,a₂,/? oraz y dla poszczególnych strategii grupowania hierarchicznego jest oczywista. Podano je dalej w tablicy 4.4.

Warto jednak najpierw podać pewną mniej znaną strategię, znaną z zastosowań ekologicznych (zob. Ludwig i Reynolds. 1988) Lance i Williams zaproponowali w 1967 r. zasadę, w której parametry równania rekurencyjnego (4.106) przyjmują wartości

^a\ ^+a2 +/?= 1;    =cr₂; fi<l; y=0    (4.107)

Stwierdzili oni, że najwłaściwsze są małe ujemne wartości parametru fi i przyjęli ^=-0,25. W świetle ograniczeń (4.107) otrzymali oni a, = a₂ =0,625, co za-