DBSCAN fungerer basert på ideen om tetthetsoppnåelighet. Den definerer klynger som tette områder av datapunkter adskilt av områder med lavere tetthet. To nøkkelparametere styrer oppførselen:

• Epsilon (ε): radiusen innenfor hvilken du søker etter nabopunkter;

• Minimum antall punkter (MinPts): minimum antall punkter som kreves innenfor ε-radiusen for å danne et tett område (inkludert punktet selv).

DBSCAN klassifiserer punkter i tre kategorier:

• Kjernepunkter: et punkt er et kjernepunkt hvis det har minst MinPts innenfor sin ε-radius;

• Grensepunkter: et punkt er et grensepunkt hvis det har færre enn MinPts innenfor sin ε-radius, men er oppnåelig fra et kjernepunkt (dvs. innenfor ε-radiusen til et kjernepunkt);

• Støypunkter: et punkt som verken er et kjernepunkt eller et grensepunkt regnes som et støypunkt.

Algoritme

1. Start med et vilkårlig, ubesøkt punkt;

2. Finn alle punkter innenfor dets ε-radius;

3. Hvis et punkt har minst MinPts naboer innenfor en ε-radius, markeres det som et kjernepunkt, og en ny klynge startes som utvides rekursivt ved å legge til alle direkte tetthetsoppnåelige punkter;

4. Hvis antall punkter innenfor ε-radiusen er mindre enn MinPts, markeres punktet som et grensepunkt (hvis det er innenfor ε-radiusen til et kjernepunkt) eller et støypunkt (hvis det ikke er det);

5. Gjenta trinn 1-4 til alle punkter er besøkt.

Tenk deg et spredningsdiagram av datapunkter. DBSCAN vil starte med å velge et punkt. Hvis det finner nok naboer innenfor ε-radiusen, markerer det dette som et kjernepunkt og begynner å danne en klynge. Deretter utvides denne klyngen ved å sjekke naboene til kjernepunktet og deres naboer, og så videre. Punkter som er nær et kjernepunkt, men som ikke har nok naboer selv, markeres som grensepunkter. Punkter som er isolerte, identifiseres som støy.