我能做些什么来提高 sklearn 在 9000+ 数据上的 Jaccard 相似度得分性能

Question

我正在尝试在向量列表 x 上创建一个 table 的 Jaccard 相似度分数，该列表中的所有其他元素都超过 9000 行（因此导致大约 9000、9000 列表）：

[[  2   2  67   2   5   3  62  68  27]
[  2   9  67   2   1   3  20  62 139]
[  2  17  67   2   0   6   6  62  73]
[  2  17  67   2   0   6  39  68  92]
[  0   0  67   0   0   3  62  62  13]
...

我是初学者，所以我试图用这样的代码来实现可耻的借口：

similarities_matrix = np.empty([len(x), len(x)])
for icounter, i in enumerate(x.as_matrix()):
    similarities_row = np.empty(len(x))
    for jcounter, j in enumerate(x.as_matrix()):
        similarities_row[jcounter] = jaccard_similarity_score(i, j)
    similarities_matrix[icounter] = similarities_row
pprint(similarities_matrix)

但它运行慢得不可思议。理想情况下，我希望我的代码在我的一生中运行（最好在 5 分钟内）

目前，此代码运行每个元素大约需要一秒来计算相似度矩阵。

Answer 1

如果您不介意使用scipy，您可以使用函数pdist from scipy.spatial.distance. The value computed by sklearn.metrics.jaccard_similarity_score(u, v) is equivalent to 1 -scipy.spatial.distance.hamming(u, v)。例如，

In [71]: from sklearn.metrics import jaccard_similarity_score

In [72]: from scipy.spatial.distance import hamming

In [73]: u = [2, 1, 3, 5]

In [74]: v = [2, 1, 4, 5]

In [75]: jaccard_similarity_score(u, v)
Out[75]: 0.75

In [76]: 1 - hamming(u, v)
Out[76]: 0.75

'hamming' 是 scipy.spatial.distance.pdist 提供的指标之一，因此您可以使用该函数计算所有成对距离。这里有一个小 x 用作示例：

In [77]: x = np.random.randint(0, 5, size=(8, 10))

In [78]: x
Out[78]: 
array([[4, 2, 2, 3, 1, 2, 0, 0, 4, 0],
       [3, 1, 4, 2, 3, 1, 2, 3, 4, 4],
       [1, 1, 0, 1, 0, 2, 0, 3, 3, 4],
       [2, 3, 3, 3, 1, 2, 3, 2, 1, 2],
       [3, 2, 3, 2, 0, 0, 4, 4, 3, 4],
       [3, 0, 1, 0, 4, 2, 0, 2, 1, 0],
       [4, 3, 2, 4, 1, 2, 3, 3, 2, 4],
       [3, 0, 4, 1, 3, 3, 3, 3, 1, 3]])

我将使用 squareform 将 pdist 的输出转换为相似度的对称数组。

In [79]: from scipy.spatial.distance import pdist, squareform

In [80]: squareform(1 - pdist(x, metric='hamming'))
Out[80]: 
array([[ 1. ,  0.1,  0.2,  0.3,  0.1,  0.3,  0.4,  0. ],
       [ 0.1,  1. ,  0.3,  0. ,  0.3,  0.1,  0.2,  0.4],
       [ 0.2,  0.3,  1. ,  0.1,  0.3,  0.2,  0.3,  0.2],
       [ 0.3,  0. ,  0.1,  1. ,  0.1,  0.3,  0.4,  0.2],
       [ 0.1,  0.3,  0.3,  0.1,  1. ,  0.1,  0.1,  0.1],
       [ 0.3,  0.1,  0.2,  0.3,  0.1,  1. ,  0.1,  0.3],
       [ 0.4,  0.2,  0.3,  0.4,  0.1,  0.1,  1. ,  0.2],
       [ 0. ,  0.4,  0.2,  0.2,  0.1,  0.3,  0.2,  1. ]])

我将你的代码转换为这个函数：

def jaccard_sim_matrix(x):
    similarities_matrix = np.empty([len(x), len(x)])
    for icounter, i in enumerate(x):
        similarities_row = np.empty(len(x))
        for jcounter, j in enumerate(x):
            similarities_row[jcounter] = jaccard_similarity_score(i, j)
        similarities_matrix[icounter] = similarities_row
    return similarities_matrix

所以我们可以验证 pdist 结果与您的计算结果相同。

In [81]: jaccard_sim_matrix(x)
Out[81]: 
array([[ 1. ,  0.1,  0.2,  0.3,  0.1,  0.3,  0.4,  0. ],
       [ 0.1,  1. ,  0.3,  0. ,  0.3,  0.1,  0.2,  0.4],
       [ 0.2,  0.3,  1. ,  0.1,  0.3,  0.2,  0.3,  0.2],
       [ 0.3,  0. ,  0.1,  1. ,  0.1,  0.3,  0.4,  0.2],
       [ 0.1,  0.3,  0.3,  0.1,  1. ,  0.1,  0.1,  0.1],
       [ 0.3,  0.1,  0.2,  0.3,  0.1,  1. ,  0.1,  0.3],
       [ 0.4,  0.2,  0.3,  0.4,  0.1,  0.1,  1. ,  0.2],
       [ 0. ,  0.4,  0.2,  0.2,  0.1,  0.3,  0.2,  1. ]])

在这里我将比较更大数组的时间：

In [82]: x = np.random.randint(0, 5, size=(500, 10))

In [83]: %timeit jaccard_sim_matrix(x)
14.9 s ± 192 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [84]: %timeit squareform(1 - pdist(x, metric='hamming'))
1.19 ms ± 2.23 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

最后，让我们为形状为 (9000, 10) 的输入计算时间：

In [94]: x = np.random.randint(0, 5, size=(9000, 10))

In [95]: %timeit squareform(1 - pdist(x, metric='hamming'))
1.34 s ± 9.13 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

这只是 1.34 秒——绝对在一生中。

我能做些什么来提高 sklearn 在 9000+ 数据上的 Jaccard 相似度得分性能

What can I do to improve sklearn's Jaccard similarity score performance on 9000+ data

python

performance

numpy

similarity