譜聚類

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