Data Science

HAC: Hierarchical Agglomerative Clustering. Is It Better Than K-Means?

A detailed look into the HAC algorithm together with Python code and several useful charts

Saul Dobilas
May 9, 20219 min read

Machine Learning

HAC: Hierarchical Agglomerative Clustering - Is It Better Than K-Means?

Hierarchical Agglomerative Clustering (HAC). Image by author.
Hierarchical Agglomerative Clustering (HAC). Image by author.

Intro

If you want to be a successful Data Scientist, it is essential to understand how different Machine Learning algorithms work.

This story is part of the series that explains the nuances of each algorithm and provides a range of Python examples to help you build your own ML models.

The story covers the following topics:

  • The category of algorithms Hierarchical Agglomerative Clustering (HAC) belongs to.

  • Details of how the HAC algorithm works.

  • Python example, which uses HAC to cluster Australian cities.

What category of algorithms does Hierarchical Agglomerative Clustering belong to?

The answer is hidden in its name. Since HAC is a clustering algorithm, it sits under the Unsupervised branch of Machine Learning.

Unsupervised techniques, in particular clustering, are often used for segmentation analysis or as a starting point in more complex projects that require an understanding of similarities between data points (e.g., customers, products, behaviors).

The below chart is my attempt to categorize a wide range of different algorithms. In many cases, an algorithm can be used to solve multiple types of problems. E.g., I placed Neural Networks in a category of their own due to their unique approach to Machine Learning. However, NNs can be used in a wide array of problems such as classification, regression, or as a component of reinforcement learning.

The below graph is interactive, so please click on different categories to enlarge and reveal more👇 .

If you enjoy Data Science and Machine Learning, please subscribe to get an email whenever I publish a new story.

How does the Hierarchical Agglomerative Clustering (HAC) algorithm work?

The basics

HAC is not as well-known as K-Means, but it is quite flexible and often easier to interpret. It uses a "bottom-up" approach, which means that each observation starts in its own cluster, and pairs of clusters are merged as one moves up the hierarchy.

To help illustrate this, I have created a few graphs. The first one demonstrates how the algorithm merges closest points one step at a time until there is only one cluster remaining.

Hierarchical Agglomerative Clustering (HAC) in action. Image by author.
Hierarchical Agglomerative Clustering (HAC) in action. Image by author.

Note, the above implementation of HAC uses 'average' linkage, which I will explain later in this section.

The second graph is known as a Dendrogram. It gives the full picture of the path taken, moving from all individual points (bottom of the graph) to one single point/cluster (top of the graph).

Hierarchical Agglomerative Clustering (HAC) Dendrogram. Image by author.
Hierarchical Agglomerative Clustering (HAC) Dendrogram. Image by author.

Note, I have added a dotted horizontal line to indicate the number of clusters I have selected. In general, a good rule of thumb is to identify the largest section within the y-axis where you do not have vertical lines intersected by any horizontal lines. Let me explain further.

The value on the y-axis is the measure of closeness between points/clusters. The horizontal lines denote places where those points/clusters are being merged.

The above graph indicates that you may want to consider having 2 clusters since the largest distance with no cluster mergers is between 24 and 30 (30–24=6).

However, in this case, I decided to choose 4 clusters instead, which is a slightly less optimal solution (approx. 19.5–14.5=5). Hence, my clusters are red, bright green, blue, and Norfolk Island that sits in the corner on its own.

Here is what the clusters look like on a map:

Australian city clustering with the HAC algorithm. Image by author.
Australian city clustering with the HAC algorithm. Image by author.

Linkage types

There are multiple ways to link the points together. I used 'average' linkage in the above example since it is easy to illustrate and understand. However, it is important to familiarize yourself with other linkage types too. Note, Python section at the end of this article will show you how to specify which linkage method you want to use.

  • 'Average': uses the average of the distances of each observation of the two sets, i.e., finds the mid-point between observations (as shown in the graphs).

  • 'Single': uses the minimum of the distances between all observations of the two sets, i.e., looks for the closest point within the cluster of points at that stage (instead of cluster mid-point used in 'average').

  • 'Complete' or 'Maximum': uses the maximum distance between all observations of the two sets. E.g., if the point is closer to the farthest point of Cluster A than the farthest point of Cluster B, then such a point would be added to Cluster A.

  • 'Ward': minimizes the variance of the clusters being merged. This is very similar to minimizing Within Cluster Sum of Squares (WCSS) used by K-Means.

'Ward' linkage is typically the one that is used most often. It is also the default option for sklearn's implementation of HAC, which we will explore in the Python section below.

