What is hierarchical clustering?

Clustering is an unsupervised machine learning technique used in data analysis to detect and group similar objects. Hierarchical cluster analysis (HCA), or hierarchical clustering, groups objects into a cluster hierarchy without enforcing a linear order within them. Many disciplines, such as biology, image analysis and the social sciences, use hierarchical clustering methods to explore and recognize patterns in datasets. Use cases include categorizing populations in clinical research, customer segmentation and detecting communities of nodes in network models.

There are two types of hierarchical clustering:

- Agglomerative or bottom-up approach¹ that repeatedly merges clusters into larger ones until a single cluster emerges.

- Divisive or top-down approach that² starts with all data in a single cluster and continues to split out successive clusters until all clusters are singletons.

Hierarchical clustering analysis has high computational costs. While using a heap can reduce computation time, memory requirements are increased. Both the divisive and agglomerative types of clustering are “greedy,” meaning that the algorithm decides which clusters to merge or split by making the locally optimal choice at each stage of the process. It is also possible to apply a stop criterion, where the algorithm stops agglomeration or splitting clusters when it reaches a predetermined number of clusters.

A tree-like diagram called a dendrogram³ is often used to visualize the hierarchy of clusters. It displays the order in which clusters have been merged or divided and shows the similarity or distance between data points. Dendrograms can also be understood as a nested list of lists⁴ with attributes.

Hierarchical clustering algorithms use the concept of a dissimilarity matrix to decide which clusters to merge or divide. Dissimilarity is the distance between two data points as measured by a chosen linkage method. The values in a dissimilarity matrix express:

- The distance⁵, a Euclidean distance as an example, between single points in a set

- A linkage clustering criterion, which specifies dissimilarity as a function of the pairwise distances of points across sets

Let’s explore the most common Euclidean distance linkage methods. Examples of other distance metrics that can be used include Minkowski, Hamming, Mahalanobis, Hausdorf and Manhattan distance. Note that each linkage method generates different clusters from the same dataset. Selecting the appropriate linkage clustering method depends on factors such as the type of data being clustered, data density, cluster shape and whether there are outliers or noise in the dataset.

The single linkage method analyzes pairwise distances between items in two clusters and then uses the minimum distance between the clusters. The min method handles nonelliptical cluster shapes well but will be impacted by noise and outliers. It has a limitation known as the chaining effect⁶. A few points creating a bridge between a cluster pair can result in the two clusters merging into one. The min linkage criteria can be represented as:

 mina∈A,b∈Bd(a,b)

where A and B are two sets of observations and d is a distance function.

Cluster distances can also be calculated based on the points that are furthest away from each other. The max method is less sensitive than the min method to noise and outliers, but using it can skew the results when there are globular or large clusters. Max-linkage often produces more spherical clusters than min-linkage. The max linkage can be represented in the formula:

 maxa∈A,b∈Bd(a,b)

where A and B are two sets of observations and d is distance.

These methods, introduced by Sokal and Michener⁷ , define the distance between clusters as the average distance between pairs across all pairs of points in the clusters. The algorithm can be either the unweighted pair group method with arithmetic mean (UPGMA) or the weighted pair group method with arithmetic mean (WPGMA). The meaning of "unweighted" here is that all distances contribute equally to each average.

UPGMA is represented by the formula

 1∣A∣·∣B∣∑a∈A∑b∈Bd(a,b)

where *A* and *B* are two sets of observations and *d* is distance.

WPGMA is represented by the formula

 d(i∪j,k)=d(i,k)+d(j,k)2

where i and j are the closest clusters being combined in each step to form a new cluster of the union of i and j. We can then calculate the distance to another cluster k, which is the arithmetic mean of the average distances between data points in k and i and k and j.

Here, we use the distance between cluster centers or centroids. The distance between centroids is calculated by using a distance function:

∥μA-μB∥2

where μ_A is the centroid of A and μ_B is the centroid of B.

Joe H. Ward introduced the minimal increase of sum of squares (MISSQ) method⁸ in the 1960s. Every data point starts in its own cluster. This approach means that the sum of squares between data points is initially at zero, then increases as we merge clusters. Ward's method minimizes the sum of the squared distances of the points from the cluster centers as they are merged. Ward's method is a good choice for quantitative variables⁹, and it is less affected by noise or outliers. It can be represented as:

 ∣A∣·∣B∣A∪B∥μA-μB∥2=∑x∈A∪B∥x-μA∪B∥2-∑x∈A∥x-μA∥2-∑x∈B∥x-μB∥2

where the mean of A and mean of B are the centroids of A and B respectively, and x is a data point that belongs to the union of A and B

Ward's minimum variance method can be refined by using a Lance-Williams algorithm. These algorithms use a recursive formula to update cluster distances and find the optimal closest cluster pair to merge.

In agglomerative hierarchical clustering, also known as agglomerative nesting (AGNES), each data point starts as a cluster. The algorithm uses a selected linkage clustering criterion based on a dissimilarity matrix to decide which pair of clusters to join. The algorithm moves up the hierarchy and keeps pairing clusters until everything has been linked together, creating a hierarchical series of nested clusters. Roughly speaking the agglomerative clustering steps¹⁰ are:

