Hierarchical clustering with agnes - how to cut the tree?

Question

I am working on a data.frame with both categorical and metric variables

# example data
a <- as.factor(c("A","A","B","C","D","A","C","A","C","C"))
b <- rep(1:5,2)
c <- as.factor(c("elephant","elephant","cat","dog","cat","elephant",
                 "cat","elephant","dog","dog"))
df <- data.frame(a,b,c)

I run a cluster analysis on this example data

# Dissimilarity Matrix Calculation

library(cluster)

x <- daisy(df, metric = c("gower"),
    stand = FALSE, type = list())

# Hierarchical Clustering

z <- agnes(x, diss = inherits(x, "dist"), metric = "euclidean",
      stand = FALSE, method = "single", par.method,
      trace.lev = 0, keep.diss = TRUE)

and receive this dendrogram

plot(z,  main="plotit", which.plot = 2)

• How do I know where to cut the tree?

I could do something like

cutree(z, k = 2, h=0.3)

but the values chosen for k and hwould be entirely arbitrary. I work on a large data set where I can't rely on information I see in the plot in this example?

• Is there a heuristic to determine the number of clusters?
• Is there a heuristic to determine the cutting height of the tree?

Answer 1

Husson et al. (2010) propose an empirical criterion based on the between-cluster inertia gain (see section 3.2 of this paper). Basically, the optimal number of clusters q is the one for which the increase in between-cluster dissimilarity for q clusters to q+1 clusters is significantly less than the increase in between-cluster dissimilarity for q-1 clusters to q clusters. So, it's similar to identifying a plateau in the plots above, but it's automatic and you don't have to "guess".

Still, you should keep in mind that each level of the dendogram corresponds to a valid partitioning of the observations, so there is no absolute best solution. The optimal number of clusters you want to select depends on your task. For example, when hierarchical clustering is used for outlier detection, you want to request a large number of clusters (n/10 in the example provided, where n is the total number of observations).

Answer 2

The academic research literature has a lot of information on this.

What I found more readable and easier to understand is section 8.1.3 from the book "Practical Data science with R" by N.Zumel and J.Mount.

From page 186 ff

PICKING THE NUMBER OF CLUSTERS

There are a number of heuristics and rules-of-thumb for picking clusters; a given heuristic will work better on some datasets than others. It’s best to take advantage of domain knowledge to help set the number of clusters, if that’s possible. Otherwise, try a variety of heuristics, and perhaps a few different values of k.

They then discuss the "Total within sum of squares" and the "Calinski-Harabasz index" (with R code)

One simple heuristic is to compute the total within sum of squares ( WSS ) for different values of k and look for an “elbow” in the curve.

...

The Calinski-Harabasz index of a clustering is the ratio of the between-cluster variance (which is essentially the variance of all the cluster centroids from the dataset’s grand centroid) to the total within-cluster variance...

But there are many more methods. CHeck out the (difficult) Coursera Course Cluster Analysis in Data Mining, week 3