Did you ever see a Professional Golf Association (PGA) championship where the players stop when their ball gets within 2 feet of the hole? How about a 100m race where they decide who has won at 98 metres? Or the concert conductor who stops his orchestra 20 bars from the end of the score? These may be somewhat absurd analogues, but they do accurately reflect the way many "naïve" k-means programs work - they stop when they get within 2% of their "goal", and their "goal" is not even a criterion function to be minimized. For example, here is the "convergence" criterion for one widely available k-means program (see if you can guess the product from the syntax): Now, ask yourself why should this test be necessary .... it's because they won't necessarily converge Standard software packages have in fact been running "naïve k-means" for decades, and they don't actually optimize anything. A case i is moved from a cluster p to another cluster q if d the move has occurred.afterAs we have explained elsewhere, the naïve test can actually result in an increase in the Euclidean Sum of Square or trace ( How did we discover this simple fact? We programmed naïve k-means and were puzzled when it failed to converge with large data sets. Then we checked the changes in E after each iteration and found that E was actually increasing at the end of some iterations. Furthermore, we noticed that in some iterations there were small numbers of cases being relocated, whereas in later iterations the number of moves were larger. So, stopping the procedure when the changes in the means has become small does not necessarily mean that the reported solution is anywhere near an optimum value for E. These programs simply hand you an arbitrary classification and say "here's a result, it's not optimum but it's the best we can do"! Returning to our opening analogy, we never discover who actually won the 100m sprint because the race stopped at 98m. Try that at the next Olympic Games. It also means that, unlike our implementation of k-means, they cannot count the frequency of each final cluster solution to test it's reproducibility because they never finally converge. You can read our most recent white paper on this, presented at the ISA in August 2004, here (pdf file). To find out more and test exact k-means with your data, |