Locality Sensitive Hashing di array numpy sparsi

Question

Ho una grande matrice numpy/scipy sparsa in cui ogni riga corrisponde a un punto nello spazio ad alta dimensione. Voglio fare domande del seguente tipo:

Dato un punto P (una riga della matrice) e una distanza epsilon, trovare tutti i punti con la distanza al massimo Epsilon da P.

La metrica di distanza che sto utilizzando è simile a Jaccard, quindi dovrebbe essere possibile utilizzare i trucchi Locality Hashing sensibili come MinHash.

Esiste un'implementazione di MinHash per array numpy sparsi da qualche parte (non riesco a trovarne uno) o esiste un modo semplice per farlo?

La ragione per cui non sto semplicemente tracciando qualcosa costruito per array non sparsi al di fuori di Github è che le scarse strutture di dati in Scipy potrebbero causare esplosioni in termini di complessità temporale.

Answer 1

Se si dispone di grandi insiemi di dati sparsi che sono troppo grandi per essere tenuto in memoria in un formato non-sparse, mi piacerebbe provare questa implementazione LSH che è costruito attorno l'assunzione di CSR Sparse Matrici di SciPy:

https://github.com/brandonrobertz/SparseLSH

Ha anche il supporto per gli archivi di valori-chiave basati su disco come LevelDB se non è possibile adattare le tabelle in memoria. Dalla documentazione:

from sparselsh import LSH 
from scipy.sparse import csr_matrix 

X = csr_matrix([ 
    [ 3, 0, 0, 0, 0, 0, -1], 
    [ 0, 1, 0, 0, 0, 0, 1], 
    [ 1, 1, 1, 1, 1, 1, 1] ]) 

# One class number for each input point 
y = [ 0, 3, 10] 

X_sim = csr_matrix([ [ 1, 1, 1, 1, 1, 1, 0]]) 

lsh = LSH(4, 
      X.shape[1], 
      num_hashtables=1, 
      storage_config={"dict":None}) 

for ix in xrange(X.shape[0]): 
    x = X.getrow(ix) 
    c = y[ix] 
    lsh.index(x, extra_data=c) 

# find points similar to X_sim 
lsh.query(X_sim, num_results=1) 

Se è sicuramente solo vuole usare MinHash, si potrebbe provare https://github.com/go2starr/lshhdc, ma non ho testato personalmente che uno per la compatibilità con matrici sparse.