Rechnen Jaccard Ähnlichkeit in Python

Question

Ich habe 20.000 Dokumente, die ich die wahre Jaccard Ähnlichkeit für berechnen möchte, so dass ich später überprüfen kann, wie genau MinWise Hashing approximiert.

Jedes Dokument wird als Spalte in einer Zahlenmatrix dargestellt, wobei jede Zeile ein Wort ist, das entweder im Dokument (Eintrag = 1) oder nicht (Eintrag = 0) angezeigt wird. Es gibt ~ 600 Wörter (Zeilen).

So wäre zum Beispiel Spalte 1 [1 0 0 0 0 0 1 0 0 0 1 0], was bedeutet, dass die Wörter 1,7,11 darin und keine anderen erschienen.

Gibt es einen effizienteren Weg, die Ähnlichkeit neben meinem elementweisen Vergleichsansatz zu berechnen? Ich sehe nicht, wie ich Sätze verwenden könnte, um die Geschwindigkeit zu verbessern, da die Sätze gerade zu (0,1) werden, aber so wie es aussieht, ist der Code unmöglich langsam.

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

Hier ist ein vektorisiert Ansatz -

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

Alternative Art und Weise n11v und n00v mit np.einsum zu berechnen -

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

Wenn rawdata besteht aus 0s und 1s nur eine einfachere Art und Weise zu erhalten sie wären -

Benchmarking

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

Funktionsdefinitionen -

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 

Verification und Timings -

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 

Einige magische 300x+ Speedup da!

Also, warum ist es so schnell? Nun, es gibt viele Faktoren, von denen die wichtigste die Tatsache ist, dass NumPy-Arrays für Leistung konstruiert und für vektorisierte Berechnungen optimiert sind. Mit dem vorgeschlagenen Ansatz nutzen wir es sehr gut und sehen solche Beschleunigungen.

Hier ist eine related Q&A, die im Detail über diese Leistungskriterien sprechen.

Answer 2

berechnen Jaccard, Verwendung:

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