Clustering spettrale in Python

Il clustering è un problema di apprendimento automatico ampiamente usato in cui punti dati simili sono raggruppati per formare un insieme di cluster. È ampiamente utilizzato in applicazioni come sistemi di raccomandazione, rilevamento di anomalie e segmentazione dei clienti. Passeremo attraverso una moderna tecnica di clustering noto come Clustering spettrale e la sua implementazione in Python usando il Sklearn biblioteca.

Cosa è clustering?

Il clustering è un problema di apprendimento automatico senza supervisione in cui si devono dividere le osservazioni "M" in cluster "k", con punti nello stesso cluster estremamente simile e punti in diversi cluster sono molto dissimili. Problemi come segmentazione dei clienti, sistemi di raccomandazione, rilevamento di anomalie, ecc., sono risolti dal clustering. Potresti avere familiarità con l'algoritmo di clustering K-Means, in cui non abbiamo etichette e dobbiamo posizionare ogni punto dati nel suo cluster. Il metodo di clustering spettrale viene utilizzato per raggiungere lo stesso obiettivo del metodo di clustering K-Means ma con un approccio basato su grafici. L'immagine seguente mostra i tre cluster separati l'uno dall'altro e hanno punti simili insieme.

Cosa sta clustering k-means?

Il clustering K-means implica l'identificazione dei cluster K del set di dati che sono distinti l'uno dall'altro. Vengono utilizzate solo variabili indipendenti per creare cluster. K significa che il clustering è un algoritmo di apprendimento non supervisionato. I punti dati nello stesso cluster sono abbastanza simili, mentre i punti dati in cluster diversi sono molto distinti. Inizi con k centri casuali e assegni oggetti a quelli più vicini ad essi. Il centro di ciascuna raccolta viene quindi ricalcolato, risultando in nuovi centri K. Continui a farlo fino a quando il numero di iterazioni raggiunge una soglia predeterminata o il centro dei cluster si muove a malapena. Il metodo del gomito è comunemente usato per determinare il valore di k.

Classificazione vs. Clustering

La classificazione è il risultato dell'apprendimento supervisionato, il che significa che si desidera che il sistema generi un'etichetta nota. Ad esempio, se hai costruito un classificatore di immagini, direbbe: "Questo è un cane, questo è un gatto", basato su campioni di cani e gatti, lo hai mostrato.

Il clustering è la conseguenza dell'apprendimento non supervisionato, il che implica che hai visto molti campioni ma non ti sono stati dati etichette per loro. Ad esempio, possiamo usare il clustering per segmentare i clienti dello stesso tipo da clienti di diversi tipi. Questa è un'affermazione del problema ampiamente utilizzata che viene risolta usando il clustering.

Cos'è l'algoritmo di clustering spettrale?

Il clustering spettrale è un moderno algoritmo di clustering basato sulla teoria dei grafici. Ha sovraperformato diversi approcci di clustering classici ed è ancora in evoluzione. Questo algoritmo prende ogni punto dati come nodo grafico e utilizza il partizionamento grafico per risolvere il problema del clustering.

Funzionante di clustering spettrale

Creazione di una struttura dei dati grafici

È possibile visualizzare qualsiasi set di dati come cloud di punti, con M punti in N dimensioni. Puoi fare un grafico da questi punti, con i nodi i punti e i bordi (rappresentati da w) essere ponderati da quanto sono simili i punti. Una volta che abbiamo i nostri dati sotto forma di un grafico, possiamo generare una matrice di adiacenza semplicemente inserendo il peso del bordo tra i nodi "I" e "J" in ogni colonna della matrice. Questo è un M X M matrice simmetrica. W è il nome per la matrice di adiacenza.

Proiettare i dati

In questo passaggio, i dati vengono proiettati in uno spazio a bassa dimensione per avvicinare i punti uno nello spazio dimensionale inferiore. La formula fornisce il grado di ciascun nodo:

La matrice di grado viene quindi calcolata usando la formula:

Il laplaciano del grafico può essere calcolato usando la formula L = d-w. Possiamo calcolare lo spettro di questa matrice, o i suoi autovettori disposti dal più significativo a meno importante, ora che abbiamo il laplaciano del grafico. L'assunzione di autovettori "k" meno significativi ti dà una rappresentazione di ciascun nodo nel grafico nelle dimensioni "k", che rappresenta ogni punto nel set di dati. Gli autovalori più piccoli sono correlati agli autovettori meno significativi. Questo è un tipo di riduzione della dimensionalità che non è lineare.

Raggruppare i dati

