ED-4.2-m11-1.0-Slajd26: Różnice pomiędzy wersjami
Nie podano opisu zmian |
Nie podano opisu zmian |
||
| Linia 4: | Linia 4: | ||
Ł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. | |||
[[ED-4.2-m11-1.0-Slajd25 | << Poprzedni slajd]] | [[ED-4.2-m11-1.0-toc|Spis treści ]] | [[ED-4.2-m11-1.0-Slajd27 | Następny slajd >>]] | [[ED-4.2-m11-1.0-Slajd25 | << Poprzedni slajd]] | [[ED-4.2-m11-1.0-toc|Spis treści ]] | [[ED-4.2-m11-1.0-Slajd27 | Następny slajd >>]] | ||
Aktualna wersja na dzień 12:39, 31 sie 2006
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.
