Distance euclidienne minimale entre les points dans deux tableaux Numpy différents, pas à l'intérieur
j'ai deux tableaux de x - y coordonnées, et je voudrais trouver la distance euclidienne minimum entre chaque point dans un tableau avec tous les points dans l'autre tableau. Les tableaux ne sont pas nécessairement de 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 cette coordonnée 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 a-t-il un moyen d'éliminer la boucle for et de faire des calculs élément par élément entre les deux tableaux? J'envisage de générer une matrice de distance pour laquelle je pourrais trouver l'élément minimum dans chaque ligne ou colonne.
une autre façon de voir le problème. Disons que je concaténate xy1 (longueur m ) et xy2 (longueur p ) en xy (longueur n ), et je stocke les longueurs des matrices originales. Théoriquement, je devrais alors être capable de générer une matrice de distance n x n à partir de ces coordonnées à partir desquelles je peux saisir une sous-matrice m x p . Est-il un moyen efficace de générer cette submatrix?
5 réponses
(mois plus tard)
scipy.spatial.distance.cdist( X, Y )
donne toutes les paires de distances,
pour X et Y 2 dim, 3 dim ...
Il fait également 22 normes différentes, détaillées
ici .
# 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
pour calculer la matrice m par 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 de ces matrices (de différences scalaires le long des deux axes), les appels .hypot les transforment en une matrice de même forme (de distances scalaires euclidiennes).
la réponse acceptée ne répond pas entièrement à la question, qui demande de trouver la distance minimum entre les deux ensembles de points, pas la distance entre chaque point dans les deux ensembles.
bien qu'une solution simple à la question initiale consiste en effet à calculer la distance entre chaque paire et de trouver par la suite le minimum un, Ceci n'est pas nécessaire si on n'est intéressé que par les distances minimum . Beaucoup plus rapide solution existe pour ce dernier problème.
toutes les solutions proposées ont une durée de fonctionnement qui s'échelonne comme m*p = len(xy1)*len(xy2) . C'est OK pour les petits ensembles de données, mais une solution optimale peut être écrite que les échelles comme m*log(p) , produisant des économies énormes pour les grands xy2 ensembles de données.
cette échelle de temps d'exécution optimale peut être obtenue 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 de xy2
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)
Edit : au lieu d'appeler sqrt , faire des carrés, etc., vous pouvez utiliser numpy.hypot :
dists = numpy.hypot(xy1[:, 0, numpy.newaxis]-xy2[:, 0], xy1[:, 1, numpy.newaxis]-xy2[:, 1])
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)