Dbscan

Da Wikipedia, l'enciclopedia libera.

Il DBSCAN (Density-Based Spatial Clustering of Applications with Noise) è un metodo di clustering proposto nel 1996 da Martin Ester, Hans-Peter Kriegel, Jörg Sander and Xiaowei Xu. È basato sulla densità perché connette regioni di punti con densità sufficientemente alta. DBSCAN è l'algoritmo più comunemente usato ed è anche il più citato nella letteratura scientifica.

Idea fondamentale[modifica | modifica sorgente]

Points at A are core points. Points B and C are density-reachable from A and thus density-connected and belong to the same cluster. Point N is a noise point that is neither a core point nor density-reachable. (MinPts=3 or MinPts=4)

DBSCAN ha una definizione di cluster basata sulla nozione di density-reachability. Fondamentalmente, un punto q è direttamente raggiungibile da un punto p se non viene superata una data distanza \varepsilon (cioè, è parte del suo \varepsilon-vicinato) e se p è circondato da un numero sufficiente di punti, allora p e q possono essere considerati parti di un cluster. Si può affermare che q è density-reachable da p se c'è una sequenza p_1,\ldots,p_n di punti con p_1 = p e p_n = q dove ogni p_{i+1} è density-reachable direttamente da p_i. Si osservi che la relazione density-reachable non è simmetrica (dato che q potrebbe situarsi su una periferia del cluster, avendo un numero insufficiente di vicini per considerarlo un elemento genuino del cluster). Di conseguenza la nozione density-connected diventa: due punti p e q sono density-connected se c'è un punto o tale che sia o e p che o e q sono density-reachable.

Un cluster, che è un sotto-insieme dei punti del database, soddisfa due proprietà:

  1. Tutti i punti all'interno del cluster sono mutualmente density-connected.
  2. Se un punto è density-connected a un altro punto del cluster, anch'esso è parte del cluster.

Algoritmo[modifica | modifica sorgente]

DBSCAN necessita di due parametri: \varepsilon (eps) e del numero minimo di punti richiesti per formare un cluster (minPts). Si comincia con un punto casuale che non è stato ancora visitato. Viene calcolato il suo \varepsilon-vicinato, e se contiene un numero sufficiente di punti viene creato un nuovo cluster. Se ciò non avviene, il punto viene etichettato come rumore. Si osservi che il punto potrebbe essere successivamente ritrovato in un \varepsilon-vicinato sufficientemente grande riconducibile ad un punto differente e, di conseguenza, essere inserito in un cluster.

Se un punto è associato ad un cluster, anche i punti del suo \varepsilon-vicinato sono parte del cluster. Conseguentemente, tutti i punti trovati all'interno del suo \varepsilon-vicinato sono aggiunti al cluster, così come i loro \varepsilon-vicinati. Questo processo continua fino a quando il cluster viene completato. Allora, un nuovo punto non visitato viene estratto e processato, portando alla scoperta di un ulteriore cluster o di rumore.

Pseudo codice[modifica | modifica sorgente]

DBSCAN(D, eps, MinPts)
   C = 0
   Per ogni punto P non visitato nel dataset D
      contrassegna P come visitato
      N = getVicini (P, eps)
      se dimensioneDi(N) < MinPts
         contrassegna P come RUMORE
      altrimenti
         C = cluster successivo
         espandiCluster(P, N, C, eps, MinPts)
          
espandiCluster(P, N, C, eps, MinPts)
   aggiungi P al cluster C
   per ogni punto P' in N 
      se P' non è stato visitato
         contrassegna P' come visitato
         N' = getVicini(P', eps)
         if dimensioneDi(N') >= MinPts
            N = N unito con N'
      se P' non è ancora membro di qualche cluster
         aggiungi P' al cluster C

Complessità[modifica | modifica sorgente]

DBSCAN visita ogni punto del database, anche più volte (es. punti candidati a cluster differenti). Per considerazioni pratiche, tuttavia, la complessità temporale è per lo più governata dal numero di invocazioni a getVicini. DBSCAN esegue esattamente una invocazione per ogni punto, e se viene utilizzata una struttura indicizzata che esegue un'interrogazione del vicinato in O(\log n), si ottiene un tempo globale di esecuzione pari a O(n \cdot \log n). Senza l'uso di strutture indicizzate, il tempo di esecuzione è pari a O(n^2). Spesso la matrice delle distanze di dimensione (n^2-n)/2 viene creata per evitare appunto il ricalcolo delle distanze. Ciò, tuttavia, necessita di O(n^2) come memoria.

Vantaggi[modifica | modifica sorgente]

  1. DBSCAN non richiede di conoscere il numero di cluster a priori, al contrario dell'algoritmo K-means.
  2. DBSCAN può trovare cluster di forme arbitrarie. Può anche trovare un cluster completamente circondato da (ma non connesso a) un cluster differente. Dato il parametro MinPts, il cosiddetto effetto single-link (cluster differenti connessi da una sottile linea di punti) viene ridotto.
  3. DBSCAN possiede la nozione di rumore.
  4. DBSCAN richiede soltanto due parametri ed è per lo più insensibile all'ordine dei punti nel database. (Solo i punti posizionati sull'arco fra due cluster differenti può cambiare la sua appartenenza se l'ordine dei punti viene cambiato. L'assegnamento ai cluster è unico solo su isomorfismi).

