Come saprai, il clustering è un concetto relativo al mondo del data mining e del machine learning non supervisionato (quindi il dataset non contiene dati etichettati).
Il suo obiettivo è quello di formare gruppi (cluster appunto) di oggetti in modo tale che gli oggetti nello stesso gruppo siano più simili (in base ad una metrica di similarità stabilita) tra loro rispetto a quelli in altri gruppi.
Esistono vari tipi di algoritmi per fare ciò, come il clusteting gerarchico, partizionale e basato su densità. In questo articolo, tratterò l’ultima tipologia facendo riferimento all’algoritmo DBSCAN.
Cos’è DBSCAN
Innanzitutto, devi sapere che il clustering basato su densità identifica le regioni dello spazio che hanno una densità di punti superiore a una certa soglia definita.
DBSCAN (Density-Based Spatial Clustering of Applications with Noise) è uno degli algoritmi di clustering basato sulla densità più conosciuti e utilizzati.
Per densità di un certo punto x del dataset si intende il numero di punti che si trovano all’interno dell’ipersfera (sfera con più di 3 dimensioni) di raggio EPS e centro x. Affinché un cluster si formi è necessario che la quantità di punti a distanza massima EPS da x sia superiore ad un numero minimo di punti (MinPts).
- EPS: raggio del cluster;
- MinPts: numero minimo di punti nel cluster.
Per il successo dell’algoritmo DBSCAN è cruciale la scelta di questi due parametri. In quanto determinano la scala di densità a cui i cluster vengono identificati e possono influenzare significativamente i risultati del clustering. Come scegliere il valore corretto? Sperimentando e valutando i risultati del clustering con diverse impostazioni di questi parametri.
Ovviamente, DBSCAN per funzionare ha bisogno della definizione di una metrica di distanza, come potrebbe essere quella euclidea (la radice quadrata della somma dei quadrati della differenza di ogni caratteristica del dato in analisi).
Distanza euclidea tra due punti.
Si possono utilizzare anche altre tipologie di distanze, ma fai attenzione perchè sono tutte sensibili alle scale di dati. Proprio per questo motivo è importante che i dati da analizzare siano di tipo numerico e che si trovino sulla stessa scala, in quanto nel caso della distanza euclidea la differenza degli attributi con valori più grandi possono dominare il calcolo della distanza rendendo la differenza degli attributi con valori più piccoli irrilevanti. La soluzione prevede di procedere con normalizzazione e standardizzazione.
Quali sono i passi di DBSCAN?
Devi sapere che DBSCAN classifica i punti in tre categorie:
- Punto core: un punto è considerato core se ha almeno MinPts punti entro il suo vicinato EPS, inclusivo del punto stesso. In ogni cluster ci possono essere più punti core.
- Punti di confine: un punto è considerato di confine se non soddisfa i criteri per essere un punto core, ma cade all’interno del vicinato EPS di un punto core.
- Outlier: un punto è considerato outlier se non rientra nelle precedenti due definizioni.
Per ogni punto x del dataset vengono calcolati tutti i suoi vicini con raggio EPS:
- Se la quantità di vicini è almeno quanto MinPts allora x è un punto core perchè indica una regione densamente popolata, quindi si assiste alla creazione di un cluster c con centro x. A questo punto, per ogni x’ vicino di x si procede nel seguente modo:
- se x’ ha i requisiti per essere considerato punto core diventa tale (punto core sempre nel cluster c) e su di esso viene applicato lo stesso processo applicato a x;
- altrimenti x’ viene etichettato come punto di confine rimanendo in c.
- Altrimenti x, viene etichettato inizialmente come outlier e rimane tale se non rientra nel vicinato di qualche altro punto core.
Dall’algoritmo appena riportato è possibile notare che fissato un raggio iniziale del vicinato, questo poi non corrisponde a quello finale del cluster. Infatti, da un punto core è possibile risalire ad altri punti core, così facendo il raggio si allarga.
Quindi, è possibile introdurre alcuni nuovi concetti:
- Punto direttamente density-reachable: un punto p è direttamente density-reachable da un punto q se:
- q è un core point;
- p è nell’ipersfera di raggio EPS centrata in q.
- Punto density-reachable: un punto p è density-reachable da un punto q se:
- esiste una catena di punti p1, p2, …, pn tale che p1 = q e pn = p;
- p(i+1) è direttamente density-reachable da pi.
- Punto density-connected: un punto p è density connected ad un punto q se esiste un punto x tale che sia p sia q sono density-reachable da x (quindi sia p che q rientrano nel raggio del core x).
Potrebbe esserci la possibilità che un punto ricada in più cluster? No perché i punti vengono visitati una volta sola e subito etichettati, quindi un punto che è stato etichettato come facente parte di una certa classe non verrà rianalizzato e ri-etichettato.
Se consideriamo n oggetti, la complessità temporale di DBSCAN è O(n2), in quanto nel caso peggiore per ogni oggetto andiamo a considerare n oggetti vicini. Quella spaziale, invece, è O(n).
Come implementare DBSCAN in Python
Puoi implementare l’algoritmo in Python manualmente oppure tramite la classe DBSCAN della libreria libreria scikit-learn.
from sklearn.cluster import DBSCAN
from sklearn.datasets import make_blobs
import numpy as np
import matplotlib.pyplot as plt
# Generazione di dati di esempio
X, _ = make_blobs(n_samples=300, centers=4, cluster_std=0.60, random_state=0)
# Applicazione di DBSCAN
dbscan = DBSCAN(eps=0.3, min_samples=10)
clusters = dbscan.fit_predict(X)
# Visualizzazione dei risultati
plt.scatter(X[:, 0], X[:, 1], c=clusters, cmap='viridis')
plt.title("DBSCAN Clustering")
plt.xlabel("Feature 1")
plt.ylabel("Feature 2")
plt.show()
Nell’esempio riportato dopo l’importazione delle varie classi è stato applicato il DBSCAN su un dataset giocattolo generato a scopo di esempio. Dal codice puoi notare che sono stati impostati due parametri:
- eps=0.3, indica il raggio da ogni punto core. Ovviamente un valore alto di questo parametro porta alla formazione di meno cluster ma più densi, viceversa si hanno più cluster meno densi;
- min_samples=10, indica il numero minimo di osservazioni che un cluster deve contenere. Questo vuol dire che se gli oggetti vicini sono meno di min_samples sono da considerare outlier, di conseguenza un valore alto di questo parametro comporta la presenza di più outlier rispetto ad un valore più basso.
Cerchi dei consigli per stabilire il valore dei parametri? Un esempio è utilizzare il grafico k-distance. Questo fornisce un grafico delle distanze ordinate tra ogni coppia di punti, in questo ad un certo punto sarà visibile un “gomito” il quale suggerisce un buon valore di soglia per EPS.
clusters = dbscan.fit_predict(X)
Inoltre, puoi personalizzare la metrica di distanza che più si adatta al tuo progetto modificando direttamente il parametro metric.
DBSCAN(eps=0.3, min_samples=10, metric='manhattan')
Perchè utilizzare DBSCAN
DBSCAN è un algoritmo utilizzato soprattutto per rilevare gli outlier in un dataset (eventualmente da gestire con un imputer), poichè isola gli outlier piuttosto che cercare di forzarli in cluster poco appropriati.
Inoltre, non richiede di specificare il numero di cluster a priori, differenziandosi da algoritmi come k-means. Questo lo rende particolarmente adatto per applicazioni dove il numero di cluster non è noto in anticipo.
È in grado di rilevare cluster che hanno forme e dimensioni diverse, ma non funziona bene quando varia la densità e il numero di attributi delle osservazioni è elevato (alta dimensionalità).
Può essere utilizzato con efficacia in una vasta gamma di applicazioni, dalla segmentazione di immagini all’analisi dei dati spaziali.
Quanto ci vuole per eseguire DBSCAN?
Il tempo di esecuzione dell’algoritmo dipende tanto da diversi fattori, ovvero le dimensioni del dataset (numero totale di osservazioni del dataset), la dimensionalità dei dati (numero di attributi di ogni osservazione).
Ma dipende anche dal valore impostato ai vari parametri (EPS e MinPts). Più i parametri sono restrittivi e più ci mette DBSCAN ad essere eseguito.
Nel caso in cui il dataset sia troppo grande, ha senso campionare prima il dataset per ridurre i tempi di calcolo. Considera, ovviamente, che applicando il campionamento (di qualsiasi tipo esso sia) potresti perdere delle caratteristiche importanti del tuo dataset.