Clustering using histograms

I need to find clusters in a very large amount of data (>2M data points), and I was looking for ways to speed up the usual algorithms, i.e. k-Means, DBSCAN, ...

Is there any major issue, especially regarding statistical significance, to run the algorithms on a histogram, where sparse bins have been filtered out, instead of the real data? What I mean is to create a histogram and throw away all bins with a count below a specific threshold, and run a clustering algorithm on the resulting data points.

Obviously, I will get some uncertainty and data loss, as well as the problem of choosing further parameters, such as the bin size. But the data set I have has a few very dense regions that I am interested in and the rest is very sparse.

2 Answers

I have been wondering the same thing. My conclusion is that doing what you propose is valid for say establishing cluster centres but the challenge is that those change as you vary bin width. An interesting exercise is to take your data and produce a series of histograms changing (say linearly) the bin width for each histogram. As width diminishes the number of data points per bin decreases. That means you get increasingly 'spiky' histograms possibly reaching a point where each bin has one data point. The question you are faced with is 'what bin size produces the most correct spikes for the data'. Downsampling is a more robust way to go.

For either method there have been many papers written on exact and approximate techniques to speed them up. Now 2M is not that much - a good index accelerated implementation should handle this in a few minutes.

For k-means there are methods that can even guarantee you approximate the result to a certain quality. For DBSCAN there are grid-based approaches that try to detect cells that cannot contain core points or where all points must be core points to speed up the process. That usually only works for Minkowski Norma and in low dimensional space, though.

But what about just downsampling your data? Few people know what to do afterwards anyway with the full data... So just pick 20k or 200k points and cluster these. Try using this result first before even bothering to cluster all your data.