Faster Python Kosinus Unähnlichkeit zwischen Scipy CSR "Vektoren"

Question

Es ist eine klassische Frage, aber ich glaube, dass viele Menschen immer noch nach Antworten suchen. Diese Frage ist eine andere als this one, da meine Frage ist die Operation zwischen zwei sparse Vektoren (keine Matrix).

Ich schrieb eine blog post darüber, wie Kosinus Scipy Spatial Distance (SSD) wird langsamer, wenn die Dimension der Daten wird immer höher (weil es auf dichten Vektoren funktioniert). Der Beitrag ist in indonesischer Sprache, aber der Code, meine Experimenteinstellungen & Ergebnisse sollten unabhängig von der Sprache leicht verständlich sein (am Ende des Beitrags).

Derzeit ist diese Lösung mehr als 70-mal schneller für hohe Dimensionsdaten (im Vergleich zu SSD) & mehr Speicher effizient:

import numpy as np 

    def fCosine(u,v): # u,v CSR vectors, Cosine Dissimilarity 
     uData = u.data; vData = v.data 
     denominator = np.sqrt(np.sum(uData**2)) * np.sqrt(np.sum(vData**2)) 
     if denominator>0: 
      uCol = u.indices; vCol = v.indices # np array 
      intersection = set(np.intersect1d(uCol,vCol)) 
      uI = np.array([u1 for i,u1 in enumerate(uData) if uCol[i] in intersection]) 
      vI = np.array([v2 for j,v2 in enumerate(vData) if vCol[j] in intersection])    
      return 1-np.dot(uI,vI)/denominator 
     else: 
      return float("inf") 

Ist es möglich, diese Funktion (Pythonic oder über JIT/Cython noch weiter zu verbessern ???). Hier

Answer 1

ist eine Alternative, alt_fCosine, die (auf meinem Rechner) etwa 3x schneller für CSR-Vektoren von Größe 10**5 und 10**4 Nicht-Null-Elemente:

import scipy.sparse as sparse 
import numpy as np 
import math 

def fCosine(u,v): # u,v CSR vectors, Cosine Dissimilarity 
    uData = u.data; vData = v.data 
    denominator = np.sqrt(np.sum(uData**2)) * np.sqrt(np.sum(vData**2)) 
    if denominator>0: 
     uCol = u.indices; vCol = v.indices # np array 
     intersection = set(np.intersect1d(uCol,vCol)) 
     uI = np.array([u1 for i,u1 in enumerate(uData) if uCol[i] in intersection]) 
     vI = np.array([v2 for j,v2 in enumerate(vData) if vCol[j] in intersection])    
     return 1-np.dot(uI,vI)/denominator 
    else: 
     return float("inf") 

def alt_fCosine(u,v): 
    uData, vData = u.data, v.data 
    denominator = math.sqrt(np.sum(uData**2) * np.sum(vData**2)) 
    if denominator>0: 
     uCol, vCol = u.indices, v.indices 
     uI = uData[np.in1d(uCol, vCol)] 
     vI = vData[np.in1d(vCol, uCol)] 
     return 1-np.dot(uI,vI)/denominator 
    else: 
     return float("inf") 

# Check that they return the same result 
N = 10**5 
u = np.round(10*sparse.random(1, N, density=0.1, format='csr')) 
v = np.round(10*sparse.random(1, N, density=0.1, format='csr')) 
assert np.allclose(fCosine(u, v), alt_fCosine(u, v)) 

alt_fCosine ersetzt zwei Listenkomprehensionen, ein Aufruf np.intersection1d und die Bildung eines Python-Set mit zwei Aufrufen an np.in1d und erweiterte Indizierung.

---

Für N = 10**5:

In [322]: %timeit fCosine(u, v) 
100 loops, best of 3: 5.73 ms per loop 

In [323]: %timeit alt_fCosine(u, v) 
1000 loops, best of 3: 1.62 ms per loop 

In [324]: 5.73/1.62 
Out[324]: 3.537037037037037