ED-4.2-m10-1.0-Slajd27

From Studia Informatyczne

Ogólny hierarchiczny aglomeracyjny algorytm grupowania

Ogólny hierarchiczny aglomeracyjny algorytm grupowania


Ogólny schemat hierarchicznego aglomeracyjnego algorytmu grupowania można zdefiniować następująco. Na wejściu algorytmu mamy bazę danych obiektów D. Wynikiem działania algorytmu jest dendrogram reprezentujący grupowanie obiektów. Algorytm składa się z 3 kroków. W kroku pierwszym, każdy obiekt jest umieszczany w osobnym klastrze. W kroku drugim jest konstruowana macierz odległości pomiędzy klastrami. Oczywiście, po kroku pierwszym, macierz ta reprezentuje, de facto, odległość pomiędzy obiektami bazy danych D. W kolejnym, trzecim kroku, dla zadanej wartości progowej niepodobieństwa dk, tworzony jest graf klastrów, w którym każda para klastrów, której wzajemna odległość jest mniejsza niż dk, jest połączona lukiem. Algorytm wraca do kroku drugiego – uaktualniana jest macierz odległości pomiędzy klastrami i ponownie, dla zadanej wartości progowej niepodobieństwa dk (wartość ta może się zmieniać w kolejnych iteracjach), którym każda para klastrów, której wzajemna odległość jest mniejsza niż dk, jest łączona łukiem w grafie klastrów. Proces ten powtarza się, aż wszystkie klastry utworzą graf spójny. Jak wspomnieliśmy wcześniej, wynikiem działania algorytmu jest dendrogram reprezentujący grupowanie obiektów. Jeżeli chcemy określić wynik grupowania obiektów dla zadanej wartości k (zadana liczba klastrów), to w dendrogramie należy ustawić warunek stopu w postaci linii przecinającej dendrogram w odpowiednim miejscu. Zauważmy, że przedstawiony ogólny algorytm aglomeracyjny pozwala zmieniać, w kolejnych iteracjach, wartość progową niepodobieństwa, co wpływa na wynik grupowania.


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