Clustering Hiérarchique : Guide complet — Principes, Exemples et Implémentation Python

Résumé

Le clustering hiérarchique est l’une des méthodes de classification non supervisée les plus anciennes et les plus intuitives du machine learning. Contrairement au K-Means qui partitionne les données en un nombre fixe de groupes, le clustering hiérarchique construit une représentation arborescente de toutes les partitions possibles, du niveau le plus fin (chaque observation forme son propre cluster) au niveau le plus grossier (toutes les observations fusionnent en un seul groupe). Cette structure s’appelle un dendrogramme et constitue l’élément caractéristique de la méthode.

Ce guide couvre le principe mathématique complet, les différentes stratégies de calcul de distance entre clusters (Ward, lien simple, lien complet, moyenne), l’implémentation pratique avec scipy et scikit-learn, ainsi que les avantages, limites et cas d’usage concrets.

Principe mathématique

Le clustering hiérarchique se décline en deux approches fondamentales qui diffèrent par leur direction de construction.

Approche agglomérative (bottom-up)

C’est l’approche de loin la plus utilisée en pratique. Le processus commence avec chaque observation dans son propre cluster, soit n clusters pour n données. À chaque étape, on identifie les deux clusters les plus proches et on les fusionne. On répète ce processus jusqu’à ce que toutes les observations soient regroupées en un seul cluster. Cela produit exactement n − 1 fusions et un dendrogramme complet.

Algorithmiquement :

1. Initialisation : chaque point xᵢ forme un singleton Cᵢ = {xᵢ}.
2. Calculer la matrice de proximité D entre toutes les paires de clusters.
3. Trouver la paire (Cᵢ, Cⱼ) minimisant D(Cᵢ, Cⱼ).
4. Fusionner Cᵢ et Cⱼ en un nouveau cluster.
5. Mettre à jour la matrice de distances.
6. Répéter de l’étape 3 jusqu’à obtenir un seul cluster.

La complexité naïve est en O(n³) temps et O(n²) mémoire, car il faut calculer et maintenir une matrice de distances de taille n × n. Des optimisations comme l’algorithme de SLINK atteignent O(n²) pour le lien simple.

Approche divisive (top-down)

L’approche divisive fonctionne à l’inverse : on commence avec toutes les observations dans un seul cluster et on divise récursivement le cluster le plus hétérogène jusqu’à obtenir n clusters singleton. Cette approche est beaucoup plus coûteuse (complexité exponentielle dans le cas général) et nécessite des heuristiques pour être applicable, comme l’utilisation du K-Means avec K=2 à chaque étape de division.

Distance entre clusters : les méthodes de liaison

La question centrale du clustering hiérarchique est : comment mesurer la distance entre deux clusters ? Chaque cluster contient potentiellement plusieurs points, et il existe plusieurs façons de définir cette distance inter-clusters. Ces choix sont appelés méthodes de liaison (linkage methods).

Liaison simple (Single Linkage)

La distance entre deux clusters est la distance minimale entre une paire de points, l’un dans chaque cluster :

D_single(Cᵢ, Cⱼ) = min{ d(x, y) | x ∈ Cᵢ, y ∈ Cⱼ }

Cette méthode tend à créer des clusters allongés et en chaîne, car il suffit qu’un seul pont de points rapprochés relie deux groupes pour les considérer comme un seul cluster. C’est ce qu’on appelle l’effet de chaînage (chaining effect). Elle est sensible au bruit mais excellente pour détecter des structures non globulaires.

Liaison complète (Complete Linkage)

La distance entre deux clusters est la distance maximale entre une paire de points :

D_complete(Cᵢ, Cⱼ) = max{ d(x, y) | x ∈ Cᵢ, y ∈ Cⱼ }

Cette approche favorise des clusters compacts et de diamètre réduit, car deux clusters ne fusionnent que si tous leurs points mutuels sont raisonnablement proches. Elle est plus robuste au bruit que le lien simple, mais peut artificiellement séparer des clusters naturels de forme allongée.

Liaison moyenne (Average Linkage / UPGMA)

La distance entre deux clusters est la moyenne de toutes les distances entre paires de points :

