ED-4.2-m10-1.0-Slajd28

Hierarchiczny aglomeracyjny algorytm grupowania

Przedstawiony na kolejnym slajdzie algorytm reprezentuje uproszczoną wersję ogólnego hierarchicznego aglomeracyjnego algorytmu grupowania. Podobnie jak w przypadku ogólnego algorytmu grupowania, w kroku pierwszym, każdy obiekt jest umieszczany w osobnym klastrze. Następnie, konstruowana jest macierz odległości pomiędzy klastrami. Znajdowana jest para najbliższych klastrów, zgodnie z przyjętą miara odległości. Znalezione klastry są łączone tworząc nowy klaster. Aktualizowana jest macierz odległości pomiędzy klastrami i poszukiwana jest kolejna para najbliższych klastrów. Proces łączenia klastrów powtarza się, aż do osiągnięcia zadanej liczby klastrów.

W przedstawionym algorytmie można wykorzystać dowolną z omówionych uprzednio miar odległości. Jeżeli miarą odległości pomiędzy klastrami jest „minimalna odległość”, to mówimy o algorytmie grupowania typu „single link” lub „single linkage”. Jeżeli miarą odległości jest „maksymalna odległość”, to mówimy o algorytmie grupowania typu „complete link” lub „complete linkage”. W przypadku przyjęcia miary „średniej odległość” mówimy o algorytmie typu „average link” lub „average linkage”. W zależności od przyjętej miary odległości uzyskujemy klastry o różnym kształcie.

<< Poprzedni slajd | Spis treści | Następny slajd >>