1. Compute the dissimilarity matrix by using a particular distance metric.

2. Assign each data point to a cluster.

3. Merge the clusters based on a linkage criterion for the similarity between clusters.

4. Update the distance matrix.

5. Repeat steps 3 and 4 until a single cluster remains or any stop criterion is met.

The principles behind divisive hierarchical clustering were developed by Macnaughton-Smith and others¹¹ in 1964 and explored further by Kaufman and Rousseeuw with their DIANA (Divisive ANAlysis clustering) algorithm¹² in 1990. Divisive clustering uses the opposite approach to agglomerative clustering. All data points start in a single cluster that is repeatedly split into more clusters. Splitting occurs until either all the remaining clusters are singletons or a stop criterion such as a predefined number of clusters is met. Divisive methods are better at identifying large clusters¹³ and can be more accurate than agglomerative methods because the algorithm considers the entire dataset distribution from the start of the process.

To improve efficiency, divisive methods use flat clustering algorithms such as k-means to split the dataset into clusters. The number of clusters must be specified upfront. The k-means algorithm splits clusters by minimizing the within-cluster sum of squares between centroid points. This is known as the inertia criterion¹⁴. The divisive clustering steps¹⁵ are:

1. Start with all data points for a dataset size N (d1, d2, d3 ... dN) in one cluster.

2. Split the cluster into two dissimilar or heterogeneous clusters by using a flat clustering method such as the k-means algorithm.

3. Repeat step 2, choosing the best cluster to split and removing the outliers from the least cohesive cluster after each iteration.

4. Stop when each example is in its own single cluster, otherwise repeat step 3.

Cluster results are typically presented in a dendrogram (binary tree structure). The x-axis in the dendrogram represents the data points and the y-axis, or the height of the lines, shows how far apart the clusters were when they were merged.

You can use a dendrogram to decide how many clusters¹⁶ will be in your final clustering model. One strategy is identifying the natural cutoff point in the tree where the branches dwindle and become longer. Alternatively, the number of clusters is given by the number of vertical lines crossed when a horizontal line cuts the dendrogram.

In the example image shown here, the horizontal line H1 cuts two vertical lines. This shows that there are two clusters at this point in the process—one cluster with points 5, 8, and 2 and one cluster with the remaining points. The further the horizontal line can move up or down without cutting other horizontal lines in the dendrogram, the better the selection of this number of clusters is for your clustering model. In the example below, the horizontal line H2 selects four clusters. H2 is not able to move up and down as far as H1 before it cuts other horizontal lines. This scenario shows that the two-cluster choice (H1) is probably more appropriate for your clustering model.

A robust clustering model¹⁷ creates clusters with high intraclass similarity and low interclass similarity. However, it can be difficult to define cluster quality, and your selection of linkage criterion and cluster numbers can significantly impact your results. Thus, when building a clustering model, try out different options and select those that best help you explore and reveal patterns in the dataset for future consideration. Factors to consider¹⁸ include:

- The number of clusters that are practical or logical for the dataset (given dataset size, cluster shapes, noise and so on)

- Statistics, such as the mean, maximum and minimum values for each cluster

- The best dissimilarity metric or linkage criterion to apply

- The impact of any outliers or outcome variables

- Any specific domain or dataset knowledge

Other methods to help determine the optimal number of clusters¹⁹ include:

- The elbow method, where you plot the within-cluster sum of squares against the number of clusters and determine the "elbow" (the point where the plot levels off)

- Gap statistic, where you compare the actual within-cluster sum of squares to the expected within-cluster sum of squares for a null reference distribution and identify the largest gap.

Hierarchical clustering provides data scientists with insights into the structure and relationships within datasets and it can be applied in various use cases.

Hierarchical clustering can help analyze trends and segment customer data—-for example, grouping by product choice, demographic, purchasing behavior, risk profile or interactions with social media.

Patient cohorts for clinical research can run into the thousands. Hierarchical clustering helps categorize mixed populations into more homogeneous groups²⁰ by using, for example, diagnostic criteria, physiological responses or DNA mutations. It can also be applied to group species by biological features to understand evolutionary development.

Hierarchical clustering is used in image-based text recognition applications to group handwritten characters by their shape. It is also used to store and retrieve information by using certain criteria or to categorize search results.

Both Python and the R programming language are widely used in data science. Python is flexible and can handle a broad spectrum of tasks. Alternatively, R is specifically designed for statistical computing and provides rich options for visualizing your hierarchical clustering analysis.

Python provides the AgglomerativeCluster function²¹ (see also agglomerative clustering examples²² on sklearn), and SciPy provides a function to plot dendrograms²³. Packages such as dendextend²⁴ enhance R's dendrogram functionality, improving sensitivity analysis and enabling you to compare and manipulate different dendrograms. For a hands-on experience, check out our step-by-step tutorials: how to implement hierarchical clustering in Python and how to implement hierarchical clustering in R.