scikit-learn DBSCAN memory usage

by

The problem apparently is a non-standard DBSCAN implementation in scikit-learn.

DBSCAN does not need a distance matrix. The algorithm was designed around using a database that can accelerate a regionQuery function, and return the neighbors within the query radius efficiently (a spatial index should support such queries in O(log n)).

The implementation in scikit however, apparently, computes the full O(n^2) distance matrix, which comes at a cost both memory-wise and runtime-wise.

So I see two choices:

  1. You may want to try the DBSCAN implementation in ELKI instead, which when used with an R*-tree index usually is substantially faster than a naive implementation.

  2. Otherwise, you may want to reimplement DBSCAN, as the implementation in scikit apparently isn’t too good. Don’t be scared of that: DBSCAN is really simple to implement yourself. The trickiest part of a good DBSCAN implementation is actually the regionQuery function. If you can get this query fast, DBSCAN will be fast. And you can actually reuse this function for other algorithms, too.

Update: by now, sklearn no longer computes a distance matrix and can, e.g., use a kd-tree index. However, because of “vectorization” it will still precompute the neighbors of every point, so the memory usage of sklearn for large epsilon is O(n²), whereas to my understanding the version in ELKI will only use O(n) memory. So if you run out of memory, choose a smaller epsilon and/or try ELKI.

More Related Contents:

  1. Is it possible to specify your own distance function using scikit-learn K-Means Clustering?
  2. Clustering text documents using scikit-learn kmeans in Python
  3. Clustering values by their proximity in python (machine learning?) [duplicate]
  4. Scikit Learn GridSearchCV without cross validation (unsupervised learning)
  5. Mixing categorial and continuous data in Naive Bayes classifier using scikit-learn
  6. python kmeans on string
  7. Why does the following code cant get value of n_fold = 1?
  8. How to extract the decision rules from scikit-learn decision-tree?
  9. How to one-hot-encode from a pandas column containing a list?
  10. scikit-learn & statsmodels – which R-squared is correct?
  11. ImportError in importing from sklearn: cannot import name check_build
  12. Random state (Pseudo-random number) in Scikit learn
  13. How to one hot encode variant length features?
  14. pandas dataframe columns scaling with sklearn
  15. How do I calculate a word-word co-occurrence matrix with sklearn?
  16. Recovering features names of explained_variance_ratio_ in PCA with sklearn
  17. scikit-learn cross validation, negative values with mean squared error
  18. ROC for multiclass classification
  19. What is exactly sklearn.pipeline.Pipeline?
  20. fit-transform on training data and transform on test data [duplicate]
  21. Model definition does not give any output
  22. How to find the importance of the features for a logistic regression model?
  23. scikit-learn random state in splitting dataset
  24. How to use sklearn fit_transform with pandas and return dataframe instead of numpy array?
  25. What are the different use cases of joblib versus pickle?
  26. confused about random_state in decision tree of scikit learn
  27. Does GridSearchCV perform cross-validation?
  28. Can I send callbacks to a KerasClassifier?
  29. How to get most informative features for scikit-learn classifier for different class?
  30. ImportError: No module named sklearn.cross_validation

Leave a Comment