machine-learning - 如何结合频谱聚类的拆分运行以获得巨大的亲和性矩阵

Question

引出问题

我有一个带有一系列简短值的2D复杂值图像。我想聚类相似的像素/分割图像。有一个或多或少的静态图像带有叠加的图像，其中有一些斑点，这些斑点在短序列中具有变化的值（主要是复数的角度）。在图像规范中，它们也可以稍作区分。

我的第一个尝试是k均值，但实际上是根据均值聚类的（平均值有区别，尤其是与周围的像素相比，但时间和角度信息更大）。我的第二次尝试是ICA，然后查看了幅度最大的k个分量，这确实成功地将图像中的某些区域识别为不同的区域，但没有识别出我感兴趣的像素组（在视觉上并不难认出它们，但它们很小。

现在的情况

因此，由于前两次尝试均无法解决，因此我环顾了Google，看来spectral clustering可能是合适的。但是使用该方法时，我遇到了一些严重的问题，主要是与有限的可用内存有关。然后我想，由于像素太多，我可以将光谱聚类应用于单独的数据。

有人here建议先将平板聚类，然后再将它们组合起来，然后他说：“最后，您将遇到重新组合它们的问题，并且可以轻松解决此问题”。当然，在解释中被指定为“简单”的位几乎从来都不是容易的。他链接到this论文，但是该方法不能处理平板中的所有数据。而是排除不接近主成分的向量。

题

我的问题分为两部分：

1.如何合并各个细分的结果？特征向量不同，簇数也不同。结果看起来像在单独的平板上一样。

2.不考虑单独平板中像素之间的距离/亲和力。我可以制作“楼板之间的楼板”吗？由于那些平板L和A不对称，因此不知道如何执行该方法。也许我可以以某种方式在最后比较/合并所有特征向量？

（3.是否有类似或更好的方法不需要那么多的内存。计算时间也可以接受，很容易爆炸）

Matlab代码示例

%% generate data
% get some outer region without data
tempdisk = strel('disk',922/2); tempdisk = double(repmat((1+sqrt(-1)).*tempdisk.Neighborhood,[1 1 15]));
% make some noise
tempnoise = (rand(921,921,15)+sqrt(-1).*rand(921,921,15))./10;
% 'background signal'
tempim1 = double(imresize(mean(imread('cameraman.tif'),3),[921,921])); tempim1 = repmat(tempim1./max(tempim1(:)),[1 1 15]);
% 'target signal'
tempim2 = double(rgb2hsv(imread('fabric.png'))); tempim2 = imresize(tempim2(:,:,2),[921,921]); tempim2 = repmat(tempim2./max(tempim2(:)),[1 1 15]);
sin1 = repmat(permute(sin(2.*pi.*(0:14)./15),[1 3 2]),[921 921 1]);
% combine into data
complexdata = (sin1.*(1.0.*tempim1+0.5.*tempim2.^2).*exp(-sqrt(-1).*2.*pi.*sin1.*(tempim2.^2)).*tempdisk+tempnoise)./1.5;

%this is what the mean data looks like
meannorm = mean(abs(complexdata),3);
meanangle = mean(angle(complexdata),3);
figure; subplot(1,2,1); imshow(meannorm,[]); title('mean norm'); subplot(1,2,2); imshow(meanangle,[]); title('mean angle')

生成的数据如下所示：



正确的图像中的明亮斑点是Im之后的图像。它们随时间的变化也最强（并且随时间相关）。

然后设置集群：

%% perform spectral clustering in seperate slabs 
% method from http://ai.stanford.edu/~ang/papers/nips01-spectral.pdf
%get all pixel vectors in a single matrix
complexrows = reshape(permute(complexdata, [3,1,2]), [15, 921*921]);
%k means and eigs dont accept complex, so convert to real here?
complexrowsTranspose = [real(complexrows);imag(complexrows)]'; 

%lets say 10000 by 10000 matrices are still ok
npix = 10000;
nslabpix = floor(length(complexrowsTranspose)/npix);
nrestpix = rem(length(complexrowsTranspose), npix);

在适合内存的平板中执行光谱聚类：

