Factor in the neighbors: Scalable and accurate collaborative filtering

Abstract

Recommender systems provide users with personalized suggestions for products or services. These systems often rely on collaborating filtering (CF), where past transactions are analyzed in order to establish connections between users and products. The most common approach to CF is based on neighborhood models, which originate from similarities between products or users. In this work we introduce a new neighborhood model with an improved prediction accuracy. Unlike previous approaches that are based on heuristic similarities, we model neighborhood relations by minimizing a global cost function. Further accuracy improvements are achieved by extending the model to exploit both explicit and implicit feedback by the users. Past models were limited by the need to compute all pairwise similarities between items or users, which grow quadratically with input size. In particular, this limitation vastly complicates adopting user similarity models, due to the typical large number of users. Our new model solves these limitations by factoring the neighborhood model, thus making both item-item and user-user implementations scale linearly with the size of the data. The methods are tested on the Netflix data, with encouraging results.

References

1. Adomavicius, G. and Tuzhilin, A. 2005. Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions. IEEE Trans. Knowl. Data Eng. 17, 6, 734--749.
2. Ali, K. and van Stam, W. 2004. Tivo: making show recommendations using a distributed collaborative filtering architecture. In Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York, NY, 394--401.
3. Bell, R. and Koren, Y. 2007a. Lessons from the Netflix Prize challenge. SIGKDD Explor. Newslet. 9, 2, 75--79.
4. Bell, R., Koren, Y., and Volinsky, C. 2007. Modeling relationships at multiple scales to improve accuracy of large recommender systems. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York, NY, 95--104.
5. Bell, R. M. and Koren, Y. 2007b. Scalable collaborative filtering with jointly derived neighborhood interpolation weights. In Proceedings of the IEEE International Conference on Data Mining (ICDM). IEEE Computer Society, 43--52.
6. Bennett, J. and Lanning, S. 2007. The Netflix Prize. In Proceedings of the KDD Cup and Workshop.
7. Blei, D. M., Ng, A. Y., and Jordan, M. I. 2003. Latent Dirichlet allocation. J. Mach. Learn. Res. 3, 993--1022.
8. Canny, J. 2002. Collaborative filtering with privacy via factor analysis. In Proceedings of the 25th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR'02). ACM, New York, NY, 238--245.
9. Das, A. S., Datar, M., Garg, A., and Rajaram, S. 2007. Google news personalization: Scalable online collaborative filtering. In Proceedings of the 16th International Conference on World Wide Web (WWW'07). ACM, New York, NY, 271--280.
10. Deerwester, S., Dumais, S. T., Furnas, G. W., Landauer, T. K., and Harshman, R. 1990. Indexing by latent semantic analysis. J. Amer. Soc. Inform. Sci. 41, 391--407.
11. Goldberg, D., Nichols, D., Oki, B. M., and Terry, D. 1992. Using collaborative filtering to weave an information tapestry. Comm. ACM 35, 12, 61--70.
12. Herlocker, J. L., Konstan, J. A., Borchers, A., and Riedl, J. 1999. An algorithmic framework for performing collaborative filtering. In Proceedings of the 22nd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR'99). ACM, New York, NY, 230--237.
13. Herlocker, J. L., Konstan, J. A., and Riedl, J. 2000. Explaining collaborative filtering recommendations. In Proceedings of the ACM Conference on Computer Supported Cooperative Work (CSCW'00). ACM, New York, NY, 241--250.
14. Hofmann, T. 2004. Latent semantic models for collaborative filtering. ACM Trans. Inform. Syst. 22, 1, 89--115.
15. Kim, D. and Yum, B.-J. 2005. Collaborative filtering based on iterative principal component analysis. Expert Syst. Appl. 28, 4, 823--830.
16. Koren, Y. 2008. Factorization meets the neighborhood: A multifaceted collaborative filtering model. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'08). ACM, New York, NY, 426--434.
17. Linden, G., Smith, B., and York, J. 2003. Amazon.com recommendations: Item-to-item collaborative filtering. IEEE Internet Comput. 7, 1, 76--80.
18. Marlin, B. M., Zemel, R. S., Roweis, S., and Slaney, M. 2007. Collaborative filtering and the missing at random assumption. In Proceedings of the 23rd Conference on Uncertainty in Artificial Intelligence (UAI).
19. Oard, D. and Kim, J. 1998. Implicit feedback for recommender systems. In Proceedings of the AAAI Workshop on Recommender Systems. 31--36.
20. Park, S.-T. and Pennock, D. M. 2007. Applying collaborative filtering techniques to movie search for better ranking and browsing. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'07). ACM, New York, NY, 550--559.
21. Paterek, A. 2007. Improving regularized singular value decomposition for collaborative filtering. In Proceedings of KDD Cup and Workshop.
22. Piatetsky, G. 2007. Interview with Simon Funk. SIGKDD Explor. Newsl. 9, 1, 38--40.
23. Salakhutdinov, R., Mnih, A., and Hinton, G. 2007. Restricted Boltzmann machines for collaborative filtering. In Proceedings of the 24th International Conference on Machine Learning (ICML'07). ACM, New York, NY, 791--798.
24. Sarwar, B., Karypis, G., Konstan, J., and Reidl, J. 2001. Item-based collaborative filtering recommendation algorithms. In Proceedings of the 10th International Conference on World Wide Web (WWW'01). ACM, New York, NY, 285--295.
25. Sarwar, B. M., Karypis, G., Konstan, J. A., and Riedl, J. T. 2000. Application of dimensionality reduction in recommender system—a case study. In Proceedings of the ACM WebKDD Workshop.
26. Takács, G., Pilászy, I., Németh, B., and Tikk, D. 2007. Major components of the gravity recommendation system. SIGKDD Explor. Newsl. 9, 2, 80--83.
27. Tintarev, N. and Masthoff, J. 2007. A survey of explanations in recommender systems. In Proceedings of the 22nd International Conference on Data Engineering Workshops, 801--810.
28. Wang, J., de Vries, A. P., and Reinders, M. J. T. 2006. Unifying user-based and item-based collaborative filtering approaches by similarity fusion. In Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR'06). ACM, New York, NY, 501--508.

Index Terms

• Information systems

  • Information retrieval

    • Retrieval tasks and goals

      • Document filtering

      • Information extraction

  • Information systems applications

    • Data mining