Wie kann der euklidische Abstand mit NumPy berechnet werden?

Question

Ich habe zwei Punkte in 3D:

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

Und ich möchte die Entfernung berechnen:

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

Was ist der beste Weg, dies mit NumPy, oder mit Python im Allgemeinen zu tun? Ich habe:

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

Answer 1

使用方法 numpy.linalg.norm :

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

Die Theorie dahinter finden Sie in Einführung in Data Mining

Dies funktioniert, weil die Euklidischer Abstand ist die l2-Norm und der Standardwert der Option ord Parameter in numpy.linalg.norm ist 2.

Answer 2

Dafür gibt es eine Funktion in SciPy. Sie heißt Euklidisch .

例

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

Answer 3

Für alle, die daran interessiert sind, mehrere Entfernungen auf einmal zu berechnen, habe ich einen kleinen Vergleich angestellt Perfplot (ein kleines Projekt von mir).

Der erste Ratschlag ist, Ihre Daten so zu organisieren, dass die Arrays die Dimension (3, n) (und sind natürlich C-zusammenhängend). Wenn das Hinzufügen in der zusammenhängenden ersten Dimension geschieht, geht es schneller, und es macht nicht so viel aus, wenn Sie sqrt-sum mit axis=0 , linalg.norm mit axis=0 , oder

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

die mit knappem Vorsprung die schnellste Variante ist. (Das gilt übrigens auch für nur eine Zeile.)

Die Varianten, bei denen man über die zweite Achse summiert, axis=1 sind alle wesentlich langsamer.

---

Code zur Reproduktion des Plots:

import numpy
import perfplot
from scipy.spatial import distance

def linalg_norm(data):
    a, b = data[0]
    return numpy.linalg.norm(a - b, axis=1)

def linalg_norm_T(data):
    a, b = data[1]
    return numpy.linalg.norm(a - b, axis=0)

def sqrt_sum(data):
    a, b = data[0]
    return numpy.sqrt(numpy.sum((a - b) ** 2, axis=1))

def sqrt_sum_T(data):
    a, b = data[1]
    return numpy.sqrt(numpy.sum((a - b) ** 2, axis=0))

def scipy_distance(data):
    a, b = data[0]
    return list(map(distance.euclidean, a, b))

def sqrt_einsum(data):
    a, b = data[0]
    a_min_b = a - b
    return numpy.sqrt(numpy.einsum("ij,ij->i", a_min_b, a_min_b))

def sqrt_einsum_T(data):
    a, b = data[1]
    a_min_b = a - b
    return numpy.sqrt(numpy.einsum("ij,ij->j", a_min_b, a_min_b))

def setup(n):
    a = numpy.random.rand(n, 3)
    b = numpy.random.rand(n, 3)
    out0 = numpy.array([a, b])
    out1 = numpy.array([a.T, b.T])
    return out0, out1

b = perfplot.bench(
    setup=setup,
    n_range=[2 ** k for k in range(22)],
    kernels=[
        linalg_norm,
        linalg_norm_T,
        scipy_distance,
        sqrt_sum,
        sqrt_sum_T,
        sqrt_einsum,
        sqrt_einsum_T,
    ],
    xlabel="len(x), len(y)",
)
b.save("norm.png")

Answer 4

Ich möchte die einfache Antwort mit verschiedenen Leistungshinweisen erläutern. np.linalg.norm wird vielleicht mehr tun, als Sie brauchen:

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

Erstens: Diese Funktion ist dafür gedacht, eine Liste zu bearbeiten und alle Werte zurückzugeben, z. B. um den Abstand von pA auf die Menge der Punkte sP :

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

Denken Sie an mehrere Dinge:

• Python-Funktionsaufrufe sind teuer.
• [Regular] Python speichert keine Namensaufrufe.

Also

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

ist nicht so unschuldig, wie es aussieht.

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

Erstens müssen wir bei jedem Aufruf global nach "np", scoped nach "linalg" und scoped nach "norm" suchen, und der Overhead von nur aufrufen die Funktion kann Dutzenden von Python-Anweisungen entsprechen.

Schließlich haben wir zwei Operationen verschwendet, um das Ergebnis zu speichern und es für die Rückgabe neu zu laden...

Erster Verbesserungsversuch: Schnelleres Nachschlagen, Überspringen der Speicherung

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

Wir bekommen die weitaus stromlinienförmigere:

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

Der Aufwand für die Funktionsaufrufe ist jedoch immer noch sehr hoch. Und Sie werden Benchmarks durchführen wollen, um festzustellen, ob Sie die Berechnungen besser selbst durchführen sollten:

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

Auf einigen Plattformen, **0.5 ist schneller als math.sqrt . Ihre Erfahrungen können variieren.

**** Leistungshinweise für Fortgeschrittene.

Warum berechnen Sie die Entfernung? Wenn der einzige Zweck darin besteht, sie anzuzeigen,

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

weitergehen. Aber wenn Sie Entfernungen vergleichen, Entfernungsmessungen durchführen usw., möchte ich einige nützliche Leistungsbeobachtungen hinzufügen.

Nehmen wir zwei Fälle: Sortieren nach Abstand oder Einschränkung einer Liste auf Elemente, die eine Bereichsbedingung erfüllen.

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

Das erste, was wir uns merken müssen, ist, dass wir die Pythagoras um die Entfernung zu berechnen ( dist = sqrt(x^2 + y^2 + z^2) ), also machen wir eine Menge von sqrt Anrufe. Mathe 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

Kurz gesagt: Solange wir nicht X^2, sondern die Entfernung in einer Einheit von X benötigen, können wir den schwierigsten Teil der Berechnungen eliminieren.

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

Toll, beide Funktionen machen keine teuren Quadratwurzeln mehr. Das wird viel schneller sein. Wir können auch in_range verbessern, indem wir es in einen Generator umwandeln:

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

Dies ist vor allem dann von Vorteil, wenn Sie etwas tun wie:

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

Aber wenn das, was Sie als Nächstes vorhaben, eine gewisse Entfernung erfordert,

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

ertragreiche Tupel berücksichtigen:

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)

Dies kann besonders nützlich sein, wenn Sie Entfernungsprüfungen verketten ("finde Dinge, die sich in der Nähe von X und innerhalb von Nm von Y befinden", da Sie die Entfernung nicht erneut berechnen müssen).

Aber was ist, wenn wir eine wirklich große Liste von things und wir erwarten, dass viele von ihnen nicht in Frage kommen?

Es gibt eigentlich eine sehr einfache Optimierung:

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

Ob dies sinnvoll ist, hängt von der Größe der "Dinge" ab.

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

Und noch einmal: Betrachten Sie das Ergebnis von dist_sq. Unser Hotdog-Beispiel wird dann:

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

Ein weiterer Fall von diese Problemlösungsmethode :

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)