% spectral clustering 
keig = 50;%how many eigenvectors needed? more is better
affinity_sigma = 1;% i dont understand how to calculate this from the paper
tic
% start with last slab (dynamically preallocate)
for islabpix = (nslabpix+1):-1:1;
    %print progress
    islabpix/nslabpix
    toc
    if islabpix>nslabpix
        pixrange = (1:nrestpix) + ((islabpix-1)*npix);;
    else
        pixrange = (1:npix) + ((islabpix-1)*npix);
    end
    %calculate affinity between all voxels in slab
    Aff = exp( -squareform(pdist(complexrowsTranspose(pixrange,:))).^2/(2*affinity_sigma^2) ); % affinity matrix
    %calculate degree matrix for normalization
    Dsq = sparse(size(Aff,1),size(Aff,2)); %degree matrix
    for idiag=1:size(Aff,1)
        Dsq(idiag,idiag) = sum(Aff(idiag,:))^(1/2);
    end
    %normalize affinity matrix
    Lap = Dsq * Aff * Dsq; %normalize affinity matrix
    %calculate eigenvectors of affinity matrix
    [eigVectors(pixrange,1:keig), eigValues] = eigs(Lap, keig); %eigenvectors of normalized aff mat
    normEigVectors(pixrange,1:keig) = eigVectors(pixrange,1:keig)./repmat(sqrt(sum(abs(eigVectors(pixrange,1:keig)).^2,2)), [1 keig]); %normalize rows of eigen vectors, normr only works on real numbers
    % perform k means clustering on weights for eigenvectors
    [idx,C,sumd,D] = kmeans([real(normEigVectors(pixrange,1:keig)),imag(normEigVectors(pixrange,1:keig))], 5); %k means on normalized eigenvecotrs

    idxval(pixrange) = idx;
end
%reshape into image
idxim = reshape(idxval, [921, 921]);
figure; imshow(idxim,[])
toc

产生的聚类：



结果看起来该方法在每个平板中都在某种程度上起作用；目标是将所有斑点的范数更高且角度变化更强（tempim2中的高饱和斑点）聚在一起，这在结果中似乎是可以识别的。现在主要是单独的平板，这是问题所在，没有跨平板的群集。这花了我的电脑大约15分钟。在此示例中，我减少了特征值的数量和图像大小，因此可以在可接受的时间内运行。我认为这说明了我的部分问题。

Answer 1

我真的没有答案，但是我认为这些指针应该可以帮助您找到答案：


您声称存在内存问题。您确定亲和矩阵稀疏吗？在您的代码中似乎只有对角度矩阵是稀疏的。通常，在像素/体素上进行光谱聚类时，将亲和度矩阵设计为非常稀疏（8个连接或26个连接）。
您将群集描述为“它们很小”。光谱聚类具有known issues且其聚类的比例非常不同。您确定您得到满意的结果吗？
如何计算相邻体素之间的亲和力（相似度）？您还可以衡量差异吗？也就是说，对于某些体素，您可以说它们不属于同一类吗？如果是这样，您是否考虑过使用correlation clustering？该方法对于不同的群集规模更健壮，并且可以自动检测群集的数量。
您是否考虑过使用multiscale / multigrid方法来粗化数据，而不是将其残酷地切成“平板”？
你看过spectralNet了吗？如果我没记错的话，这种方法应该可以让您“学习”部分点的光谱聚类，然后使用网络将聚类“外推”到新的点。




更新：
根据Leo's comment，我想说的是，当涉及到非常大的数据的光谱聚类时，将数据残酷地切成“平板”，然后尝试将其“缝合”在一起可能不是最好的粗略操作（不是我认为这是不可能的）。解决该问题的更好方法是显着稀疏亲和度矩阵：仅对每个点的邻居计算成对亲和度，从而导致亲和度矩阵稀疏。这样一来，无需“切片”和“缝合”就可以一次处理所有点。

至于光谱聚类和相关聚类之间的区别：
为什么即使输入亲和矩阵如此稀疏，频谱聚类仍能够对所有点进行聚类？如何确定点a和远点c应该属于同一簇，即使它们之间没有计算亲和力也是如此？
简单的答案是相似性的transitivity：如果a与b相似，并且b与c相似，则a和c应该聚在一起。
哪里有收获？在频谱聚类中，亲和矩阵中的所有条目都是非负的，这意味着除非绝对没有连接a和c的路径（极少的机会），否则会存在一些“传递亲和力”，这表明a和c应该属于同一集群。因此，如果看一下频谱聚类的数学方法，您会注意到“平凡的解决方案”，即将所有点都放在同一聚类中，可以为该问题提供全局最优解。必须人为地迫使解决方案具有k簇，以避开琐碎的解决方案。
该怎么办？如果仅考虑正亲和度，则0值是模棱两可的：这意味着“我没有费心计算这些点之间的亲和度”，但也可能意味着“我认为这两个点不应位于同一群集中”。为了克服这种歧义，如果A(i, j) > 0表示点i和点j应该在同一簇中且确定性A(i, j)，而A(i, j) < 0表示i和j不应位于同一群集中（确定为|A(i, j)|）。引入负亲和力会打破可能链接较远点的“传递链”，而将所有点放置在同一簇中不再是微不足道的。
如何利用负面亲和力？当您的亲和力矩阵同时具有正（吸引力）和负（排斥）值时，您可以使用相关性聚类对点进行聚类，这基本上是在最大化每个聚类中各点之间的亲和力/吸引力，同时使不同聚类中各点之间的排斥性最大化。相关性聚类的一个不错的特性是，它可以“自动”发现潜在的聚类数，请参见sec。 this paper中的2。