
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.
DBSCAN usa una definizione di cluster basata sulla nozione di "density-reachability". Un punto formula_1 è direttamente raggiungibile da un punto formula_2 se la loro distanza è minore di un assegnato formula_3 (cioè, è parte del suo formula_3-vicinato) e se formula_2 è circondato da un sufficiente numero di punti, allora formula_2 e formula_1 possono essere considerati parti di un cluster. Il punto formula_1 è "density-reachable" da formula_2 se c'è una sequenza formula_10 di punti con formula_11 e formula_12 dove ogni formula_13 è density-reachable direttamente da formula_14. Si osservi che la relazione density-reachable non è simmetrica dato che formula_1 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 formula_2 e formula_1 sono density-connected se c'è un punto formula_18 tale che sia formula_18 e formula_2 sia formula_18 e formula_1 sono density-reachable.
Un cluster, che è un sotto-insieme dei punti del database, soddisfa due proprietà:
DBSCAN necessita di due parametri: formula_3 (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 formula_3-vicinato e se contiene un numero sufficiente di punti viene creato un nuovo cluster. Se ciò non avviene il punto viene etichettato come rumore e successivamente potrebbe essere ritrovato in un formula_3-vicinato sufficientemente grande riconducibile ad un punto differente entrando a far parte di un cluster.
Se un punto è associato ad un cluster anche i punti del suo formula_3-vicinato sono parte del cluster. Conseguentemente tutti i punti trovati all'interno del suo formula_3-vicinato sono aggiunti al cluster, così come i loro formula_3-vicinati. Questo processo continua fino a quando il cluster viene completato. Il processo continua fino a quando non sono stati visitati tutti i punti.
 DBSCAN(D, eps, MinPts)
DBSCAN visita ogni punto del database, anche più volte nel caso di punti candidati a cluster differenti. Tuttavia per considerazioni pratiche la complessità temporale è per lo più governata dal numero di invocazioni a getVicini, in riferimento allo pseudo codice di cui sopra. DBSCAN esegue esattamente una invocazione per ogni punto e se viene utilizzata una struttura indicizzata che esegue un'interrogazione del vicinato in formula_29, si ottiene un tempo globale di esecuzione pari a formula_30. Senza l'uso di strutture indicizzate, il tempo di esecuzione è pari a formula_31. Spesso la matrice delle distanze di dimensione formula_32 viene creata per evitare appunto il ricalcolo delle distanze riducendo il tempo di elaborazione a spese della memoria utilizzata pari a formula_31.
DBSCAN presenta i seguenti vantaggi:
Il rilevamento del vicinato più vicino avviene nella funzione getVicini(P,epsilon). Per ogni punto P vengono determinati 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 formula_34dato 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 specificamente progettati per questo tipo di applicazioni.
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 formula_3 può essere determinato come un k-distance graph. Come per le regole del pollice, formula_36 può essere derivato dal numero di dimensioni nel data set formula_37 come formula_38. 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 un'incrementale ottimizzazione dei parametri su particolari valori.
Per ogni oggetto vengono trovati i vicini che ricadono in un raggio dato come parametro in ingresso; se il numero di questi vicini è superiore ad un fattore di soglia, anch'esso fornito in input all'algoritmo, allora questi punti fanno parte del medesimo cluster di quello dell'oggetto che si sta osservando e in questo caso il punto è denominato core point.
Al termine dell'algoritmo ci potrebbero essere alcuni punti non appartenenti a cluster catalogati come "rumore".
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 cui "p" e "q" sono entrambi rintracciabili.


Lo scarto quadratico medio (o deviazione standard o scarto tipo) è un indice di dispersione statistico, vale a dire una stima della variabilità di una popolazione di dati o di una variabile casuale.
È uno dei modi per esprimere la dispersione dei dati intorno ad un indice di posizione, quale può essere, ad esempio, la media aritmetica o una sua stima. Ha pertanto la stessa unità di misura dei valori osservati (al contrario della varianza che ha come unità di misura il quadrato dell'unità di misura dei valori di riferimento). In statistica la precisione si può esprimere come lo scarto quadratico medio.
Il termine ""standard deviation"" è stato introdotto in statistica da Pearson nel 1894 assieme alla lettera greca formula_1 (sigma) che lo rappresenta. Il termine italiano "deviazione standard" ne è la traduzione più utilizzata nel linguaggio comune; il termine dell'Ente Nazionale Italiano di Unificazione è tuttavia "scarto tipo", definito come la radice quadrata positiva della varianza per lo meno fin dal 1984.
Se non indicato diversamente, lo scarto quadratico medio è la radice quadrata della varianza, la quale viene coerentemente rappresentata con il quadrato di sigma (formula_2).
In statistica lo scarto quadratico medio di un carattere rilevato su una popolazione di formula_3 unità statistiche si definisce esplicitamente come:
dove formula_5 è la media aritmetica di formula_6.
Formalmente lo scarto quadratico medio di una variabile può essere calcolata a partire dalla funzione generatrice dei momenti, in particolare è la radice quadrata della differenza tra il momento secondo ed il momento primo elevato al quadrato.
A partire dallo scarto quadratico medio si definisce anche il coefficiente di variazione o la "deviazione standard relativa" come il rapporto tra lo scarto tipo formula_7 e il valore assoluto della media aritmetica della variabile in esame:
Questo indice relativo (che viene spesso espresso in termini percentuali) consente di effettuare confronti tra dispersioni di dati di tipo diverso, indipendentemente dalle loro quantità assolute.
Nell'ambito della statistica inferenziale (dove è noto solo un campione della popolazione), soprattutto nell'ambito della teoria della stima, a volte si rimpiazza il denominatore formula_3 con formula_10 ottenendo:
Sostanzialmente, poiché non è nota la media dell'intera popolazione, ma solo una sua stima (la media del campione), bisogna utilizzare formula_10 per ottenere uno stimatore corretto formula_13 della varianza incognita formula_7 di formula_6 sull'intera popolazione a partire dai dati del campione. La sua radice quadrata diviene lo scarto quadratico medio "corretto".
Questa correzione al denominatore fa sì che la nuova definizione sia un po' più grande della precedente, correggendo così la tendenza della precedente a sottostimare le incertezze soprattutto nel caso in cui si lavori con pochi dati (formula_3 piccolo).
Osserviamo il caso limite di formula_17, cioè quando si ha un campione di un solo elemento: la prima definizione dà il risultato formula_18, che ovviamente non è molto ragionevole nell'ambito della statistica inferenziale, mentre quella "corretta" dà un risultato non definito del tipo formula_19, rispecchiando così la totale ignoranza inerente all'incertezza su una singola misura. In questo senso, si dice che la statistica non dice nulla sul singolo caso.
Osserviamo che la differenza tra le due definizioni per campioni molto estesi è spesso numericamente insignificante.
Il calcolo può essere semplificato come segue:
cioè, applicando il tutto alla formula originale:
Sia formula_6 una variabile aleatoria, lo scarto quadratico medio è definito come la radice quadrata della varianza di formula_6
Formalmente lo scarto quadratico medio di una variabile aleatoria può essere calcolato a partire dalla funzione generatrice dei momenti, in particolare è la radice quadrata della differenza tra il momento secondo ed il momento primo elevato al quadrato, cioè
dove formula_26 è il valore atteso di formula_6.
In ambito finanziario, lo scarto quadratico medio viene usato per indicare la variabilità di un'attività finanziaria e dei suoi payoff (rendimenti). Esso fornisce quindi, implicitamente, una misura della volatilità dell'attività, quindi del suo rischio.
In fisica, è un ottimo indice dell'errore casuale della misurazione di una grandezza fisica.
In ambito sportivo è utilizzato per valutare la prestazione di un giocatore di bowling in riferimento ad un certo numero di partite. Il valore trovato non incide sul punteggio ma sintetizza le capacità e i miglioramenti del giocatore.
In ingegneria, è uno dei parametri da considerare per valutare la capacità di un processo produttivo.
Nelle applicazioni informatiche, è a volte conveniente utilizzare la formula
che consente, con sole tre variabili formula_29, di calcolare lo scarto quadratico medio, oltre che la media, di un flusso di numeri di lunghezza formula_3 senza dover ricorrere ad una memorizzazione degli stessi.