Svantaggi[modifica | modifica sorgente]

  1. DBSCAN non può che comportare un clustering buono quanto la sua misura della distanza che è riconducibile alla funzione getVicini(P,epsilon). La più comune misura usata è la distanza euclidea. In particolare per il high-dimensional data, questa misura della distanza diventa quasi inutile tanto da esser denominata "Maledizione della dimensionalità"; nei fatti diventa difficile trovare un valore appropriato per epsilon. Questo effetto, tuttavia, è presente anche in altri algoritmi basatii sulla distanza euclidea.
  2. DBSCAN non è in grado di classificare insiemi di dati con grandi differenze nelle densità, dato che la combinazione minPts-epsilon non può poi essere scelta in modo appropriato per tutti i cluster.

Guarda la sezione in basso sulle estensioni per modifiche algoritmiche che gestiscono queste caratteristiche.

Rilevamento vicinato più vicino[modifica | modifica sorgente]

Il rilevamento del vicinato più vicino avviene nella funzione getVicini(P,epsilon). Per ogni punto P vengono calcolati tutti gli altri punti che sono all'interno dell'intervallo epsilon, basandosi sulla funzione della distanza usata nell'algoritmo. L'analisi richiede che sia calcolata una matrice delle distanze per l'intero data set. La generazione della matrice delle distanze ha una complessità di O((n2-n)/2) dato che è necessaria solo una matrice triangolare superiore. All'interno della matrice delle distanze il vicinato più vicino può essere calcolato selezionando la tupla che ha come valori il minimo delle funzioni su riga e colonna. La ricerca ha spinto il rilevamento del vicinato, nei database tradizionali, per migliorare la velocità. Questi ultimi risolvono il problema utilizzando indici specificatamente progettati per questo tipo di applicazioni.

Stima dei parametri[modifica | modifica sorgente]

Ogni processo di data mining ha il problema dei parametri. Ogni parametro influenza l'algoritmo in modo specifico. Per il DBSCAN i parametri epsilon e MinPnts sono necessari. I parametri devono essere specificati dall'utente dato che ogni data set richiede parametri differenti. Un valore iniziale per \varepsilon può essere determinato come un k-distance graph. Come per le regole del pollice, k può essere derivato dal numero di dimensioni nel data set D come k=D+1. Tuttavia, valori maggiori sono usualmente migliori per data set con rumore.

Anche se questa stima dei parametri restituisce un insieme sufficiente di parametri, la classificazione risultante può rivelarsi diversa da ciò che si aspetta. Pertanto la ricerca ha realizzato una incrementale ottimizzazione dei parametri su particolari valori.

Altro[modifica | modifica sorgente]

Per ogni oggetto, saranno trovati i vicini che ricadono in un raggio dato come parametro in ingresso; se il numero di tali vicini è superiore ad un fattore di soglia (anch'esso fornito in input all'algoritmo), allora tali punti faranno parte del medesimo cluster di quello dell'oggetto che si sta osservando (in questo caso il nostro punto sarà denominato core point).

Al termine dell'algoritmo avremo dei punti appartenenti a cluster e punti lasciati liberi; questi ultimi saranno rumore. Un oggetto q è direttamente rintracciabile in base alla densità rispetto ad un punto p, se q è un vicino di p (con lo stesso raggio dato in input), con il rispetto del minimo numero di vicini per quanto riguarda p.

Se c'è una catena di oggetti da attraversare (con i consueti vincoli) per raggiungere un punto q da uno p, allora q sarà detto semplicemente rintracciabile.

Ultimo caso è quello in cui due oggetti "p" e "q" sono detti connessi: per essere definiti in tal modo, deve esistere un terzo punto o, per il quale "p" e "q" sono entrambi rintracciabili.

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica