Hierarchical Clustering in R

Hierarchical Clustering is a crucial part of unsupervised machine learning. It is a powerful tool for grouping data based on inherent patterns and shared characteristics. By visually representing the hierarchy of clusters, it provides deep insights into the intricacies and overlapping structures of our data.

Hierarchical Clustering operates broadly through two approaches — Agglomerative and Divisive. The Agglomerative technique, also known as 'bottom-up,' begins by treating every data point as a distinct cluster and then merges them until only one cluster remains. Conversely, the Divisive methodology, termed 'top-down,' begins with all data points in a single cluster and splits them progressively until each point forms its own cluster.

One of the most common forms of Hierarchical Clustering is Agglomerative Hierarchical Clustering. It starts with every single object in a single cluster. Then, in each successive iteration, it merges the closest pair of clusters and updates the similarity (or distance) between the newly formed cluster and each old cluster. The algorithm repeats this process until all objects are in a single remaining cluster.

The Agglomerative Hierarchical Clustering involves the following major steps:

• Compute the similarity (or distance) matrix containing the distance between each pair of objects in the dataset.
• Represent each data object as a singleton cluster.
• Repeat merging the two closest clusters and updating the distance matrix until only one cluster remains.
• The output is a tree-like diagram named dendrogram which represents the order and distances (similarity) of merges during the algorithm execution.

The Distance Matrix is a foundational element in hierarchical clustering that plays a critical role in understanding the relations and proximities between data points. Essentially, it is a square matrix where each element (i, j) represents the distance between the i-th and the j-th points in the dataset. The choice of distance metric (Euclidean, Manhattan, Cosine, etc.) can significantly influence the clustering outcome and is crucial to the coherence of the resulting clusters.

Distance matrix representation in linear algebra is as follows:

So, for example, D[2, 3] represents the distance between the second and third data points, and D[3, 2] would be the same value since the distance matrix is symmetric.

1. Initial Cluster Formation: It provides the initial groundwork for forming clusters by quantifying the closeness or similarity between individual data points or clusters.

2. Cluster Merging Strategy: It is essential to decide which clusters to merge at each step of the agglomerative clustering process. Clusters with the smallest distances between them are merged, promoting more natural groupings in the data.

3. Efficiency in Recalculation: After merging clusters, updating the distance matrix (instead of recalculating all distances from scratch) speeds up the clustering process considerably. Different linkage criteria (single, complete, average, etc.) provide various strategies for updating these distances.

4. Visual Representation and Analysis: The final dendrogram, which visualizes the process of hierarchical clustering, is fundamentally reliant on the distances computed and stored in this matrix. This visualization aids in determining the appropriate number of clusters by identifying significant gaps in the distances at which clusters merge.

Understanding and appropriately calculating the distance matrix is, therefore, a precursor to effectively implementing hierarchical clustering algorithms and extracting meaningful insights from complex datasets.

We'll use the Iris dataset and some standard R libraries — ggplot2 for data visualization.

# Load libraries
library(ggplot2)
library(GGally)
data(iris)

We plot our dataset with GGally's ggpairs, which aids in drawing more attractive and informative statistical graphics:

# Pairplot for the Iris dataset
ggpairs(iris, columns = 1:4, aes(color = Species))

Output plot:

Step 1: Euclidean Distance Function

Let's define a function to calculate the Euclidean distance between two points:

# Euclidean distance between two points
euc_dist <- function(a, b) {
  sqrt(sum((a - b)^2))
}

Now we can define a function that computes the distance matrix between clusters (using average linkage):

# Function to calculate the distance matrix between clusters
calculate_distance_matrix <- function(X, clusters) {
  n <- length(clusters)
  dist_matrix <- matrix(0, nrow = n, ncol = n)
  for (i in 1:(n-1)) {
    for (j in (i+1):n) {
      dists <- c()
      for (k in clusters[[i]]) {
        for (l in clusters[[j]]) {
          dists <- c(dists, euc_dist(X[k, ], X[l, ]))
        }
      }
      # Average linkage
      dist_matrix[i, j] <- mean(dists)
      dist_matrix[j, i] <- dist_matrix[i, j]
    }
  }
  return(dist_matrix)
}

Now, let's define the main function for Agglomerative Clustering:

# Main agglomerative clustering function
agglomerative_clustering <- function(X, n_clusters) {
  clusters <- lapply(1:nrow(X), function(i) i)
  while (length(clusters) > n_clusters) {
    dist_matrix <- calculate_distance_matrix(X, clusters)
    diag(dist_matrix) <- Inf # Avoid self-merging
    min_idx <- which(dist_matrix == min(dist_matrix), arr.ind = TRUE)[1, ]
    i <- min_idx[1]
    j <- min_idx[2]
    # Merge clusters
    clusters[[i]] <- c(clusters[[i]], clusters[[j]])
    clusters <- clusters[-j]
  }
  # Assign labels
  labels <- rep(0, nrow(X))
  for (label in seq_along(clusters)) {
    labels[clusters[[label]]] <- label
  }
  return(labels)
}

Let's visualize the clustering using the first two principal components for better separation:

# PCA for visualization
pca <- prcomp(X_scaled)
iris$PC1 <- pca$x[, 1]
iris$PC2 <- pca$x[, 2]

# Visualize the clustering
ggplot(iris, aes(x = PC1, y = PC2, color = Cluster, shape = Species)) +
  geom_point(size = 3) +
  labs(title = "Custom Agglomerative Clustering on Iris (PCA Projection)")

Output plot:

R provides an optimized, efficient implementation of Hierarchical Clustering through the hclust() function. Let's try it with our Iris dataset.

Step 1: Compute Distance Matrix

# Compute distance matrix
dist_matrix <- dist(X_scaled, method = "euclidean")

Step 2: Perform Hierarchical Clustering

# Perform hierarchical clustering
hc <- hclust(dist_matrix, method = "average")

Step 3: Cut Tree into Clusters

# Cut tree into 3 clusters
iris$Cluster_hclust <- as.factor(cutree(hc, k = 3))

Step 4: Visualize the Clusters

ggplot(iris, aes(x = PC1, y = PC2, color = Cluster_hclust, shape = Species)) +
  geom_point(size = 3) +
  labs(title = "hclust Agglomerative Clustering on Iris (PCA Projection)")

Output plot:

Here, we are plotting the dendrogram produced by hierarchical clustering on the Iris dataset (using only the four numeric features). The dendrogram visually represents how clusters are formed at each step of the agglomerative process.

# Basic hierarchical clustering
hc <- hclust(dist(iris[, 1:4]))

# Plot only the top portion
plot(hc, labels = FALSE, main = "Top of Hierarchical Clustering Dendrogram")
rect.hclust(hc, k = 3, border = "red")  # show 3 clusters

Output:

Congratulations! You've successfully broken down the nuances of Hierarchical Clustering, focusing on Agglomerative Clustering, and brought Hierarchical Clustering to life using R. You implemented the algorithm from scratch, visualized the results with ggplot2, and compared your results to R's built-in hclust function. Practice tasks await next, offering the perfect platform to apply acquired concepts and deepen your understanding of Hierarchical Clustering. Carry this momentum forward, and let's forge ahead into the captivating world of Hierarchical Clustering!