6.2 Agglomerative hierarchical clustering

The hierarchical clustering for a two-dimensional dataset with complete, single and average linkages.

Figure 6.2: The hierarchical clustering for a two-dimensional dataset with complete, single and average linkages.

Hierarchical clustering starts by considering that each observation is its own cluster, and then merges sequentially the clusters with a lower degree of disimilarity \(d\) (the lower the similarity, the larger the similarity). For example, if there are three clusters, \(A\), \(B\) and \(C\), and their dissimilarities are \(d(A,B)=0.1\), \(d(A,C)=0.5\), \(d(B,C)=0.9\), then the three clusters will be reduced to just two: \((A,B)\) and \(C\).

The advantages of hierarchical clustering are several:

  • We do not need to specify a fixed number of clusters \(k\).
  • The clusters are naturally nested within each other, something that does not happen in \(k\)-means. Is possible to visualize this nested structure throughout the dendogram.
  • It can deal with categorical variables, throughout the specification of proper dissimilarity measures. In particular, it can deal with numerical variables using the Euclidean distance.

The linkage employed by hierarchical clustering refers to how the cluster are fused:

  • Complete. Takes the maximal dissimilarity between all the pairwise dissimilarities between the observations in cluster A and cluster B.
  • Single. Takes the minimal dissimilarity between all the pairwise dissimilarities between the observations in cluster A and cluster B.
  • Average. Takes the average dissimilarity between all the pairwise dissimilarities between the observations in cluster A and cluster B.

Hierarchical clustering is quite sensible to the kind of dissimilarity employed and the kind of linkage used. In addition, the hierarchical property might force the clusters to unnatural behaviors. Particularly, single linkage may result in extended, chained clusters in which a single observation is added at a new level. As a consequence, complete and average are usually recommended in practice.

Let’s illustrate how to perform hierarchical clustering in laligaStd.

# Compute dissimilary matrix - in this case Euclidean distance
d <- dist(laligaStd)

# Hierarchical clustering with complete linkage
treeComp <- hclust(d, method = "complete")
plot(treeComp)


# With average linkage
treeAve <- hclust(d, method = "average")
plot(treeAve)


# With single linkage
treeSingle <- hclust(d, method = "single")
plot(treeSingle) # Chaining


# Set the number of clusters after inspecting visually the dendogram for "long" groups of hanging leaves
# These are the cluster assignments
cutree(treeComp, k = 2) # (Barcelona, Real Madrid) and (rest)
##       Barcelona     Real Madrid Atlético Madrid      Villarreal 
##               1               1               1               2 
##        Athletic           Celta         Sevilla          Málaga 
##               2               2               2               2 
##   Real Sociedad           Betis      Las Palmas        Valencia 
##               2               2               2               2 
##           Eibar        Espanyol       Deportivo         Granada 
##               2               2               2               2 
##  Sporting Gijón  Rayo Vallecano          Getafe         Levante 
##               2               2               2               2
cutree(treeComp, k = 3) # (Barcelona, Real Madrid), (Atlético Madrid) and (rest)
##       Barcelona     Real Madrid Atlético Madrid      Villarreal 
##               1               1               2               3 
##        Athletic           Celta         Sevilla          Málaga 
##               3               3               3               3 
##   Real Sociedad           Betis      Las Palmas        Valencia 
##               3               3               3               3 
##           Eibar        Espanyol       Deportivo         Granada 
##               3               3               3               3 
##  Sporting Gijón  Rayo Vallecano          Getafe         Levante 
##               3               3               3               3

