20 Questions to Test Your Skills on Hierarchical Clustering

Hierarchical clustering is one of the most widely used unsupervised machine learning algorithms. It‘s a great tool to have in your data science toolkit. In this post, we‘ll dive deep into how hierarchical clustering works, discuss different approaches and parameters, and provide questions along the way to test your understanding. By the end, you‘ll be well-equipped to apply hierarchical clustering to your own datasets.

Intro to Clustering and Hierarchical Clustering

First, let‘s take a step back – what exactly is clustering? Clustering is a type of unsupervised learning that involves grouping data points together based on their similarity, without any pre-defined labels. The goal is for data points within the same cluster to be more similar to each other than to points in other clusters. This is useful for exploratory data analysis, customer segmentation, anomaly detection, and more.

There are various clustering algorithms, including k-means, DBSCAN, Gaussian mixture models, and the focus of this post – hierarchical clustering. Hierarchical clustering algorithms build nested clusters by either merging smaller clusters into larger ones (agglomerative approach) or dividing larger clusters into smaller ones (divisive approach). The result is a tree-based representation of the objects, known as a dendrogram.

QUESTION 1: What are the two main approaches to hierarchical clustering?
A. Agglomerative and divisive
B. Top-down and bottom-up
C. Supervised and unsupervised
D. Single-linkage and complete-linkage

Agglomerative vs Divisive Hierarchical Clustering

In agglomerative hierarchical clustering, each data point starts as its own cluster. At each iteration, the two most similar clusters are merged together until all points belong to a single cluster. This is a "bottom-up" approach.

In contrast, divisive hierarchical clustering takes a "top-down" approach. All data points start in one cluster, which is divided into smaller clusters at each iteration until each point is in its own cluster.

In practice, agglomerative clustering is used more commonly than divisive. Divisive clustering is more complex computationally, whereas agglomerative clustering results in a uniquely determined hierarchy.

QUESTION 2: True or False: Agglomerative clustering is more frequently used than divisive clustering.

Linkage Methods for Agglomerative Clustering

A core component of hierarchical clustering is the linkage method, which determines how the distance between two clusters is calculated. This in turn influences which clusters get merged at each step. There are several common linkage methods:

Single Linkage:
The distance between two clusters is the minimum distance between any two members of the clusters. Single linkage can handle non-elliptical shapes but is sensitive to noise and outliers.

Complete Linkage:
The distance between two clusters is the maximum distance between any two members of the clusters. Complete linkage is less susceptible to noise and tends to form compact clusters, but it can break large clusters and has trouble with convex shapes.

Average Linkage:
The distance between two clusters is the average distance between each point in one cluster to every point in the other cluster. This is a compromise between single and complete linkage.

Centroid Linkage:
The distance between two clusters is the distance between the centroids of each cluster.

Ward‘s Method:
Clusters are merged in a way that minimizes the variance within all clusters. At each step, the pair of clusters with minimum between-cluster distance are merged.

QUESTION 3: Which linkage method calculates the distance between two clusters as the minimum distance between any two members of the clusters?
A. Single linkage
B. Complete linkage
C. Average linkage
D. Centroid linkage

QUESTION 4: True or False: Complete linkage is more robust to noise and outliers compared to single linkage.

Visualizing Results with Dendrograms

A dendrogram is a tree diagram that shows the hierarchical relationship between clusters. The height of each node represents the distance between the two clusters being merged.

To interpret a dendrogram:

• Clusters that are more similar will have lines that join lower on the tree
• Clusters that are less similar will have lines that join higher up
• The height of the lines indicates how different the clusters are from each other
• A horizontal line can be drawn across the dendrogram to specify a cutoff distance and determine the final clusters

QUESTION 5:
In the dendrogram shown above, which two leaves are the most similar to each other?
A. A and B
B. B and C
C. D and E
D. E and F

Choosing the Optimal Number of Clusters

One of the trickiest aspects of hierarchical clustering is selecting the optimal number of clusters for your final result. This often requires domain expertise and experimentation, but there are some quantitative measures that can guide your choice.

The silhouette score measures how well each datapoint fits into its assigned cluster versus the neighboring cluster. It ranges from -1 to 1, where a higher score indicates a model with better defined clusters. To calculate the silhouette score for a single datapoint:

