Clustering con DBSCAN nel Machine Learning con Python

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:

1. Inizia con un punto casuale non visitato.
2. Se questo punto è un punto centrale, tutti i punti raggiungibili da esso fanno parte del suo cluster.
3. Se il punto non è centrale, viene segnato come rumore.
4. 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 di noise, maggiore sarà la dispersione dei punti dati. In questo esempio, abbiamo impostato noise a 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.26399382975954

Sono 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.