Effiziente und genaue Berechnung der euklidischen Distanz

Folgenden einige online-Forschung (Eins, Zwei, numpy, scipy, scikit, Mathematik), ich habe Wege gefunden, das für die Berechnung der euklidische Distanz in Python:

# 1
numpy.linalg.norm(a-b)

# 2
distance.euclidean(vector1, vector2)

# 3
sklearn.metrics.pairwise.euclidean_distances  

# 4
sqrt((xa-xb)^2 + (ya-yb)^2 + (za-zb)^2)

# 5
dist = [(a - b)**2 for a, b in zip(vector1, vector2)]
dist = math.sqrt(sum(dist))

# 6
math.hypot(x, y)

Ich Frage mich, wenn jemand könnte einen Einblick, auf welche der oben genannten (oder jede andere, die ich noch nicht gefunden) gilt als das beste in Bezug auf Effizienz und Präzision. Wenn jemand Kenntnis über Ressource(N), der diskutiert, das Thema, das wäre auch toll.

Den Kontext ich bin interessant ist bei der Berechnung der euklidischen Distanz zwischen Paaren von Anzahl-Tupel, z.B. der Abstand zwischen (52, 106, 35, 12) und (33, 153, 75, 10).

Vergessen Sie nicht, den integrierten math.hypot(). Können Sie leicht testen Sie die Geschwindigkeit mit der timeit - Modul.
Toller Vorschlag, hatte keine Ahnung, dass so eine integrierte Methode existiert! (bearbeitet meine Frage, es aufzunehmen)
Mögliche Einschränkung mit math.hypot() ist, dass es macht nur 2D-Vektoren, in der Erwägung, dass viele der anderen, die Sie erwähnen, behandeln können Vektoren von 3 oder mehr Dimensionen. Auf der anderen Seite, wenn alles, was Sie tun, ist 2D, die nicht-generalisierte gebaut-vielleicht haben Sie einen speed-Vorteil.
Interessant VORBEHALT, obwohl es für meinen Fall kann es ideal sein. Möglicherweise naive Frage: bei der Berechnung der euklidischen Distanz zwischen (52, 106, 35, 12) und (33, 153, 75, 10) sind die zwei 4D-Vektoren??
Alles hängt davon ab, wie man Sie zu interpretieren in das Programm. Konnte zwei 4D-Vektoren oder vier 2D-Vektoren...der ehemalige scheint wahrscheinlich — ich kann nicht sagen, aus deinem Beispiel-code.
Nun, alles, was mich interessiert ist der Vergleich der euklidischen Distanz der x1 mit y1, x2 mit y2 etc., wo (x1, x2, x3, x4) und (y1, y2, y3, y4). Und ich kann mehr als 4 Werte auf den Tupeln. Könnten Sie mir bitte helfen zu verstehen, was Art von dimension, Vektoren, die ich brauche?
Gute news, das was du beschrieben hast sind drei 2D-Vektoren zwischen den 4 Punkten, die math.hypot() und Griff in Ordnung.
Nicht du meinst zwei 2D-Vektoren zwischen den 4 Punkten?
Nein, ich meinte den drei 2D-Vektoren definiert, die von den Paaren von Endpunkten zwischen (52,33) und (106,153), (106,153) und (35,75), plus (35,75) und (12,10). Vielleicht sollten Sie Bearbeiten Ihre Frage und zeigen die gewünschten Ergebnisse.

InformationsquelleAutor | 2016-06-13

11

Fazit zuerst:

Vom test-Ergebnis mit timeit für Effizienz-test, können wir schließen, dass in Bezug auf die Effizienz:

Method5 (zip, math.sqrt) > Method1 (numpy.linalg.norm) > Method2 (scipy.spatial.distance) > Method3 (sklearn.metrics.pairwise.euclidean_distances )

Während ich nicht wirklich testen Sie Ihre Method4 wie es ist nicht geeignet für Allgemeine Fälle und es ist im Allgemeinen äquivalent zu Method5.

Für den rest, ganz überraschend, Method5 ist das Schnellste. Während für Method1 verwendet numpy als das, was wir erwartet haben, die stark optimiert in C, ist die zweite Schnellste.

Für scipy.spatial.distance, wenn Sie gehen direkt auf die definition der Funktion, werden Sie sehen, dass es tatsächlich mit numpy.linalg.norm, außer es wird die Validierung auf die beiden input-Vektoren vor der eigentlichen numpy.linalg.norm. Deswegen ist es etwas langsamer thant numpy.linalg.norm.

Schließlich für sklearn, laut der Dokumentation:

Diese Formulierung hat zwei Vorteile gegenüber anderen Arten von computing-Entfernungen. Erstens, es ist rechnerisch effizienten Umgang mit sparse-data. Zweitens, wenn ein argument variiert, die andere aber unverändert bleibt, dann Punkt(x, x) und/oder dot(y, y) kann im Voraus berechnet.
Dies ist jedoch nicht die Genaueste Methode, dies zu tun Berechnung, und die Distanz-matrix von dieser Funktion zurückgegeben wird, kann nicht genau symmetrisch als erforderlich

