Cosine similarity on sparse matrix

Question

I'm trying to implement item based filtering, with a large feature space representing consumers who bought (1) or did not buy (0) a particular product.

I have a long tail distribution, so the matrix is quite sparse. R is not handling it well. What can I do to streamline the measurement of cosine similarity?

Answer 1

Use the Matrix package to store the matrix, and the skmeans_xdist function to calculate cosine distances.

/edit: It appears that the skmeans_xdist function is not very efficient. Here's a simple example of how you would calculate cosine similarity for a netflix-sized matrix in R.

First, build the matrix:

library(Matrix)
set.seed(42)
non_zero <- 99000000
i <- sample(1:17770, non_zero, replace=TRUE)
j <- sample(1:480189, non_zero, replace=TRUE)
x <- sample(1:5, non_zero, replace=TRUE)
m <- sparseMatrix(i=i,j=j,x=x) #Rows are movies, columns are users
m <- drop0(m)

Next normalize each row so it's vector distance is 1. This takes 85 seconds on my machine.

row_norms <- sqrt(rowSums(m^2))
row_norms <- t(crossprod(sign(m), Diagonal(x=row_norms)))
row_norms@x <- 1/row_norms@x
m_norm <- m * row_norms

Finally, we can find cosine similarity, which takes me 155 seconds

system.time(sim <- tcrossprod(m_norm))

Also, note that the cosine similarity matrix is pretty sparse, because many movies do not share any users in common. You can convert to cosine distance using 1-sim, but that might take a while (I haven't timed it).

/edit a couple years later: Here's a faster row-normalization function:

row_normalize <- function(m){
  row_norms <- sqrt(rowSums(m^2))
  row_norms <- t(crossprod(sign(m), Diagonal(x=row_norms)))
  row_norms@x <- 1/row_norms@x
  m_norm <- m * row_norms
  return(m_norm)
}

fast_row_normalize <- function(m){
    d <- Diagonal(x=1/sqrt(rowSums(m^2)))
    return(t(crossprod(m, d)))
}

library(microbenchmark)
microbenchmark(
  a = row_normalize(m),
  b = fast_row_normalize(m),
  times=1
)

The new function takes only 25 seconds (vs 89 seconds for the other one— I guess my computer got slower =/):

Unit: seconds
 expr      min       lq     mean   median       uq      max neval
    a 89.68086 89.68086 89.68086 89.68086 89.68086 89.68086     1
    b 24.09879 24.09879 24.09879 24.09879 24.09879 24.09879     1

Answer 2

R often does not scale well to large data. You may need to move on to more efficient implementations. There are plenty of choices around. But of course, there probably are also various R packages that could help you a bit further.

Also, it pays off to stop thinking in matrixes. What you are working with is a graph. 1 is an edge, and 0 is not. An easy way to accelerate computing the similarities here is to cleverly exploit the similarity. This btw. is pretty much the benefits you get by processing the data in "column form" in Hadoop, for example.

When you realize that cosine similarity consists of three components: product of A and B, length of A and length of B, you will notice that two parts are independent of the other vector, and the third part has the squared sparsity, this will drastically reduce the computations needed for a cosine similarity "matrix" (again, stop seeing it as a matrix)

The streamlining then is:

1. Compute the length of each single vector, for normalization (i.e. compute $|A|$)
2. For each attribute (!) send a message to each pair of non-zero entries. If you have $0.01$ of non-zero values in each of $c$ columns, this will be just $O(0.0001 * c * n^2)$ messages.
3. Count the number of messages received for each pair, this is $A\cdot B$, divide by $|A|$ and $|B|$.

Alternatively:

1. Standardize each vector to length $|A|=1$ (your matrix will no longer be binary!)
2. For each attribute (!) send a message with the product of the two values to each pair of non-zero entries. If you have $0.01$ of non-zero values in each of $c$ columns, this will be just $O(0.0001 * c * n^2)$ messages.
3. Sum the messages received for each pair, this is the cosine similarity. (No division necessary, as $|A|=|B|=1$)

And definitely think about how to store and organize your data in memory. Here, fast data access and manipulation is 90% of the cost, the actual computations are trivial. Don't let R do it automatically, because that probably means it is doing it wrong...

Answer 3

Part of the mcl software (http://micans.org/mcl) is a program mcxarray created specifically to do fast all vs all comparisons, including cosine similarity. It utilises sparse representations, and it can be parallelised over different CPUs (with threads) and different machines (with jobs), with easy re-integration of the computed parts. Disclaimer - it was written by me.

Answer 4

I am using gensim, which works pretty well especially with text data which is usually high dimensional and sparse

Answer 5

You may consider using qlcMatrix::cosSparse. It is the fastest R package for computing cosine similarity on a matrix > 50% sparse:

See my answer here for benchmarking results:

https://stackoverflow.com/questions/29417754/is-there-any-sparse-support-for-dist-function-in-r/64944105#64944105