Clustering hiérarchique

Algorithmes et mises à jour du Hierarchical Clustering : Clustering hiérarchique – Concept complet

Introduction

Le clustering hiérarchique est une famille d’algorithmes de machine learning non supervisé utilisée pour regrouper des données en clusters imbriqués organisés sous forme d’arbre hiérarchique. Cette structure, généralement représentée par un dendrogramme, permet de visualiser les relations entre les groupes à différents niveaux de granularité, du plus fin au plus global.

Contrairement aux méthodes de clustering dites « plates » comme le k-means qui produisent une partition fixe du jeu de données, le clustering hiérarchique construit une hiérarchie complète de partitions possibles. L’utilisateur peut ensuite choisir le nombre de clusters en « coupant » le dendrogramme au niveau souhaité, sans avoir à spécifier ce nombre au départ.

Le clustering hiérarchique est largement utilisé en segmentation client, en bio-informatique et analyse génomique, en reconnaissance d’images, en text mining ou encore pour l’exploration de données marketing. Il s’appuie sur des mesures de distance (ou de dissimilarité) entre objets et sur des critères de liaison (linkage) pour construire l’arbre de clusters.

Dans cet article, nous allons détailler les concepts clés du clustering hiérarchique, les différents types d’algorithmes, les métriques de distance et de similarité, ainsi que les bonnes pratiques pour l’implémenter efficacement en Python (ou dans d’autres environnements), tout en évoquant ses limitations et quelques cas d’usage concrets.

Concepts clés du clustering hiérarchique

Qu'est-ce que le clustering hiérarchique ?

Le clustering hiérarchique est une approche de segmentation qui construit une hiérarchie de clusters à partir d’un ensemble de points de données. Chaque niveau de la hiérarchie correspond à une partition différente du jeu de données, allant d’une situation où chaque point est isolé à une autre où tous les points appartiennent à un unique cluster.

Cette hiérarchie est représentée par un dendrogramme, un diagramme arborescent qui indique à quel niveau de distance (ou de similarité) des clusters sont fusionnés ou divisés. Le dendrogramme est au cœur de l’interprétation du clustering hiérarchique : il permet de voir comment se structurent les données et d’identifier des groupes naturels à différentes échelles.

Contrairement aux méthodes comme le k-means, qui nécessitent de fixer à l’avance le nombre de clusters, le clustering hiérarchique permet de reporter ce choix à la phase d’analyse des résultats. L’analyste peut ainsi tester plusieurs découpes de l’arbre et comparer la cohérence des partitions obtenues.

Approches agglomératives et divisives

On distingue deux grandes familles de clustering hiérarchique :

• Clustering hiérarchique ascendant (agglomératif) : chaque observation commence dans son propre cluster. À chaque étape, on fusionne les deux clusters les plus proches selon une mesure de distance et un critère de liaison choisis. Le processus se poursuit jusqu’à ce qu’il ne reste plus qu’un seul cluster ou qu’un critère d’arrêt soit atteint. C’est l’approche la plus répandue en pratique.
• Clustering hiérarchique descendant (divisif) : on commence avec un seul cluster contenant l’ensemble des observations. À chaque étape, on divise un cluster en deux sous-clusters (souvent en utilisant un algorithme de clustering « plat » comme k-means à l’intérieur de ce cluster). Cette approche est conceptuellement intuitive mais moins couramment implémentée dans les bibliothèques standards.

Les deux approches produisent une structure hiérarchique, mais les étapes intermédiaires (et donc parfois le résultat final pour un nombre donné de clusters) peuvent différer, car la suite de fusions ou de divisions n’est pas nécessairement symétrique.

Dendrogramme et découpe de l’arbre

Le dendrogramme est un outil visuel central du clustering hiérarchique. Il représente :

• les feuilles, qui correspondent aux observations individuelles ;
• les nœuds internes, qui représentent les clusters formés par fusion ou division ;
• la hauteur des branches, qui indique la distance (ou dissimilarité) au moment où deux clusters sont fusionnés.

Pour obtenir une partition en un certain nombre de clusters, on « couppe » le dendrogramme à une hauteur donnée. Toutes les branches situées en dessous de cette hauteur définissent les clusters finaux. On peut ainsi ajuster dynamiquement la granularité de la segmentation sans relancer l’algorithme.

