DBSCAN fungerer ud fra idéen om densitetsopnåelighed. Den definerer klynger som tætte områder af datapunkter adskilt af områder med lavere tæthed. To nøgleparametre styrer dens adfærd:

• Epsilon (ε): radius inden for hvilken du søger efter nabopunkter;

• Minimum antal punkter (MinPts): det mindste antal punkter, der kræves inden for ε-radius for at danne et tæt område (inklusive punktet selv).

DBSCAN klassificerer punkter i tre kategorier:

• Kernerpunkter: et punkt er et kernepunkt, hvis det har mindst MinPts inden for sin ε-radius;

• Grænsepunkter: et punkt er et grænsepunkt, hvis det har færre end MinPts inden for sin ε-radius, men er opnåeligt fra et kernepunkt (dvs. inden for ε-radius af et kernepunkt);

• Støjpunkter: et punkt, der hverken er et kernepunkt eller et grænsepunkt, betragtes som et støjpunkt.

Algoritme

1. Start med et vilkårligt ubesøgt punkt;

2. Find alle punkter inden for dets ε-radius;

3. Hvis et punkt har mindst MinPts naboer inden for en ε-radius, markeres det som et kernepunkt, hvilket initierer en ny klynge, der udvides rekursivt ved at tilføje alle direkte tæthedsopnåelige punkter;

4. Hvis antallet af punkter inden for ε-radius er mindre end MinPts, markeres punktet som et grænsepunkt (hvis det er inden for ε-radius af et kernepunkt) eller et støjpunkt (hvis det ikke er);

5. Gentag trin 1-4, indtil alle punkter er besøgt.

Forestil dig et spredningsdiagram af datapunkter. DBSCAN ville starte med at vælge et punkt. Hvis det finder nok naboer inden for dets ε-radius, markeres det som et kernepunkt og begynder at danne en klynge. Derefter udvides denne klynge ved at undersøge kernepunktets naboer og deres naboer osv. Punkter, der er tæt på et kernepunkt, men ikke selv har nok naboer, markeres som grænsepunkter. Punkter, der er isolerede, identificeres som støj.