0
$\begingroup$

I am trying to write my own k-means and k-medoids clustering algorithms. I understand the general idea: given k centroids, one continually updates the centroids such that the distance between the points and centroids is minimized; these distances can be euclidean, manhattan, etc. The centroids are members of the original dataset in the case of k-medoids, unlike k-means.

So say the algorithm is computing data-centroid distances before updating the centroids and repeating this process. Suppose there are two or more potential centroids for which the minimized distances are equal. Is there a criteria or general rule to pick which centroid to update?

This question is also posed here; the answer suggests using the originally assigned centroid to avoid infinite loops. This appears to me to be a reason based on programming errors as opposed to the actual method.

Improve this question
$\endgroup$
3
  • $\begingroup$ when things are truly equal it means any choice is equally valid, so you need a break-the-loop metric, which is the point of the linked answer. Without some very clear guidance on what an equality situation looks like and what the impact of the outcomes may be it is hard to go beyond the linked answer. $\endgroup$
    – ReneBt
    Commented Apr 24, 2019 at 8:24
  • $\begingroup$ My question was more about the “math” aspect than the code; I would prefer a correct yet difficult implementation over a not-as-correct yet easy implementation. I suppose I should I provide an example in which multiple equidistant centroids potentially correspond to a particular group of data points, but a single example could bias the method of selecting a single centroid from these centroids, and I do not know enough about all the potential cases. I was hoping there was a secondary metric I could apply for such a case. $\endgroup$
    – user223366
    Commented Apr 24, 2019 at 9:42
  • $\begingroup$ If things are not truly equal then yes there will be other metrics, but if they are truly equal there won't be.What it boils down to is whether the decision has any consequence that you can measure. If it does, measure it and make decisions based on that. If it doesn't then an arbitrary tie-break rule will choose one, breaking infinite loops but have no measureable impact on your outcome. $\endgroup$
    – ReneBt
    Commented Apr 24, 2019 at 14:14

1 Answer 1

Reset to default
1
$\begingroup$

Ties (exact same distances) are not programming errors.

You could break them with a random generator, but that could cause an infinite loop in theory (or at least some extra iterations).

Or you just don't change anything in such cases, then you are fine.

Another option would be to always assign to the "first" cluster, which should also be stable.

It does not really make a difference as long as you make a deterministic decision.

Beware that the k-means style approach for k-medoids works quite poor.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I meant that the handling the equidistant points could lead to infinite loops but are errors themselves, sorry if that wasn't clear. Given that the pre-updated positions of the centroids affect the post-updated centroid positions, why does it "not really make a difference"? $\endgroup$
    – user223366
    Commented Apr 24, 2019 at 6:31
  • $\begingroup$ Are not* errors $\endgroup$
    – user223366
    Commented Apr 24, 2019 at 7:29
  • $\begingroup$ As long as you can guarantee convergence it's fine. The usual proof requires that you'll never cycle through the same state. $\endgroup$
    – Has QUIT--Anony-Mousse
    Commented Apr 24, 2019 at 16:26

Your Answer

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