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?

enter image description here

  • 2
    $\begingroup$ +1. You won't believe how much shoddy crap is published in scRNA-seq bioinformatics these days, including top journals in the field. Not saying that this paper is that, but if you see a Nature Methods or a Genome Biology paper with some new computational method, please do not assume it's any good. $\endgroup$ – amoeba says Reinstate Monica Nov 13 '18 at 9:27
  • $\begingroup$ stats.stackexchange.com/a/81494 says that it is possible to code k-means so that it properly processes the euclidean distance matrix and gives the same results as usual k-means processing cases by features dataset, but that is inefficient. Usual k-means is not suited to work with distances. $\endgroup$ – ttnphns Nov 13 '18 at 10:17

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.

  • 2
    $\begingroup$ +1. I can't believe they are really doing this without giving any justification. But I think they are. Amazing. $\endgroup$ – amoeba says Reinstate Monica Nov 13 '18 at 9:27
  • $\begingroup$ These are so many black box approaches piled on top of each other - I doubt you could give a good reason to do so, even if you tried hard... $\endgroup$ – Has QUIT--Anony-Mousse Nov 13 '18 at 22:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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