D_average(Cᵢ, Cⱼ) = (1 / |Cᵢ| × |Cⱼ|) × Σ d(x, y)  pour x ∈ Cᵢ, y ∈ Cⱼ

C’est un compromis entre les deux méthodes précédentes. Elle est souvent considérée comme un bon choix par défaut car elle évite à la fois le chaînage excessif du lien simple et la trop grande compacité du lien complet.

Critère de Ward (Ward’s Method)

Le critère de Ward est le plus sophistiqué des quatre. Au lieu de mesurer directement la distance entre points, il minimise l’augmentation de l’inertie intra-classe (la somme des carrés des écarts à la moyenne de chaque cluster) résultant de la fusion :

D_ward(Cᵢ, Cⱼ) = (|Cᵢ| × |Cⱼ| / (|Cᵢ| + |Cⱼ|)) × ||μᵢ − μⱼ||²

où μᵢ et μⱼ sont les centroïdes respectifs des deux clusters.

Ward fusionne toujours la paire de clusters dont la réunion augmente le moins la variance intra-cluster globale. Le résultat ressemble à un K-Means hiérarchique : il produit des clusters globulaires de tailles équilibrées. C’est la méthode par défaut dans la plupart des implémentations modernes.

Matrice de distances et construction du dendrogramme

Toutes ces méthodes opèrent sur une matrice de distances à n × n éléments, où chaque entrée D[i, j] représente la distance (euclidienne, Manhattan, cosinus, etc.) entre les observations i et j.

Au fil des fusions, la matrice est mise à jour selon la formule de la méthode de liaison choisie. Chaque étape de fusion est enregistrée avec :

• Les indices des deux clusters fusionnés ;
• La distance à laquelle la fusion s’est produite ;
• Le nombre d’éléments dans le nouveau cluster.

L’ensemble de ces enregistrements forme le dendrogramme, un arbre binaire dont les feuilles sont les observations individuelles et dont les nœuds internes représentent les fusions successives. La hauteur de chaque nœud correspond à la distance de fusion.

Intuition : comprendre le dendrogramme

Imaginez un arbre généalogique inversé. Dans un arbre classique, vous commencez avec des ancêtres lointains et vous descendez vers les générations présentes. Le clustering hiérarchique fait l’inverse : on commence avec chaque point seul (la génération la plus récente) et on remonte dans le temps en fusionnant les groupes les plus proches, jusqu’à trouver un ancêtre commun unique.

Le dendrogramme visualise exactement ce processus. Sur l’axe horizontal, vous voyez les observations (ou des groupes d’observations). Sur l’axe vertical, vous lisez la distance ou la dissimilarité à laquelle chaque fusion s’est produite.

L’avantage décisif du dendrogramme est qu’il ne vous force pas à choisir un nombre de clusters à l’avance. Vous pouvez couper l’arbre à n’importe quelle hauteur :

• Une coupe haute produit peu de clusters, très généraux.
• Une coupe basse produit beaucoup de clusters, très spécifiques.
• Vous pouvez observer visuellement les sauts de hauteur : un grand espace vertical entre deux fusions suggère une frontière naturelle entre des macro-groupes.

C’est cette flexibilité qui rend le clustering hiérarchique si précieux pour l’exploration de données : avant même de choisir un nombre de clusters, vous pouvez voir la structure hiérarchique de vos données.

Implémentation Python

Voyons comment implémenter le clustering hiérarchique en Python, en utilisant à la fois scipy pour la création du dendrogramme et scikit-learn pour l’affectation aux clusters.

Dendrogramme avec scipy

La bibliothèque scipy fournit la fonction linkage pour calculer l’arbre hiérarchique et dendrogram pour le visualiser :

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

# Générer des données synthétiques
X, y_true = make_blobs(
    n_samples=200,
    n_features=2,
    centers=4,
    random_state=42
)

# Calculer le clustering hiérarchique (méthode de Ward)
Z = linkage(X, method='ward', metric='euclidean')

