hierarchical clustering is an unsupervised learning method used to group similar data points into clusters based on their distance or similarity. instead of choosing the number of clusters in advance, it builds a tree-like structure called a dendrogram that shows how clusters merge or split at different levels. it helps identify natural groupings in data and is commonly used in pattern recognition, customer segmentation, gene analysis and image grouping.

imagine we have four fruits with different weights: an apple (100g), a banana (120g), a cherry (50g) and a grape (30g). hierarchical clustering starts by treating each fruit as its own group.

start with each fruit as its own cluster.
merge the closest items: grape (30g) and cherry (50g) are grouped first.
next, apple (100g) and banana (120g) are grouped.
finally, these two clusters merge into one.

finally all the fruits are merged into one large group, showing how hierarchical clustering progressively combines the most similar data points.

dendrogram

a dendrogram is like a family tree for clusters. it shows how individual data points or groups of data merge together. the bottom shows each data point as its own group and as we move up, similar groups are combined. the lower the merge point, the more similar the groups are. it helps us see how things are grouped step by step.

at the bottom of the dendrogram the points p, q, r, s and t are all separate.
as we move up, the closest points are merged into a single group.
the lines connecting the points show how they are progressively merged based on similarity.
the height at which they are connected shows how similar the points are to each other; the shorter the line the more similar they are

types of hierarchical clustering

now we understand the basics of hierarchical clustering. there are two main types of hierarchical clustering.

agglomerative clustering
divisive clustering

1. hierarchical agglomerative clustering

it is also known as the bottom-up approach or hierarchical agglomerative clustering (hac). bottom-up algorithms treat each data as a singleton cluster at the outset and then successively agglomerate pairs of clusters until all clusters have been merged into a single cluster that contains all data.

hierarchical agglomerative clustering - geeksforgeeks — hierarchical agglomerative clustering

workflow for hierarchical agglomerative clustering

start with individual points: each data point is its own cluster. for example if we have 5 data points we start with 5 clusters each containing just one data point.
calculate distances between clusters: calculate the distance between every pair of clusters. initially since each cluster has one point this is the distance between the two data points.
merge the closest clusters: identify the two clusters with the smallest distance and merge them into a single cluster.
update distance matrix: after merging we now have one less cluster. recalculate the distances between the new cluster and the remaining clusters.
repeat steps 3 and 4: keep merging the closest clusters and updating the distance matrix until we have only one cluster left.
create a dendrogram: as the process continues we can visualize the merging of clusters using a tree-like diagram called a dendrogram. it shows the hierarchy of how clusters are merged.

implementation

let's see the implementation of agglomerative clustering,

start with each data point as its own cluster.
compute distances between all clusters.
merge the two closest clusters based on a linkage method.
update the distances to reflect the new cluster.
repeat merging until the desired number of clusters or one cluster remains.
the dendrogram visualizes these merges as a tree, showing cluster relationships and distances.

python

import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import agglomerativeclustering
from scipy.cluster.hierarchy import dendrogram
from sklearn.datasets import make_blobs

x, _ = make_blobs(n_samples=30, centers=3, cluster_std=10, random_state=42)

clustering = agglomerativeclustering(n_clusters=3)
labels = clustering.fit_predict(x)

agg = agglomerativeclustering(distance_threshold=0, n_clusters=none)
agg.fit(x)


def plot_dendrogram(model, **kwargs):
    counts = np.zeros(model.children_.shape[0])
    n_samples = len(model.labels_)

    for i, merge in enumerate(model.children_):
        current_count = 0
        for child_idx in merge:
            if child_idx < n_samples:
                current_count += 1
            else:
                current_count += counts[child_idx - n_samples]
        counts[i] = current_count

    linkage_matrix = np.column_stack(
        [model.children_, model.distances_, counts]).astype(float)
    dendrogram(linkage_matrix, **kwargs)


fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(14, 6))

ax1.scatter(x[:, 0], x[:, 1], c=labels, cmap='viridis', s=70)
ax1.set_title("agglomerative clustering")
ax1.set_xlabel("feature 1")
ax1.set_ylabel("feature 2")

plt.sca(ax2)
plot_dendrogram(agg, truncate_mode='level', p=5)
plt.title("hierarchical clustering dendrogram")
plt.xlabel("sample index")
plt.ylabel("distance")

plt.tight_layout()
plt.show()

output :

2. hierarchical divisive clustering

divisive clustering is also known as a top-down approach. top-down clustering requires a method for splitting a cluster that contains the whole data and proceeds by splitting clusters recursively until individual data have been split into singleton clusters.

workflow for hierarchical divisive clustering :

start with all data points in one cluster: treat the entire dataset as a single large cluster.
split the cluster: divide the cluster into two smaller clusters. the division is typically done by finding the two most dissimilar points in the cluster and using them to separate the data into two parts.
repeat the process: for each of the new clusters, repeat the splitting process: choose the cluster with the most dissimilar points and split it again into two smaller clusters.
stop when each data point is in its own cluster: continue this process until every data point is its own cluster or the stopping condition (such as a predefined number of clusters) is met.

untitled-diagram-153-1 — divisive clustering

implementation

let's see the implementation of divisive clustering,

starts with all data points as one big cluster.
finds the largest cluster and splits it into two using kmeans.
repeats splitting the largest cluster until reaching the desired number of clusters.
assigns cluster labels to each data point based on the splits.
returns history of clusters at each step and final labels.
visualizes data points colored by their final cluster.

python

import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import kmeans
from sklearn.datasets import make_blobs
from scipy.cluster.hierarchy import dendrogram, linkage

x, _ = make_blobs(n_samples=30, centers=5, cluster_std=10, random_state=42)


def divisive_clustering(data, max_clusters=3):
    while len(clusters) < max_clusters:
        cluster_to_split = max(clusters, key=lambda x: len(x))
        clusters.remove(cluster_to_split)

        kmeans = kmeans(n_clusters=2, random_state=42).fit(cluster_to_split)
        cluster1 = cluster_to_split[kmeans.labels_ == 0]
        cluster2 = cluster_to_split[kmeans.labels_ == 1]

        clusters.extend([cluster1, cluster2])
    return clusters


clusters = divisive_clustering(x, max_clusters=3)

plt.figure(figsize=(12, 5))

plt.subplot(1, 2, 1)
colors = ['r', 'g', 'b', 'c', 'm', 'y']
for i, cluster in enumerate(clusters):
    plt.scatter(cluster[:, 0], cluster[:, 1], s=50,
                c=colors[i], label=f'cluster {i+1}')
plt.title('divisive clustering result')
plt.legend()

linked = linkage(x, method='ward')

plt.subplot(1, 2, 2)
dendrogram(linked, orientation='top',
           distance_sort='descending', show_leaf_counts=true)
plt.title('hierarchical clustering dendrogram')

plt.tight_layout()
plt.show()

output:

computing distance matrix

while merging two clusters we check the distance between two every pair of clusters and merge the pair with the least distance/most similarity. but the question is how is that distance determined. there are different ways of defining inter cluster distance/similarity. some of them are:

min distance: find the minimum distance between any two points of the cluster.
max distance: find the maximum distance between any two points of the cluster.
group average: find the average distance between every two points of the clusters.
ward's method: the similarity of two clusters is based on the increase in squared error when two clusters are merged.

the image compares cluster distance methods:

min uses the shortest distance between clusters
max uses the longest
group average computes the mean of all pairwise distances
ward’s method minimizes the increase in within-cluster variance during merging

suggested quiz

0 questions

quiz completed successfully

your score : 0/0

accuracy : 0%

comment

article tags:

Save or share this article