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（有点 gem）所能达到的最快速度。如果我将它与使用 RCppArmadillo 的 RCpp 函数进行比较（根据@f-privé 的建议稍微更新）

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

所以，我将定义以 R 为基础计算 crossprod，然后在 Rcpp 中进行缩放。

PS：如果你有一个非常稀疏的矩阵，你可以使用包 Matrix 将你的矩阵转换为稀疏矩阵。这个新的 class 矩阵也有 crossprod 方法，所以你也可以使用 coss2。

Answer 3

coop 包的 coop::cosine 功能可能是现在最好的方法。它是在 Rcpp 中实现的，但也有与 lsa::cosine 不同的方法，并且内存开销也更低。它的使用和lsa::cosine完全一样，只是把包名换掉了。

为了进一步加速，您可能需要更改您的 BLAS 库。 coop 手册有一些基本的细节和建议。

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

Fast computation of > 10^6 cosine vector similarities in R

r

performance

parallel-processing

cosine-similarity