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?


1 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.

  • $\begingroup$ To avoid misunderstandings and presumptions, I've edited the question. $\endgroup$
    – Jonathan
    Oct 30, 2019 at 8:46
  • $\begingroup$ As far as I can tell - your question doesn't discuss what exactly you use as "centroid distance", there is some ambiguity involved - the answer will still be the same: because the total sum of distances decomposes into intra and inter cluster distances, and dividing into k parts reduces by approximately k. A deviation from this trend can only be expected if you have a very good solution for k but not for k-1. Then there will be one k that is special, the others will still follow this trend. $\endgroup$ Oct 30, 2019 at 20:56

Your Answer

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

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