DBSCAN

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) est un algorithme de partitionnement de données proposé en 1996 par Martin Ester, Hans-Peter Kriegel, Jörg Sander et Xiaowei Xu[1]. Il s'agit d'un algorithme basé sur la densité dans la mesure où il s’appuie sur la densité estimée des clusters pour effectuer le partitionnement.

Idée de base[modifier | modifier le code]

Les points A sont les points déjà dans le cluster. Les points B et C sont atteignable depuis A et appartiennent donc au même cluster. Le point N est une donnée aberrante puisque son epsilon voisinage ne contient pas MinPts points ou plus.

L'algorithme DBSCAN utilise 2 paramètres : la distance \epsilon et le nombre minimum de points MinPts devant se trouver dans un rayon \epsilon pour que ces points soient considérés comme un cluster. Les paramètres d'entrées sont donc une estimation de la densité de points des clusters. L'idée de base de l'algorithme est ensuite, pour un point donné, de récupérer son \epsilon-voisinage et de vérifier qu'il contient bien MinPts points ou plus. Ce point est alors considéré comme faisant partie d'un cluster. On parcourt ensuite l'\epsilon-voisinage de proche en proche afin de trouver l'ensemble des points du cluster.

Algorithme[modifier | modifier le code]

DBSCAN(D, eps, MinPts)
   C = 0
   pour chaque point P non visité des données D
      marquer P comme visité
      PtsVoisins = epsilonVoisinage(P, eps)
      si tailleDe(PtsVoisins) < MinPts
         mark P as NOISE
      sinon
         C++
         expandCluster(D, P, PtsVoisins, C, eps, MinPts)
          
expandCluster(D, P, PtsVoisins, C, eps, MinPts)
   ajouter P au cluster C
   pour chaque point P' de PtsVoisins 
      si P' n'a pas été visité
         marquer P' comme visité
         PtsVoisins' = epsilonVoisinage(D, P', eps)
         si tailleDe(PtsVoisins') >= MinPts
            PtsVoisins = PtsVoisins U PtsVoisins'
      si P' n'est membre d'aucun cluster
         ajouter P' au cluster C
          
epsilonVoisinage(D, P, eps)
   retourner tous les points de D qui sont à une distance inférieur à epsilon de P

Avantages et inconvénients[modifier | modifier le code]

L'algorithme est très simple et ne nécessite pas qu'on lui précise le nombre de clusters à trouver. Il est capable de gérer les données aberrantes en les éliminant du processus de partitionnement. Les clusters n'ont pas pour obligation d'être linéairement séparable (en comparaison avec l'algorithme des k-moyennes par exemple). Cependant, il n'est pas capable de gérer des clusters de densités différentes.

Références[modifier | modifier le code]

  1. M. Ester, H.-P. Kriegel, J. Sander, and X. Xu, “A density-based algorithm for discovering clusters in large spatial databases with noise,” in Proceedings of the 2nd International Conference on Knowledge Discovery and Data mining, 1996, pp. 226–231.