Cálculo eficiente de una matriz de distancia euclidiana usando Numpy

Estate atento porque en esta crónica hallarás el resultado que buscas.Este post fue analizado por nuestros especialistas para asegurar la calidad y veracidad de nuestro contenido.

Solución:

Puedes aprovechar la complex escribe :

# build a complex array of your cells
z = np.array([complex(c.m_x, c.m_y) for c in cells])

Primera solución

# mesh this array so that you will have all combinations
m, n = np.meshgrid(z, z)
# get the distance via the norm
out = abs(m-n)

Segunda solución

La malla es la idea principal. Pero numpy es inteligente, por lo que no tiene que generar m & n. Simplemente calcule la diferencia usando una versión transpuesta de z. La malla se hace automáticamente:

out = abs(z[..., np.newaxis] - z)

Tercera solución

Y si z se establece directamente como un bidimensional arraypuedes usar z.T en lugar de lo raro z[..., np.newaxis]. Entonces, finalmente, su código se verá así:

z = np.array([[complex(c.m_x, c.m_y) for c in cells]]) # notice the [[ ... ]]
out = abs(z.T-z)

Ejemplo

>>> z = np.array([[0.+0.j, 2.+1.j, -1.+4.j]])
>>> abs(z.T-z)
array([[ 0.        ,  2.23606798,  4.12310563],
       [ 2.23606798,  0.        ,  4.24264069],
       [ 4.12310563,  4.24264069,  0.        ]])

Como complemento, es posible que desee eliminar los duplicados después, tomando el triángulo superior:

>>> np.triu(out)
array([[ 0.        ,  2.23606798,  4.12310563],
       [ 0.        ,  0.        ,  4.24264069],
       [ 0.        ,  0.        ,  0.        ]])

Algunos puntos de referencia

>>> timeit.timeit('abs(z.T-z)', setup='import numpy as np;z = np.array([[0.+0.j, 2.+1.j, -1.+4.j]])')
4.645645342274779
>>> timeit.timeit('abs(z[..., np.newaxis] - z)', setup='import numpy as np;z = np.array([0.+0.j, 2.+1.j, -1.+4.j])')
5.049334864854522
>>> timeit.timeit('m, n = np.meshgrid(z, z); abs(m-n)', setup='import numpy as np;z = np.array([0.+0.j, 2.+1.j, -1.+4.j])')
22.489568296184686

Si no necesita la matriz de distancia completa, será mejor que use kd-tree. Considerar scipy.spatial.cKDTree o sklearn.neighbors.KDTree. Esto se debe a que un kd-tree puede encontrar k-vecinos más cercanos en el tiempo O (n log n) y, por lo tanto, evita la complejidad O (n ** 2) de calcular todas las distancias n por n.

Así es como puedes hacerlo usando numpy:

import numpy as np

x = np.array([0,1,2])
y = np.array([2,4,6])

# take advantage of broadcasting, to make a 2dim array of diffs
dx = x[..., np.newaxis] - x[np.newaxis, ...]
dy = y[..., np.newaxis] - y[np.newaxis, ...]
dx
=> array([[ 0, -1, -2],
          [ 1,  0, -1],
          [ 2,  1,  0]])

# stack in one array, to speed up calculations
d = np.array([dx,dy])
d.shape
=> (2, 3, 3)

Ahora todo lo que queda es calcular la norma L2 a lo largo del eje 0 (como se explica aquí):

(d**2).sum(axis=0)**0.5
=> array([[ 0.        ,  2.23606798,  4.47213595],
          [ 2.23606798,  0.        ,  2.23606798],
          [ 4.47213595,  2.23606798,  0.        ]])

Al final de la artículo puedes encontrar las interpretaciones de otros creadores, tú además tienes la habilidad dejar el tuyo si lo crees conveniente.

---

---

Utiliza Nuestro Buscador