Many papers suggest doing clustering not on the (n x p)raw data but on the n x n or p x p matrices computed according to determined similarity measures (eg, correlation, cosine, point mutual information, etc).

This is useful for sparse data, and personally, I find it also useful to switch categorical data in continuous one that works way better with classic clustering methods.

My problem is the interpretation though: doing the clustering on the n x p, n x n, p x p matrices will give you different results. Especially the differences in clustering between the n x p and n x n are hard to explain.

I would say that:

  • clusters on n x p (along n) identify groups of observations (n) that tend in having similar values in their p features.
  • clusters on n x n identify observations that have similar similarity patterns to other observations (tricky!).
  • clusters on p x p identify features that have similar similarity patterns to other features (even more tricky!).

I can write these things up, but I'm not sure I'm grasping the deep meaning and implications of the differences.


1 Answer 1


I disagree with the premise that "many papers suggest" doing this.

Occasionally I've seen people misuse methods this way (in particular using k-means on distance matrixes), usually because of a lack of understanding or training... A misuse caused by three factors:

  1. Some methods work on n x n distance matrixes derived from feature matrixes. This is perfectly reasonable. But note that these don't compute the distances of entire rows of such matrixes again.
  2. K-means expects n x p numeric data matrixes. But it won't fail when given an n x n matrix, obviously. And if your data isn't numeric, the correct input does not work (correctly), but the bad input does...
  3. Lack of type safety in commonly used tools such as R and python that fail to emit a warning "k-means expects the raw data, not a distance matrix".

Anyway, now to understanding k-means on the n x n distance matrix. This has some really weird semantics. Because adding points to the original data now adds variables to this matrix, and hence clusters with more points have more weight in the resulting matrix. IMHO it does not make a whole lot of sense to have changes to one cluster affect the distances of points in other clusters... Consider a data set with three clusters. When you remove one of them and re-cluster the other two, you'd expect to find the same clustering again. But now you won't, because the distances changed.

The semantics are weird because they are not based on the values, only on the distances. Consider the 1 dimensional data set that contains 10000 times the point 0 (or anything close to 0) and then once the point -100 and +100. Because of symmetry to the 10000 central points, these two outliers are suddenly similar - they have the same distance to all points except each other.

  • $\begingroup$ Thank you. I didn't think about the implications of adding data points to the n x n matrix. I totally agree. But, for the sake of discussing, the fact that having more n increases the number of clusters, is not a signal of a finer resolution that can be achieved once you have more data? Actually I'm working mostly with p x p matrices and with gaussian mixture models, and I'm more interested in the interpretation of that clustering. $\endgroup$
    – Bakaburg
    Commented Jul 15, 2019 at 8:38
  • $\begingroup$ As long as you live in the ideal world where points are uniformly added to all clusters that doesn't matter much... Otherwise there is some weird weighting in the data where big clusters have more influence than small clusters even on the similarity of points far away. $\endgroup$ Commented Jul 16, 2019 at 1:18
  • $\begingroup$ Ok, the description about the pitfalls of the n x n matrices are now clearer to me, especially for instability in case of low n. What about the interpretation of the p x p matrix? $\endgroup$
    – Bakaburg
    Commented Jul 19, 2019 at 7:51
  • $\begingroup$ Distances on the p x p matrix are just equally fcked up. Rather than using the actual variable similarity, you now use a similarity by how similar they are to others. Consider a data set with V1, V2 both independently uniform random. V3 to V100 are highly correlated. When doing kmeans on the p x p matrix, V1 and V2 are suddenly very similar, because they are similarly unrelated to V3 to V100. I don't think "distances on distances" even is a good idea. $\endgroup$ Commented Jul 19, 2019 at 12:45

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.