why K-means Algorithm will terminate in a finite number of iterations? I am trying to prove that the K-means algorithm will terminate in a finite number of iterations. But I got stuck on how to get start... and why, intuitively, it will terminate in a finite step?
Any suggestions will be really welcome!
 A: There are ultimately only a finite number of cluster assignments, so if the algorithm ran on forever, you would end up passing through a given assignment more than once. This is impossible because any reasonable K-means algorithm will strictly reduce the error on each step, so you could not possibly come back to the same assignment.
A: Under K means there are optimization algorithms running. The optimization is trying to reduce the value of the loss function. In K means setting, the loss function is sum of the squared distance between data and cluster center.
However, no matter what loss function is, you need to run algorithm to optimize it or reduce the loss. So, your question can be viewed as what is the termination condition in an optimization.
There are many criteria can be used. First one would be the solution does not change, and the second one can be "I spend enough time /iteration on it". and Just want to stop. Although I can further improve the solution.
For example, in a toy optimization setting, suppose your objective function (want to minimize) is $y=x^2$. And your algorithm is really slow. After 1000 iterations and one hour, you have $x=0.01$ and $y=0.0001$. You can stop there to say, I am good enough, and do not want to waste my time on fine running. 
On the other hand, it is possible your algorithm is fast, and get $x=0$ very fast, and the algorithm can discover, there is no way to improve the answer, so the algorithm stop.
To summarize, K means is just one type of optimization and it stops in finite number because in some real completed data finding a solution would take a very long time (possible for days or years), so the tool you are using will automatically stop after a while.