HAC advantage over K-Means clustering

The attractive part of using HAC is the ability to analyze dendrogram, which provides an insight into the similarity level between any two data points.

It only takes one glance at a dendrogram to see that Pearce, Bullsbrook is very 'distant' from Norfolk Island, while Sydney and Sydney Airport are quite close together. While this is fairly obvious given our location data, it becomes very beneficial when we use more abstract attributes.

In general, you can generate very similar clusters using HAC and K-Means, but having the ability to see the path of each data point, makes HAC more useful in analyzing similarities and differences between individual data points or clusters.

Hierarchical Agglomerative Clustering (HAC) in Python using Australian city location data

Setup

We will use the following data and libraries:

Let's import all the libraries:

python
from sklearn.cluster import AgglomerativeClustering # For HAC clusteringimport scipy.cluster.hierarchy as sch # For HAC Denddrogramimport matplotlib.pyplot as plt # for data visualizationimport plotly.graph_objects as go # for data visualizationimport pandas as pd # for data manipulationfrom geopy.geocoders import Nominatim # for getting city coordinatesfrom progressbar import ProgressBar # for displaying progress import time # for adding time delays

Then we get the Australian weather data from Kaggle, which you can download following this link: https://www.kaggle.com/jsphyg/weather-dataset-rattle-package.

We ingest the data and derive a few new variables, such as Location2, which has the right format to extract city coordinates using Geopy.

python
# Set Pandas options to display more columnspd.options.display.max_columns=50# Read in the weather data csvdf=pd.read_csv('weatherAUS.csv', encoding='utf-8')# Drop records where target RainTomorrow=NaNdf=df[pd.isnull(df['RainTomorrow'])==False]# For other columns with missing values, fill them in with column meandf=df.fillna(df.mean())# Add spaces between multiple words in location namesdf['Location2']=df['Location'].str.replace( r"([A-Z])", r" 1").str.strip()# Update Location for Pearce RAAF so it can be found by geolocatordf['Location2']=df['Location2'].apply(lambda x: 'Pearce, Bullsbrook' if x=='Pearce R A A F' else x)# Show a snaphsot of datadf
A snippet of Kaggle's Australian weather data with some modifications. Image by author.
A snippet of Kaggle's Australian weather data with some modifications. Image by author.

Since our original data only contains location (city) names and not coordinates, we will use Geopy's Nominatim to get those coordinates. Note that we add a sleep time of 1 second between each call not to overload the server.

python
# Create a list of unique locations (cities)loc_list=list(df.Location2.unique())geolocator = Nominatim(user_agent="add-your-agent-name")country ="Australia"loc_res=[]pbar=ProgressBar() # This will help us to show the progress of our iterationfor city in pbar(loc_list):    loc = geolocator.geocode(city+','+ country)    res = [city, loc.latitude, loc.longitude]    loc_res = loc_res + [res]    time.sleep(1) # sleep for 1 second before submitting the next query# Add locations to a dataframedf_loc=pd.DataFrame(loc_res, columns=['Loc', 'Latitude', 'Longitude'])# Show datadf_loc

And this is the snippet of what we get in return:

Australian city coordinates. Image by author.
Australian city coordinates. Image by author.

Let's plot the cities on a map:

python
# Create a figurefig = go.Figure(data=go.Scattergeo(        lat=df_loc['Latitude'],        lon=df_loc['Longitude'],        hovertext=df_loc['Loc'],         mode = 'markers',        marker_color = 'black',        ))# Update layout so we can zoom in on Australiafig.update_layout(        width=980,        height=720,        margin={"r":0,"t":10,"l":0,"b":10},        geo = dict(            scope='world',            projection_type='miller',            landcolor = "rgb(250, 250, 250)",            center=dict(lat=-25.69839, lon=139.8813), # focus point            projection_scale=6 # zoom in on        ),    )fig.show()
Australian cities on a map. Image by author.
Australian cities on a map. Image by author.

HAC clustering - dendrogram

To decide on the number of clusters, we will first draw a dendrogram like the one we have analyzed earlier. Note, we will draw two of them, one using 'average' linkage and another using 'ward' linkage so you can see the difference in the results.

Average linkage:

