DBSCAN++ : Passe ton Clustering à l'échelle supérieure

  MINI-COURS #24      ⏱️ 35-45 minutes de lecture

KMeans est un algorithme de clustering non supervisé qui regroupe les données en fonction des distances. Il est largement reconnu pour sa simplicité et son efficacité. Essentiellement, l'idée centrale est de partitionner un jeu de données en clusters distincts, chaque point appartenant au cluster dont le centroïde est le plus proche.

Bien que sa simplicité en fasse souvent l'algorithme de clustering préféré, KMeans présente de nombreuses limitations qui entravent son efficacité dans plusieurs scénarios.

Par exemple, KMeans ne tient pas compte de la variance ni de la forme des clusters.

En d'autres termes, l'une des principales limites de KMeans est son hypothèse de clusters sphériques.

Une façon intuitive et graphique de comprendre l'algorithme KMeans est de placer un cercle au centre de chaque cluster, qui englobe les points.

💡 En 3 dimensions, les cercles peuvent être remplacés par des sphères. En dimensions supérieures, on peut les imaginer comme des hyper-sphères.

Comme KMeans consiste essentiellement à placer des cercles, ses résultats ne sont pas idéaux lorsque le jeu de données présente des formes irrégulières ou des tailles variables, comme indiqué ci-dessous :

Au lieu de cela, un clustering idéal devrait regrouper les données comme suit :

On peut observer la même chose dans le jeu de données suivant :

Cette rigidité de KMeans à ne former que des clusters globulaires conduit souvent à des erreurs de classification et à des assignations de clusters sous-optimales.

Une autre limitation significative de l'algorithme KMeans est son hypothèse inhérente que chaque point de données doit être assigné à un cluster.

Plus précisément, KMeans part du principe que chaque point appartient à un et un seul cluster, ne laissant aucune place pour la représentation du bruit ou des outliers (données aberrantes).

Cette caractéristique peut être problématique dans les scénarios où le jeu de données contient des irrégularités, des anomalies ou du bruit qui ne se conforment pas à des frontières de clusters claires.

Par conséquent, KMeans peut assigner par inadvertance des points à des clusters même lorsqu'ils n'appartiennent véritablement à aucun modèle discernable.

Ceci est illustré dans l'image ci-dessous :

Cette tendance peut conduire à des résultats de clustering sous-optimaux, en particulier dans les jeux de données à densités variables, aux formes irrégulières ou en présence de données bruitées.

Dans les datasets réels où la structure sous-jacente n'est pas adaptée aux hypothèses de KMeans, l'assignation rigide de tous les points limite son efficacité.

Nous devons être conscients de cette limitation et envisager des approches alternatives, telles que les méthodes basées sur la densité ou hiérarchiques, lorsque nous traitons des données présentant beaucoup de bruit ou d'outliers.

Une contrainte notable de l'utilisation de KMeans est la nécessité d'une connaissance préalable ou d'hypothèses sur le nombre exact de clusters dans le jeu de données.

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

Bien sûr, ce n'est pas un problème insurmontable, et il existe diverses méthodes pour déterminer une valeur fiable pour le paramètre k, mais cette contrainte pose des défis lorsque le vrai nombre de clusters est inconnu à l'avance, menant à des inexactitudes potentielles.

Note en passant : Nous utilisons couramment la méthode du Coude (Elbow curve) pour déterminer le nombre de clusters (k) pour KMeans.

Cependant, le problème avec la courbe du Coude est qu'elle :

Le score de Silhouette est une mesure alternative pour évaluer la qualité du clustering, et il est généralement considéré comme plus fiable que la courbe du Coude.

Le mesurer à travers une plage de centroïdes (k) peut révéler quels résultats de clustering sont les plus prometteurs.

Le visuel ci-dessous compare la courbe du Coude et le graphique de Silhouette :

Il est clair que la courbe du Coude est très trompeuse et imprécise. Dans un dataset avec 25 clusters :

