Najbliżsi sąsiedzi szukają danych o bardzo dużych wymiarach

Mam dużą rzadką macierz użytkowników i przedmiotów, które lubią (rzędu 1 mln użytkowników i 100 000 przedmiotów, z bardzo niskim poziomem rzadkości). Badam sposoby, w jakie mogę na nim przeprowadzić wyszukiwanie kNN. Biorąc pod uwagę rozmiar mojego zbioru danych i niektóre wstępne testy, które przeprowadziłem, zakładam, że metoda, której użyję, będzie musiała być równoległa lub rozproszona. Rozważam więc dwie klasy możliwych rozwiązań: jedno, które jest albo dostępne (lub możliwe do wdrożenia w dość łatwy sposób) na pojedynczej maszynie wielordzeniowej, a drugie na klastrze Spark, tj. Jako program MapReduce. Oto trzy ogólne pomysły, które rozważałem:

• Zakładając metrykę podobieństwa cosinus, wykonaj pełne pomnożenie znormalizowanej macierzy przez jej transpozycję (zaimplementowaną jako suma produktów zewnętrznych)
• Korzystanie z mieszania wrażliwego na lokalizację (LSH)
• Zmniejszenie najpierw wymiarów problemu dzięki PCA

Byłbym wdzięczny za wszelkie przemyślenia lub porady dotyczące możliwych innych sposobów rozwiązania tego problemu.

Mam nadzieję, że następujące zasoby mogą dostarczyć ci dodatkowych pomysłów na rozwiązanie problemu:

1) Artykuł badawczy „Efektywne algorytmy łączenia najbliższych sąsiadów dla wielkoformatowych rzadkich danych” : http://arxiv.org/abs/1011.2807

2) Dokument z zajęć „System rekomendacji oparty na filtrowaniu grupowym” (Uniwersytet Stanforda): http://cs229.stanford.edu/proj2008/Wen-RecommendationSystemBasedOnCollaborativeFiltering.pdf

3) Projekt konkursu na nagrodę Netflix (na podstawie k-NN ) : http://cs.carleton.edu/cs_comps/0910/netflixprize/final_results/knn/index.html

4) Artykuł badawczy „Hubs in Space: Popular Neighbors in High-Dimensional Data” na temat klątwy zjawiska wymiarowości i jej związku z uczeniem maszynowym , a zwłaszcza algorytmu k-NN , w szczególności: http://jmlr.org /papers/volume11/radovanovic10a/radovanovic10a.pdf

5) Oprogramowanie do rzadkiej klasyfikacji k-NN (bezpłatne, ale wydaje się, że nie jest open source - może wyjaśnić z autorami): http://www.autonlab.org/autonweb/10408.html

6) Kilka wątków dyskusyjnych na temat 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 (w przeciwieństwie do wszystkich poprzednich dyskusji, które odnoszą się Python, ta dotyczy Rekosystemu)

7) Zwróć uwagę na GraphLab , równoległą platformę open source do uczenia maszynowego ( http://select.cs.cmu.edu/code/graphlab ), która obsługuje równoległe tworzenie klastrów za pomocą MapReducemodelu: http: //select.cs.cmu. edu / code / graphlab / clustering.html

Możesz również sprawdzić moją odpowiedź tutaj na Data Science StackExchange na temat rzadkiej regresji w poszukiwaniu linków do odpowiednich Rpakietów i CRAN Task Viewstron: /datascience//a/918/2452 .

Jeśli pracujesz nad wspólnym filtrowaniem, powinieneś postawić problem jako przybliżenie macierzy niskiego rzędu, w którym obaj użytkownicy są elementami, są osadzeni w tej samej przestrzeni o niskiej wymiarowości. Wyszukiwanie podobieństwa będzie wówczas znacznie prostsze. Polecam używanie LSH, jak zasugerowałeś. Inną owocną drogą do zmniejszenia wymiarów, o której jeszcze nie wspomniano, jest losowa projekcja .

Powinieneś użyć: PySparNN , najnowszej implementacji Facebooka w pythonie, która jest cholernie szybka. Jest również łatwy w użyciu.