P3200174

27t Analiza skupici

kialac). Na pierwszych etapai h, na których łączą się w jedno skupienie najbliższe pojedyncze obiekty, otrzyniujemy identyczne odległości w metodzie centruj dalncj i metodzie mediany (zauważmy, że jeżeli n, = n, — 1, to wzory na przeliczanie odległości są w obu tych metodach identyczne). Na wyższych etapach bieżenia, kiedy korzystamy już z odległości przeliczonych, a łączą się skupienia o rożnych liczebuuściach, odległości między skupieniami w metodzie mediany są mc większe od odległości w metodzie centroidalnej. Dendrogram dla metody mediany przedstawiono na rysunku 4.1 3.

4,00

2,00

5,7274 i-		4,0029				3,1874
			—<	>- 17	3,3986
		n

4    5    6    2    7    1    3 Obiekty

Poziomy

6,00

Rysunek 4.1 5 Dendrogram (metoda mediany)

Dendrogram w metodzie mediany jest bardzo spłaszczony i przypomina bardziej drzewko połączeń w metodzie najbliższego sąsiada, niż w metodzie centroidalnej czy średnio grupowej.

4.6.7. Metoda Warda

Metoda Warda (ang. minimum variance, sum ofsquares lub też incremcntal sum of squ-areclusteńng), zaproponowana w roku 1963, jest metodą znacznie różniącą się od poprzednich metod zarówno pod względem sposobu pomiaru podobieństwa, jak i kryterium łączenia skupień. Jest ona jedną z technik z grupy algorytmów, które usiłują na każdym etapie optymalizować podział otrzymany poprzez połączenie dwóch elementów, stosując kryterium minimalnego wzrostu łącznej wewnątrz-grupowej sumy kwadratów odchyleń wszystkich zmiennych dla każdego obiektu od ich średnich grupowych⁸⁸.

Przyjmując dla uproszczenia sytuację jednowymiarową (cecha X,), załóżmy, ze n obserwacji zamierzamy pogrupować w sposób hierarchiczny. Na każdym ⁿ Porównaj ideę grupowania podziałowego, punkt 4 7

1 W

etapie grupowania k (k- J,..    „

• t UI4 /| —* L 1,1.

naayt- sumę kwadratów odchyleń ud śuu, ^,4tyLhkku|:

w obrębu: każde

I(jr

^j,tn należy w_y/

/.<: skupltliid

A'. I'

tjr» 1.

14 102 j

1 następnie obliczyć łączną wewnątrzgrupową (lub we kwadratów, poprzez sumowanie po skupieniach

li-łli/skupuniufcij, Milo.,

14 103,

gdzie: 11 _f - liczba elementów w skupieniu g

x_tj - wartość cechy i-tej jednostki (i = 1.....n skupieniu g

Wartość wskaźnika W należy obliczać dla każdego możliwego pod/.ialu nu danym etapie łączenia. Procedura grupowania W aida przebieg* oasu,pu/^. Nd początku wszystkie obiekty traktujemy jako jednotlemciuowi grupy dlu których li'¹⁰¹ = 0. Na pierwszym etapie połączą sic dwa obiekt\ powicdzrm »1 naihli/ sze w sensie powyższego kryterium, czyli takie dla który ci. suma

lt^MI,= Ż(x —    )² + 2(a\ - x )‘ będzie najmniejsza Będą to te dwa obiekty

*    /=i    ⁹    /»>    ⁹

które dzieli najmniejsza odległość euklidesowa Można bowiem v»ykazai. /«

L    « 2L

Ż(a\. — a'_;)~ +    — Jr_;) = Z(jr_f -x. r / 2=(d;' >" / 2    (4104)

Na każdym kolejnym etapie łączone są dwie grupy w tuki sposob ab\ uzyskam możliwie najmniejszy przyrost wskaźnika ł1 ' Mozę byc oczywiścu więcej niż jedna para grup, które łącząc się, wywołałyby taki sam najmniejszy przyrost sumy kwadratów, jakkolwiek jest to mało prawdopodobne W każdy ni kolejnym kroku zmniejsza się liczba grup, aby po n krokach otrzymać tylko jedną grupę dla której

będziemy mieli 11'^(,i 1 = Z (a; - x_t)\ przy czym x - £ a / «. Jest to zatem co

do sposobu łączenia grup powtórzenie procedury hierarchicznej, jakkolwiek kry terium stosowane w łączeniach jest szczególne, odmienne mz w metodach po przednich. Powyższa suma kwadratów odchyleń H jest „ustalona, ale dochodzenie do niej w wyniku sukcesywnego zmniejszania liczby skupień 1 równoczesnego zw iększania ich liczebności powinno byc jak najwolniejsze | H Ward tłumaczył ow najmniejszy przyrost sunie kwadratów odchyleń wynikający' z połączenia dwóch skupień jako najmniejszą dodatkową stratę informacji (ang minimum inerease in informatian łoss), jaką nieuchronnie poc iąga za sobą zwięk wenie rozproszenia w nowym skupieniu, przy czym stratę informacji utożsamia! on z U’" * (zob Everitt, 1993).