Il Clustering Spettrale nel Machine Learning con Scikit-learn

Pubblicato il di
Post Views: 114
Spectral Clustering header

Il clustering spettrale è una tecnica di clustering utilizzata nel machine learning per raggruppare insiemi di dati simili. Si basa sull’analisi degli spettri delle matrici di similarità o dissimilarità tra i dati. Questa tecnica è particolarmente efficace quando i dati hanno una struttura non lineare o quando la separazione tra i cluster non è chiaramente definita nello spazio euclideo. Il processo di clustering spettrale coinvolge solitamente tre fasi: la costruzione di una matrice di similarità o dissimilarità, la riduzione dimensionale e l’applicazione di un algoritmo di clustering sui dati trasformati. Questa tecnica è utile in diversi settori, inclusi il riconoscimento di pattern, l’analisi delle immagini e la classificazione dei documenti.

Il Clustering Spettrale

Il clustering spettrale nel campo del machine learning ha una storia affascinante che affonda le radici nella teoria dei grafi e nell’algebra lineare. Inizialmente, concetti fondamentali come la matrice di adiacenza e la Laplaciana di un grafo hanno fornito le basi matematiche per l’approccio spettrale al clustering. Durante gli anni ’80 e ’90, con l’aumento dell’interesse per l’applicazione della teoria dei grafi e dell’algebra lineare nel machine learning, gli studiosi hanno cominciato a esplorare come utilizzare gli autovalori e gli autovettori di matrici associate ai dati per scopi di clustering e riduzione dimensionale.

Il clustering spettrale ha subito uno sviluppo significativo con il tempo, con importanti contributi da parte di ricercatori come Andrew Ng e Michael Jordan. Questo ha portato a una migliore comprensione dei principi alla base del clustering spettrale e alla sua applicazione pratica in una varietà di domini. La sua diffusione sia nell’ambito accademico che in quello industriale è stata notevole, grazie alla sua capacità di gestire dati complessi e ad alta dimensionalità.

L’utilizzo del clustering spettrale si è esteso a una vasta gamma di settori, includendo il riconoscimento di pattern, l’analisi delle immagini, il rilevamento di comunità nelle reti sociali e molto altro ancora. La continua ricerca e sviluppo hanno portato a nuove tecniche, algoritmi e applicazioni, con l’obiettivo di creare modelli più efficienti, scalabili e adattabili a una vasta gamma di problemi di clustering.

Il clustering spettrale è una tecnica che sfrutta la teoria dei grafi e l’analisi degli autovalori per raggruppare dati simili insieme.

  1. Costruzione della matrice di similarità o dissimilarità (W):
    In questa fase, si calcola una matrice che rappresenta la similarità o dissimilarità tra i punti nel dataset. Questa matrice può essere rappresentata come una matrice di adiacenza di un grafo pesato. Ad esempio, se abbiamo un insieme di punti x_1, x_2, …, x_n, possiamo calcolare una matrice di similarità (W) in cui w_{ij} rappresenta la similarità tra i punti x_i e x_j. Le formule per calcolare w_{ij} possono variare a seconda del contesto e della natura dei dati.
  2. Riduzione dimensionale (D):
    Una volta ottenuta la matrice di similarità (W), viene costruita una matrice diagonale (D) contenente le somme delle righe di (W). Questo passaggio serve a calcolare la cosiddetta Laplaciana normalizzata, che sarà utilizzata successivamente. La matrice (D) può essere definita come:
    D_{ii} = \sum_{j=1}^{n} w_{ij}
  3. Calcolo della Laplaciana normalizzata (L):
    La Laplaciana normalizzata (L) è calcolata come la differenza tra la matrice di grado (D) e la matrice di similarità (W). La Laplaciana normalizzata è importante perché contiene informazioni sulla struttura dei dati che sono utili per il clustering. È definita come:
    L = D - W
  4. Calcolo degli autovalori e autovettori (λ, v):
    Successivamente, vengono calcolati gli autovalori e gli autovettori della Laplaciana normalizzata (L). Gli autovalori (\lambda) e gli autovettori (v) soddisfano l’equazione:
    Lv = \lambda v
    Gli autovettori corrispondenti agli autovalori più piccoli rappresentano le dimensioni principali del sottospazio in cui i dati possono essere proiettati.
  5. Clustering usando gli autovettori:
    Infine, i dati vengono raggruppati utilizzando gli autovettori corrispondenti agli autovalori più piccoli come caratteristiche per gli algoritmi di clustering come il K-Means.

Questo è un approccio generale al clustering spettrale. Tuttavia, possono esserci variazioni e estensioni a seconda del contesto specifico e degli obiettivi del problema di clustering.

Il Clustering Spettrale con Scikit-learn

il clustering spettrale può essere implementato con scikit-learn, una popolare libreria di machine learning in Python. Scikit-learn fornisce una classe chiamata SpectralClustering che permette di eseguire il clustering spettrale su un dataset. Questa classe offre diverse opzioni per personalizzare l’algoritmo, inclusi diversi metodi per calcolare l’affinità tra i punti e il numero di cluster desiderato.