python
# Select attributesX = df_loc[['Latitude', 'Longitude']]# Create a figureplt.figure(figsize=(16,9), dpi=300)# Create linkageZ = sch.linkage(X, method='average', optimal_ordering=True) # note we use method='average'# Specify cluster colorssch.set_link_color_palette(['red', '#34eb34', 'blue', '#ae34eb'])# Draw a dendrogramsch.dendrogram(Z, leaf_rotation=90, leaf_font_size=10, labels=list(df_loc['Loc']),                color_threshold=14.55, above_threshold_color='black')# Add horizontal lineplt.axhline(y=14.55, c='grey', lw=1, linestyle='dashed')# Show the plotplt.show()
HAC dendrogram using average linkage (same as above). Image by author.
HAC dendrogram using average linkage (same as above). Image by author.

Ward linkage:

python
# Select attributesX = df_loc[['Latitude', 'Longitude']]# Create a figureplt.figure(figsize=(16,9), dpi=300)# Create linkageZ = sch.linkage(X, method='ward', optimal_ordering=True) # note, we use method='ward'# Specify cluster colorssch.set_link_color_palette(['red', '#34eb34', 'blue', '#ae34eb'])# Draw a dendrogramsch.dendrogram(Z, leaf_rotation=90, leaf_font_size=10, labels=list(df_loc['Loc']),                color_threshold=25, above_threshold_color='black')# Add horizontal lineplt.axhline(y=25, c='grey', lw=1, linestyle='dashed')# Show the plotplt.show()
HAC dendrogram using ward linkage. Image by author.
HAC dendrogram using ward linkage. Image by author.

As you can see, we get quite different results when using the 'ward' linkage. The previous blue cluster has been split into two, and lonely Norfolk Island has been merged into the purple cluster.

HAC clustering - generating cluster labels

Since we have decided to have 4 clusters, let's run the scikit learn's HAC algorithm to generate cluster labels for both 'average' and 'ward' linkage methods.

python
# Set the model and its parameters# note, options for linkage: {'ward', 'complete', 'average', 'single'}, default='ward'modela4 = AgglomerativeClustering(n_clusters=4, affinity='euclidean', linkage='average')modelw4 = AgglomerativeClustering(n_clusters=4, affinity='euclidean', linkage='ward')# Fit HAC on our dataclusta4 = modela4.fit(X)clustw4 = modelw4.fit(X)# Attach cluster labels back to the location datasetdf_loc['Clusta4']=clusta4.labels_df_loc['Clustw4']=clustw4.labels_# Print datadf_loc
A snippet of location data with cluster labels attached. Image by author.
A snippet of location data with cluster labels attached. Image by author.

Finally, let's draw the results on a map.

Average linkage:

python
# Create a figurefig = go.Figure(data=go.Scattergeo(        lat=df_loc['Latitude'],        lon=df_loc['Longitude'],        hovertext=df_loc[['Loc', 'Clusta4']],         mode = 'markers',        marker=dict(colorscale=['#34eb34', 'blue', '#ae34eb', 'red']),        marker_color = df_loc['Clusta4'],        ))# Update layout so we can zoom in on Australiafig.update_layout(        showlegend=False,        width=980,        height=720,        margin={"r":0,"t":10,"l":0,"b":10},        geo = dict(            scope='world',            projection_type='miller',            landcolor = "rgb(250, 250, 250)",            center=dict(lat=-25.69839, lon=139.8813), # focus point            projection_scale=6 # zoom in on        ),    )fig.show()
HAC clustering of Australian cities using average linkage (same as above). Image by author.
HAC clustering of Australian cities using average linkage (same as above). Image by author.

Ward linkage:

To plot clusters using 'ward,' we use the same Python code as above, except we change 'Clusta4' with 'Clustw4' in rows 5 and 8.

HAC clustering of Australian cities using ward linkage. Image by author.
HAC clustering of Australian cities using ward linkage. Image by author.

Conclusion

The nice thing about Hierarchical Agglomerative Clustering is that it gives you visibility on the proximity of all the data points through a dendrogram. This becomes even more important when you take your clustering to multi-dimensional space by using more than two attributes.

To summarize, I want to reiterate what I said in my K-Means article: clustering is rarely the end of your analysis; often, it is just the beginning. Hence, make sure to explore how you can use your newly created clusters to improve your understanding of the data and see how it can aid the development of other types of models.

Have fun using HAC in your projects, and feel free to let me know if you have any questions or suggestions!

Cheers! 👏 Saul Dobilas


If you liked this article, you might also enjoy a detailed explanation of the inner workings of other types of clustering algorithms:

K-Means Clustering - A Comprehensive Guide to Its Successful Use in Python

DBSCAN Clustering Algorithm - How to Build Powerful Density-Based Models

GMM: Gaussian Mixture Models - How to Successfully Use It to Cluster Your Data?

Related Articles