Comment stocker des ensembles, pour trouver rapidement des modèles similaires?

StackOverflow https://stackoverflow.com/questions/462563

Question

(Ce n’est pas un devoir ni une question de travail. C’est juste mon intérêt personnel / ma profession et mon sens de la fiction. Mais je suis intéressé par un bon algorithme ou une bonne structure de données.)

Supposons que je gérerais un site de rencontre. Et mon trait particulier serait que les célibataires étaient assortis aux goûts du film . (Pourquoi pas?)

Dans ce cas, il me faudrait un moyen de stocker les classements de film pour chaque utilisateur. (Jusqu'à présent, pas de problème.) Et il me faudrait une structure de données pour trouver le meilleur utilisateur. La distance entre deux modèles de goût correspond à la distance moyenne entre toutes les notes attribuées par les deux utilisateurs.

Exemple 

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

Distance (X, Z) = moy (abs (9-9) + abs (1-4)) = 1,5

Distance (Y, Z) = moy (abs (4-6) + abs (6-4) + abs (8-7)) = 1,666

Donc, M. X s’adapte légèrement mieux à Mme Z que M. Y.

J'aime la soulution qui ...

  • ... n'a pas besoin de nombreuses opérations sur la base de données
  • ... n'a pas besoin de gérer beaucoup de données
  • ... courez vite
  • ... fournissez la meilleure correspondance
  • Ok, je pourrais peut-être aussi envisager de bonnes approximations.

Essayez de garder à l’esprit que cela devrait également fonctionner avec des milliers de films possibles, des utilisateurs ne évaluant qu’environ 20 à 50 films et des milliers d’utilisateurs.

(Puisqu'il s'agit d'un casse-tête mental et non d'un réel problème, les arrêts de travail ne vous aident pas vraiment.)

Quel serait votre algorithme de recherche ou structure de données?

Était-ce utile?

La solution

Cela ressemble beaucoup au défi Prix Netflix , plus précisément à la première moitié de l'approche la plus populaire. . Les implémentations possibles de ce que vous essayez de faire sont nombreuses et variées. Aucune d’entre elles n’est exceptionnellement efficace, et la métrique L1 n’est pas une très bonne option pour des corrélations fiables.

Autres conseils

On dirait que vous recherchez le voisin le plus proche dans l'espace du film. Et votre fonction de distance est la métrique L1 Vous pouvez probablement utiliser un index spatial quelconque. Vous pouvez peut-être utiliser les techniques du filtrage collaboratif . 

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 complexité sera O (n 1.5 ) plutôt que O (n 2 ), car il y aura des comparaisons n avec sqrt (n) films (moyenne de films remplis ensemble par paire).

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top