matlab - 给定两组向量，如何为第一组中的每个向量找到第二组中最接近的向量？

Question

给定：尺寸为{S1, S2}的向量的两组D。 S1由N*D矩阵表示，因此S2由M*D矩阵表示。

我正在寻找一种优雅的方法来获取s1中每个向量S1中s2中最近的邻居S2以及相应的距离。

一个简单的方法当然就是拥有两个for循环并获取

dist = norm(s1 - s2);

但是，必须有一种更优雅，更有效的方法来执行此操作。

Answer 1

对。具有bsxfun和permute的强大功能，具有sum的一面，并且带有reshape的破折号。这是第一部分，您将在其中计算S1中的一个点与S2中的另一个点之间的成对距离：

out = reshape(sqrt(sum(bsxfun(@minus, S1, permute(S2, [3 2 1])).^2, 2)), size(S1,1), size(S2,1));

现在您需要做的最后一件事是确定S2中与每个S1最接近的向量。可以使用min完成：

[dist,ind] = min(out, [], 2);

dist将包含S1中的点与S2中的点之间的最小距离，而ind会告诉您是哪一点。



这段代码看起来很吓人，但让我们将其分解为几部分。


permute(S2, [3 2 1])：这采用矩阵S2，它是一个M x D矩阵，并且对尺寸进行了混洗，使其成为一个1 x D x M矩阵....现在我们为什么要这样做？让我们继续下一部分，它将更有意义。
bsxfun(@minus, S1, ...)：bsxfun代表二进制单例扩展功能。 bsxfun的作用是，如果您有两个输入，其中两个输入中的一个或两个都具有单一尺寸，或者两个输入中的任何一个只有一个尺寸值为1的尺寸，则每个输入都将复制为其单一尺寸以匹配尺寸另一个输入，然后按元素操作将这些输入一起应用于生成您的输出。在这种情况下，我想将这两个新形成的输入相减。

因此，假设S1是N x D ...或从技术上讲，这是N x D x 1，并且S2是M x D（我对其进行了排列以使其变为1 x D x M），我们将创建一个N x D x M长的新矩阵。第一个输入将自身复制为3D矩阵，其中每个切片均等于S1，即N x D。 S2现在是3D矩阵，但以这样的方式表示：原始矩阵中的每一行都是3D矩阵中的一个切片，其中每个切片仅由一行组成。这对于N行是重复的。

现在，我们应用@minus操作，其效果是，对于此新矩阵中的每个输出切片i，这将为您提供i中的S2点与所有其他点之间的分量明智差异。点在S1中。例如，对于切片＃1，行＃1为您提供S2中的点＃1和S1中的点＃1之间的分量明智差异。第2行为您提供S2中的点＃1和点＃2 S1之间的分量明智的差异，依此类推。
sum((...).^2, 2)：我们想找到一个点与另一个点之间的欧几里得距离，因此我们将这些距离求和独立地求和。这将导致一个新的3D矩阵，其中每个切片包含N值，其中每个N点的距离都为M。例如，第一个切片将为您提供距S2中的＃1点与S1中的所有其他点的距离。
out = reshape(..., size(S1,1), size(S2,1));：现在，我们对其进行重塑，使其变为一个M x N矩阵，以便(i,j)的每一行和每一列对都为您提供i中的S1点和j中的S2点之间的距离，从而完成了计算。
进行[dist,ind] = min(out, [], 2);确定S1中的一个点与S2中的其他点之间的最小距离。 dist会给您最小的距离，而ind会告诉您它是哪个向量。因此，对于dist中的每个元素，它为您提供了i中的点S1和S2之一之间的最小距离，并且ind告诉您哪个向量属于S2。




通过使用您提出的遍历每对点并计算范数的方法，我们可以验证这是否为我们提供了正确的结果。让我们创建S1和S2：

S1 = [1 2 3; 4 5 6; 7 8 9; 10 11 12];
S2 = [-1 -1 -1; 0 9 8];

显示得更整洁：

>> S1

S1 =

     1     2     3
     4     5     6
     7     8     9
    10    11    12

>> S2

S2 =

    -1    -1    -1
     0     9     8

使用循环方法，我们有以下代码：

out = zeros(size(S1,1), size(S2,1));
for ii = 1 : size(S1,1)
    for jj = 1 :size(S2,1) 
        out(ii,jj) = norm(S1(ii,:) - S2(jj,:));
    end
end

我们得到这个矩阵：

>> out

out =

    5.3852    8.6603
   10.4881    6.0000
   15.6525    7.1414
   20.8327   10.9545

同样，如果运行我编写的代码，我们还将得到：

>> out = reshape(sqrt(sum(bsxfun(@minus, S1, permute(S2, [3 2 1])).^2, 2)), size(S1,1), size(S2,1))

out =

    5.3852    8.6603
   10.4881    6.0000
   15.6525    7.1414
   20.8327   10.9545

为了完成此过程，让我们找到最小的距离和相应的向量：

>> [dist,ind] = min(out, [], 2);
>> dist

dist =

    5.3852
    6.0000
    7.1414
   10.9545

>> ind

ind =

     1
     2
     2
     2

因此，对于S1中的第一个向量，在S2中与它最接近的向量是第一个向量，距离为5.3852。类似地，S1的第二个矢量，是S2中最接近的矢量，是第二个矢量，距离为6。您可以对其他值重复此操作，以确保它是正确的。