спектральная кластеризация

Во-первых, я должен сказать, что я новичок в Matlab (и на этом сайте...), поэтому, пожалуйста, извините мое невежество.

Я пытаюсь написать функцию в Matlab, которая будет использовать Spectral Clustering для разделения набора точек на два кластера.

мой код выглядит следующим образом

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

Если я правильно понимаю, то, используя второй наименьший собственный вектор, я должен иметь возможность выполнить разделение данных на два кластера. Если i-й член 2-го собственного вектора положителен, i-я точка данных будет в одном кластере, иначе это было бы в другом кластере.

Однако, когда я пытаюсь сделать следующее

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

Я ожидаю, что первые четыре точки сформируют один кластер, а последние четыре — другой.

Однако я получаю

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

Взяв второй собственный вектор

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

Я обнаружил, что один кластер включает точки 1,0;0,1;100,100;101,100, а другой кластер состоит из точек 1,1;0,0;100,101;101,101.

Интересно, что я делаю неправильно?

Примечание. Я работаю над вышеперечисленным как часть домашнего задания.

Заранее спасибо!


matlab cluster-analysis linear-algebra eigenvector
person user2182857    schedule 18.03.2013    source источник

Ответы (3)


arrow_upward
4
arrow_downward

То, что вы получаете, правильно. Пусть U будет матрицей, содержащей собственные векторы, как показано выше, и пусть они расположены так, что 1-й столбец соответствует наименьшему собственному значению, а прогрессивные столбцы соответствуют возрастающим собственным значениям. Затем возьмите подмножество столбцов U, сохранив собственные векторы, соответствующие меньшим собственным значениям. Теперь прочитайте эти столбцы построчно в новый набор векторов, назовите его Y. Кластер Y, чтобы получить спектральные кластеры. Итак, предположим, что наше подмножество — это только первый столбец. Мы ясно видим, что если u сгруппировать первый столбец, u получит первые 4 в 1 кластер, а следующие 4 — в другой кластер, чего вы и хотите.

person Spectre    schedule 19.03.2013

arrow_upward
3
arrow_downward

Взгляните на реализацию на веб-странице профессора Дж. Ши. Обратите особое внимание на функцию discretisation.m.

Более того, ваш код очень неэффективен. Вам нужно больше использовать векторизацию 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 );
person Shai    schedule 19.03.2013

arrow_upward
2
arrow_downward

Два наблюдения:

  1. L=D-W; L=D^(-0.5)*L*D^(-0.5); Почему вы позволяете ему вычислять единичную матрицу? Просто используйте единичную матрицу eye(n) и вычтите из нее D^(-0,5) * W * D^(-0,5), чтобы вычислить лапласиан L

  2. eig возвращает собственные векторы в виде столбцов, почему вы берете строку? Вы проверили значения соответствующих собственных значений в E, чтобы быть уверенными, что вы смотрите на собственный вектор, соответствующий второму наименьшему собственному значению?

person uberwach    schedule 19.03.2013