DBSCAN: Cos'è? Quando usarlo? Come usarlo.

DBSCAN (clustering spaziale basato su densità di applicazioni con rumore) è un popolare metodo di apprendimento non supervisionato utilizzato negli algoritmi di costruzione di modelli e machine learning. Prima di andare oltre, dobbiamo definire che cos'è un metodo di apprendimento "senza supervisione". I metodi di apprendimento senza supervisione sono quando non ci sono obiettivi o risultati chiari che stiamo cercando di trovare. Invece, stiamo raggruppando i dati in base alla somiglianza delle osservazioni. Per chiarire, prendiamo Netflix come esempio. Sulla base degli spettacoli precedenti che hai visto in passato, Netflix ti consiglierà di guardare gli spettacoli successivi. Chiunque abbia mai guardato o è stato su Netflix ha visto lo schermo qui sotto con consigli (Sì, questa immagine è presa direttamente dal mio account Netflix e se non hai mai visto Shameless prima di suggerire di salire su APPENA POSSIBILE).

Poiché ho visto "Shameless", Netflix mi consiglia di guardare molti altri spettacoli simili. Ma da dove sta raccogliendo questi consigli Netflix? Considerando che sta cercando di prevedere il futuro con quale spettacolo guarderò dopo, Netflix non ha nulla su cui basare le previsioni o le raccomandazioni (nessun chiaro obiettivo definitivo). Invece, Netflix guarda altri utenti che hanno anche guardato "Shameless" in passato e guarda ciò che quegli utenti hanno guardato oltre a "Shameless". In questo modo, Netflix raggruppa i suoi utenti in base alla somiglianza degli interessi. Questo è esattamente come funziona l'apprendimento senza supervisione. Raggruppando semplicemente le osservazioni in base alla somiglianza, sperando di trarre conclusioni accurate sulla base dei cluster.

Torna a DBSCAN. DBSCAN è un metodo di clustering utilizzato nell'apprendimento automatico per separare i cluster di alta densità dai cluster di bassa densità. Dato che DBSCAN è un algoritmo di clustering basato sulla densità, svolge un ottimo lavoro nel ricercare aree nei dati con un'alta densità di osservazioni, rispetto alle aree dei dati che non sono molto dense di osservazioni. DBSCAN può anche ordinare i dati in cluster di forme diverse, un altro vantaggio notevole. DBSCAN funziona come tale:

  • Divide il set di dati in n dimensioni
  • Per ogni punto nel set di dati, DBSCAN forma una forma n dimensionale attorno a quel punto dati, quindi conta il numero di punti dati che rientrano in quella forma.
  • DBSCAN conta questa forma come un cluster. DBSCAN espande in modo iterativo il cluster, esaminando ogni singolo punto all'interno del cluster e contando il numero di altri punti dati nelle vicinanze. Prendi il seguente grafico per un esempio:

Seguendo passo per passo il processo di cui sopra, DBSCAN inizierà dividendo i dati in n dimensioni. Dopo che DBSCAN lo ha fatto, inizierà in un punto casuale (in questo caso supponiamo che fosse uno dei punti rossi) e conterà quanti altri punti si trovano nelle vicinanze. DBSCAN continuerà questo processo fino a quando non ci saranno altri punti dati nelle vicinanze e quindi cercherà di formare un secondo cluster.

Come avrai notato dal grafico, ci sono un paio di parametri e specifiche che dobbiamo fornire a DBSCAN prima che funzioni. I due parametri che dobbiamo specificare sono tali:

Qual è il numero minimo di punti dati necessari per determinare un singolo cluster?
Quanto lontano può essere un punto dal punto successivo all'interno dello stesso cluster?

Facendo riferimento al grafico, epsilon è il raggio indicato per testare la distanza tra i punti dati. Se un punto rientra nella distanza epsilon di un altro punto, quei due punti saranno nello stesso cluster.

Inoltre, il numero minimo di punti necessari è impostato su 4 in questo scenario. Quando si passa attraverso ciascun punto dati, finché DBSCAN trova 4 punti a una distanza di epsilon l'uno dall'altro, si forma un cluster.

