Obliczanie Jaccard Podobieństwo w Pythonie

Question

Mam 20 000 dokumentów, dla których chcę obliczyć prawdziwe podobieństwo Jaccard, tak, że mogę później sprawdzić, jak dokładnie Hashowanie MinWise je przybliża.

Każdy dokument jest reprezentowany jako kolumna w macierzy numpy, gdzie każdy wiersz jest słowem, które pojawia się w dokumencie (pozycja = 1) lub nie (pozycja = 0). Istnieje ~ 600 słów (wiersze).

Tak na przykład kolumna 1 byłaby [1 0 0 0 0 0 1 0 0 0 1 0], co oznacza, że ​​pojawiły się w niej słowa 1,7,11, a nie inne.

Czy istnieje skuteczniejszy sposób obliczenia podobieństwa poza moim podejściem opartym na elementarnym porównaniu? Nie widzę sposobu, w jaki mogłem używać zestawów, aby poprawić prędkość, ponieważ zestawy stają się (0,1), ale w obecnej postaci kod jest niesamowicie wolny.

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

Oto wektorowy podejście -

# 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) 

Alternatywny sposób obliczyć n11v i n00v z 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)) 

Jeśli rawdata składa 0s i tylko 1s, prostszy sposób, aby uzyskać byłyby one -

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

Benchmarking definicje

Function -

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 

weryfikacja i czasy -

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 

Niektóre magiczne 300x+ SpeedUp tam!

Dlaczego więc jest tak szybki? Cóż, istnieje wiele czynników, z których najważniejszym jest fakt, że tablice NumPy są zbudowane pod kątem wydajności i zoptymalizowane pod względem wektoryzacji. Dzięki proponowanemu podejściu wykorzystujemy je całkiem dobrze i obserwujemy takie przyspieszenia.

Oto jeden numer related Q&A, który szczegółowo omawia te kryteria wydajności.

Answer 2

Aby obliczyć Jaccard, przeznaczenie:

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