Speicher Effiziente L2-Norm mit Python-Broadcasting

Question

Ich versuche, eine Möglichkeit zu implementieren, Punkte in einem Test-Dataset basierend auf ihrer Ähnlichkeit mit einem Beispiel-Dataset mit euklidischer Distanz zu gruppieren. Der Testdatensatz hat 500 Punkte, jeder Punkt ist ein N-dimensionaler Vektor (N = 1024). Das Trainingsdatenset hat ungefähr 10000 Punkte und jeder Punkt ist auch ein 1024-Dim-Vektor. Das Ziel besteht darin, den L2-Abstand zwischen jedem Testpunkt und allen Stichprobenpunkten zu finden, um die nächste Stichprobe zu finden (ohne Python-Abstandsfunktionen zu verwenden). Da die Testanordnung und Ausbildung Array unterschiedliche Größen haben, habe ich versucht, unter Verwendung von Rundfunk:

import numpy as np 
    dist = np.sqrt(np.sum((test[:,np.newaxis] - train)**2, axis=2)) 

den Test eine Anordnung von Form (500,1024) und die Bahn ist eine Anordnung von Form (10000,1024). Ich erhalte einen MemoryError. Derselbe Code funktioniert jedoch auch für kleinere Arrays. Zum Beispiel:

 test= np.array([[1,2],[3,4]]) 
    train=np.array([[1,0],[0,1],[1,1]]) 

Gibt es eine speichereffizientere Möglichkeit, die obige Berechnung ohne Schleifen durchzuführen? Basierend auf den Online-Beiträgen können wir die L2-Norm unter Verwendung der Matrixmultiplikation sqrt (X * X-2 * X * Y + Y * Y) implementieren. Also versuchte ich folgendes:

x2 = np.dot(test, test.T) 
    y2 = np.dot(train,train.T) 
    xy = 2* np.dot(test,train.T) 

    dist = np.sqrt(x2 - xy + y2) 

Da die Matrizen unterschiedliche Formen haben, als ich versuchte, zu übertragen gibt es eine Dimension Mismatch und ich bin nicht sicher, was der richtige Weg ist viel Erfahrung mit Python zu übertragen (nicht haben Rundfunk). Ich würde gerne wissen, was der richtige Weg ist, um die L2-Abstandsberechnung als Matrixmultiplikation in Python zu implementieren, wo die Matrizen unterschiedliche Formen haben. Die resultierende Abstandsmatrix sollte dist [i, j] = euklidische Distanz zwischen dem Testpunkt i und dem Probenpunkt j haben.

dank

Answer 1

Vereinfachte und Arbeitsversion von this answer:

x, y = test, train 

x2 = np.sum(x**2, axis=1, keepdims=True) 
y2 = np.sum(y**2, axis=1) 
xy = np.dot(x, y.T) 
dist = np.sqrt(x2 - 2*xy + y2) 

So ist der Ansatz, den Sie im Sinn haben, ist richtig, aber Sie müssen vorsichtig sein, wie Sie es anwenden.

Um Ihnen das Leben zu erleichtern, sollten Sie die geprüften und bewährten Funktionen von scipy oder scikit-learn verwenden.

Answer 2

Hier sendet mit Formen der Zwischenprodukte explizit gemacht:

m = x.shape[0] # x has shape (m, d) 
n = y.shape[0] # y has shape (n, d) 
x2 = np.sum(x**2, axis=1).reshape((m, 1)) 
y2 = np.sum(y**2, axis=1).reshape((1, n)) 
xy = x.dot(y.T) # shape is (m, n) 
dists = np.sqrt(x2 + y2 - 2*xy) # shape is (m, n) 

Die documentation über den Rundfunk hat einige sehr gute Beispiele.

Answer 3

Ich denke, was Sie schon fragen, existiert in scipy in Form der cdist Funktion.