6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ DBSCAN is finding connected components. Objects in images tend to be connected and not necessarily sphere like, so DBSCAN is good for them. $\endgroup$ – DaL Feb 3 '16 at 7:48
7
$\begingroup$

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

Seattle Crime data clustered with k-means

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

Seattle Crime data clustered with DBSCAN

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!

$\endgroup$
  • $\begingroup$ Very good answer! +1! Not part of the original Q, but what crime data source was used and what lib did you use for the mapping? This is really well done! $\endgroup$ – ZAR Aug 2 at 19:00
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think the point of the question was to ask about a real-life data set that exhibits properties under which dbscan is likely to work well. I fully agree with you observations but it does not seem to solve the problem. $\endgroup$ – Shagun Sodhani Feb 3 '16 at 16:30
  • $\begingroup$ @Shagun see that last case study example. K-means probably won't work well on that data because of the noise. $\endgroup$ – Anony-Mousse Feb 3 '16 at 17:54
  • $\begingroup$ I agree that astronomical dataset could be a good fit for dbscan but could you please add say the link to one such dataset? Your answer is definitely correct though. $\endgroup$ – Shagun Sodhani Feb 3 '16 at 18:00
  • 1
    $\begingroup$ Try this: skyserver.sdss.org/dr12/en/help/download/downloadhome.aspx maybe this is interesting data. $\endgroup$ – Anony-Mousse Feb 6 '16 at 21:44
  • $\begingroup$ Thanks @Anony-Mousse. Add it to your original answer itself :) $\endgroup$ – Shagun Sodhani Feb 7 '16 at 4:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.