1
$\begingroup$

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!

$\endgroup$

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ finite number of cluster assignments, but exponential number!. Say if you have 100 data points, 10 clusters, then you have 100^10 possible configurations. $\endgroup$
    – Haitao Du
    Commented Jun 24, 2016 at 23:50
  • $\begingroup$ @hxd1011: I don't understand your point. That's still a finite number hence any reasonable algorithm should terminate because you will have to encounter the same state twice at some point, which means your error necessarily went up at some point. Any reasonable $K$ means algorithm won't actually go through all those configurations and will get stuck in a local minema. $\endgroup$
    – Alex R.
    Commented Jun 25, 2016 at 0:09
  • $\begingroup$ My point would be the space is too large, that in practice, an algorithm will not encounter same state multiple times. It is like the chance of collision in Hash. I think your point (reasonable K means wont go though all configurations is the point) $\endgroup$
    – Haitao Du
    Commented Jun 25, 2016 at 0:13
  • $\begingroup$ @hxd1011: it absolutely can encounter the same state twice, depending on the implementation. For example, you could run $K$ means in a single batch by attempting to reassign a random single point to a randomly chosen cluster and accepting the assignment if it results in lower error. In a local minimum (when verifying you are indeed in a local minimum), you will try to assign the the point to the cluster it was previously in (i.e. the prior step). $\endgroup$
    – Alex R.
    Commented Jun 25, 2016 at 0:19
  • $\begingroup$ I know you are right. My point was that I would not say, there are "finite number of configurations", because although it is finite but the number is too large, can be viewed as infinite number with current computation power. Instead I would emphasize what is converge, and why it will converge as you mentioned. $\endgroup$
    – Haitao Du
    Commented Jun 25, 2016 at 0:26
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.