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.

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 :

Le résultat est clair : DBSCAN produit un mauvais clustering.
Compare maintenant avec les résultats de HDBSCAN sur les mêmes données :

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.

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 :

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 :

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

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 :

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 :

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.

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 :

Formes de clusters produites par KMeans quand les données forment des clusters ovales
À la place, un clustering idéal devrait ressembler à ceci :

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 :

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 :

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 :

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

Des clusters de densités variables

Des points de bruit

Ç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 :
Les clusters auront des formes et des tailles arbitraires.
Les clusters auront des densités arbitraires.
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.

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

HDBSCAN, en revanche, se montre bien plus robuste.

💡 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
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 ExpertsEn 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


