In scikit-learn, can DBSCAN use sparse matrix?

Question

I got Memory Error when I was running dbscan algorithm of scikit. My data is about 20000*10000, it's a binary matrix.

(Maybe it's not suitable to use DBSCAN with such a matrix. I'm a beginner of machine learning. I just want to find a cluster method which don't need an initial cluster number)

Anyway I found sparse matrix and feature extraction of scikit.

http://scikit-learn.org/dev/modules/feature_extraction.html http://docs.scipy.org/doc/scipy/reference/sparse.html

But I still have no idea how to use it. In DBSCAN's specification, there is no indication about using sparse matrix. Is it not allowed?

If anyone knows how to use sparse matrix in DBSCAN, please tell me. Or you can tell me a more suitable cluster method.

Possible duplicate of scikit-learn DBSCAN memory usage

Nikana Reklawyks
– Nikana Reklawyks

2017-01-17 03:56:28 +00:00
Commented Jan 17, 2017 at 3:56 — Nikana Reklawyks
– Nikana Reklawyks, Commented Jan 17, 2017 at 3:56

Has QUIT--Anony-Mousse · Accepted Answer · 2016-01-06 20:59:27Z

8

The scikit implementation of DBSCAN is, unfortunately, very naive. It needs to be rewritten to take indexing (ball trees etc.) into account.

As of now, it will apparently insist of computing a complete distance matrix, which wastes a lot of memory.

May I suggest that you just reimplement DBSCAN yourself. It's fairly easy, there exists good pseudocode e.g. on Wikipedia and in the original publication. It should be just a few lines, and you can then easily take benefit of your data representation. E.g. if you already have a similarity graph in a sparse representation, it's usually fairly trivial to do a "range query" (i.e. use only the edges that satisfy your distance threshold)

Here is a issue in scikit-learn github where they talk about improving the implementation. A user reports his version using the ball-tree is 50x faster (which doesn't surprise me, I've seen similar speedups with indexes before - it will likely become more pronounced when further increasing the data set size).

Update: the DBSCAN version in scikit-learn has received substantial improvements since this answer was written.

edited Jan 6, 2016 at 20:59

answered May 25, 2013 at 12:36

Has QUIT--Anony-Mousse

77.8k14 gold badges146 silver badges198 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Fred Foo Over a year ago

You might be interested in scikit-learn 0.14, where DBSCAN was indeed modified to use ball trees.

titus Over a year ago

also DBSCAN now supports sparse input in v0.16

Fred Foo · Accepted Answer · 2013-04-19 12:56:43Z

1

You can pass a distance matrix to DBSCAN, so assuming X is your sample matrix, the following should work:

from sklearn.metrics.pairwise import euclidean_distances

D = euclidean_distances(X, X)
db = DBSCAN(metric="precomputed").fit(D)

However, the matrix D will be even larger than X: n_samples² entries. With sparse matrices, k-means is probably the best option.

(DBSCAN may seem attractive because it doesn't need a pre-determined number of clusters, but it trades that for two parameters that you have to tune. It's mostly applicable in settings where the samples are points in space and you know how close you want those points to be to be in the same cluster, or when you have a black box distance metric that scikit-learn doesn't support.)

answered Apr 19, 2013 at 12:56

Fred Foo

365k80 gold badges765 silver badges852 bronze badges

2 Comments

Has QUIT--Anony-Mousse Over a year ago

DBSCAN doesn't require the distance matrix, that is a limitation of the current sklearn implementation, not of the algorithm. Plus, in many cases, both the epsion and the minpts parameter of DBSCAN can be chosen much easier than k. When using geographic data for example, a user may well be able to say that a radius of "1 km" is a good epsilon, and that there should be at least 10 events within this radius.

Fred Foo Over a year ago

@Anony-Mousse: I'm aware that the problems are in the implementation, not the algorithm. As for picking eps and minpts, yes, for some problems that may be easy, but for others, extensive tuning may be required. Not all problems live in Euclidean space or even on the surface of the earth.

K.-Michael Aye · Accepted Answer · 2016-08-18 13:02:13Z

1

Yes, since version 0.16.1. Here's a commit for a test:

https://github.com/scikit-learn/scikit-learn/commit/494b8e574337e510bcb6fd0c941e390371ef1879

answered Aug 18, 2016 at 13:02

K.-Michael Aye

5,6357 gold badges46 silver badges58 bronze badges

Comments

Has QUIT--Anony-Mousse · Accepted Answer · 2013-05-25 12:36:59Z

0

Sklearn's DBSCAN algorithm doesn't take sparse arrays. However, KMeans and Spectral clustering do, you can try these. More on sklearns clustering methods: http://scikit-learn.org/stable/modules/clustering.html

edited May 25, 2013 at 12:36

Has QUIT--Anony-Mousse

77.8k14 gold badges146 silver badges198 bronze badges

answered Apr 19, 2013 at 6:57

Ando Saabas

1,99715 silver badges12 bronze badges

Collectives™ on Stack Overflow

In scikit-learn, can DBSCAN use sparse matrix?

4 Answers 4

2 Comments

2 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related