Effiziente Jaccardähnlichkeit DocumentTermMatrix

Question

Ich möchte eine Möglichkeit, Jaccard Ähnlichkeit zwischen Dokumenten einer tm::DocumentTermMatrix effizient zu berechnen. Ich kann etwas ähnliches für Kosinusähnlichkeit über die Slam Paket wie in this answer. gezeigt Ich stieß auf CrossValidated another question and response, die R spezifisch war, aber über Matrixalgebra nicht unbedingt der effizienteste Weg. Ich habe versucht, diese Lösung mit effizienteren Slam Funktionen zu implementieren, aber bekomme nicht die selbe Lösung wie wenn ich einen weniger effizienten Ansatz verwende, um den DTM zu einer Matrix zu zwingen und proxy::dist zu verwenden.

Wie kann ich die Jaccard-Ähnlichkeit zwischen Dokumenten einer großen DocumentTermMatrix in R effizient berechnen?

#Data & pacages

library(Matrix);library(proxy);library(tm);library(slam);library(Matrix) 

mat <- structure(list(i = c(1L, 2L, 1L, 2L, 1L, 2L, 1L, 2L, 3L, 1L, 
    2L, 3L, 3L, 3L, 4L, 4L, 4L, 4L), j = c(1L, 1L, 2L, 2L, 3L, 3L, 
    4L, 4L, 4L, 5L, 5L, 6L, 7L, 8L, 9L, 10L, 11L, 12L), v = c(1, 
    1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1), nrow = 4L, 
     ncol = 12L, dimnames = structure(list(Docs = c("1", "2", 
     "3", "4"), Terms = c("computer", "is", "fun", "not", "too", 
     "no", "it's", "dumb", "what", "should", "we", "do")), .Names = c("Docs", 
     "Terms"))), .Names = c("i", "j", "v", "nrow", "ncol", "dimnames" 
    ), class = c("DocumentTermMatrix", "simple_triplet_matrix"), weighting = c("term frequency", 
    "tf")) 

#Inefficient Berechnung (erwartete Ausgabe)

proxy::dist(as.matrix(mat), method = 'jaccard') 

##  1  2  3 
## 2 0.000    
## 3 0.875 0.875  
## 4 1.000 1.000 1.000 

#My Attempt

A <- slam::tcrossprod_simple_triplet_matrix(mat) 
im <- which(A > 0, arr.ind=TRUE) 
b <- slam::row_sums(mat) 
Aim <- A[im] 

stats::as.dist(Matrix::sparseMatrix(
     i = im[,1], 
     j = im[,2], 
     x = Aim/(b[im[,1]] + b[im[,2]] - Aim), 
     dims = dim(A) 
)) 

##  1 2 3 
## 2 2.0   
## 3 0.1 0.1  
## 4 0.0 0.0 0.0 

Ausgänge stimmen nicht überein.

FYI Hier ist der Originaltext:

c("Computer is fun. Not too fun.", "Computer is fun. Not too fun.", 
    "No it's not, it's dumb.", "What should we do?") 

I erwarten würde Elemente 1 & 2 0 Entfernung und das Element auf 3 zu Element näher an 1 als das Element 1 und 4 (I erwarten würde weitesten Abstand, da keine Wörter geteilt werden), wie in der proxy::dist Lösung gesehen.

EDIT

Beachten Sie, dass auch auf einem mittelgroßen DTM die Matrix riesig wird. Hier ist ein Beispiel mit dem veganen Paket. Hinweis 4 Minuten zu lösen, wo die Kosinusähnlichkeit ~ 5 Sekunden ist.

library(qdap); library(quanteda);library(vegan);library(slam) 
x <- quanteda::convert(quanteda::dfm(rep(pres_debates2012$dialogue), stem = FALSE, 
     verbose = FALSE, removeNumbers = FALSE), to = 'tm') 


## <<DocumentTermMatrix (documents: 2912, terms: 3368)>> 
## Non-/sparse entries: 37836/9769780 
## Sparsity   : 100% 
## Maximal term length: 16 
## Weighting   : term frequency (tf) 

tic <- Sys.time() 
jaccard_dist_mat <- vegan::vegdist(as.matrix(x), method = 'jaccard') 
Sys.time() - tiC#Time difference of 4.01837 mins 

tic <- Sys.time() 
tdm <- t(x) 
cosine_dist_mat <- 1 - crossprod_simple_triplet_matrix(tdm)/(sqrt(col_sums(tdm^2) %*% t(col_sums(tdm^2)))) 
Sys.time() - tiC#Time difference of 5.024992 secs 

Answer 1

Jaccard Maßnahme ist ein Maß zwischen SETS und Eingangsmatrix sollte binäre sein. Die very first line sagt:

## common values: 
A = tcrossprod(m) 

Bei Tasche-of-Wörter DTM dies nicht die Anzahl der gemeinsamen Werte ist!

library(text2vec) 
library(magrittr) 
library(Matrix) 