Comparaison avec k-means et autres méthodes

Le clustering hiérarchique présente plusieurs différences importantes par rapport à des méthodes comme k-means :

• Il ne nécessite pas de spécifier le nombre de clusters à l’avance, même si un critère d’arrêt peut être défini.
• Il produit une hiérarchie complète de partitions, et non une seule partition.
• Il peut gérer des formes de clusters non sphériques, là où k-means est mieux adapté à des clusters compacts et de forme à peu près circulaire dans l’espace des features.
• Il est souvent plus coûteux en temps et en mémoire, ce qui le rend moins adapté aux jeux de données très volumineux.

Types de clustering hiérarchique et critères de liaison

Types de clustering hiérarchique

Au-delà de la distinction ascendant / descendant, le clustering hiérarchique se décline en plusieurs variantes selon le critère de liaison utilisé pour calculer la distance entre deux clusters. Ce critère influe fortement sur la forme des clusters obtenus.

Principaux critères de liaison (linkage)

Les méthodes les plus courantes sont les suivantes :

• Single linkage (liaison simple) : la distance entre deux clusters est définie comme la plus petite distance entre un point de l’un et un point de l’autre. Elle tend à produire des clusters en « chaîne » et peut être sensible au bruit.
• Complete linkage (liaison complète) : la distance entre deux clusters est définie comme la plus grande distance entre un point de l’un et un point de l’autre. Elle favorise des clusters plus compacts, mais peut fragmenter des groupes allongés.
• Average linkage (liaison moyenne) : la distance entre deux clusters est la moyenne des distances entre tous les couples de points appartenant aux deux clusters. Elle constitue souvent un compromis entre single et complete linkage.
• Liaison de Ward : cette méthode cherche à minimiser l’augmentation de la variance intra-cluster à chaque fusion. Elle est très utilisée car elle produit en général des clusters compacts et bien séparés.

Le choix du critère de liaison dépend de la géométrie attendue des clusters, de la présence de bruit et de la métrique de distance utilisée. En pratique, il est recommandé de tester plusieurs options et de comparer la qualité des partitions obtenues.

Métriques de distance et de similarité

Distances usuelles pour le clustering hiérarchique

Pour évaluer la similarité ou la dissimilarité entre points (et ensuite entre clusters), différentes métriques de distance peuvent être utilisées :

• Distance euclidienne : c’est la distance « à vol d’oiseau » dans l’espace multidimensionnel. Elle est très répandue pour les données numériques continues.
• Distance de Manhattan : elle correspond à la somme des distances absolues le long de chaque dimension. Elle est parfois plus robuste lorsqu’on souhaite limiter l’influence des grandes différences sur une dimension particulière.
• Distance de Minkowski : généralisation de la distance euclidienne et de Manhattan, contrôlée par un paramètre d’ordre.
• Distance de cosine (ou 1 − similarité cosinus) : particulièrement adaptée pour comparer des vecteurs de textes ou de mots, où l’orientation du vecteur prime sur sa norme.
• Distances spécifiques au domaine : par exemple, des distances basées sur des scores de similarité génomique, des distances d’édition pour les chaînes de caractères, ou des distances définies sur des graphes.

Dans le texte initial, l’expression « dépendance euclidienne » est inexacte : on parle de distance euclidienne, distance de Manhattan et distance (ou similarité) cosinus, et non de « dépendance ».

Normalisation et échelle des variables

Avant d’appliquer un clustering hiérarchique, il est crucial de normaliser ou standardiser les variables, en particulier lorsque les dimensions sont exprimées dans des unités différentes (par exemple euros, années, centimètres). Sans cette étape, les variables de grande amplitude peuvent dominer la distance globale et biaiser la formation des clusters.

Les approches courantes incluent :

• la standardisation (soustraction de la moyenne et division par l’écart-type) ;
• la normalisation min-max (ramener les valeurs dans un intervalle, souvent [0, 1]) ;
• la normalisation par norme (par exemple norme L2 pour des vecteurs de texte).

Complexité algorithmique et limites

Coût en temps et en mémoire

