Come si può calcolare la distanza euclidea con NumPy?

Question

Ho due punti in 3D:

(xa, ya, za)
(xb, yb, zb)

E voglio calcolare la distanza:

dist = sqrt((xa-xb)^2 + (ya-yb)^2 + (za-zb)^2)

Qual è il modo migliore per farlo con NumPy o con Python in generale? Ho:

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

Answer 1

Usa numpy.linalg.norm :

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

Answer 2

C'è una funzione per questo in SciPy. Si chiama Euclidean .

Esempio:

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

Answer 3

Per chiunque sia interessato a calcolare più distanze contemporaneamente, ho fatto un piccolo confronto usando perfplot ( un mio piccolo progetto). Si scopre che

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

calcola le distanze delle righe in a e b più velocemente. Questo è vero anche per una sola riga!

---

Codice per riprodurre 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

Un'altra istanza di questo metodo di risoluzione dei problemi :

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

Voglio spiegare la semplice risposta con varie note di performance. np.linalg.norm farà forse più del necessario:

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

Innanzitutto, questa funzione è progettata per funzionare su un elenco e restituire tutti i valori, ad es. per confrontare la distanza da pA all'insieme di punti sP :

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

Ricorda diverse cose:

• Le chiamate alle funzioni Python sono costose.
• [Regular] Python non memorizza nella cache le ricerche dei nomi.

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

non è così innocente come sembra.

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

In primo luogo - ogni volta che lo chiamiamo, dobbiamo fare una ricerca globale per "quot" np ", una ricerca mirata per" linalg " e una ricerca mirata per "norma", e il sovraccarico della semplice chiamata la funzione può equivalere a dozzine di istruzioni di Python.

Infine, abbiamo sprecato due operazioni per memorizzare il risultato e ricaricarlo per il ritorno ...

Primo passaggio al miglioramento: velocizza la ricerca, salta il negozio

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

Siamo molto più snelli:

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

Tuttavia, l'overhead della chiamata di funzione equivale ancora a qualche lavoro. E vorrai fare dei benchmark per determinare se potresti fare meglio la matematica da solo:

def distance(pointA, pointB):
    return (
        ((pointA.x - pointB.x) ** 2) +
        ((pointA.y - pointB.y) ** 2) +
        ((pointA.z - pointB.z) ** 2)
    ) ** 0.5  # fast sqrt

Su alcune piattaforme, ** 0,5 è più veloce di math.sqrt . Il chilometraggio può variare.

**** Note sulle prestazioni avanzate.

Perché stai calcolando la distanza? Se l'unico scopo è visualizzarlo,

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

muoviti. Ma se si confrontano le distanze, si eseguono controlli di portata, ecc., Vorrei aggiungere alcune utili osservazioni sulle prestazioni.

Prendiamo due casi: ordinamento per distanza o abbattimento di un elenco per gli elementi che soddisfano un vincolo di intervallo.

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

La prima cosa che dobbiamo ricordare è che stiamo usando Pythagoras per calcolare il distance ( dist = sqrt (x ^ 2 + y ^ 2 + z ^ 2) ), quindi stiamo effettuando molte chiamate sqrt . Matematica 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

In breve: fino a quando non richiederemo effettivamente la distanza in un'unità di X anziché X ^ 2, possiamo eliminare la parte più difficile dei calcoli.

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

Fantastico, entrambe le funzioni non fanno più costose radici quadrate. Sarà molto più veloce. Possiamo anche migliorare in_range convertendolo in un generatore:

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

Ciò ha in particolare dei vantaggi se stai facendo qualcosa del tipo:

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

Ma se la prossima cosa che farai richiede una distanza,

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

considera di produrre tuple:

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)

Questo può essere particolarmente utile se potessi controllare a catena l'intervallo ("trova cose vicine a X e entro Nm di Y", poiché non devi calcolare di nuovo la distanza).

Ma cosa succede se stiamo cercando un elenco davvero grande di cose e prevediamo che molti di loro non varranno la pena di essere presi in considerazione?

In realtà esiste un'ottimizzazione molto semplice:

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 questo è utile dipenderà dalla dimensione delle "cose".

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 ancora, considera di cedere dist_sq. Il nostro esempio di hot dog diventa quindi:

# 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

Trovo una funzione 'dist' in matplotlib.mlab, ma non credo sia abbastanza utile.

Lo sto pubblicando qui solo come riferimento.

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

Può essere fatto come il seguente. Non so quanto sia veloce, ma non utilizza 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

Puoi semplicemente sottrarre i vettori e quindi il prodotto interno.

Seguendo il tuo esempio,

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)

È un codice semplice ed è facile da capire.

Answer 9

Mi piace np.dot (punto prodotto):

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

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

Answer 10

A partire da Python 3.8 , la math fornisce direttamente il dist , che restituisce la distanza euclidea tra due punti (indicata come una tupla di coordinate):

from math import dist

dist((1, 2, 6), (-2, 3, 2)) # 5.0990195135927845

Se stai lavorando con elenchi anziché tuple:

dist(tuple([1, 2, 6]), tuple([-2, 3, 2]))

Answer 11

Avendo a e b come li hai definiti, puoi usare anche:

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

Answer 12

Un bel one-liner:

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

Tuttavia, se la velocità è un problema, consiglierei di sperimentare sulla tua macchina. Ho scoperto che l'utilizzo del math della libreria sqrt con l'operatore ** per il quadrato è molto più veloce sulla mia macchina rispetto alla soluzione NumPy a una riga .

Ho eseguito i miei test usando questo semplice programma:

#!/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

Sulla mia macchina, math_calc_dist funziona molto più velocemente di numpy_calc_dist : 1,5 secondi contro 23,5 secondi .

Per ottenere una differenza misurabile tra fast_calc_dist e math_calc_dist ho dovuto impostare TOTAL_LOCATIONS su 6000. Quindi fast_calc_dist richiede ~ 50 secondi mentre math_calc_dist richiede ~ 60 secondi .

Puoi anche sperimentare numpy.sqrt e numpy.square sebbene entrambi fossero più lenti delle alternative math sulla mia macchina.

I miei test sono stati eseguiti con Python 2.6.6.

Answer 13

Ecco un codice conciso per la distanza euclidea in Python dato due punti rappresentati come liste in 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

Puoi facilmente usare la formula

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

che in realtà non fa altro che usare il teorema di Pitagora per calcolare la distanza, aggiungendo i quadrati di & # 916; x, & # 916; ye & # 916; z e facendo il root del risultato.

Answer 17

Calcola la distanza euclidea per lo spazio multidimensionale:

 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

Trova prima la differenza di due matrici. Quindi, applica la moltiplicazione degli elementi con il comando moltiplica di numpy. Dopo, trova la somma dell'elemento saggia moltiplicata per la nuova matrice. Infine, trova la radice quadrata della sommatoria.

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