내부가 아닌 두 개의 다른 Numpy 어레이에서 점 사이의 최소 유클리드 거리

Question

나는 두 개의 배열이 있습니다 엑스-와이 좌표, 그리고 나는 사이의 최소 유클리드 거리를 찾고 싶습니다. 각 하나의 배열을 가리키십시오 모두 다른 배열의 포인트. 배열이 반드시 같은 크기는 아닙니다. 예를 들어:

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 (길이 중) 그리고 xy2 (길이 피) 안으로 xy (길이 N), 그리고 원래 배열의 길이를 저장합니다. 이론적으로 나는 NXN 내가 잡을 수있는 좌표의 거리 매트릭스 MXP 하위 매트릭스. 이 하위 매트릭스를 효율적으로 생성하는 방법이 있습니까?

Answer 1

(몇달 뒤)scipy.spatial.distance.cdist( X, Y )x와 y 2 dim, 3 dim ...에 대한 모든 거리 쌍을 제공합니다.
또한 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

Answer 2

거리의 p 매트릭스에 의해 m을 계산하려면 다음이 작동해야합니다.

>>> 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 전화는 그것들을 같은 모양의 매트릭스 (스칼라 유클리드 거리의)로 바꿉니다.

Answer 3

당신이하려는 일을 위해 :

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])

Answer 4

허용 된 답변은 질문을 완전히 다루지 않습니다. 최저한의 두 지점 세트 사이의 거리는 사이의 거리가 아닙니다. 모든 두 세트를 가리 킵니다.

원래 질문에 대한 간단한 솔루션은 실제로 사이의 거리를 계산하는 것으로 구성됩니다. 모든 쌍과 엄청나게 최소를 찾는 것은 최저한의 거리. 후자의 문제에 대한 훨씬 빠른 해결책이 존재합니다.

제안 된 모든 솔루션에는 다음과 같은 규모의 실행 시간이 있습니다. 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 각 지점 사이의 최소 거리입니다 xy1 그리고 포인트 세트 xy2

Answer 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)