Cycling in k-means algorithm According to wiki the most widely used convergence criterion is "assigment hasn't changed". I was wondering whether cycling can occur if we use such convergence criterion? I'd be pleased if anyone pointed a reference to an article that gives an example of cycling or proves that this is impossible.
 A: This paper appears to prove convergence in a finite number of steps.
A: The $k$-means objective function strictly decreases with each change of assignment, which automatically implies convergence without cycling. Moreover, the partitions produced in each step of $k$-means satisfy a "Voronoi property" in that each point is always assigned to its nearest center. This implies an upper bound on the total number of possible partitions, which yields a finite upper bound on the termination time for $k$-means. 
A: In finite precision, cycling may appear.
Cycling is frequent in single precision, exceptional in double precision.
When close to a local minimum, the objective function may sometimes slightly increase due to round-off errors. This is often innocuous as the algorithm function decreases again and eventually reaches a local minimum. But occasionally, the algorithm steps on a previously visited assignment, and start cycling.
It is easy and safe to watch for cycles in real-world stopping criteria implementations.