# Compare differences - treeComp makes more sense than treeAve
cutree(treeComp, k = 4) 
##       Barcelona     Real Madrid Atlético Madrid      Villarreal 
##               1               1               2               3 
##        Athletic           Celta         Sevilla          Málaga 
##               3               3               3               3 
##   Real Sociedad           Betis      Las Palmas        Valencia 
##               3               3               3               4 
##           Eibar        Espanyol       Deportivo         Granada 
##               4               4               3               4 
##  Sporting Gijón  Rayo Vallecano          Getafe         Levante 
##               4               4               4               4
cutree(treeAve, k = 4) 
##       Barcelona     Real Madrid Atlético Madrid      Villarreal 
##               1               1               2               3 
##        Athletic           Celta         Sevilla          Málaga 
##               3               3               3               3 
##   Real Sociedad           Betis      Las Palmas        Valencia 
##               3               3               3               3 
##           Eibar        Espanyol       Deportivo         Granada 
##               3               3               4               3 
##  Sporting Gijón  Rayo Vallecano          Getafe         Levante 
##               3               3               3               3

# We can plot the results in the first two PCs, as we did in k-means
cluster <- cutree(treeComp, k = 2)
plot(pca$scores[, 1:2], col = cluster)
text(x = pca$scores[, 1:2], labels = rownames(pca$scores), pos = 3, col = cluster)


cluster <- cutree(treeComp, k = 3)
plot(pca$scores[, 1:2], col = cluster)
text(x = pca$scores[, 1:2], labels = rownames(pca$scores), pos = 3, col = cluster)


cluster <- cutree(treeComp, k = 4)
plot(pca$scores[, 1:2], col = cluster)
text(x = pca$scores[, 1:2], labels = rownames(pca$scores), pos = 3, col = cluster)

If categorical variables are present, replace dist by daisy from the cluster package (you need to do first library(cluster)). For example, let’s cluster the iris dataset.

# Load data
data(iris)

# The fifth variable is a factor
head(iris)
##   Sepal.Length Sepal.Width Petal.Length Petal.Width Species
## 1          5.1         3.5          1.4         0.2  setosa
## 2          4.9         3.0          1.4         0.2  setosa
## 3          4.7         3.2          1.3         0.2  setosa
## 4          4.6         3.1          1.5         0.2  setosa
## 5          5.0         3.6          1.4         0.2  setosa
## 6          5.4         3.9          1.7         0.4  setosa

# Compute dissimilarity matrix using the gower dissimilarity measure
# This dissimilarity is able to handle both numerical and categorical variables
# daisy automatically detects wether there are factors present in the data and applies goer
# otherwise it applies the Euclidean distance
library(cluster)
## Warning: package 'cluster' was built under R version 3.2.5
d <- daisy(iris)
tree <- hclust(d)

# 3 main clusters
plot(tree)


# The clusters correspond to the Species
cutree(tree, k = 3)
##   [1] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
##  [36] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
##  [71] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3
## [106] 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
## [141] 3 3 3 3 3 3 3 3 3 3
table(iris$Species, cutree(tree, k = 3))
##             
##               1  2  3
##   setosa     50  0  0
##   versicolor  0 50  0
##   virginica   0  0 50

Performing hierarchical clustering in practice depends on several decisions that may have big consequences on the final output:

  • What kind of dissimilarity and linkage should be employed? Not a single answer: try several and compare.
  • Where to cut the dendogram? The general advice is to look for groups of branches hanging for a long space and cut on their top.

Despite the general advice, there is not a single and best solution for the previous questions. What is advisable in practice is to analyse several choices, report the general patterns that arise and the different features of the data the methods expose.

Hierarchical clustering can also be performed through the help of R Commander. To do so, go to 'Statistics' -> 'Dimensional Analysis' -> 'Clustering' -> 'Hierar...'. If you do this for the USArrests dataset after rescaling, you should get something like this:

HClust.1 <- hclust(dist(model.matrix(~-1 + Assault+Murder+Rape+UrbanPop, USArrests)) , 
  method= "complete")
plot(HClust.1, main= "Cluster Dendrogram for Solution HClust.1", xlab= 
  "Observation Number in Data Set USArrests", sub="Method=complete; Distance=euclidian")

Import the eurojob (download) dataset and standardize it properly. Perform a hierarchical clustering analysis for the three kind of linkages seen.