2

I have a theoretical problem, I think it is easier to show it instead of talking about it:

enter image description here

So by visual examination we got 2 clusters, which k-means does not necessarily get, because some points on the edge of the bigger cluster are closer to the center of the smaller cluster than to the center of the bigger one. A possible solution would be to move closer to the second cluster with the centroid of the first cluster. I am not sure whether k-means does this (probably not), but if we have multiple small clusters around the big one, this does not help either. How could we modify the k-means to overcome this? Are there clustering algorithms, which don't have this weakness?

ttnphns
  • 51,648
  • 40
  • 253
  • 462
inf3rno
  • 161
  • 8
  • @ttnphns I have not a clue how to modify k-means to overcome this problem (probably there are many different ways to do that). If you think your proposition with rings is a possible solution, then it is just as good answer as the other, which recommends density based clustering instead. – inf3rno Mar 27 '18 at 08:58
  • Did you even read just the Wikipedia article? Or a clustering book? There is so much more than kmeans. – Has QUIT--Anony-Mousse Mar 28 '18 at 07:34
  • @Anony-Mousse I liked to learn k-means, because I watched a video about it, and it was very easy to understand what it does. On the other hand wikipedia is full of mathematical formulas usually without any good explanation, so for a beginner it is close to impossible to learn statistics/clustering from there. I bought some statistics books, but I haven't had the time to read them yet. – inf3rno Mar 28 '18 at 09:41

1 Answers1

3

Your example looks like a textbook case where density based clustering works better. Such algorithms look for regions of high density and cluster those. The possibly best-known such algorithm is DBSCAN. We also have a tag . With decent parameterization, DBSCAN should be able to detect your two clusters.

You may also be interested in How to understand the drawbacks of K-means.

Stephan Kolassa
  • 95,027
  • 13
  • 197
  • 357
  • 1
    GMM should also work fine on above toy example, because the clusters are spherical. But yes, except for the cluster shape it is pretty much the motivational example of density based clustering... – Has QUIT--Anony-Mousse Mar 28 '18 at 07:32
  • Thanks for the link! So according to it, you have to find the right assumptions before applying any clustering algorithm otherwise the result will be a disaster. – inf3rno Mar 29 '18 at 13:22