¿Cómo almacenar conjuntos, para encontrar patrones similares rápidamente?

Question

(Esto no es tarea ni problema de trabajo. Es solo mi interés / ocupación personal y completamente ficticio. Pero estoy interesado en un buen algoritmo o estructura de datos).

Asumamos que diría un sitio de citas. Y mi función especial sería que los singles fueron combinados con el gusto de la película . (¿Por qué no?)

En ese caso, necesitaría una forma de almacenar las clasificaciones de películas para cada usuario. (Hasta ahora no hay problema.) Y necesitaría una estructura de datos para encontrar el mejor usuario. La distancia entre dos patrones de sabor sería la distancia promedio entre todas las calificaciones que hicieron ambos usuarios.

Ejemplo

movies   A B C D E F G H I J K L M ...
user Xm  9 5   1   1   5
user Ym      4 6 1         8
user Zf  9   6 4           7

Distancia (X, Z) = promedio (abs (9-9) + abs (1-4)) = 1.5

Distancia (Y, Z) = promedio (abs (4-6) + abs (6-4) + abs (8-7)) = 1.666

Entonces, el Sr. X se ajusta un poco mejor a la Sra. Z que el Sr. Y.

Me gusta la soulution que ...

• ... no necesita muchas operaciones en la base de datos
• ... no es necesario manejar una gran cantidad de datos
• ... corre rápido
• ... entrega la mejor combinación
• Ok, tal vez yo también consideraría buenas aproximaciones.

Trate de tener en cuenta que esto también debería funcionar con miles de películas posibles, usuarios que solo califican entre 20 y 50 películas y miles de usuarios.

(Debido a que este es un rompecabezas mental y no un problema real, los entornos de trabajo realmente no están ayudando).

¿Cuál sería su algoritmo de búsqueda o estructura de datos?

Answer 1

Suena muy parecido al Netflix Prize desafío, más específicamente la primera mitad del enfoque más popular . Las posibles implementaciones de lo que está intentando hacer son numerosas y variadas. Ninguno de ellos es excepcionalmente eficiente, y la métrica L1 no es una opción particularmente buena para correlaciones confiables.

Answer 2

Parece que está buscando el vecino más cercano en el espacio de la película. Y su función de distancia es la métrica L1 . Probablemente pueda usar un índice espacial de algún tipo. Tal vez pueda usar técnicas de filtrado colaborativo .

Answer 3

CREATE TABLE data (user INTEGER, movie INTEGER, rate INTEGER);

SELECT  other.user, AVG(ABS(d1.rate - d2.rate)) AS distance
FROM    data me, data other
WHERE   me.user = :user
    AND other.user <> me.user
    AND other.movie = me.movie
GROUP BY
    other.user
ORDER BY
    distance

La complejidad será O (n ^1.5 )) en lugar de O (n ² ), ya que habrá n comparaciones con sqrt (n) películas (promedio de películas completadas por cada par).