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.

  • In Python, wie kann ich Korrelation und statistische Signifikanz zwischen zwei Arrays von Daten zu berechnen?
  • Binned boxplot in matplotlib mit numpy und scipy in Python
  • 3D-Matrix-Perspektive transformieren
  • Spark mit PySpark Bilder lesen
  • Füllen Sie einen Pandas SparseDataFrame aus einer SciPy Sparse Coo Matrix
  • Was ist ein guter Weg, um ein Ähnlichkeitsmaß von zwei Bildern zu erhalten, die ein Liniendiagramm enthalten?
  • Probleme mit 2D-Interpolation in Scipy
  • Verfolgen Sie Mayavi Maus ziehen, um die Erde um ihre Achse zu drehen
  • Python ist die beste Programmiersprache der Welt.