Jak można obliczyć odległość euklidesową za pomocą NumPy?

Jest do tego funkcja w SciPy. Nazywa się Euklidesowym .

Przykład:

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

Dla wszystkich zainteresowanych obliczaniem wielu odległości naraz, zrobiłem małe porównanie za pomocą perfplot (mój mały projekt). Okazuje się, że

a_min_b = a - b
numpy.sqrt(numpy.einsum('ij,ij->i', a_min_b, a_min_b))

Oblicza odległości wierszy w a i b. Dotyczy to również tylko jednego rzędu!

Kod do odtworzenia fabuły:

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

Kolejna instancja tej metody rozwiązywania problemów :

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)

Chcę wyjaśnić prostą odpowiedź z różnymi notatkami wydajności. np.linalg.norm zrobi może więcej niż potrzebujesz:

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

Po pierwsze-funkcja ta jest przeznaczona do pracy nad listą i zwraca wszystkie wartości, np. aby porównać odległość od pA do zbioru punktów sP:

sP = set(points)
pA = point
distances = np.linalg.norm(sP - pA, ord=2, axis=1.)  # 'distances' is a list

Zapamiętaj kilka rzeczy:

• wywołania funkcji Pythona są drogie.
• [Regular] Python nie buforuje nazwy Szukaj.

Więc

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

Po pierwsze-za każdym razem, gdy ją wywołujemy, musimy wykonać globalne wyszukiwanie dla "np", wyszukiwanie dla" linalg "i wyszukiwanie dla" norm", a koszt wywołania funkcji może być równy dziesiątkom instrukcji Pythona.

Na koniec zmarnowaliśmy dwie operacje, aby zapisać wynik i ponownie załadować go do zwrotu...

Pierwszy pass przy ulepszeniu: make the lookup faster, skip the store

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

Dostajemy znacznie bardziej usprawnione:

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

Wywołanie funkcji narzut wciąż wymaga trochę pracy. I będziesz chciał zrobić benchmarki, aby określić, czy lepiej będzie samemu robić matematykę: {]}

def distance(pointX, pointY):
    return (
        ((pointX.x - pointY.x) ** 2) +
        ((pointY.y - pointY.y) ** 2) +
        ((pointZ.z - pointZ.z) ** 2)
    ) ** 0.5  # fast sqrt

**** zaawansowane notatki o wydajności.

Dlaczego obliczasz odległość? Jeśli jedynym celem jest wyświetlanie it,

 print("The target is %.2fm away" % (distance(a, b)))

Rusz się. Ale jeśli porównujesz odległości, sprawdzasz zasięg itp. Chciałbym dodać kilka przydatnych obserwacji wydajności.

Weźmy dwa przypadki: sortowanie według odległości lub sortowanie listy do elementów spełniających ograniczenie zakresu.

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

Pierwszą rzeczą, którą musimy pamiętać, jest to, że używamy Pitagorasa do obliczenia odległości (dist = sqrt(x^2 + y^2 + z^2)), więc wykonujemy wiele sqrt połączeń. Matematyka 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

W skrócie: dopóki faktycznie wymagamy odległości w jednostce X zamiast x^2, możemy wyeliminować najtrudniejszą część obliczeń.

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

def in_range(origin, range, things):
    range_sq = range**2
    yield from (thing for thing in things
                if distance_sq(origin, thing) <= range_sq)

To szczególnie ma korzyści, jeśli robisz coś takiego:

if any(in_range(origin, max_dist, things)):
    ...

Ale jeśli następna rzecz, którą zamierzasz zrobić, wymaga dystansu,

for nearby in in_range(origin, walking_distance, hotdog_stands):
    print("%s %.2fm" % (nearby.name, distance(origin, nearby)))

Rozważmy poddanie krotki:

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)

Może to być szczególnie przydatne, jeśli możesz sprawdzić zasięg łańcucha ("Znajdź rzeczy, które są blisko X i w Nm od Y", ponieważ nie musisz ponownie obliczać odległości).

Ale co jeśli szukamy naprawdę dużej listy things i przewidujemy, że wiele z nich nie będzie wartych rozważenia?

Istnieje naprawdę bardzo prosta optymalizacja:

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

To, czy jest to użyteczne, zależy od wielkości "rzeczy".

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

I jeszcze raz rozważmy otrzymanie dist_sq. Nasz przykład hotdoga staje się wtedy:

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

Znajduję funkcję 'dist' w matplotlib.mlab, ale nie sądzę, żeby był wystarczająco poręczny.

Zamieszczam go tutaj tylko w celach informacyjnych.

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)

Można to zrobić w następujący sposób. Nie wiem jak szybko, ale nie używa 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)))

Mając a i b Jak je zdefiniowałeś, możesz również użyć:

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

Ładny jeden-liner:

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

Jednakże, jeśli chodzi o prędkość, polecam eksperymentowanie na Twojej maszynie. Odkryłem, że użycie math biblioteki sqrt z ** operatorem kwadratu jest znacznie szybsze na mojej maszynie niż jednoliniowe rozwiązanie NumPy.

Przeprowadziłem testy używając tego prostego programu:

#!/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 mojej maszynie, math_calc_dist działa znacznie szybciej niż numpy_calc_dist: 1.5 sekundy kontra 23,5 sekundy .

Aby uzyskać mierzalny różnica między fastest_calc_dist i math_calc_dist musiałem zwiększyć TOTAL_LOCATIONS do 6000. Następnie fastest_calc_dist trwa ~50 sekund podczas math_calc_dist trwa ~60 sekund.

Możesz również eksperymentować z numpy.sqrt i numpy.square choć oba były wolniejsze niż math alternatywy na mojej maszynie.

Moje testy były uruchamiane z Pythonem 2.6.6.

Można po prostu odjąć wektory, a następnie innerproduct.

Idąc za twoim przykładem,

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)

Jest to prosty kod i jest łatwy do zrozumienia.

Lubię np.kropka (produkt dot):

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

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

Oto zwięzły kod dla odległości euklidesowej w Pythonie z dwoma punktami reprezentowanymi jako listy w Pythonie.

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)

Możesz łatwo użyć formuły

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

, który w rzeczywistości nie robi nic więcej, jak użycie twierdzenia Pitagorasa do obliczenia odległości, dodając kwadraty Δx, Δy i Δz i ukorzeniając wynik.

import math

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

Jeśli chcesz znaleźć odległość określonego punktu od pierwszego ze skurczów, możesz użyć, plus możesz to zrobić z dowolną liczbą wymiarów.

import numpy as np

A = [3,4]
Dis = np.sqrt(A[0]**2 + A[1]**2)

Oblicz odległość euklidesową dla przestrzeni wielowymiarowej:

 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

Najpierw Znajdź różnicę dwóch macierzy. Następnie zastosuj mnożenie elementów za pomocą polecenia mnożenia numpy ' ego. Następnie znajdź sumowanie pierwiastka wise ' a pomnożone przez nową macierz. Na koniec znajdź pierwiastek kwadratowy sumowania.

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