我需要找到最接近的句子。 我有一个句子数组和一个用户句子,我需要找到数组中最接近用户的句子元素。
我使用 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万句话。 如何加快、优化此过程?
我将不胜感激任何建议。
6000 万个句子向量的初始计算本质上是您需要支付一次的固定成本。我假设您主要关心每个后续查找的时间,对于单个用户提供的查询句子。
使用 numpy 本机数组操作可以加快距离计算的速度,而不是在 Python 循环中进行自己的单独计算。(它能够使用其优化的代码批量执行操作。
但首先,您需要将list_sentences
替换为真正的numpy数组,该数组只能通过array-index访问。(如果你有其他键/文本需要与每个插槽相关联,你可以在其他地方使用一些字典或列表来执行此操作。
假设您已经这样做了,以任何对您的数据来说很自然的方式,现在有array_sentences
,一个 6000 万乘 500 维的 numpy 数组,每行有一个句子平均向量。
然后,获取充满距离的数组的 1 行方法是作为 6000 万个候选者和 1 个查询之间差值的向量长度("范数")(每个查询给出 6000 万个条目答案):
dists = np.linalg.norm(array_sentences - v)
另一种 1 行方法是使用 numpy 实用程序函数cdist()
来计算每对两个输入集合之间的通勤距离。在这里,您的第一个集合只是一个查询向量v
(但如果您有批处理要一次执行,一次提供多个查询可能会提供额外的轻微加速):
dists = np.linalg.cdists(array[v], array_sentences)
(请注意,这种向量比较通常使用余弦距离/余弦相似性而不是欧几里得距离。如果你切换到它,你可能会做其他规范/点积而不是上面的第一个选项,或者使用metric='cosine'
选项来cdist()
。
一旦你在 numpy 数组中拥有所有距离,使用 numpy-native 排序选项可能比使用 Pythonsorted()
更快。例如,numpy 的间接排序argsort()
,它只返回排序后的索引(从而避免移动所有向量坐标),因为您只想知道哪些项目是最佳匹配项。例如:
sorted_indexes = argsort(dists)
best_index = sorted_indexes[0]
如果您需要将该 int 索引转换回其他键/文本,您可以使用自己的字典/列表来记住插槽到键的关系。
通过与所有候选人进行比较,所有这些仍然给出了一个完全正确的结果,这(即使做得最好)仍然很耗时。
有一些方法可以基于对完整候选集的预构建索引来获得更快的结果 - 但是这样的索引在高维空间(如500维空间)中变得非常棘手。他们经常牺牲完全准确的结果来换取更快的结果。(也就是说,它们返回的"最接近的 1"或"最接近的 N"会有一些错误,但通常不会偏离太多。有关此类库的示例,请参阅Spotify的ANNOY或Facebook的FAISS。
至少如果你对多个句子执行此过程,你可以尝试使用scipy.spatial.cKDTree
(我不知道它是否在单个查询上为自己买单。另外500
相当高,我似乎记得KDTrees在不太多的维度上效果更好。你必须进行实验)。
假设你已经把所有的向量(字典值)放到一个大的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)
我可以考虑优化此过程的 2 种可能方法。
首先,如果你的目标只是得到最接近的向量(或句子),你可以去掉list_sentences
变量,只在内存中保留你找到的最接近的句子。这样,您就不需要在末尾对完整(可能非常大)列表进行排序,而只返回最接近的列表。
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
。我不知道 scipyeuclidean
方法是如何实现的,但我想它接近于对所有向量维度的平方差求和。你想要的是如果总和大于min_dist
则停止的方法(无论如何距离都会大于min_dist
,你不会保留它)。