Implement hierarchical clustering in Python

Clustering is an unsupervised machine-learning technique used in data analysis to detect and group similar objects. Hierarchical cluster analysis (HCA), or hierarchical clustering, is a technique to create a hierarchy of clusters by grouping similar data points.

Hierarchical clustering does not require prior knowledge of the number of clusters, allowing for a more intuitive representation of the relationships between data points. The results of hierarchical clustering are often visualized using a dendrogram, a tree-like diagram that illustrates the merging or splitting of clusters. The main advantage of hierarchical clustering is its flexibility. It can handle different types of data without relying on assumptions about the shape or size of the clusters.

This tutorial is a beginner's guide to implementing the hierarchical clustering algorithm on a real-world data set in Python using Jupyter notebooks on IBM watsonx.ai. This tutorial uses the product classification and clustering data set from the UCI Machine Learning Repository. This data set, collected from PriceRunner, a popular product comparison platform, includes 35,311 product offers from 10 categories provided by 306 merchants. In this tutorial, we'll segregate a selection of 5000 random data points into an optimum number of clusters and then visualize them in terms of category labels.

More on hierarchical clustering

To learn more about hierarchical clustering, consider the different types of hierarchical clustering, the freatures of partial clustering versus hierarchical clustering, and various applications of hierarchical clustering.

Types of hierarchical clustering

There are two main types of hierarchical clustering: agglomerative and divisive. Agglomerative hierarchical clustering, or the bottom-up approach, starts by considering each data point as an individual cluster. It then iteratively merges the closest clusters based on a defined similarity measure until all the data points belong to a single cluster. The linkage methods determine how the similarity between clusters is calculated. This approach creates a hierarchy of clusters, with each level representing a different level of granularity. The choice of similarity measure and linkage method can significantly impact the results of agglomerative hierarchical clustering. Popular similarity measures include the Euclidean distance, Manhattan distance, Minkowski distance, and cosine similarity.

On the other hand, divisive hierarchical clustering, also called top-down clustering, adopts an approach that contrasts with agglomerative clustering. This clustering method starts with all data points belonging to a single cluster and recursively splits the cluster into smaller clusters until each data point forms its own cluster. This process creates a hierarchy of clusters, with each level representing a different level of granularity. Divisive hierarchical clustering can be computationally expensive, especially for large data sets. As with agglomerative clustering, the choice of criterion for cluster splitting can significantly impact the results.

Partitional versus hierarchical clustering

Let's now compare and contrast partial versus hierarchical clustering.

Applications of hierarchical clustering

Hierarchical clustering is versatile and is used across industries as a powerful tool for segmenting data and uncovering hidden structures in diverse data sets. In the retail field, it helps marketers understand customer journeys by segmenting shoppers based on purchasing habits and affinities. This understanding paves the way for targeted campaigns and personalized recommendations. Hierarchical clustering also aids in healthcare diagnosis and resource allocation. This technique reveals clusters with similar symptoms or risk factors, enabling early intervention and customized treatment plans by analyzing patient records. Hierarchical clustering also assists astronomers in cosmic studies.

Prerequisites

You need an IBM Cloud account to create a watsonx.ai project.

Steps

Step 1: Set up your environment

While you can choose from several tools, this tutorial walks you through how to set up an IBM account to use a Jupyter Notebook. Jupyter Notebooks are widely used within data science to combine code, text, images, and data visualizations to formulate a well-formed analysis.

1. Log in to watsonx.ai using your IBM Cloud account.

2. Create a watsonx.ai project.

3. Create a Jupyter Notebook.

This step will open a notebook environment where you can load your data set and copy the code from this tutorial to tackle a simple clustering problem.

Step 2: Install and import relevant libraries

We'll need to install the following libraries for this tutorial:

• pandas to handle the data set.
• NumPy to analyze numerical values.
• scikit-learn to implement machine learning algorithms like clustering.
• SciPy to implement hierarchical clustering without using in-built functions.
• Matplotlib to create visualizations.
• Seaborn to visualize the data set correlation heatmap.

Before moving forward, ensure you have installed all the required libraries on your console. If you haven't done so, install the libraries using the following commands.

#Load required libraries
import pandas as pd
import numpy as np

from sklearn.cluster import AgglomerativeClustering
from scipy.cluster.hierarchy import linkage, cut_tree, dendrogram

import matplotlib.pyplot as plt
import seaborn as sns

Step 3: Load the data set

In this step, we'll first download the data set from the UCI repository and load the file into a pandas data frame. We'll then view the first few rows of the data frame.

The data set can be accessed publicly at the following URL: https://archive.ics.uci.edu/static/public/837/product+classification+and+clustering.zip.

#Prepare the Data

!wget https://archive.ics.uci.edu/static/public/837/product+classification+and+clustering.zip

