Blog.

DBSCAN: Density-based spatial clustering of applications with noise


Autore
Andrea Provino
Data
Tempo di lettura
3 minuti
Categoria
Data Science, machine-learning

dbscan-density-based-spatial-clustering-of-application-with-noise-machine-learning-data-science

DBSCAN è l’acronimo inglese di Density-based spatial clustering of applications with noise, un sofisticato algoritmo di clustering comunemente usato per il Data Mining e Machine Learning.

Un passo alla volta.

Sai cos’è il clustering?

Benissimo, se avessi qualche dubbio, un post di approfondimento su tutto quello che devi sapere sul clustering è sempre lì a disposizione per te.

Negli ultimi giorni abbiamo analizzato dei noiosi strumenti di visualizzazione dati, conoscenze fondamentali nel portoflio di ogni data scientist.

Delle particolari librerie usate, Folium è senz’altro una delle più curiose: torna particolarmente utile per la visualizzazione di dati geo-spaziali (geospatial data).

È proprio questo il punto legame con l’argomento odierno: devi sapere che DBSCAN è un algoritmo di clustering density-based particolarmente appropriato per i dati spaziali.

Ok, ora sappiamo esattamente quanto prima.

Non va bene, dobbiamo scavare più a fondo.

Per procedere sono necessarie alcune conoscenze pregresse:

  • Principio di funzionamento degli algoritmi di clustering
  • Termini tecnici: centroidi

DBSCAN: Density-based spatial clustering

Gli algoritmi di clustering sono un esempio di unsupervised learning, dal momento che il loro funzionamento non richiede la presenza di una label nel dataset.

Ora, tra i nomi di clustering algorithm più comuni figurano certo il K-Means e l’Hierarchical Clustering.

Quando i dati richiedono lo sviluppo di cluster dalle forme arbitrarie o gruppi di cluster limitrofi e sovrapposti, le tecniche tradizionali faticano a ottenere buoni risultati:

  • Gli elementi all’interno del cluster potrebbero non condividere similarità sufficienti
  • Povere performance

Le difficoltà non terminano qui.

Gli algoritmi tradizionali sono privi della nozione di outliers, il DBSCAN è invece in grado di riconoscerli evitando che questi finiscano assegnati a un cluster pur non appartenendo ad alcuno di essi: un’operazione fondamentale nel campo della anomaly detection.

Le osservazioni aberranti avvicinano a sé i centroidi dei cluster, rendendo più complessa la loro gestione.

In contrasto, altri sistemi di clustering come il DBSCAN separano regioni ad alta e bassa densità.

Evidentemente per densità ci riferiamo al numero di osservazioni entro uno specifico raggio.

Ancora una volta, ora per questioni stilistiche, il DBSCAN è un popolare sistema di clustering density-based.

Uno dei meravigliosi vantaggi del DBSCAN è la capacità d’individuare cluster dalle forme arbitrarie senza rimanere influenzato dal rumore di fondo (noise).

How DBSCAN works

Il funzionamento del DBSCAN si basa sul presupposto che se una particolare osservazione appartenesse a uno specifico cluster, dovrebbe essere vicina alla maggior parte dei samples appartenenti al medesimo cluster.

Due parametri giocano un ruolo chiave:

  • radius
  • minimum points

Definiamo poi dense area quella regione di spazio delimitata dalla circonferenza di raggio epsilon contenete un sufficiente numero di datapoints.

Chi definisce questo sufficiente numero ?

INFN, Istituto Nazionale di Fisica Nucleare.

Scherzi a parte, lo decidiamo attraverso minimumSamples il parametro per il minum number of datapoints.

Ecco visivamente come opera:

Codice

Questo articolo ha una valenza prettamente teorica.

Ho comunque deciso di riportare giusto un minimo di codice.

Qui sotto trovi lo snippet di importazione con sklearn, invece a qui il codice del DBSCAN in Python.

from sklearn.cluster import DBSCAN 
epsilon = 0.3
minimumSamples = 7
db = DBSCAN(eps=epsilon, min_samples=minimumSamples).fit(X)

Conclusione

DBSCAN è un sofisticato strumento di clustering density-based che:

  • Identifica cluster dalle forme arbitrarie
  • Determina cluster circondati, o sovrapposti, da altri cluster.
  • Ha un senso di rumore
  • E’ robusto agli outliers
  • Non richiede la specificazione del numero totale di cluster.

Per approfondire.

Per il momento è tutto.

Per aspera, ad astra.

Un caldo abbraccio, Andrea

Taggeddata sciencedata scientistteoria


Ultimi post

Patricia Merkle Trie

Il Practical Algorithm To Retrieve Information Coded In Alphanumeric Merkle Trie, o Patricia Merkle Trie è una struttura dati chiave-valore usatada Ethereum e particolarmente efficiente per il salvataggio e la verifica dell’integrità dell’informazione. In questo post ne studieremo le caratteristiche. Prima di procedere, ci conviene ripassare l’introduzione al Merkle Tree nella quale abbiamo chiarito il […]

Andrea Provino
ethereum-patricia-merkle-tree
Tree Data Structure: cos’è un Merkle Tree

Un Merkle Tree è una struttura dati efficiente per verificare che un dato appartenga a un insieme esteso di elementi. È comunemente impiegato nelle Peer to Peer network in cui la generazione efficiente di prove (proof) contribuisce alla scalabilità della rete. Capire i vantaggi di questa struttura ci tornerà utile nel nostro percorso di esplorazione […]

Andrea Provino
merkle-tree-cover
UTXO: come funziona il modello Unspent Transaction Outputs

Per tenere traccia dei bilanci utente, la blockchain di Bitcoin sfrutta un modello di contabilità definito UTXO o Unspent Transaction Outputs. In questo articolo ne esaminiamo le caratteristiche. Ogni blockchain è dotata di un sistema di contabilità, un meccanismo attraverso cui tenere traccia dei bilanci di ciascun utente. I due grandi modelli di riferimento nel […]

Andrea Provino
bitcoin-utxo
Cos’è Ethereum

Possiamo definire Ethereum come una macchina a stati distribuita che traccia le transizioni di un archivio dati general-purpose (i.e. una memoria in grado di registrare qualsiasi dato esprimibile come coppia di chiave e valore o key-value) all’interno della Ethereum Blockchain. È arrivato il momento di esplorare uno dei progetti tecnologici più innovativi e interessanti degli […]

Andrea Provino
ethereum