Metoda Warda

Metoda Warda to jedna z aglomeracyjnych metod grupowania, którą spośród pozostałych wyróżnia wykorzystanie podejścia analizy wariancji do oszacowania odległości między skupieniami. Zmierza ona do minimalizacji sumy kwadratów odchyleń dowolnych dwóch skupień, które mogą zostać uformowane na każdym etapie. Traktowana jest jako bardzo efektywna, chociaż zmierza do tworzenia skupień o małej wielkości. Daje pełną kontrolę nad wynikową liczbą grup oraz przedstawia najbardziej naturalne skupiska elementów.

Schemat grupowania

Kolejność postępowania w metodzie Warda jest podobna jak w pozostałych metodach aglomeracyjnych. Znaczące różnice występują w użytych we wzorze parametrach. Schemat postępowania wygląda następująco:

1. Wyznaczenie macierzy odległości taksonomicznych o wymiarach n·n, która zawiera odległość każdej pary obiektów. Macierz ta jest symetryczna względem głównej przekątnej, którą stanowią same zera.
2. Wyszukanie par obiektów (a w dalszej części skupień), dla których wzajemna odległość jest najmniejsza. Przyjąć należy, że obiekty te mają numery „p” i „q”, przy czym p<q.
3. Złączenie „p” i „q” w jedno nowe skupienie, które zajmuje pozycję o numerze „p”. Jednocześnie usuwa się obiekt (skupienie) o numerze „q”, zaś numery skupień o numerze od niego wyższym zmniejsza się o jeden. W ten sposób wymiar macierzy zmniejsza się o 1.
   Np. jeżeli dla grupy 10 obiektów łączy się obiekt 4 i 7, nowe skupienie powstaje w miejscu 4, w miejsce obiektu siódmego przechodzi dotychczasowy ósmy, 9 zmienia się w 8 i 10 w 9. Macierz 10x10 zmienia się w 9x9.
4. Wyznacza się odległość nowego skupienia od każdego pozostałego według wzoru:

$D_{pr}=a_{1}\cdot d_{pr} a_{2}\cdot d_{qr} b\cdot d_{pq},$

gdzie:

$r$ przebiega numery skupień różne od „p” i „q”

$D_{pr}$ – odległość nowego skupienia od skupienia o numerze „r”

$d_{pr}$ – odległość pierwotnego skupienia „p” od skupienia „r”

$d_{qr}$ – odległość pierwotnego skupienia „q” od skupienia „r”

$d_{pq}$ – wzajemna odległość pierwotnych skupień „p” i „q”

$a_{1},$ $a_{2},$ $b$ – parametry, które w metodzie Warda mają wzory:

$a_{1}={\frac {n_{p} n_{r}}{n_{p} n_{q} n_{r}}}\quad {}$ $a_{2}={\frac {n_{q} n_{r}}{n_{p} n_{q} n_{r}}}\quad {}$ $b={\frac {-n_{r}}{n_{p} n_{q} n_{r}}}$

we wzorach tych „n” oznacza liczebność pojedynczych obiektów w poszczególnych obiektach.

Uwaga! Chociaż obliczenia wskazują inaczej, na głównej przekątnej zawsze utrzymuje się zera, inaczej mówiąc – odległość nowego skupienia od niego samego zawsze wynosi 0.

Krok drugi i trzeci powtarza się tak długo, aż wszystkie jednostki zostaną połączone w jedno n-elementowe skupienie.

Interpretacja otrzymanego skupienia

Drzewko ilustrujące grupowanie metodą Warda

Po zakończeniu grupowania tworzy się diagram drzewa (dendrogram). Liczby na osi poziomej oznaczają odległość, a długości linii łączących poszczególne skupienia odpowiadają najmniejszym odległościom wyszukiwanym w kroku nr 2. Należy zauważyć, że rosną one wraz z każdym kolejnym połączeniem. Wiąże się to z faktem, że odległości wyliczane dla nowo tworzonych skupień są zawsze większe niż odległości bazowe.

Z wykresu można dowiedzieć się:

• w jakiej kolejności dokonywano łączenia obiektów,
• jakie skupienia łączono w n-tym grupowaniu,
• w zależności od wybranej odległości można ustalić dowolną liczbę grup (na przykładowym obrazku wybierając np. odległość nie większą niż siedem, widoczne jest 5 grup),
• jaka jest liczebność i skład poszczególnych grup.

Zobacz też

• metoda aglomeracyjna

Bibliografia

• Biegańska U., Cluster Analysis
• Statistica.pl
• Lula P., Web Mining, materiały dydaktyczne