Klastry zajmujące mało miejsca

Większość algorytmów grupowania, jakie widziałem, zaczyna się od tworzenia odległości między poszczególnymi punktami, co staje się problematyczne w przypadku większych zestawów danych. Czy jest taki, który tego nie robi? Czy może jest to podejście częściowe / przybliżone / naprzemienne?

Który algorytm / implementacja klastrowania zajmuje mniej niż O (n ^ 2) miejsca?

Czy jest gdzieś lista algorytmów oraz ich wymagań dotyczących czasu i przestrzeni?

K-Means i Mean-Shift używają surowych deskryptorów próbek (nie ma potrzeby wstępnego obliczania macierzy powinowactwa).

W przeciwnym razie do grupowania widmowego lub iteracji mocy można użyć rzadkiej reprezentacji macierzy (np. Skompresowane rzadkie rzędy) macierzy powinowactwa k najbliższych sąsiadów (dla pewnej metryki odległości lub powinowactwa). Jeśli k jest małe (powiedzmy 5 lub 10). Otrzymasz bardzo oszczędną przestrzennie reprezentację (2 * n_samples * k * 8 bajtów dla wartości zmiennoprzecinkowych o podwójnej precyzji).

Niektóre algorytmy grupowania mogą wykorzystywać struktury indeksów przestrzennych. Pozwala to na przykład na działanie DBSCAN i OPTICS w czasie (o ile indeks pozwala na zapytania ).$O(n\log n)$$O(\log n)$

Oczywiście algorytm działający w tej złożoności nie buduje macierzy odległości .$O(n^2)$

W przypadku niektórych algorytmów, takich jak hierarchiczne grupowanie z pojedynczym łączeniem i łączenie pełne, dostępne są zoptymalizowane algorytmy (SLINK, CLINK). Po prostu większość ludzi korzysta z tego, co może dostać i co jest łatwe do wdrożenia. I grupowanie hierarchiczne to naiwny łatwo wdrożyć używając iteracjach nad matrycy odległość (otrzymanego w algorytm ...).$n$$n^2$$O(n^3)$

Nie znam pełnej listy algorytmów klastrowania. W końcu prawdopodobnie istnieje ponad 100 algorytmów klastrowych. Na przykład istnieje co najmniej tuzin wariantów k-średnich. Ponadto występuje złożoność w czasie wykonywania, a także złożoność pamięci; jest przypadek średni i najgorszy. Istnieją ogromne różnice w implementacji (np. Wspomniane powyżej pojedyncze łącze; implementacje DBSCAN, które nie używają indeksu, a zatem znajdują się w i chociaż nie muszą przechowywać pełnej macierzy odległości , nadal muszą obliczyć wszystkie odległości parami). Plus jest mnóstwo parametrów. Dla k-średnich,$O(n^2)$$n\times n$$k$jest krytyczny. W przypadku praktycznie dowolnego algorytmu funkcja odległości ma ogromną różnicę (dowolne wiele implementacji dopuszcza tylko odległość euklidesową ...). A kiedy dojdziesz do kosztownych funkcji odległości (poza trywialnymi rzeczami, takimi jak euklides), liczba obliczeń odległości może szybko stać się główną częścią. Musisz zatem rozróżnić całkowitą liczbę operacji od liczby potrzebnych obliczeń odległości. Tak więc algorytm, który jest w operacjach , ale tylko obliczenia odległości mogą łatwo przewyższyć algorytm, który jest w obu przypadkach, gdy funkcje odległości są naprawdę drogie (powiedzmy odległość sama funkcja to ).$O(n^2)$$O(n)$$O(n \log n)$$O(n)$

Dobre pytanie. Metoda „słomianego człowieka” dla powiedzmy 3 najbliższych sąsiadów polega na próbkowaniu sąsiadów Nsample z każdego punktu danych, zachowując najbliższy 3. Chociaż jest to banalne, uruchomienie dla kilku wartości Nsample da ci pojęcie o stosunku sygnału / szumu, hałasie bliskim / tle , łatwo wykreślone dla twoich danych. Dodatkową sztuczką jest sprawdzenie sąsiadów sąsiadów, aby sprawdzić, czy któryś z nich nie jest bliższy niż bezpośredni sąsiad. Ponadto, jeśli dane wejściowe są już dobrze przetasowane, próbkuj w blokach, w przeciwnym razie pamięć podręczna zostanie zniszczona.

(Dodano): zobacz Fastcluster w R i wierzę w SciPy v0.11.
Aby zobaczyć tekst, zobacz wyszukiwarka podobieństw Google .

Powtórz: „Odpowiednia miara podobieństwa jest o wiele ważniejsza dla osiągnięcia sukcesu w klastrowaniu niż wybór algorytmu klastrowania” - metoda wyboru klastrowania .