提高该算法的时间复杂度

Question

我有N对向量（集合1中的N到集合2中的N）需要通过余弦相似度配对到最接近的向量。这意味着我需要计算N ^ 2的距离，并为集合1中的每个元素取最大相似度w.r.t。设置2。

运行它的简单代码将是

import numpy as np
from sklearn.metrics.pairwise import cosine_similarity

pairs = []

for vect_1 in set_1:
    dist = []
    for vect_2 in set_2:
        dist.append(cosine_similarity(vect_1,vect_2))
    pairs.append(np.argmax(dist))

我知道这具有O（N ^ 2）的时间复杂度，但我想知道是否可能存在一些优化/启发式方法，以使平均情况更好。

类似地，我可能会优化有关代码本身的内容吗？

Answer 1

您应该能够使用scipy.spatial.distance.cdist，它可以为给定指标计算整个矩阵。时间的复杂性是不可避免的，但是科学的速度使其变得很快。