基于等价性将值分组在一起

Question

我有一个 Nx2 矩阵（在本例中为 6X2），如下所示：

我想按以下方式对它们进行分组：

*(5,4) 是第一组。它与剩余的行一起检查。由于5和4都没有出现在剩余的行中，所以可以保持原样。

*(8,6) 是下一组。然而在第 3 行 8 再次出现为 (9,8)。所以它连接到第二组，即第二组变成（8,6,9,8）。

*下一个(10,9)是seen.But 9属于第2组，10也加进去了。所以第二组现在是 (8,6,9,8,10,9)。

*看到下一个(15,14)。到目前为止，它还没有出现或重复。所以它变成了第三组即（15,14）。

*终于看到了(16,15)。但由于 15 在第 3 组中重复出现，该组现在更新为 (15,14,16,15)。

最后可以使用MATLAB中的unique命令去除组中的冗余元素

我希望最终输出为组数：

5   4
8   6   9   10
15  14  16

注意：行组中元素的顺序并不重要，因为 (5,4) 或 (4,5) 是相同的。另外我猜，最终输出可能附加了零，以使其成为一个等维矩阵，即

5   4   0   0 
8   6   9  10 
15 14  16   0

请帮忙。谢谢。

Answer 1

这让我想起了一个一般的聚类问题。 Cuthill-McKee 算法正是您要搜索的内容，尽管它通常用不同的术语表示。好消息是Matlab在symrcm函数中实现了它。

这是一段适用于您的示例的代码。请注意，它非常强大，并且还能够处理更复杂的数据集：

% --- Definition
D = [5 4 ; 8 6 ; 9 8 ; 10 9 ; 15 14 ; 16 15];
N = max(D(:));
U = unique(D(:));

% --- Tansformation to adjacency matrix
A = sparse(N,N);

% Diagonal element
for i = 1:numel(U)
    A(U(i),U(i)) = 1;
end

% Adjacency links
for i = 1:size(D,1)
    A(D(i,1),D(i,2)) = 1;
    A(D(i,2),D(i,1)) = 1;
end

% --- Cuthill Mc-Kee algorithm
r = symrcm(A);

% --- Find the clusters

% Preparation
B = (A(r,r)^N)>0;
i = 1;
C = {};

% Find clusters iteratively
while i<=N

     if ~any(B(:,i))
         i = i+1;
     else
         I = find(B(:,i));
         i = max(I)+1;
         C{end+1} = r(I);
     end

end

% --- Display
for i = 1:numel(C)
    disp(C{i})
end

和输出：

5     4
10     9     8     6    
16    15    14

最佳，

Answer 2

所以，我觉得应该有一种方法可以使用基于树的算法或 disjoint-set/union-find 类型的方法来做到这一点。但是对于可能不是那么有效的肮脏的第一种方法，我编写了以下代码：

A = [5 4
     8 6
     9 8     
    10 9
    15 14
    16 15
     8 8
     3 4
     3 1
     ];
B = mat2cell(A,ones(size(A,1),1),2);

iter = 1;
while(true)
    if (iter > size(B,1))
        break
    end
    y = B{iter};
    C = cat(1,false(iter,1),cellfun(@(x) any(sum(bsxfun(@eq,x,y'))),B(iter+1:end)));
    if any(C)
        B{iter} = (cat(2,B{iter}, B{C}));
        % or put you can start shortening them here, by calling unique() already:
        %B{iter} = unique(cat(2,B{iter}, B{C}));
        B(C) = [];
    else
        iter = iter+1;
    end
end

B = cellfun(@unique,B,'uni',false);
B{:}

效果还不错。我不知道这是否能满足您的需求，但快速编写代码很有趣。感谢您提出有趣的问题。

基于等价性将值分组在一起

Grouping values together based on equivalence

arrays

matlab

matrix-indexing