MINI-COURS #37      ⏱️ 18 – 22 minutes de lecture

🔒 Contenu réservé aux membres du Cercle des Experts
Débloque la leçon complète et tous les autres mini-cours.

Au programme

On a déjà creusé plusieurs algorithmes de clustering avancés dans les dossiers précédents, notamment ceux-ci :

Dans ce dossier, on continue la série clustering avec HDBSCAN, un algorithme de clustering hiérarchique puissant qui étend les capacités de DBSCAN en ajoutant une dimension hiérarchique et en gérant beaucoup mieux les densités variables.

  • DBSCAN signifie Density-Based Spatial Clustering of Applications with Noise.

  • HDBSCAN signifie Hierarchical Density-Based Spatial Clustering of Applications with Noise.

Pour rappel, DBSCAN part du principe que la densité locale des points de données est (plus ou moins) uniforme à l'échelle globale. C'est son paramètre eps qui gouverne cette hypothèse.

Schéma illustrant l'hypothèse de densité uniforme de DBSCAN, avec un paramètre eps appliqué de façon identique à tous les points d'un cluster en forme de fer à cheval

Regarde par exemple les résultats de clustering obtenus avec DBSCAN sur le dataset factice ci-dessous, où chaque cluster a une densité différente :

Comparaison avant/après montrant DBSCAN produire un clustering fragmenté sur trois clusters de densités différentes

Le résultat est clair : DBSCAN produit un mauvais clustering.

Compare maintenant avec les résultats de HDBSCAN sur les mêmes données :

Comparaison avant/après montrant HDBSCAN identifier correctement trois clusters de densités différentes

Sur un dataset avec trois clusters de densités variables, HDBSCAN se montre bien plus robuste.

À la fin de ce dossier précédent, beaucoup d'entre vous ont montré de l'intérêt pour un deep dive complet sur HDBSCAN. Ça tombe bien, c'est exactement le sujet du jour.

On va couvrir les concepts clés qui te permettront de comprendre comment HDBSCAN fonctionne, et pourquoi c'est un algorithme de clustering aussi puissant.

C'est parti !

À quoi ressemblent les données ?

Tout problème de clustering démarre avec un dataset (non labellisé) et quelques hypothèses à son sujet.

Grille représentant un dataset non labellisé, point de départ de tout problème de clustering avant l'application d'un algorithme comme HDBSCAN

Avant de concevoir (ou d'utiliser) un algorithme de clustering, la première question à se poser est :

❝

Qu'est-ce qu'on sait des données qu'on nous donne ? Quel type de données cherche-t-on à clusteriser ?

Dans l'idéal, on veut poser le moins d'hypothèses possible. Deux hypothèses de base suffisent pour avancer :

Illustration de trois clusters de formes et tailles arbitraires (orange, bleu, vert) entourés de points de bruit gris isolés
  • Le dataset contient du bruit, ce qui veut dire que tous les points n'appartiennent pas forcément à un cluster.

  • Il existe un certain nombre de clusters (on ne sait pas combien) de formes arbitraires dans le dataset.

Dans ce dossier, on va construire les fondations de HDBSCAN à partir du dataset 2D suivant :

Nuage de points en 2D représentant le dataset factice utilisé tout au long du dossier pour comparer KMeans, DBSCAN et HDBSCAN

Comme c'est un dataset en 2D, il est facile de constater visuellement qu'il y a 6 clusters, le reste étant du bruit :

Le même dataset factice, avec les 6 clusters de formes arbitraires entourés manuellement pour illustrer l'inspection visuelle avant clustering

Mais évidemment, l'inspection visuelle n'est pas toujours possible (en particulier sur des données en haute dimension). On a donc besoin d'un algorithme de clustering capable d'identifier des clusters dans n'importe quel espace, quelle que soit sa dimension.

Essayons avec KMeans

Le premier réflexe face à un problème de clustering, c'est souvent d'essayer KMeans. Comme on connaît le nombre de clusters dans ce cas précis, lançons un KMeans et regardons les résultats :

En traçant le dataset avec les labels obtenus, on obtient le graphique suivant :

Nuage de points montrant l'échec de KMeans à retrouver les 6 clusters d'origine malgré un nombre de clusters spécifié correctement

Imaginons un instant qu'on dispose déjà d'une implémentation de HDBSCAN, et qu'on la lance sur le même dataset :

En traçant le dataset avec les labels obtenus, on obtient :

Nuage de points montrant HDBSCAN retrouver correctement les 6 clusters et isoler les points de bruit en vert clair, sans spécifier le nombre de clusters

Malgré le fait qu'on ait spécifié le bon nombre de clusters à KMeans, celui-ci échoue à produire un clustering correct. HDBSCAN, lui, fait un bien meilleur travail (à l'œil nu) sans même qu'on lui précise le nombre de clusters.