jaccard_similarity <- function(m) { 
    A <- tcrossprod(m) 
    im <- which(A > 0, arr.ind=TRUE, useNames = F) 
    b <- rowSums(m) 
    Aim <- A[im] 
    sparseMatrix(
    i = im[,1], 
    j = im[,2], 
    x = Aim/(b[im[,1]] + b[im[,2]] - Aim), 
    dims = dim(A) 
) 
} 

jaccard_distance <- function(m) { 
    1 - jaccard_similarity(m) 
} 

cosine <- function(m) { 
    m_normalized <- m/sqrt(rowSums(m^2)) 
    tcrossprod(m_normalized) 
} 

Benchmarks:

data("movie_review") 
tokens <- movie_review$review %>% tolower %>% word_tokenizer 

dtm <- create_dtm(itoken(tokens), hash_vectorizer(hash_size = 2**16)) 
dim(dtm) 
# 5000 65536 

system.time(dmt_cos <- cosine(dtm)) 
# user system elapsed 
# 2.524 0.169 2.693 

system.time({ 
    dtm_binary <- transform_binary(dtm) 
    # or simply 
    # dtm_binary <- sign(dtm) 
    dtm_jac <- jaccard_similarity(dtm_binary) 
}) 
# user system elapsed 
# 11.398 1.599 12.996 
max(dtm_jac) 
# 1 
dim(dtm_jac) 
# 5000 5000 

EDIT 2016.07.01:

Siehe auch schnellere Version von text2vec 0.4 (~ 2.85x, wenn sie nicht von dgCMatrix zu konvertieren zu dgTMatrix und ~ 1.75x whe n brauchen Spalte Haupt dgCMatrix)

jaccard_dist_text2vec_04 <- function(x, y = NULL, format = 'dgCMatrix') { 
    if (!inherits(x, 'sparseMatrix')) 
    stop("at the moment jaccard distance defined only for sparse matrices") 
    # union x 
    rs_x = rowSums(x) 
    if (is.null(y)) { 
    # intersect x 
    RESULT = tcrossprod(x) 
    rs_y = rs_x 
    } else { 
    if (!inherits(y, 'sparseMatrix')) 
     stop("at the moment jaccard distance defined only for sparse matrices") 
    # intersect x y 
    RESULT = tcrossprod(x, y) 
    # union y 
    rs_y = rowSums(y) 
    } 
    RESULT = as(RESULT, 'dgTMatrix') 
    # add 1 to indices because of zero-based indices in sparse matrices 
    # 1 - (...) because we calculate distance, not similarity 
    RESULT@x <- 1 - RESULT@x/(rs_x[RESULT@i + 1L] + rs_y[RESULT@j + 1L] - RESULT@x) 
    if (!inherits(RESULT, format)) 
    RESULT = as(RESULT, format) 
    RESULT 
} 
system.time({ 
    dtm_binary <- transform_binary(dtm) 
    dtm_jac <-jaccard_dist(dtm_binary, format = 'dgTMatrix') 
}) 
# user system elapsed 
# 4.075 0.517 4.593 
system.time({ 
    dtm_binary <- transform_binary(dtm) 
    dtm_jac <-jaccard_dist(dtm_binary, format = 'dgCMatrix') 
}) 
# user system elapsed 
# 6.571 0.939 7.516 

Answer 2

Wie wäre es vegdist() vom vegan Paket? Es verwendet C-Code und ist ca. 10x schneller als Proxy:

library(vegan) 
vegdist(as.matrix(mat), method = 'jaccard') 
## 1 2 3 
## 2 0.0   
## 3 0.9 0.9  
## 4 1.0 1.0 1.0 

library(microbenchmark) 
matt <- as.matrix(mat) 
microbenchmark(proxy::dist(matt, method = 'jaccard'), 
       vegdist(matt, method = 'jaccard')) 

## Unit: microseconds 
##         expr  min  lq  mean 
## proxy::dist(matt, method = "jaccard") 4879.338 4995.2755 5133.9305 
##  vegdist(matt, method = "jaccard") 587.935 633.2625 703.8335 
## median  uq  max neval 
## 5069.203 5157.520 7549.346 100 
## 671.466 723.569 1305.357 100 

Answer 3

Mit stringdistmatrix vom stringdist Paket und mit Hilfe der nthread Option, um es parallel laufen zu lassen, beschleunigt sie eine ganze Menge. im Durchschnitt sechs Sekunden langsamer als Ihre Tests mit Kosinusähnlichkeit.

library(qdap) 
library(slam) 
library(stringdist) 
data(pres_debates2012) 

x <- quanteda::convert(quanteda::dfm(rep(pres_debates2012$dialogue), stem = FALSE, 
            verbose = FALSE, removeNumbers = FALSE), to = 'tm') 

tic <- Sys.time() 
tdm <- t(x) 
cosine_dist_mat <- 1 - crossprod_simple_triplet_matrix(tdm)/(sqrt(col_sums(tdm^2) %*% t(col_sums(tdm^2)))) 
Sys.time() - tiC#Time difference of 4.069233 secs 

tic <- Sys.time() 
t <- stringdistmatrix(pres_debates2012$dialogue, method = "jaccard", nthread = 4) 
Sys.time() - tiC#Time difference of 10.18158 secs