L’algorithme standard de clustering hiérarchique agglomératif a généralement une complexité en temps de l’ordre de O(n³) dans sa forme naïve, avec une complexité mémoire de l’ordre de O(n²), principalement à cause du stockage de la matrice des distances et des mises à jour successives.

Il existe toutefois des implémentations plus efficaces pour certains critères de liaison (par exemple single linkage et complete linkage), permettant de réduire la complexité en temps à O(n²) avec des structures de données et des algorithmes optimisés.

Ces coûts expliquent pourquoi le clustering hiérarchique est moins adapté aux très grands jeux de données. Au-delà de plusieurs dizaines ou centaines de milliers de points, on privilégie souvent des méthodes de clustering plus scalables ou des variantes approximatives.

Clustering hiérarchique et grandes bases de données

Pour répondre précisément à la question fréquente « Peut-on utiliser le clustering hiérarchique pour de grandes bases de données ? » :

• Sur des jeux de données de taille modérée (par exemple quelques milliers à quelques dizaines de milliers d’observations), le clustering hiérarchique est généralement envisageable, surtout avec des implémentations optimisées.
• Sur des bases très volumineuses, le coût en temps et en mémoire devient rapidement prohibitif. On recourt alors à des méthodes approximatives, à un échantillonnage des données, ou à des algorithmes de clustering plus légers (k-means, DBSCAN, méthodes de clustering par grappes de graphes, etc.).

Bonnes pratiques pour le clustering hiérarchique

Sélection du type de clustering et du linkage

La première étape consiste à choisir l’approche hiérarchique (agglomérative ou divisive) et le critère de liaison. En pratique :

• Le clustering agglomératif est le plus utilisé et le mieux supporté par les bibliothèques standards (Scikit-learn, SciPy, R, etc.).
• Parmi les linkages, la méthode de Ward est un excellent choix par défaut pour les données numériques continues, car elle produit des clusters compacts et bien séparés.
• Le single linkage est intéressant pour détecter des structures en chaîne ou des clusters allongés, mais il est sensible au bruit et aux outliers.
• Le complete linkage et l’average linkage peuvent offrir un compromis entre compacité et robustesse.

Prétraitement des données

Un prétraitement rigoureux des données améliore fortement la qualité du clustering hiérarchique :

• Nettoyage des données : suppression ou correction des valeurs aberrantes grossières, uniformisation des formats (dates, devises, encodage texte...).
• Gestion des données manquantes : imputation (moyenne, médiane, modèles plus avancés) ou exclusion raisonnable de certaines observations ou variables. Le clustering hiérarchique ne gère pas nativement les valeurs manquantes.
• Normalisation / standardisation : comme indiqué plus haut, elle est essentielle lorsque les variables n’ont pas la même échelle.
• Sélection de variables pertinentes : supprimer les variables très corrélées ou non informatives peut améliorer la qualité des clusters et réduire le bruit.

Évaluation et validation des clusters

Une fois le dendrogramme obtenu et une découpe choisie, il est important de vérifier la qualité des clusters. Plusieurs approches sont possibles :

• Score de silhouette : mesure à quel point chaque observation est bien assignée à son cluster par rapport aux clusters voisins. Un score moyen élevé indique une bonne séparation des groupes.
• Indice de Davies-Bouldin ou d’autres indices internes de validité : ils comparent la compacité interne des clusters et la séparation entre clusters.
• Validation visuelle : visualisation des données en deux ou trois dimensions (par exemple via PCA ou t-SNE) avec la couleur des clusters, inspection des profils moyens de variables par cluster, etc.
• Validation métier : les clusters doivent être interprétables et utiles dans le contexte de l’application (marketing, santé, industrie...).

Outils et implémentations pratiques

Bibliothèques Python pour le clustering hiérarchique

Plusieurs bibliothèques Python permettent d’implémenter facilement un clustering hiérarchique :

• Scikit-learn : propose des classes comme AgglomerativeClustering pour le clustering hiérarchique agglomératif. Elle permet de choisir la distance, le linkage et le nombre de clusters visés, ou bien de fixer une distance maximale de fusion.
• SciPy : fournit des fonctions de bas niveau telles que linkage et dendrogram pour calculer les fusions successives et visualiser le dendrogramme. SciPy est souvent utilisé lorsque l’on veut un contrôle fin sur la construction et l’affichage de l’arbre.

