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 clés régissent son comportement :

• Epsilon (ε) : le rayon dans lequel rechercher les points voisins ;

• Nombre minimum de points (MinPts) : le nombre minimum 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 qu'il se trouve dans le rayon ε d'un point central) ;

• Points de bruit : un point qui n'est ni central ni frontière est considéré comme un point de 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, initiant 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 se trouve dans le rayon ε d'un point central) ou comme point de bruit (s'il ne l'est pas) ;

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

Imaginez un nuage de points. 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 vérifiant 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.