For which real world data sets does DBSCAN surpass K-means.?

Question

For clustering, DBSCAN surpass k-means in terms of handling arbitrary shape data sets. In the most published papers about density based clustering, the experiments are performed with synthetic data sets that have special features (for example, the moon-shaped data sets). Can someone point me to some real world datasets where DBSCAN outperforms K-means.

Answer 1

I play around quite a bit with location data and have found examples both where k-means works fine and where k-means is a poor representation and DBSCAN is a great fit.

If you've ever gone hiking or mountain climbing on a day with fog or a low cloud cover, there are times where you get to the top of the peak and can only see the surrounding peaks poking up through the clouds. I like to use this analogy when I think of DBSCAN. The density filtering allows one to select a threshold where data is kept, and all of the remaining data is filtered out.

Take a look at this Seattle crime incident data. Suppose I want to cluster the data by location to form pseudo neighborhoods i.e. neighborhoods that are roughly defined the the geography of where criminal events tend to occur. This is an example of k-means working just fine in location analytics:

Seattle crime data superimposing a primitive map with k-means clustering

If you know Seattle at all, you can see that the clusters tend to pick out neighborhoods and this works quite well in breaking up neighborhoods. Now suppose I want to pick out the high crime areas of Seattle in order to identify the hot spots. No matter how I adjust k, the k-means clustering doesn't really provide any additional insight. But the density filtering in DBSCAN does a wonderful job of identifying high crime areas:

Seattle crime data superimposing a primitive map with DBSCAN clustering

I think this gives the jest of some strengths that can be exploited using the two algorithms. There's nothing special about the crime data. For what its worth, I have a tutorial that goes through the analytics of identifying a user's home and work locations from their cell phone GPS pings. This is another case where DBSCAN was very useful, but the DBSCAN specific parts a buried a ways down in the tutorial.

Hope this helps!

Answer 2

There is no good evaluation data at all for clustering that would allow such conclusions.

There isn't even good real data where you could say variant 1 of k-means is better than variant 2 of k-means.

There is also no good evaluation measure that would handle the notion of "noise" well either.

So: don't go by some number.

Clustering is about solving a data problem. You have data, you try algorithms and parameters and study (important) the result. Until you find something interesting. This cannot be automated, or measured (well, you could ask 100 scientists on what worked for them - i remember having seen e.g. some astronomy papers that used DBSCAN with success - but of course they can't put a number 0 to 1 on this).

You may want to look e.g. at this Case Study with DBSCAN - I doubt k-means is of much help on this data set. In particular, it will assign the noise points to some cluster, when they should not be assigned at all.