快速计算R中的> 10^6余弦向量相似度

Question

我得到了约1600个文档x〜120个字的文档项矩阵。我想计算所有这些向量之间的余弦相似度，但我们正在谈论约1,300,000个比较[n *（n-1）/ 2]。

我用parallel :: mclapply与8但它仍然需要永远。

你建议哪种解决方案？

谢谢

Answer 1

这是我的承担。

如果我定义的余弦相似度作为

coss <- function(x) {crossprod(x)/(sqrt(tcrossprod(colSums(x^2))))} 

（我认为这是关于尽快我可以用基础R功能使它和经常监督crossprod这是一个小宝石）。如果我使用RCppArmadillo的RCPP功能进行比较（略更新所建议@ F-私法）

NumericMatrix cosine_similarity(NumericMatrix x) { 
    arma::mat X(x.begin(), x.nrow(), x.ncol(), false); 

    // Compute the crossprod                      
    arma::mat res = X.t() * X; 
    int n = x.ncol(); 
    arma::vec diag(n); 
    int i, j; 

    for (i=0; i<n; i++) { 
    diag(i) = sqrt(res(i,i)); 
    } 

    for (i = 0; i < n; i++) 
    for (j = 0; j < n; j++) 
     res(i, j) /= diag(i)*diag(j); 

    return(wrap(res)); 
} 

（这有可能会与一些在犰狳库中的专业功能优化 - 只是想获得一些定时测量）。

比较那些收益率

> XX <- matrix(rnorm(120*1600), ncol=1600) 
> microbenchmark::microbenchmark(cosine_similarity(XX), coss(XX), coss2(XX), times=50) 
> microbenchmark::microbenchmark(coss(x), coss2(x), cosine_similarity(x), cosine_similarity2(x), coss3(x), times=50) 
Unit: milliseconds 
        expr  min  lq  mean median  uq  max 
       coss(x) 173.0975 183.0606 192.8333 187.6082 193.2885 331.9206 
       coss2(x) 162.4193 171.3178 183.7533 178.8296 184.9762 319.7934 
cosine_similarity2(x) 169.6075 175.5601 191.4402 181.3405 186.4769 319.8792 
neval cld 
    50 a 
    50 b 
    50 a 

这实在是没有那么糟糕。使用C++计算余弦相似度的好处是超小的（@ f-privé的解决方案最快），所以我猜你的计时问题是由于你正在做什么来将文本从单词转换为数字，而不是在计算时余弦相似。不知道更多关于您的特定代码，我们很难为您提供帮助。

Answer 2

我非常同意@ekstroem关于crossprod的使用，但我认为在他的实现中有不必要的计算。我认为coss是错误的结果。 他的回答与我相比，你可以使用这个CPP文件：

// [[Rcpp::depends(RcppArmadillo)]] 
#include <RcppArmadillo.h> 
using namespace Rcpp; 

// [[Rcpp::export]] 
NumericMatrix cosine_similarity(NumericMatrix x) {                

    arma::mat X(x.begin(), x.nrow(), x.ncol(), false); 
    arma::mat rowSums = sum(X % X, 0); 
    arma::mat res; 

    res = X.t() * X/sqrt(rowSums.t() * rowSums); 

    return(wrap(res)); 
} 

// [[Rcpp::export]] 
NumericMatrix& toCosine(NumericMatrix& mat, 
         const NumericVector& diag) { 

    int n = mat.nrow(); 
    int i, j; 

    for (j = 0; j < n; j++) 
    for (i = 0; i < n; i++) 
     mat(i, j) /= diag(i) * diag(j); 

    return mat; 
} 

/*** R 
coss <- function(x) { 
    crossprod(x)/(sqrt(crossprod(x^2))) 
} 

coss2 <- function(x) { 
    cross <- crossprod(x) 
    toCosine(cross, sqrt(diag(cross))) 
} 

XX <- matrix(rnorm(120*1600), ncol=1600) 

microbenchmark::microbenchmark(
    cosine_similarity(XX), 
    coss(XX), 
    coss2(XX), 
    times = 20 
) 
*/ 

Unit: milliseconds 
        expr  min  lq  mean median  uq  max neval 
cosine_similarity(XX) 172.1943 176.4804 181.6294 181.6345 185.7542 199.0042 20 
       coss(XX) 262.6167 270.9357 278.8999 274.4312 276.1176 337.0531 20 
      coss2(XX) 134.6742 137.6013 147.3153 140.4783 146.5806 204.2115 20 

所以，我会去definility为基础R计算crossprod，然后执行缩放比例Rcpp。 PS：如果你有一个非常稀疏的矩阵，你可以使用包Matrix将你的矩阵转换为稀疏矩阵。这种新的矩阵类型也有crossprod方法，所以你也可以使用coss2。