DBSCAN fonctionne selon le principe de la connectivité par densité. Il définit les clusters comme des régions denses de points de données séparées par des zones de plus faible densité. Deux paramètres principaux régissent son comportement :

• Epsilon (ε) : le rayon dans lequel les points voisins sont recherchés ;

• Nombre minimum de points (MinPts) : le nombre minimal de points requis à l'intérieur du rayon ε pour former une région dense (y compris le point lui-même).

DBSCAN classe les points en trois catégories :

• Points centraux : un point est central s'il possède au moins MinPts dans son rayon ε ;

• Points frontières : un point est frontière s'il possède moins de MinPts dans son rayon ε mais est accessible à partir d'un point central (c'est-à-dire dans le rayon ε d'un point central) ;

• Points bruit : un point qui n'est ni central ni frontière est considéré comme un point bruit.

Algorithme

1. Commencer avec un point arbitraire non visité ;

2. Trouver tous les points dans son rayon ε ;

3. Si un point possède au moins MinPts voisins dans un rayon ε, il est marqué comme point central, ce qui initie un nouveau cluster qui s'étend récursivement en ajoutant tous les points directement accessibles par densité ;

4. Si le nombre de points dans le rayon ε est inférieur à MinPts, marquer le point comme point frontière (s'il est dans le rayon ε d'un point central) ou comme point bruit (s'il ne l'est pas) ;

5. Répéter les étapes 1 à 4 jusqu'à ce que tous les points soient visités.

Considérer un nuage de points de données. DBSCAN commence par sélectionner un point. S'il trouve suffisamment de voisins dans son rayon ε, il le marque comme point central et commence à former un cluster. Il étend ensuite ce cluster en examinant les voisins du point central et leurs voisins, et ainsi de suite. Les points proches d'un point central mais n'ayant pas eux-mêmes assez de voisins sont marqués comme points frontières. Les points isolés sont identifiés comme bruit.