2016-06-25 131 views
5

Ho un set di 100 mila vettori e ho bisogno di recuperare il vettore più vicino a 25 in base alla somiglianza del coseno.Come calcolare rapidamente la similarità del coseno per un numero elevato di vettori in Python?

Scipy e Sklearn hanno implementazioni per calcolare i vettori di distanza coseno/similitudine 2, ma dovrò calcolare il Cosine Sim per 100k X 100k e poi prendere il top-25. Esiste un implemenet veloce nel calcolo di Python che?

Come da @Silmathoron suggerimento, questo è quello che sto facendo -

#vectors is a list of vectors of size : 100K x 400 i.e. 100K vectors each of dimenions 400 
vectors = numpy.array(vectors) 
similarity = numpy.dot(vectors, vectors.T) 


# squared magnitude of preference vectors (number of occurrences) 
square_mag = numpy.diag(similarity) 

# inverse squared magnitude 
inv_square_mag = 1/square_mag 

# if it doesn't occur, set it's inverse magnitude to zero (instead of inf) 
inv_square_mag[numpy.isinf(inv_square_mag)] = 0 

# inverse of the magnitude 
inv_mag = numpy.sqrt(inv_square_mag) 

# cosine similarity (elementwise multiply by inverse magnitudes) 
cosine = similarity * inv_mag 
cosine = cosine.T * inv_mag 

k = 26 

box_plot_file = file("box_data.csv","w+") 

for sim,query in itertools.izip(cosine,queries): 
    k_largest = heapq.nlargest(k, sim) 
    k_largest = map(str,k_largest) 
    result = query + "," + ",".join(k_largest) + "\n" 
    box_plot_file.write(result) 
box_plot_file.close() 
+0

Cosa intendi per "vettore 25 più vicino"? Le prime 25 coppie più vicine? O qualcos'altro? –

+0

Per ogni vettore, calcolerò la somiglianza del coseno con ogni altro vettore e selezionerò 25 vettori per ciascun vettore rispetto alla somiglianza del coseno. – user3667569

+0

dipende da quanto velocemente lo vuoi ... se ci mostri un esempio della tua implementazione con il tempo necessario (potenzialmente su un sottocampione se è davvero troppo lento) e dicci l'aumento di velocità desiderato, allora possiamo dire se si può accelerare con un algoritmo migliore solo in python o se si ha bisogno di andare in cython o multithreading ... – Silmathoron

risposta

2

vorrei provare più intelligente algoritmi prima, piuttosto che accelerare la forza bruta (calcolando tutte le coppie di vettori). KDTrees potrebbe funzionare, scipy.spatial.KDTree(), se i tuoi vettori sono di bassa dimensione. Se si tratta di dimensioni elevate, potrebbe essere necessario prima una proiezione casuale: http://scikit-learn.org/stable/modules/random_projection.html