我该怎么做才能提高sklearn在9000+数据上的Jaccard相似度得分表现

I am trying create a table of Jaccard similarity score on a list of vectors x with every other elements in the list that has over 9000 rows (so resulting to a roughly 9000, 9000 list):

我正在尝试在向量列表x上创建一个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]
...

I'm a beginner so I tried to my implement shameful excuse of a code like this:

我是一名初学者,所以我试图用这样的代码实现可耻的借口:

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)

But it runs impossibly slow. Ideally I wanted my code to run within the span of my lifetime (preferably under 5 minutes.)

但它运行速度非常慢。理想情况下,我希望我的代码在我的生命周期内运行(最好在5分钟之内。)

Currently, this code runs roughly a second per element to compute the similarity matrix.

目前,该代码每个元素运行大约一秒钟以计算相似性矩阵。

1 个解决方案

#1

If you don't mind using scipy, you can use the function 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). For example,

如果您不介意使用scipy,可以使用scipy.spatial.distance中的函数pdist。由sklearn.metrics.jaccard_similarity_score(u,v)计算的值等于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' is one of the metrics provided by scipy.spatial.distance.pdist, so you can use that function to compute all the pairwise distances. Here's a small x to use as an example:

'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]])

I'll use squareform to convert the output of pdist to the symmetric array of similarities.

我将使用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. ]])

I converted your code to this function:

我将您的代码转换为此函数:

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

so we can verify that the pdist result is the same as your calculation.

所以我们可以验证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. ]])

Here I'll compare the timing for a larger array:

在这里,我将比较更大阵列的时间:

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)

Finally, let's time the calculation for an input with shape (9000, 10):

最后,让我们计算一下具有形状(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)

That's just 1.34 seconds--definitely within the span of a lifetime.

那只是1.34秒 - 绝对是在一生中。

#1