¿Cómo se puede calcular la distancia euclidiana con NumPy?

Tengo dos puntos en 3D:

(xa, ya, za) (xb, yb, zb) 

Y quiero calcular la distancia:

 dist = sqrt((xa-xb)^2 + (ya-yb)^2 + (za-zb)^2) 

¿Cuál es la mejor manera de hacer esto con NumPy, o con Python en general? Yo tengo:

 a = numpy.array((xa ,ya, za)) b = numpy.array((xb, yb, zb)) 

Utilice numpy.linalg.norm :

 dist = numpy.linalg.norm(ab) 

Hay una función para eso en SciPy. Se llama euclidiana .

Ejemplo:

 from scipy.spatial import distance a = (1, 2, 3) b = (4, 5, 6) dst = distance.euclidean(a, b) 

Para cualquier persona interesada en calcular varias distancias a la vez, he hecho una pequeña comparación con perfplot (un pequeño proyecto mío). Resulta que

 a_min_b = a - b numpy.sqrt(numpy.einsum('ij,ij->i', a_min_b, a_min_b)) 

calcula las distancias de las filas en b más rápido. ¡Esto también es válido para una sola fila también!

introduzca la descripción de la imagen aquí


Código para reproducir la ttwig:

 import matplotlib import numpy import perfplot from scipy.spatial import distance def linalg_norm(data): a, b = data return numpy.linalg.norm(ab, axis=1) def sqrt_sum(data): a, b = data return numpy.sqrt(numpy.sum((ab)**2, axis=1)) def scipy_distance(data): a, b = data return list(map(distance.euclidean, a, b)) def mpl_dist(data): a, b = data return list(map(matplotlib.mlab.dist, a, b)) def sqrt_einsum(data): a, b = data a_min_b = a - b return numpy.sqrt(numpy.einsum('ij,ij->i', a_min_b, a_min_b)) perfplot.show( setup=lambda n: numpy.random.rand(2, n, 3), n_range=[2**k for k in range(20)], kernels=[linalg_norm, scipy_distance, mpl_dist, sqrt_sum, sqrt_einsum], logx=True, logy=True, xlabel='len(x), len(y)' ) 

Otro ejemplo de este método de resolución de problemas :

 def dist(x,y): return numpy.sqrt(numpy.sum((xy)**2)) a = numpy.array((xa,ya,za)) b = numpy.array((xb,yb,zb)) dist_a_b = dist(a,b) 

Quiero exponer la respuesta simple con varias notas de rendimiento. np.linalg.norm hará quizás más de lo que necesita:

 dist = numpy.linalg.norm(ab) 

En primer lugar, esta función está diseñada para trabajar sobre una lista y devolver todos los valores, por ejemplo, para comparar la distancia desde pA al conjunto de puntos sP :

 sP = set(points) pA = point distances = np.linalg.norm(sP - pA, ord=2, axis=1.) # 'distances' is a list 

Recuerda varias cosas:

  • Las llamadas a funciones de Python son caras.
  • [Regular] Python no guarda búsquedas de nombres en caché.

Asi que

 def distance(pointA, pointB): dist = np.linalg.norm(pointA - pointB) return dist 

No es tan inocente como parece.

 >>> dis.dis(distance) 2 0 LOAD_GLOBAL 0 (np) 2 LOAD_ATTR 1 (linalg) 4 LOAD_ATTR 2 (norm) 6 LOAD_FAST 0 (pointA) 8 LOAD_FAST 1 (pointB) 10 BINARY_SUBTRACT 12 CALL_FUNCTION 1 14 STORE_FAST 2 (dist) 3 16 LOAD_FAST 2 (dist) 18 RETURN_VALUE 

En primer lugar, cada vez que lo llamemos, tenemos que hacer una búsqueda global de “np”, una búsqueda de ámbito para “linalg” y una búsqueda de ámbito de “norma”, y la sobrecarga de simplemente llamar a la función puede igualar a decenas de python instrucciones.

Por último, desperdiciamos dos operaciones para almacenar el resultado y volver a cargarlo para devolverlo …

Primer paso en la mejora: agilice la búsqueda, salte la tienda

 def distance(pointA, pointB, _norm=np.linalg.norm): return _norm(pointA - pointB) 

Conseguimos el mucho más simplificado:

 >>> dis.dis(distance) 2 0 LOAD_FAST 2 (_norm) 2 LOAD_FAST 0 (pointA) 4 LOAD_FAST 1 (pointB) 6 BINARY_SUBTRACT 8 CALL_FUNCTION 1 10 RETURN_VALUE 

Sin embargo, la sobrecarga de llamadas a funciones todavía implica cierto trabajo. Y querrá hacer puntos de referencia para determinar si podría estar mejor haciendo las matemáticas usted mismo:

 def distance(pointA, pointB): return ( ((pointA.x - pointB.x) ** 2) + ((pointA.y - pointB.y) ** 2) + ((pointA.z - pointB.z) ** 2) ) ** 0.5 # fast sqrt 

En algunas plataformas, **0.5 es más rápido que math.sqrt . Su experiencia puede ser diferente.

