In K means Clustering, suppose, if there exists equal euclidean distance of a data point to all of its k cluster centers, which cluster the data point will choose to become its member? Is there any literature proof supporting it?

  • 1
    $\begingroup$ You can just assign your data-point to one cluster centers (random choice), and continue to use K-means until convergence. However, if this is a new data-point that you want to consider after the convergence of your algorithm, and this data-point have "almost" the same distance to all cluster centers, then you may consider creating a new cluster having this data-point as a center. $\endgroup$ – shn Dec 18 '12 at 23:18

Actually, $k$-means does not use Euclidean distance.

It assignes object so that the sum of squared deviations (across all dimensions) is minimized by this assignment. Let $X$ are the observation and $C$ are the current cluster centers, the objective is:

$$\sum_{x\in X} \min_{c\in C} \sum_{i=1}^d \left|x_i - c_i\right|^2$$

which is a trivial rearrangement of the sum of in-cluster-variances. Note that the part inside the $\min$ coincides with the squared euclidean distance formula, which in turn is monotone to Euclidean distance. So the interpretation that $k$-means assigns objects to the closes center is absolutely correct. It is just that $k$-means does not care about the distance itself, it tries to minimize the sum of variances.

If there is a tie, i.e. there are two cluster centers $c\in C$ an object can be assigned to that have the same variance, any of them can be chosen, as both minimize the objetive function. $k$-means is usually used randomized anyway, this little bit of indetermism does not change much.

In practise, you will see very different behaviour:

  • some implementations may prefer the "first best"
  • some implementations may prefer the "last best"
  • some implementations may prefer to keep the previous assignment, if possible, in the hope to converge faster this way
  • some implementations may prefer to reassign, in the hope to find better solutions this way

I don't think there is a clear reason to prefer one over the other. It is mostly for technical reasons that it is implemented one way or another. For the mathematical objective of minimizing variance, it clearly does not matter.

| cite | improve this answer | |
  • $\begingroup$ I don't understand clearly, what is "first best" and "last best"? And Is there any literature or some kind of proofs, to explain these behaviours.? $\endgroup$ – user16073 Dec 17 '12 at 4:26
  • $\begingroup$ Well, the first result that is optimal, and the last result that is optimal. There is no literature or proofs for the way things tie handling is implemented technically. Mathematically they are all optimal and thus correct. $\endgroup$ – Has QUIT--Anony-Mousse Dec 17 '12 at 7:13
  • $\begingroup$ For what exactly do you want a proof? Your question is quite imprecise, somewhat like asking for a proof that even numbers are more even than odd numbers. $\endgroup$ – Has QUIT--Anony-Mousse Dec 17 '12 at 7:14

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.