Szybki k-oznacza jak algorytm dla 10 ^ 10 punktów?

Szukam k-oznacza grupowanie na zbiorze punktów 10-wymiarowych. Haczyk: jest 10 ^ 10 punktów .

Szukam tylko środka i wielkości największych klastrów (powiedzmy od 10 do 100 klastrów); Nie dbam o to, w jakim klastrze kończy się każdy punkt. Używanie k-średnich nie jest ważne; Właśnie szukam podobnego efektu, każdy przybliżony średni k lub związany z nim algorytm byłby świetny (minibatch-SGD oznacza ...). Ponieważ GMM jest w pewnym sensie tym samym problemem co k-znaczy, robienie GMM na danych o tym samym rozmiarze jest również interesujące.

W tej skali podpróbkowanie danych prawdopodobnie nie zmienia znacząco wyniku: szanse znalezienia tych samych 10 najlepszych klastrów przy użyciu 1/10000 próbki danych są bardzo dobre. Ale nawet wtedy jest to problem 10 ^ 6 punktów, który jest na / poza krawędzią możliwą do przełknięcia.

k-średnich opiera się na średnich .

Modeluje klastry za pomocą środków, a tym samym poprawa poprzez dodanie większej ilości danych jest marginalna. Błąd średniej oceny zmniejsza się o 1 / sqrt (n); więc dodawanie kolejnych danych opłaca się coraz mniej ...

Strategie dla tak dużych danych zawsze opierają się na próbkowaniu:

Jeśli chcesz mieć sublinearne środowisko uruchomieniowe, musisz wykonać próbkowanie!

W rzeczywistości Mini-Batch-Kmeans itp. Robią dokładnie to: wielokrotnie próbkując z zestawu danych.

Jednak próbkowanie (w szczególności próbkowanie bezstronne) również nie jest całkowicie bezpłatne ... zwykle musisz odczytać dane liniowo, aby pobrać próbkę, ponieważ nie masz losowego dostępu do poszczególnych rekordów.

Wybrałbym algorytm MacQueena. Jest online; domyślnie wykonuje pojedyncze przełożenie danych (chociaż popularne jest iterowanie). Nie jest łatwo dystrybuować, ale myślę, że możesz sobie pozwolić na liniowy odczyt swoich danych, powiedz 10 razy z dysku SSD?

Jako komentarz boczny zauważ, że użycie K-średnich dla danych 10D może skończyć się nigdzie zgodnie z przekleństwem wymiarowości. Oczywiście różni się nieco w zależności od charakteru danych, ale kiedy próbowałem określić próg, w którym K-Means zaczyna zachowywać się dziwnie w odniesieniu do wymiaru, otrzymałem coś w rodzaju 7D. Po 7 wymiarach zaczęło brakować poprawnych klastrów (moje dane zostały wygenerowane ręcznie zgodnie z 4 dobrze oddzielonymi rozkładami Gaussa i użyłem funkcji kmeans MATLAB do mojego małego eksperymentu).