Pythonで多数のベクトルのコサイン類似度を素早く計算する方法は？

Question

私はベクトルのセットを持っており、コサインの類似性に基づいてトップ25の最も近いベクトルを取り出す必要があります。

ScipyとSklearnは余弦距離/類似度2ベクトルの計算を実装していますが、100k X 100kサイズのCosine Simを計算してからtop-25を取り出す必要があります。 Pythonで速いimplemenetがありますか？

#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() 

Answer 1

私がしようとするだろう賢くアルゴリズム最初ではなく、（ベクトルのすべてのペアを計算する）ブルートフォースをスピードアップ - @Silmathoron提案を1として

が、これは私がやっているものです。あなたのベクトルの次元が小さい場合は、KDTrees、scipy.spatial.KDTree（）が動作します。それらが高次元である場合は、最初にランダム投影が必要な場合があります。 http://scikit-learn.org/stable/modules/random_projection.html