DBSCAN werkt op basis van het concept dichtheidsbereikbaarheid. Het definieert clusters als dichte regio's van datapunten die gescheiden zijn door gebieden met een lagere dichtheid. Twee belangrijke parameters bepalen het gedrag:

• Epsilon (ε): de straal waarbinnen naar naburige punten wordt gezocht;

• Minimum aantal punten (MinPts): het minimum aantal punten dat binnen de ε-straal vereist is om een dichte regio te vormen (inclusief het punt zelf).

DBSCAN classificeert punten in drie categorieën:

• Kernpunten: een punt is een kernpunt als het ten minste MinPts binnen zijn ε-straal heeft;

• Randpunten: een punt is een randpunt als het minder dan MinPts binnen zijn ε-straal heeft, maar bereikbaar is vanaf een kernpunt (d.w.z. binnen de ε-straal van een kernpunt);

• Ruispunten: een punt dat noch een kernpunt noch een randpunt is, wordt beschouwd als een ruispunt.

Algoritme

1. Begin met een willekeurig niet-bezocht punt;

2. Zoek alle punten binnen zijn ε-straal;

3. Als een punt ten minste MinPts buren binnen een ε-straal heeft, wordt het gemarkeerd als een kernpunt, waarmee een nieuw cluster wordt gestart dat zich recursief uitbreidt door alle direct dichtheidsbereikbare punten toe te voegen;

4. Als het aantal punten binnen de ε-straal minder dan MinPts is, markeer het punt dan als een randpunt (als het binnen de ε-straal van een kernpunt ligt) of een ruispunt (als dat niet het geval is);

5. Herhaal stappen 1-4 totdat alle punten zijn bezocht.

Stel je een spreidingsdiagram van datapunten voor. DBSCAN begint met het selecteren van een punt. Als het voldoende buren binnen zijn ε-straal vindt, markeert het dit als een kernpunt en begint een cluster te vormen. Vervolgens breidt het dit cluster uit door de buren van het kernpunt en hun buren te controleren, enzovoort. Punten die dicht bij een kernpunt liggen maar zelf niet genoeg buren hebben, worden gemarkeerd als randpunten. Geïsoleerde punten worden aangeduid als ruis.