Les voisins les plus proches recherchent des données dimensionnelles très élevées

J'ai une grande matrice clairsemée d'utilisateurs et d'articles qu'ils aiment (de l'ordre de 1 million d'utilisateurs et de 100 000 articles, avec un très faible niveau de rareté). J'explore les façons dont je pourrais effectuer une recherche sur kNN. Compte tenu de la taille de mon jeu de données et de certains tests initiaux que j'ai effectués, je suppose que la méthode que j'utiliserai devra être parallèle ou distribuée. J'envisage donc deux classes de solutions possibles: l'une qui est soit disponible (ou implémentable d'une manière raisonnablement facile) sur une seule machine multicœur, l'autre sur un cluster Spark, c'est-à-dire en tant que programme MapReduce. Voici trois grandes idées que j'ai examinées:

• En supposant une métrique de similitude cosinus, effectuez la multiplication complète de la matrice normalisée par sa transposition (implémentée comme une somme de produits externes)
• Utilisation du hachage sensible à la localité (LSH)
• Réduire d'abord la dimensionnalité du problème avec un PCA

J'apprécierais toute réflexion ou conseil sur d'autres manières possibles de résoudre ce problème.

J'espère que les ressources suivantes pourraient vous apporter des idées supplémentaires pour résoudre le problème:

1) Document de recherche "Algorithmes efficaces de jointure K-plus proche voisin pour les données clairsemées de haute dimension" : http://arxiv.org/abs/1011.2807

2) Document de projet de classe "Système de recommandation basé sur le filtrage collaboratif" (Université de Stanford): http://cs229.stanford.edu/proj2008/Wen-RecommendationSystemBasedOnCollaborativeFiltering.pdf

3) Projet pour le concours du prix Netflix ( basé sur k-NN ) : http://cs.carleton.edu/cs_comps/0910/netflixprize/final_results/knn/index.html

4) Document de recherche "Hubs in Space: Popular Nearest Neighbours in High-Dimensional Data" sur la malédiction du phénomène de dimensionnalité et sa relation avec l'apprentissage automatique , en général, et l' algorithme k-NN , en particulier: http://jmlr.org /papers/volume11/radovanovic10a/radovanovic10a.pdf

5) Logiciel pour la classification clairsemée de k-NN (gratuit, mais ne semble pas être open source - pourrait clarifier avec les auteurs): http://www.autonlab.org/autonweb/10408.html

6) Plusieurs fils de discussion sur StackOverflow :

• /programming/20333092/knn-with-big-sparse-matrices-in-python
• /programming/18164348/efficient-nearest-neighbour-search-for-sparse-matrices
• /programming/21085990/scipy-sparse-distance-matrix-scikit-or-scipy
• /programming/10472681/handling-incomplete-data-data-sparsity-in-knn
• /programming/5560218/computing-sparse-pairwise-distance-matrix-in-r (contrairement à toutes les discussions précédentes, auxquelles il est fait référence Python, celle-ci se réfère à l' Récosystème)

7) Faites attention à GraphLab , un framework parallèle open source pour l'apprentissage automatique ( http://select.cs.cmu.edu/code/graphlab ), qui prend en charge le clustering parallèle via le MapReducemodèle: http: //select.cs.cmu. edu / code / graphlab / clustering.html

Vous pouvez également consulter ma réponse ici sur Data Science StackExchange sur la régression clairsemée pour des liens vers des Rpackages et des CRAN Task Viewpages pertinents : /datascience//a/918/2452 .

Si vous travaillez sur le filtrage collaboratif, vous devez poser le problème comme une approximation de matrice de bas rang, dans laquelle les deux utilisateurs sont des éléments co-intégrés dans le même espace de faible dimensionnalité. La recherche de similarité sera alors beaucoup plus simple. Je recommande d'utiliser LSH, comme vous l'avez suggéré. Une autre avenue fructueuse pour la réduction de la dimensionnalité non encore mentionnée est la projection aléatoire .

Vous devriez utiliser: PySparNN , une implémentation récente de Facebook en python qui est sanglant rapidement. Il est également facile à utiliser.