How to implement density-based clustering?

Question

I’m looking to implement density-based clustering with R or Mathematica on a giant file (600,000 points on a 3 billion x 3 billion plane). Is DBSCAN the right method for data that is this sparse? I am also anticipating a huge amount of noise. Which parameters would I tweak to account for this?

Answer 1

Given you have a large dataset data as well as noisy data I strongly recommend that a dimensional reduction step is done prior to clustering. This should allow potentially irrelevant variation to be filtered out and the clustering algorithm to work in a lower dimensional space. Standard dimensional reduction techniques like Principal Component Analysis (PCA) and Locality-sensitive hashing (LSH) are two standard approaches.

Detecting density-based clusters in high-dimensional spaces, even when having noiseless data can be very demanding. High-dimensional density estimation is a typical scenario where the curse of dimensionality manifests. DBSCAN ultimately relies on finding fixed-radius nearest neighbours for each point. As the dimensionality of the data increases this nearest neighbour (NN) finding task becomes more and more attenuated. In addition (and most importantly) a standard distance metric as Euclidean distance gets potentially increasingly irrelevant. Therefore even if we have a distance and neighbourhood to work with that information is not very useful. This association between curse of dimensionality and NN-related tasks has been touched upon many time in CV, eg. see 1, 2, 3, 4.

By the way, something "simple" like the following script where $N$ is quite larger than just 600$k$ as in your case, runs on my laptop (Intel i5 U-series) in under 5 minutes using ~10 GB of RAM. This is because the fixed-radius nearest neighbour problem mentioned above is solved within the library dbscan using $k$-d trees; most NN-finding routines use some approximation approach; otherwise even cases with just a few more than tenths of thousands of points would get prohibitively large to work with when involving $O(n^2)$ requirements. So while not "instant" a use-case with 600$k$ points is definitely doable in R given a standard workstation and some appropriate dimensional reduction.

N = 10^7; p = 50;
Q = matrix(nrow = N, rt(N*p, df = 2))
library(dbscan)
W = dbscan(Q, eps= 0.01, minPts = 100) # About 4.5'

Answer 2

DBSCAN will work, but you need a good index structure. Without a good index, it will be $O(n^2)$ which is too expensive.

If you have a lot of noise, increase minPts.