1. Find the average distance between the datapoint and all other points in its cluster (a)
2. Find the average distance between the datapoint and all points in the nearest neighboring cluster (b)
3. Silhouette score = (b – a) / max(a, b)

Another internal validation metric is the Dunn index, which computes the ratio between the minimal inter-cluster distance to the maximal intra-cluster distance. A higher Dunn index indicates better clustering.

QUESTION 6:
Calculate the silhouette score for a datapoint with:

• Average intra-cluster distance (a) = 3
• Average distance to neighboring cluster (b) = 6
  A. 0.33
  B. 0.5
  C. 0.67
  D. 1.0

Hierarchical Clustering in Python with Scikit-Learn

Now let‘s see hierarchical clustering in action with Python‘s Scikit-Learn library. We‘ll use the AgglomerativeClustering class.

First, let‘s create a sample dataset:

from sklearn.datasets import make_blobs
X, _ = make_blobs(n_samples=12, centers=3, n_features=2,
random_state=0)

Next, we import AgglomerativeClustering, specifying the desired number of clusters and linkage method:

from sklearn.cluster import AgglomerativeClustering
ac = AgglomerativeClustering(n_clusters=3, 
linkage=‘complete‘)
ac.fit(X)

We can visualize the results, plotting the data points colored by their assigned cluster:

import matplotlib.pyplot as plt
plt.figure(figsize=(6, 4))
plt.scatter(X[:, 0], X[:, 1], c=ac.labels_)
plt.title(‘Hierarchical Clustering (Complete Linkage)‘)
plt.show()

QUESTION 7:
What parameter in AgglomerativeClustering controls the linkage method used?
A. method
B. metric
C. linkage
D. affinity

To plot the associated dendrogram:

from scipy.cluster.hierarchy import dendrogram
plt.title(‘Dendrogram‘)
dendrogram(ac.fit(X).children_)
plt.show()

QUESTION 8:
Based on the dendrogram shown, how many clusters would result from a horizontal cut at a distance of 4?

Advantages and Disadvantages of Hierarchical Clustering

Advantages:

• Doesn‘t require specifying number of clusters upfront
• Provides a full clustering tree for easy visualization and cluster selection after the fact
• Captures hierarchical structure present in some datasets

Disadvantages:

• High time and space complexity, making it infeasible for large datasets
  • Time complexity ranges from O(n^2) to O(n^3)
  • Space complexity is O(n^2) due to storing the distance matrix
• Sensitive to noise and outliers
• Cannot undo previous steps, so early bad decisions can never be fixed

QUESTION 9:
Which statement is FALSE about hierarchical clustering?
A. It provides an interpretable dendrogram for visualizing clusters
B. It has a low space complexity of O(n)
C. It‘s sensitive to noise and outliers
D. It captures nested cluster structures

QUESTION 10:
What is one reason hierarchical clustering is not typically used for datasets with millions of samples?
A. Millions of samples likely don‘t have a hierarchical structure
B. The time and space complexity is too high for large n
C. The dendrogram would be impossible to visualize
D. There would be too many clusters to interpret

Conclusion

Hierarchical clustering is a powerful unsupervised learning technique to group unlabeled data into a hierarchy of clusters. It comes in two flavors – agglomerative (bottom-up) and divisive (top-down). Agglomerative clustering is more popular and offers several linkage methods for measuring inter-cluster distances, including single, complete, average, centroid, and Ward‘s linkage.

The output dendrogram provides a highly interpretable view of the clustering results. However, the time and space complexity of hierarchical clustering limits its use to small-to-medium datasets. Choosing the final number of clusters can be challenging, but metrics like the silhouette score and Dunn index can assist.

To apply hierarchical clustering to your own data, check out the implementations in Python‘s Scikit-Learn or R‘s stats package. And make sure to experiment with different linkage methods and visualizations for your specific dataset and application.

Key Takeaways

• Hierarchical clustering groups data into a hierarchy of clusters, allowing clusters to have sub-clusters
• Agglomerative clustering is a bottom-up approach, while divisive clustering is top-down
• Key parameters are the linkage method, distance metric, and number of clusters
• Dendrograms visualize the clustering process and results
• Hierarchical clustering captures rich cluster structures but has high computational complexity

References and Resources

• Scikit-Learn Documentation: Hierarchical Clustering
• An Introduction to Statistical Learning, Chapter 10.3 – Clustering Methods
• Hands-On Machine Learning with Scikit-Learn, Keras & TensorFlow