Regroupement Hiérarchique

Le clustering agglomératif est un algorithme de clustering hiérarchique utilisé en apprentissage automatique et en fouille de données : il regroupe des points de données similaires en clusters imbriqués en fonction de leurs distances par paires. L'algorithme se compose de trois étapes différentes :

Étape 1. Faire de chaque point de données un cluster ;

Étape 2. Prenez les deux clusters les plus proches et faites-en un seul cluster;

Étape 3. Répétez l'étape 2 jusqu'à ce qu'il n'y ait plus qu'un seul cluster;

Mais comment effectuer le regroupement si le résultat est toujours un seul cluster ? Contrairement à d'autres algorithmes de clustering qui nécessitent de spécifier le nombre de clusters à l'avance, le clustering hiérarchique produit une structure arborescente hiérarchique appelée dendrogramme qui permet de déterminer le nombre de clusters après le processus de clustering.

Dendrogramme est un diagramme qui montre la relation hiérarchique entre les objets. Ainsi, en utilisant le dendrogramme, nous pouvons suivre avec quelle séquence quels clusters sont combinés pendant l'exécution de l'algorithme. Et c'est avec l'aide du dendrogramme que le nombre optimal de clusters dans lesquels nos données peuvent être divisées est déterminé :

Identifier la ligne verticale la plus longue : Recherchez la ligne la plus longue qui ne croise pas les lignes horizontales dans le dendrogramme. Cela représente la plus grande distance entre deux clusters dans le jeu de données ;
Dessiner une ligne horizontale : Tracez une ligne horizontale à travers la ligne verticale la plus longue identifiée à l'étape 2 (la ligne pointillée rouge dans l'image ci-dessous). Cette ligne est tracée à une hauteur où les branches du dendrogramme sont relativement longues et claires, indiquant une séparation naturelle entre les clusters ;
Le nombre de clusters sera déterminé par le nombre de fois que la ligne horizontale intersecte le dendrogramme.

Remarque

Même avec un dendrogramme, il peut y avoir plusieurs options pour diviser les données en clusters : le nombre de clusters le plus approprié peut être défini en combinant un dendrogramme avec des connaissances du domaine.

Remarque

Dans l'algorithme agglomératif, nous pouvons également prédéfinir le nombre de clusters. Dans ce cas, le dendrogramme sera divisé en clusters de manière à ce que le nombre de clusters dans le résultat soit le même que celui donné a priori.

Un paramètre très important de l'algorithme est le linkage : la méthode utilisée pour calculer la distance entre deux clusters. Il existe plusieurs méthodes de linkage qui peuvent être utilisées, notamment :

Single Linkage : Cette méthode calcule la distance entre deux clusters comme la distance la plus courte entre deux points quelconques dans les deux clusters ;
Complete Linkage : Cette méthode calcule la distance entre deux clusters comme la distance la plus longue entre deux points quelconques dans les deux clusters ;
Average Linkage : Cette méthode calcule la distance entre deux clusters comme la distance moyenne entre toutes les paires de points dans les deux clusters.

Enfin, examinons l'implémentation Python du clustering agglomératif :


              123456789101112131415161718192021
            
from sklearn.cluster import AgglomerativeClustering
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
# Firstly, we will create our dataset
X, y = make_blobs(n_samples=500, cluster_std=1, centers=4, random_state=170)
transformation = [[0.6, -0.6], [-0.4, 0.8]]
X_aniso = np.matmul(X, transformation)

# In this line we will specify parameters of our Agglomerative model
agglomerative = AgglomerativeClustering(linkage='single',
                                        distance_threshold=0.6, n_clusters=None)
# Training our model
agglomerative.fit(X_aniso)

# Providing visualization of results
fig, axes=plt.subplots(1,2)
axes[0].scatter(X[:, 0], X[:, 1], c=agglomerative.labels_, s=50, cmap='tab20b')
axes[0].set_title('Clustered data')
axes[1].scatter(X[:, 0], X[:, 1], c=y, s=50, cmap='tab20b')
axes[1].set_title('Real data')

Dans le code ci-dessus, nous utilisons la classe AgglomerativeClustering pour créer un modèle, où :

Le paramètre linkage détermine le type de liaison : 'complete', 'average', 'single' ;
distance_threshold est le seuil de distance de liaison au-dessus duquel les clusters ne seront pas fusionnés.

Remarque

La classe AgglomerativeClustering n'a pas d'implémentation pour la méthode .predict() : nous devons entraîner le modèle à chaque fois que nous voulons regrouper de nouvelles données.

Tout était clair ?

Merci pour vos commentaires !

Section 2. Chapitre 3