Euclidiana mínima distância entre os pontos em duas matrizes Numpy diferentes, não dentro

Question

Eu tenho duas matrizes de x - y coordenadas, e eu gostaria de saber a distância euclidiana mínima entre cada ponto em um único storage com todas os pontos em outro array. As matrizes não são necessariamente do mesmo tamanho. Por exemplo:

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

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

Meu método atual percorre cada xy coordenar em xy1 e calcula as distâncias entre que coordenam e as outras 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()

Existe uma maneira de eliminar o loop e de alguma forma fazer cálculos elemento por elemento entre as duas matrizes? I prevemos gerar uma matriz de distâncias para os quais I pode encontrar o elemento mínimo em cada linha ou coluna.

Outra maneira de olhar para o problema. Diga eu concatenar xy1 (comprimento m ) e xy2 (comprimento p ) em xy (comprimento n ), e que armazena os comprimentos do original matrizes. Teoricamente, deveria, então, ser capaz de gerar um n x n matriz de distância a partir dessas coordenadas de onde eu posso pegar um m x p submatrix. Existe uma maneira de gerar de forma eficiente este submatrix?

Answer 1

(Meses mais tarde) scipy.spatial.distance.cdist( X, Y ) dá a todos os pares de distâncias, para X e Y 2 dim, dim 3 ...
Ele também faz 22 normas diferentes, detalhou aqui .

# 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 a m por p matriz de distâncias, isso deve 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)

as chamadas .outer fazer duas tais matrizes (de diferenças escalares ao longo dos dois eixos), as chamadas .hypot transforma aqueles em uma matriz do mesmo formato (de distâncias euclideanos escalares).

Answer 3

Para o que você está tentando fazer:

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 : Em vez de chamar sqrt, fazendo praças, etc., você pode usar numpy.hypot:

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

Answer 4

A resposta aceita não resolver completamente a questão, que os pedidos de encontrar o mínimo distância entre os dois conjuntos de pontos, e não a distância entre todas ponto nos dois conjuntos.

Altough uma solução simples para a pergunta original na verdade consiste em calcular a distância entre todas par e susequently encontrar o mínimo, isso não é necessário se alguém está interessado apenas no mínima distâncias. Existe uma solução muito mais rápida para o último problema.

Todas as soluções propostas têm um tempo de execução que escalas como m*p = len(xy1)*len(xy2). Este é OK para pequenos conjuntos de dados, mas uma solução ótima pode ser escrito que escalas como m*log(p), produzindo uma enorme economia para grandes conjuntos de dados xy2.

Esta escala de tempo de execução ideal pode ser alcançado usando scipy .spatial.cKDTree como 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)

onde mindist é a distância mínima entre cada ponto em xy1 eo conjunto de pontos em 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)