Wykorzystanie pamięci scikit-learning DBSCAN

Question

ZAKTUALIZOWANE: Ostatecznie, rozwiązanie, które wybrałem do grupowania mojego dużego zbioru danych, zostało zaproponowane przez Anony-Mousse poniżej. Oznacza to, że za pomocą implementacji ELK w DBSCAN można tworzyć klastrowanie zamiast uczenia się przez scikit. Można go uruchomić z wiersza poleceń i przy odpowiednim indeksowaniu, wykonuje to zadanie w ciągu kilku godzin. Użyj GUI i małych przykładowych zestawów danych, aby opracować opcje, których chcesz użyć, a następnie udaj się do miasta. Warto się przyjrzeć. Anywho, przeczytaj opis mojego pierwotnego problemu i interesującą dyskusję.

Mam zestaw danych zawierający ~ 2,5 miliona próbek, każdy z 35 funkcjami (wartości zmiennoprzecinkowe), które próbuję utworzyć klaster. Próbowałem to zrobić dzięki implementacji DBSCAN scikit-learning przy użyciu metryki odległości Manhattan i wartości epsilon oszacowanej na podstawie niewielkich losowych próbek pobranych z danych. Jak na razie dobrze. (tutaj jest fragment, dla odniesienia)

db = DBSCAN(eps=40, min_samples=10, metric='cityblock').fit(mydata) 

Moim problemem w tej chwili jest to, że łatwo mi zabraknie pamięci. (Obecnie pracuję na maszynie z 16 GB pamięci RAM)

Moje pytanie brzmi, czy DBSCAN oblicza macierz odległości parami w locie w trakcie działania, i to jest to, co pożera moją pamięć? (2,5 miliona^2) * 8 bajtów jest oczywiście głupio duże, rozumiem to. Czy nie powinienem używać metody fit()? A ogólniej, czy istnieje sposób obejścia tego problemu, czy generalnie szczerzę tu niewłaściwe drzewo?

Przepraszam, jeśli odpowiedź staje się oczywista. Zastanawiałem się nad tym przez kilka dni. Dzięki!

Dodatek: Nawet jeśli ktoś mógłby wyjaśnić mi różnicę między fit(X) i fit_predict(X), doceniłbym to - obawiam się, że po prostu nie rozumiem tego.

Dodatek # 2: Na pewno, po prostu wypróbowałem to na maszynie z ~ 550 GB pamięci RAM i nadal wybuchło, więc czuję, że DBSCAN prawdopodobnie próbuje utworzyć macierz odległości parami lub coś, co wyraźnie zaznaczam nie chcę tego robić. Chyba teraz najważniejsze pytanie brzmi: jak zatrzymać to zachowanie lub znaleźć inne metody, które mogą bardziej odpowiadać moim potrzebom. Dziękuję, że przyjechałeś tu ze mną.

Załącznik nr 3 (!): Zapomniałem dołączyć traceback, to jest tutaj,

Traceback (most recent call last): 
    File "tDBSCAN.py", line 34, in <module> 
    db = DBSCAN(eps=float(sys.argv[2]), min_samples=10, metric='cityblock').fit(mydata) 
    File "/home/jtownsend/.local/lib/python2.6/site-packages/sklearn/base.py", line 329, in fit_predict 
    self.fit(X) 
    File "/home/jtownsend/.local/lib/python2.6/site-packages/sklearn/cluster/dbscan_.py", line 186, in fit 
    **self.get_params()) 
    File "/home/jtownsend/.local/lib/python2.6/site-packages/sklearn/cluster/dbscan_.py", line 69, in dbscan 
    D = pairwise_distances(X, metric=metric) 
    File "/home/jtownsend/.local/lib/python2.6/site-packages/sklearn/metrics/pairwise.py", line 651, in pairwise_distances 
    return func(X, Y, **kwds) 
    File "/home/jtownsend/.local/lib/python2.6/site-packages/sklearn/metrics/pairwise.py", line 237, in manhattan_distances 
    D = np.abs(X[:, np.newaxis, :] - Y[np.newaxis, :, :]) 
MemoryError 

Answer 1

Problem najwyraźniej to wdrożenie niskiej jakości DBSCAN w scikit.

DBSCAN nie potrzebuje matrycy odległości. Algorytm został zaprojektowany z wykorzystaniem bazy danych, która może przyspieszyć funkcję regionQuery i wydajnie zwrócić sąsiadów w promieniu zapytania (indeks przestrzenny powinien obsługiwać takie zapytania w O(log n)).

Jednak implementacja w scikit, jak widać, oblicza pełną macierz odległościową O(n^2), co wiąże się z kosztami zarówno pod względem pamięci, jak i czasu pracy.

Widzę dwie możliwości:

1. Możesz spróbować DBSCAN wdrożenie w ELKI zamiast tego, który, gdy jest używany z R * Indeks -tree zwykle jest znacznie szybsze niż naiwnej realizacji.

2. W przeciwnym razie możesz chcieć ponownie zaimplementować DBSCAN, ponieważ implementacja w scikit najwyraźniej nie jest zbyt dobra. Nie bój się tego: DBSCAN jest naprawdę prosty w implementacji. Najtrudniejszą częścią dobrej implementacji DBSCAN jest funkcja regionQuery. Jeśli możesz szybko uzyskać to zapytanie, DBSCAN będzie szybki. Możesz też ponownie użyć tej funkcji dla innych algorytmów.

Update: teraz, sklearn nie oblicza odległość matrycy i może, na przykład, użyć wskaźnika KD drzewa. Jednak ze względu na "wektoryzację" nadal będzie obliczał sąsiadów każdego punktu, więc wykorzystanie pamięci przez sklearn dla dużego epsilon jest O (n²), podczas gdy do mojego zrozumienia wersja w ELKI będzie używać tylko pamięci O (n). Więc jeśli zabraknie Ci pamięci, wybierz mniejszy epsilon i/lub spróbuj ELKI.

Answer 2

Algorytm DBSCAN faktycznie robi obliczyć macierz odległości, więc nie ma szans tutaj. W przypadku tak dużej ilości danych polecam używanie MiniBatchKMeans. Nie możesz użyć metryki Manhattan tam po wyjęciu z pudełka, ale możesz wykonać własną implementację. Może najpierw wypróbuj standardową implementację z metryką euklidesową.

Nie znam wielu algorytmów grupujących, które nie wykonują odległości par.

Korzystanie z nowo osadzonego środka leżącego pod spodem cheat-sheet: choć szczęście.

Answer 3

Możesz to zrobić za pomocą algorytmu DBSCAN scikit-learn z algorytmem metryki i drzewka haversine. Nie ma potrzeby wstępnego obliczania matrycy odległości.

Ten przykład clusters over a million GPS latitude-longitude points z DBSCAN/haversine i unika problemów zużycie pamięci:

df = pd.read_csv('gps.csv') 
coords = df.as_matrix(columns=['lat', 'lon']) 
db = DBSCAN(eps=eps, min_samples=ms, algorithm='ball_tree', metric='haversine').fit(np.radians(coords)) 

Zauważ, że ten specjalnie używa scikit-learn v0.15, jak niektóre wcześniejsze/późniejsze wersje wydają się wymagać pełnego dystansu macierz, która ma być obliczona, która bardzo szybko wysadza twoją pamięć RAM. Ale jeśli używasz Anaconda, można szybko skonfigurować to z:

conda install scikit-learn=0.15 

też tworzyć czyste środowisko wirtualne dla tego zadania grupowania:

conda create -n clusterenv python=3.4 scikit-learn=0.15 matplotlib pandas jupyter 
activate clusterenv