快速計算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。