python - 如何加快向量集之间余弦相似度的计算

Question

我有一组向量(~30k)，每个向量由fasttext生成的300个元素组成，每个向量代表一个实体的含义，我想计算所有实体之间的相似度，所以我在一个向量中迭代嵌套物质，O(N^2) 复杂度，这在时间上是不切实际的。

你能推荐我另一种计算方法吗，或者我怎样才能并行化它？

def calculate_similarity(v1, v2):
    """
    Calculate cosine distance between two vectors
    """
    n1 = np.linalg.norm(v1)
    n2 = np.linalg.norm(v2)
    return np.dot(v1, v2) / n1 / n2


similarities = {}
for ith_entity, ith_vector in vectors.items():
    for jth_entity, jth_vector in vectors.items():
        if ith_entity == jth_entity:
            continue
        if (ith_entity, jth_entity) in similarities.keys() or (jth_entity, ith_entity) in similarities.keys():
            continue
        similarities[(ith_entity, jth_entity)] = calculate_similarity(ith_vector, jth_vector)

Answer 1

您可以通过使用 scipy 摆脱嵌套循环，这很慢。的距离模块。

给定 vectors = {'k1':v1, 'k2':v2, ..., 'km':vm}与 vi是一个长度为 n 的 Python 列表。

import numpy as np 
from scipy.spatial import distance

# transfrom vectors to m x n numpy array 
data = np.array(list(vectors.values())

# compute pairwise cosine distance 
pws = distance.pdist(data, metric='cosine')

pws是压缩距离矩阵。它是一维的，按以下顺序保存距离:

pws = np.array([ (k1, k2), (k1, k3), (k1, k4), ..., (k1, km),
                           (k2, k3), (k2, k4), ..., (k2, km),
                                      ...,
                                                   (km-1, km) ])

另请注意 distance.pdist计算余弦距离而不是余弦相似度。