Speicherfehler beim Clustering mit DBSCAN (große Matrixberechnung)

Question

Ich gruppiere Daten mit DBSCAN, um Ausreißer zu entfernen. Die Berechnung ist sehr speicherintensiv, da die Implementierung von DBSCAN in scikit-learn fast 1 GB Daten nicht verarbeiten kann. Das Problem wurde bereits erwähnt here

Der Engpass des folgenden Codes scheint die Matrixberechnung zu sein, die sehr speicherintensiv ist (Größe der Matrix: 10mln x 10mln). Gibt es eine Möglichkeit, die Berechnung von DBSCAN zu optimieren?

Meine kurze Forschung zeigt, dass die Matrix in irgendeiner Weise auf eine spärliche Matrix reduziert werden sollte, um es machbar zu machen.

Meine Ideen, wie dieses Problem zu lösen:

1. erstellen und eine spärliche Matrix
2. berechnen Teile Matrix berechnen und sie in Dateien speichern und kombinieren sie später
3. führen DBSCAN auf kleine Teilmengen von Daten und Zusammenführen der Ergebnisse
4. Umstellung auf Java und verwenden ELKI Werkzeug

Code:

import numpy as np 
import pandas as pd 
import sklearn 
from sklearn.preprocessing import StandardScaler 
from sklearn.cluster import DBSCAN 

# sample data 
speed = np.random.uniform(0,25,1000000) 
power = np.random.uniform(0,3000,1000000) 

# create a dataframe 
data_dict = {'speed': speed, 
      'power': power} 

df = pd.DataFrame(data_dict) 

# convert to matrix 
df = df.as_matrix().astype("float64", copy = False) 

X = data 

# normalize data 
X = StandardScaler().fit_transform(X) 

# precompute matrix of distances 
dist_matrix = sklearn.metrics.pairwise.euclidean_distances(X, X) 

# perform DBSCAN clustering 
db = DBSCAN(eps=0.1, min_samples=60, metric="precomputed", n_jobs=-1).fit(dist_matrix) 

Answer 1

1 bis 3 wird nicht funktionieren.

1. Ihre Daten sind dicht. Es gibt keine "meistens 0", so dass spärliche Formate tatsächlich viel mehr mehr Speicher benötigen. Die genauen Schwellenwerte variieren, aber als Faustregel benötigen Sie mindestens 90% der 0-Werte, damit sparse Formate wirksam werden.

2. DBSCAN verwendet keine Entfernungsmatrix.

3. Arbeiten an Teilen, dann ist das Zusammenführen nicht so einfach (es gibt GriDBSCAN, was dies für euklidische Stärke tut). Sie können nicht einfach zufällige Partitionen nehmen und sie später zusammenführen.