**** Notas de rendimiento avanzadas.

¿Por qué estás calculando la distancia? Si el único propósito es mostrarlo,

  print("The target is %.2fm away" % (distance(a, b))) 

superar. Pero si está comparando distancias, haciendo verificaciones de rango, etc., me gustaría agregar algunas observaciones de rendimiento útiles.

Tomemos dos casos: clasificación por distancia o selección de una lista de elementos que cumplan con una restricción de rango.

 # Ultra naive implementations. Hold onto your hat. def sort_things_by_distance(origin, things): return things.sort(key=lambda thing: distance(origin, thing)) def in_range(origin, range, things): things_in_range = [] for thing in things: if distance(origin, thing) <= range: things_in_range.append(thing) 

Lo primero que debemos recordar es que estamos usando Pythagoras para calcular la distancia ( dist = sqrt(x^2 + y^2 + z^2) ) por lo que estamos haciendo muchas llamadas a sqrt . Matemáticas 101:

 dist = root ( x^2 + y^2 + z^2 ) :. dist^2 = x^2 + y^2 + z^2 and sq(N) < sq(M) iff M > N and sq(N) > sq(M) iff N > M and sq(N) = sq(M) iff N == M 

En resumen: hasta que realmente necesitemos la distancia en una unidad de X en lugar de X ^ 2, podemos eliminar la parte más difícil de los cálculos.

 # Still naive, but much faster. def distance_sq(left, right): """ Returns the square of the distance between left and right. """ return ( ((left.x - right.x) ** 2) + ((left.y - right.y) ** 2) + ((left.z - right.z) ** 2) ) def sort_things_by_distance(origin, things): return things.sort(key=lambda thing: distance_sq(origin, thing)) def in_range(origin, range, things): things_in_range = [] # Remember that sqrt(N)**2 == N, so if we square # range, we don't need to root the distances. range_sq = range**2 for thing in things: if distance_sq(origin, thing) <= range_sq: things_in_range.append(thing) 

Genial, ambas funciones ya no hacen ninguna raíz cuadrada cara. Eso será mucho más rápido. También podemos mejorar in_range convirtiéndolo en un generador:

 def in_range(origin, range, things): range_sq = range**2 yield from (thing for thing in things if distance_sq(origin, thing) <= range_sq) 

Esto tiene beneficios especialmente si estás haciendo algo como:

 if any(in_range(origin, max_dist, things)): ... 

Pero si lo siguiente que vas a hacer requiere una distancia,

 for nearby in in_range(origin, walking_distance, hotdog_stands): print("%s %.2fm" % (nearby.name, distance(origin, nearby))) 

considera producir tuplas:

 def in_range_with_dist_sq(origin, range, things): range_sq = range**2 for thing in things: dist_sq = distance_sq(origin, thing) if dist_sq <= range_sq: yield (thing, dist_sq) 

Esto puede ser especialmente útil si puede encadenar controles de rango ('encontrar cosas que estén cerca de X y dentro de Nm de Y', ya que no tiene que volver a calcular la distancia).

Pero, ¿qué sucede si estamos buscando una lista muy grande de things y anticipamos que muchas de ellas no valen la pena?

En realidad hay una optimización muy simple:

 def in_range_all_the_things(origin, range, things): range_sq = range**2 for thing in things: dist_sq = (origin.x - thing.x) ** 2 if dist_sq <= range_sq: dist_sq += (origin.y - thing.y) ** 2 if dist_sq <= range_sq: dist_sq += (origin.z - thing.z) ** 2 if dist_sq <= range_sq: yield thing 

Si esto es útil dependerá del tamaño de las "cosas".

 def in_range_all_the_things(origin, range, things): range_sq = range**2 if len(things) >= 4096: for thing in things: dist_sq = (origin.x - thing.x) ** 2 if dist_sq <= range_sq: dist_sq += (origin.y - thing.y) ** 2 if dist_sq <= range_sq: dist_sq += (origin.z - thing.z) ** 2 if dist_sq <= range_sq: yield thing elif len(things) > 32: for things in things: dist_sq = (origin.x - thing.x) ** 2 if dist_sq <= range_sq: dist_sq += (origin.y - thing.y) ** 2 + (origin.z - thing.z) ** 2 if dist_sq <= range_sq: yield thing else: ... just calculate distance and range-check it ... 

Y una vez más, considere ceder el dist_sq. Nuestro ejemplo de hotdog se convierte entonces en:

 # Chaining generators info = in_range_with_dist_sq(origin, walking_distance, hotdog_stands) info = (stand, dist_sq**0.5 for stand, dist_sq in info) for stand, dist in info: print("%s %.2fm" % (stand, dist)) 

Encuentro una función ‘dist’ en matplotlib.mlab, pero no creo que sea lo suficientemente útil.

Lo estoy publicando aquí solo como referencia.

 import numpy as np import matplotlib as plt a = np.array([1, 2, 3]) b = np.array([2, 3, 4]) # Distance between a and b dis = plt.mlab.dist(a, b) 

