Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
DBSCAN
Résumé
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. Il s'agit d'un algorithme fondé sur la densité dans la mesure qui s’appuie sur la densité estimée des clusters pour effectuer le partitionnement.
thumb|400px|Les points A sont les points déjà dans le cluster. Les points B et C sont atteignables depuis A et appartiennent donc au même cluster. Le point N est une donnée aberrante puisque son epsilon voisinage ne contient pas de points dont l'epsilon voisinage contient MinPts points ou plus.
L'algorithme DBSCAN utilise 2 paramètres : la distance et le nombre minimum de points devant se trouver dans un rayon 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 -voisinage et de vérifier qu'il contient bien points ou plus. Ce point est alors considéré comme faisant partie d'un cluster. On parcourt ensuite l'-voisinage de proche en proche afin de trouver l'ensemble des points du cluster.
DBSCAN(D, ε, MinPts)
C = 0
pour chaque point P non visité des données D
marquer P comme visité
PtsVoisins = epsilonVoisinage(D, P, ε)
si tailleDe(PtsVoisins) < MinPts
marquer P comme BRUIT
sinon
C++
étendreCluster(D, P, PtsVoisins, C, ε, MinPts)
étendreCluster(D, P, PtsVoisins, C, ε, 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', ε)
si tailleDe(PtsVoisins') >= MinPts
PtsVoisins = PtsVoisins U PtsVoisins'
si P' n'est membre d'aucun cluster
ajouter P' au cluster C
epsilonVoisinage(D, P, ε)
retourner tous les points de D qui sont à une distance inférieure à ε de P
Les points du jeu de données sont séparés en 3 types :
Les points centraux (core points)
Les points frontières (border points)
Les points aberrants (noise points)
Un point du jeu de données est dit central si :
Son voisinage est dense
Ces points forment des composantes connexes indépendantes de l'ordre d'exploration du jeu de données.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Proximité ontologique
Personnes associées (4)