# What stop-criteria for agglomerative hierarchical clustering are used in practice?

I have found extensive literature proposing all sorts of criteria (e.g. Glenn et al. 1985(pdf) and Jung et al. 2002(pdf)). However, most of these are not that easy to implement (at least from my perspective). I am using scipy.cluster.hierarchy to obtain a cluster hierarchy, and I am now trying to decide how to form flat clusters from that. My goal is to discover common patterns in my observations, so I have no reference to compare the obtained clustering to. Can anyone suggest a pragmatic solution?

• On my web-page, there is "Clustering criterions" zip collection with the description (and SPSS functions) of a number of popular internal clustering criterions (stopping rules). For your info. – ttnphns May 8 '18 at 10:02

The following Wikipedia entry actually does a pretty good job of explaining the most popular and relatively simple methods:

The Elbow Method heuristic described there is probably the most popular due to its simple explanation (amount of variance explained by number of clusters) coupled with the visual check. The information theoretic method isn't hard to implement either and the page has some pseudocode you could use to start. The latter is analagous to a penalized likelihood based on model complexity as in the well known information criteria such as AIC, BIC, etc.

• Thanks! The Wikipedia article on hierarchical clustering does not link to that one. – Björn Pollex Sep 12 '10 at 20:32
• Oh right. Fixed now under "see also" links, thanks for pointing that out! – ars Sep 12 '10 at 20:38
• In Elbow Method, what if the objects to be clustered are quite "complex"? I mean they are not simple points, instead they are complex collections of data. I have figured out they pairwise distance (self-defined distance). How would I calculate the so-called "variance" here to apply Elbow Method? – Sibbs Gambling Sep 23 '13 at 9:52

It is rather difficult to provide a clear-cut solution about how to choose the "best" number of clusters in your data, whatever the clustering method you use, because Cluster Analysis seeks to isolate groups of statistical units (whether it be individuals or variables) for exploratory or descriptive purpose, essentially. Hence, you also have to interpret the output of your clustering scheme and several cluster solutions may be equally interesting.

Now, regarding usual statistical criteria used to decide when to stop to aggregate data, as pointed by @ars most are visual-guided criteria, including the analysis of the dendrogram or the inspection of clusters profiles, also called silhouette plots (Rousseeuw, 1987). Several numerical criteria, also known as validity indices, were also proposed, e.g. Dunn’s validity index, Davies-Bouldin valid- ity index, C index, Hubert’s gamma, to name a few. Hierarchical clustering is often run together with k-means (in fact, several instances of k-means since it is a stochastic algorithm), so that it add support to the clustering solutions found. I don't know if all of this stuff is readily available in Python, but a huge amount of methods is available in R (see the Cluster task view, already cited by @mbq for a related question, What tools could be used for applying clustering algorithms on MovieLens?). Other approaches include fuzzy clustering and model-based clustering (also called latent trait analysis, in the psychometric community) if you seek more robust way to choose the number of clusters in your data.

BTW, I just came across this webpage, scipy-cluster, which is an extension to Scipy for generating, visualizing, and analyzing hierarchical clusters. Maybe it includes other functionalities? I've also heard of PyChem which offers pretty good stuff for multivariate analysis.

The following reference may also be helpful:

Steinley, D., & Brusco, M. J. (2008). Selection of variables in cluster analysis: An empirical comparison of eight procedures. Psychometrika, 73, 125-144.

• Thanks for this excellent answer! In fact, the hierarchical clustering module you showed is already part of scipy. Also, scipy provides an implementation of k-means, so I could easily use that. – Björn Pollex Sep 13 '10 at 8:36
• Ok, I didn't look in details into this. For k-means, you need to pay attention to the fact that we generally need two outer loops for validating cluster solution (one where you vary the # of clusters and another for varying the seed -- the objective being to minimize the RSS); then you can use the Gap statistic to choose the optimal # of clusters. – chl Sep 13 '10 at 9:18

I recently became fund of the clustergram visualization method (implemented in R).

I use it for an extra method to assess a "good" number of clusters. Extending it to other clustering methods is not so hard (I actually did it, just didn't get to publish the code)