时间戳

首页 > 解决方案 > 从稀疏数组有效地计算成对 Jaccard 相似度

python - 从稀疏数组有效地计算成对 Jaccard 相似度

问题描述

我有一个如下所示的数组，每一行是一个观察值，每一列是一个特征：

import scipy
my_sparse_array = scipy.sparse.random(2000, 10000000, density=0.01, format='csr')

对于每对观察值（行），我想计算它们之间的 Jaccard 相似度——考虑到数组中的非零值意味着存在该特征，而零值表示该特征不存在。因此，交集是两个观测值都具有非零值的特征，而联合是只有一个观测值具有非零值的地方。两者都为零的特征将被忽略。

进行这种成对计算的最有效方法是什么。我的计划是组合 0 - 1999 年的所有对，对两行进行子集化，删除具有非零列的任何列，然后进行计算，但这似乎非常低效，因为它需要完成大量拼接。

所需的输出是带有 Jaccard 索引的 2000 x 2000 矩阵。一个额外的好处是制作一个 4 列的中间数组，观察索引 1，观察索引 2，交集和联合。

谢谢！杰克

标签： pythonperformancenumpyscipysparse-matrix

解决方案

准确地说，只要至少有一个条目不为零，它就应该计入联合。

无论如何，您都必须进行 O(n^2) 比较。特别是，有 n(n-1)/2 个可能的对。因此，任何加速都将来自比较本身。

似乎条目的值与您的定义无关，因此如果您转换为布尔值，事情会更快。假设X=my_sparse_array.astype('bool)'您的稀疏布尔数组大小为 (2000,10000000)。您可以计算行之间的交集和并集i，j如下所示：

intersection = scipy.sum(X[i].multiply(X[j]))
union = scipy.sum(X[i]+X[j])

乘法函数逐点起作用，因此如果和的第 - 个k条目都X[i].multiply(X[j])为 1，则 的k第 - 个条目为1，否则为 0。因此它充当逻辑和操作。同样，作为逻辑或操作。Sum 只是给出一行中非零条目的数量。X[i]X[j]+

推荐阅读