Hierarchical Clustering

R Machine Learning Series

Introduction

The previous post provided a practical application of using K-means Clustering to real-world dataset. Hierarchical clustering is an alternative approach to k-means clustering for identifying groups in the dataset. It does not require us to pre-specify the number of clusters to be generated as is required by the k-means approach. Furthermore, hierarchical clustering has an added advantage over K-means clustering in that it results in an attractive tree-based representation of the observations, called a dendrogram.

R Packages Required and Data Preparation

To perform a clustering algorithm for both Hierarchical and K-means clustering in R, generally, the data should be prepared as follows:

1. Rows are observations (individuals) and columns are variables.

2. Any missing value in the data must be removed or imputed.

3. The data must be standardized (scaled) to make variables comparable.

This post uses USArrests dataset, which contains statistics in arrests per 100,000 residents for assault, murder, and rape in each of the 50 US states in 1973. It includes also the percent of the population living in urban areas.

The required packages are:

library(tidyverse)  # Data manipulation. 
library(factoextra) # Clustering visualization. 

R Codes

# Clear our workspace: 
rm(list = ls())

# Load data
data(USArrests)

# Normalize 0-1 datasets:

df <- USArrests %>% mutate_all(function(x) {(x - min(x)) / (max(x) - min(x))})

# Set rowname: 
row.names(df) <- row.names(USArrests)

# Compute distances: 
dd <- dist(df, method = "euclidean")

# Visualize the dissimilarity: 
fviz_dist(dd, lab_size = 7)

# Perform hierarchical clustering: 
hc <- hclust(dd, method = "ward.D2")

# Set theme for all plots: 

library(extrafont)
my_font <- "Roboto Condensed"

# Create a draft of dendrogram by using fviz_dend() function: 

fviz_dend(hc, 
          k = 4,   
          cex = 0.5, 
          rect = TRUE, 
          rect_fill = TRUE, 
          horiz = FALSE, 
          palette = "jco", 
          rect_border = "jco", 
          color_labels_by_k = TRUE) -> basic_plot

# Decorate the draft: 

basic_plot + 
  theme_gray() + 
  theme(plot.margin = unit(rep(0.7, 4), "cm")) + 
  theme(text = element_text(family = my_font)) + 
  labs(title = "Dendrogram based on Hierarchical Clustering (Version 1)", 
       caption = "Source: World Almanac and Book of facts 1975")

In the dendrogram displayed above, each leaf corresponds to one observation. As we move up the tree, observations that are similar to each other are combined into branches, which are themselves fused at a higher height.

The height of the fusion, provided on the vertical axis, indicates the (dis)similarity between two observations. The higher the height of the fusion, the less similar the observations are. Note that, conclusions about the proximity of two observations can be drawn only based on the height where branches containing those two observations first are fused. We cannot use the proximity of two observations along the horizontal axis as a criteria of their similarity.

The height of the cut to the dendrogram controls the number of clusters obtained. It plays the same role as the k in k-means clustering. In order to identify sub-groups (clusters), we can cut the dendrogram with cutree() function:

# Cut tree into 4 groups: 
sub_grp <- cutree(hc, k = 4)

# Create plot of clusters: 
fviz_cluster(list(data = df, cluster = paste0("Group", sub_grp)), 
             alpha = 1, 
             palette = "jco", 
             labelsize = 9, 
             ellipse.type = "norm") -> cluster_plot

# Decorate the plot: 
cluster_plot + 
  theme(legend.position = c(0.1, 0.8)) + 
  theme(plot.margin = unit(rep(0.5, 4), "cm")) + 
  theme(text = element_text(family = my_font)) + 
  labs(title = "Cluster based on Hierarchical Clustering", 
       caption = "Source: World Almanac and Book of facts 1975") 

And we can extract the clusters and add to our initial data to do some descriptive statistics at the cluster level:

USArrests %>%
  mutate(Cluster = paste0("Group", sub_grp)) %>%
  group_by(Cluster) %>%
  summarise_all(mean) %>% 
  mutate_if(is.numeric, function(x) {round(x, 2)}) %>% 
  knitr::kable()

Cluster	Murder	Assault	UrbanPop	Rape
Group1	14.67	251.29	54.29	21.69
Group2	10.82	257.38	76.00	33.19
Group3	6.06	140.06	71.33	18.68
Group4	3.09	76.00	52.08	11.83

References

1. https://www.datanovia.com/en/blog/cluster-analysis-in-r-simplified-and-enhanced/
2. http://www.sthda.com/english/articles/31-principal-component-methods-in-r-practical-guide/112-pca-principal-component-analysis-essentials/
3. http://www.sthda.com/english/articles/31-principal-component-methods-in-r-practical-guide/117-hcpc-hierarchical-clustering-on-principal-components-essentials/
4. http://www.sthda.com/english/wiki/factoextra-r-package-easy-multivariate-data-analyses-and-elegant-visualization
5. https://uc-r.github.io/hc_clustering
6. http://www.cookbook-r.com/Graphs/Legends_(ggplot2)/
7. https://blog.exploratory.io/visualizing-k-means-clustering-results-to-understand-the-characteristics-of-clusters-better-b0226fb3dd10
8. https://www.freecodecamp.org/news/clustering-the-top-1-asset-analysis-in-r-6c529b382b42/
9. https://www.huber.embl.de/msmb/Chap-MultivaHetero.html