IMPORTANTE: Affinché un punto sia considerato un punto "centrale", deve contenere il numero minimo di punti entro la distanza epsilon. Ergo, la visualizzazione in realtà ha solo DUE punti fondamentali. Visualizza la documentazione qui e guarda il parametro min_samples in particolare.

Noterai anche che il punto blu nel grafico non è contenuto in nessun cluster. DBSCAN NON classifica necessariamente tutti i punti di dati ed è quindi eccezionale nel gestire i valori anomali nel set di dati. Esaminiamo il grafico seguente:

L'immagine a sinistra raffigura un metodo di clustering più tradizionale che non tiene conto della multidimensionalità. Considerando che l'immagine giusta mostra come DBSCAN può contorcere i dati in diverse forme e dimensioni al fine di trovare cluster simili.

L'immagine a sinistra raffigura un metodo di clustering più tradizionale, come K-Means, che non tiene conto della multidimensionalità. Considerando che l'immagine giusta mostra come DBSCAN può contorcere i dati in diverse forme e dimensioni al fine di trovare cluster simili. Notiamo anche nell'immagine giusta che i punti lungo il bordo esterno del set di dati non sono classificati, suggerendo che sono valori anomali tra i dati.

Vantaggi di DBSCAN:

  • È eccezionale nel separare i cluster di alta densità rispetto ai cluster di bassa densità all'interno di un determinato set di dati.
  • È ottimo con la gestione dei valori anomali all'interno del set di dati.

Svantaggi di DBSCAN:

  • Non funziona bene quando si hanno a che fare con cluster di densità variabile. Mentre DBSCAN è bravo a separare i cluster ad alta densità dai cluster a bassa densità, DBSCAN lotta con cluster di densità simile.
  • Lotta con dati ad alta dimensionalità. Lo so, in questo intero articolo ho affermato come DBSCAN sia eccezionale nel contorto i dati in diverse dimensioni e forme. Tuttavia, DBSCAN può andare così lontano, se dati dati con troppe dimensioni, DBSCAN ne soffre

Di seguito ho incluso come implementare DBSCAN in Python, in cui in seguito spiegherò le metriche e la valutazione del tuo modello DBSCAN

Implementazione DBSCAN in Python

1. Assegnare i dati come i nostri valori X.
Ricorda, poiché si tratta di un apprendimento non supervisionato, non abbiamo alcun valore y da impostare.
2. Istanziare il nostro modello DBSCAN. Nel codice seguente, epsilon = 3 e min_samples è il numero minimo di punti necessari per costituire un cluster.
3. Memorizzazione delle etichette formate dal DBSCAN
4. Identificare quali punti compongono i nostri "punti fondamentali"
5. Calcolo del numero di cluster
6. Calcolo del punteggio silhouette

Metriche per la misurazione delle prestazioni di DBSCAN:

Punteggio silhouette: il punteggio silhouette viene calcolato utilizzando la distanza media tra i punti e la distanza media tra i cluster. Ad esempio, un cluster con molti punti dati molto vicini tra loro (alta densità) E è molto lontano dal cluster più vicino successivo (il che suggerisce che il cluster è molto unico rispetto al successivo più vicino), avrà un punteggio di silhouette forte . Un punteggio silhouette varia da -1 a 1, con -1 che è il punteggio peggiore possibile e 1 che è il punteggio migliore. I punteggi di silhouette di 0 suggeriscono cluster sovrapposti.

Inerzia: l'inerzia misura la somma dei cluster interni dei quadrati (la somma dei quadrati è la somma di tutti i residui). L'inerzia viene utilizzata per misurare quanto i cluster correlati sono tra loro, più basso è il punteggio di inerzia, meglio è. Tuttavia, è importante notare che l'inerzia dipende fortemente dal presupposto che i cluster siano convessi (di forma sferica). DBSCAN non divide necessariamente i dati in cluster sferici, quindi l'inerzia non è una buona metrica da utilizzare per la valutazione dei modelli DBSCAN (motivo per cui non ho incluso l'inerzia nel codice sopra). L'inerzia è più spesso utilizzata in altri metodi di clustering, come il clustering di K-significa.

Altre risorse:

Il blog di Naftali Harris è un'enorme risorsa aggiuntiva per ulteriori informazioni