Computing Jaccard сходство в Python

Question

У меня есть 20 000 документов, которые я хочу вычислить истинное сходство Jaccard, так что я могу позже проверить, насколько точно хеширование MinWise приближается к нему.

Каждый документ представлен в виде столбца в матрице numpy, где каждая строка представляет собой слово, которое либо появляется в документе (entry = 1), либо не является (entry = 0). Есть ~ 600 слов (строк).

Так, например, столбец 1 будет [1 0 0 0 0 0 1 0 0 0 1 0], что означает, что в нем появились слова 1,7,11, а другие нет.

Есть ли более эффективный способ вычисления сходства, кроме моего элементарного подхода к сопоставлению? Я не вижу, как я могу использовать наборы для повышения скорости, так как наборы просто становятся (0,1), но, поскольку он стоит, код невероятно медленный.

import numpy as np 

#load file into python 
rawdata = np.loadtxt("myfile.csv",delimiter="\t") 
#Convert the documents from rows to columns 
rawdata = np.transpose(rawdata) 
#compute true jacard similarity 
ndocs = rawdata.shape[1] 
nwords = rawdata.shape[0] 
tru_sim = np.zeros((ndocs,ndocs)) 

#computes jaccard similarity of 2 documents 
def jaccard(c1, c2): 
    n11 = sum((c1==1)&(c2==1)) 
    n00 = sum((c1==0)&(c2==0)) 
    jac = n11/(nfeats-n00) 
    return (jac) 

for i in range(0,ndocs): 
    tru_sim[i,i]=1 
    for j in range(i+1,ndocs): 
     tru_sim[i,j] = jaccard(rawdata[:,i],rawdata[:,j]) 

Answer 1

Вот Векторизованных подход -

# Get the row, col indices that are to be set in output array   
r,c = np.tril_indices(ndocs,-1) 

# Use those indicees to slice out respective columns 
p1 = rawdata[:,c] 
p2 = rawdata[:,r] 

# Perform n11 and n00 vectorized computations across all indexed columns 
n11v = ((p1==1) & (p2==1)).sum(0) 
n00v = ((p1==0) & (p2==0)).sum(0) 

# Finally, setup output array and set final division computations 
out = np.eye(ndocs) 
out[c,r] = n11v/(nfeats-n00v) 

Альтернативный способ вычисления n11v и n00v с np.einsum -

n11v = np.einsum('ij,ij->j',(p1==1),(p2==1).astype(int)) 
n00v = np.einsum('ij,ij->j',(p1==0),(p2==0).astype(int)) 

Если rawdata состоит из 0s и 1s только более простой способ получить их будет -

n11v = np.einsum('ij,ij->j',p1,p2) 
n00v = np.einsum('ij,ij->j',1-p1,1-p2) 

Бенчмаркинг определения

Функция -

def original_app(rawdata, ndocs, nfeats): 
    tru_sim = np.zeros((ndocs,ndocs)) 
    for i in range(0,ndocs): 
     tru_sim[i,i]=1 
     for j in range(i+1,ndocs): 
      tru_sim[i,j] = jaccard(rawdata[:,i],rawdata[:,j]) 
    return tru_sim 

def vectorized_app(rawdata, ndocs, nfeats): 
    r,c = np.tril_indices(ndocs,-1) 
    p1 = rawdata[:,c] 
    p2 = rawdata[:,r] 
    n11v = ((p1==1) & (p2==1)).sum(0) 
    n00v = ((p1==0) & (p2==0)).sum(0) 
    out = np.eye(ndocs) 
    out[c,r] = n11v/(nfeats-n00v) 
    return out 

Проверочные и тайминги -

In [6]: # Setup inputs 
    ...: rawdata = (np.random.rand(20,10000)>0.2).astype(int) 
    ...: rawdata = np.transpose(rawdata) 
    ...: ndocs = rawdata.shape[1] 
    ...: nwords = rawdata.shape[0] 
    ...: nfeats = 5 
    ...: 

In [7]: # Verify results 
    ...: out1 = original_app(rawdata, ndocs, nfeats) 
    ...: out2 = vectorized_app(rawdata, ndocs, nfeats) 
    ...: print np.allclose(out1,out2) 
    ...: 
True 

In [8]: %timeit original_app(rawdata, ndocs, nfeats) 
1 loops, best of 3: 8.72 s per loop 

In [9]: %timeit vectorized_app(rawdata, ndocs, nfeats) 
10 loops, best of 3: 27.6 ms per loop 

Некоторые волшебно 300x+ убыстрение там!

Итак, почему это так быстро? Ну, есть множество факторов, наиболее важным из которых является то, что массивы NumPy построены для производительности и оптимизированы для векторизованных вычислений. С предлагаемым подходом мы довольно хорошо используем его и, таким образом, видим такие ускорения.

Адрес related Q&A, которые подробно описывают эти критерии эффективности.

Answer 2

Для вычисления Jaccard, используйте:

def jaccard(x,y): 
    x = np.asarray(x, np.bool) # Not necessary, if you keep your data 
    y = np.asarray(y, np.bool) # in a boolean array already! 
    return np.double(np.bitwise_and(x, y).sum())/np.double(np.bitwise_or(x, y).sum()) 

print jaccard([1,1,0,0,0],[0,1,0,0,1]) 
>>> 0.33333333333333331