Se puede hacer como el siguiente. No sé qué tan rápido es, pero no está usando NumPy.

 from math import sqrt a = (1, 2, 3) # Data point 1 b = (4, 5, 6) # Data point 2 print sqrt(sum( (a - b)**2 for a, b in zip(a, b))) 

Un bonito de una sola línea:

 dist = numpy.linalg.norm(ab) 

Sin embargo, si la velocidad es una preocupación, recomendaría experimentar en su máquina. Descubrí que usar sqrt la biblioteca math con el operador ** para el cuadrado es mucho más rápido en mi máquina que la solución NumPy de una sola línea.

Corrí mis pruebas usando este sencillo progtwig:

 #!/usr/bin/python import math import numpy from random import uniform def fastest_calc_dist(p1,p2): return math.sqrt((p2[0] - p1[0]) ** 2 + (p2[1] - p1[1]) ** 2 + (p2[2] - p1[2]) ** 2) def math_calc_dist(p1,p2): return math.sqrt(math.pow((p2[0] - p1[0]), 2) + math.pow((p2[1] - p1[1]), 2) + math.pow((p2[2] - p1[2]), 2)) def numpy_calc_dist(p1,p2): return numpy.linalg.norm(numpy.array(p1)-numpy.array(p2)) TOTAL_LOCATIONS = 1000 p1 = dict() p2 = dict() for i in range(0, TOTAL_LOCATIONS): p1[i] = (uniform(0,1000),uniform(0,1000),uniform(0,1000)) p2[i] = (uniform(0,1000),uniform(0,1000),uniform(0,1000)) total_dist = 0 for i in range(0, TOTAL_LOCATIONS): for j in range(0, TOTAL_LOCATIONS): dist = fastest_calc_dist(p1[i], p2[j]) #change this line for testing total_dist += dist print total_dist 

En mi máquina, math_calc_dist ejecuta mucho más rápido que numpy_calc_dist : 1.5 segundos contra 23.5 segundos .

Para obtener una diferencia medible entre la función fastest_calc_dist y math_calc_dist , tuve que boost el TOTAL_LOCATIONS a 6000. Luego, fastest_calc_dist tarda unos 50 segundos, mientras que math_calc_dist toma unos 60 segundos .

También puedes experimentar con numpy.sqrt y numpy.square aunque ambos eran más lentos que las alternativas math en mi máquina.

Mis pruebas se ejecutaron con Python 2.6.6.

Solo puedes restar los vectores y luego el producto interno.

Siguiendo tu ejemplo,

 a = numpy.array((xa, ya, za)) b = numpy.array((xb, yb, zb)) tmp = a - b sum_squared = numpy.dot(tmp.T, tmp) result sqrt(sum_squared) 

Es un código simple y es fácil de entender.

Iniciando Python 3.8 , el módulo math proporciona directamente la función dist , que devuelve la distancia euclidiana entre dos puntos (dada como una tupla de coordenadas):

 from python import math dist((1, 2, 6), (-2, 3, 2)) # 5.0990195135927845 

Si estás trabajando con listas en lugar de tuplas:

 dist(tuple([1, 2, 6]), tuple([-2, 3, 2])) 

Teniendo a y b como los definiste, puedes usar también:

 distance = np.sqrt(np.sum((ab)**2)) 

Me gusta np.dot (producto de puntos):

 a = numpy.array((xa,ya,za)) b = numpy.array((xb,yb,zb)) distance = (np.dot(ab,ab))**.5 

Aquí hay un código conciso para la distancia euclidiana en Python, dados dos puntos representados como listas en Python.

 def distance(v1,v2): return sum([(xy)**2 for (x,y) in zip(v1,v2)])**(0.5) 
 import numpy as np from scipy.spatial import distance input_arr = np.array([[0,3,0],[2,0,0],[0,1,3],[0,1,2],[-1,0,1],[1,1,1]]) test_case = np.array([0,0,0]) dst=[] for i in range(0,6): temp = distance.euclidean(test_case,input_arr[i]) dst.append(temp) print(dst) 
 import math dist = math.hypot(math.hypot(xa-xb, ya-yb), za-zb) 

Puedes usar fácilmente la fórmula

 distance = np.sqrt(np.sum(np.square(ab))) 

que en realidad no hace nada más que usar el teorema de Pitágoras para calcular la distancia, agregando los cuadrados de Δx, Δy y Δz y arraigando el resultado.

Calcule la distancia euclidiana para el espacio multidimensional:

  import math x = [1, 2, 6] y = [-2, 3, 2] dist = math.sqrt(sum([(xi-yi)**2 for xi,yi in zip(x, y)])) 5.0990195135927845 

Encuentra la diferencia de dos matrices primero. Luego, aplique la multiplicación inteligente de elementos con el comando multiplicar de numpy. Después de eso, encuentre la sum del elemento multiplicado por la nueva matriz. Finalmente, encuentra la raíz cuadrada de la sum.

 def findEuclideanDistance(a, b): euclidean_distance = a - b euclidean_distance = np.sum(np.multiply(euclidean_distance, euclidean_distance)) euclidean_distance = np.sqrt(euclidean_distance) return euclidean_distance