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.
$\begingroup$
$\endgroup$
1
asked Apr 27, 2011 at 11:13
-
2$\begingroup$ Let me emphasize (since this overlooked often) that the convergence proofs need (squared) euclidean distance, so that the distance function and the mean function optimize the same criterion. If you use a different distance (actually, you should not use a distance, but "least sum of squares") you may lose convergence in k-means. $\endgroup$– Has QUIT--Anony-MousseCommented Mar 18, 2013 at 7:51
Add a comment
|
3 Answers
1
-
1$\begingroup$ Exactly what I was looking for! $\endgroup$ Commented Apr 27, 2011 at 16:51
$\begingroup$
$\endgroup$
2
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.
answered Apr 27, 2011 at 16:44
-
$\begingroup$ Thanks, it's intuitive that objective function decreases, but I wasn't sure that it decreases strictly. I wanted to make sure that there is no patological case just like in linear programming $\endgroup$ Commented Apr 27, 2011 at 16:55
-
$\begingroup$ Well yes and no. While it converges, it can take exponential time, much as how simplex does. Moreover, for both problems, you can show that "smoothed" variants converge in polynomial time $\endgroup$ Commented Apr 27, 2011 at 19:26
$\begingroup$
$\endgroup$
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.
