Skillarnの9000+データでのJaccardの類似性スコアのパフォーマンスを向上させるにはどうすればいいですか

Question

ベクトルのリストでJaccardの類似性スコアの表を作成しようとしていますxリスト内の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をscipy.spatial.distanceから使用できます。 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'は、scipy.spatial.distance.pdistが提供するメトリックの1つです。ここでは一例として使用する小さな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]]) 

私は類似の対称配列にpdistの出力を変換するためにsquareformを使用します。

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秒です。間違いなく一生の間です。