Algorytm LECZENIA - CURE algorithm

Część serii na
Uczenie maszynowe i eksploracja danych
Problemy Klasyfikacja Grupowanie Regresja Wykrywanie anomalii Czyszczenie danych AutoML Zasady stowarzyszenia Nauka wzmacniania Prognoza strukturalna Inżynieria funkcji Nauka funkcji Nauka online Nauka częściowo nadzorowana Nauka nienadzorowana Nauka rangi Indukcja gramatyczna
Uczenie nadzorowane ( klasyfikacja  • regresja ) Drzewa decyzyjne Zespoły Parcianka Wzmacnianie Losowy las k -NN Regresja liniowa Naiwny Bayes Sztuczne sieci neuronowe Regresja logistyczna Perceptron Maszyna wektorów trafności (RVM) Maszyna wektorów pomocniczych (SVM)
Grupowanie BRZOZOWY LECZYĆ Hierarchiczny k -oznacza Oczekiwanie – maksymalizacja (EM) DBSCAN OPTYKA Średnia zmiana
Redukcja wymiarowości Analiza czynników CCA ICA LDA NMF PCA PGD t-SNE
Prognoza strukturalna Modele graficzne Sieć Bayesa Warunkowe pole losowe Ukryty Markow
Wykrywanie anomalii k -NN Lokalny czynnik odstający
Sztuczna sieć neuronowa Autokoder Obliczenia kognitywne Głęboka nauka DeepDream Perceptron wielowarstwowy RNN LSTM GRU ESN Ograniczona maszyna Boltzmanna GAN SOM Konwolucyjna sieć neuronowa U-Net Transformator Wzrastająca sieć neuronowa Memtranzystor Elektrochemiczna pamięć RAM (ECRAM)
Nauka wzmacniania Q-learning SARSA Różnica czasowa (TD)
Teoria Kompromis między odchyleniami a wariancją Teoria uczenia się komputerowego Minimalizacja ryzyka empirycznego Nauka Occam Nauka PAC Nauka statystyczna Teoria VC
Miejsca uczenia maszynowego NeuroIPS ICML ML JMLR ArXiv:cs.LG
Powiązane artykuły Słowniczek sztucznej inteligencji Lista zbiorów danych do badań nad uczeniem maszynowym Zarys uczenia maszynowego
v T mi

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:

${\ Displaystyle E = \ suma _ {i = 1} ^ {k} \ suma _ {p \ w C_ {i}} (p-m_ {i}) ^ {2},}$

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. ${\displaystyle d_{min},d_{średnia}}$

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 ² 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ż

• grupowanie k-średnich
• Algorytm BFR

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.