Les algorithmes non paramétriques non supervisés sont largement utilisés en entreprise pour analyser de grands jeux de données.
La raison est simple : dans beaucoup d'applications concrètes, obtenir les vraies étiquettes (labels) est très difficile, voire impossible.
Dans ces cas-là :
Soit les équipes data annotent les données, ce qui peut s'avérer infaisable en pratique,
Soit on utilise des méthodes non supervisées pour identifier des patterns.
Si KMeans est très répandu ici grâce à sa simplicité et son efficacité en tant qu'algorithme de clustering, il a de nombreuses limites :
Il ne prend pas en compte la covariance des clusters.
Il ne peut produire que des clusters sphériques. Comme tu peux le voir ci-dessous, même si les données forment des clusters non circulaires, il produit quand même des clusters ronds.
Les algorithmes basés sur la densité, comme DBSCAN, répondent assez efficacement à ces limitations.
L'idée centrale derrière DBSCAN est de regrouper les points de données en fonction de la "densité", c'est-à-dire que les points proches les uns des autres dans une région de haute densité sont groupés ensemble, et séparés des autres par des régions de plus faible densité.
Mais malheureusement, avec DBSCAN, on se heurte à un autre problème souvent sous-estimé.
L'un des éléments qui rend DBSCAN parfois inutilisable en pratique, c'est son temps d'exécution.
Jusqu'à récemment, on pensait que DBSCAN avait une complexité de O(nlogn), mais il a été prouvé qu'elle est de O(n²) dans le pire des cas.
D'ailleurs, on peut aussi le vérifier sur la figure ci-dessous. Elle montre le temps d'exécution de DBSCAN en fonction du nombre d'échantillons :
C'est clair : DBSCAN a une relation quadratique avec la taille du jeu de données.
Il y a donc un besoin croissant de développer des versions plus efficaces de DBSCAN.
DBSCAN++ est un pas majeur vers un DBSCAN rapide et scalable.
En résumé, DBSCAN++ repose sur l'observation suivante : on n'a besoin de calculer les estimations de densité que pour un sous-ensemble "m" des "n" points du jeu de données, où "m" peut être bien plus petit que "n" pour obtenir un clustering correct.
L'efficacité de DBSCAN++ est évidente sur l'image ci-dessous :
Sur un jeu de données de 60 000 points :
DBSCAN++ est 20x plus rapide que DBSCAN.
DBSCAN++ produit de meilleurs scores de clustering que DBSCAN.
Mais comment ça fonctionne de bout en bout ?
Pourquoi sélectionner un sous-ensemble de points reste efficace ?
Quelles stratégies peut-on utiliser pour sélectionner ce sous-ensemble ?
Quelles autres limitations DBSCAN++ résout-il ?
DBSCAN++ est un algorithme récent. Quels sont les points à garder en tête pour l'utiliser efficacement ?
Si tu es curieux, le dernier deep dive en machine learning traite exactement de ce sujet : DBSCAN++ : l'alternative plus rapide et scalable au clustering DBSCAN.
La plupart des jeux de données réels sont non supervisés et naturellement très volumineux :
KMeans n'est généralement pas adapté à cause des hypothèses strictes mentionnées plus haut.
DBSCAN peut fonctionner, mais il souffrira du temps d'exécution.
Du coup, connaître des algorithmes comme DBSCAN++ devient vraiment essentiel.
Bien sûr, je sais que beaucoup d'entre vous n'ont pas forcément une compréhension claire de DBSCAN lui-même.
J'ai donc aussi fourni une présentation détaillée de DBSCAN, qui sert de base naturelle pour comprendre DBSCAN++.
Autre point : un problème avec DBSCAN++, c'est qu'il n'est pas intégré dans Sklearn.
Mais pas de panique.
Pour cet article, j'ai écrit une implémentation entièrement vectorisée de DBSCAN++, qui est liée dans l'article et que tu peux utiliser dans tes projets.
Lis le deep dive ici : DBSCAN++ : l'alternative plus rapide et scalable au clustering DBSCAN.
Je suis convaincu qu'apprendre DBSCAN++ sera extrêmement précieux pour tes compétences et tes projets futurs :)
Envie d'aller plus loin ? DataXp t'attend : formations et parcours pour progresser en data science, machine learning et IA.
