DBSCAN, acronimo di Density-Based Spatial Clustering of Applications with Noise, è un algoritmo di clustering utilizzato nel machine learning per raggruppare insiemi di dati in base alla loro densità nello spazio. L’obiettivo principale di DBSCAN è identificare regioni di alta densità separate da regioni di bassa densità.
L’algoritmo DBSCAN
DBSCAN (Density-Based Spatial Clustering of Applications with Noise) è un algoritmo di clustering inventato da Martin Ester, Hans-Peter Kriegel, Jörg Sander e Xiaowei Xu nel 1996. È stato presentato nel loro articolo intitolato “A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise”.
L’idea principale di DBSCAN è quella di identificare cluster di punti in uno spazio dato, basandosi sulla densità dei punti. A differenza di altri algoritmi di clustering come K-Means, DBSCAN non richiede di specificare a priori il numero di cluster. Invece, determina automaticamente i cluster in base alla densità dei punti nei dat
Ci sono alcuni concetti fondamentali alla base di questo algoritmo:
- punto di densità
- punto centrale
- punto di bordo
- punto di rumore
DBSCAN definisce un punto di densità come un punto con un numero minimo di punti entro una certa distanza. Un punto ( p ) è definito di densità se il numero di punti all’interno di una certa distanza 
da ( p ) supera un valore minimo ( MinPts ). Questo può essere espresso come:
Dove 
è il numero di punti entro la distanza da ( p ) e ( D ) è l’insieme dei dati.
Un punto p è definito punto centrale se il numero di punti entro una certa distanza (eps) è maggiore o uguale a un valore minimo (MinPts). Matematicamente:
Un punto di bordo è un punto che non è centrale ma è raggiungibile da un punto centrale. In altre parole, è un punto che si trova all’interno della vicinanza di un punto centrale ma non soddisfa il requisito di densità.
Un Punto di rumore non è né centrale né di bordo.
L’algoritmo DBSCAN utilizza queste definizioni per identificare i cluster nei dati. Inizia con un punto casuale non visitato e, se questo punto è centrale, tutti i punti nel suo vicinato vengono assegnati allo stesso cluster. L’algoritmo procede in modo iterativo fino a quando tutti i punti sono stati visitati.
Una formula chiave nell’algoritmo è la definizione di “raggiungibilità” tra due punti. Due punti ( p ) e ( q ) sono considerati raggiungibili se esiste una sequenza di punti che collega ( p ) a ( q ) dove ogni punto successivo è un punto centrale. Questo viene espresso come:
Inoltre, la densità di un cluster può essere espressa come la somma dei punti di densità nei punti centrali del cluster:
Queste formule e definizioni forniscono una base solida per la comprensione e l’implementazione dell’algoritmo DBSCAN nel clustering dei dati.
L’algoritmo procede in questo modo:
- Inizia con un punto casuale non visitato.
- Se questo punto è un punto centrale, tutti i punti raggiungibili da esso fanno parte del suo cluster.
- Se il punto non è centrale, viene segnato come rumore.
- Ripete il processo finché tutti i punti sono stati visitati.
Le principali caratteristiche di DBSCAN sono la sua capacità di gestire cluster di forma arbitraria e la sua resistenza al rumore. Tuttavia, richiede la specificazione di due parametri: eps e MinPts, il che può renderlo sensibile alla scelta dei parametri ottimali per determinati insiemi di dati.
In generale, DBSCAN è un’ottima scelta quando si hanno dati con densità variegate e si desidera identificare cluster di forme e dimensioni diverse.
Usare DBSCAN per il clustering con Scikit-learn in Python
Come molti altri algoritmi per il clustering, anche DBSCAN è presente nella libreria scikit-learn di Python. Puoi utilizzare la classe DBSCAN per eseguire il clustering basato sulla densità utilizzando questo algoritmo.
In questo esempio utilizzeremo make_moons di scikit-learn per generare i dati in maniera automatica. Questa funzione è utilizzata per generare un insieme di dati sintetici che ha la forma di due semicerchi, simili a due lune crescenti, all’interno di uno spazio bidimensionale. Questo tipo di dataset è spesso utilizzato per scopi dimostrativi o per testare algoritmi di clustering e classificazione.
Vediamo un codice di esempio per generare i dati da sottoporre a clustering successivamente:
from sklearn.datasets import make_moons
import matplotlib.pyplot as plt
# Generate moon-shaped data
X, _ = make_moons(n_samples=1000, noise=0.1)
# Visualize the generated data
plt.figure(figsize=(8, 6))
plt.scatter(X[:, 0], X[:, 1], marker='o', edgecolor='k')
plt.title('Generated Moon-Shaped Data')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.show()
Eseguendo otteniamo il seguente risultato:
Ecco una spiegazione dei principali parametri utilizzati con make_moons:
n_samples: Il numero di punti dati da generare. In questo esempio, abbiamo specificato 1000 punti.noise: La deviazione standard del rumore gaussiano aggiunto ai dati generati. Maggiore è il valore dinoise, maggiore sarà la dispersione dei punti dati. In questo esempio, abbiamo impostatonoisea 0.1, il che significa che una piccola quantità di rumore è aggiunta ai dati generati per renderli più realistici.
Quindi, la funzione make_moons genera un insieme di dati casuali posizionando due semicerchi in uno spazio bidimensionale, e aggiunge un po’ di rumore gaussiano per rendere i dati un po’ più realistici. Questo è particolarmente utile per testare algoritmi di clustering come DBSCAN in scenari in cui i dati hanno forme non lineari o complesse.
Adesso andiamo ad applicare DBSCAN al dataset appena generato:
dbscan = DBSCAN(eps=0.10, min_samples=5)
labels = dbscan.fit_predict(X)
plt.figure(figsize=(8, 6))
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='viridis', marker='o', edgecolor='k')
plt.title('DBSCAN Clustering')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.colorbar(label='Cluster')
plt.show()Eseguendo otteniamo il seguente risultato:
Come possiamo vedere dal grafico, abbiamo la definizione netta dei due cluster, con due colori differenti. Giallo (cluster 1) e Verde (cluster 0) che sono ben netti e non ci sono punti di colore intermedio che rappresentano delle ambiguità tra l’assegnazione ai due cluster del punto in questione. Inoltre i punti con il colore blu (cluster -1) sono quei colori che vengono considerati esterni e non appartenenti a nessun cluster.
Valutazione dei parametri da passare a DBSCAN
Abbiamo visto un risultato ottimale con la separazione perfetta dei punti in due cluster ben distinti. Per ottenere questi risultati abbiamo utilizzato due specifici valori dei parametri passati a DBSCAN:
dbscan = DBSCAN(eps=0.10, min_samples=5)Ma a priori, quando partiamo da zero, come possiamo conoscere il valore ottimale di questi valori?
Esistono dei metodi che ci permettono di ottenere i valori ottimali di questi parametri:
- il metodo del gomito
- il metodo della silhouette
Partiamo, utilizzando il metodo del gomito per trovare un valore appropriato per eps. Questo metodo coinvolge il tracciamento della curva della distanza media tra i punti e il loro più vicino vicino (k-dist graph), e individuare il punto in cui la curva inizia a piegarsi. Questo punto può essere considerato come un buon valore per eps.
from sklearn.neighbors import NearestNeighbors
import matplotlib.pyplot as plt
# Compute the k-nearest neighbors for each point
k = 10 # Number of neighbors to consider
nbrs = NearestNeighbors(n_neighbors=k).fit(X)
distances, indices = nbrs.kneighbors(X)
# Compute the average distance of the k-th nearest neighbor for each point
avg_distances = distances.mean(axis=1)
# Visualize the plot of k-nearest neighbors distance
plt.plot(sorted(avg_distances))
plt.xlabel('Point')
plt.ylabel(f'Average {k}-Nearest Neighbor Distance')
plt.title(f'{k}-Nearest Neighbor Distance Plot')
plt.show()Eseguendo si ottiene:
Come valore ottimale, valuto il valore corrispondente al “gomito della curva” che arrotondando considero pari a 0.10. Adesso che conosco il valore migliore di eps (0.10) posso applicare il metodo della silhouette per ottenere il valore ottimale di min_sample,
from sklearn.metrics import silhouette_score
import numpy as np
# Optimal value for eps
eps = 0.10
# Range of values for min_samples to explore
min_samples_range = range(2, 10)
# Initialize a list to save silhouette scores
silhouette_scores = []
# Compute silhouette score for each min_samples value
for min_samples in min_samples_range:
dbscan = DBSCAN(eps=eps, min_samples=min_samples)
labels = dbscan.fit_predict(X)
if len(np.unique(labels)) > 1: # Ensure there are at least 2 clusters
silhouette_avg = silhouette_score(X, labels)
silhouette_scores.append(silhouette_avg)
else:
silhouette_scores.append(-1) # Set a negative score if there's only one cluster
# Find the min_samples value with the maximum silhouette score
best_min_samples = min_samples_range[np.argmax(silhouette_scores)]
best_silhouette_score = max(silhouette_scores)
print(f"The best value for min_samples is {best_min_samples} with a silhouette score of {best_silhouette_score}")Eseguendo si ottiene:
The best value for min_samples is 5 with a silhouette score of 0.26399382975954Sono i due parametri che ho inserito all’inizio. I parametri potranno variare di dataset in dataset.
DBSCAN vs K-Means
Per quanto riguarda il clustering, l’algoritmo più comunemente noto ed usato è K-Means. E’ importante quindi conoscere quali siano le differenza tra DBSCAN e K-Means e quando sia più opportuno usare uno o l’altro.
DBSCAN è un algoritmo di clustering basato sulla densità che assegna i punti ai cluster in base alla densità dei dati. Richiede la specifica di due parametri: ( \epsilon ), che rappresenta la distanza massima tra i punti per essere considerati vicini, e ( MinPts ), il numero minimo di punti entro ( \epsilon ) per formare un cluster. Identifica regioni di alta densità separandole da regioni di bassa densità. Non è necessario specificare a priori il numero di cluster. Può identificare cluster di forma arbitraria e non è vincolato a cluster di forma sferica. È resistente al rumore e in grado di identificare punti di rumore come cluster separati. È più efficiente di K-means su set di dati con densità variegate, ma può essere meno efficace su set di dati di grandi dimensioni a causa della complessità computazionale.
K-means è un algoritmo di clustering che assegna i punti a uno dei ( k ) cluster, dove ( k ) è un numero predefinito di cluster specificato dall’utente. Richiede di specificare il numero di cluster ( k ) a priori. Cerca di minimizzare la somma delle distanze quadrate tra i punti e il centroide di ciascun cluster. Produce cluster di forma sferica, poiché minimizza la distanza tra i punti e il centroide. K-means è sensibile ai valori anomali e può essere influenzato da dati rumorosi. È efficace su grandi set di dati, ma può essere computazionalmente costoso.
Quando usare K-means:
- Quando si conosce a priori il numero approssimativo di cluster e si desidera produrre cluster di forma sferica.
- Quando i dati sono relativamente puliti e non contengono molti valori anomali.
Quando usare DBSCAN:
- Quando la forma e la dimensione dei cluster non sono note a priori e si desidera identificare cluster di forma arbitraria.
- Quando i dati contengono rumore o valori anomali e si desidera che tali punti siano considerati come cluster separati o rumore.
- Quando si desidera evitare la specificazione a priori del numero di cluster.
In sintesi, la scelta tra K-means e DBSCAN dipende dalle caratteristiche specifiche dei dati e dagli obiettivi del clustering. È importante esaminare attentamente le proprietà dei dati, la forma prevista dei cluster, la presenza di rumore e la necessità di interpretare facilmente i risultati prima di selezionare l’algoritmo più adatto. In alcuni casi, potrebbe essere utile eseguire entrambi gli algoritmi e confrontare i risultati per determinare quale funziona meglio per il proprio problema.