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

Question

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

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

一个简单的方法当然是有两个 for 循环并得到

dist = norm(s1 - s2);

但是，必须有一种更优雅、更有效的方法来做到这一点。

Answer 1

是的。拥有bsxfun and permute, with a side of sum, and a dash of 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代表Binary Singleton EXpansion FUN动作。 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，这会给出点 [=50] 之间的分量差异=] 在 S2 中，所有其他点在 S1 中。例如，对于切片 #1，行 #1 为您提供 S2 中的点 #1 和 S1 中的点 #1 之间的分量差异。第 2 行为您提供 S2 中的第 1 点和第 2 点 S1 之间的组件差异，依此类推。
sum((...).^2, 2)：我们想要找到一个点和另一个点之间的欧几里得距离，所以我们将这些距离的平方独立地加在每一列上。这会产生一个新的 3D 矩阵，其中每个切片包含 N 值，其中每个 M 点有 N 距离。例如，第一个切片将为您提供从 S2 中的点 #1 到 S1 中所有其他点的距离。
out = reshape(..., size(S1,1), size(S2,1));：我们现在重塑它，使它成为一个 M x N 矩阵，这样 (i,j) 的每一行和列对都会为您提供点之间的距离S1中的i和S2中的j，从而完成计算。
执行 [dist,ind] = min(out, [], 2); 确定 S1 中的一个点与 S2 中的其他点之间的最小距离。 dist 会给你最小的距离，而 ind 会告诉你 它是哪个矢量 。因此，对于 dist 中的每个元素，它为您提供 S1 中的点 i 与 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。你可以对其他值重复这个，看看它是否正确。

Answer 2

在一行中怎么样？

[dist, ind] = min(pdist2(S2,S1));

ind是S1中每个向量在S2中最近向量的索引，dist给出对应的最小距离。

借用、

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

结果是

dist =
   5.385164807134504   6.000000000000000   7.141428428542850  10.954451150103322
ind =
    1     2     2     2

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

Given two sets of vectors, how do I find the closest vector in the second set for each vector in the first set?

matlab

cluster-analysis

vector

nearest-neighbor