# Afficher le dendrogramme
plt.figure(figsize=(12, 6))
dendrogram(
    Z,
    truncate_mode='level',
    p=10,
    leaf_font_size=9
)
plt.title('Dendrogramme — Clustering Hiérarchique (Ward)')
plt.xlabel('Observations')
plt.ylabel('Distance de fusion')
plt.axhline(
    y=15, color='red', linestyle='--',
    label='Seuil de coupe'
)
plt.legend()
plt.tight_layout()
plt.show()

La ligne rouge horizontale représente un seuil de coupure : toute fusion au-dessus de cette ligne est ignorée, ce qui détermine le nombre final de clusters.

Affectation avec scikit-learn

Pour obtenir les étiquettes de cluster directement, scikit-learn propose AgglomerativeClustering :

from sklearn.cluster import AgglomerativeClustering

# Méthode de Ward
agglo = AgglomerativeClustering(
    n_clusters=4,
    linkage='ward',
    metric='euclidean'
)
labels_ward = agglo.fit_predict(X)

# Visualisation des résultats
plt.figure(figsize=(10, 6))
scatter = plt.scatter(
    X[:, 0], X[:, 1],
    c=labels_ward, cmap='viridis',
    s=40, alpha=0.8, edgecolors='k'
)
plt.colorbar(scatter, label='Cluster')
plt.title('Clusters hiérarchiques — Liaison Ward')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.tight_layout()
plt.show()

Comparaison des méthodes de liaison

Voici comment comparer les quatre méthodes sur les mêmes données :

from sklearn.cluster import AgglomerativeClustering
import matplotlib.pyplot as plt

linkages = ['ward', 'complete', 'average', 'single']

fig, axes = plt.subplots(2, 2, figsize=(14, 10))
axes = axes.ravel()

for i, method in enumerate(linkages):
    if method == 'ward':
        agglo = AgglomerativeClustering(
            n_clusters=4, linkage=method
        )
    else:
        agglo = AgglomerativeClustering(
            n_clusters=4, linkage=method,
            metric='euclidean'
        )
    labels = agglo.fit_predict(X)

    axes[i].scatter(
        X[:, 0], X[:, 1],
        c=labels, cmap='viridis',
        s=35, alpha=0.8, edgecolors='k'
    )
    axes[i].set_title(f'Liaison : {method}')
    axes[i].set_xlabel('Feature 1')
    axes[i].set_ylabel('Feature 2')

plt.suptitle('Comparaison des méthodes de liaison')
plt.tight_layout()
plt.show()

Vous observerez que :

• Ward produit des clusters équilibrés et globulaires, proches de ce que ferait K-Means.
• Complete tend à créer des clusters plus compacts, parfois plus nombreux dans les zones denses.
• Average offre un bon compromis avec des frontières douces.
• Single est le plus susceptible de créer des clusters en chaîne, reliant des groupes éloignés par des ponts de points isolés.

Couper le dendrogramme avec scipy

Si vous travaillez directement avec scipy, la fonction cut_tree permet d’extraire les clusters à un niveau donné :

from scipy.cluster.hierarchy import cut_tree

# Couper pour obtenir exactement 4 clusters
labels = cut_tree(Z, n_clusters=4).ravel()

# Ou couper à une hauteur de distance spécifique
labels_threshold = cut_tree(Z, height=10).ravel()
print(f'Nombre de clusters au seuil 10 : {len(np.unique(labels_threshold))}')

L’approche par hauteur (plutôt que par nombre fixe) est cohérente avec la philosophie hiérarchique : vous définissez le niveau de granularité souhaité, et l’algorithme détermine automatiquement combien de clusters cela produit.

Hyperparamètres

Le clustering hiérarchique possède peu d’hyperparamètres, mais chacun a un impact majeur sur les résultats.

n_clusters (nombre de clusters)

C’est le paramètre principal si vous utilisez AgglomerativeClustering de scikit-learn. Alternative : distance_threshold permet de spécifier une hauteur de coupure dans le dendrogramme au lieu d’un nombre fixe. Si vous utilisez distance_threshold, alors n_clusters doit être fixé à None.

linkage (méthode de liaison)

Le choix entre ward, complete, average et single est le déterminant structurel le plus important. En pratique :

