Activity 4.1 - Hierarchical clustering

SUBMISSION INSTRUCTIONS

  1. Render to html
  2. Publish your html
  3. Submit a link to your published solutions
#Loading packages needed for this assignment
library(tidyverse)
library(cluster)
library(factoextra)
library(patchwork)

Question 1

Consider three data sets below. Each data set contains three “clusters” in two dimensions. In the first, the clusters are three convex spheres. (A convex cluster is one where all points in the cluster can be connected with a straight line that does not leave the cluster.) In the second, one cluster is a sphere; one is a ring; and one is a half-moon. In the third, two clusters are spirals and one is a sphere. Our goal is to compare the performance of various hierarchical methods in clustering different cluster shapes.

three_spheres <- read.csv('Data/cluster_data1.csv')
ring_moon_sphere <- read.csv('Data/cluster_data2.csv')
two_spirals_sphere <- read.csv('Data/cluster_data3.csv')

Perform agglomerative clustering with single, complete, average, and Ward linkages. Cut each tree to produce three clusters. Produce 12 scatterplots, one per data set/linkage combination, showing the 3-cluster solution. Title each graph with the linkage used, as well as the average silhouette width (\(\bar s\)) for that clustering solution. Use patchwork to create a nice 4x3 grid of your plots. Play around with larger #| fig-width and #| fig-height values in your R chunk options to make sure your grid is large enough.

Discuss the following:

  1. Which linkage works best for which scenario?

    Complete, average, and Ward linkage work best for the three spheres because they favor compact, round clusters. Single linkage is the only one that recovers the ring, moon, and spirals, because it chains nearest neighbors together and can follow curved shapes.

  2. Does the average silhouette width always do a good job of measuring the quality of the clustering solution?

    No. Silhouette width rewards compact, round clusters, so it gives a higher score to Ward and complete linkage on the spiral and ring data even though they cut those shapes apart, and a lower score to single linkage even though it found the true clusters.

(Hint: you have a lot of repetitive code to write. You may find it helpful to write a function that takes a data set and a linkage method as arguments, does the clustering and computes average silhouette width, and produces the desired plot.)

library(tidyverse)
library(cluster)
library(patchwork)

three_spheres      <- read.csv('Data/cluster_data1.csv')
ring_moon_sphere   <- read.csv('Data/cluster_data2.csv')
two_spirals_sphere <- read.csv('Data/cluster_data3.csv')

# Function: agglomerative clustering with a given linkage, cut to 3 clusters,
# compute average silhouette width, and plot the 3-cluster solution
cluster_plot <- function(data, linkage) {
  # keep the two coordinate columns
  data_numeric <- data %>% 
    dplyr::select(where(is.numeric)) %>% 
    dplyr::select(1:2) %>% 
    setNames(c('x', 'y'))
  
  # agglomerative clustering
  clust <- agnes(data_numeric, metric = 'euclidean', method = linkage)
  
  # cut the tree to 3 clusters
  clusters <- cutree(clust, k = 3)
  
  # average silhouette width
  sils <- silhouette(x = clusters, dist = dist(data_numeric))
  s_bar <- mean(sils[, 'sil_width'])
  
  # plot
  data_numeric %>% 
    mutate(cluster = factor(clusters)) %>% 
    ggplot(aes(x = x, y = y, color = cluster)) +
    geom_point() + 
    guides(color = 'none') + 
    theme_classic(base_size = 16) + 
    labs(title = paste0(str_to_title(linkage), ' linkage, ',
                        'avg. silhouette width = ', round(s_bar, 2)))
}

# Three spheres
p1  <- cluster_plot(three_spheres, 'single')
p2  <- cluster_plot(three_spheres, 'complete')
p3  <- cluster_plot(three_spheres, 'average')
p4  <- cluster_plot(three_spheres, 'ward')

# Ring, moon, sphere
p5  <- cluster_plot(ring_moon_sphere, 'single')
p6  <- cluster_plot(ring_moon_sphere, 'complete')
p7  <- cluster_plot(ring_moon_sphere, 'average')
p8  <- cluster_plot(ring_moon_sphere, 'ward')

# Two spirals, sphere
p9  <- cluster_plot(two_spirals_sphere, 'single')
p10 <- cluster_plot(two_spirals_sphere, 'complete')
p11 <- cluster_plot(two_spirals_sphere, 'average')
p12 <- cluster_plot(two_spirals_sphere, 'ward')

# 4x3 grid: rows = data sets, columns = linkages
(p1 + p2 + p3 + p4) /
  (p5 + p6 + p7 + p8) /
  (p9 + p10 + p11 + p12)

Question 2

Consider the data set below on milk content of 25 mammals. The variables have been pre-scaled to z-scores, hence no additional standardizing is necessary. (Data source: Everitt et al. Cluster analysis 4ed)

mammals <- read.csv('Data/mammal_milk.csv') %>% 
  column_to_rownames('Mammal')

A)

Perform agglomerative clustering with single, complete, average, and Ward linkages. Which has the best agglomerative coefficient?

library(tidyverse)
library(cluster)

# Find the mammal/milk data file in the Data folder
milk_file <- list.files('Data', pattern = 'mammal|milk', 
                        ignore.case = TRUE, full.names = TRUE)[1]
