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

Question

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

我在找一个优雅的方式来获得每个向量s1在S1近邻s2中S2和根据距离.

一个简单的方法当然是有两个for循环和get

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告诉你哪个点.

这段代码看起来非常令人生畏,但让我们把它分解成碎片.

1. permute(S2, [3 2 1]):这需要矩阵S2,它是一个M x D矩阵并对尺寸进行混洗,使其成为1 x D x M矩阵....现在我们为什么要这样做呢？让我们进入下一部分,它会更有意义.

2. bsxfun(@minus, S1, ...):bsxfun代表乙 inary 小号 ingletonË X潘申FUN ction.什么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为您提供了点#1 S2和点#1 之间的组件明智差异S1.第2行为您提供了点#1 S2和点#2 之间的组件明智差异S1,依此类推.

3. sum((...).^2, 2):我们想要找到一个点和另一个点之间的欧几里德距离,因此我们将每个列的平方距离相加.这导致新的3D矩阵,其中每个切片包含每个点N都有N距离的M值.例如,第一个切片将为您提供距离点#1 in S2的所有其他点的距离S1.

4. out = reshape(..., size(S1,1), size(S2,1));:我们现在这个重塑,使之成为一个M x N矩阵,使每一行和每一列一双(i,j)给你点之间的距离i在S1和j中S2,从而完成计算.

5. 执行[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.您可以对其他值重复此操作,看它是否正确.

Answer 2

一行怎么样？

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

ind是S2每个向量中最近向量的索引S1,并dist给出相应的最小距离.

借用@ rayryeng的例子,

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