ED-4.2-m11-1.0-Slajd24

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Algorytm k-medoidów (2)

Algorytm k-medoidów (2)


Ogólny schemat algorytm k-medoidów jest analogiczny do schematu algorytmu k-średnich, w którym średnią klastra zastąpiono medoidem klastra. Jednakże, zastąpienie średniej klastra jego medoidem ma istotną konsekwencję z punktu widzenia efektywności działania algorytmu. Aktualizacja średniej klastra w algorytmie k-średnich jest prostą operacją arytmetyczną. W algorytmie k-medoidów aktualizujemy medoid klastra, tj. wybieramy nowy punkt centralny klastra. Wybór nowego punktu centralnego polega na zastąpieniu aktualnego medoidu klastra obiektem nie będącym medoidem, jeżeli ta operacja poprawi wartość funkcji kryterialnej. Sprawdzenie, czy obiekt y (nie będący medoidem) może zastąpić aktualny medoid m wymaga analizy 4 przypadków dla każdego obiektu p (p również nie jest medoidem). Przypadek 1: p należy do klastra medoidu m. Jeżeli zastąpimy medoid m obiektem y i p znajduje się bliżej medoidu n, to przydziel p do klastra medoidu n. Przypadek 2: p należy do klastra medoidu m. Jeżeli zastąpimy medoid m obiektem y i p znajduje się bliżej obiektu y, to przydziel p do klastra nowego medoidu y. Przypadek 3: p należy do klastra medoidu n. Jeżeli zastąpimy medoid m obiektem y i p znajduje się bliżej medoidu n, to nie zmieniaj przydziału obiektu p. Przypadek 4: p należy do klastra medoidu n. Jeżeli zastąpimy medoid m obiektem y i p znajduje się bliżej obiektu y, to przydziel p do klastra nowego medoidu y. Po przeanalizowaniu wszystkich punktów oblicz wartośc funkcji kryterialnej. Jeżeli operacja zastąpienia medoidu m obiektem y poprawia wartość tej funkcji to dokonaj zastąpienia medoidu m obiektem y. Łatwo zauważyć, że operacja znajdowania nowego medoidu klastra jest znacznie bardziej złożona aniżeli operacja znajdowania średniej klastra.


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