milk_file   # prints which file was used
[1] "Data/mammal_milk.csv"
my_data <- read.csv(milk_file)

# Use the text column (mammal names) as row names, keep only numeric columns
name_col <- names(my_data)[!sapply(my_data, is.numeric)][1]
if (!is.na(name_col)) {
  my_data <- my_data %>% column_to_rownames(name_col)
}
my_data <- my_data %>% dplyr::select(where(is.numeric))

# Scale and compute Euclidean distance
my_scaled <- scale(my_data)
my_dist   <- dist(my_scaled, method = 'euclidean')

# Agglomerative clustering with each linkage
my_single   <- agnes(my_dist, method = 'single')
my_complete <- agnes(my_dist, method = 'complete')
my_average  <- agnes(my_dist, method = 'average')
my_ward     <- agnes(my_dist, method = 'ward')

# Agglomerative coefficients
data.frame(
  Linkage = c('Single', 'Complete', 'Average', 'Ward'),
  AC = round(c(my_single$ac, my_complete$ac, my_average$ac, my_ward$ac), 3)
)
   Linkage    AC
1   Single 0.788
2 Complete 0.899
3  Average 0.871
4     Ward 0.941

Ward linkage has the best agglomerative coefficient (AC = 0.941), followed by complete (0.899), average (0.871), and single (0.788), so Ward finds the strongest clustering structure in the mammal milk data.

B)

Plot a dendrogram of the method with the highest AC. Which mammals cluster together first?

library(factoextra)

# Dendrogram of the Ward linkage (swap in whichever had the highest AC)
fviz_dend(my_ward, cex = 0.6) + 
  labs(title = 'Ward linkage')

# Which mammals cluster together first?
my_ward_hc <- as.hclust(my_ward)
first_heights <- my_ward_hc$height == min(my_ward_hc$height)
first_merges <- my_ward_hc$merge[first_heights, , drop = FALSE]

# Pairs of single mammals (negative numbers = individual observations)
apply(first_merges, 1, function(m) rownames(my_scaled)[-m[m < 0]])
     [,1]      
[1,] "Deer"    
[2,] "Reindeer"

Deer and reindeer cluster together first: they merge at the lowest height on the Ward dendrogram, so their milk compositions are the most similar of all the mammals.

C)

If the tree is cut at a height of 4, how many clusters will form? Which cluster will have the fewest mammals, and which mammals will they be?

# Cut the tree at height 4
clusters_h4 <- cutree(as.hclust(my_ward), h = 4)

# How many clusters?
max(clusters_h4)
[1] 4
# How many mammals in each cluster?
table(clusters_h4)
clusters_h4
 1  2  3  4 
11  6  6  2 
# Mammals in the smallest cluster
smallest <- names(which.min(table(clusters_h4)))
names(clusters_h4)[clusters_h4 == smallest]
[1] "Dolphin" "Seal"   
# Dendrogram with the cut shown
fviz_dend(my_ward, h = 4, cex = 0.6) + 
  geom_hline(yintercept = 4, linetype = 2) + 
  labs(title = 'Ward linkage, cut at height 4')

Cutting the tree at a height of 4 gives 4 clusters, with 11, 6, 6, and 2 mammals. The smallest cluster has only 2 mammals, dolphin and seal.

D)

Use WSS and average silhouette method to suggest the optimal number of clusters. Re-create the dendrogram with the cluster memberships indicated.

library(patchwork)

p_wss <- fviz_nbclust(my_scaled, 
                      FUNcluster = hcut,
                      k.max = 10,
                      method = 'wss',
                      diss = my_dist,
                      hc_method = 'ward',
                      hc_func = 'agnes') + 
  labs(title = 'WSS vs k')

p_sil <- fviz_nbclust(my_scaled, 
                      FUNcluster = hcut,
                      k.max = 10,
                      method = 'silhouette',
                      diss = my_dist,
                      hc_method = 'ward',
                      hc_func = 'agnes') + 
  labs(title = 'Average silhouette width vs k')

p_wss + p_sil

E)

Use suitable visualizations, including dimension reduction techniques, to explore the different milk characteristics of the assigned clusters. Discuss.

library(FactoMineR)
library(factoextra)

# Number of clusters chosen in part D (change if you picked a different k)
k_best <- 3

# Cluster labels
final_clusters <- cutree(my_ward, k = k_best)

# PCA on the milk variables (PCA() scales by default)
milk_pca <- PCA(my_data, graph = FALSE)

fviz_pca(milk_pca, 
         habillage = factor(final_clusters),
         repel = TRUE) + 
  ggtitle(paste0('PCA biplot, Ward linkage ', k_best, '-cluster solution'))

The first two principal components explain 95.3% of the variation. Dim1 (78.1%) contrasts water and lactose against fat, protein, and ash. Cluster 1 is the largest group (horse, donkey, monkey, camel, hippo). It sits on the left, so its milk is high in water and lactose and low in fat and protein. Cluster 2 (dog, rat, rabbit, deer, reindeer, whale) is high in protein and ash and high in fat. Cluster 3 (dolphin and seal) is far out in the direction of the fat arrow, their milk is extremely fattyvand low in water, maybe an adaptation to cold aquatic environments.