DBSCAN: punti core, punti di bordo e rumore

K-Means presuppone che i cluster siano convessi e più o meno sferici. Non funziona con forme a mezzaluna, ad anello o allungate perché suddivide i punti in base alla distanza dai centroidi. DBSCAN (Density-Based Spatial Clustering of Applications with Noise) supera questo limite definendo i cluster come regioni dense separate da aree a bassa densità, e individua cluster di qualsiasi forma.

DBSCAN è controllato da due parametri: eps (epsilon) definisce il raggio del vicinato attorno a un punto, mentre min_samples imposta il numero minimo di punti, incluso il punto stesso, richiesto entro tale raggio affinché l’area venga considerata una regione densa. Insieme, questi parametri determinano quali punti siano punti core, punti di bordo o rumore.

Un punto è un punto core se almeno min_samples punti (incluso il punto stesso) si trovano a una distanza non superiore a eps. I punti core sono i semi da cui si sviluppano i cluster. Ogni punto nella regione di vicinato del punto core è direttamente raggiungibile da esso: questo costituisce la base per l'espansione del cluster.

Un punto di bordo ha meno di min_samples vicini entro eps, ma si trova nella regione di vicinato eps di un punto core. Appartiene al cluster del punto core, ma non contribuisce a espanderlo ulteriormente. Un punto è connesso per densità a un altro se esiste una catena di passaggi direttamente raggiungibili che li collega attraverso punti core.

I punti che sono né core né di bordo — punti isolati con troppo pochi vicini — vengono etichettati come rumore (label = -1 in scikit-learn). Questo rende DBSCAN un naturale rilevatore di outlier: le anomalie che non appartengono ad alcun cluster denso vengono automaticamente contrassegnate come rumore, senza alcuna configurazione aggiuntiva.

Utilizzi sklearn.cluster.DBSCAN. Dopo il fitting, db.labels_ contiene gli ID interi dei cluster, a partire da 0, mentre -1 indica il rumore. db.core_sample_indices_ elenca quali campioni sono punti core. Il numero di cluster viene determinato automaticamente: non è necessario specificare k in anticipo.

DBSCAN è particolarmente efficace su dataset come due lune interbloccate o anelli concentrici, cioè forme in cui K-Means fallisce completamente. Poiché DBSCAN espande i cluster lungo catene di densità, segue naturalmente la varietà curva dei dati. Questo rappresenta un vantaggio algoritmico fondamentale per i dati geospaziali, i cluster di cellule biologiche e i dataset con anomalie incorporate.

Un metodo pratico per scegliere eps consiste nel tracciare il grafico delle k-distanze: calcoli la distanza di ogni punto dal suo k-esimo vicino più prossimo (dove k = min_samples), ordini queste distanze e cerchi il gomito. La distanza in corrispondenza del gomito è una buona candidata per eps. I punti al di sopra del gomito si trovano in regioni poco dense (rumore); quelli al di sotto si trovano in regioni dense.

Aumentando eps si uniscono i cluster (alla fine tutto diventa un unico cluster). Diminuendo eps si creano più cluster e più rumore. Aumentando min_samples si richiedono punti core più densi, rendendo più difficile la formazione dei cluster e generando più punti di rumore. È necessario regolare entrambi i parametri insieme: il grafico delle k-distanze guida la scelta di eps, mentre min_samples viene generalmente impostato, come punto di partenza, sulla dimensionalità dei dati più uno.

Utilizzi DBSCAN quando: i cluster hanno forme irregolari, non conosce k in anticipo, il rilevamento degli outlier è importante oppure i dati presentano densità variabile. Utilizzi K-Means quando: i cluster sono approssimativamente sferici, il dataset è molto grande (DBSCAN ha complessità O(n log n) con un indice spaziale) oppure deve ottenere un numero specifico di cluster per ragioni aziendali, come la segmentazione del mercato in esattamente 5 regioni.

DBSCAN è particolarmente diffuso per il clustering geospaziale (per individuare gli hotspot nei dati GPS), perché identifica naturalmente le aree urbane dense marcando al contempo come rumore i punti rurali sparsi. Utilizzi metric='haversine' e converta le coordinate in radianti per raggruppare i punti in base alla distanza lungo il cerchio massimo sulla superficie terrestre. Il risultato consiste in cluster geograficamente significativi, senza doverne specificare il numero.

In questa lezione ha imparato che: DBSCAN classifica i punti come core, di bordo o rumore in base al raggio eps e alla soglia min_samples; individua cluster di forma arbitraria concatenando punti core raggiungibili per densità; e i punti di rumore (label -1) sono outlier automatici, una funzionalità che K-Means non offre. Prossimamente applicheremo il clustering dall'inizio alla fine in un progetto di segmentazione dei clienti.