distancia euclidiana mínima entre puntos en dos matrices NumPy diferentes, no dentro de

Question

Tengo dos conjuntos de x - y coordenadas, y me gustaría encontrar la distancia euclidiana mínima entre los cada punto en una matriz con todos los puntos en la otra matriz. Las matrices no son necesariamente del mismo tamaño. Por ejemplo:

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

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

Mi método actual recorre cada xy coordenadas en xy1 y calcula las distancias entre los que coordinan y las otras coordenadas.

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

¿Hay una manera de eliminar el bucle y de alguna manera hacer cálculos de elemento por elemento entre las dos matrices? I Envision generar una matriz de distancia para que pudiera encontrar el elemento mínimo en cada fila o columna.

Otra forma de ver el problema. Digamos que concatenar xy1 (longitud m ) y xy2 (longitud p ) en xy (longitud n ), y almacenar la longitud del original matrices. En teoría, debería entonces ser capaz de generar un n x n matriz de distancia a partir de esas coordenadas de la que puede agarrar un m x p submatriz. ¿Hay una manera de generar eficientemente esta submatriz?

Answer 1

(meses después) scipy.spatial.distance.cdist( X, Y ) da todos los pares de distancias, para X e Y 2 tenue, tenue 3 ...
También hace 22 normas diferentes, detallado aquí .

# 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

Para calcular el m por matriz de p de las distancias, esto debería funcionar:

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

las llamadas .outer hacen dos de tales matrices (de las diferencias escalares a lo largo de los dos ejes), las llamadas .hypot convierte aquellos en una matriz del mismo de forma (de distancias euclidianas escalares).

Answer 3

Por lo que estamos tratando de hacer:

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)

Editar : En lugar de llamar sqrt, haciendo cuadrados, etc., puede utilizar numpy.hypot:

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

Answer 4

La respuesta aceptada no responde plenamente a la pregunta, que solicita para encontrar el mínimo distancia entre los dos conjuntos de puntos, no la distancia entre cada punto en los dos conjuntos.

Altough una solución sencilla a la pregunta original de hecho consiste en calcular la distancia entre cada par y encontrar susequently el mínimo, esto no es necesario si uno está interesado sólo en el mínimo distancias. Existe una solución mucho más rápido para el último problema.

Todas las soluciones propuestas tienen un tiempo de ejecución que escala como m*p = len(xy1)*len(xy2). Esto está bien para los pequeños conjuntos de datos, pero una solución óptima se puede escribir que escala como m*log(p), produciendo un gran ahorro de grandes conjuntos de datos xy2.

Este escalamiento óptimo tiempo de ejecución se puede lograr utilizando scipy .spatial.cKDTree como sigue

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)

donde mindist es la distancia mínima entre cada punto en xy1 y el conjunto de puntos en 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)