Générer des «voisins» pour les utilisateurs en fonction de la cote

Question

Je cherche des techniques pour générer des «voisins» (personnes ayant le même goût) pour les utilisateurs d'un site sur lequel je travaille; quelque chose de similaire à la façon dont last.fm fonctionne.

Actuellement, j'ai une fonction de compatibilité pour les utilisateurs qui pourraient entrer en jeu. Il classe les utilisateurs sur 1) a évalué les éléments similaires 2) a évalué l'élément de manière similaire. La fonction pèse le point 2 supérieur et ce serait le plus important si je devais utiliser un seul de ces facteurs lors de la génération de «voisins». Une idée que j'ai eu serait de simplement calculer la compatibilité de chaque combinaison d'utilisateurs et de sélectionner les utilisateurs les mieux notés pour être les voisins de l'utilisateur. L'inconvénient de ceci est que le nombre d'utilisateurs augmente, ce processus peut prendre beaucoup de temps. Pour seulement 1000 utilisateurs, il faut 1000C2 (0.5 * 1000 * 999 = = 499 500) appels à la fonction de compatibilité, ce qui peut être très lourd sur le serveur aussi. Donc, je cherche des conseils, des liens vers des articles, etc sur la meilleure façon de réaliser un système comme celui-ci.

Answer 1

Le problème semble être "problèmes de classification". Oui, il y a tellement de solutions et d'approches.

Pour démarrer l'enregistrement d'exploration ceci: http://en.wikipedia.org/wiki/Statistical_classification

Answer 2

Dans le livre Programmation Intelligence Collective
http://oreilly.com/catalog/9780596529321

Chapitre 2 « Faire des recommandations » fait un très bon travail décrivant les méthodes de recommander des articles à des personnes basé sur les similitudes entre les utilisateurs. Vous pouvez utiliser les algorithmes de similarité pour trouver les «voisins» que vous recherchez. Le chapitre est disponible sur la recherche de google livre ici:
http://books.google.com/books?id=fEsZ3Ey-Hq4C&printsec=frontcover

Answer 3

Avez-vous entendu parler de kohonen networks?

C'est un algorithme d'auto-apprentissage qui regroupe des variables similaires dans des intervalles similaires. Bien que la plupart des sites comme celui que je vous lie à affiche le net comme bidimensionnel, il est peu impliqué dans l'extension de l'algorithme dans un hypercube à plusieurs dimensions. Avec une telle structure de données, trouver et mémoriser des voisins ayant des goûts similaires est trivial car des utilisateurs similaires devraient être stockés dans des emplacements similaires (presque comme un code de hachage inverse). Cela réduit votre problème à trouver les variables qui définiront la similarité et établiront des distances entre les valeurs énumératives possibles, comme par exemple classique et acoustique sont proches tandis que le death metal et le reggae sont assez éloignés (du moins dans mon opinion) Soit dit en passant, afin de trouver de bonnes variables de division, le meilleur algorithme est decision tree. Les nœuds les plus proches de la racine seront les variables les plus importantes pour établir la «proximité».

Answer 4

Il semble que vous ayez besoin de lire à propos de clustering algorithms. L'idée générale est qu'au lieu de comparer chaque point avec chaque autre point chaque fois que vous les divisez en groupes de points similaires. Ensuite, le voisinage peut être tous les points dans le même groupe. Le nombre/taille des clusters est généralement un paramètre de l'algorithme de clustering.

Vous pouvez trouver un video about clustering dans la série de Google sur cluster computing and mapreduce.

Answer 5

Les problèmes de performances peuvent être considérablement atténués si vous considérez cela comme un problème de génération/traitement par lots plutôt que comme une requête en temps réel.

Le graphique peut être calculé statiquement puis mis à jour de manière latente par ex. horaire, quotidien, etc. pour ensuite générer des bords et un stockage optimisés pour une requête d'exécution, par ex. top 10 utilisateurs similaires pour chaque utilisateur. +12 pour la programmation de l'intelligence collective - c'est très instructif - je souhaite que ce ne soit pas (ou je l'étais!) Orienté sur Python, mais toujours bon.

Answer 6

