Если вы используете лапласиан, как в своем коде («настоящий» лапласиан), то для группировки ваших точек в два набора вам понадобится собственный вектор, соответствующий второму наименьшему собственному значению.
Интуитивная идея состоит в том, чтобы соединить все ваши точки друг с другом с помощью пружин, где пружины становятся более жесткими, если точки находятся рядом друг с другом, и менее жесткими, если точки находятся далеко. Собственные векторы лапласиана — это режимы вибрации, если вы ударяете молотком по пружинной сети и наблюдаете, как она колеблется: меньшие собственные значения соответствуют низкочастотным «объемным» модам, а большие собственные значения соответствуют более высокочастотным колебаниям. Вы хотите, чтобы собственное значение соответствовало второму наименьшему собственному значению, которое будет похоже на вторую моду в барабане, с положительной сгруппированной вместе и отрицательной частью сгруппированной вместе.
Теперь в комментариях возникает некоторая путаница по поводу того, следует ли использовать наибольшее или наименьшее собственное значение, и это связано с тем, что лапласиан в статье, на которую ссылается Дэйв, немного отличается, будучи тождеством минус ваш лапласиан. Так что там они хотят самые большие, а вы хотите самые маленькие. Кластеризация в документе также немного более продвинута и лучше, но не так проста в реализации.
Вот ваш код, модифицированный для работы:
load rings.mat
[D, N] = size(X); % data stored in X
%initial plot data
figure; hold on;
for i=1:N,
plot(X(1,i), X(2,i),'o');
end
% perform spectral clustering
W = zeros(N,N);
D = zeros(N,N);
sigma = 0.3; % <--- Changed to be smaller
for i=1:N,
for j=1:N,
xixj2 = (X(1,i)-X(1,j))^2 + (X(2,i)-X(2,j))^2 ;
W(i,j) = exp( -1*xixj2 / (2*sigma^2) ) ; % compute weight here
% if (i==j)
% W(i,j)=0;
% end;
end;
D(i,i) = sum(W(i,:)) ;
end;
L = D - W ;
normL = D^-0.5*L*D^-0.5;
[u,s,v] = svd(normL);
% New code below this point
cluster1 = find(u(:,end-1) >= 0);
cluster2 = find(u(:,end-1) < 0);
figure
plot(X(1,cluster1),X(2,cluster1),'.b')
hold on
plot(X(1,cluster2),X(2,cluster2),'.r')
hold off
title(sprintf('sigma=%d',sigma))
Вот результат:
Теперь обратите внимание, что я изменил сигму на меньшую — с 1,0 до 0,3. Когда я оставил его на 1.0, я получил следующий результат:
что, как я предполагаю, связано с тем, что при сигме = 1 точки во внутреннем кластере могли «притягивать» внешний кластер (от которого они находятся примерно на расстоянии 1) достаточно, чтобы было энергетически выгоднее разделить оба круга пополам. как твердый вибрирующий барабан, а не два разных круга.
person
Nick Alger
schedule
20.11.2015
