¿Cómo trato con cálculo de similitud de datos?

Question

Tengo muchos registros como este:

M es de alrededor de 10 millones de dólares y N es de alrededor de 100K.

Ahora quiero aplicar el filtrado colaborativo en estos datos, por ejemplo, Un usuario llega con sus características(datos dispersos), ¿cómo puedo saber que usuario existente es más parecida a la de él/ella ?

Yo no creo que pueda calcular todos los registros cada vez que llega una petición, gracias ! O hay algún otro algoritmo podría hacer esto ?

Answer 1

Lo que estamos hablando es de un "Espacio Vectorial Modelo" de la recuperación de la información. Listas de Wikipedia algunos programas que ayudan con esto - el que estoy más familiarizado con Lucene.

Esta página describe su algoritmo. Los puntos principales son que 1) usted puede invertir su índice, 2) usted puede mirar a través de los índices en paralelo y 3) se puede limitar sólo a la parte superior $k$. Todas estas cosas le dan una muy buena aceleración.

Answer 2

He estado haciendo un procedimiento similar sobre una base regular últimamente. No es rápido, y toma un pedazo decente de espacio en disco duro si el proceso de un lote de archivos. Como nota, los datos con los que trabajo tiene menos "características", más "usuarios", y puedo usar perl para procesar.

En primer lugar, yo no recomendaría el almacenamiento de los datos juntos como una sola matriz, ya que la mayoría de los programas (R) no será capaz de manejarlo. Si almacena cada usuario como un archivo independiente (.txt o cualquier otro formato funciona mejor para usted), usted puede acceder a ellos individualmente, incluso con R.

Entonces, como un documento nuevo que entra, usted tendrá que hacer de 100.000 comparaciones de cada uno de ellos entre dos vectores de longitud de 10 millones de dólares.

He aquí un ejemplo en R con al azar dos vectores binarios de longitud de 10.000.000.

x=as.numeric(rnorm(10000000)<0)

y=as.numeric(rnorm(10000000)<0)

sim = crossprod(x,y)/sqrt(crossprod(x)*crossprod(y))  

         [,1]
[1,] 0.4999211

Puesto que los dos vectores en este ejemplo son aleatorios 0,1 vectores, tienen una similitud del coseno de 0.5. Esta semejanza (coseno sim) el cálculo se realizó en menos de un segundo sin mí tratando de optimizar.

A ver cuánto tiempo el proceso, se podía recorrer en este código, a más de 100.000 iteraciones y almacenar cada una similitud de resultados con los resultados vector que contiene todos sus partidos. He probado el código anterior con 1000 iteraciones y que tomó cerca de 70 segundos.

También puede insertar cualquier medida de similitud que usted desea. Sin duda es factible en términos de tiempo de cálculo, pero puede que desee optimizar este si usted necesita más rápido. Espero que esto le da una idea de lo que podría tomar de cómputo.

Answer 3

Usted podría tratar de ordenar los datos por el número total de "1" en cada fila (longitud del vector). Esto le puede dar un espacio para empezar a buscar cuando le dan un nuevo usuario. Por ejemplo, si el nuevo usuario tiene una longitud de 1342, puedes revisar todas las entradas con longitudes de más o menos 500. Usted puede hacer esto de manera eficiente, si los datos están ordenados. Obviamente, esto requiere una inversión inicial de tiempo de cálculo para pre-ordenar los datos.

La mejor solución dependerá probablemente de las características especiales de los datos (que mencionar que los datos son escasos, por lo que debe intentar explotar que de alguna manera). Mi respuesta sería eficaz si la diferencia en la longitud de los dos vectores se correlaciona con la distancia entre ellos (por ejemplo, la distancia de Hamming). Usted puede comprobar para ver si esto es cierto, sobre una muestra aleatoria de sus datos haciendo un simple diagrama de dispersión.

En general, su mejor apuesta sería la de determinar alguna función escalar que es un buen indicador de cómo de similares dos entradas, a continuación, ordenar los datos por la función y, a continuación, buscar localmente cuando se le da una nueva entrada. Mi primera idea sería intentar longitud del vector como esa función, pero hay una buena probabilidad de que usted será capaz de encontrar uno mejor por jugar con sus datos.

Answer 4

Hay un número de no-euclidiana medidas de distancia, algunos de los cuales se utilizan específicamente para datos binarios. Dos de distancia-las medidas son: 1) Simple Coincidencia Coeficiente; 2) El Coeficiente De Jaccard. Tienen diferentes fortalezas y debilidades. En la simple coincidencia de coeficiente de mutuo ausencias y presencias contribuir a la similitud, aunque el coeficiente de Jaccard es bueno para centrarse en la mutua presencia.

Usted puede buscar las medidas más específicamente si quieres (Simple Coincidencia y de Jaccard se resumen a continuación: http://stat.ethz.ch/education/semesters/ss2012/ams/slides/v4.2.pdf)

Si usted está usando R, la función "dist" en el paquete de base tiene la simple coincidencia de coeficiente (conocido como "binario simétrico") y el comando "vegdist" en el paquete "vegano" tiene el índice de Jaccard.

(Edit): me acabo de enterar de algo, que, dependiendo de su hardware, podría producir algún beneficio. Si tienes una NVIDIA de varios núcleos de la GPU (que es bastante común), el paquete 'rpud' tiene una función rpuDist (), que calcula el número de la distancia, las métricas de uso de la GPU con una gran mejoría, como se muestra aquí: [http://www.r-tutor.com/gpu-computing/clustering/distance-matrix] http://www.r-tutor.com/gpu-computing/clustering/distance-matrix Yo no lo he probado, y con un conjunto de datos de su tamaño podría ser otro de los cuellos de botella, pero podría ser vale la pena tener un ir en él. También, parece que este, y otro paquete (gputools) sólo están disponibles en Linux, así que es otra de las limitaciones...

Espero que ayude!