There are a few different commonly used clustering algorithms within the single-cell space, although Leiden seems to be the top choice these days. FlowSOM is a classic package for analyzing flow cytometry data. It has a two-step approach for clustering. First, it builds a self-organizing map (SOM) where cells are assigned to 100 grid points. Then, it uses ConsensusClusterPlus to meta-cluster the SOM codes. I have not seen other packages that take this approach. There is no publication for FlowSOM and the documentation does not explain this part. Why this two-step approach and why isn't this more common?
The two step approach will be used in any cluster algorithm (except see "network theory" below), you just may not see it. Clustering methods are very common in genomics, they are popular because they are very visual and will stack against a heatmap nicely. They have been replaced by dimensionality reduction such as PCA type analysis. For data mining PCA is a much more robust method for a number of reasons for example they overcome the problems listed as "The Bad" and "The Ugly" below. PCA type analysis is difficult to visualise, particularly when it steps into multi-dimensions and thats why developers like clustering ... easy for the developer to understand and easy for the use to visually appreciate, particularly against a heat map.
Any classical clustering The first step is to build a matrix and the second is to reorganise the relationships within the matrix using a pre-defined algorithm, unweighted pairwise group method with arithmetic mean (UPGMA).
- The matrix in this case will be the grid.
- The second step is the clustering method. The method used ConsensusClusterPlus by Wilkerson and Hayes (2010) is, 0
The consensus clustering (CC) method provides quantitative and visual stability evidence for estimating the number of unsupervised classes in a dataset.
All that means is it stacks a heat map onto a clustering tree. Here's the output of the paper and the 'workhorse' is the tree presented in "A",
Like all great movies, it has 3 faces,
The Good using
k-means clustering and that is well respected method in supervised-learning and suspect it performs pretty well in unsupervised learning too. It's a good method.
The bad There could easily be artefacts in the deeper relationships of the tree and that would need a full empirical investigation. I know that because genetic diversity is often measured by trees and loads of attention has gone into modelling the process and CCP is assuming homogeneity in the rate process - which rarely hplds in biology. Thus, there will be situations where that falls over, however, what I strongly suspect is that the k-means methods is attempting to circumvent this situation, without doing so explicitly (if that makes any sense). I would need to study the algorithm to assess this and I would not use clustering in data mining/unsupervised learning.
The Ugly The basic problem with clustering and the reason it isn't used in genetic diversity *, is because there's loads of clustering algorithms, they give different answers and there's no way to distinguish which is which. Having said all that
k-means clustering is very respectable.
The reason it's not common is that there has never been a consensus on the cluster algorithm and modellers prefer to avoid them because they are only used for data exploration/mining and not useful for hypothesis testing. However I do stress that
k-means supervised learning is a very good method, but that is not the same as clustering (which is unsupervised learning).
* or at least if it is used its just a method to visual a matrix and a like Warning clustering! will appear somewhere in the legend.
Parameters and conclusion There is a parameter issue with the Figure above is tracking manually. It demonstrates k has a HUGE influence on the result. In real world supervised learning parameterisation is automated, never ever would it be done manually. The technique is called parameterisation and it's kinda important (so like the user can't use a parameter that gives an output that suits them!! [I've not said that BTW]). So you'd ask an algorithm above the k=x algorithm to find the optimal value of k.
FlowSOM automates the value for k and then tells you ... thats good and I'd be happy with that. If it doesn't, you have to manually feed loads of values of k and provide an independent assessment on which was the best. That is not cool and you will have to perform a laborious manual calculation.
Network theory Leiden looks to be part of network theory e.g. Trag and van Eck (2019). That is a significant advantage over classical clustering, because network theory is being dumped over the top, i.e. the third step, which can yield real power over the data set. Personally I follow graph theory, but both have major potential and are heavily under-utilised. Its not really fair to compare a classical method with the power of network theory. Certainly when entering graph theory what you can leverage from the graph (network) is enormous. I personally, thought the whole area was being ignored (there's lots of applications), but maybe its time will yet come into the mainstream.
To @Pallie's comments of
dimensionality and distance. I do not disagree at all and is the reason why dimensionality reduction approaches such as PCA or multi-dimensional scaling are preferred.
RAM overhead Of course the calculation will be hard on RAM: if k was fixed at 2 or 3, it will run reasonably quickly, but might not be meaning. Any k parameterisation will be RAM intensive, but IMO thats the nature of big data calculation and cloud computing: you just pick a computer with loads of RAM or just fit more RAM. There will also be a risk of course of RAM bottlenecks on standard machines (where it just freezes). The key thing is whether the approaches are giving biologically significant different results and personally I would consider it empirically. These are different calculations and this is complex data.