Concludiamo l’esplorarazione del mondo del clustering, analizzando il funzionamento di un altro algoritmo molto conosciuto: il Density-Based Spatial Clustering of Applications with Noise o per gli amici DBSCAN.

Negli articoli precedenti abbiamo conosciuto il K-Means per il quale è necessario fornire in anticipo il numero di cluster da generare, successivamente abbiamo analizzato il clustering gerarchico, basato sulla costruzione del dendrogramma che, in pratica, esplora tutte le combinazioni di numero di cluster per poi poter scegliere quello che più ci aggrada a posteriori.

Nel caso del DBSCAN il numero di cluster non è necessario fornirlo in quanto sarà l’algoritmo stesso a scoprire quanti cluster esistono in base a due iperparametri che verranno forniti:

• epsilon o eps (ε): la distanza minima che devono avere due dati in ingresso per essere considerati “vicini“
• minSamples: numero minimo di dati in ingresso, “vicini” tra loro, richiesto per formare un cluster. In generale a questo iper parametro va dato un valore >= numero dimensioni dataset + 1. Ad esempio, se abbiamo un dataset costituito da valori in due dimensioni (punti su un piano), allora minSamples >= 3.

Algoritmo DBSCAN

Il DBSCAN itera sui punti del dataset in ingresso ed esegue delle valutazioni basate sui due iperparametri eps e minSamples. L’algoritmo si può riassumere all’incirca come segue:

per ogni punto p
    n = get_numero_punti_vicini(p, eps)
    se n >= minSamples allora 
        p è core_point 
        crea_cluster(p)
    altrimenti 
        cp = cerca_core_point_vicino(p, eps)
        se esiste(cp) allora
            p è border_point
            p assegnato_a_cluster(cp)
        altrimenti
            p è noise_point

Un core point è un punto che ha attorno a lui (entro la distanza eps) un numero di altri punti almeno pari a minSamples. Un core point definisce un cluster.

Un border point è un punto attorno al quale si trovano un numero di punti minore di minSamples, ma uno di questi è un core point. Per questo motivo questo border point viene assegnato al cluster identificato dal core point a lui vicino.

Un noise point è un punto attorno al quale si trovano un numero di punti minore di minSamples e NESSUNO di questi è un core point. Questo significa che il noise point è a distanza maggiore di eps da qualunque core point. Per questo motivo non viene associato a nessun cluster e resta per conto suo, come outlier, cioè come valore anomalo.

Una delle caratteristiche del DBSCAN è quella di riuscire a gestire cluster anche non sferici, anche se, come tutti gli altri algoritmi di clustering, sfrutta una distanza (che quindi è calcolata su uno spazio circolare, sferico o in generale iper-sferico).
Come funziona? E’ sufficiente considerare il fatto che un core point può essere a sua volta un border point (cioè può essere vicino ad un altro core point identificato in precedenza) e questo porta alla fusione di più cluster in uno solo.

Codice Python

NOTA: il codice di questo esempio lo trovi qui

Creiamo un dataset diverso dal solito, cioè con cluster che non siano sferici. Usiamo un apposito generatore di SciKitLearn e lo impostiamo in modo da generare anche un leggero rumore, in modo da poter vedere anche dei noise point nella nostra clusterizzazione.

# creo un dataset decisamente non "sferico", usando una apposita funzione di SciKitLearn
X, _ = make_moons(n_samples=400, noise=0.1, random_state=1234)
plt.scatter(X[:, 0], X[:, 1], s=300)
plt.show()

Come si vede dall’immagine a fianco, viene creato un dataset distribuito su due mezze lune che si intrecciano.

Questa disposizione di dati non è facilmente clusterizzabile con gli algoritmi già visti (k-means e gerarchico) proprio perchè le due mezze lune non sono insiemi sferici.

Per eseguire un DBSCAN utilizzo l’omonima classe di SciKitLearn e come al solito la addestro con i dati in ingresso e infine ottengo la predizione dei cluster per ogni punto. In questo caso utilizzo un metodo unico che è il fit_predict. Successivamente visualizzo il risultato.

# istanzio la classe di clustering DBSCAN
dbscan = DBSCAN(eps=0.15, min_samples=3)
# eseguo fitting e predizione in una volta sola
y_dbscan = dbscan.fit_predict(X)

Come si vede la clusterizzazione è quasi perfetta (ci sono due punti scuri a sinistra, corrispondenti a due noise point).

Da notare che il risultato della clusterizzazione in questo caso dipende enormemente dai parametri eps e min_samples utilizzati per istanziare la classe DBSCAN. In base a come cambiano questi valori, si ottengono cluster diversi.

Ma come si sarebbero comportati il k-means e il clustering gerarchico? Vediamolo insieme.

# verifico il risultato del k-means
km = KMeans(init="k-means++", n_clusters=2)
y_kmeans = km.fit_predict(X)

Il risultato del k-means non è perfetto. Questo perchè questo algoritmo si basa sulla distanza dai centroidi e quindi i cluster avranno tendenzialmente una forma sferica.

Come si vede dall’immagine, il centroide giallo sarà nel centro dei punti gialli. In questo cluster finiscono tutti i punti ad una certa distanza da quel centroide, compresi parte della mezza luna inferiore. Analogamente per il cluster viola.

# verifico con cluster gerarchico
agglom_clustering = AgglomerativeClustering(n_clusters=2, linkage="ward")
# in un unico passaggio addestro il modello ed elaboto la predizione
y_agglomerative = agglom_clustering.fit_predict(X)

Nel caso del clustering gerarchico la situazione della mezza luna inferiore è migliorata, ma questo va a discapito della mezza luna superiore.

In ogni caso anche questo algoritmo non riesce a gestire correttamente questo dataset perchè tendenzialmente sfrutta cluster sferici.

Il DBSCAN invece riesce a gestire cluster di forma diversa, aggregando man mano dei piccoli cluster (sferici anch’essi…) in modo autonomo.

See you soon!

Sbizzarritevi come al solito sperimentando con iperparametri diversi ed altri dataset.

Noi ci vediamo al prossimo articolo.

Bye!