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에서 제공하는 통계 중 하나입니다, 그래서 당신은 모든 페어의 거리를 계산하기 위해이 기능을 사용할 수 있습니다. 여기에 예제로 사용 작은 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. ]]) 

I은 ​​큰 어레이의 타이밍을 비교한다 :

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 초입니다. 확실히 평생 동안.