distance euclidienne minimale entre les points dans deux tableaux différents NumPy, pas dans

Question

J'ai deux tableaux de x - y coordonnées, et je voudrais trouver la distance euclidienne minimale entre chaque point dans un tableau avec tous les points dans l'autre tableau. Les tableaux ne sont pas nécessairement la même taille. Par exemple:

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

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

Ma méthode actuelle boucle à travers chaque coordonnée xy dans xy1 et calcule les distances entre les coordonnées que et les autres coordonnées.

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

Y at-il un moyen d'éliminer la boucle et d'une certaine manière de faire des calculs, élément par élément entre les deux tableaux? J'Envision générer une matrice de distance pour laquelle je puisse trouver l'élément minimum dans chaque ligne ou colonne.

Une autre façon de voir le problème. Dire que je concaténer xy1 (longueur m ) et xy2 (longueur p ) dans xy (longueur n ), et je stocke les dimensions de l'original tableaux. En théorie, je puis être capable de générer un n x n matrice de distances à partir de ces coordonnées à partir de laquelle je peux saisir un m x p sous-matrice. Y at-il un moyen de générer efficacement cette sous-matrice?

Answer 1

(Quelques mois plus tard) scipy.spatial.distance.cdist( X, Y ) donne toutes les paires de distances, pour dim, 3 dim ... X et Y 2
Il fait également 22 normes différentes, détaillées .

# 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

Pour calculer la m par la matrice p des distances, cela devrait fonctionner:

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

les appels .outer font deux telles matrices (des différences scalaires le long des deux axes), les appels .hypot transforme ceux dans une matrice de même forme (de distances euclidiennes scalaire).

Answer 3

Pour ce que vous essayez de faire:

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)

Modifier : Au lieu d'appeler sqrt, carrés faisant, etc., vous pouvez utiliser numpy.hypot:

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

Answer 4

La réponse acceptée ne traite pas entièrement la question, qui demande de trouver le minimum distance entre les deux ensembles de points, pas la distance entre tous point dans les deux ensembles.

Altough une solution simple à la question initiale consiste en effet de calculer la distance entre chaque paire et trouver postérieurment le minimum, ce n'est pas nécessaire si l'on est seulement intéressé par le minimum . distances Une solution existe beaucoup plus rapide pour ce dernier problème.

Toutes les solutions proposées ont une durée qui évolue comme m*p = len(xy1)*len(xy2). Ceci est OK pour les petits ensembles de données, mais une solution peut être écrit que les échelles comme m*log(p), produisant d'énormes économies pour les grands ensembles de données xy2.

Cette mise à l'échelle optimale du temps d'exécution peut être réalisée en utilisant scipy .spatial.cKDTree comme suit

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)

où mindist est la distance minimale entre chaque point de xy1 et l'ensemble de points dans 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)