Da in Ihrer Frage, die Sie verwenden möchten, um einen festen Satz von Daten, der Vorteil dieser Implementierung ist, nicht reflektiert. Und aufgrund der trade-off zwischen der Leistung und Präzision, es gibt auch die schlechteste Präzision zwischen den Methoden.

Hinsichtlich der Genauigkeit, Method5=Metho1=Method2>Method3

Effizienz-Test-Skript:
```
import numpy as np
from scipy.spatial import distance
from sklearn.metrics.pairwise import euclidean_distances
import math

# 1
def eudis1(v1, v2):
    return np.linalg.norm(v1-v2)

# 2
def eudis2(v1, v2):
    return distance.euclidean(v1, v2)

# 3
def eudis3(v1, v2):
    return euclidean_distances(v1, v2)

# 5
def eudis5(v1, v2):
    dist = [(a - b)**2 for a, b in zip(v1, v2)]
    dist = math.sqrt(sum(dist))
    return dist

dis1 = (52, 106, 35, 12)
dis2 = (33, 153, 75, 10)
v1, v2 = np.array(dis1), np.array(dis2)

import timeit

def wrapper(func, *args, **kwargs):
    def wrapped():
        return func(*args, **kwargs)
    return wrapped

wrappered1 = wrapper(eudis1, v1, v2)
wrappered2 = wrapper(eudis2, v1, v2)
wrappered3 = wrapper(eudis3, v1, v2)
wrappered5 = wrapper(eudis5, v1, v2)
t1 = timeit.repeat(wrappered1, repeat=3, number=100000)
t2 = timeit.repeat(wrappered2, repeat=3, number=100000)
t3 = timeit.repeat(wrappered3, repeat=3, number=100000)
t5 = timeit.repeat(wrappered5, repeat=3, number=100000)

print('\n')
print('t1: ', sum(t1)/len(t1))
print('t2: ', sum(t2)/len(t2))
print('t3: ', sum(t3)/len(t3))
print('t5: ', sum(t5)/len(t5))
```
Effizienz-Test-Ausgabe:
```
t1:  0.654838958307
t2:  1.53977598714
t3:  6.7898791732
t5:  0.422228400305
```
Präzisions-mess-Skript & Ergebnis:
```
In [8]: eudis1(v1,v2)
Out[8]: 64.60650122085238

In [9]: eudis2(v1,v2)
Out[9]: 64.60650122085238

In [10]: eudis3(v1,v2)
Out[10]: array([[ 64.60650122]])

In [11]: eudis5(v1,v2)
Out[11]: 64.60650122085238
```
- Bitte fügen Sie den built-in math.hypot(). (Die OP ist mit Python 3, BTW).
- Tolle Sachen! Wie @martineau schlägt, wenn man könnte hinzufügen, die gebaut-in math.hypot() das wäre erstaunlich. Vor allem, da ich bisher noch nie verwendet habe/davon gehört.
InformationsquelleAutor MaThMaX
1

Dies ist nicht genau die Frage zu beantworten, aber es ist wohl erwähnenswert, dass, wenn Sie nicht daran interessiert sind, die tatsächliche euklidische Distanz, sondern wollen einfach nur, um zu vergleichen euklidischen Entfernungen gegen einander, Quadratwurzeln sind monotone Funktionen, d.h. x**(1/2) < y**(1/2) wenn und nur wenn x < y.

Also, wenn Sie nicht wollen, dass die explizite Entfernung, sondern zum Beispiel einfach nur wissen wollen, ob der euklidische Abstand von vector1 ist näher an eine Liste von Vektoren, genannt vectorlist, können Sie vermeiden, die teuer sind (sowohl in Bezug auf Präzision und Zeit) square root, aber können Sie mit so etwas wie

