# Does the average distance in K-means have to be monotone decreasing?

I'm implementing the k-means algorithm myself. I don't see any obvious mistake in my code and it seems to work well. However, there's something I don't understand.

My algorithm, working on vectors $x_i \in X$, cetroids $c_j \in C$ and labels $l_i \in L$ looks like:

1. choose centers $C=\{c_1,c_2,...,c_k\}$ from $X_i$ randomly (no repetitions)
2. label each vector with the index of nearest centroid $$l_i = \text{arg}\min_{j \in \{1..k\}}(||x_i-c_j||, c_j \in C)$$
3. find new means of each cluster $$c_j = \text{mean}\{x \in X_i \;\text{and}\; l_i=j\}\;\text{for}\;j=1..k$$
4. if the centroids have moved signifficantly in the previous step, goto 2

A plain vanilla k-means, I guess.

However, when I make a plot of the average of point-to-respective-centroid distances after each iteration, $$\text{mean}\{||x_i-c_j||\;\text{and}\;j=l_i\;\text{for each}\;x_i \in X \},$$ I can see that the mean distance is not monotone decreasing (although in general it is decreasing and converging nicely):

http://i.stack.imgur.com/ySgWf.png (sorry it won't allow me embed the image)

I remember to be told it should be always decreasing, and my intuition is the same. What's wrong? My algorithm (implementation) or my assumption about the mean of distances?

• If the right hand plot in your linked image is the error as a function of iteration then something is wrong. It should be clear that at every step in the K-means algorithm the data points can't get further away from their respective centers. Yours goes down and then back up. Dec 2, 2012 at 22:09
• Two more comments: 1) Is the 4th step in your algorithm simply to check for convergence? 2) You should be looking at the sum of squared distance not the average distances. Dec 2, 2012 at 22:16
• I think I must have a bug then. I wanted to be sure. Thank you for the explanation. Dec 2, 2012 at 22:38
• I think I found the bug. You were right, the cause was really that I was depicting the mean of distances instead of the sum of squares. Now the bug seems to be gone. However, I don't get it, because both should be monotone decreasing, I guess. Perhaps it's the numerical errors introduced due to square root and division and all the rounding involved? Dec 2, 2012 at 23:34
• I'm not sure. And after thinking about this a little more, I think your originally plot could be possible if you were passing through a local minima. Dec 2, 2012 at 23:37

K-means minimizes the total sum of squared deviations. Don't think of it in terms of distances. Yes, you assign objects by their distance. But that distance (squaredEuclidean) is just the sum of 1d squared deviations. So what you really are optimizing is the sum of squared 1d deviations.

The key part however is the mean, and here it is more obvious that this method optimizes based on single dimensions. The arithmetic mean is the minimum least squares estimation, again.

So you really should plot the sum of squared deviations, not the mean of euclidean distances.

Yes: euclidean distances and squared euclidean distances are monotone - for a single object.

Example in one dimension:

Objects at 0 and 2, mean at 0.5:

average distance: (0.5 + 1.5) / 2 = 1

squared deviations: 0.25 + 2.25 = 2.5

Object at 0 and 2, mean at 1:

average distance: (1 + 1) / 2 = 1

squared deviations: 1 + 1 = 2

So the second example is only better wrt. squared deviations, not with linear deviations. In particular, an optimum for the linear deviations isn't necessarily optimal for the squared deviations.

Above example highlights that one shouldn't just plug in arbitrary distances into k-means. It technically is not distance based. It is based on squared deviations in each single dimension, which happen to sum up to the squared euclidean distance, which is monotone with the regular euclidean distance, so it appears as if we are assigning every object to the nearest cluster center, although what we are actually doing is minimize the sum of squared 1d deviations.

• Thank you for the example. That's exactly what I needed. Dec 3, 2012 at 8:39