Ces outils peuvent être combinés avec des bibliothèques de visualisation (Matplotlib, Seaborn, Plotly) pour produire des dendrogrammes interactifs ou des représentations graphiques détaillées des clusters.

Autres environnements et logiciels

En dehors de Python, le clustering hiérarchique est largement disponible :

• R : via des fonctions comme hclust et des packages dédiés à la visualisation de dendrogrammes.
• Logiciels de statistiques (SPSS, SAS, Stata) : offrent des modules de classification hiérarchique avec interface graphique.
• Outils de data mining (KNIME, Orange, RapidMiner) : intègrent des nœuds de clustering hiérarchique dans des workflows visuels.

Applications courantes du clustering hiérarchique

Segmentation client et marketing

En marketing, le clustering hiérarchique est utilisé pour créer des segments de clients à partir de données de comportement (achats, navigation, engagement) et de données sociodémographiques. La hiérarchie permet d’examiner en détail des sous-segments à l’intérieur de groupes plus larges, par exemple :

• un cluster global de « clients fidèles » peut être subdivisé en sous-clusters « gros acheteurs récurrents », « abonnés premium », etc. ;
• les dendrogrammes aident à visualiser comment ces segments se structurent les uns par rapport aux autres.

Analyse génomique et bio-informatique

En bio-informatique, le clustering hiérarchique est largement utilisé pour analyser des profils d’expression génique, des séquences ou d’autres données biologiques. Il permet par exemple :

• de regrouper des gènes présentant des profils d’expression similaires à travers différentes conditions expérimentales ;
• de regrouper des échantillons (patients, tissus) en fonction de leur signature moléculaire.

La représentation en carte de chaleur (heatmap) couplée à un dendrogramme de lignes et de colonnes est devenue un standard pour ce type d’analyses.

Reconnaissance d’images et traitement du signal

Dans la reconnaissance d’images et le traitement du signal, le clustering hiérarchique peut servir à regrouper :

• des images semblables selon des caractéristiques extraites (descripteurs de forme, couleur, caractéristiques issues de réseaux de neurones profonds) ;
• des segments d’un signal ou des motifs récurrents, par exemple pour la détection de patterns en audio, EEG, etc.

La hiérarchie facilite la navigation dans de grandes collections de médias en offrant une organisation par catégories et sous-catégories.

Text mining et NLP

En traitement automatique du langage naturel (NLP), le clustering hiérarchique est appliqué à des documents vectorisés (via TF-IDF, embeddings, etc.) pour créer une organisation thématique :

• regroupement d’articles de presse, de pages web ou de posts sur les réseaux sociaux par thématiques proches ;
• exploration de corpus volumineux sans connaissance préalable des sujets dominants.

L’usage de distances basées sur la similarité cosinus est courant dans ce contexte.

Clustering hiérarchique, SEO et analyse de contenus

Analyse de contenus pour la stratégie SEO

Pour les professionnels du SEO et de la rédaction web, le clustering hiérarchique peut être utilisé pour analyser des corpus de contenus (articles de blog, fiches produits, pages d’un site) en fonction de leurs mots-clés, intentions de recherche ou thématiques sémantiques.

Concrètement, on peut :

• représenter chaque page par un vecteur de caractéristiques (fréquences de termes, embeddings de phrases, métadonnées) ;
• appliquer un clustering hiérarchique pour regrouper les contenus en clusters thématiques imbriqués ;
• identifier des silos thématiques naturels et des contenus orphelins ou redondants.

Cela permet d’optimiser l’architecture du site, les maillages internes et la couverture des sujets, en s’assurant que chaque cluster de contenus réponde de façon cohérente à un ensemble d’intentions de recherche.

Utilisation de Google Analytics et Google Search Console

Des outils comme Google Analytics et Google Search Console ne réalisent pas directement le clustering hiérarchique, mais fournissent des indicateurs clés (trafic, taux de clics, requêtes, comportement utilisateur) qui peuvent être combinés avec des algorithmes de clustering hiérarchique réalisés dans un environnement d’analyse (Python, R, etc.).

