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

Question

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? Tengo:

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

Answer 1

Use numpy.linalg.norm :

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

Answer 2

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)

Answer 3

Para cualquier persona interesada en calcular varias distancias a la vez, he hecho una pequeña comparación con perfplot ( un pequeño proyecto mio). 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 a y 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)'
    )

Answer 4

Otra instancia de este método de resolución de problemas :

def dist(x,y):   
    return numpy.sqrt(numpy.sum((x-y)**2))

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

Answer 5

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)

Primero: esta función está diseñada para trabajar sobre una lista y devolver todos los valores, p. 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 almacena en caché las búsquedas de nombres.

Entonces

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 llamamos, tenemos que hacer una búsqueda global de " np " ;, una búsqueda de ámbito para " linalg " y una búsqueda en el ámbito de la " norma " ;, y la sobrecarga de simplemente llamar la función puede equipararse a docenas de instrucciones de python.

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

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

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

Obtenemos 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 la llamada de función todavía equivale a algo de trabajo. Y querrá hacer puntos de referencia para determinar si podría ser mejor haciendo los cálculos 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 kilometraje puede variar.

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

muévete. Pero si está comparando distancias, haciendo controles de rango, etc., me gustaría agregar algunas observaciones de rendimiento útiles.

Tomemos dos casos: ordenar por distancia o seleccionar una lista de elementos que cumplan 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 el distancia ( dist = sqrt (x ^ 2 + y ^ 2 + z ^ 2) ) por lo que estamos haciendo muchas llamadas de 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 tienen raíces cuadradas costosas. 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)))

considere ceder 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 las verificaciones de alcance ('encuentre cosas que estén cerca de X y dentro de Nm de Y', ya que no tiene que calcular la distancia nuevamente).

¿Pero qué pasa si estamos buscando una lista realmente grande de cosas y anticipamos que muchas de ellas no valen la pena ser consideradas?

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 nuevamente, considere obtener el dist_sq. Nuestro ejemplo de hot dog se convierte 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))

Answer 6

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

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

Answer 7

Se puede hacer de la siguiente manera. 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)))

Answer 8

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 fácil de entender.

Answer 9

Me gusta np.dot (producto punto):

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

distance = (np.dot(a-b,a-b))**.5

Answer 10

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

from math import dist

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

Answer 11

Teniendo a y b como los definió, también puede usar:

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

Answer 12

Una buena frase:

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 el código sqrt de 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 .

Ejecuté 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 se ejecuta mucho más rápido que numpy_calc_dist : 1.5 segundos versus 23.5 segundos .

Para obtener una diferencia mensurable entre fast_calc_dist y math_calc_dist tuve que subir TOTAL_LOCATIONS a 6000. Luego, fast_calc_dist tarda ~ 50 segundos mientras que math_calc_dist tarda ~ 60 segundos .

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

Mis pruebas se ejecutaron con Python 2.6.6.

Answer 13

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([(x-y)**2 for (x,y) in zip(v1,v2)])**(0.5)

Answer 14

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)

Answer 15

import math

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

Answer 16

Puedes usar fácilmente la fórmula

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

que en realidad no hace más que usar el teorema de Pitágoras para calcular la distancia, agregando los cuadrados de & # 916; x, & # 916; y y & # 916; z y enraizando el resultado.

Answer 17

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

Answer 18

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 suma de la nueva matriz multiplicada por elementos sabios. Finalmente, encuentre la raíz cuadrada de la sumatoria.

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