1
$\begingroup$

I'm wondering how k-means deals with randomly initializing two centers (for two distinct observations x_1 and x_2, but with the same spatial localization) that are at the same point? I'm planning to cluster a bunch of observations I have, but I would ideally like to keep observations that have the same spatial localization in the same cluster. In the picture the two points at the bottom could have been randomly assigned to be two centers. enter image description here

I've seen a similar answer asked here: In k-means, can two initial random centeroids be same?, but I'm wondering more how k-means handles situations like this algorithmically.

Some background in sklearn: As I understand it, in python you can initialize your data using a random initialization, whereupon I don't think there is any restraint on different centers being in the same point, and also there is the kmeans++ initialization, where my question does not apply, because kmeans++ finds centers "spread apart".

$\endgroup$
1
$\begingroup$

Quoting the R documentation for kmeans

 centers: either the number of clusters, say k, or a set of initial
          (distinct) cluster centres.  If a number, a random set of
          (distinct) rows in ‘x’ is chosen as the initial centres.

If I read this correctly, if two observations are perfectly overlapping they cannot be two centers because the algorithm needs distinct rows.

If, instead, they are nearly overlapping, they should be handled like any other observation. In this case, the documentation reads:

In rare cases, when some of the points (rows of ‘x’) are extremely close, the
algorithm may not converge in the “Quick-Transfer” stage, signalling a warning
(and returning ‘ifault = 4’).  Slight rounding of the data may be advisable in
that case.

I suppose other implementation of kmeans follow the same logic?

$\endgroup$
3
  • $\begingroup$ thank you for your answer! I don't think kmeans in sklearn is implemented the same way, but I didn't specify I was thinking about python, so that is my bad. In python you can initialize your data using a random initialization, whereupon I don't think there is any distinct involved, and also the kmeans++ initialization, where my question does not apply, because kmeans++ finds centers "spread apart". $\endgroup$
    – Erosennin
    May 4 '21 at 8:32
  • 1
    $\begingroup$ @Erosennin - I see - If you are after a practical answer, I would imagine sklearn does "the right thing" if two random points overlap since that doesn't seem to be an esoteric scenario. (Not the most scientific comment...) $\endgroup$
    – dariober
    May 4 '21 at 8:47
  • $\begingroup$ I'm interested in the practical answer as well, but most in how the algorithm works. From your explanation it seems to me that in R two distinct rows removes this problem (if distinct is indeed distinct coordinates), hence you've basically answered my question from an R perspective. $\endgroup$
    – Erosennin
    May 4 '21 at 9:29

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.