Minimaler euklidischer Abstand zwischen Punkten in zwei verschiedenen Arrays Numpy, nicht innerhalb von

Question

Ich habe zwei Arrays von x - y Koordinaten, und ich möchte den minimalen euklidischen Abstand zwischen finden jeder Punkt in einem Array mit alle die Punkte in der anderen Reihe. Die Arrays sind nicht notwendigerweise die gleiche Größe. Zum Beispiel:

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

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

My Stromverfahren durchlaufen jeden Koordinaten xy in xy1 und berechnet die Abstände zwischen der Koordinate und den anderen Koordinaten.

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

Gibt es eine Möglichkeit die for-Schleife zu beseitigen und irgendwie zu tun Element-für-Element-Berechnungen zwischen den beiden Feldern? Ich sehe eine Abstandsmatrix zu erzeugen, für die ich das kleinste Element in jeder Zeile oder Spalte finden könnte.

Eine andere Möglichkeit, das Problem zu suchen. Sagen I verketten xy1 (Länge M ) und xy2 (Länge p ) in xy (Länge n ), und ich speichern die Längen des ursprünglichen Arrays. Theoretisch soll ich dann in der Lage sein, ein n x n Abstandsmatrix aus diesen Koordinaten zu erzeugen, aus denen ich ein m x p Submatrix greifen. Gibt es eine Möglichkeit, um effizient diese Submatrix zu generieren?

Answer 1

(Monate später) scipy.spatial.distance.cdist( X, Y ) gibt alle Paare von Entfernungen, für X und Y 2 dim, 3 dim ...
Auch hat es 22 verschiedene Normen, detaillierte hier .

# 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

, um den m durch p Matrix von Entfernungen zu berechnen, sollte diese Arbeit:

>>> 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 Anrufe zwei solcher Matrices (skalarer Unterschiede entlang der beiden Achsen), die Anrufe .hypot schaltet diese in einer gleichFormMatrix (skalarer euklidischen Abstände).

Answer 3

Für das, was Sie zu tun versuchen:

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)

Bearbeiten : Statt sqrt aufzurufen, tun Quadrate, etc., können Sie numpy.hypot verwenden:

dists = numpy.hypot(xy1[:, 0, numpy.newaxis]-xy2[:, 0], xy1[:, 1, numpy.newaxis]-xy2[:, 1])

Answer 4

Die akzeptierte Antwort bezieht sich nicht vollständig auf die Frage, was die Minimum zu finden fordert Abstand zwischen den beiden Sätzen von Punkten, nicht der Abstand zwischen jeder Punkt in den beiden Sets.

Altough eine einfache Lösung auf die ursprüngliche Frage in der Tat die Entfernung der Berechnung zwischen besteht alle Paar und susequently das Minimum einen zu finden, ist dies nicht notwendig, wenn man nur daran interessiert, in dem Minimum Entfernungen. Eine viel schnellere Lösung besteht für das letztere Problem.

Alle vorgeschlagenen Lösungen haben eine Laufzeit, die als m*p = len(xy1)*len(xy2) skaliert. Das ist in Ordnung für kleine Datenmengen, aber eine optimale Lösung kann geschrieben werden, die als m*log(p) skaliert und produzieren enorme Einsparungen für großen xy2 Datensätze.

Diese optimale Ausführungszeit Skalierung erreicht werden kann unter Verwendung von scipy .spatial.cKDTree wie folgt

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)

wobei mindist ist der minimale Abstand zwischen jedem Punkt in xy1 und dem Satz von Punkten in 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)