• Ward est le meilleur choix par défaut pour des données numériques sans structure spéciale.
• Average est un bon second choix si Ward ne converge pas (métrique non euclidienne).
• Complete et Single servent surtout à l’exploration pour comprendre la structure des données.

metric (métrique de distance)

La métrique par défaut est la distance euclidienne, mais d’autres sont possibles selon le contexte. Pour du texte, le cosinus est pertinent. Pour des données géographiques, Haversine est approprié. Attention : la méthode de Ward n’est valide qu’avec une métrique euclidienne.

distance_threshold

Plutôt que de fixer un nombre de clusters, vous pouvez définir une distance maximale de fusion. Deux clusters ne fusionnent que s’ils sont à moins de cette distance l’un de l’autre. Cela produit un nombre de clusters qui dépend de la structure naturelle des données.

Avantages et limites

Avantages

• Pas besoin de préciser K à l’avance : le dendrogramme permet d’explorer toutes les granularités possibles.
• Résultat déterministe : contrairement au K-Means qui dépend de l’initialisation aléatoire, le clustering hiérarchique produit toujours le même résultat sur les mêmes données.
• Interprétabilité supérieure : le dendrogramme est un outil de visualisation puissant qui révèle la structure naturelle des données.
• Flexibilité métrique : fonctionne avec n’importe quelle mesure de dissimilarité (euclidienne, Manhattan, cosinus, corrélation, etc.).
• Hiérarchie riche : le résultat n’est pas juste une partition mais une organisation complète à plusieurs niveaux.
• Idéal pour petits datasets : produit d’excellents résultats sur des ensembles de données de taille modérée.

Limites

• Complexité en O(n³) : l’algorithme naïf est très coûteux sur de grands volumes de données. Des variantes optimisées atteignent O(n²), mais cela reste prohibitif au-delà de quelques dizaines de milliers de points.
• Non incrémental : une fois l’arbre construit, ajouter une nouvelle donnée nécessite de recalculer (ou d’utiliser des approximations).
• Sensibilité au bruit et aux outliers : particulièrement vrai pour le lien simple.
• Irréversibilité des fusions : une fois deux clusters fusionnés, la décision est définitive. Une erreur précoce se propage (problème de l’effet cascade).
• Ward exige l’euclidienne : la méthode de Ward ne fonctionne qu’avec la distance euclidienne, ce qui limite sa flexibilité.

4 cas d’usage concrets

1. Taxonomie biologique et classification d’espèces

Le clustering hiérarchique est historiquement né de la biologie systémique. Les phylogénéticiens l’utilisent pour construire des arbres évolutifs à partir de distances génétiques entre espèces. La méthode average linkage (UPGMA) est particulièrement adaptée car elle donne une estimation du temps de divergence entre deux groupes.

2. Analyse de segments clients en marketing

Les équipes marketing l’emploient pour identifier des segments hiérarchiques : d’abord les grandes familles de clients (particuliers vs professionnels), puis les sous-segments (jeunes urbains, familles, retraités…). Le dendrogramme permet de choisir le niveau de segmentation pertinent pour la stratégie commerciale.

3. Clustering de documents et organisation thématique

En traitement du langage naturel, le clustering hiérarchique permet d’organiser des documents en thèmes et sous-thèmes. Par exemple, un corpus d’articles de presse peut être structuré en grandes catégories (politique, économie, sport) puis en sous-catégories (élections, marchés financiers, football…). La similarité cosinus entre vecteurs TF-IDF sert de métrique de distance.

4. Analyse d’images médicales

En imagerie médicale, le clustering hiérarchique est utilisé pour la segmentation d’images. Les pixels sont regroupés selon leur intensité et leur proximité spatiale, créant une hiérarchie de régions qui peut être coupée à différents niveaux selon la finesse de segmentation souhaitée. Cette approche multi-échelle est particulièrement utile pour détecter des lésions de tailles variées.

Voir aussi

• Maîtrisez les Nombres Triffle en Python : Guide Complet pour Développeurs
• Démystifiez le Module ‘abc’ en Python : Guide Complet avec Exemples Pratiques