Hierarchical clustering

No account yet ?

Hierarchical clustering is another clustering algorithm, which creates a tree-like structure.

This structure is called a dendrogram.

This type of clustering can be divided into two categories:

hierarchical top-down classifications, all points are first assigned to the same group then, when the model is refined, the points are separated into clusters until there is one cluster for each point.

Hierarchical ascending classifications, each point starts by being considered as its own group then, when the model is refined, pairs of clusters are combined, according to their similarities, into a large group containing all the observations.

As with the K-means method, distance measurements are used to assess the similarity between points.

There are four main methods for measuring similarity:

Single linkage

In this method, the distance between two clusters corresponds to the minimum distance between two points of each cluster

Complete linkage

In this second method, the distance between two clusters corresponds to the maximum distance between two points of each cluster.

Average linkage

In this third method, the distance between two clusters corresponds to the average of the distances between all the pairs of points in each group.

Ward's linkage

In this fourth method, the distance between two clusters corresponds to the increase in the sum of squares, after each cluster has been combined.

The goal is to minimize the total variance between clusters.

In these four methods, the Euclidean distance is the most used evaluation measure to calculate the distances between points.

Tested in Anaconda and Python 3.7

import numpy as np
from matplotlib import pyplot as plot
from scipy.cluster.hierarchy import dendrogram
from sklearn.datasets import load_iris
from sklearn.cluster import AgglomerativeClustering
 
 
def plot_dendrogram(model, **kwargs):
 
    count = np.zeros(model.children_.shape[0])
    nsamples = len(model.labels_)
    for i, merge in enumerate(model.children_):
        currentcount = 0
        for child_idx in merge:
            if child_idx < nsamples:
                currentcount += 1  
            else:
                currentcount += count[child_idx - nsamples]
        count[i] = currentcount
 
    linkagematrix = np.column_stack(
        [model.children_, model.distances_, count]
    ).astype(float)
 
    dendrogram(linkagematrix, **kwargs)
 
 
iris = load_iris()
X = iris.data
 
model = AgglomerativeClustering(distance_threshold=0, n_clusters=None)
 
model = model.fit(X)
plot.title("Hierarchical Clustering Dendrogram")
plot_dendrogram(model, truncate_mode="level", p=3)
plot.xlabel("Number of points in node (or index of point if no parenthesis).")