min(vectorlist, key = lambda compare: sum([(a - b)**2 for a, b in zip(vector1, compare)])

InformationsquelleAutor Tarje Bargheer

Als Allgemeine Faustregel gilt, halten Sie sich an die scipy und numpy Implementierungen, wo möglich, als Sie sind vektorisiert und viel schneller als native Python-code. (Hauptgründe sind: Implementierungen in C, Vektorisierung eliminiert Typ-Prüfung overhead-looping macht.)

(Beiseite: Meine Antwort nicht gerade präzise, aber ich denke, das gleiche Prinzip gilt für die Genauigkeit wie für die Effizienz.)

Als ein bisschen von einem bonus, ich werde chip-in mit ein wenig Informationen darüber, wie Sie Profil-Ihr code, um zu Messen, Effizienz. Wenn Sie die IPython interpreter, das Geheimnis ist die Verwendung der %prun line magic.

In [1]: import numpy

In [2]: from scipy.spatial import distance

In [3]: c1 = numpy.array((52, 106, 35, 12))

In [4]: c2 = numpy.array((33, 153, 75, 10))

In [5]: %prun distance.euclidean(c1, c2)
         35 function calls in 0.000 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 {built-in method builtins.exec}
        1    0.000    0.000    0.000    0.000 linalg.py:1976(norm)
        1    0.000    0.000    0.000    0.000 {built-in method numpy.core.multiarray.dot}
        6    0.000    0.000    0.000    0.000 {built-in method numpy.core.multiarray.array}
        4    0.000    0.000    0.000    0.000 numeric.py:406(asarray)
        1    0.000    0.000    0.000    0.000 distance.py:232(euclidean)
        2    0.000    0.000    0.000    0.000 distance.py:152(_validate_vector)
        2    0.000    0.000    0.000    0.000 shape_base.py:9(atleast_1d)
        1    0.000    0.000    0.000    0.000 misc.py:11(norm)
        1    0.000    0.000    0.000    0.000 function_base.py:605(asarray_chkfinite)
        2    0.000    0.000    0.000    0.000 numeric.py:476(asanyarray)
        1    0.000    0.000    0.000    0.000 {method 'ravel' of 'numpy.ndarray' objects}
        1    0.000    0.000    0.000    0.000 linalg.py:111(isComplexType)
        1    0.000    0.000    0.000    0.000 <string>:1(<module>)
        2    0.000    0.000    0.000    0.000 {method 'append' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {built-in method builtins.issubclass}
        4    0.000    0.000    0.000    0.000 {built-in method builtins.len}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        2    0.000    0.000    0.000    0.000 {method 'squeeze' of 'numpy.ndarray' objects}


In [6]: %prun numpy.linalg.norm(c1 - c2)
         10 function calls in 0.000 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 {built-in method builtins.exec}
        1    0.000    0.000    0.000    0.000 linalg.py:1976(norm)
        1    0.000    0.000    0.000    0.000 {built-in method numpy.core.multiarray.dot}
        1    0.000    0.000    0.000    0.000 <string>:1(<module>)
        1    0.000    0.000    0.000    0.000 numeric.py:406(asarray)
        1    0.000    0.000    0.000    0.000 {method 'ravel' of 'numpy.ndarray' objects}
        1    0.000    0.000    0.000    0.000 linalg.py:111(isComplexType)
        1    0.000    0.000    0.000    0.000 {built-in method builtins.issubclass}
        1    0.000    0.000    0.000    0.000 {built-in method numpy.core.multiarray.array}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

Was %prun tut, ist Ihnen sagen, wie lange eine Funktion aufrufen, die benötigt wird, um, einschließlich ein bisschen trace um herauszufinden, wo der Flaschenhals sein könnte. In diesem Fall werden sowohl der scipy.spatial.distance.euclidean und numpy.linalg.norm Implementierungen sind ziemlich schnell. Angenommen, man definiert eine Funktion dist(vect1, vect2) können Sie ein Profil mit der gleichen IPython Magie nennen. Als ein zusätzlicher bonus, %prun funktioniert auch innerhalb der Jupyter notebook, und Sie können tun %%prun zu Profil, eine ganze Zelle von code, anstatt nur eine Funktion, indem Sie einfach %%prun die erste Zeile der Zelle.

InformationsquelleAutor ericmjl

0

Ich weiß nicht, wie die Präzision und die Geschwindigkeit im Vergleich zu den anderen Bibliotheken, die Sie erwähnt, aber Sie können es tun für 2D-Vektoren mit Hilfe des built-in math.hypot() Funktion:
```
from math import hypot

def pairwise(iterable):
    "s -> (s0, s1), (s1, s2), (s2, s3), ..."
    a, b = iter(iterable), iter(iterable)
    next(b, None)
    return zip(a, b)

a = (52, 106, 35, 12)
b = (33, 153, 75, 10)

dist = [hypot(p2[0]-p1[0], p2[1]-p1[1]) for p1, p2 in pairwise(tuple(zip(a, b)))]
print(dist)  # -> [131.59027319676787, 105.47511554864494, 68.94925670375281]
```
- Vielen Dank für diese, ich werde versuchen, zu testen und auch die Zeit. Könnten Sie kurz erläutern, was die pairwise - Methode funktioniert?
- Sicher. Die pairwise() Funktion ist eine leichte Abwandlung der im itertools Rezepte - Dokumentation. Und die ursprüngliche return-Werte aus den wiederholenden argument übergeben wird, in der Reihenfolge, die in dem doc-string an den Anfang der Funktion.
InformationsquelleAutor martineau

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.

Fazit zuerst:

Effizienz-Test-Skript:

Effizienz-Test-Ausgabe:

Präzisions-mess-Skript & Ergebnis: