从稀疏数组高效计算成对 Jaccard 相似度
Efficiently compute pairwise Jaccard similarity from sparse array
我有一个如下所示的数组，每一行都是一个观察值，每一列都是一个特征：
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、交集和并集。
谢谢！
杰克
准确地说，只要至少有一个条目不为零，它就应该计入并集。
无论如何，你都必须进行 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])
乘法函数逐点作用，所以如果X[i]和[=18的第k个条目都是X[i].multiply(X[j])的第k个条目是1 =] 为一，否则为零。因此它充当逻辑和操作。同样，+ 充当逻辑或操作。 Sum 只是给出一行中非零条目的数量。
我有一个如下所示的数组，每一行都是一个观察值，每一列都是一个特征：
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、交集和并集。
谢谢！ 杰克
准确地说，只要至少有一个条目不为零，它就应该计入并集。
无论如何，你都必须进行 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])
乘法函数逐点作用，所以如果X[i]和[=18的第k个条目都是X[i].multiply(X[j])的第k个条目是1 =] 为一，否则为零。因此它充当逻辑和操作。同样，+ 充当逻辑或操作。 Sum 只是给出一行中非零条目的数量。