Similitud entre los usuarios basados ​​en votos

Question

Digamos que tengo un conjunto de usuarios, un conjunto de canciones, y un conjunto de votos en cada canción:

=========== =========== ======= 
User  Song  Vote 
=========== =========== ======= 
user1  song1  [score] 
user1  song2  [score] 
user1  song3  [score] 
user2  song1  [score] 
user2  song2  [score] 
user2  song3  [score] 
user3  song1  [score] 
user3  song2  [score] 
user3  song3  [score] 
user-n  song-n  [score] 
=========== =========== ======= 

cuál es la forma más eficiente para calcular la similitud de usuario basada en canción-votos? ¿Hay una mejor manera de iterar sobre cada usuario y cada voto para cada canción?

Answer 1

Hay dos sistemas de medición comunes que se pueden utilizar para encontrar similitudes entre los usuarios:

1. distancia euclídea, eso es exactamente lo que eres pensamiento: imagina un gráfico n-dimensional que tiene para cada eje una canción que es revisada por dos usuarios involucrados (u1 y * u2) y el valor en su eje es el puntaje. Se puede calcular fácilmente similitud utilizando la fórmula:

   para cada canción revisado por U1 y U2, calcular pow(u1.song.score - u2.song.score, 2) y añadir todos juntos en sum_of_powers. El coeficiente de similitud viene dado por 1/1 + (sqrt(sum_of_powers)).

2. Pearson Correlation (o coeficiente de correlación): es un mejor enfoque que determina cuánto se relacionan dos conjuntos de datos uno con otro. Este enfoque utiliza fórmulas más complejas y un poco de fondo de estadísticas, verifíquelo aquí: wiki. Tendrás un gráfico para cada par de usuarios, luego trazar puntos de acuerdo a los puntajes ... por ejemplo, si aSong ha sido votado 2 desde u1 y 4 desde u2 trazará el punto (2,4) (asumiendo que usuario1 es eje xy u2 es el eje y)

Solo para aclarar, se utiliza la regresión lineal encontrar dos coeficientes A y B, que describen la línea que minimiza la distancia desde todos los puntos de la gráfica. Esta línea tiene esta fórmula: y = Ax + B. Si dos conjuntos son puntos similares deben estar cerca de la diagonal principal, entonces A debe tender a 1 mientras que B a 0. No asuma esta explicación como completa o como referencia porque carece de solidez y formalismo matemático típico, solo para darle una idea.

EDIT: existen como escritas por otros, más complejos algoritmos a los datos del cluster, como k-medias, pero me sugieren que usted comience a partir de las fáciles (en realidad lo que necesitará algo más difícil justo cuando se da cuenta de que los resultados son no es suficiente).

Answer 2

Debería poder encontrar un buen algoritmo en este libro: The Algorithm Design Manual por Steven Skiena.

El libro tiene un montón de algoritmos para diversos fines. Usted quiere un algoritmo de agrupamiento de gráficos, creo. No tengo a mano mi copia del libro, así que no puedo buscarlo.

Una búsqueda rápida en Google encontró una página de Wikipedia: http://en.wikipedia.org/wiki/Cluster_analysis Quizás eso ayude, pero creo que el libro explica los algoritmos más claramente.

Answer 3

Recomiendo el libro Programming Collective Intelligence de Toby Segaran. El Capítulo 3 describe diferentes métodos de agrupación como Hierarchical Clustering y K-means Clustering.

El código fuente de los ejemplos está disponible here

Answer 4

Si quiere los resultados más precisos, entonces no, tendría que repetir todo.

Si su base de datos es lo suficientemente grande, puede tomar un muestreo estadístico, por ejemplo, tomando entre 1,000 -10,000 usuarios y haciendo coincidir con eso.

También sería mejor agregar algunas tablas más a la base de datos, almacenar los resultados, y solo actualizarlo cada cierto tiempo, en lugar de calcular esto sobre la marcha.

Answer 5

Ilya Grigorik hizo una serie de algoritmos de recomendación, aunque se estaba centrando en Ruby. Parece estar en la sección de aprendizaje automático en su archives, pero no hay un enlace de sección directa.

Answer 6

Creo que a mucha gente aquí le falta la simplicidad de la pregunta. Él no dijo nada sobre la creación de un sistema de predicción de clasificación. Solo quiere calcular la similitud entre el comportamiento de calificación de cada usuario y el comportamiento de calificación de cada uno de los otros usuarios. El coeficiente de correlación de Pearson da exactamente eso. Sí, debe iterar sobre cada par de usuario/usuario.

EDIT:

Después de pensar en esto un poco más:

Pearson es grande si desea que la similitud entre los gustos de dos usuarios, pero no su nivel de 'opinionatedness' ... un usuario que califica una serie de canciones 4, 5 y 6 que se correlacionan perfectamente con otro usuario que califica las mismas canciones 3, 6 y 9. En otras palabras, tienen el mismo "sabor" (clasificarían las canciones en el mismo orden)), pero el segundo usuario es mucho más obstinado. En otras palabras, el coeficiente de correlación trata cualquier dos vectores de calificación con una relación lineal como igual.

Sin embargo, si desea la similitud entre las calificaciones reales que los usuarios dieron a cada canción, debe usar el error cuadrático medio entre los dos vectores de calificación. Esta es una métrica puramente basada en la distancia (las relaciones lineales no juegan en la puntuación de similitud), por lo que los usuarios de 4,5,6 y 3,6,9 no tendrían una puntuación de similitud perfecta.

La decisión se reduce a lo que entendemos por "similar" ...

Eso es todo.

Answer 7

Si quiere hacerlo de una manera aproximada sin visitar todos los registros, puede usar el Coeficiente de Jaccard. Probablemente necesite alguna adaptación si quiere considerar los puntajes. Pero creo que esas son las mejores soluciones si su sistema es demasiado grande y no tiene el tiempo para verificar todos los registros.