DBSCAN si basa sul concetto di raggiungibilità per densità. Definisce i cluster come regioni dense di punti dati separate da aree a densità inferiore. Due parametri principali ne regolano il comportamento:

• Epsilon (ε): il raggio entro il quale si cercano i punti vicini;

• Numero minimo di punti (MinPts): il numero minimo di punti richiesto all'interno del raggio ε per formare una regione densa (incluso il punto stesso).

DBSCAN classifica i punti in tre categorie:

• Punti core: un punto è un punto core se ha almeno MinPts all'interno del suo raggio ε;

• Punti di bordo: un punto è un punto di bordo se ha meno di MinPts all'interno del suo raggio ε ma è raggiungibile da un punto core (cioè si trova nel raggio ε di un punto core);

• Punti rumore: un punto che non è né un punto core né un punto di bordo è considerato un punto rumore.

Algoritmo

1. Iniziare con un punto arbitrario non ancora visitato;

2. Trovare tutti i punti all'interno del suo raggio ε;

3. Se un punto ha almeno MinPts vicini entro un raggio ε, viene contrassegnato come punto core, avviando un nuovo cluster che si espande ricorsivamente aggiungendo tutti i punti direttamente raggiungibili per densità;

4. Se il numero di punti all'interno del raggio ε è inferiore a MinPts, contrassegnare il punto come punto di bordo (se si trova nel raggio ε di un punto core) o come punto rumore (se non lo è);

5. Ripetere i passaggi 1-4 fino a quando tutti i punti sono stati visitati.

Immaginare un grafico a dispersione di punti dati. DBSCAN inizierebbe selezionando un punto. Se trova abbastanza vicini entro il suo raggio ε, lo contrassegna come punto core e inizia a formare un cluster. Successivamente espande questo cluster verificando i vicini del punto core e i loro vicini, e così via. I punti che sono vicini a un punto core ma non hanno abbastanza vicini vengono contrassegnati come punti di bordo. I punti isolati vengono identificati come rumore.