DBSCAN fungerar utifrån idén om densitetsåtkomlighet. Den definierar kluster som täta områden av datapunkter åtskilda av områden med lägre densitet. Två nyckelparametrar styr dess beteende:

• Epsilon (ε): radien inom vilken närliggande punkter söks;

• Minsta antal punkter (MinPts): det minsta antalet punkter som krävs inom ε-radien för att bilda ett tätt område (inklusive punkten själv).

DBSCAN klassificerar punkter i tre kategorier:

• Kärnpunkter: en punkt är en kärnpunkt om den har minst MinPts inom sin ε-radie;

• Gränspunkter: en punkt är en gränspunkt om den har färre än MinPts inom sin ε-radie men är åtkomlig från en kärnpunkt (dvs. inom ε-radien från en kärnpunkt);

• Bruspunkt: en punkt som varken är en kärnpunkt eller en gränspunkt betraktas som en bruspunkt.

Algoritm

1. Börja med en godtycklig obesökt punkt;

2. Hitta alla punkter inom dess ε-radie;

3. Om en punkt har minst MinPts grannar inom en ε-radie markeras den som en kärnpunkt, vilket initierar ett nytt kluster som rekursivt expanderar genom att lägga till alla direkt densitetsåtkomliga punkter;

4. Om antalet punkter inom ε-radien är mindre än MinPts, markera punkten som en gränspunkt (om den är inom ε-radien från en kärnpunkt) eller en bruspunkt (om den inte är det);

5. Upprepa steg 1-4 tills alla punkter har besökts.

Föreställ dig ett spridningsdiagram av datapunkter. DBSCAN skulle börja med att välja en punkt. Om den hittar tillräckligt många grannar inom dess ε-radie markeras den som en kärnpunkt och börjar bilda ett kluster. Därefter expanderar den detta kluster genom att kontrollera kärnpunktens grannar och deras grannar, och så vidare. Punkter som ligger nära en kärnpunkt men inte har tillräckligt många egna grannar markeras som gränspunkter. Punkter som är isolerade identifieras som brus.