distanza euclidea minima tra i punti in due differenti matrici NumPy, non all'interno

Question

Ho due array di x - y coordinate, e vorrebbe trovare la distanza euclidea minima tra ciascun punto in un array con tutti i punti dell'altra schiera. Gli array non sono necessariamente le stesse dimensioni. Ad esempio:

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

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

Il mio metodo corrente scorre ogni xy coordinata nella xy1 e calcola le distanze tra che coordinare e le altre coordinate.

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

C'è un modo per eliminare il ciclo for e fare in qualche modo calcoli elemento per elemento tra i due array? Immagino generare una matrice di distanza per la quale sono riuscito a trovare l'elemento minimo in ciascuna riga o colonna.

Un altro modo di guardare al problema. Dire che concateno xy1 (lunghezza m ) e xy2 (lunghezza p ) in xy (lunghezza n ), e devo conservare le lunghezze dell'originale array. Teoricamente, devo quindi in grado di generare un n x n matrice distanza da quelle coordinate da cui posso afferrare un m x p sottomatrice. C'è un modo per generare in modo efficiente questa sottomatrice?

Answer 1

(mesi dopo) scipy.spatial.distance.cdist( X, Y ) dà tutte le coppie di distanze, per X e Y 2 dim, 3 dim ...
Si fa anche 22 norme diverse, dettagliato qui .

# 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

Per calcolare il m dalla matrice p delle distanze, questo dovrebbe funzionare:

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

le chiamate .outer fanno due tali matrici (differenze scalari lungo i due assi), le chiamate .hypot trasforma quelli in una matrice stessa forma (delle distanze euclidee scalari).

Answer 3

Per quello che si sta cercando di fare:

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)

Modifica : Invece di chiamare sqrt, facendo piazze, ecc, è possibile utilizzare numpy.hypot:

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

Answer 4

La risposta accettata non affronta pienamente la domanda, che richiede di trovare il minima distanza tra le due serie di punti, non la distanza tra il ogni punto nelle due imposta.

Benche una soluzione semplice alla domanda iniziale infatti consiste nel calcolare la distanza tra ogni coppia e trovare susequently quella minima, questo non è necessario se si è interessati solo a minima distanze. Esiste una soluzione molto veloce per quest'ultimo problema.

Tutte le soluzioni proposte hanno un tempo di esecuzione in grado di scalare come m*p = len(xy1)*len(xy2). Questo va bene per i piccoli insiemi di dati, ma una soluzione ottimale può essere scritta in grado di scalare da m*log(p), producendo enormi risparmi per i grandi insiemi di dati xy2.

Questa scaling ottimale tempo di esecuzione può essere ottenuto utilizzando SciPy .spatial.cKDTree come segue

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)

dove mindist è la distanza minima tra ciascun punto xy1 e l'insieme dei punti 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)