Python 中计算加权 Jaccard 指数的最佳方法

Question

我有一个构建为稀疏加权矩阵的数据集，我想为其计算下游的加权 Jaccard 指数 grouping/clustering，灵感来自以下文章：http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/36928.pdf

我在寻找在 Python 中进行上述计算的最佳方法时遇到了一个小问题。我目前用来检验我的假设的函数如下：

def weighted_jaccard_index(x,y):
    mins, maxs = 0, 0
    for i in np.arange(len(x)):
        mins += np.amin([x[i],y[i]])
        maxs += np.amax([x[i],y[i]])
    return mins/maxs

然后我通过传递我定义的函数 weighted_jaccard_index:

通过 from scipy.spatial.distance import pdist 提供这个

w_j = pdist(X, weighted_jaccard_index)

但我发现了很大的性能问题，这并不奇怪。我目前正在研究将 MinHash 与 datasketch 包一起使用，但我很乐意就如何最好地实现这一点提出意见。我认为这样的事情是可能的：

df_np = df_gameinfo.to_numpy()
mg = ds.WeightedMinHashGenerator(20,20000)
lsh = ds.MinHashLSH(threshold=0.2,num_perm=20000)

#Create index in LSH
for i in np.arange(len(df_np)):
    vc = df_arr[i]
    m_hash = mg.minhash(vc)
    lsh.insert(i,m_hash)

test_ex = df.iloc[9522].to_numpy() #Random observations to calculate distance for
test_ex_m = mg.minhash(test_ex)

lsh.query(test_ex_m)

可能会在 Numpy 中使用矢量化，但我不确定如何表达它。

数据大小为 20k 个观测值和 30 个维度 (NxM = 20.000x30)。

Answer 1

您可以使用连接：

q = np.concatenate([x,y], axis=1)
np.sum(np.amin(q,axis=1))/np.sum(np.amax(q,axis=1))

%%timeit -r 10 -n 10 为 100 x 10 阵列给出每个循环 131 µs ± 61.7 µs（10 次运行的平均值±标准偏差，每次 10 次循环）。

您的原始函数给出：对于相同的数据，每个循环 4.46 毫秒 ± 95.9 微秒（10 次运行的平均值 ± 标准偏差，每次 10 次循环）

def jacc_index(x,y):
    q = np.concatenate([x,y], axis=1)
    return np.sum(np.amin(q,axis=1))/np.sum(np.amax(q,axis=1))

Python 中计算加权 Jaccard 指数的最佳方法

Optimal way for calculating Weighted Jaccard index in Python

python

numpy

distance

minhash