匹配 2 个矩阵的行以获得行差异的最小总和

Question

我有 2 个行数和列数相等的矩阵。 A(4x3) 和 B(4x3).

我想将 A 的行与 B 的行进行匹配，以便在相减时得到最小和。 A 和 B 内部的示例：

A=  -0.3612   -0.1911   -15.3818
     0.0376    0.0206    0.3498
     0.0418    0.0229    0.3887
     0.0188    0.0103    0.1749

我正在这样做：

for j=1:size(B,1)
    [vv, inds]=min(sum(abs(bsxfun(@minus,A,B(j,:))),2));
    minJJ(j,:)=vv;  
    indsMatch(j,:)=inds;
    MM=min( minJJ);

    [A,ps] = removerows(A,'ind',inds);
    [B,ps] = removerows(B,'ind',j); 
end

我收到错误：

Improper assignment with rectangular empty matrix.

我想用这个得到的是indsMatch。我想要矩阵 A 的 'order of rows indexes' 与 B 的行配对（基于最小差异）。 B 的索引保留为 1 2 3 4.

Answer 1

除了实现错误之外，您总是选择具有最小距离的行对的贪婪方法是错误的。以这个例子为例：

A=zeros(4,3);A(:,1)=[0,1,2,3]
B=zeros(4,3);B(:,1)=[0,1,2,3]+.9

虽然最佳解决方案是不置换任何东西，但如果 A 与 B 的 1 到 3 总差为 0.3，则代码首先将第 2 行对齐到第 4 行，然后将 1 与 4 相加另一个 3.9 加起来总共 4.2 而最佳是 4*0.9=3.6

我不知道有什么方法比暴力破解所有组合更好。

为了给您一个正确实施的良好开端，首先要降低问题的复杂性。计算距离矩阵：

distanceMatrix=sum(abs(bsxfun(@minus,permute(A,[1,3,2]),permute(B,[3,1,2]))),3);

反映A的行距B的行距

Answer 2

蛮力，但矢量化。

%// data
A = [ -0.3612   -0.1911   -15.3818
     0.0376    0.0206    0.3498
     0.0418    0.0229    0.3887
     0.0188    0.0103    0.1749 ]
B = flipud(A) + 0.2

%// number of rows and columns
[n,m] = size(A);
allcombs = perms(1:n).';  %'
%// all sortings of A
AA = A(allcombs(:),:)
%// repeat whole matrix B n! times
BB = repmat(B,factorial(n),1)
%// differences
D = bsxfun(@minus, AA, BB)
%// sum(abs( ... ))
E = blockproc(D,[n,m],@(x) sum(abs( x.data(:) )))
%// idx of minimum set
[~,idx] = min(E)

%// output
Aout = AA(idx:idx+n-1,:)
Bout = BB(idx:idx+n-1,:)

如果 n > 11 或更少，此方法可能会失败。

blockproc 需要 图像处理工具箱。

Answer 3

这是另一种矢量化方法。它尝试 B 行的所有排列，并在矩阵 Bresult.

中生成最佳行排列 B

[m, n] = size(A);
ind = perms(1:m);                                  % // all permutations of row indices
BB = permute(reshape(B(ind.',:),m,[],n),[1 3 2]);  %'// all row-permuted B matrices 
C = sum(sum(abs(bsxfun(@minus, A, BB)),2),1);      % // compute the sum for each
[minsum, imin] = min(C);                           % // minimize
Bresult = B(ind(imin,:),:);                        % // output result

匹配 2 个矩阵的行以获得行差异的最小总和

Match rows of 2 matrices for a minimum total sum of row-wise differences

matlab

rows

matrix

difference