Effiziente Distanzberechnung zwischen N Punkten und einer Referenz in numpy / scipy

Ich habe gerade angefangen, scipy / numpy zu benutzen. Ich habe ein 100000 * 3 Array, jede Zeile ist eine Koordinate und ein 1 * 3 Mittelpunkt. Ich möchte die Distanz für jede Zeile im Array zum Zentrum berechnen und sie in einem anderen Array speichern. Was ist der effizienteste Weg, um es zu tun?

5 Solutions collect form web for “Effiziente Distanzberechnung zwischen N Punkten und einer Referenz in numpy / scipy”

Ich würde einen Blick auf scipy.spatial.distance.cdist :

http://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.distance.cdist.html

 import numpy as np import scipy a = np.random.normal(size=(10,3)) b = np.random.normal(size=(1,3)) dist = scipy.spatial.distance.cdist(a,b) # pick the appropriate distance metric 

dist für die Standard-Fernmetrik entspricht:

 np.sqrt(np.sum((ab)**2,axis=1)) 

Obwohl cdist ist viel effizienter für große Arrays (auf meiner Maschine für Ihre Größe Problem, cdist ist schneller um einen Faktor von ~ 35x).

Ich würde die Sklearn-Implementierung der euklidischen Distanz nutzen. Der Vorteil ist die Verwendung des effizienteren Ausdrucks durch die Matrix-Multiplikation:

 dist(x, y) = sqrt(dot(x, x) - 2 * dot(x, y) + dot(y, y) 

Ein einfaches Skript würde so aussehen:

 import numpy as np x = np.random.rand(1000, 3) y = np.random.rand(1000, 3) dist = np.sqrt(np.dot(x, x)) - (dot(x, y) + dot(x, y)) + dot(y, y) 

Der Vorteil dieses Ansatzes wurde in der Sklearn-Dokumentation gut beschrieben: http://scikit-learn.org/stable/modules/generated/sklearn.metrics.pairwise.euclidean_distances.html#sklearn.metrics.pairwise.euclidean_distances

Ich benutze diesen Ansatz, um große Datamatrizen (10000, 10000) mit einigen kleinen Modifikationen wie die Verwendung der np.einsum-Funktion zu knacken.

Sie können auch die Entwicklung der Norm (ähnlich wie bemerkenswerte Identitäten) nutzen. Dies ist wahrscheinlich der effizienteste Weg, um den Abstand einer Matrix von Punkten zu berechnen.

Hier ist ein Code-Snippet, den ich ursprünglich für eine k-Nearest-Neighbors-Implementierung verwendet habe, in Octave, aber du kannst es leicht an numpy anpassen, da es nur Matrixmultiplikationen verwendet (das Äquivalent ist numpy.dot ()):

 % Computing the euclidian distance between each known point (Xapp) and unknown points (Xtest) % Note: we use the development of the norm just like a remarkable identity: % ||x1 - x2||^2 = ||x1||^2 + ||x2||^2 - 2*<x1,x2> [napp, d] = size(Xapp); [ntest, d] = size(Xtest); A = sum(Xapp.^2, 2); A = repmat(A, 1, ntest); B = sum(Xtest.^2, 2); B = repmat(B', napp, 1); C = Xapp*Xtest'; dist = A+B-2.*C; 

Möglicherweise müssen Sie eine detailliertere Art und Weise angeben, welche Distanzfunktion Sie interessieren, aber hier ist eine sehr einfache (und effiziente) Implementierung der quadratischen Euklidischen Distanz, die auf dem inner product basiert (was offensichtlich verallgemeinert werden kann, auf einfache Weise, auf andere Art von Distanzmaßnahmen):

 In []: P, c= randn(5, 3), randn(1, 3) In []: dot(((P- c)** 2), ones(3)) Out[]: array([ 8.80512, 4.61693, 2.6002, 3.3293, 12.41800]) 

Wo P sind deine Punkte und c ist das Zentrum.

Dies könnte Ihre Frage nicht direkt beantworten, aber wenn Sie nach allen Permutationen von Partikelpaaren sind, habe ich in einigen Fällen die folgende Lösung schneller als die pdist-Funktion gefunden.

 import numpy as np L = 100 # simulation box dimension N = 100 # Number of particles dim = 2 # Dimensions # Generate random positions of particles r = (np.random.random(size=(N,dim))-0.5)*L # uti is a list of two (1-D) numpy arrays # containing the indices of the upper triangular matrix uti = np.triu_indices(100,k=1) # k=1 eliminates diagonal indices # uti[0] is i, and uti[1] is j from the previous example dr = r[uti[0]] - r[uti[1]] # computes differences between particle positions D = np.sqrt(np.sum(dr*dr, axis=1)) # computes distances; D is a 4950 x 1 np array 

Sehen Sie dies für einen eingehenderen Blick auf diese Angelegenheit, auf meinem Blog-Post.

  • Schneiden von spärlichen Matrizen in Scipy - welche Typen funktionieren am besten?
  • Pandas: Verwenden Sie mehrere Spalten eines Dataframe als Index eines anderen
  • Funktioniert scipy.integrate.ode.set_solout?
  • Berechnen von Pearson-Korrelation und Bedeutung in Python
  • Gute Umsetzung der gierigen Set-Cover für große Datensätze?
  • Inverse Distanz gewichtet (IDW) Interpolation mit Python
  • Python: Import Scipy führt zu Traceback Verweis auf eine gelöschte Datei
  • So erkennen Sie eine Verschiebung zwischen den Bildern
  • Zweite Ordnung Gradient in numpy
  • Finde Markov Steady State mit linken Eigenwerten (mit numpy oder scipy)
  • Wie komme ich zurück, grad als Tupel für scipys fmin_cg Funktion
  • Python ist die beste Programmiersprache der Welt.