Assurez-vous de regarder Collaborative Filtering. De nombreux systèmes de recommandation utilisent le filtrage collaboratif pour suggérer des éléments aux utilisateurs. Ils le font en trouvant des «voisins», puis en suggérant des articles que vos voisins ont très bien notés mais que vous n'avez pas notés. Vous pourriez aller jusqu'à trouver des voisins, et qui sait, peut-être que vous voudrez des recommandations à l'avenir.

GroupLens est un laboratoire de recherche de l'Université du Minnesota qui étudie les techniques de filtrage collaboratif. Ils ont une tonne de recherches publiées ainsi que quelques exemples de jeux de données.

Le Netflix Prize est un concours pour déterminer qui peut le plus efficacement résoudre ce genre de problème. Suivez les liens de leur LeaderBoard. Quelques-uns des concurrents partagent leurs solutions.

En ce qui concerne une solution peu coûteuse informatiquement, vous pouvez essayer ceci:

• Créer des catégories pour vos articles. Si nous parlons de musique, ils peuvent être classiques, rock, jazz, hip-hop ... ou aller plus loin: Grindcore, Math Rock, Riot Grrrl ...
• Maintenant, chaque fois qu'un utilisateur évalue un objet, retrouvez ses notes au niveau de la catégorie. Donc, vous savez que l'utilisateur A aime Honky Tonk et Acid House parce qu'ils donnent souvent à ces articles des notes élevées. La fréquence et la force sont probablement importantes pour le score global de votre catégorie.
• Quand il est temps de trouver des voisins, au lieu de passer en revue toutes les évaluations, il suffit de rechercher des scores similaires dans les catégories.

Cette méthode ne serait pas aussi précise mais elle est rapide.

Cheers.

Answer 7

Ce dont vous avez besoin est un algorithme de clustering qui regrouperait automatiquement les utilisateurs similaires. La première difficulté que vous rencontrez est que la plupart des algorithmes de clustering s'attendent à ce que les éléments qu'ils regroupent soient représentés en tant que points dans un espace euclidien. Dans votre cas, vous n'avez pas les coordonnées des points. Au lieu de cela, vous pouvez calculer la valeur de la fonction "similarité" entre des paires d'entre eux.

Une bonne possibilité ici est d'utiliser spectral clustering, qui nécessite précisément ce que vous avez: une matrice de similarité. L'inconvénient est que vous devez toujours calculer votre fonction de compatibilité pour chaque paire de points, i. e. l'algorithme est O (n^2).

Si vous avez absolument besoin d'un algorithme plus rapide que O (n^2), vous pouvez essayer une approche appelée dissimilarity spaces. L'idée est très simple. Vous inversez votre fonction de compatibilité (par exemple en prenant sa réciproque) pour le transformer en une mesure de dissimilitude ou de distance. Ensuite, vous comparez chaque élément (utilisateur, dans votre cas) à un ensemble d'éléments prototypes et traitez les distances résultantes en tant que coordonnées dans un espace. Par exemple, si vous avez 100 prototypes, chaque utilisateur serait représenté par un vecteur de 100 éléments, i. e. par un point dans l'espace 100-dimensionnel.Vous pouvez ensuite utiliser n'importe quel algorithme de clustering standard, tel que K-means. La question est maintenant de savoir comment choisir les prototypes et combien en avez-vous besoin. Divers heuristiques ont été essayées, cependant, voici un dissertation qui soutient que le choix aléatoire des prototypes peut être suffisant. Il montre des expériences dans lesquelles l'utilisation de 100 ou 200 prototypes choisis au hasard a donné de bons résultats. Dans votre cas, si vous avez 1000 utilisateurs, et que vous en choisissez 200 pour être des prototypes, vous devrez évaluer votre fonction de compatibilité 200 000 fois, ce qui représente une amélioration d'un facteur 2,5 par rapport à chaque paire. Le véritable avantage, cependant, est que pour 1 000 000 d'utilisateurs, 200 prototypes seraient encore suffisants, et vous auriez besoin de faire 200 000 000 comparaisons, plutôt que 500 000 000 000 une amélioration d'un facteur 2500. Ce que vous obtenez est l'algorithme O (n) mieux que O (n^2), malgré un facteur constant potentiellement important.