Pourquoi KMeans échoue-t-il ? Voyons ça.

Les limites de KMeans

Si sa simplicité en fait souvent l'algorithme de clustering préféré, KMeans a plusieurs limites qui plombent son efficacité dans de nombreux cas.

1) KMeans ne tient pas compte de la variance ni de la forme des clusters

Une des limites principales de KMeans, c'est son hypothèse implicite que les clusters sont sphériques.

Une façon intuitive et visuelle de comprendre l'algorithme KMeans, c'est d'imaginer un cercle placé au centre de chaque cluster, qui englobe les points.

Schéma illustrant KMeans qui place un cercle autour de chaque cluster, une hypothèse de forme sphérique adaptée aux clusters bien séparés et arrondis

Formes de clusters produites par KMeans quand les données forment des clusters circulaires

💡 En 3 dimensions, les cercles deviennent des sphères. Au-delà, on parle d'hypersphères.

Comme KMeans revient essentiellement à placer des cercles, ses résultats sont décevants dès que le dataset présente des formes irrégulières ou des tailles variables, comme ci-dessous :

Schéma montrant KMeans forcer des frontières circulaires sur des clusters allongés et non globulaires, produisant un découpage incorrect

Formes de clusters produites par KMeans quand les données forment des clusters ovales

À la place, un clustering idéal devrait ressembler à ceci :

Schéma montrant le clustering idéal attendu sur des données à clusters allongés, avec des frontières ovales épousant la vraie forme des données

Forme de cluster idéale quand les données forment des clusters ovales

On observe le même phénomène sur le dataset suivant :

Comparaison entre KMeans, qui force deux cercles se chevauchant sur des clusters en forme de croissant, et le clustering idéal qui respecte leur forme réelle

Cette rigidité de KMeans, qui ne sait clusteriser que des formes globulaires, mène régulièrement à des erreurs de classification et à des assignations de clusters sous-optimales.

2) Chaque point est forcément assigné à un cluster

Autre limite importante de KMeans : son hypothèse implicite que chaque point de données doit appartenir à un cluster.

Plus précisément, KMeans part du principe que chaque point appartient à un cluster, et à un seul, sans aucune place pour représenter du bruit ou des outliers.

Ça devient problématique quand le dataset contient des irrégularités, des anomalies ou du bruit qui ne collent à aucune frontière de cluster claire.

Résultat : KMeans va malgré tout assigner ces points à un cluster, même quand ils ne correspondent en réalité à aucun pattern identifiable.

C'est ce qu'illustre l'image ci-dessous :

Schéma montrant trois outliers isolés être forcés dans les clusters les plus proches par KMeans, illustrant son absence de gestion du bruit

Cette tendance peut dégrader la qualité du clustering, en particulier sur des datasets à densités variables, à formes irrégulières, ou contenant du bruit.

Sur des données réelles, où la structure sous-jacente ne colle pas forcément aux hypothèses de KMeans, cette assignation rigide de tous les points à un cluster peut sérieusement limiter l'efficacité de l'algorithme.

C'est une limite à garder en tête, qui pousse à envisager d'autres approches (density-based ou hiérarchiques par exemple) dès qu'un dataset présente du bruit ou des outliers significatifs.

3) La nécessité de spécifier le nombre de clusters

Autre contrainte notable de KMeans : il faut connaître (ou supposer) à l'avance le nombre exact de clusters dans le dataset.

Contrairement à d'autres algorithmes capables de déterminer automatiquement le nombre optimal de clusters à partir de la structure des données, KMeans repose sur une valeur prédéfinie du nombre de clusters (souvent notée k).