from sklearn.datasets import make_moons
from sklearn.cluster import SpectralClustering
import matplotlib.pyplot as plt

X, _ = make_moons(n_samples=1000, noise=0.1, random_state=42)

# 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 si ottiene lo scatterplot dei punti del dataset appena generato:

Spectral Clustering - dataset mezzaluna

Adesso che abbiamo il dataset applichiamoci un algoritmo di clustering spettrale:

spectral_clustering = SpectralClustering(n_clusters=2, affinity='rbf', gamma=20.0, random_state=42)
clusters = spectral_clustering.fit_predict(X)

plt.figure(figsize=(8, 6))
plt.scatter(X[:, 0], X[:, 1], c=clusters, cmap='viridis')
plt.title('Spectral Clustering')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.show()

Eseguendo si ottiene una rappresentazione grafica dei risultati del clustering, colorando i punti in base all’etichetta del cluster assegnata loro.

Spectral Clustering - results 01

Tuttavia con questo metodo di clustering le cose non sono così semplici. Se controlliamo 

spectral_clustering = SpectralClustering(n_clusters=2, affinity='rbf', gamma=20.0, random_state=42)

Abbiamo utilizzato una serie di parametri molto particolari.

In contesto del clustering spettrale, il parametro affinity si riferisce al metodo utilizzato per calcolare la similarità o dissimilarità tra i punti nel dataset. Questo parametro influisce sulla costruzione della matrice di similarità o dissimilarità, che è fondamentale per il clustering spettrale.

Quando parliamo di “affinità”, ci riferiamo essenzialmente a quanto due punti sono simili tra loro. In termini pratici, l’affinità determina quanto i punti sono vicini o simili in uno spazio multidimensionale. Più due punti sono simili, maggiore sarà il valore dell’affinità tra di essi, e viceversa.

Nel contesto del clustering spettrale, ci sono diversi metodi per calcolare l’affinità. Alcuni dei principali metodi sono:

  • Nearest Neighbors: L’affinità tra i punti viene calcolata in base alla distanza euclidea o a una metrica di distanza definita tra i punti più vicini.
  • RBF (Radial Basis Function): L’affinità viene calcolata utilizzando una funzione radiale gaussiana, che misura la distanza tra i punti nello spazio delle caratteristiche.
  • Precomputed: Consente di fornire una matrice di similarità o dissimilarità precalcolata tra i punti.
  • KNN (K-Nearest Neighbors): Utilizza la similarità tra i k-punti più vicini come affinità.

Ognuno di questi metodi di affinità ha i propri vantaggi e può essere più adatto a determinati tipi di dati o strutture di clustering. Scegliere il metodo di affinità appropriato è importante per ottenere risultati accurati e significativi nel clustering spettrale.

Nel caso dei cluster moon-shaped abbiamo usato RBF come affinità.

Il parametro gamma è specifico per i kernel a base radiale (RBF) e altri kernel simili utilizzati in tecniche di machine learning come Support Vector Machine (SVM) e clustering spettrale. In questo contesto, gamma controlla la larghezza della funzione kernel.

Per quanto riguarda il clustering spettrale, quando si utilizza un’affinità basata su RBF, come nel caso di affinity='rbf', il parametro gamma influenza la forma della funzione radiale gaussiana utilizzata per calcolare l’affinità tra i punti del dataset.

In poche parole, un valore più alto di gamma significa che la funzione radiale gaussiana si restringe e ha un raggio più piccolo, rendendo così i punti più vicini tra loro più influenti nell’affinità. Al contrario, un valore più basso di gamma significa che la funzione radiale gaussiana si estende e ha un raggio più grande, considerando quindi un numero maggiore di punti nel calcolo dell’affinità.

Quindi, regolare il parametro gamma è importante per ottenere risultati ottimali nel clustering spettrale e in altri algoritmi che utilizzano kernel RBF. Sperimentando con diversi valori di gamma, è possibile trovare il giusto compromesso per adattare l’algoritmo ai propri dati e ottenere risultati di clustering migliori.

# Define the gamma values to test
gamma_values = [0.1, 1.0, 10.0, 100.0]

# Create subplots for each gamma value
fig, axes = plt.subplots(2, 2, figsize=(12, 10))

for i, gamma in enumerate(gamma_values):
    row = i // 2
    col = i % 2
    
    # Define the Spectral Clustering model with the current gamma
    spectral_clustering = SpectralClustering(n_clusters=2, affinity='rbf', gamma=gamma, random_state=42)
    
    # Perform clustering
    clusters = spectral_clustering.fit_predict(X)
    
    # Visualize clustering results
    axes[row, col].scatter(X[:, 0], X[:, 1], c=clusters, cmap='viridis')
    axes[row, col].set_title(f'Spectral Clustering with gamma={gamma}')
    axes[row, col].set_xlabel('Feature 1')
    axes[row, col].set_ylabel('Feature 2')

plt.tight_layout()
plt.show()

Modificando i valori di gamma per il nostro esempio otteniamo infatti i seguenti risultati:

Spectral Clustering - results with gamma

Come possiamo vedere, cominciamo ad avere risultati accettabili per valori di gamma > 10.

