我有一个大型稀疏矩阵-使用稀疏.csr_矩阵来自西皮。这些值是二进制的。对于每一行,我需要计算到同一矩阵中每一行的Jaccard距离。最有效的方法是什么?即使对于一个10.000 x 10.000矩阵,我的运行时也需要几分钟才能完成。在
当前解决方案:
def jaccard(a, b):
intersection = float(len(set(a) & set(b)))
union = float(len(set(a) | set(b)))
return 1.0 - (intersection/union)
def regions(csr, p, epsilon):
neighbors = []
for index in range(len(csr.indptr)-1):
if jaccard(p, csr.indices[csr.indptr[index]:csr.indptr[index+1]]) <= epsilon:
neighbors.append(index)
return neighbors
csr = scipy.sparse.csr_matrix("file")
regions(csr, 0.51) #this is called for every row
这里是一个具有scikit-learn类API的解决方案。在
以下是一些测试和基准测试:
^{pr2}$断言所有结果近似相等
基准运行时(来自Jupyer笔记本)
如果使用矩阵乘法计算集合交集,然后使用规则
|union(a, b)| == |a| + |b| - |intersection(a, b)|
来确定并集,则矢量化相对容易:注意转换为bool,然后是int,因为}是密集矩阵。在
X
的数据类型必须足够大,以累积两倍于最大行和的值,X
的条目必须是零或一。这段代码的缺点是它在RAM上很重,因为unions
和{如果您只对小于某个截止值的距离感兴趣,
^{pr2}$epsilon
,可以针对稀疏矩阵调整代码:如果这仍然需要大量的RAM,您可以尝试在一个维度上进行向量化,在另一个维度上使用Python循环。在
补充一句:我使用了上述方法的加权版本,其简单实现如下:
我怀疑这是最有效的实现,但它比
scipy.spatial.distance.jaccard
中的密集实现快得多。在相关问题 更多 >
编程相关推荐