python - 在庞大的数组中寻找最近的数组

Question

我需要找到最接近的句子。我有一个句子数组和一个用户句子，我需要在数组中找到最接近用户句子的元素。

我使用 word2vec 以向量的形式呈现每个句子:

def get_avg_vector(word_list, model_w2v, size=500):
    sum_vec = np.zeros(shape = (1, size))
    count = 0

    for w in word_list:
        if w in model_w2v and w != '':
            sum_vec += model_w2v[w]
            count +=1
    if count == 0:
        return sum_vec
    else:
        return sum_vec / count + 1

因此，数组元素如下所示:

array([[ 0.93162371,  0.95618944,  0.98519795,  0.98580566,  0.96563747,
         0.97070891,  0.99079191,  1.01572807,  1.00631016,  1.07349398,
         1.02079309,  1.0064849 ,  0.99179418,  1.02865136,  1.02610303,
         1.02909719,  0.99350413,  0.97481178,  0.97980362,  0.98068508,
         1.05657591,  0.97224562,  0.99778703,  0.97888296,  1.01650529,
         1.0421448 ,  0.98731804,  0.98349052,  0.93752996,  0.98205837,
         1.05691232,  0.99914532,  1.02040555,  0.99427229,  1.01193818,
         0.94922226,  0.9818139 ,  1.03955   ,  1.01252615,  1.01402485,
         ...
         0.98990598,  0.99576604,  1.0903802 ,  1.02493086,  0.97395976,
         0.95563786,  1.00538653,  1.0036294 ,  0.97220088,  1.04822631,
         1.02806122,  0.95402776,  1.0048053 ,  0.97677222,  0.97830801]])

我也将用户的句子表示为一个向量，我计算最接近它的元素是这样的:

%%cython
from scipy.spatial.distance import euclidean

def compute_dist(v, list_sentences):
    dist_dict = {}

    for key, val in list_sentences.items():
        dist_dict[key] = euclidean(v, val)

    return sorted(dist_dict.items(), key=lambda x: x[1])[0][0]

上述方法中的

list_sentences是一个字典，其中键是句子的文本表示，值是向量。

这需要很长时间，因为我有超过 6000 万个句子。我怎样才能加快、优化这个过程？

如有任何建议，我将不胜感激。

Answer 1

6000 万个句子向量的初始计算本质上是固定成本，您只需支付一次。我假设您主要关心每次后续查找的时间，即单个用户提供的查询语句。

使用 numpy native 数组操作可以加快距离计算，而不是在 Python 循环中进行您自己的单独计算。 (它能够使用其优化代码批量执行操作。)

但首先您需要将 list_sentences 替换为真正的 numpy 数组，只能通过数组索引访问。 (如果您有其他键/文本需要与每个插槽相关联，您可以在其他地方使用一些字典或列表进行关联。)

假设您已经完成了该操作，无论采用何种方式对您的数据来说都是自然的，现在有了 array_sentences，这是一个 6000 万 x 500 维的 numpy 数组，每行一个句子平均向量.

然后，获得一个充满距离的数组的 1-liner 方法是 6000 万个候选者中的每一个与 1 个查询(给出 6000 万个条目)之间的差异的向量长度(“范数”)回答每个差异):

dists = np.linalg.norm(array_sentences - v)  

另一种 1-liner 方法是使用 numpy 效用函数 cdist() 计算每对两个输入集合之间的距离。在这里，您的第一个集合只是一个查询向量 v(但如果您要同时处理多个批处理，一次提供多个查询可能会提供额外的轻微加速):

dists = np.linalg.cdists(array[v], array_sentences)

(请注意，此类向量比较通常使用余弦距离/余弦相似度而不是欧氏距离。如果您切换到那个，您可能正在做其他规范/点积而不是上面的第一个选项，或者使用metric='cosine' cdist() 的选项。)

一旦您拥有 numpy 数组中的所有距离，使用 numpy 原生排序选项可能比使用 Python sorted() 更快。例如，numpy 的间接排序 argsort()，它只返回排序后的索引(因此避免移动所有向量坐标)，因为您只想知道哪个项是最佳匹配项。例如:

sorted_indexes = argsort(dists)
best_index = sorted_indexes[0]

如果您需要将该 int 索引转回您的其他键/文本，您将使用自己的字典/列表来记住槽到键的关系。

通过与所有候选人进行比较，所有这些仍然会给出完全正确的结果，这(即使做得最好)仍然很耗时。

有一些方法可以更快地获得结果，这些方法基于对所有候选对象的预先构建索引——但是这样的索引在高维空间(比如 500 维空间)中变得非常棘手。他们通常会牺牲完全准确的结果来换取更快的结果。 (也就是说，它们为“最接近的 1”或“最接近的 N”返回的内容会有一些错误，但通常不会有太大偏差。)有关此类库的示例，请参见 Spotify's ANNOY。或 Facebook's FAISS .