Ce n'est pas un problème en soi, il existe plusieurs méthodes pour estimer une valeur fiable de k. Mais cette contrainte devient problématique quand le vrai nombre de clusters est inconnu à l'avance, ce qui peut mener à des résultats imprécis et sous-optimaux.

Ces limites de KMeans montrent bien l'intérêt d'explorer d'autres algorithmes capables d'y répondre.

KMeans fait partie de la famille des algorithmes de clustering par centroïdes, mais il existe de nombreuses autres familles (illustrées ci-dessous), à utiliser selon le contexte :

Tableau récapitulatif des 6 familles d'algorithmes de clustering (centroïdes, connectivité, densité, graphes, distributions, compression) avec leur méthodologie et les algorithmes associés comme KMeans, HDBSCAN, DBSCAN et GMM

Pourquoi KMeans a échoué ?

Une fois ces limites de KMeans posées, il devient facile de comprendre pourquoi il a produit des résultats aussi médiocres sur notre dataset d'origine.

Plus précisément, le dataset qu'on a utilisé présente :

  • Des clusters de formes et de tailles arbitraires

Dataset factice annoté montrant les six clusters de formes irrégulières et arbitraires, non détectables par un algorithme supposant des clusters sphériques
  • Des clusters de densités variables

Dataset factice annoté montrant des clusters de densités nettement différentes, un défi pour les algorithmes supposant une densité uniforme
  • Des points de bruit

Dataset factice annoté délimitant la région dense des clusters, avec de nombreux points de bruit dispersés à l'extérieur

Ça explique clairement la contre-performance de KMeans sur ce dataset. Mais ça nous donne aussi de bonnes pistes pour construire un algorithme plus robuste.

Poser les bonnes attentes

Les trois points ci-dessus définissent des attentes claires sur notre dataset. Il paraît raisonnable de supposer qu'un dataset réel présentera les mêmes caractéristiques :

  1. Les clusters auront des formes et des tailles arbitraires.

  2. Les clusters auront des densités arbitraires.

  3. Le dataset contiendra des points de bruit.

Si on retire la 2ème caractéristique (densités arbitraires), l'algorithme DBSCAN répond à ces critères.

Mais comme on l'a vu plus haut (et dans le deep dive dédié à DBSCAN), il suppose que la densité locale des points est (plus ou moins) uniforme à l'échelle globale. C'est son paramètre eps qui gouverne ça.

Schéma illustrant l'hypothèse de densité uniforme de DBSCAN, avec un paramètre eps appliqué de façon identique à tous les points d'un cluster en forme de fer à cheval

DBSCAN a donc du mal avec un dataset où chaque cluster a une densité différente :

Comparaison avant/après montrant DBSCAN produire un clustering fragmenté avec de nombreux faux points de bruit sur un dataset à trois clusters de densités différentes

HDBSCAN, en revanche, se montre bien plus robuste.

Comparaison avant/après montrant HDBSCAN identifier correctement les trois clusters malgré des densités très différentes, contrairement à DBSCAN

💡 En continuant, tu vas découvrir :

  • Le paradoxe qui rend la validation des hypothèses de clustering presque impossible en pratique, et pourquoi il faut un algorithme qui pose le moins d'hypothèses possible

  • Comment définir rigoureusement ce qu'est un "cluster", au-delà de l'intuition visuelle

  • Les deux méthodes pour estimer une densité de probabilité à partir des données brutes, et laquelle des deux HDBSCAN utilise (et pourquoi)

  • Le concept de "core distance", la pièce maîtresse qui rend HDBSCAN robuste aux changements d'échelle

  • Comment HDBSCAN transforme un simple seuil de densité en régions de clusters connectées

logo

La suite de ce mini-cours est réservée aux membres du Cercle des Experts.

Tu as déjà le début. Pour accéder à l’explication complète et aux autres mini-cours, rejoins le Cercle des Experts.

Rejoindre le Cercle des Experts

En devenant membre, tu débloques :

  • L’intégralité de ce mini-cours, sans coupure
  • Tous les mini-cours et les ressources associées
  • Chaque nouveau mini-cours dès sa sortie

Commentaires

Avatar

ou participer

À lire ensuite

Des shots dans la même veine, à lire entre deux tâches.

Voir tous les shots
caret-right