Comment trouver des utilisateurs similaires en utilisant leurs centres d'intérêt

Question

J'essaie de créer un système qui serait capable de trouver des utilisateurs avec des films/livres/intérêts/etc préférés similaires, comme voisins sur last.fm. Les utilisateurs partageant le plus d'intérêts mutuels auraient la correspondance la plus élevée et seraient affichés dans les profils d'utilisateurs (5 meilleures correspondances environ).

Y a-t-il de manière raisonnablement rapide pour cela? La solution évidente serait de créer une table avec des identifiants d'utilisateur et des identifiants d'intérêts et de comparer un utilisateur avec tous les autres utilisateurs, mais cela prendrait une éternité sur une table avec ... disent des millions d'utilisateurs ayant chacun 20 intérêts.

Je suppose qu'une solution efficace existe, car last.fm fonctionne très bien. Je préférerais utiliser une base de données SQL commune comme mySQL ou pgSQL, mais tout serait possible.

Merci pour vos suggestions.

---

MISE À JOUR:
Comme il se trouve, le plus gros problème est de trouver les plus proches voisins dans les bases de données SQL, comme aucun de ceux open source prend en charge ce type de recherche. Donc, ma solution serait de modifier ANN pour l'exécuter en tant que service et l'interroger depuis PHP (en utilisant des sockets par exemple) - avoir des millions d'utilisateurs avec 7 dimensions en mémoire n'est pas vraiment un gros problème et ça fonctionne incroyablement vite.

Une autre solution pour les petits ensembles de données est cette simple requête:

SELECT b.user_id, COUNT(1) AS mutual_interests 
FROM `users_interests` a JOIN `users_interests` b ON (a.interest_id = b.interest_id) 
WHERE a.user_id = 5 AND b.user_id != 5 
GROUP BY b.user_id ORDER BY mutual_interests DESC, b.user_id ASC 

20-50ms avec 100K utilisateurs ayant chacun ~ 20 intérêts (10 000 intérêts possibles) en moyenne

Answer 1

Vous voulez résoudre le le plus proche problème du plus proche voisin. Encodez les caractéristiques des utilisateurs en tant que vecteur dans un espace, puis trouvez approximativement l'autre utilisateur le plus proche dans cet espace.

Quel espace exactement et quelle métrique de distance que vous voulez utiliser sont probablement des choses à évaluer expérimentalement en fonction de vos données. Heureusement, il existe un paquet C++ que vous pouvez utiliser pour résoudre ce problème avec différents métriques et algorithmes pour répondre à vos besoins: http://www.cs.umd.edu/~mount/ANN/

Éditer: Il est vrai que le temps d'exécution ici dépend du nombre de fonctionnalités. Mais il y a un théorème pratique en géométrie de haute dimension qui dit que si vous avez n points dans des dimensions arbitrairement hautes, et que vous vous souciez seulement des distances approximatives, vous pouvez les projeter dans les dimensions O (log n) sans perte. Voir ici (http://en.wikipedia.org/wiki/Johnson-Lindenstrauss_lemma). (Une projection aléatoire est effectuée en multipliant vos points par une matrice de valeurs aléatoires + 1/-1). Notez que log (1,000,000) = 6, par exemple.