谱聚类

Question

首先，我必须说我是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个部件特征向量是正的，第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; 101100 和其他集群是从点1,1; 0,0; ​​100,101; 101,101

我想知道我在做什么错。

注：我正在研究上述作为家庭作业项目的一部分。

在此先感谢！

Answer 1

你所得到的是正确的。设U是包含如上所示的特征向量的矩阵，并且将它们排列成使得第一列对应于最小特征值，而渐进列对应于上行特征值。然后，通过保留与较小特征值对应的特征向量来取U的一个列子集。现在，将这些列逐行读入一组新的向量中，将其称为Y.群集Y以获得谱群集。所以，让我们假设我们的子集只是第一列。我们清楚地看到，如果你要聚集第一列，你会得到第一个4到1个簇，然后4到另一个簇，这是你想要的。

Answer 2

两个意见：

1. L=D-W; L=D^(-0.5)*L*D^(-0.5); 你为什么让他计算单位矩阵？只需使用单位矩阵眼睛（n）并减去D ^（ - 0.5）* W * D ^（ - 0.5）即可计算出拉普拉斯算子L为什么要将该特征向量作为列返回，行？您是否检查了E中相应特征值的值，因此您可以确定您正在查看对应于第二小特征值的特征值？

Answer 3

看看执行on Prof. J. Shi's webpage。密切关注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);