What does it mean to apply k-means algorithm on transformed distance matrix?

Question

I am reading a very good (recent) publication in clustering: Kiselev et al., 2017, SC3 - consensus clustering of single-cell RNA-Seq data (if you don't have access, see author PDF).

The algorithm framework works as follows:

1. Compute distance matrix (Euclidean, Pearson, Spearman) on samples x features matrix.
   
2. Apply feature transformation (PCA, Laplacian) on the distance matrix (samples x samples).
   
3. Apply K-means algorithms on the transformed distance matrix in step 2.
   
4. ....
   

It seems to me that they did in the "wrong" order. In my mind, I will do feature transformation first, followed by computation of distance matrix and then do clustering. But I think they have an justification but I couldn't find it in their paper. Could anyone explain why it works?

Answer 1

K-means shouldn't be applied to a distance matrix at all.

It is meant to compute means in the original data.

There is kernel k-means, but it works differently, and requires a proper kernel to work.

If you apply k-means on the distance matrix, you cluster the distances, not the data. This causes some odd double-weighting of the number of points: if you have n copies of the same point, it also gets n colums in the distance matrix, so it's effect increases there also. So this boosts effects of dense clusters in a very non-intuitive way. The results will often be reasonable (so you don't easily notice this), but the semantics of these results are very non-intuitive, and not satisfy any useful quality criterion. It also is much slower: at least O(n²).

Adding a PCA or other dimension reduction step inbetween certainly does not make the results more valid, on the contrary. PCA will reweight the factors, so in the end you have pretty much no idea what the clustering minimizes. No, I don't think this is a very good paper: The analysis methodology is completely broken.