Os vizinhos mais próximos pesquisam dados dimensionais muito altos

Eu tenho uma grande matriz esparsa de usuários e itens que eles gostam (na ordem de 1 milhão de usuários e 100 mil itens, com um nível muito baixo de escassez). Estou explorando maneiras pelas quais eu poderia executar a pesquisa kNN nele. Dado o tamanho do meu conjunto de dados e alguns testes iniciais que realizei, suponho que o método que utilizarei precisará ser paralelo ou distribuído. Portanto, estou considerando duas classes de soluções possíveis: uma que está disponível (ou implementável de uma maneira razoavelmente fácil) em uma única máquina multicore, a outra em um cluster Spark, ou seja, como um programa MapReduce. Aqui estão três idéias gerais que eu considerei:

• Assumindo uma métrica de similaridade de cosseno, execute a multiplicação completa da matriz normalizada por sua transposição (implementada como uma soma de produtos externos)
• Usando hash sensível à localidade (LSH)
• Reduzindo primeiro a dimensionalidade do problema com um PCA

Gostaria de receber quaisquer pensamentos ou conselhos sobre possíveis outras maneiras pelas quais eu poderia resolver esse problema.

Espero que os seguintes recursos possam lhe trazer idéias adicionais para solucionar o problema:

1) Artigo de pesquisa "Algoritmos de junção eficiente entre vizinhos mais próximos de K para dados esparsos de alta dimensão" : http://arxiv.org/abs/1011.2807

2) Documento do projeto de classe "Sistema de Recomendação Baseado em Filtragem Colaborativa" (Stanford University): http://cs229.stanford.edu/proj2008/Wen-RecommendationSystemBasedOnCollaborativeFiltering.pdf

3) Projeto para o Concurso de Prêmios Netflix ( baseado em k-NN ) : http://cs.carleton.edu/cs_comps/0910/netflixprize/final_results/knn/index.html

4) Artigo de pesquisa "Hubs no espaço: vizinhos mais próximos populares em dados de alta dimensão" sobre a maldição do fenômeno da dimensionalidade e sua relação com o aprendizado de máquina , em geral, e o algoritmo k-NN , em particular: http://jmlr.org /papers/volume11/radovanovic10a/radovanovic10a.pdf

5) Software para classificação esparsa de k-NN (gratuito, mas parece não ser de código aberto - pode esclarecer os autores): http://www.autonlab.org/autonweb/10408.html

6) Vários tópicos de discussão no 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 (ao contrário de todas as discussões anteriores, às quais se refere Python, esta se refere ao Recossistema)

7) Preste atenção ao GraphLab , uma estrutura paralela de código aberto para aprendizado de máquina ( http://select.cs.cmu.edu/code/graphlab ), que suporta cluster paralelo via MapReducemodelo: http: //select.cs.cmu. edu / code / graphlab / clustering.html

Você também pode verificar minha resposta aqui no Data Science StackExchange, em regressão esparsa, para obter links para Rpacotes e CRAN Task Viewpáginas relevantes : /datascience//a/918/2452 .

Se você estiver trabalhando na filtragem colaborativa, deve apresentar o problema como uma aproximação de matriz de baixo escalão, em que ambos os usuários são itens que são co-incorporados no mesmo espaço de baixa dimensionalidade. A pesquisa por similaridade será muito mais simples. Eu recomendo usar LSH, como você sugeriu. Outro caminho frutífero para a redução da dimensionalidade ainda não mencionado é a projeção aleatória .

Você deve usar: PySparNN , uma implementação recente do Facebook em python, que é muito rápida. Também é fácil de usar.