Como armazenar conjuntos, para encontrar padrões semelhantes rápido?

Question

(Este não é um trabalho de casa e nenhum problema de trabalho. É apenas o meu interesse pessoal / ocupação e completamente fictícia. Mas eu estou interessado em um bom algoritmo ou estrutura de dados.)

Vamos supor que eu iria correr um site de namoro. E a minha característica especial seria que os singles foram acompanhado por gosto filme . (Por que não?)

Nesse caso, eu precisaria de uma maneira de armazenar as classificações de filmes para cada usuário. (Até agora não há problema.) E eu precisaria de uma estrutura de dados para encontrar o melhor usuário montagem. A distância entre dois padrões de gosto seria a distância média entre todas as classificações que ambos os usuários feitas.

Exemplo

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

Distância (X, Z) = avg (abs (9-9) + abs (4/1)) = 1,5

Distância (Y, Z) = avg (abs (4-6) + abs (6-4) + abs (8-7)) = 1.666

Assim, o Sr. X se encaixa um pouco melhor com a Sra Z, que o Sr. Y faz.

eu como soulution que ...

• ... não precisa de muitas operações no banco de dados
• ... não precisa lidar com uma grande quantidade de dados
• ... correr rápido
• ... oferecer a melhor harmonização
• Ok, talvez eu consideraria boas aproximações também.

Tente manter em mente que este também deve trabalhar com milhares de possíveis filmes, os usuários que a taxa de apenas cerca de 20-50 filmes e milhares de usuários.

(Porque este é um quebra-cabeça mental e não um problema real, o trabalho a arrounds não são realmente ajudando.)

Qual seria o seu algoritmo de busca ou estrutura de dados?

Answer 1

Soa muito como desafio a href="http://www.netflixprize.com/index" rel="nofollow noreferrer"> Prêmio , mais especificamente a primeira metade da abordagem mais popular . Os possíveis implementações do que você está tentando fazer são numerosos e variados. Nenhum deles são excepcionalmente eficiente, eo L1 métrica não é uma opção particularmente bom para as correlações confiáveis.

Answer 2

Parece que você está procurando o vizinho mais próximo no espaço filme. E sua função de distância é a L1 métrica . Provavelmente, você pode usar um índice espacial de algum tipo. Talvez você pode usar técnicas de colaborativo filtragem .

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

Complexidade será O (n ^1,5 )) em vez de O (n ² ), uma vez que haverá comparações n para filmes sqrt(n) (média de filmes preenchido em conjunto pela cada par).