快速计算成对距离和Matlab中最近邻的方法? [英] Fast way to compute pairwise distances and the nearest neighbours in Matlab?

问题描述

我有一个n×d矩阵A，代表n个d维点.我还有另一个m×d矩阵B，代表m个d维点.

1. 我想知道如何有效地计算其(i，j)的m×n矩阵 元素表示第i行之间的欧几里得距离 矩阵A和矩阵B的第j行?
2. 如何有效地确定m个元素的向量，其第k个 元素表示最接近B的第k行的A的行?

请注意，我知道如何使用循环执行以上两个操作.但是在Matlab中，使用循环效率不高，因此我提出了这些问题.

谢谢！

解决方案

如果您有足够的RAM，可以采用一种有效的方法

[idxA,idxB] = ndgrid(1:n,1:m);

distMat = zeros(n,m);

distMat(:) = sqrt( sum((A(idxA,:) - B(idxB,:)).^2,2) );

您绝对应该对这两种解决方案进行简要介绍，因为可以充分优化循环，从而使ndgrid解决方案的速度更慢.

要找到A中最接近B点的行，可以使用min.请注意，这只会给您每个点一个最小距离.如果需要确定纽带，则必须使用find.

[minDist,closestRowsInA] = min(distMat,[],1); 

I have a n by d matrix A, representing n d-dimensional points. I have another m by d matrix B, representing m d-dimensional points.

1. I wonder how to efficiently computer a m by n matrix, whose (i,j) element represents the Euclidean distance between the i-th row of matrix A and the j-th row of matrix B?
2. How shall I efficiently determine a vector of m elements, whose k-th element represents the row of A closest to the k-th row of B?

Note I know how to do the above two using loops. But in Matlab, it is not efficient to use loops, so I ask these questions.

Thanks!

解决方案

If you have enough RAM, an efficient way could be

[idxA,idxB] = ndgrid(1:n,1:m);

distMat = zeros(n,m);

distMat(:) = sqrt( sum((A(idxA,:) - B(idxB,:)).^2,2) );

You should definitely profile the two solutions, since the loop may be sufficiently optimized that the ndgrid solution is slower.

To find the row in A closest to the points in B, you can use min. Note that this will only give you one minimum distance for each point; if you need to identify ties, you have to use find.

[minDist,closestRowsInA] = min(distMat,[],1); 

这篇关于快速计算成对距离和Matlab中最近邻的方法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！