Github user srowen commented on the issue:
    @sethah I agree that when there are lots of unique points (>> k) then this 
is almost certain to not happen, and that's most real-world use cases, but the 
question indeed is what should happen when this is not the case. In that sense, 
this change only affects corner cases so isn't really a big deal either way.
    Yes the one case is clear: sampling with replacement when the data set has 
< k (unique) points. It will always return k centroids, so must return 
duplicates. In this case, every point will be at distance 0 from some centroid 
and so I don't think the centroids can move apart. It stops in 1 iteration with 
the degenerate solution, with some centroids assigned 0 points. Not the end of 
the world but not exactly meaningful.
    The more interesting case is k-means ||. Of course, again, if there are < k 
unique points to start, in this case as well, returning k centroids means 
returning duplicates. Same argument there -- seems to be no value in returning 
k centroids.
    This is really the sum of the argument to me, regardless of what Derrick's 
case is.
    A twist: it's possible, but quite improbable, for k-means || to choose 
fewer than k unique centroids, when there are >= k distinct points. This is 
most likely when there are barely more than k distinct points. In that case 
it's possible that duplicated centroids do get pulled apart and do end up doing 
something meaningful. I am arguing this case is not worth dealing with because 
it's rare and it doesn't meaningfully harm the quality of the resulting 
clustering, but, that point is arguable.
    I am about 7/10 in favor of the change, certainly the bit about sampling 
without replacement, but the rest I could drop if there's any significant 
objection to it.

If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at or file a JIRA ticket
with INFRA.

To unsubscribe, e-mail:
For additional commands, e-mail:

Reply via email to