Regroupement hiérarchique

Pas encore de compte ?

Le clustering hiérarchique est un autre algorithme de clustering, qui créé une structure s'apparentant à un arbre.

On appelle cette structure un dendrogramme.

Ce type de clustering peut être divisé en deux catégories :

les classifications descendantes hiérarchiques, tous les points commencent par être assignés à un même groupe puis, lorsque le modèle est affiné, les points sont séparés en clusters jusqu'à ce qu'il y est un cluster pour chaque point.

Les classifications ascendantes hiérarchiques, chaque point commence par être considéré comme son propre groupe puis, lorsque le modèle est affiné, des paires de clusters sont combinés, en fonction de leurs similarités, en un grand groupe contenant toutes les observations.

Comme pour la méthode des K-moyennes, les mesures de distances sont utilisées pour évaluer la similarité entre les points.

Il existe quatre principales méthodes pour mesurer la similarité :

Single linkage

Dans cette méthode, la distance entre deux clusters correspond à la distance minimale entre deux points de chaque cluster

Complete linkage

Dans cette deuxième méthode, la distance entre deux clusters correspond à la distance maximale entre deux points de chaque cluster.

Average linkage

Dans cette troisième méthode, la distance entre deux clusters correspond à la moyenne des distances entre toutes les paires de points dans chaque groupe.

Ward's linkage

Dans cette quatrième méthode, la distance entre deux clusters correspond à l'augmentation de la somme des carrés, après que chaque cluster a été combiné.

Le but est de minimiser la variance totale entre clusters.

Dans ces quatre méthodes, la distance Euclidienne est la mesure d'évaluation la plus utilisée pour calculer les distances entre points.

Testé sous Anaconda et 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).")