vectors two linalg euclidean dist python numpy euclidean-distance

linalg - euclidean distance two vectors python



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

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

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

def distance(v1,v2): return sum([(x-y)**2 for (x,y) in zip(v1,v2)])**(0.5)

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, encontrar la suma del elemento multiplicado por la nueva matriz. Finalmente, encuentra la raíz cuadrada de la suma.

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

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)

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

Ejemplo:

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

Me gusta np.dot (producto de puntos):

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

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!

Código para reproducir la trama:

import matplotlib import numpy import perfplot from scipy.spatial import distance def linalg_norm(data): a, b = data return numpy.linalg.norm(a-b, axis=1) def sqrt_sum(data): a, b = data return numpy.sqrt(numpy.sum((a-b)**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)'' )

Puedes usar fácilmente la fórmula

distance = np.sqrt(np.sum(np.square(a-b)))

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.

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

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 equipararse a docenas de python instrucciones.

Por último, desperdiciamos dos operaciones para almacenar el resultado y volver a cargarlo para devolver ...

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 hacer mejor las matemáticas usted mismo:

def distance(pointX, pointY): return ( ((pointX.x - pointY.x) ** 2) + ((pointY.y - pointY.y) ** 2) + ((pointZ.z - pointZ.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 avanzado.

¿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 por 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 ningún squareroots caro. 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 calcular la distancia nuevamente).

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

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 de nuevo, considera rendir 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))

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

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.

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

distance = np.sqrt(np.sum((a-b)**2))

Un bonito de una sola línea:

dist = numpy.linalg.norm(a-b)

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 programa:

#!/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 mensurable entre las fastest_calc_dist y math_calc_dist , tuve que aumentar TOTAL_LOCATIONS a 6000. Luego, fastest_calc_dist tarda unos 50 segundos, mientras que math_calc_dist tarda 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.

import math dist = math.hypot(math.hypot(xa-xb, ya-yb), za-zb)

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)