我有N对字符串列表(从集合1到N,从集合2),它们需要通过Jaccard相似度与最近的字符串列表配对。这意味着我需要计算N^2距离,并为集合1中的每个元素取最大相似性w.r.t。第二组。
运行它的简单代码是
import numpy as np
def jaccard_similarity(a, b):
intersection = set(a).intersection(set(b))
union = set(a).union(set(b))
return len(intersection)/len(union)
set_1 = [['Pisa','Tower','River','Tuscany'],['London','City','UK','England'],['Berlin','Germany','Munich']]
set_2 = [['Pisa','Arno','River','Tuscany','Florence','London','Tower'],['Germany','German','UBanh'],['London','City','UK','England','Europe']]
pairs = []
for vect_1 in set_1:
dist = []
for vect_2 in set_2:
dist.append(jaccard_similarity(vect_1,vect_2))
pairs.append(np.argmax(dist))
print(pairs)我知道这有O(N^2)的时间复杂度,但我想知道是否会有一些优化/启发式,以便平均情况会更好。
类似地,有什么关于代码本身的东西我可以优化吗?
编辑:我修改了这个问题,使它更加精确。
发布于 2020-04-26 16:18:44
您应该能够使用scipy.spatial.distance.cdist,它计算给定度量的整个矩阵。时间的复杂性是不可避免的,但是时间的复杂性使时间变得更快。
https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.distance.cdist.html
https://stackoverflow.com/questions/61443990
复制相似问题