spektrale Clustering

Question

Zunächst einmal muss ich sagen, dass ich Matlab neu bin (und zu dieser Seite ...), bitte entschuldigen Sie meine Ignoranz.

Ich versuche, eine Funktion in Matlab schreiben, die Spectral Clustering verwendet, um eine Reihe von Punkten in zwei Cluster aufzuteilen.

mein Code als

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

folgt Wenn ich richtig verstehe, dann durch den zweiten kleinsten Eigenvektor mit soll ich in der Lage, eine Partition der Daten in zwei Cluster ausführen - Wenn das i-te Element der zweiten Eigenvektor ist positiv, der i-te Datenpunkt wäre in dem einen Cluster, andernfalls wäre er in dem anderen Cluster.

aber wenn ich versuche, die folgende

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

Ich würde erwarten, dass die ersten vier Punkte ein Cluster bilden würden, und die letzten vier wäre eine andere bilden.

Allerdings erhalte ich

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 

die 2. Unter Eigenvektor

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

Ich finde das ein Cluster die Punkte 1,0 enthält; 0,1; 100,100; 101.100 und die anderen Cluster wird aus den Punkten 1,1; 0,0; 100,101; 101,101

Ich frage mich, was mache ich falsch.

Hinweis: Ich arbeite an dem oben genannten als Teil eines Hausaufgabenprojekts.

Vielen Dank im Voraus!

Answer 1

Was Sie bekommen, ist korrekt. Sei U die Matrix, die die Eigenvektoren enthält, wie oben gezeigt, und lasse sie so angeordnet werden, dass die erste Spalte dem kleinsten Eigenwert und die progressiven Spalten den aufsteigenden Eigenwerten entsprechen. Nehmen Sie dann eine Teilmenge der Spalten von U, indem Sie die Eigenvektoren beibehalten, die den kleineren Eigenwerten entsprechen. Nun lies diese Spalten zeilenweise in eine neue Menge von Vektoren, nenne sie Y. Cluster Y, um die spektralen Cluster zu erhalten. Nehmen wir an, unsere Teilmenge ist nur die erste Spalte. Wir sehen deutlich, dass, wenn Sie die erste Spalte bündeln würden, Sie die ersten 4 in einen Cluster und die nächsten 4 in einen anderen Cluster bekommen würden, was Sie wollen.

Answer 2

Zwei Beobachtungen:

1. L=D-W; L=D^(-0.5)*L*D^(-0.5); Warum Sie lassen ihm die Identitätsmatrix berechnen? Verwenden Sie einfach die Identitätsmatrix eye (n) und subtrahieren Sie D^(- 0.5) * W * D^(- 0.5) daraus, um den Laplace - Operator L

2. zu berechnen. Eigen liefert die Eigenvektoren als Spalten, warum nehmen Sie die Reihe? Haben Sie die Werte der entsprechenden Eigenwerte in E überprüft, so können Sie sicher sein, dass Sie ein Eigenvek finden, das dem zweitkleinsten Eigenwert entspricht?

Answer 3

Werfen Sie einen Blick auf die Implementierung on Prof. J. Shi's webpage. Achten Sie genau auf discretisation.m Funktion.

Darüber hinaus ist Ihr Code sehr ineffizient. Sie müssen die Matlab-Vektorisierung besser ausnutzen:

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