Spectral Clustering
- Introdotto da
- Ng, A. Y.; Jordan, M. I.; Weiss, Y.
- Anno
- 2002
- Tipo
- Graph-based clustering (spectral method)
Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese
A cosa serve?
Spectral Clustering è un algoritmo di apprendimento non supervisionato basato su grafi, formalizzato da Ng, Jordan e Weiss nel 2002, che mappa i punti dati in uno spazio-eigenspazio a bassa dimensionalità derivato dal Laplaciano del grafo di similarità prima di applicare k-means.
Questo embedding spettrale rende possibile recuperare cluster di forma arbitraria — anelli, mezzelune, spirali intrecciate — che i metodi basati sulla distanza euclidea non riescono costantemente a separare.
L’intuizione alla base del metodo
Il k-means standard partiziona lo spazio per distanza in linea retta, quindi può trovare solo blob convessi, approssimativamente sferici. Spectral Clustering aggira questo problema pensando prima ai dati come a una rete: ogni punto è un nodo e gli archi tra i nodi portano un peso che riflette quanto sono simili i due punti. I cluster corrispondono a regioni della rete che sono densamente connesse internamente ma debolmente connesse al resto. La matrice Laplaciana del grafo codifica questa struttura di connettività e i suoi autovettori più piccoli agiscono come un sistema di coordinate liscio che allunga i dati in modo che i cluster ben separati finiscano lontani anche quando erano aggrovigliati nello spazio originale. Un semplice passaggio k-means in quel nuovo sistema di coordinate li separa quindi nettamente.
Storia
Le fondamenta teoriche dello spectral clustering risalgono al lavoro di Fiedler del 1973 sulla connettività dei grafi e sull'autovalore di connettività algebrica. Shi e Malik (2000) hanno portato l'approccio nella computer vision attraverso il loro criterio normalized-cuts per la segmentazione delle immagini. Ng, Jordan e Weiss (2002) hanno presentato un algoritmo pulito e di uso generale a NIPS — quello ora più comunemente citato — insieme a un'analisi perturbativa che spiega quando e perché il metodo funziona. Il tutorial di Von Luxburg del 2007 in Statistics and Computing ha unificato le formulazioni concorrenti, chiarito il ruolo della normalizzazione Laplaciana ed è diventato il riferimento standard per i professionisti. Lo spectral clustering occupa ora un posto centrale nel curriculum di machine learning e rimane un argomento di ricerca attivo, con lavori in corso su approssimazioni scalabili, kernel robusti ed estensioni a grafi e manifold.
Quando usarlo
Spectral Clustering è ben adatto quando i cluster nei dati sono non convessi, non linearmente separabili o connessi da ponti sottili che i metodi di partizionamento euclideo non possono rilevare — esempi comuni includono cluster a forma di anello, spirali intrecciate e segmenti di immagine. È appropriato quando la similarità a coppie tra i punti può essere calcolata in modo significativo (sia da un kernel su caratteristiche grezze sia da una matrice di affinità pre-fornita), e quando il numero di cluster k è noto o può essere stimato dall'euristica dell'eigengap. Il metodo non richiede assunzioni distribuzionali sulle forme dei cluster. Limitazioni pratiche includono memoria quadratica nel numero di punti (per la matrice di affinità completa) e tempo cubico per l'autodecomposizione, rendendo la formulazione standard costosa oltre circa 10.000 punti. Metodi approssimati (Nystrom, grafi sparsi, SVD randomizzato) estendono la sua portata a dataset più grandi.
Limiti e considerazioni
- La costruzione della matrice di affinità completa n x n richiede O(n^2) di memoria e O(n^3) di tempo per l'autodecomposizione, rendendo l'algoritmo ingenuo infattibile per dataset di grandi dimensioni.
- I risultati sono sensibili alla scelta della larghezza di banda del kernel sigma e alla strategia di costruzione del grafo; scelte errate possono unire o frammentare i cluster.
- L'inizializzazione k-means nell'embedding spettrale introduce casualità; esecuzioni diverse possono produrre partizioni diverse.
- Non scala bene a spazi di caratteristiche ad altissima dimensionalità senza un'attenta selezione del kernel.
- Fornisce solo etichette di cluster; non offre un modello generativo né un'estensione out-of-sample naturale per nuovi punti.
Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.
Punti di forza
- Rileva cluster di forma arbitraria, comprese configurazioni non convesse e non linearmente separabili che sconfiggono k-means e modelli di miscela Gaussiana.
- Può operare su qualsiasi matrice di similarità a coppie, non solo distanze euclidee, rendendolo applicabile a grafi, stringhe e altri dati strutturati.
- L'euristica dell'eigengap fornisce una guida basata sui dati e basata su principi per la scelta del numero di cluster k.
- Radicato in una ricca teoria spettrale dei grafi, che consente un'analisi formale della convergenza e della qualità dei cluster.
- Concettualmente semplice e facilmente implementabile utilizzando librerie standard di algebra lineare.
Applicazioni
- Segmentazione di immagini: partizionamento di pixel o superpixel in regioni percettivamente coerenti utilizzando la similarità delle caratteristiche a livello di pixel.
- Rilevamento di comunità in reti sociali e biologiche dove la connettività a coppie piuttosto che i vettori di caratteristiche definisce la struttura.
- Bioinformatica: raggruppamento di geni o proteine per similarità del profilo di espressione, dove i cluster di espressione sono raramente convessi nello spazio dei geni.
- Elaborazione del linguaggio naturale: clustering di documenti o frasi utilizzando kernel di similarità semantica.
- Computer vision: segmentazione del movimento e partizionamento di nuvole di punti dove i confini dei cluster sono irregolari.
- Analisi esplorativa dei dati: rivelazione di strutture di cluster non ovvie prima di applicare metodi di conferma.
Come funziona
Come funziona
Viene costruita una matrice di similarità (affinità) a coppie W dai dati. La scelta più comune è il kernel Gaussiano (RBF), che assegna un peso elevato alle coppie vicine e un peso vicino a zero a quelle distanti. Il parametro di larghezza di banda sigma controlla la rapidità con cui la similarità decade con la distanza; sceglierlo bene è fondamentale. In alternativa, si può usare un grafo k-vicini più prossimi per rappresentazioni più sparse su grandi dataset.
Formula
W_{ij} = \exp\!\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right)La matrice dei gradi D è la matrice diagonale il cui i-esimo elemento è la somma della i-esima riga di W. Da W e D si forma il Laplaciano del grafo normalizzato (simmetrico) L_sym. Questa matrice cattura la struttura completa di connettività del grafo di similarità; il suo spettro di autovalori rivela quanti cluster naturali contiene il dato e quanto sono nettamente separati.
Formula
L_{\mathrm{sym}} = D^{-1/2}(D - W)D^{-1/2} = I - D^{-1/2}W D^{-1/2}Vengono calcolati i k autovettori corrispondenti ai k autovalori più piccoli di L_sym. Questi autovettori formano le colonne della matrice di embedding U, che ha una riga per punto dati. In questo spazio spettrale k-dimensionale, i punti che appartengono allo stesso cluster vengono avvicinati anche se erano intercalati nello spazio delle caratteristiche originale.
Formula
L_{\mathrm{sym}}\, u = \lambda u \quad \Rightarrow \quad U = [u_1,\, u_2,\, \ldots,\, u_k]Ogni riga di U viene divisa per la sua norma euclidea per proiettare i punti incorporati sull'ipersfera unitaria. Questa normalizzazione, introdotta da Ng, Jordan e Weiss, rimuove differenze di scala spurie tra autovettori e assicura che il successivo passaggio k-means si concentri sulla geometria angolare dell'embedding piuttosto che sulla magnitudine.
Formula
T_{ij} = U_{ij} \Big/ \left(\sum_{j'} U_{ij'}^2\right)^{1/2}Il clustering k-means standard viene applicato alle righe della matrice di embedding normalizzata T. Poiché l'embedding spettrale ha già districato la geometria dei cluster, k-means trova partizioni significative anche per forme di cluster non convesse. Le etichette dei cluster vengono quindi mappate ai punti dati originali.
Errori comuni
- Scelta di sigma senza validazione incrociata basata su principi o auto-tuning; una larghezza di banda troppo piccola crea un grafo disconnesso, mentre una troppo grande unisce cluster distinti.
- Trascurare la normalizzazione delle righe della matrice di affinità prima di k-means (il passaggio di normalizzazione delle righe di Ng et al. è essenziale per la stabilità).
- Ignorare l'eigengap: usare un k fisso senza ispezionare lo spettro degli autovalori porta spesso a una sotto- o sovra-segmentazione.
- Applicare l'algoritmo completo a dataset con decine di migliaia di punti senza passare a una variante approssimata o sparsa.
- Confondere Laplaciani non normalizzati (L = D - W) e normalizzati (L_sym, L_rw), che possono cambiare sostanzialmente le assegnazioni dei cluster.
Domande frequenti
Come scelgo il numero di cluster k?
L'euristica dell'eigengap è la guida standard: calcolare gli autovalori del Laplaciano normalizzato in ordine crescente e cercare il più grande intervallo tra autovalori consecutivi. L'indice in cui si verifica questo intervallo suggerisce il numero naturale di cluster. Quando l'eigengap è ambiguo, approcci basati sulla stabilità — eseguire l'algoritmo per diversi valori di k e confrontare le assegnazioni dei cluster tra le perturbazioni — possono aiutare.
Come devo impostare la larghezza di banda del kernel Gaussiano sigma?
Un'euristica comune è la mediana delle distanze a coppie nel dataset, o uno schema di auto-tuning dei vicini più prossimi (Zelnik-Manor & Perona, 2004) che assegna una larghezza di banda locale a ciascun punto. In pratica, sigma dovrebbe essere validato ispezionando la connettività del grafo di affinità risultante: ogni punto dovrebbe avere almeno alcuni vicini ad alto peso e il grafo non dovrebbe frammentarsi in componenti isolate.
Perché è necessario il passaggio di normalizzazione delle righe?
Gli autovettori del Laplaciano possono differire sostanzialmente in scala. Senza normalizzare ogni riga della matrice di embedding a lunghezza unitaria, il passaggio k-means può essere dominato da autovettori con grandi magnitudini e ignorare componenti informative ma di minore magnitudine. La normalizzazione delle righe introdotta da Ng, Jordan e Weiss mappa tutti i punti sulla sfera unitaria in modo che k-means risponda alla geometria angolare dell'embedding.
Lo spectral clustering può gestire dataset molto grandi?
Non nella sua forma ingenua, che richiede O(n^2) di memoria e O(n^3) di tempo per l'autodecomposizione. Per n grande, i rimedi standard includono: costruire un grafo k-vicini più prossimi sparso invece di una matrice di affinità completa; usare l'approssimazione Nystrom per stimare gli autovettori da un sottocampionamento; o applicare SVD randomizzato. Questi metodi approssimati recuperano la maggior parte dell'accuratezza a una frazione del costo.
Metodi correlati
Fonti
Ng, A. Y., Jordan, M. I., & Weiss, Y. (2002). On Spectral Clustering: Analysis and an Algorithm. Advances in Neural Information Processing Systems, 14, 849–856.
Apri il riferimento della pubblicazioneCopiato.von Luxburg, U. (2007). A Tutorial on Spectral Clustering. Statistics and Computing, 17, 395–416.
Apri il riferimento DOICopiato.Shi, J., & Malik, J. (2000). Normalized Cuts and Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8), 888–905.
Apri il riferimento DOICopiato.