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

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

至少如果你对多个句子执行此过程，你可以尝试使用 scipy.spatial.cKDTree（我不知道它是否在单个查询中收回成本。而且 500 相当高，我似乎记得 KDTrees 在不那么多的维度上工作得更好。你必须试验）。

假设您已将所有向量（dict 值）放入一个大的 numpy 数组中：

>>> import numpy as np
>>> from scipy.spatial import cKDTree as KDTree
>>>
# 100,000 vectors (that's all my RAM can take)
>>> a = np.random.random((100000, 500))
>>>
>>> t = KDTree(a)
# create one new vector and find distance and index of closest
>>> t.query(np.random.random(500))
(8.20910072933986, 83407)

Answer 2

我可以想出 2 种可能的方法来优化这个过程。

首先，如果您的目标只是获得最接近的向量（或句子），则可以去掉 list_sentences 变量，只在内存中保留您找到的最接近的句子。这样，您就不需要在最后对完整的（并且可能非常大）列表进行排序，而只需 return 最接近的列表。

def compute_dist(v, list_sentences):
    min_dist = 0

    for key, val in list_sentences.items():
        dist = euclidean(v, val)
        if dist < min_dist:
            closest_sentence = key
            min_dist = dist

    return closest_sentence

第二个可能更不可靠。您可以尝试通过给它第三个参数来重新实现 euclidean 方法，该参数将是您目前找到的最近向量与用户向量之间的当前最小距离 min_dist。我不知道 scipy euclidean 方法是如何实现的，但我猜它接近于对所有向量维度的平方差求和。你想要的是如果总和高于min_dist就停止的方法（距离无论如何都会高于min_dist并且你不会保留它）。

Answer 3

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

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

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

让我们假设您已经以对您的数据而言自然的任何方式完成了该操作，并且现在有 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)

（请注意，此类向量比较通常使用 cosine-distance/cosine-similarity 而不是欧几里德距离。如果您切换到那个，您可能正在做其他 norming/dot-products 而不是上面的第一个选项，或者使用metric='cosine' 选项 cdist()。）

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

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

如果您需要将该 int 索引转回您的另一个 key/text，您将使用自己的 dict/list 来记住槽到键的关系。

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

有一些方法可以获得更快的结果，基于对完整候选集的预先构建索引——但是这样的索引在高维 space 中变得非常棘手（比如你的 500 维 space).他们通常会牺牲完全准确的结果来换取更快的结果。（也就是说，他们 return for 'closest 1' 或 'closest N' 会有一些错误，但通常不会有太大偏差。）有关此类库的示例，请参阅 Spotify's ANNOY or Facebook's FAISS。

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

Search for the nearest array in a huge array of arrays

python

arrays

performance

numpy

word2vec