Clustering con DBSCAN

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) è un algoritmo di clustering che raggruppa punti vicini tra loro in base a un criterio di densità. Contrariamente ad altri modelli di clustering come K-mean, DBSCAN può identificare cluster di forme arbitrarie e non richiede che il numero di cluster sia specificato in anticipo. È meno sensibile al rumore e può gestire cluster di diversa densità.

Per avere un risultato soddisfacente utilizzando l'algoritmo DBSCAN si assume che i diversi cluster nei dati abbiano una densità relativamente simile, dove per densità si intende il numero di punti che esistono in ogni intorno N(x, ε) definito da un raggio ε e un punto dati x. Questa affermazione può essere verificata otticamente osservando l'esempio DBSCAN al centro dell'immagine sopra, dove i punti attorno all'ammasso blu, che hanno una densità leggermente diversa, sono considerati parte dell'ammasso arancione.

Gli unici parametri necessari per implementare DBSCAN sono:

• MinPts = I punti minimi che un quartiere di un punto dati deve avere affinché il punto dati sia considerato un punto centrale del cluster
• ε = Il raggio dei quartieri (cioè quanto grande vogliamo che siano i nostri "cerchi" attorno al punto dati centrale)

1. Punto centrale: questo tipo di punto dati ha densità ≥ MinPts. Ciò significa che il numero di punti dati in N(x, ε) è maggiore o uguale a MinPts.

2. Punto di confine: questo tipo di punto dati ha densità < MinPts ma distanza (y, cp) ≤ ε dove cp è un punto centrale. Significa che quei punti non hanno la densità richiesta per essere punti centrali, ma non sono nemmeno così lontani da un punto centrale per essere considerati rumore.

Esempio : MinPts = 4, ε = 3 allora y è un punto di confine

3. Punto di rumore: questo tipo di punto dati ha densità < MinPts e distanza (z, cp) ≥ ε. Significa che non ha la densità richiesta per essere un punto centrale ed è lontano da qualsiasi punto centrale.

Esempio : MinPts = 4, ε = 3 allora z è un punto di rumore

E quindi, sulla base di quel processo di categorizzazione dei punti dati, l'algoritmo DBSCAN procede come segue:

1. Scorri su ogni punto dati e classificalo in una di queste tre categorie
2. Elimina tutti i punti di disturbo
3. Considera tutti i punti centrali che si trovano vicini l'uno all'altro come nello stesso cluster (significa che se cp_1 e cp_2 sono punti centrali e distance(cp_1, cp_2) ≤ ε allora cp_1 e cp_2 sono considerati nello stesso cluster.)
4. Assegna ogni punto di confine in un gruppo di punti centrali in base alla loro distanza (i punti di confine che si trovano esattamente nel punto medio tra due gruppi devono essere risolti separatamente, magari lanciando una moneta; D)