Klaster Big Data w R i czy próbkowanie jest istotne?

13

Jestem nowy w nauce o danych i mam problem ze znalezieniem klastrów w zestawie danych z 200 000 wierszy i 50 kolumnami w R.

Ponieważ dane mają zarówno zmienne liczbowe, jak i nominalne, metody takie jak K-średnie, które wykorzystują euklidesową miarę odległości, nie wydają się właściwym wyborem. Zwracam się więc do PAM, agnes i hclust, który przyjmuje jako dane macierz odległości.

Metoda daisy może działać na danych mieszanych, ale macierz odległości jest po prostu zbyt duża: 200 000 razy 200 000 jest znacznie większa niż 2 ^ 31-1 (limit długości wektora przed R 3.0.0.)

Nowy R 3.0.0 wydany wczoraj obsługuje długie wektory o długości większej niż 2 ^ 31-1. Ale podwójna matryca 200 000 na 200 000 wymaga ciągłej pamięci RAM większej niż 16 Gb, co nie jest możliwe na moim komputerze.

Czytam o obliczeniach równoległych i pakiecie bigmemory i nie jestem pewien, czy one pomogą: jeśli użyję daisy, wygeneruje dużą matrycę, która i tak nie zmieści się w pamięci.

Przeczytałem również o poście o pobieraniu próbek: czy pobieranie próbek jest istotne w czasach „dużych zbiorów danych”?

Czy w moim przypadku istotne jest zastosowanie próbkowania w zbiorze danych, skupienie w próbce, a następnie wywnioskowanie struktury całego zestawu danych?

Czy możesz prosić o sugestie? Dziękuję Ci!

O mojej maszynie:

Wersja R 3.0.0 (2013-04-03)

Platforma: x86_64-w64-mingw32 / x64 (64-bit)

System operacyjny: Windows 7 64bit

RAM: 16,0 GB

Społeczność
źródło
Jedyną znaną mi metodą klastrowania, która dotyczy dużych zbiorów danych (np. Milionów przypadków) i która może akceptować zmienne nominalne wraz ze zmiennymi numerycznymi, jest klaster TwoStep znaleziony w SPSS.
ttnphns

Odpowiedzi:

4

Jak zauważyłeś, żadna metoda wymagająca matrycy pełnej odległości nie będzie działać. Pamięć to jedno, ale drugie to środowisko wykonawcze. Typowe implementacje hierarchicznego grupowania są w (wiem, że ELKI ma SLINK, który jest algorytmem do klastrowania pojedynczego łącza). To po prostu nie skaluje się do dużych zestawów danych.O ( n 2 )O(n3)O(n2)

Sam PAM nie powinien wymagać pełnej macierzy odległości, ale wiadomo, że algorytm źle skaluje, ponieważ następnie musi (ponownie) obliczyć wszystkie pary odległości w obrębie każdego skupienia na każdej iteracji, aby znaleźć najbardziej centralne elementy. Jest to o wiele mniej, jeśli masz dużą liczbę klastrów, ale mimo to dość drogie!

Zamiast tego powinieneś przyjrzeć się metodom, które mogą wykorzystywać struktury indeksów do przyspieszenia. Przy dobrym indeksie takie algorytmy grupowania mogą działać w co jest znacznie lepsze w przypadku dużych zestawów danych.O(nlogn)

Jednak w przypadku większości tych algorytmów należy najpierw upewnić się, że funkcja odległości jest naprawdę dobra; musisz rozważyć sposoby przyspieszenia zapytań za pomocą odpowiednich indeksów.

Zauważ również, że w wielu przypadkach - i może się tak zdarzyć w przypadku PAM - możesz najpierw uruchomić algorytm na próbce , a następnie dopracować go tylko na pełnym zestawie danych. Jeśli twoja próbka jest reprezentatywna, algorytmy takie jak k-średnie i PAM powinny dać ci zasadniczo taki sam wynik jak dla pełnego zestawu danych.

Ma ZAKOŃCZENIE - Anony-Mus
źródło
Nie pomoże tutaj OP, ale w przypadku, gdy przyjdzie ktoś inny, który ma „pośrednie” liczby próbek: istnieje również szybki klaster dla R (patrz math.stanford.edu/~muellner/fastcluster.html ).
cbeleites niezadowoleni z SX
Cześć Anony-Mousse, czy możesz wskazać mi niektóre algorytmy wykorzystujące przyspieszenie struktury indeksu? Wielkie dzięki!
Na przykład DBSCAN można przyspieszyć dzięki indeksom obsługującym zapytania o zakres epsilon. Prawdopodobnie oznacza to także klaster zmiany. Optyka, który może być również przyspieszone w ten sposób, może być postrzegane jako bardziej zaawansowaną wersją klastrów sprzężeń (można nazwać „hierarchiczne grupowanie gęstość podnośnik”)
ma zakończyć - anony-Mousse
2

wypróbuj funkcję CLARA z pakietu klastra w R. Implementuje algorytm przypominający pam poprzez subsampling danych (upewnij się, że podajesz rozmiary podprób, które mają sens dla danych, ponieważ wartości domyślne są celowo zbyt małe). Działa to szczególnie dobrze, jeśli mediacje w twoich danych mogą być reprezentowane przez małą próbkę wszystkich danych (tzn. - w zestawie danych jest stosunkowo mniej klastrów). W ten sposób możesz efektywnie grupować małe losowe próbki i dodawać punkty do wstępnie obliczonego rozwiązania klastrowania.

http://en.wikibooks.org/wiki/Data_Mining_Algorithms_In_R/Clustering/CLARA

zzk
źródło
Cześć ZZK, dziękuję za odpowiedź. Czytałem wcześniej o Clara, ale wydaje się, że zapewnia ona jedynie metrykę euklidesową i manhattan. Głównym problemem jest to, że mój zestaw danych zawiera zarówno zmienne liczbowe, jak i nominalne. Dlatego użycie żadnej miary do pomiaru odległości nie jest właściwe.
Ach tak, to jest obecnie również ograniczenie. Wierzę, że metoda ta może być wykonana na dowolnym dowolnym dystansie, ale nie zadałem sobie trudu, aby przejrzeć kod źródłowy, aby sprawdzić, czy można go zmienić.
zzk
0

Możesz także zastosować analizę wielu korespondencji do swoich zmiennych jakościowych i dokonać przekształceń w zmienną numeryczną.

Alvaro
źródło
2
To wydaje się dobrym pomysłem, ale może być trochę rzadkie. Czy możesz to trochę wyjaśnić, aby wyjaśnić, co to jest i dlaczego to by pomogło?
gung - Przywróć Monikę