Como pode a distância euclidiana ser calculado com NumPy?
https://stackoverflow.com/questions/1401712
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu tenho dois pontos em 3D:
(xa, ya, za)
(xb, yb, zb)
E eu quero calcular a distância:
dist = sqrt((xa-xb)^2 + (ya-yb)^2 + (za-zb)^2)
Qual é a melhor maneira de fazer isso com NumPy ou com Python em geral? Eu tenho:
a = numpy.array((xa ,ya, za))
b = numpy.array((xb, yb, zb))
Solução
Use numpy.linalg.norm :
dist = numpy.linalg.norm(a-b)
Outras dicas
Há uma função para que em SciPy. É chamado euclidiana .
Exemplo:
from scipy.spatial import distance
a = (1, 2, 3)
b = (4, 5, 6)
dst = distance.euclidean(a, b)
Para alguém interessado em computação várias distâncias de uma vez, eu fiz um pouco de comparação utilizando perfplot ( um pequeno projeto meu). Acontece que
a_min_b = a - b
numpy.sqrt(numpy.einsum('ij,ij->i', a_min_b, a_min_b))
calcula as distâncias das linhas em a e b mais rápido. Isso realmente é válido para apenas uma linha bem!
Código para reproduzir o enredo:
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)'
)
Outra instância do este método 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)
Eu quero expor sobre a resposta simples com várias notas de desempenho. np.linalg.norm vai fazer talvez mais do que você precisa:
dist = numpy.linalg.norm(a-b)
Em primeiro lugar - esta função é projetado para trabalho sobre uma lista e retornar todos os valores, por exemplo, para comparar a distância de pA para o conjunto de pontos sP:
sP = set(points)
pA = point
distances = np.linalg.norm(sP - pA, ord=2, axis=1.) # 'distances' is a list
Lembre-se várias coisas:
- chamadas de função Python são caros.
- [regular] Python não pesquisas de nome cache.
Assim
def distance(pointA, pointB):
dist = np.linalg.norm(pointA - pointB)
return dist
não é tão inocente quanto 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
Em primeiro lugar - cada vez que chamá-lo, temos que fazer uma pesquisa global para "np", um escopo de pesquisa para "linalg" e uma pesquisa com escopo de "norma", e a sobrecarga de apenas chamando a função pode equivaler a dezenas de instruções python.
Por fim, desperdiçado duas operações para armazenar o resultado e recarregá-lo para o retorno ...
A primeira passagem na melhoria: tornar a pesquisa mais rápido, pular a loja
def distance(pointA, pointB, _norm=np.linalg.norm):
return _norm(pointA - pointB)
Temos a muito mais simplificada:
>>> 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
A chamada de função sobrecarga ainda ascende a cerca de trabalho, no entanto. E você vai querer fazer benchmarks para determinar se você pode estar fazendo melhor a matemática se:
def distance(pointA, pointB):
return (
((pointA.x - pointB.x) ** 2) +
((pointA.y - pointB.y) ** 2) +
((pointA.z - pointB.z) ** 2)
) ** 0.5 # fast sqrt
Em algumas plataformas, **0.5 é mais rápido que math.sqrt. Sua milhagem pode variar.
**** notas de desempenho avançadas.
Por que você está calculando a distância? Se o único objetivo é exibi-lo,
print("The target is %.2fm away" % (distance(a, b)))
move longitudinalmente. Mas se você está comparando distâncias, fazer verificações de intervalo, etc., eu gostaria de acrescentar algumas observações de desempenho útil.
Deixe-nos tomar dois casos:. Classificação por distância ou abate uma lista de itens que atendem a uma restrição gama
# 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)
A primeira coisa que precisamos lembrar é que estamos usando Pitágoras para calcular o distância (dist = sqrt(x^2 + y^2 + z^2)) por isso estamos fazendo um monte de chamadas sqrt. Math 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
Em resumo:. Até que realmente exigem a distância em uma unidade de X em vez de X ^ 2, podemos eliminar a parte mais difícil dos 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)
Grande, ambas as funções não mais fazer quaisquer raízes quadradas caros. Isso vai ser muito mais rápido. Nós também pode melhorar in_range, convertendo-a um gerador:
def in_range(origin, range, things):
range_sq = range**2
yield from (thing for thing in things
if distance_sq(origin, thing) <= range_sq)
Esta especialmente tem benefícios se você está fazendo algo como:
if any(in_range(origin, max_dist, things)):
...
Mas, se a próxima coisa que você vai fazer requer uma distância,
for nearby in in_range(origin, walking_distance, hotdog_stands):
print("%s %.2fm" % (nearby.name, distance(origin, nearby)))
consideram produzindo 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)
Isso pode ser especialmente útil se você pode cheques alcance cadeia ( 'encontrar coisas que estão perto de X e dentro Nm de Y', desde que você não tem que calcular a distância de novo).
Mas o que dizer se estamos procurando realmente um grande lista de things e prevemos que muitos deles não ser digno de consideração?
Há realmente uma otimização muito simples:
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
Se isto é útil vai depender do tamanho de 'coisas'.
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 ...
E, novamente, considere produzindo o dist_sq. Nosso exemplo hotdog, em seguida, torna-se:
# 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))
I encontrar uma função 'dist' em matplotlib.mlab, mas eu não acho que é útil o suficiente.
Estou postando aqui apenas para referência.
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)
Pode ser feito como o seguinte. Eu não sei quão rápido ele é, mas ele não 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)))
Você pode apenas subtrair os vetores e, em seguida, innerproduct.
A seguir o seu exemplo,
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)
É código simples e é fácil de entender.
Gosto np.dot (produto de ponto):
a = numpy.array((xa,ya,za))
b = numpy.array((xb,yb,zb))
distance = (np.dot(a-b,a-b))**.5
Iniciando Python 3.8, o math módulo fornece diretamente o dist função, que retorna a distância euclidiana entre dois pontos (dado como um tuplo de coordenadas):
from math import dist
dist((1, 2, 6), (-2, 3, 2)) # 5.0990195135927845
Se você está trabalhando com listas em vez de tuplas:
dist(tuple([1, 2, 6]), tuple([-2, 3, 2]))
Tendo a e b como você os definiu, você pode usar também:
distance = np.sqrt(np.sum((a-b)**2))
Um one-liner agradável:
dist = numpy.linalg.norm(a-b)
No entanto, se a velocidade é uma preocupação que eu recomendo experimentar em sua máquina. Descobri que usando math da biblioteca sqrt com o operador ** para a praça é muito mais rápido na minha máquina do que a solução NumPy one-liner.
Corri meus testes usando esse programa simples:
#!/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
Na minha máquina, math_calc_dist corre muito mais rápido do que numpy_calc_dist:. 1,5 segundos contra 23,5 segundos
Para obter uma diferença mensurável entre fastest_calc_dist e math_calc_dist eu tinha para se TOTAL_LOCATIONS para 6000. fastest_calc_dist Então toma ~ 50 segundos enquanto math_calc_dist leva ~ 60 segundos .
Você também pode experimentar com numpy.sqrt e numpy.square embora ambos foram mais lentos do que as alternativas math na minha máquina.
Meus testes foram executados com Python 2.6.6.
Aqui está um código conciso para distância Euclidiana em Python dado dois pontos representados como listas em Python.
def distance(v1,v2):
return sum([(x-y)**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)
Você pode facilmente usar a fórmula
distance = np.sqrt(np.sum(np.square(a-b)))
que faz realmente nada mais do que o uso de Pitágoras Teorema para calcular a distância, adicionando as praças de Ax, Ay e Az e torcendo o resultado.
Calcular a distância euclidiana para o espaço 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
Encontre diferença de duas matrizes em primeiro lugar. Em seguida, aplique elemento multiplicação sábio com o comando multiplicam de numpy. Depois, em seguida, encontrar somatório do elemento sábio multiplicado nova matriz. Finalmente, encontrar a raiz quadrada da soma.
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
