I am currently dealing with an issue regarding cluster validation.

I have a pairwise distance matrix (based on the hamming distance between a set of core genes of different strains of a bacterium). I performed k-medoids clustering on the pairwise distances, attempting to validate my initial suspicion that there are 3 clusters. Surprisingly, the average silhouette index is around 0.3 for k = 2 and around 0.2 for k = 3, suggesting that the clustering is "better" for the k = 2 case. I understand that the silhouette index is only one of many cluster validation methods and that the silhouette index cannot be wrong per se.

I have the suspicion that the silhouette index supports k = 2 over k = 3 because my putative clusters are of different inter-cluster distance as well as of different variability, as indicated by an nMDS plot as well as boxplots of (real) pairwise distances between clusters. Specifically, I appear to have two tight clusters that are close to each other (cluster 1 and 2), while the third cluster is further away and less well defined (cluster 3).


boxplots of real intra- and inter-cluster distances

I believe that the average silhouette index is smaller for k = 2 as the neighbouring cluster in that case is far away (for both clusters), where in the k = 3 case the average index is smaller since the two well defined clusters' neighbouring cluster are much closer (the other well defined cluster, respectively).

I am aware that the nMDS representation is not necessarily representative of the true pairwise distances.

I would like to know how to find out whether it would be ok to dismiss k = 2 in favor of k = 3 and, if so, how to make that point in the most elegant fashion.

  • $\begingroup$ I think that your reasoning about "why" it were so is credible. Average type Silhouette index (you might want to read about other possible its variants on my web-page in "Clustering criterions" collection) does not hunt specifically for close yet tight, well-separated clusters. You are very true that there are many clustering indices, each having its "tastes" in data. In the end, one would prefer number of clusters which is the most interpretable solution. $\endgroup$ – ttnphns Nov 19 '17 at 16:22
  • $\begingroup$ Silhouette of 0.2 and 0.3 are both considered to be bad. So neither clustering worked. Try HAC instead of k-medoids, for example. Try to understand why it doesn't work - you may need to improve the distance function for your data. $\endgroup$ – Has QUIT--Anony-Mousse Nov 20 '17 at 7:10

If my memory serves, silhouettes often tend to support smaller number of clusters, but there are bigger issues with your analysis. You're analyzing biological data and straying far from the best practices in the field.

In your case both 1+2 vs 3 and 1 vs 2 vs 3 are valid clusterings, so you'd be better off with the hierarchical clustering, (3, (1, 2)) in a Newick notation. UPGMA/NJ, if you don't have the computational resources, ML or bayesian phylogenetics otherwise.

In addition, Hamming distances can be applicable only for very close strains, where the distances would be on the order of single mutations. Otherwise use some distance metric aware of possible multiple mutations on a single site and different mutation rates. There are quite a few of those, as well as methods for choosing the best one using eg Bayesian information criterion. Kimura 2-param seems to be a safe choice.

  • $\begingroup$ Thanks for your answer. We did indeed built a phylogeny based on the core gene alignment using RaxML as well. To my knowledge, it is not trivial to do clustering (and especially cluster validation) based on a phylogenetic tree. $\endgroup$ – PejoPhylo Nov 19 '17 at 13:10
  • $\begingroup$ The clades in the tree are clusters, and bootstrap values provide validation. You just need to identify well-supported clades diverging near the root and take them. With the clustering being as it is, I guess 1 and 2 will be well-formed clades and 3 would be a paraphyletic mess. I haven't heard of the method that would be a better argument for species/strain clustering. Not the widely accepted one, at least. $\endgroup$ – Synedraacus Nov 19 '17 at 13:52
  • $\begingroup$ I agree with what you're saying, but I still don't see an easy (and rigorous) way to determine the "best supported" nr of clusters/clades/subspecies from a phylogenetic tree. $\endgroup$ – PejoPhylo Nov 19 '17 at 13:56

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.