Questo passaggio prevede principalmente il clustering dei dati dimensionali ridotti utilizzando il clustering K-Means o qualsiasi altra tecnica di clustering classico. La matrice laplaciana grafica normalizzata viene prima assegnata a ciascun nodo. I dati vengono quindi raggruppati utilizzando qualsiasi metodo standard.

In uno scenario ideale, prevede che i tuoi dati non siano completamente connessi, con componenti connessi distinti per ciascun cluster. Tuttavia, in pratica, questo è raramente il caso: dipende da varie cose, inclusi i dati stessi e da come si progettano il grafico di adiacenza. In termini di efficienza, i cluster migliori sono separati, il clustering più spettrale si comporta in modo prevedibile: il grafico avrà più di un componente collegato (idealmente K, il numero di cluster nel set di dati), i primi autovalori saranno zero ed in esecuzione K-Means nello spazio creato prendendo i primi autovettori K del grafico Laplacian produrrà risultati abbastanza soddisfacenti. Più sono più vicini i cluster, più gli autovalori sono da 0 e più sono più vicini i punti nell'autori.

K-Means vs. Clustering spettrale

Considera i dati indicati di seguito.

Anche quando il vero numero di cluster k è noto all'algoritmo, i k-mee non riescono a raggruppare i dati sopra corretti correttamente. Questo perché K-Means è un buon algoritmo di clustering di dati per trovare gruppi globulari come quelli qui sotto:

dove tutti i membri del cluster sono vicini tra loro (in senso euclideo). Gli approcci di cluster per grafici come il clustering spettrale, d'altra parte, non raggruppano i punti dati direttamente nello spazio dei dati nativi ma invece costruiscono una matrice di somiglianza con (i, j)_th riga che rappresenta una certa distanza di somiglianza tra l'i_th e j_th Punti dati nel set di dati.

In un certo senso, il clustering spettrale è più generale (e potente) rispetto ai k-medie poiché il clustering spettrale è applicabile ogni volta che i k-medie non lo sono (basta usare una semplice distanza euclidea come misura di somiglianza). Tuttavia, il contrario non è vero. Quando si sceglie una di queste strategie sull'altra, ci sono alcune preoccupazioni pratiche da tenere a mente. La matrice dei dati di input è fattorizzata con k-means, mentre la matrice Laplacian è fattorizzata con clustering spettrale (una matrice derivata dalla matrice di somiglianza).

Implementazione del clustering spettrale usando Python

Importazione delle biblioteche

da Sklearn.Cluster Import SpectralClustering
Importa Numpy come NP
Leggere i dati
X = np.Array ([[1, 1], [2, 1], [1, 0],
[4, 7], [3, 5], [3, 6]])

Si noti che in questo esempio abbiamo preso i dati con meno dimensioni. Se si dispone di dati dimensionali maggiori, è possibile applicare l'analisi dei componenti principali (PCA) per ridurre le dimensioni dei dati.

Inizializzare il nostro modello

Model = SpectralClustering (N_Clusters = 2,
ASSACTION_LABELS = 'discretizza',
random_state = 0).Fit (x)

Ottieni etichette di ogni punto dati

Stampa (modello.Etichette_)

Produzione

Array ([1, 1, 1, 0, 0, 0])

Vantaggi del clustering spettrale

• Il clustering spettrale non assume la forma dei dati. Si comporta bene su tutti i tipi di distribuzioni di dati. Altri algoritmi classici come K-Means assumono la forma dei dati come sferici.
• Funziona abbastanza bene quando le relazioni sono approssimativamente transitive (come la somiglianza).
• Non abbiamo bisogno dell'intero set di dati su Cluster; Solo una matrice di somiglianza/distanza, o forse solo la laplaciana, sarà sufficiente.

Svantaggi del clustering spettrale

• Gli autovettori di calcolo sono il collo di bottiglia; Pertanto, è costoso per set di dati davvero grandi.
• Non funziona bene con set di dati rumorosi.
• Il numero di cluster (k) deve essere deciso in anticipo.

Casi d'uso di clustering spettrale

• Segmentazione delle immagini
• Segmentazione del cliente
• Risoluzione dell'entità
• Clustering spettrale sequenze di proteine

Conclusione

Abbiamo visto come possiamo usare il clustering spettrale per cluster i nostri punti dati. Prima proiettiamo i dati in una struttura dei dati grafici, riduciamo le dimensioni dei dati e quindi applichiamo la tecnica di clustering tradizionale sui dati ridotti. In seguito abbiamo visto quanto facilmente questo complesso algoritmo potesse essere implementato in Python usando alcune righe di codice.