ED-4.2-m11-1.0-Slajd26

Z Studia Informatyczne
Wersja z dnia 12:39, 31 sie 2006 autorstwa ALesniewska (dyskusja | edycje)
(różn.) ← poprzednia wersja | przejdź do aktualnej wersji (różn.) | następna wersja → (różn.)
Przejdź do nawigacjiPrzejdź do wyszukiwania

CLARA, CLARANS

CLARA, CLARANS


Łatwo zauważyć, że algorytmy typu k-medoidów są słabo skalowalne – są bardzo kosztowne obliczeniowo dla dużych wartości n i k. Złożoność algorytmu wynika z kosztownej analizy aktualizacji medoidów. Próbą rozwiązania tego problemu była propozycja algorytmu CLARA. Idea algorytmu CLARA sprowadza się do następującego pomysłu: zamiast rozważać cały dostępny zbiór obiektów do grupowania, wybieramy reprezentatywny podzbiór obiektów metodą próbkowania. Rozwinięciem idei algorytmu CLARA i połączenia go z algorytmem PAM jest popularny algorytm CLARANS. Podobnie jak w przypadku algorytmu CLARA, zamiast rozważać cały dostępny zbiór obiektów do grupowania, wybieramy reprezentatywny podzbiór obiektów metodą próbkowania. Następnie, z wybranej próbki, stosując algorytm PAM, wybieramy zbiór medoidów będących środkami klastrów. Jeżeli mechanizm próbkowania obiektów zapewnia losowość próbki, to próbka będzie dobrze odzwierciedlała rozkład obiektów w oryginalnym zbiorze obiektów. Wybrany zbiór medoidów będzie, natomiast, w miarę wiernie odpowiadał wyborowi medoidów przez algorytm PAM z całego zbioru obiektów. Algorytmy CLARA i CLARANS cechują się lepszą efektywnością aniżeli klasyczny algorytm k-medoidów, jednakże nie zmieniają zasadniczą wysokiej złożoności metody k-medoidów. Poprawa efektywności jest skutkiem lepszego wyboru początkowego medoidów, a co za tym idzie, najczęściej, mniejszą liczbą iteracji.


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