Ok, iniziamo a parlare di DBSCAN.
Il clustering spaziale basato sulla densità delle applicazioni con rumore (DBSCAN) è un noto algoritmo di clustering dei dati che è comunemente usato nel data mining e nel machine learning.
Basato su un insieme di punti (pensiamo in uno spazio bidimensionale come esemplificato nella figura), DBSCAN raggruppa i punti che sono vicini tra loro in base a una misura di distanza (di solito la distanza euclidea) e un numero minimo di punti. Segna anche come outlier i punti che si trovano in regioni a bassa densità.
Parametri:
L’algoritmo DBSCAN richiede fondamentalmente 2 parametri:
eps: specifica quanto vicini devono essere i punti tra loro per essere considerati parte di un cluster. Significa che se la distanza tra due punti è inferiore o uguale a questo valore (eps), questi punti sono considerati vicini.
minPoints: il numero minimo di punti per formare una regione densa. Per esempio, se impostiamo il parametro minPoints a 5, allora abbiamo bisogno di almeno 5 punti per formare una regione densa.
Stima dei parametri:
La stima dei parametri è un problema per ogni attività di data mining. Per scegliere buoni parametri abbiamo bisogno di capire come vengono utilizzati e avere almeno una conoscenza di base precedente sul set di dati che verrà utilizzato.
eps: se il valore eps scelto è troppo piccolo, una gran parte dei dati non sarà clusterizzata. Saranno considerati outlier perché non soddisfano il numero di punti per creare una regione densa. D’altra parte, se il valore scelto è troppo alto, i cluster si fonderanno e la maggior parte degli oggetti sarà nello stesso cluster. L’eps dovrebbe essere scelto in base alla distanza del dataset (possiamo usare un grafico di k-distance per trovarlo), ma in generale sono preferibili piccoli valori di eps.
minPoints: Come regola generale, un minimo di minPoints può essere derivato da un numero di dimensioni (D) nel set di dati, come minPoints ≥ D + 1. Valori più grandi sono di solito migliori per i set di dati con rumore e formeranno cluster più significativi. Il valore minimo per i minPoints deve essere 3, ma più grande è il set di dati, più grande è il valore di minPoints che dovrebbe essere scelto.
Puoi trovare maggiori informazioni sulla stima dei parametri qui.
Perché dovremmo usare DBSCAN?
L’algoritmo DBSCAN dovrebbe essere usato per trovare associazioni e strutture nei dati che sono difficili da trovare manualmente ma che possono essere rilevanti e utili per trovare modelli e prevedere tendenze.
I metodi di clustering sono di solito usati in biologia, medicina, scienze sociali, archeologia, marketing, riconoscimento dei caratteri, sistemi di gestione e così via.
Pensiamo ad un uso pratico di DBSCAN. Supponiamo di avere un e-commerce e di voler migliorare le nostre vendite raccomandando prodotti rilevanti ai nostri clienti. Non sappiamo esattamente cosa stanno cercando i nostri clienti, ma sulla base di un set di dati possiamo prevedere e raccomandare un prodotto rilevante a un cliente specifico. Possiamo applicare il DBSCAN al nostro set di dati (basato sul database dell’e-commerce) e trovare cluster basati sui prodotti che gli utenti hanno acquistato. Usando questi cluster possiamo trovare somiglianze tra i clienti, per esempio, il cliente A ha comprato 1 penna, 1 libro e 1 forbice e il cliente B ha comprato 1 libro e 1 forbice, allora possiamo raccomandare 1 penna al cliente B. Questo è solo un piccolo esempio di utilizzo di DBSCAN, ma può essere usato in un sacco di applicazioni in diversi settori.
Come possiamo implementarlo facilmente?
Come ho già scritto (consiglio: non credete a tutto quello che scrivo) il DBSCAN è un algoritmo ben noto, quindi, non dovete preoccuparvi di implementarlo da soli. Puoi usare una delle librerie/pacchetti che si possono trovare su internet. Ecco una lista di link dove potete trovare l’implementazione di DBSCAN: Matlab, R, R, Python, Python.
Ho anche sviluppato un’applicazione (in portoghese) per spiegare come funziona DBSCAN in modo didattico. L’applicazione è stata scritta in C++ e potete trovarla su Github.