L’Affinity Propagation è un algoritmo di clustering nel machine learning utilizzato per identificare cluster all’interno di un insieme di dati. Si basa sul concetto di “similitudine” tra le istanze dei dati anziché sulla distanza euclidea. L’algoritmo cerca di trovare un insieme di esemplari che rappresentino meglio l’insieme dei dati, utilizzando una matrice di similarità per calcolare le “responsabilità” e le “disponibilità” tra le istanze. Questo metodo è utile in situazioni in cui i cluster hanno una struttura a grafo e può essere efficace anche con grandi quantità di dati.
L’Affinity Propagation (AP)
L’Affinity Propagation (AP) è un algoritmo di clustering che utilizza il concetto di similarità tra le istanze dei dati per identificare gli “esemplari” o i “centroidi” del cluster. Fu proposto per la prima volta da Brendan J. Frey e Delbert Dueck nel 2007, nel loro articolo intitolato “Clustering by Passing Messages Between Data Points“. Questo articolo è stato pubblicato nella rivista Science, una delle più prestigiose riviste scientifiche al mondo.
La motivazione principale di Frey e Dueck era quella di sviluppare un algoritmo di clustering che potesse gestire in modo efficiente dataset di grandi dimensioni senza la necessità di specificare a priori il numero di cluster. L’Affinity Propagation si basa sul concetto di “passaggio di messaggi” tra le istanze dei dati per identificare automaticamente i cluster e i loro centroidi.
Una delle caratteristiche chiave dell’Affinity Propagation è la sua capacità di identificare sia i cluster che i centroidi simultaneamente, senza richiedere algoritmi iterativi separati per la ricerca di centroidi come in alcuni altri algoritmi di clustering. L’Affinity Propagation ha guadagnato popolarità nel campo del machine learning e della data science grazie alla sua flessibilità e alle sue prestazioni su una vasta gamma di problemi di clustering. Tuttavia, a causa della sua complessità computazionale, può essere meno adatto a dataset molto grandi o con un numero molto elevato di dimensioni.
Vediamo più in dettaglio alcune sue caratteristiche:
Similarità: L’algoritmo si basa su una matrice di similarità ( S ), in cui ( S_{ij} ) rappresenta la similarità tra le istanze ( i ) e ( j ) dei dati. Questa similarità può essere calcolata utilizzando varie metriche, come la similarità coseno, la similarità di Jaccard o altre metriche di similarità specifiche per il problema.
Responsabilità ( r ): La responsabilità ( r(i, k) ) rappresenta quanto l’istanza ( i ) dovrebbe scegliere l’istanza ( k ) come suo esemplare. Viene calcolata utilizzando l’equazione:
dove ( a(i, k) ) rappresenta l’accumulo di responsabilità che l’istanza ( i ) assegna all’istanza ( k ).
Disponibilità ( a ): La disponibilità ( a(i, k) ) rappresenta quanto l’istanza ( k ) è disposta ad accettare l’istanza ( i ) come suo esemplare. Viene calcolata utilizzando l’equazione:
dove ( r(k, k) ) rappresenta l’accumulo di responsabilità che l’istanza ( k ) assegna a se stessa.
Iterazioni: L’algoritmo itera alternativamente tra il calcolo delle responsabilità e delle disponibilità fino a convergenza.
Assegnazione dei cluster: Dopo la convergenza, gli esemplari dei cluster sono identificati dagli indici delle righe con valori non nulli sulla diagonale della matrice ( r + a ).
Questo è solo un’introduzione all’Affinity Propagation con le formule matematiche di base. La comprensione approfondita richiede un’esplorazione più dettagliata delle equazioni e delle loro implicazioni nel contesto del clustering.
Affinity Propagation con Scikit-Learn
L’implementazione di Affinity Propagation è fornita in Scikit-learn come parte del modulo sklearn.cluster. Puoi utilizzare la classe AffinityPropagation per eseguire il clustering dei dati utilizzando questo algoritmo.
Quindi per prima cosa prepariamoci un dataset rappresentativo su cui applicare tale metodo. Possiamo utilizzare make_blobs, una funzione di scikit-learn che ci permette di generare dei punti casuali distribuiti intorno a dei centroidi, cioè ci permette di generare un dataset con dei cluster già all’interno.
from sklearn.cluster import AffinityPropagation
from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt
# Generate a sample dataset
X, _ = make_blobs(n_samples=300, centers=4, cluster_std=0.60, random_state=0)
# Visualize the generated data
plt.scatter(X[:, 0], X[:, 1], s=50)
plt.title('Generated Data')
plt.xlabel("Feature 1")
plt.ylabel("Feature 2")
plt.show()Questo genererà un set di dati di esempio con 4 cluster, ognuno con una distribuzione normale e una deviazione standard di 0.6, e lo visualizzerà utilizzando un grafico a dispersione. La colorazione dei punti corrisponderà ai cluster generati.
Eseguendo si ottiene il seguente dataset:
Adesso che abbiamo un dataset adatto vediamo come applicare Affinity Propagation su di esso.
af = AffinityPropagation(preference=-50, random_state=0)
af.fit(X)
# Label the data with assigned clusters
cluster_centers_indices = af.cluster_centers_indices_
labels = af.labels_
# Number of clusters found
n_clusters_ = len(cluster_centers_indices)
print(f"Number of clusters found: {n_clusters_}")
# Plot the results
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='viridis')
plt.title('Affinity Propagation Clustering')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.show()Nel codice, viene creato un oggetto AffinityPropagation con il parametro preference impostato su -50 e il seed random random_state impostato su 0. L’algoritmo Affinity Propagation viene quindi addestrato sui dati X tramite il metodo fit(X).
Dopo aver addestrato il modello, le istanze di dati vengono etichettate con i cluster assegnati. Gli indici dei centroidi dei cluster identificati vengono estratti tramite af.cluster_centers_indices_. Le etichette dei cluster assegnate a ciascuna istanza di dati vengono ottenute tramite af.labels_.
Il valore di preference impostato a -50 influenza la selezione dei centroidi iniziali, influenzando indirettamente il numero di cluster identificati. Poiché il parametro preference è negativo, viene favorita una selezione più restrittiva dei centroidi iniziali, il che potrebbe portare a un numero più basso di cluster rispetto alla configurazione predefinita.
Il numero di cluster trovati viene stampato a schermo per fornire un’indicazione del risultato del clustering. La visualizzazione dello scatter plot fornisce un’ulteriore comprensione della distribuzione dei dati e dei cluster identificati.
Eseguendo si ottiene questo risultato:
Valutazione dei risultati ottenuti dalla Affinity Propagation
Per valutare la validità del clustering ottenuto con l’algoritmo Affinity Propagation, possiamo utilizzare il coefficiente di silhouette. Il coefficiente di silhouette misura quanto ogni punto di dati è simile al suo cluster assegnato rispetto agli altri cluster. Un valore alto del coefficiente di silhouette indica che i punti sono ben raggruppati, mentre un valore basso indica che i punti potrebbero essere stati erroneamente assegnati a un cluster.
Ecco come calcolare il coefficiente di silhouette nel tuo esempio:
from sklearn.metrics import silhouette_score
# Calculate the silhouette score
silhouette_avg = silhouette_score(X, labels)
print(f"Average silhouette score: {silhouette_avg}")Il coefficiente di silhouette medio è un valore compreso tra -1 e 1, dove:
- Un valore vicino a 1 indica che i campioni sono stati assegnati in modo corretto ai loro cluster e che i cluster sono ben separati.
- Un valore vicino a 0 indica che i cluster possono sovrapporsi.
- Un valore negativo indica che i campioni potrebbero essere stati assegnati ai cluster sbagliati.
Eseguendo otteniamo il seguente risultato:
Average silhouette score: 0.6819938690643478Nel nostro caso, il coefficiente di silhouette medio è 0.6819938690643478, che è un valore abbastanza buono. Indica che i campioni sono stati raggruppati in modo abbastanza appropriato nei loro cluster, con una certa separazione tra i cluster. Questo suggerisce che il clustering ottenuto con Affinity Propagation nel tuo esempio potrebbe essere considerato abbastanza valido. Tuttavia, è sempre consigliabile esaminare anche altre metriche e visualizzazioni per una valutazione più completa della qualità del clustering.
Quando usare l’Affinity Propagation per il clustering?
L’Affinity Propagation è un algoritmo di clustering con caratteristiche uniche che lo rendono adatto per determinati tipi di dati e contesti. Ecco alcune situazioni in cui potresti considerare l’utilizzo dell’Affinity Propagation rispetto ad altri metodi di clustering nel machine learning:
- Numero sconosciuto di cluster: Affinity Propagation è utile quando il numero di cluster non è noto a priori e desideri che il modello determini automaticamente il numero ottimale di cluster. Al contrario di algoritmi come K-Means, non è necessario specificare il numero di cluster a priori.
- Gruppi di dimensioni diverse: Affinity Propagation può gestire gruppi di dimensioni e densità diverse. Poiché non richiede la presunzione di cluster con forma sferica o uguale dimensione, può essere efficace anche su dataset in cui i cluster hanno varie forme e dimensioni.
- Dati con similarità non lineare o non metrica: L’Affinity Propagation non richiede che i dati siano distribuiti in uno spazio euclideo e può essere applicato a dati con similarità non lineare o non metrica. Ciò lo rende adatto a una vasta gamma di problemi e tipi di dati.
- Interpretazione dei centroidi: Affinity Propagation identifica non solo i cluster, ma anche gli “esemplari” o i “centroidi” all’interno di ciascun cluster. Questo può essere utile se desideri interpretare i punti di riferimento all’interno dei cluster.
- Dati di grandi dimensioni: Affinity Propagation può gestire efficacemente grandi quantità di dati, grazie alla sua complessità computazionale ragionevole.
Tuttavia, è importante notare che Affinity Propagation potrebbe non essere la scelta migliore per tutti i tipi di dati o problemi di clustering. Può essere sensibile ai suoi parametri e potrebbe richiedere del tuning per ottenere risultati ottimali. Inoltre, può essere computazionalmente costoso su dataset molto grandi. Pertanto, è sempre consigliabile esplorare e confrontare diversi algoritmi di clustering per trovare quello più adatto alle tue esigenze specifiche.