Memoria Efficiente norma L2 che utilizza la trasmissione Python

Question

Sto cercando di implementare un metodo per creare punti cluster in un set di dati di test in base alla loro somiglianza con un set di dati campione, utilizzando la distanza euclidea. Il set di dati di test ha 500 punti, ogni punto è un vettore di dimensione N (N = 1024). Il set di dati di addestramento ha circa 10000 punti e ogni punto è anche un vettore dim. 1024. L'obiettivo è trovare la distanza L2 tra ciascun punto di test e tutti i punti campione per trovare il campione più vicino (senza usare alcuna funzione di distanza python). Poiché la matrice di prova e matrice formazione hanno dimensioni diverse, ho provato usando radiodiffusione:

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

dove test è un array di forma (500,1024) e la stazione è un array di forma (10000,1024). Sto ottenendo un MemoryError. Tuttavia, lo stesso codice funziona con array più piccoli. Per esempio:

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

C'è una memoria modo più efficiente per fare il calcolo di cui sopra, senza loop? Sulla base dei post online, possiamo implementare la norma L2 utilizzando la moltiplicazione di matrice sqrt (X * X-2 * X * Y + Y * Y). Così ho provato la seguente:

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) 

Dal momento che le matrici hanno forme diverse, quando ho cercato di trasmettere, non c'è corrispondenza dimensione e io non sono sicuro di quello che è il modo giusto per trasmettere (non hanno molta esperienza con Python broadcasting). Mi piacerebbe sapere qual è il modo giusto per implementare il calcolo della distanza L2 come una moltiplicazione di matrice in Python, dove le matrici hanno forme diverse. La matrice di distanza risultante dovrebbe avere dist [i, j] = distanza euclidea tra il punto di prova i e il punto di campionamento j.

grazie

Answer 1

semplificato e versione funzionante da 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) 

Quindi l'approccio che avete in mente è corretto, ma è necessario fare attenzione a come lo si applica.

Per semplificarti la vita, prendi in considerazione l'utilizzo delle funzioni testate e collaudate da scipy o scikit-learn.

Answer 2

Qui è Broadcasting con forme degli intermedi effettuati esplicito:

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) 

La documentation sulla radiodiffusione ha alcuni piuttosto buoni esempi.

Answer 3

Penso che quello che stai chiedendo esiste già in scipy nella forma della funzione cdist.

from scipy.spatial.distance import cdist 
res = cdist(test, train, metric='euclidean')