On peut par exemple :

• exporter des données de performance de pages (sessions, conversions, temps passé) et des données de contenu (titres, métadonnées, mots-clés) ;
• appliquer un clustering hiérarchique pour identifier des groupes de pages aux comportements similaires ;
• adapter la stratégie éditoriale ou les optimisations SEO à partir de ces segments (améliorer certaines familles de contenus, renforcer les liens internes, etc.).

FAQ sur le clustering hiérarchique

Pourquoi choisir le clustering hiérarchique plutôt que d'autres méthodes ?

Le clustering hiérarchique est particulièrement adapté lorsque vous souhaitez conserver une structure hiérarchique dans vos données, explorer les clusters à différents niveaux de granularité, ou lorsque vous ne connaissez pas à l’avance le nombre optimal de clusters. Il est aussi très utile pour la visualisation et l’interprétation des relations entre groupes via les dendrogrammes.

Comment choisir la bonne métrique de distance ou de similarité ?

Le choix de la métrique dépend du type de données et du problème. Pour des données numériques continues, la distance euclidienne ou la distance de Manhattan sont des choix fréquents, souvent combinés avec la méthode de Ward ou average linkage. Pour des données textuelles ou des vecteurs de caractéristiques normalisés, la similarité cosinus (transformée en distance) est souvent plus appropriée. Il est recommandé de tester plusieurs combinaisons et de comparer la qualité des partitions obtenues.

Puis-je visualiser mes résultats ?

Oui, les dendrogrammes sont une excellente manière de visualiser la structure hiérarchique générée par le clustering hiérarchique. Ils permettent de voir les fusions (ou divisions) successives de clusters, la distance à laquelle elles se produisent et de déterminer visuellement un niveau de découpe pertinent pour obtenir un nombre de clusters cohérent.

C'est quoi un dendrogramme ?

Un dendrogramme est un diagramme arborescent qui représente la succession des fusions (dans l’approche agglomérative) ou des divisions (dans l’approche divisive) de clusters au cours du processus de clustering hiérarchique. La hauteur des branches indique la distance à laquelle les clusters se rejoignent. En coupant horizontalement le dendrogramme à une certaine hauteur, on obtient une partition du jeu de données en un nombre de clusters déterminé.

Puis-je utiliser le clustering hiérarchique pour de grandes bases de données ?

Il est possible d’appliquer le clustering hiérarchique à des bases de données de taille modérée, mais la méthode devient rapidement coûteuse en temps et en mémoire lorsque le nombre d’observations est très élevé, en raison de sa complexité typiquement quadratique à cubique. Pour de très grandes bases (des centaines de milliers ou des millions de points), on privilégiera soit des méthodes de clustering plus scalables, soit des approches hybrides (échantillonnage, pré-clustering, techniques approximatives) avant d’appliquer un clustering hiérarchique sur un ensemble réduit.

Le clustering hiérarchique est-il sensible au bruit et aux valeurs aberrantes ?

Oui, comme de nombreuses méthodes basées sur les distances, le clustering hiérarchique peut être sensible aux outliers. Des points très isolés peuvent influer sur la structure du dendrogramme, en particulier avec certains linkages comme le single linkage. Il est donc recommandé de détecter et traiter les valeurs aberrantes en amont ou de tester des critères de liaison plus robustes.

Dois-je toujours normaliser mes données avant un clustering hiérarchique ?

Dans la plupart des cas, oui. Lorsque les variables ne sont pas sur la même échelle, celles qui présentent une plus grande variance peuvent dominer le calcul de la distance et influer fortement sur la formation des clusters. La standardisation ou une autre forme de normalisation est donc une bonne pratique avant d’appliquer un clustering hiérarchique sur des données numériques.

Comment déterminer le « bon » nombre de clusters à partir d’un dendrogramme ?

Il n’existe pas de réponse unique, mais plusieurs approches complémentaires : inspection visuelle du dendrogramme (recherche de grandes hauteurs de branches, de « sauts » marqués dans les distances de fusion), calcul d’indices de validité (score de silhouette, indices internes), et surtout validation métier (les clusters obtenus doivent être interprétables et utiles dans le contexte de l’analyse).