谱聚类

Question

首先，我必须说我是matlab的新手（也是这个网站的新手...），所以请原谅我的无知。

我正在尝试编写一个在matlab中使用谱聚类将一组点分成两个簇的函数。

我的代码如下：

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个成员是正数，则第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组成。

我想知道我做错了什么。

注意：我正在作为一个家庭作业项目而处理以上内容。

提前致谢！

- user2182857

Answer 1

您所得到的是正确的。令U为包含如上所示特征向量的矩阵，并安排它们使第一列对应最小特征值，随后的列对应升序特征值。然后，通过保留对应较小特征值的特征向量来获取U的列的子集。现在，将这些列逐行读入一个新的向量集Y中，进行聚类以获取谱聚类。因此，让我们假设我们的子集只有第一列。我们清楚地看到，如果u对第一列进行聚类，u将把前4个聚合成一个簇，把接下来的4个聚合成另一个簇，这正是您想要的。

- Spectre

Answer 2

请看J. Shi教授的网页上的实现。请注意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 );

- Shai

Answer 3

两点观察：

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中相应特征值的值，以确保正在查看与第二小特征值对应的特征向量？

- uberwach