Algorytm LECZENIA - CURE algorithm
Część serii na |
Uczenie maszynowe i eksploracja danych |
---|
CURE (Clustering Using REpresentatives) to wydajny algorytm grupowania danych dla dużych baz danych . W porównaniu z grupowaniem K-średnich jest bardziej odporny na wartości odstające i umożliwia identyfikację klastrów o niesferycznych kształtach i wariancji wielkości.
Wady tradycyjnych algorytmów
Popularny algorytm grupowania K-średnich minimalizuje sumę kwadratów błędów kryterium:
Biorąc pod uwagę duże różnice w rozmiarach lub geometriach różnych klastrów, metoda błędu kwadratowego może podzielić duże klastry, aby zminimalizować błąd kwadratowy, co nie zawsze jest poprawne. Ponadto w przypadku hierarchicznych algorytmów grupowania problemy te występują, ponieważ żadna z miar odległości między klastrami ( ) nie działa z różnymi kształtami klastrów. Również czas działania jest długi, gdy n jest duże.
Problem z algorytmem BIRCH polega na tym, że po wygenerowaniu klastrów po kroku 3 wykorzystuje on centroidy klastrów i przypisuje każdy punkt danych do klastra z najbliższym centroidem. Używanie tylko centroidu do redystrybucji danych powoduje problemy, gdy klastry nie mają jednakowych rozmiarów i kształtów.
Algorytm grupowania CURE
Aby uniknąć problemów z niejednorodnymi rozmiarami lub kształtami klastrów, CURE wykorzystuje hierarchiczny algorytm grupowania , który przyjmuje środek między punktami opartymi na centroidach a wszystkimi ekstremami punktowymi. W CURE wybierana jest stała liczba c dobrze rozproszonych punktów klastra i są one kurczone w kierunku środka ciężkości klastra o ułamek α. Punkty rozproszone po zmniejszeniu są wykorzystywane jako reprezentanci klastra. Klastry z najbliższą parą przedstawicieli to klastry, które są łączone na każdym etapie hierarchicznego algorytmu grupowania CURE. Umożliwia to CURE prawidłową identyfikację klastrów i zmniejsza wrażliwość na wartości odstające.
Czas działania to O( n 2 log n ), co czyni go dość kosztownym, a złożoność przestrzeni to O( n ).
Algorytmu nie można zastosować bezpośrednio do dużych baz danych ze względu na dużą złożoność środowiska uruchomieniowego. Ulepszenia odpowiadają na to wymaganie.
- Próbkowanie losowe : próbkowanie losowe obsługuje duże zestawy danych. Generalnie losowa próbka mieści się w pamięci głównej . Losowe pobieranie próbek wiąże się z kompromisem między dokładnością a wydajnością.
- Partycjonowanie : Podstawowym pomysłem jest podzielenie przestrzeni próbki na p partycji. Każda partycja zawiera n/p elementów. Pierwszy przebieg częściowo grupuje każdą partycję, aż końcowa liczba klastrów zmniejszy się do n/pq dla pewnej stałej q ≥ 1. Drugi przebieg grupowania na n/q częściowo grupuje partycje. W drugim przebiegu przechowywane są tylko punkty reprezentatywne, ponieważ procedura łączenia wymaga tylko punktów reprezentatywnych poprzednich klastrów przed obliczeniem punktów reprezentatywnych dla połączonego klastra. Partycjonowanie wejścia skraca czas wykonania.
- Etykietowanie danych na dysku : Biorąc pod uwagę tylko reprezentatywne punkty dla k klastrów, pozostałe punkty danych są również przypisywane do klastrów. W tym celu wybierany jest ułamek losowo wybranych punktów reprezentatywnych dla każdego z k skupień i punkt danych jest przypisywany do skupienia zawierającego najbliższy mu punkt reprezentatywny.
Pseudo kod
LECZENIE (liczba punktów, k )
Wejście: zbiór punktów S
Wyjście: k klastrów
- Dla każdego skupienia u (każdy punkt wejściowy), w u.średnia i u.rep przechowuj średnią punktów w skupieniu i zestaw c reprezentatywnych punktów skupienia (początkowo c = 1, ponieważ każdy skupienie ma jeden punkt danych) . Również u.closest przechowuje klaster najbliżej u.
- Wszystkie punkty wejściowe są wstawiane do drzewa kd T
- Traktuj każdy punkt wejściowy jako oddzielny klaster, oblicz u.closest dla każdego u, a następnie wstaw każdy klaster do sterty Q. (klastry są ułożone w kolejności rosnącej odległości między u i u.closest).
- Podczas gdy rozmiar (Q) > k
- Usuń górny element Q (powiedzmy u) i połącz go z najbliższym skupieniem u.closest (powiedzmy v) i oblicz nowe punkty reprezentatywne dla połączonego skupienia w.
- Usuń u i v z T i Q.
- Dla wszystkich klastrów x w Q zaktualizuj x.closest i przenieś x
- wstaw w do Q
- powtarzać
Dostępność
- Biblioteka open source pyclustering zawiera implementację algorytmu CURE w Pythonie i C++.
Zobacz też
Bibliografia
- Guha, Sudipto; Rastogi, Rajeev; Shim, Kyuseok (1998). „CURE: wydajny algorytm klastrowania dla dużych baz danych” (PDF) . Systemy informacyjne . 26 (1): 35–58. doi : 10.1016/S0306-4379(01)00008-4 .
- Kogan, Jakub; Mikołaj, Karol K.; Teboulle, M. (2006). Grupowanie danych wielowymiarowych: najnowsze postępy w grupowaniu . Skoczek. Numer ISBN 978-3-540-28348-5.
- Theodoridis, Sergios; Koutroumbas, Konstantinos (2006). Rozpoznawanie wzorców . Prasa akademicka. s. 572-574. Numer ISBN 978-0-12-369531-4.