zgrupowanie widmowe

Question

Po pierwsze muszę powiedzieć, że jestem nowy w matlab (i na tej stronie ...), więc proszę wybaczyć moją niewiedzę.

Próbuję napisać funkcję w programie Matlab, która będzie używać klastrowania Spectral do dzielenia zestawu punktów na dwa klastry.

mój kod wygląda następująco

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); 

Jeśli dobrze rozumiem, a następnie przy użyciu drugą najmniejszą wektor własny powinien być w stanie wykonać partycję danych do dwóch klastrów - Jeżeli członek-ty z 2 eigenvector jest dodatnie, i-ten punkt danych byłby w jednym klastrze, w przeciwnym razie byłby w innym klastrze.

Jednak gdy próbuję następujące

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

Spodziewam się, że pierwsze cztery punkty będą tworzyć jeden klaster, a cztery ostatnie będą tworzyć kolejny.

Jednak otrzymać

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 

Biorąc 2nd wektora własnego

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

znaleźć jeden klaster zawiera punkty 1,0; 0,1; 100,100; 101,100 i innego klastra składa się z punktów 1,1; 0,0; 100,101; 101,101

Zastanawiam się, co robię źle.

Uwaga: Pracuję nad powyższym w ramach projektu domowego.

Z góry dziękuję!

Answer 1

To, co otrzymujesz, jest poprawne. Niech U będzie macierzą zawierającą wektory własne, jak pokazano powyżej, i niech będą ułożone tak, aby pierwsza kolumna odpowiadała najmniejszej wartości własnej, a kolumny progresywne odpowiadały rosnącej wartości własnej. Następnie weź podzbiór kolumn U, zachowując wektory własne odpowiadające mniejszym wartościom własnym. Teraz przeczytaj te kolumny w wierszu w nowy zestaw wektorów, nazwij go Y. Cluster Y, aby uzyskać klastry widmowe. Przyjmijmy więc, że nasz podzbiór jest tylko pierwszą kolumną. Wyraźnie widzimy, że jeśli zgrupujesz pierwszą kolumnę, dostaniesz pierwszy klaster 4 w 1, a następny 4 w inny klaster, który jest tym, czego potrzebujesz.

Answer 2

Dwie obserwacje:

1. L=D-W; L=D^(-0.5)*L*D^(-0.5); Dlaczego pozwalasz mu obliczyć macierz tożsamości? Wystarczy użyć oka macierzy tożsamości (n) i odjąć D^(- 0,5) * W * D^(- 0,5) od tego, aby obliczyć Laplacian L

2. eig zwraca wektory własne jako kolumny, dlaczego bierzesz rząd? Czy sprawdziłeś wartości odpowiednich wartości własnych w E, więc możesz być pewien, że patrzysz na wartość własną odpowiadającą 2 najmniejszej wartości własnej?

Answer 3

Zobacz implementację on Prof. J. Shi's webpage. Zwróć szczególną uwagę na funkcję discretisation.m.

Co więcej, Twój kod jest bardzo nieefektywny. Musisz w większym stopniu wykorzystać wektoryzację Matlaba:

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);