df = pd.read_csv(\"product+classification+and+clustering.zip\")

#View the first few rows of the data frame
df.head()

The output shows the initial entries of the data set. To explore the data definitions, refer to the product classification and clustering data set.

Step 4: Prepare the data set

To understand the data set further, we'll plot the data description.

#Check data types and column names
df.info()

The output shows that three parameters ("Product Title," "Cluster Label," and "Category Label") have the data type object. These parameters must be converted into numerical values before we can use them for analysis.

#Preprocess the data
df_processed = df.copy()
df_processed\[\'Product Title\'\] = pd.factorize(df\[\'Product Title\'\])\[0\]
df_processed\[\' Cluster Label\'\] = pd.factorize(df\[\' Cluster Label\'\])\[0\]
df_processed\[\' Category Label\'\], categories = pd.factorize(df\[\' Category Label\'\])
#View the processed data
df_processed.head()

Of these parameters, we will retain the mapping for the parameter "Category Label" and the variable "categories" and use it for visualizations later in the tutorial.

   Product ID  Product Title   Merchant ID   Cluster ID   Cluster Label      Category ID   Category Label
0           1              0             1            1               0             2612                0
1           2              1             2            1               0             2612                0
2           3              2             3            1               0             2612                0
3           4              3             4            1               0             2612                0
4           5              4             5            1               0             2612                0

The output shows that the modified data set now only contains numerical values.

Next, let's check for missing values in the data set.

#Print the number of missing values in the data set
missing_values = df_processed.isnull().sum()
missing_values

This will output:

Product ID         0
Product Title      0
 Merchant ID       0
 Cluster ID        0
 Cluster Label     0
 Category ID       0
 Category Label    0
dtype: int64

We can see that there are no missing values in the data set.

Next, we'll plot a correlation heatmap of the data to understand the correlation among the various parameters in the data set.

#Plot a heatmap of the data set
correlation_matrix = df_processed.corr()
sns.heatmap(correlation_matrix, cmap=\'coolwarm\', annot=True)

Here, we see the generated heatmap:

Notice that with the exception of "Merchant ID," all the other parameters have a high correlation with each other. The correlation of "Merchant ID" with all the other parameters is also above 45%, indicating it is not insignificant and shouldn't be ignored. Typically, a correlation value of less than 40% is considered weak.

Step 5: Separate the target and feature sets

With over 35,000 rows, performing hierarchical clustering on the entire data set will be computationally expensive and time-consuming. To reduce the time required and the computational intensity we'll first take a random set of 5,000 data points for analysis.

#Random sampling of 5000 data points
df_feature = df_processed.sample(n=5000, random_state=42)

To control the dimensionality of the analysis, we'll consider only two columns, "Product ID" and "Category Label" as clustering parameters.

#Extract the feature set
df_feature=df_small\[\['Product ID', ' Category Label'\]\]

We will use the data frame, df_feature, for all further analysis.

Step 6: Implement hierarchical clustering

The linkage function in the SciPy library module is a general function for performing agglomerative hierarchical clustering. The linkage method specifies how the distance between clusters is calculated during the merging process. The method parameter in the linkage function determines the linkage method to be used.

In this step, we will use the linkage function to implement ward linkage clustering on the data set. The ward linkage method is the most integrated clustering type available in multiple software packages. It excels in merging a smaller pair of clusters without increasing the in-cluster variance. We'll use the Euclidean distance as the distance metric for clustering.

#Perform hierarchical clustering
hc_ward = linkage(df_feature, method=\"ward\", metric=\"euclidean\")

We can best visualize the outcome of this clustering using a dendrogram. A dendrogram is a tree-like diagram used in hierarchical clustering to represent the arrangement of data points based on their similarity or dissimilarity. It displays the hierarchical relationships between clusters and individual data points by illustrating how they merge or split at different levels of the hierarchy. The plot will have data points on the x-axis and cluster distance on the y-axis. By drawing a horizontal line across the dendrogram, you can identify the number of clusters at that point by counting the number of times it intersects with the vertical lines. We'll draw this line on the dendrogram using the plt.axhline method for a specific value of y.

Note that in this plot the distances between our clusters are very large. The cluster distance at the point of the first cluster is 1,100,000. At the point of 6 clusters where the clusters distances begin to shrunk, it is around 125,000. That's what we pass to plt.axhline to see our potential number of clusters.

#Plot the dendrogram (linkage method 'ward')
plt.figure(figsize=(10,6))
d_ward = dendrogram(hc_ward, leaf_rotation=90, leaf_font_size=10, link_color_func=lambda x: \'black\')
plt.title(\'Ward Linkage Dendrogram\')
plt.xlabel(\'Data Points\')
plt.ylabel(\'Cluster Distance\')

#Plot a horizontal line indicating the clustering point
plt.axhline(y=125000, color=\'r\', linestyle=\'\--\')

In the dendrogram, the vertical lines represent clusters, and the height at which they merge or split indicates the level of similarity or distance between the data points or clusters. The longer the vertical lines, the greater the dissimilarity between the merged clusters.

To compute the optimal number of clusters, observe the height of the vertical lines in the dendrogram and identify the point where the rate of change in height (distance) between the mergers decreases, forming an "elbow." The number of clusters at this point will be considered the optimal number. As is visible from the dendrogram, the optimum number of clusters for this data is six. This can also be identified by plotting the variation in height with respect to the number of clusters.

#Plot the elbow point
distances = hc_ward\[-30:, 2\]
num_clusters = np.arange(31, 1, -1)
plt.plot(num_clusters, distances, marker=\'o\')
plt.plot(6, hc_ward\[-5,2\], color=\'red\', marker=\'o\')
plt.title(\'Identifying the elbow point\')
plt.xlabel(\'Number of clusters\')
plt.ylabel(\'Variation in cluster distance\')

This creates a plot identifying the elbow point:

As visible in the plot, the variation in cluster distances diminishes considerably after the number of clusters reaches 6, as indicated by the red dot. This point is considered the elbow point.

Next, we'll perform cluster analysis. We'll cut the dendrogram using the optimum number of clusters, in our case 6, and assign the cluster label to each data point.

#Cut the dendrogram to form clusters
num_clusters = 6

#Add cluster membership to the original data
cluster_labels = cut_tree(hc_ward, n_clusters=num_clusters).flatten()

Alternate implementation of hierarchical clustering

Another way of implementing agglomerative clustering is by using the AgglomerativeClustering function directly from the sklearn.clustering module. We'll implement ward clustering on the data using the optimum number of clusters identified earlier.

#Fit agglomerative clustering
ac = AgglomerativeClustering(n_clusters= num_clusters, linkage=\'ward\')
cluster_labels = ac.fit_predict(df_feature)

Note that both methods will yield the same results.

Step 7: Visualize the cluster

In this step, to visualize the clusters, we'll plot the variation of "Product ID" versus "Category Label" and color the graph based on the cluster each data point is assigned to. Further, we will use the "Category Label" variable to label the y-axis and identify the pattern of clustering accomplished by the model.

Then, we'll generate a scatterplot to visualize the clusters.

data = np.array(df_feature.values)
#  Scatter plot for the visualizing the clusters
plt.figure(figsize=(12, 6))
for cluster_label in np.unique(cluster_labels):
    cluster_indices = np.where(cluster_labels == cluster_label)
    plt.scatter(data[cluster_indices, 0], data[cluster_indices, 1], s=40, label=f'Cluster {cluster_label}')

plt.yticks(np.arange(len(categories)), categories)
plt.title('Agglomerative Clustering')
plt.xlabel('Product IDs')
plt.ylabel('Category Labels')
plt.legend()

This will generate a scatterplot showing the different clusters plotted based on different categories:

The scatterplot displays the six different clusters, each represented with a unique color. We can observe that the model has merged instances of "Dishwashers" and "Washing Machines," indicating a similarity between these categories. This merge is logical, as both these devices are used for washing. Similarly, "CPUs" and "TVs" have been combined into one cluster. However, observe that the model is confused between the "fridges," "Fridge freezers," and "freezers" categories. This confusion can be fixed with more training data.

Summary

In this tutorial, you learned that hierarchical clustering is an unsupervised learning algorithm that groups data into a tree of nested clusters. There are two main types of hierarchical clustering: agglomerative and divisive.

You learned to implement hierarchical clustering on the product classification and clustering data set. After exploring the data, you found no missing values in the data set. You then plotted a correlation heatmap to understand the correlation among the various parameters. You used two features, "Product ID" and "Category Label," to perform hierarchical clustering on the data. Next, you implemented ward hierarchical clustering on the SciPy and Scikit-learn library functions. You then found the optimal number of clusters to be six using a dendrogram and by plotting the elbow point. Next, you performed cluster analysis, cut the dendrogram using the optimal number of clusters, and assigned the cluster label to each data point. Then, you visualized the clusters by plotting the variation of "Product ID" versus "Category Label." The scatterplot clearly showed the six different clusters.

Try watsonx for free

Build an AI strategy for your business on one collaborative AI and data platform called IBM watsonx, which brings together new generative AI capabilities, powered by foundation models, and traditional machine learning into a powerful platform spanning the AI lifecycle. With watsonx.ai, you can train, validate, tune, and deploy models with ease and build AI applications in a fraction of the time with a fraction of the data.

Try watsonx.ai, the next-generation studio for AI builders.

Next steps

Explore more articles and tutorials about watsonx on IBM Developer.