DBSCAN, Density-Based Spatial Clustering of Applications with Noise, è un algoritmo di clustering basato sulla densità. Raggruppa punti che si trovano in regioni dense dello spazio e identifica come rumore i punti isolati. A differenza del k-means, non richiede di fissare in anticipo il numero di cluster e può individuare gruppi di forma non sferica.
È uno dei metodi più importanti nell’analisi dei cluster perché traduce un’idea geometrica intuitiva: un cluster è una regione in cui i punti sono sufficientemente vicini e sufficientemente numerosi.
1. Parametri fondamentali
DBSCAN usa due parametri:
- \varepsilon, raggio del vicinato;
- \mathrm{minPts}, numero minimo di punti richiesto per considerare densa una regione.
Il vicinato \varepsilon di un punto x_i è:
dove d è una distanza scelta, spesso euclidea. Il punto x_i è considerato punto core se:
La scelta di \varepsilon e \mathrm{minPts} determina l’intera struttura del risultato.
2. Tipi di punti
DBSCAN classifica i punti in tre categorie:
- core point: ha almeno \mathrm{minPts} punti nel proprio vicinato;
- border point: non è core, ma appartiene al vicinato di un punto core;
- noise point: non è core e non è raggiungibile da alcun punto core.
I punti di rumore non vengono assegnati a cluster. Questa è una differenza importante rispetto a molti algoritmi partizionali, che forzano ogni osservazione dentro un gruppo anche quando è isolata.
3. Raggiungibilità e connettività
Un punto q è direttamente raggiungibile per densità da un punto core p se:
Un punto è raggiungibile per densità se esiste una catena di punti core che collega i due punti. Un cluster è quindi una componente connessa di punti raggiungibili per densità, più eventuali punti di bordo associati.
Questa definizione consente a DBSCAN di trovare cluster curvi, allungati, concavi o irregolari, purché la densità locale resti sufficiente lungo la struttura.
4. Algoritmo operativo
In forma semplificata, l’algoritmo procede così:
- scegliere un punto non ancora visitato;
- calcolare il suo vicinato \varepsilon;
- se il punto non è core, marcarlo provvisoriamente come rumore;
- se è core, iniziare un nuovo cluster;
- espandere il cluster aggiungendo tutti i punti raggiungibili per densità;
- ripetere finché tutti i punti sono stati visitati.
Un punto inizialmente marcato come rumore può diventare punto di bordo se viene raggiunto durante l’espansione di un cluster.
5. Scelta di epsilon
La scelta di \varepsilon è il punto più delicato. Se è troppo piccolo, molti punti saranno classificati come rumore e i cluster verranno spezzati. Se è troppo grande, cluster distinti verranno fusi.
Una tecnica comune è il grafico delle distanze al k-esimo vicino, con k=\mathrm{minPts}. Si ordinano le distanze e si cerca un gomito: un punto in cui la distanza cresce rapidamente. Quel valore può suggerire una soglia \varepsilon ragionevole.
Questo criterio non è automatico. In dati rumorosi o ad alta dimensione il gomito può essere debole, assente o dipendente dalla scala delle variabili.
6. Scelta di minPts
Il parametro \mathrm{minPts} controlla quanto deve essere densa una regione per diventare cluster. Valori piccoli rendono l’algoritmo sensibile al rumore; valori grandi richiedono cluster più consistenti.
Una regola pratica è usare almeno:
dove p è la dimensione dello spazio, ma spesso si scelgono valori più alti per aumentare robustezza. In presenza di rumore forte, \mathrm{minPts} più grande riduce la probabilità che fluttuazioni casuali formino cluster spurii.
7. Distanza e standardizzazione
DBSCAN dipende direttamente dalla distanza. Se le variabili hanno scale diverse, la distanza euclidea può essere dominata da una sola variabile. Standardizzazione, trasformazioni o scelta di una metrica adeguata sono quindi passaggi essenziali.
In alcuni problemi può essere utile usare distanze diverse da quella euclidea, per esempio distanza di Manhattan, distanze su grafi, distanze per sequenze o misure basate su similarità. La definizione di densità deve però restare coerente con il significato fisico o operativo dei dati.
La distanza di Mahalanobis può essere utile quando le variabili sono fortemente correlate, ma va usata con cautela perché richiede una covarianza stimata in modo stabile.
8. Vantaggi
DBSCAN ha tre vantaggi principali:
- non richiede il numero di cluster in input;
- riconosce punti di rumore;
- trova cluster di forma arbitraria.
Questi aspetti lo rendono efficace in dati spaziali, traiettorie, segnali, dati geografici, segmentazione di eventi, anomaly detection e analisi esplorative in cui i gruppi non hanno forma ellissoidale.
9. Limiti
Il limite principale è la densità variabile. Se un dataset contiene un cluster molto denso e uno molto rarefatto, un solo valore di \varepsilon può essere inadatto: quello piccolo spezza il cluster rarefatto, quello grande fonde o allarga troppo il cluster denso.
Un altro limite è la dimensione alta. In spazi ad alta dimensionalità le distanze tendono a diventare meno informative: molti punti risultano quasi equidistanti e la nozione di vicinato locale perde forza. Prima di applicare DBSCAN può essere necessario ridurre dimensione o selezionare variabili.
Infine, DBSCAN non assegna probabilità di appartenenza. Se serve quantificare incertezza o sovrapposizione tra gruppi, un Gaussian Mixture Model può essere più adatto.
10. Valutazione del risultato
La valutazione di DBSCAN non dovrebbe limitarsi al numero di cluster ottenuti. Occorre controllare:
- quota di punti marcati come rumore;
- stabilità rispetto a \varepsilon e \mathrm{minPts};
- coerenza dei cluster con il dominio;
- sensibilità alla scala delle variabili;
- eventuale presenza di densità molto diverse.
Gli esercizi di cluster analysis aiutano a vedere come cambiano i risultati al variare delle scelte operative.
11. Errori comuni
Il primo errore è applicare DBSCAN con parametri predefiniti senza ispezionare le distanze. Il valore di \varepsilon non è universale.
Il secondo errore è interpretare tutti i punti noise come errori di misura. Alcuni possono essere anomalie reali, punti rari ma importanti o osservazioni appartenenti a cluster di densità diversa.
Il terzo errore è confrontare DBSCAN e k-means come se risolvessero lo stesso problema. k-means cerca una partizione intorno a centroidi; DBSCAN cerca regioni dense e può lasciare punti non assegnati.
12. Uso operativo
In un flusso tecnico, DBSCAN è indicato quando si sospetta che i cluster abbiano forma irregolare e che esistano outlier da non forzare in gruppi. La procedura robusta consiste nel standardizzare le variabili, scegliere una metrica coerente, esplorare il grafico delle distanze ai vicini, provare più combinazioni di parametri e verificare la stabilità del risultato.
Il metodo è potente proprio perché non impone cluster sferici; diventa però fragile se si dimentica che la densità è sempre definita rispetto a una scala, una metrica e una dimensione dello spazio.