1
$\begingroup$

Imagine you have $k$ classes. Every class $i$ has points which are follow a probability distribution, such that their distance to 0 is $i$ in mean, but this distance follows a normal distribution. The direction is uniformly distributed. So all classes are in shells around the origin 0.

Can $k$-means get these shells when you choose the "right" distance metric? (Obviously it can't find it if you take the euclidean metric, but I wonder if there is any metric at all or if this problem is inherently unsolvable by $k$-means, even if you know the number of clusters $k$)

Improve this question
$\endgroup$
7
  • $\begingroup$ I'm not sure if "shell" is the right word. Probably "spheres" is better? Google finds for both, "concentric spheres" and "concentric shells" images. $\endgroup$
    – Martin Thoma
    Dec 2, 2015 at 16:17
  • 1
    $\begingroup$ It sounds like you'd do best explicitly calculating the magnitude of each vector and then clustering based on magnitude explicitly. $\endgroup$
    – jamesmf
    Dec 2, 2015 at 16:31
  • $\begingroup$ @jamesmf If I know that my data looks like this, I cluster the integer distance to 0, of course. But that would be "cheating". You can always apply functions to make your data linearly separable. The question is how complicated the data has to get until the algorithm fails. For single layer neural neurons it was XOR, for example. Of course, you could say that the single layer neuron could classify XOR correct if you give it XOR as input, but that is not the point... $\endgroup$
    – Martin Thoma
    Dec 2, 2015 at 22:00
  • 1
    $\begingroup$ I understand your point, I simply meant that choosing an arbitrary distance metric for kmeans was not meaningfully different than explicitly calculating magnitude and using "traditional" distance metrics. $\endgroup$
    – jamesmf
    Dec 2, 2015 at 22:46
  • $\begingroup$ @jamesmf Ah, ok, now I get what you mean. Yes, you're right. I didn't think of that before. However, I'm still happy I've asked the question here, because I could learn something by the answer :-) $\endgroup$
    – Martin Thoma
    Dec 2, 2015 at 22:59

1 Answer 1

Reset to default
2
$\begingroup$

You cannot just use arbitrary distance functions with k-means.

because the algorithm is not based on metric properties but on variance.

https://stats.stackexchange.com/q/81481/7828

Fact is that k-means minimizes the sum of squares. This does not even give you the "smallest distances" but only the smallest squared distances. This is not the same (see: difference between median and mean) - if you want to minimize Euclidean distances, use k-medians or if you want other distances PAM (k-medoids).

You can generalize k-means to use a few more distances known as "Bergman divergences" and you can do some variant of the kernel trick. But that is not very powerful, because you don't have labels for optimizing the kernel parameters! Still, that could be what this exercise question is up to... If your "shells" are indeed centered at 0, then you can transform your data (read: kernel trick done wrong) to angle+distance from origin, and k-means may be able to cluster the projected data (dependent on the not well defined scaling of the axes). Or the textbook did not realize that a kernel k-means has been proposed long ago. Then the argument is probably this: the mean of each shell is 0, and thus the shells cannot be distinguished. This clearly holds for unmodified k-means.

Improve this answer
$\endgroup$
2
  • $\begingroup$ This is not from a textbook. I've asked this question myself. $\endgroup$
    – Martin Thoma
    Dec 2, 2015 at 22:18
  • $\begingroup$ Sorry, I have a really low opinion on clustering chapters of machine learning textbooks... ;-) $\endgroup$
    – Has QUIT--Anony-Mousse
    Dec 2, 2015 at 22:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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