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

14

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.

Alex I.
źródło
1
Kilka algorytmów opisano w książce „Mining of Massive Datasets”, którą można pobrać bezpłatnie tutaj . Przeczytaj rozdział 7 „Klastrowanie”.
lanenok

Odpowiedzi:

12

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?

Ma ZAKOŃCZENIE - Anony-Mus
źródło
Nie wiedziałem o algorytmie online MacQueen! Czy zwykle osiąga takie same wyniki jak „klasyczne” środki K? Co powiesz na zastosowanie zamiast tego pobierania próbek ze zbiornika? W ten sposób OP ma próbkę do ponownego uruchomienia K-średnich na wypadek, gdyby przetestowano wiele wartości K.
Victor Ma
6

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).

Kasra Manshaei
źródło
Jest to możliwe i oczywiście zawsze zależne od danych. Jednak biorąc pod uwagę, że plakat ma 10 ^ 10 (przypuszczalnie niezależnych) próbek, wydaje się, że 10 wymiarów nie byłoby tutaj zbyt dużym problemem.
Ryan J. Smith
2
Dzięki za komentarz @ RyanJ.Smith. twój komentarz jest dokładnie w tym samym kierunku co mój. Po prostu nie widziałem nic na temat tego problemu w poście. I o liczbie próbek; ma jednak wiele punktów próbnych, które wciąż mogą utknąć w problemie wymiarowości. Myślę, że argumentujesz przeciwną stronę problemu niskiej wielkości próbki, który moim zdaniem jest nieważny. Jeśli ma dane o dużych wymiarach, problem będzie miał niewielki rozmiar próbki, ale myślę, że duża ilość danych niekoniecznie nic znaczy.
Kasra Manshaei
10 wymiarów to jeszcze niewiele.
Ma ZAKOŃCZENIE - Anony-Mousse
1
Jak określasz mojego przyjaciela? to, co powiedziałem, było wynikiem eksperymentu mającego odpowiedzieć na takie pytanie, jednak NIE MOŻNA na nie odpowiedzieć w ogóle! Czym dokładnie jest „dużo” w twoim komentarzu? zależy to od wielu okoliczności, o których wspomniałem w mojej odpowiedzi. w niektórych sytuacjach 10D może być problematyczne.
Kasra Manshaei