Tips for clustering rows of a gigantic "distance" matrix

Question

I've been assigned to the following task:

I was given 1,000,000 data points and was asked to create a sort of distance matrix and to cluster the rows. So this matrix is 1,000,000 x 1,000,000 which is obviously way to large to fit on my poor 8GB of RAM.

I'd like to ask for some tips of how to handle this kind of data.

I'd like to choose maybe 100,000 data points at random and cluster their distances instead hoping they represent the entirety of the data.. even so this seems like a hard task.

So what kinds of clustering methods could work here? If I can't feed all my data at once to some algorithms which usually can handle lots of data such as hierarchical clustering or DBscan what options do I have left?

Answer 1

Starting with a small random sample is always a good idea, otherwise there would be too much processing without good result.

It depends also of the project's objective project: if the objective is to have an overview of the data, a random sampling of 5%-10% would be enough. You can make several test of random samples to ensure that the percentage is representative enough. If the objective is to have a complete understanding of all data, you should start with a small sample and increase the amount progressively until reaching 100%.

If you have too much processing time, you will want to use multiprocessing, fast calculation libraries, use of ROM or efficient coding.

In both cases, you can start with a small random sample of 2000 elements to compare quickly different clustering algorithms, thanks to their low amount (= little processing time).

Then, if your data has many features, I would recommend dimensional reduction with algorithms like t-SNE (https://www.youtube.com/watch?v=wvsE8jm1GzE) or UMAP (https://www.youtube.com/watch?v=6BPl81wGGP8) to make meaningful clusters. Those clusters could be identified automatically using Kmeans for instance.