43

我有两个x - y坐标数组，我想找到一个数组中的每个点与另一个数组中的所有点之间的最小欧几里得距离。数组不一定大小相同。例如：

xy1=numpy.array(
[[  243,  3173],
[  525,  2997]])

xy2=numpy.array(
[[ 682, 2644],
[ 277, 2651],
[ 396, 2640]])

我当前的方法循环遍历每个坐标xy并xy1计算该坐标与其他坐标之间的距离。

mindist=numpy.zeros(len(xy1))
minid=numpy.zeros(len(xy1))

for i,xy in enumerate(xy1):
    dists=numpy.sqrt(numpy.sum((xy-xy2)**2,axis=1))
    mindist[i],minid[i]=dists.min(),dists.argmin()

有没有办法消除 for 循环并以某种方式在两个数组之间进行逐个元素的计算？我设想生成一个距离矩阵，我可以为它找到每一行或每一列中的最小元素。

另一种看待问题的方式。假设我将xy1(length m ) 和xy2(length p ) 连接到xy(length n ) 中，并存储原始数组的长度。从理论上讲，我应该能够从那些我可以从中获取 mxp 子矩阵的坐标生成一个 nxn 距离矩阵。有没有办法有效地生成这个子矩阵？

4

7 回答 7

46

（几个月后） scipy.spatial.distance.cdist( X, Y ) 给出所有成对的距离，对于 X 和 Y 2 暗，3 暗......
它也有 22 种不同的规范，详细 在这里。

# cdist example: (nx,dim) (ny,dim) -> (nx,ny)

from __future__ import division
import sys
import numpy as np
from scipy.spatial.distance import cdist

#...............................................................................
dim = 10
nx = 1000
ny = 100
metric = "euclidean"
seed = 1

    # change these params in sh or ipython: run this.py dim=3 ...
for arg in sys.argv[1:]:
    exec( arg )
np.random.seed(seed)
np.set_printoptions( 2, threshold=100, edgeitems=10, suppress=True )

title = "%s  dim %d  nx %d  ny %d  metric %s" % (
        __file__, dim, nx, ny, metric )
print "\n", title

#...............................................................................
X = np.random.uniform( 0, 1, size=(nx,dim) )
Y = np.random.uniform( 0, 1, size=(ny,dim) )
dist = cdist( X, Y, metric=metric )  # -> (nx, ny) distances
#...............................................................................

print "scipy.spatial.distance.cdist: X %s Y %s -> %s" % (
        X.shape, Y.shape, dist.shape )
print "dist average %.3g +- %.2g" % (dist.mean(), dist.std())
print "check: dist[0,3] %.3g == cdist( [X[0]], [Y[3]] ) %.3g" % (
        dist[0,3], cdist( [X[0]], [Y[3]] ))


# (trivia: how do pairwise distances between uniform-random points in the unit cube
# depend on the metric ? With the right scaling, not much at all:
# L1 / dim      ~ .33 +- .2/sqrt dim
# L2 / sqrt dim ~ .4 +- .2/sqrt dim
# Lmax / 2      ~ .4 +- .2/sqrt dim
于 2010-06-27T16:22:18.993 回答
30

要计算 m x p 距离矩阵，这应该有效：

>>> def distances(xy1, xy2):
...   d0 = numpy.subtract.outer(xy1[:,0], xy2[:,0])
...   d1 = numpy.subtract.outer(xy1[:,1], xy2[:,1])
...   return numpy.hypot(d0, d1)

调用产生两个这样的.outer矩阵（沿两个轴的标量差异），.hypot调用将它们变成相同形状的矩阵（标量欧几里得距离）。

于 2009-12-09T04:44:54.250 回答
12

接受的答案并没有完全解决这个问题，它要求找到两组点之间的最小距离，而不是两组中每个点之间的距离。

尽管对原始问题的直接解决方案确实包括计算每对之间的距离并随后找到最小的距离，但如果只对最小距离感兴趣，则没有必要这样做。对于后一个问题，存在一个更快的解决方案。

所有提出的解决方案的运行时间都可以缩放为m*p = len(xy1)*len(xy2). 这对于小型数据集来说是可以的，但可以编写一个最佳解决方案，将其缩放为m*log(p)，从而为大型xy2数据集节省大量成本。

可以使用scipy.spatial.cKDTree实现这种最佳执行时间缩放，如下所示

import numpy as np
from scipy import spatial

xy1 = np.array(
    [[243,  3173],
     [525,  2997]])

xy2 = np.array(
    [[682, 2644],
     [277, 2651],
     [396, 2640]])

# This solution is optimal when xy2 is very large
tree = spatial.cKDTree(xy2)
mindist, minid = tree.query(xy1)
print(mindist)

# This solution by @denis is OK for small xy2
mindist = np.min(spatial.distance.cdist(xy1, xy2), axis=1)
print(mindist)

其中是每个点和点集mindist之间的最小距离xy1xy2

于 2017-09-07T12:54:36.477 回答
5

对于您要执行的操作：

dists = numpy.sqrt((xy1[:, 0, numpy.newaxis] - xy2[:, 0])**2 + (xy1[:, 1, numpy.newaxis - xy2[:, 1])**2)
mindist = numpy.min(dists, axis=1)
minid = numpy.argmin(dists, axis=1)

编辑：而不是调用sqrt，做方块等，你可以使用numpy.hypot：

dists = numpy.hypot(xy1[:, 0, numpy.newaxis]-xy2[:, 0], xy1[:, 1, numpy.newaxis]-xy2[:, 1])
于 2009-12-09T04:34:52.923 回答
5 
import numpy as np
P = np.add.outer(np.sum(xy1**2, axis=1), np.sum(xy2**2, axis=1))
N = np.dot(xy1, xy2.T)
dists = np.sqrt(P - 2*N)
于 2017-04-12T02:27:05.127 回答
0

我认为以下功能也有效。

import numpy as np
from typing import Optional
def pairwise_dist(X: np.ndarray, Y: Optional[np.ndarray] = None) -> np.ndarray:
    Y = X if Y is None else Y
    xx = (X ** 2).sum(axis = 1)[:, None]
    yy = (Y ** 2).sum(axis = 1)[:, None]
    return xx + yy.T - 2 * (X @ Y.T)

解释
假设每行X和Y是两组点的坐标。
让它们的大小分别为m X p和p X n。
结果将产生一个大小为 numpy 的数组，m X n第-th 条目分别是和的第- 行和第 - 行(i, j)之间的距离。ijXY

于 2020-10-13T15:17:16.047 回答
0

我强烈建议使用一些内置的方法来计算平方，并为它们定制根以优化计算方式并且非常安全地防止溢出。

就溢出而言，下面的@alex 答案是最安全的，而且应该非常快。同样对于单点，您可以使用现在支持超过 2 维的 math.hypot。

>>> def distances(xy1, xy2):
...   d0 = numpy.subtract.outer(xy1[:,0], xy2[:,0])
...   d1 = numpy.subtract.outer(xy1[:,1], xy2[:,1])
...   return numpy.hypot(d0, d1)

安全问题

i, j, k = 1e+200, 1e+200, 1e+200
math.hypot(i, j, k)
# np.hypot for 2d points
# 1.7320508075688773e+200

np.sqrt(np.sum((np.array([i, j, k])) ** 2))
# RuntimeWarning: overflow encountered in square

上溢/下溢/速度

于 2021-09-26T10:35:22.497 回答