Un ulteriore esempio

Vediamo adesso un altro esempio, utilizzando un dataset completamente differente. 

from sklearn.datasets import make_circles
from sklearn.cluster import SpectralClustering
import matplotlib.pyplot as plt

# Generiamo dei dati di esempio a forma di cerchi concentrici
X, _ = make_circles(n_samples=400, factor=0.5, noise=0.05)

# 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()

I punti questa volta saranno disposti circolarmente, ed i cluster saranno disposti su diametri diversi

Spectral Clustering - results circles

Se applichiamo a questo dataset lo stesso metodo precedente con affinità RBF su un range di diversi gamma:

Spectral Clustering - results circles gamma

Si vede che si ottengono risultati ottimali con gamma uguale a 100.

Ma un risultato simile si può ottenere anche modificando l’affinità, con “Nearest Neighbors“. 

spectral_clustering = SpectralClustering(n_clusters=2, affinity='nearest_neighbors', random_state=42)
Spectral Clustering - Nearest Neighbors

In questo caso abbiamo ottenuto risultati soddisfacenti in entrambe i casi.

Meglio usare RBF con gamma molto alti o Nearest Neighbors?

Nell’esempio precedente abbiamo visto che i migliori risultati si hanno comunque sia con affinità RBF con valori gamma molto alti o con affinità Nearest Neighbors. Non esiste un meglio o un peggio in tutte le evenienze. La scelta può dipendere dal tipo di dati che stai analizzando e dagli obiettivi del clustering.

Affinità RBF con gamma molto alto:

Questo approccio tende a produrre cluster più compatti e densi. Con un valore di gamma elevato, la funzione RBF avrà un raggio molto piccolo, e ciò significa che i punti influenti nell’affinità saranno solo quelli molto vicini. È adatto per dataset dove i cluster sono compatti e ben separati.

Affinità Nearest Neighbors:

Questo approccio utilizza la similarità tra i k-nearest neighbors come affinità, rendendo i punti vicini tra loro influenti nell’affinità. È adatto per dataset con strutture più complesse o non lineari, dove i cluster possono avere forme irregolari o intersezioni. Potrebbe essere più robusto rispetto all’affinità RBF con un gamma molto alto nei casi in cui i cluster hanno dimensioni o densità variegate.

In generale, se i tuoi dati hanno cluster ben definiti e separati, l’utilizzo dell’affinità RBF con un gamma elevato potrebbe essere una scelta ragionevole. Tuttavia, se i tuoi dati sono più complessi e hai bisogno di una maggiore flessibilità nel definire i cluster, potresti preferire l’utilizzo dell’affinità Nearest Neighbors.

Ti consiglio di provare entrambi gli approcci e valutare i risultati in base alle tue esigenze specifiche e alla struttura dei dati che stai trattando.

In generale, quando usare il Clustering Spettrale?

Il clustering spettrale può essere una scelta efficace in diversi scenari, ma ci sono alcune situazioni in cui può eccellere rispetto ad altri metodi di clustering. Ecco alcuni casi in cui il clustering spettrale potrebbe essere preferibile:

  1. Dataset non lineari o complessi: Il clustering spettrale è particolarmente utile quando i dati hanno una struttura non lineare o complessa, in cui altri algoritmi di clustering potrebbero avere difficoltà a separare i cluster in modo efficace. Grazie alla sua capacità di catturare relazioni non lineari tra i punti, il clustering spettrale può essere più adatto in questi casi.
  2. Dataset di grandi dimensioni: Il clustering spettrale può gestire dataset di grandi dimensioni in modo efficiente, poiché il calcolo delle distanze viene effettuato su una rappresentazione dei dati ridotta, ottenuta tramite la decomposizione spettrale. Questo lo rende una scelta vantaggiosa per dataset di grandi dimensioni in cui altri algoritmi di clustering potrebbero essere computazionalmente onerosi.
  3. Dataset con variazioni di densità o dimensioni dei cluster: Il clustering spettrale non fa assunzioni sulla forma o sulla densità dei cluster, il che lo rende adatto per dataset in cui i cluster hanno variazioni di densità o dimensioni. Può gestire efficacemente cluster di forme diverse e dimensioni variegate.
  4. Clustering semi-supervisionato: Il clustering spettrale può essere esteso per supportare il clustering semi-supervisionato, incorporando informazioni di etichetta parziale o supervisionata nel processo di clustering.
  5. Dataset con grafi o dati strutturati: Il clustering spettrale si basa sull’analisi degli spettri delle matrici di similarità o dissimilarità tra i dati, rendendolo adatto per dati strutturati, come grafi, reti o dati con relazioni intrinseche definite.

Tuttavia, è importante notare che il clustering spettrale può essere computazionalmente più costoso rispetto ad altri algoritmi di clustering, soprattutto per dataset di grandi dimensioni. Inoltre, la scelta dell’affinità e dei parametri può influenzare significativamente i risultati del clustering spettrale. Pertanto, è consigliabile valutare attentamente le caratteristiche del dataset e sperimentare con diversi approcci di clustering per trovare la soluzione migliore per il proprio problema.

.

Lascia un commento