CODEWITHSUNDEEP
machine-learningk-means
Kevin
Kevin

Reputation: 6831

Can k-means fall into an infinite loop ?

I've studied the k-means algorithm and I know how it works.

Just curious,is there any situation that this algorithm will go into an infinite loop,say if we have some particular bad choices for initial centroid points? I could only imagine a situation k-means will get to local minimum with bad initial choices.

Upvotes: 7

Views: 2323

Answers (2)

eltings
eltings

Reputation: 57

Consider also this answer to the same question. https://stackoverflow.com/a/60312554/15467861

The last edge case: What if more than one minimum state has equal loss? This is a highly unlikely scenario, but can cause issues if and only if the algorithm is coded poorly for tie breakers. Essentially, the only way this can cause a cycle is if a data point has equal distance for two clusters, and is allowed to change clusters away from it's current cluster even on equal distance. Suffice to say, the algorithms are generally coded so that the data points never swap on a tie, or in some other deterministic manner, thus avoiding this scenario entirely.

Upvotes: 0

Jacob
Jacob

Reputation: 34621

No. k-means has an upper bound of O(nkd) in d-dimensional space.

Upvotes: 11

Related Questions