sklearn - euclidean distance two vectors python

Distancia euclídea mínima entre puntos en dos matrices Numpy diferentes, no dentro

Question

Tengo dos matrices de coordenadas x - y , y me gustaría encontrar la distancia euclidiana mínima entre 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 coordenada xy en xy1 y calcula las distancias entre esa coordenada 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 alguna forma de eliminar el bucle for y, de algún modo, hacer cálculos elemento por elemento entre las dos matrices? Me imagino que generaré una matriz de distancia para la cual podría encontrar el elemento mínimo en cada fila o columna.

Otra forma de ver el problema. Supongamos que concateno xy1 (longitud m ) y xy2 (longitud p ) en xy (longitud n ), y xy2 las longitudes de las matrices originales. Teóricamente, debería ser capaz de generar una matriz de distancia nxn a partir de esas coordenadas a partir de las cuales puedo tomar una submatriz mxp . ¿Hay alguna 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 dim, 3 dim ...
También hace 22 normas diferentes, detalladas here .

# 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

La respuesta aceptada no aborda completamente la pregunta, que solicita encontrar la distancia mínima entre los dos conjuntos de puntos, no la distancia entre cada punto en los dos conjuntos.

A pesar de que una solución directa a la pregunta original de hecho consiste en calcular la distancia entre cada par y, por el momento, encontrar el mínimo, esto no es necesario si a uno solo le interesan las distancias mínimas . Existe una solución mucho más rápida para este último problema.

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

Esta escala de tiempo de ejecución óptima se puede lograr utilizando scipy.spatial.cKDTree siguiente manera

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 3

Para calcular la matriz de distancias m por p, 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 de .outer forman dos matrices de este tipo (de las diferencias escalares a lo largo de los dos ejes), las llamadas .hypot convierten en una matriz de la misma forma (de distancias euclídeas escalares).

Answer 4

Por lo que estás 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 a sqrt , hacer cuadrados, etc., puede usar numpy.hypot :

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

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)