유클리드 거리를 Numpy로 어떻게 계산할 수 있습니까?
-
05-07-2019 - |
문제
3D에 두 지점이 있습니다.
(xa, ya, za)
(xb, yb, zb)
그리고 나는 거리를 계산하고 싶습니다 :
dist = sqrt((xa-xb)^2 + (ya-yb)^2 + (za-zb)^2)
Numpy 또는 Python으로 일반적 으로이 작업을 수행하는 가장 좋은 방법은 무엇입니까? 나는 가지고있다:
a = numpy.array((xa ,ya, za))
b = numpy.array((xb, yb, zb))
해결책
dist = numpy.linalg.norm(a-b)
다른 팁
Scipy에는 그 기능이 있습니다. 라고 불린다 유클리드.
예시:
from scipy.spatial import distance
a = (1, 2, 3)
b = (4, 5, 6)
dst = distance.euclidean(a, b)
한 번에 여러 거리를 계산하는 데 관심이있는 사람은 perfplot (내 작은 프로젝트). 그것은 그게 밝혀졌습니다
a_min_b = a - b
numpy.sqrt(numpy.einsum('ij,ij->i', a_min_b, a_min_b))
행의 거리를 계산합니다 a
그리고 b
가장 빠른. 이것은 실제로 단 하나의 행에서도 사실입니다!
플롯을 재현하기위한 코드 :
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)'
)
또 다른 인스턴스 이 문제 해결 방법:
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)
다양한 성능 노트로 간단한 답변을 설명하고 싶습니다. np.linalg.norm은 아마도 필요한 것보다 더 많은 일을 할 것입니다.
dist = numpy.linalg.norm(a-b)
첫째 -이 기능은 목록을 통해 작동하고 모든 값을 반환하도록 설계되었습니다. pA
포인트 세트에 sP
:
sP = set(points)
pA = point
distances = np.linalg.norm(sP - pA, ord=2, axis=1.) # 'distances' is a list
몇 가지를 기억하십시오.
- 파이썬 기능 호출은 비싸다.
- 일반] Python은 이름 조회를 캐시하지 않습니다.
그래서
def distance(pointA, pointB):
dist = np.linalg.norm(pointA - pointB)
return dist
외모만큼 결백하지 않습니다.
>>> 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
첫째 - 우리가 호출 할 때마다 "NP"에 대한 글로벌 조회, "linalg"에 대한 스코프 조회 및 "Norm"에 대한 스코프 조회, 단순한 오버 헤드를 수행해야합니다. 부름 이 기능은 수십 개의 파이썬 지침과 동일시 될 수 있습니다.
마지막으로, 우리는 결과를 저장하고 반품을 위해 다시로드하기 위해 두 개의 작업을 낭비했습니다 ...
개선시 첫 번째 패스 : 조회를 더 빨리 만들고 매장을 건너 뛰십시오.
def distance(pointA, pointB, _norm=np.linalg.norm):
return _norm(pointA - pointB)
우리는 훨씬 더 간소화됩니다.
>>> 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
그러나 함수 호출 오버 헤드는 여전히 일부 작업에 해당합니다. 그리고 수학을 직접 수행 할 수 있는지 여부를 결정하기 위해 벤치 마크를 수행하고 싶을 것입니다.
def distance(pointA, pointB):
return (
((pointA.x - pointB.x) ** 2) +
((pointA.y - pointB.y) ** 2) +
((pointA.z - pointB.z) ** 2)
) ** 0.5 # fast sqrt
일부 플랫폼에서 **0.5
보다 빠릅니다 math.sqrt
. 귀하의 마일리지가 다를 수 있습니다.
**** 고급 성능 노트.
거리를 계산하는 이유는 무엇입니까? 유일한 목적이 그것을 표시하는 것이라면
print("The target is %.2fm away" % (distance(a, b)))
를 따라 이동. 그러나 거리를 비교하거나 범위 검사 등을 비교하는 경우 유용한 성능 관찰을 추가하고 싶습니다.
거리별로 정렬하거나 범위 제약 조건을 충족하는 항목에 목록을 컬링하는 두 가지 경우를 봅시다.
# 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)
우리가 기억해야 할 첫 번째는 우리가 사용하고 있다는 것입니다. 피타고라스 거리를 계산하려면 (dist = sqrt(x^2 + y^2 + z^2)
) 그래서 우리는 많은 것을 만들고 있습니다 sqrt
전화. 수학 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
간단히 말해서 : 실제로 x^2가 아닌 X 단위의 거리가 필요할 때까지 계산의 가장 어려운 부분을 제거 할 수 있습니다.
# 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)
훌륭합니다. 두 기능 모두 비싼 사각형 뿌리를 수행합니다. 훨씬 더 빨라질 것입니다. 또한 발전기로 변환하여 IN_Range를 향상시킬 수 있습니다.
def in_range(origin, range, things):
range_sq = range**2
yield from (thing for thing in things
if distance_sq(origin, thing) <= range_sq)
특히 다음과 같은 작업을 수행하는 경우 특히 이점이 있습니다.
if any(in_range(origin, max_dist, things)):
...
그러나 다음에 할 일이 거리가 필요하다면
for nearby in in_range(origin, walking_distance, hotdog_stands):
print("%s %.2fm" % (nearby.name, distance(origin, nearby)))
튜플 생성 고려 :
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)
이는 범위 검사를 체인 할 수있는 경우 특히 유용 할 수 있습니다 ( '거리를 다시 계산할 필요가 없기 때문에' 'X 근처와 Y의 NM 내에있는 것을 찾으십시오').
그러나 우리가 정말로 큰 목록을 찾고 있다면 things
그리고 우리는 그들 중 많은 사람들이 고려할 가치가 없을 것으로 예상합니까?
실제로 매우 간단한 최적화가 있습니다.
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
이것이 유용한 지 여부는 '사물'의 크기에 따라 다릅니다.
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 ...
그리고 다시, dist_sq를 산출하는 것을 고려하십시오. 우리의 핫도그 예제는 다음과 같습니다.
# 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))
나는 matplotlib.mlab에서 'dist'기능을 찾지 만 충분히 편리하다고 생각하지 않습니다.
참조를 위해 여기에 게시하고 있습니다.
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)
다음과 같이 할 수 있습니다. 나는 그것이 얼마나 빨리 있는지 모르겠지만 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)))
벡터를 빼고 내부 제품 만 빼면됩니다.
당신의 예제에 따라
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)
간단한 코드이며 이해하기 쉽습니다.
좋아요 np.dot
(도트 제품) :
a = numpy.array((xa,ya,za))
b = numpy.array((xb,yb,zb))
distance = (np.dot(a-b,a-b))**.5
was a
그리고 b
정의했듯이 다음을 사용할 수도 있습니다.
distance = np.sqrt(np.sum((a-b)**2))
멋진 원 라이너 :
dist = numpy.linalg.norm(a-b)
그러나 속도가 우려되는 경우 기계 실험을 권장합니다. 나는 그것을 사용했다 math
도서관 sqrt
이랑 **
정사각형의 연산자는 1-liner numpy 솔루션보다 내 기계에서 훨씬 빠릅니다.
이 간단한 프로그램을 사용하여 테스트를 실행했습니다.
#!/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
내 기계에서 math_calc_dist
보다 훨씬 빠르게 실행됩니다 numpy_calc_dist
: 1.5 초 ~ 대 23.5 초.
측정 가능한 차이를 얻으려면 fastest_calc_dist
그리고 math_calc_dist
나는 위로 올라 가야했다 TOTAL_LOCATIONS
그런 다음 6000 fastest_calc_dist
테이크 ~ 50 초 동안 math_calc_dist
테이크 ~ 60 초.
실험 할 수도 있습니다 numpy.sqrt
그리고 numpy.square
둘 다보다 느 렸지만 math
내 컴퓨터의 대안.
내 테스트는 Python 2.6.6으로 실행되었습니다.
파이썬의 목록으로 표시되는 두 가지 점이 주어진 파이썬에서 유클리드 거리에 대한 간결한 코드가 있습니다.
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)
공식을 쉽게 사용할 수 있습니다
distance = np.sqrt(np.sum(np.square(a-b)))
실제로 Δx, Δy 및 Δz의 제곱을 추가하고 결과를 뿌려서 피타고라스의 정리를 사용하여 거리를 계산하는 것 이상입니다.
다차원 공간의 유클리드 거리를 계산하십시오.
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
먼저 두 행렬의 차이를 찾으십시오. 그런 다음 Numpy의 Multiply 명령으로 요소 현명한 곱셈을 적용하십시오. 그 후, 원소 현명한 새로운 매트릭스의 요약을 찾으십시오. 마지막으로, 요약의 제곱근을 찾으십시오.
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