DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

DBSCAN (clustering spaziale basato sulla densità con rumore) è un algoritmo di apprendimento non supervisionato che raggruppa in cluster i punti molto vicini tra loro e contrassegna come rumore quelli nelle regioni poco dense. Martin Ester, Hans-Peter Kriegel, Jörg Sander e Xiaowei Xu lo hanno presentato alla conferenza KDD nel 1996. Non richiede di specificare in anticipo il numero di cluster, segue cluster di qualsiasi forma, per esempio anelli, mezzelune o strade tortuose, e l'etichetta di rumore funge anche da semplice forma di rilevamento delle anomalie. L'intero algoritmo è controllato da due parametri: il raggio del vicinato e il numero di punti necessario perché un vicinato sia considerato denso.

Punti centrali, punti di confine e rumore#

DBSCAN esamina il vicinato di ogni punto, ovvero l'insieme dei punti entro una distanza eps, e ne conta gli elementi:

• Punto centrale: ha almeno min_samples punti nel proprio vicinato, includendo se stesso nell'implementazione di scikit-learn. I punti centrali formano l'interno denso di un cluster.
• Punto di confine: ha troppi pochi vicini per essere un punto centrale, ma si trova entro eps da uno di essi. I punti di confine formano i margini di un cluster.
• Punto di rumore: non è né l'uno né l'altro, quindi non appartiene ad alcun cluster e riceve l'etichetta -1.

Un cluster cresce a partire da qualsiasi punto centrale non ancora visitato. DBSCAN aggiunge tutti i punti del suo vicinato, poi riparte da ogni nuovo punto centrale aggiunto, finché non ci sono più punti raggiungibili; così, una catena di vicinati densi sovrapposti diventa un unico cluster, indipendentemente dalle sue curve. I punti di confine si uniscono a un cluster senza estenderlo. Il risultato è deterministico a parità di ordine dell'input, ma un punto di confine raggiungibile da due cluster si unisce al primo che lo raggiunge, quindi mescolare i dati può spostare i punti di confine da un cluster all'altro.

Scelta di eps e min_samples#

Il raggio eps è il fattore più importante e dipende dalla scala dei dati; per questo di solito le caratteristiche vengono prima standardizzate. Se il raggio è troppo piccolo, la maggior parte dei punti viene considerata rumore; se è troppo grande, i cluster vicini si fondono. L'euristica abituale ordina la distanza di ogni punto dal suo k-esimo vicino più prossimo, con k uguale a min_samples, e sceglie eps in corrispondenza del gomito della curva, dove le distanze iniziano ad aumentare rapidamente. Valori maggiori di min_samples rendono il clustering più tollerante al rumore e sono comuni nei dataset grandi o rumorosi. Negli spazi ad alta dimensionalità, come quelli degli embedding di immagini, le distanze tra punti diventano simili tra loro; per questo spesso si applica una riduzione della dimensionalità, come l'analisi delle componenti principali (PCA), prima di eseguire DBSCAN.

DBSCAN, K-Means e HDBSCAN a confronto#

Il clustering k-means richiede di specificare in anticipo il numero di cluster, assegna ogni punto al centroide più vicino e tende quindi a favorire cluster compatti e rotondi, includendo i valori anomali in qualche gruppo. DBSCAN individua il numero di cluster in base alla densità e lascia fuori i valori anomali. Il suo punto debole è un unico eps globale: quando i cluster hanno densità molto diverse, nessun raggio distingue i cluster radi dal rumore e quelli densi tra loro. HDBSCAN affronta il problema eseguendo di fatto DBSCAN per tutti i valori di eps e mantenendo i cluster più stabili; entrambi gli algoritmi sono disponibili nel modulo di clustering di scikit-learn, insieme al correlato OPTICS.

Questo esempio raggruppa due mezzelune intrecciate con 20 valori anomali casuali aggiunti e valuta ogni risultato rispetto ai gruppi reali usando l'indice di Rand corretto, in cui 1.0 indica una corrispondenza perfetta:

import numpy as np
from sklearn.cluster import DBSCAN, KMeans
from sklearn.datasets import make_moons
from sklearn.metrics import adjusted_rand_score

# Two interleaving crescents plus 20 scattered outliers (true label -1)
X, y = make_moons(n_samples=300, noise=0.05, random_state=0)
rng = np.random.default_rng(0)
X = np.vstack([X, rng.uniform(-1.5, 2.5, size=(20, 2))])
y = np.concatenate([y, np.full(20, -1)])

# DBSCAN infers clusters from density; k-means is told there are 2
db_labels = DBSCAN(eps=0.2, min_samples=5).fit_predict(X)
km_labels = KMeans(n_clusters=2, random_state=0).fit_predict(X)

print(f"DBSCAN: {db_labels.max() + 1} clusters, {(db_labels == -1).sum()} noise points")
print(f"ARI: DBSCAN {adjusted_rand_score(y, db_labels):.2f}, k-means {adjusted_rand_score(y, km_labels):.2f}")

Lo script stampa 2 cluster e 15 punti di rumore per DBSCAN, e indici di Rand corretti pari a 0.97 per DBSCAN e 0.20 per k-means. DBSCAN segue entrambe le mezzelune e isola i valori anomali che si trovano lontano da esse, mentre k-means taglia le mezzelune con un confine rettilineo, pur avendo ricevuto il numero corretto di cluster.

Applicazioni nel mondo reale#

• Percezione LiDAR: le pipeline per veicoli autonomi e robotica rimuovono i punti del terreno da una scansione LiDAR e raggruppano poi i punti 3D rimanenti in ostacoli separati; il clustering basato sulla densità è una scelta comune perché il numero di oggetti è sconosciuto.
• Post-elaborazione del rilevamento: i centri dei riquadri dei rilevamenti YOLO26, disponibili come result.boxes.xywh, possono essere raggruppati con DBSCAN per trovare gruppi di persone in una folla o difetti ricorrenti su una linea di produzione; i rilevamenti isolati vengono così classificati come rumore.
• Monitoraggio delle frodi e dei sensori: le transazioni o le letture etichettate -1 sono molto distanti da ogni gruppo denso di comportamenti normali e diventano candidate per una revisione.
• Analisi geospaziale: le aziende di consegna e di ride-hailing raggruppano i punti GPS per individuare le soste frequenti e le zone di prelievo più gettonate. DBSCAN di Scikit-learn accetta metric="haversine" per latitudine e longitudine in radianti; in questo caso, eps è un angolo sulla sfera unitaria, quindi un raggio di 100 metri diventa eps = 0.1 / 6371, usando il raggio medio terrestre di 6,371 km.