Nous avons déjà couvert cela dans quelques éditions précédentes de la newsletter si tu souhaites plus de détails :

Revenons à nos moutons...

Les limitations ci-dessus soulignent l'importance extrême d'apprendre d'autres algorithmes plus performants pour pallier ces manques.

Bien que KMeans fasse partie des algorithmes basés sur les centroïdes, il existe de nombreux types d'algorithmes de clustering (montrés ci-dessous) utilisables selon la situation :

Nous avons déjà couvert le clustering basé sur la distribution auparavant :

L'objectif de ce mini-cours est donc le clustering basé sur la densité, et plus spécifiquement DBSCAN++, qui est une amélioration significative de l'algorithme DBSCAN classique.

Comprenons cela en détail !

Mais avant de comprendre DBSCAN++, comprenons ce qu'est DBSCAN.

DBSCAN, qui signifie Density-Based Spatial Clustering of Applications with Noise, est un algorithme populaire en machine learning et data mining.

Comme son nom l'indique, l'idée centrale derrière DBSCAN est de regrouper les points de données basés sur la "densité", c'est-à-dire les points proches les uns des autres dans une région à haute densité, séparés par des régions de plus faible densité.

Il excelle à chercher des zones dans les données avec une forte densité de points, par opposition aux zones peu denses en observations.

La notion de densité dans DBSCAN lui permet de trier les données en clusters de formes variées également, ce qui est son avantage substantiel sur les algorithmes traditionnels comme KMeans.

En conséquence, il résout immédiatement chacune des limitations de KMeans discutées plus haut :

Parcourons un exemple simple pour comprendre le fonctionnement de l'algorithme.

Disons que nous avons un dataset de points comme suit :

Clairement, nous avons deux clusters distincts et un point de bruit au centre. Notre objectif est de regrouper ces points en groupes denséments peuplés.

Premièrement, nous comptons le nombre de points au voisinage de chaque point de données. Par exemple, si nous commençons avec le point vert, nous dessinons un cercle autour de lui.

Le rayon epsilon du cercle est le premier paramètre que nous devons spécifier en utilisant DBSCAN. En d'autres termes, c'est un hyperparamètre.

Après avoir dessiné le cercle, nous comptons le nombre de points qui tombent dans ce cercle de rayon ϵ. Par exemple, pour notre point vert, il y a six points proches.

De même, nous comptons le nombre de points proches pour tous les points restants.

Après avoir compté les points au voisinage de chaque donnée, nous classifions chaque point dans l'une des trois catégories :

Et bien sûr, comme tu l’as deviné, minPts est un autre hyperparamètre de DBSCAN.

Après avoir classifié tous les points, nous procédons au clustering.

L'idée est simple :

L'algorithme termine son exécution une fois qu'il ne reste plus de points cœurs non visités.

Dans DBSCAN, déterminer le paramètre epsilon est souvent délicat. Mais la courbe du Coude est souvent utile ici.

Pour commencer, DBSCAN a deux hyperparamètres :

Nous pouvons utiliser la courbe du Coude pour trouver epsilon :

Pour chaque point, trace la distance vers son k-ième voisin le plus proche (en ordre croissant), où k est l'hyperparamètre minPts. C'est ce qu'on appelle le k-distance plot.

La valeur optimale d'epsilon se trouve près du point de coude.

Pourquoi ça marche ?

Rappelle-toi que dans ce graphique, nous mesurons la distance vers un voisin spécifique (le k-ième) pour tous les points. Ainsi, le point de coude suggère une distance vers un point plus isolé ou un point dans un cluster différent.

Le point où le changement est le plus prononcé suggère un epsilon optimal. L'efficacité est évidente sur l'image ci-dessus.

Comme illustré, choisir la valeur du coude fournit de meilleurs résultats de clustering.

💡 En continuant, tu vas découvrir :