Why is k correlated with the mean and variance of the distance between centroids in k-means?

Question

I've noticed that if I'm doing k-means clustering (in MATLAB) on basically any set of data (not randomness), the mean and variance in centroid linkage distance appears to always be approximately proportional to k.

The centroid linkage distance is the distance between two cluster centroids. So there are $\frac{k(k-1)}{2}$ distances in total.

Does k always correlate with the centroid linkage distance mean and variance? If so, why exactly is this true? For example, is it to do with the fact that k-means separates data into veronoi cells? Is it the convexity of those cells that necessitates this scaling?

If this scaling doesn't always happen, in what cases does it fail?

Answer 1

The inter-cluster variance is more likely proportional to k-1, on uniform random data, i.e., when k-means does not give useful results. Pay attention to the result quality - arguing about bad results is quite useless, isn't it?

Selecting a subset of k-means based on this measure is a pretty ignorant idea, as you then would need to reassign the unassigned points to other clusters again; and that result will be much worse than running k-means with a smaller k.

Inter-cluster variance of k-means is interesting because the total variance is the sum of intra-cluster and inter-cluster variance. But if you remove some cluster centers, the intra-cluster variance grows a lot.

It's roughly proportional to k-1, because k=1 has 0 inter-cluster variance, you roughly split the data k-1 times when creating k clusters. All these arguments require uniform data though. That is a key idea of the VRC measure that can be used as heuristic to choose k: if the variance changes proportionally to k-1, then the results are as bad as random; but a change that is much better than this suggests a good value of k.