clustering spettrale

Question

Prima di tutto devo dire che sono nuovo di matlab (e di questo sito ...), quindi scusate la mia ignoranza.

Sto provando a scrivere una funzione in MATLAB che utilizzerà il clustering spettrale per dividere un insieme di punti in due cluster.

il mio codice è il seguente

function Groups = TrySpectralClustering(data) 
dist_mat = squareform(pdist(data)); 

W= zeros(length(data),length(data)); 

for i=1:length(data), 
    for j=(i+1):length(data), 
    W(i,j)=10^(-dist_mat(i,j)); 
    W(j,i)=W(i,j); 
    end 
end 
D = zeros(length(data),length(data)); 
for i=1:length(W), 
D(i,i)=sum(W(i,:)); 
end 
L=D-W; 
L=D^(-0.5)*L*D^(-0.5); 
[ V E ] = eig(L); 
disp ('V:'); 
disp (V); 

Se ho capito bene, poi utilizzando la seconda più piccola autovettore dovrei essere in grado di eseguire una partizione dei dati in due gruppi - Se il membro-esimo del 2 ° l'autovettore è positivo, il punto di dati esimo sarebbe in un cluster, altrimenti sarebbe nell'altro cluster.

Tuttavia, quando provo il seguente

f=[1,1;0,0;1,0;0,1;100,100;100,101;101,101;101,100] 
TrySpectralClustering(f) 

mi sarei aspettato che i primi quattro punti formerebbero un cluster, e gli ultimi quattro sarebbe formare un altro.

Tuttavia, ricevo

V: 
    -0.0000 -0.5000 0.0000 -0.5777 0.0000 0.4078 -0.0000 0.5000 
    -0.0000 -0.5000 0.0000 0.5777 0.0000 -0.4078 -0.0000 0.5000 
    -0.0000 -0.5000 0.0000 0.4078 0.0000 0.5777 -0.0000 -0.5000 
    -0.0000 -0.5000 0.0000 -0.4078 0.0000 -0.5777 -0.0000 -0.5000 
    -0.5000 -0.0000 -0.0000 -0.0000 -0.7071 -0.0000 0.5000 -0.0000 
    -0.5000 -0.0000 0.7071 0.0000 -0.0000 -0.0000 -0.5000 -0.0000 
    -0.5000 0.0000 -0.0000 0.0000 0.7071 0.0000 0.5000 0.0000 
    -0.5000   0 -0.7071   0   0   0 -0.5000   0 

Prendendo il secondo autovettore

-0.0000 -0.5000 0.0000 0.5777 0.0000 -0.4078 -0.0000 0.5000 

trovo quello cluster include i punti 1,0; 0,1; 100,100; 101.100 e l'altro gruppo è fatto dai punti 1,1; 0,0; 100,101; 101,101

Mi chiedo cosa sto sbagliando.

Nota: sto lavorando su quanto sopra come parte di un progetto di compiti a casa.

Grazie in anticipo!

Answer 1

Quello che stai ottenendo è corretto. Sia U la matrice che contiene gli autovettori come mostrato sopra e che siano disposti in modo tale che la prima colonna corrisponda al più piccolo autovalore e le colonne progressive corrispondano agli autovalori ascendenti. Quindi, prendi un sottoinsieme di colonne di U mantenendo gli autovettori corrispondenti agli autovalori più piccoli. Ora, leggi queste colonne in fila in un nuovo set di vettori, chiamalo Y. Cluster Y per ottenere i cluster spettrali. Quindi, supponiamo che il nostro sottoinsieme sia solo la prima colonna. Vediamo chiaramente che se si dovesse raggruppare la prima colonna, si otterrebbe il primo cluster 4 in 1 e il successivo 4 in un altro cluster, che è ciò che si desidera.

Answer 2

Due osservazioni:

1. L=D-W; L=D^(-0.5)*L*D^(-0.5); Perché lasci lo calcola la matrice di identità? Basta usare la matrice di identità eye (n) e sottrarre D^(- 0.5) * W * D^(- 0.5) da quella per calcolare la Laplacian L

2. eig restituisce gli autovettori come colonne, perché prendi la riga? Hai controllato i valori degli autovalori corrispondenti in E, quindi puoi star sicuro che stai guardando un autovelox corrispondente al secondo più piccolo autovalore?

Answer 3

Dai un'occhiata all'implementazione on Prof. J. Shi's webpage. Prestare particolare attenzione alla funzione discretisation.m.

Inoltre, il codice è molto inefficiente. È necessario trarre maggiore vantaggio dalla vettorizzazione di Matlab:

W = 10.^(- dist_mat); % single liner of nested loop for comuting W 
% computing the symmetric laplacian 
d = sum(W, 2); % sum each row 
d(d == 0) = 1; % avoid division by zero 
d_half = 1./sqrt(d); 
L = eye(n) - bsxfun(@times, bsxfun(@times, W, d_half'), d_half);