Similitud del coseno en matrices dispersas

Question

Estoy intentando implementar un filtrado basado en artículos, con un gran espacio de características que representa a los consumidores que compraron (1) o no compraron (0) un producto concreto.

Tengo una distribución de cola larga, por lo que la matriz es bastante dispersa. R no lo maneja bien. ¿Qué puedo hacer para agilizar la medición de la similitud del coseno?

Answer 1

Utiliza el Matriz para almacenar la matriz, y el paquete skmeans_xdist para calcular distancias coseno.

/edit: Parece que el skmeans_xdist no es muy eficaz. He aquí un ejemplo sencillo de cómo se calcularía la similitud del coseno para una matriz del tamaño de Netflix en R.

Primero, construye la matriz:

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)

A continuación, normalice cada fila para que su distancia vectorial sea 1. Esto tarda 85 segundos en mi máquina.

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

Por último, podemos encontrar la similitud coseno, que me lleva 155 segundos

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

Obsérvese también que la matriz de similitud coseno es bastante dispersa, porque muchas películas no tienen ningún usuario en común. Puede convertir a distancia coseno utilizando 1-sim pero puede tardar un poco (no lo he cronometrado).

/editar un par de años después: Aquí hay una función de normalización de filas más rápida:

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
)

La nueva función sólo tarda 25 segundos (frente a los 89 segundos de la otra, supongo que mi ordenador se ha vuelto más lento =/):

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 no suele adaptarse bien a los datos de gran tamaño. Puede que necesites pasar a implementaciones más eficientes. Hay muchas opciones. Pero, por supuesto, es probable que también haya varios paquetes de R que puedan ayudarte un poco más.

Además, merece la pena dejar de pensar en matrices . Con lo que estás trabajando es con un gráfico . 1 es una arista y 0 no lo es. Una forma fácil de acelerar el cálculo de las similitudes es explotar inteligentemente la similitud. Esto, sin embargo, es más o menos los beneficios que se obtienen mediante el procesamiento de los datos en "forma de columna" en Hadoop, por ejemplo.

Cuando te das cuenta de que la similitud coseno consta de tres componentes: producto de A y B, la longitud de A y la longitud de B, te darás cuenta de que dos partes son independientes del otro vector, y la tercera parte tiene la dispersión al cuadrado, esto reducirá drásticamente los cálculos necesarios para una "matriz" de similitud coseno (de nuevo, dejar de verlo como una matriz)

La racionalización es entonces:

1. Calcular la longitud de cada vector individual, para la normalización (es decir, calcular $|A|$ )
2. Para cada atributo (!) envíe un mensaje a cada par de entradas distintas de cero. Si tiene $0.01$ de valores distintos de cero en cada uno de $c$ columnas, esto será sólo $O(0.0001 * c * n^2)$ mensajes.
3. Contar el número de mensajes recibidos para cada par, esto es $A\cdot B$ dividir por $|A|$ y $|B|$ .

Alternativamente:

1. Normalizar cada vector a la longitud $|A|=1$ (¡tu matriz dejará de ser binaria!)
2. Para cada atributo (!) envía un mensaje con el producto de los dos valores a cada par de entradas distintas de cero. Si tiene $0.01$ de valores distintos de cero en cada uno de $c$ columnas, esto será sólo $O(0.0001 * c * n^2)$ mensajes.
3. Suma los mensajes recibidos para cada par, esta es la similitud coseno. (No es necesario dividir, ya que $|A|=|B|=1$ )

Y piensa definitivamente en cómo tienda y organizar tus datos en la memoria. Aquí, el acceso rápido a los datos y la manipulación es el 90% del coste, los cálculos reales son triviales. No dejes que R lo haga automáticamente, porque eso probablemente significa que lo está haciendo mal...

Answer 3

Parte del software mcl ( http://micans.org/mcl ) es un programa mcxarray creado específicamente para realizar comparaciones rápidas de todos contra todos, incluida la similitud del coseno. Utiliza representaciones dispersas, y puede ser paralelizado sobre diferentes CPUs (con hilos) y diferentes máquinas (con trabajos), con fácil reintegración de las partes computadas. Descargo de responsabilidad: lo he escrito yo.

Answer 4

Estoy utilizando gensim que funciona bastante bien, sobre todo con datos de texto, que suelen ser muy dimensionales y dispersos.

Answer 5

Puede utilizar qlcMatrix::cosSparse . Es el paquete R más rápido para calcular la similitud del coseno en una matriz > 50% dispersa:

Consulte mi respuesta aquí para conocer los resultados de la evaluación comparativa:

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