Latency of Neighborhood Based Recommender Systems

• Autorzy: Chojnacki S. , Kłopotek M.

Identyfikatory

DOI

10.3233/FI-2015-1233

• Języki publikacji: EN

Abstrakty

EN

Latency of user-based and item-based recommenders is evaluated. The two algorithms can deliver high quality predictions in dynamically changing environments. However, their response time depends not only on the size, but also on the structure of underlying datasets. This constitutes a major drawback when compared to two other competitive approaches i.e. content-based and modelbased systems. Therefore, we believe that there exists a need for comprehensive evaluation of the latency of the two algorithms. During a typical worst case scenario analysis of collaborative filtering algorithms two assumption are made. The first assumption says that data are stored in dense collections. The second assumption states that large amount of computations can be performed in advance during the training phase. As a result it is advised to deploy user-based system when the number of users is relatively small. Item-based algorithms are believed to have better technical properties when the number of items is small. We consider a situation in which the two assumptions are not necessarily met. We show that even though the latency of the two methods depends heavily on the proportion of users to items, this factor does not differentiate the two methods. We evaluate the algorithms with several real-life datasets. We augment the analysis with both graph-theoretical and experimental techniques.

Słowa kluczowe

EN

recommender systems; computer users; computer algorithms; reaction time; data analysis

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 139, nr 3
• Strony: 229--248
• Opis fizyczny: Bibliogr. 25 poz., tab., wykr.

Twórcy

autor

Chojnacki S.

• Institute of Computer Science Polish Academy of Sciences Jana Kazimierza 5, 01-248 Warszawa, Poland

autor

Kłopotek M.

• Institute of Computer Science Polish Academy of Sciences Jana Kazimierza 5, 01-248 Warszawa, Poland

Bibliografia

• [1] D. Agarwal, B. C. Chen, P. Elango, N. Motgi, S. T. Park, R. Ramakrishnan, S. Roy, and J. Zachariah. Online Models for Content Optimization. In D. Koller, D. Schuurmans, Y. Bengio, and L. Bottou, editors, NIPS, pages 17–24. MIT Press, 2008.
• [2] X. Amatriain, A. Jaimes, N. Oliver, and J. M. Pujol. Data mining methods for recommender systems. In F. Ricci, L. Rokach, B. Shapira, and P. B. Kantor, editors, Recommender Systems Handbook, pages 39–71. Springer US, 2011.
• [3] A. Barabási and R. Albert. Emergence of scaling in random networks. Science (New York, N.Y.), 286(5439):509–512, 1999.
• [4] A. Z. Broder. Computational advertising and recommender systems. In Proceedings of the 2008 ACM conference on Recommender systems, RecSys ’08, pages 1–2. ACM, 2008.
• [5] S. Chojnacki, K. Ciesielski, and M. Kłopotek. Node degree distribution in affiliation graphs for social network density modeling. In L. Bolc, M. Makowski, and A. Wierzbicki, editors, Social Informatics, volume 6430 of Lecture Notes in Computer Science, pages 51–61. Springer Berlin / Heidelberg, 2010.
• [6] S. Chojnacki, D. Czerski, and M. Kłopotek. Optimization of tag recommender systems in a real life setting. In 3rd Conference on Human System Interaction, pages 107–112, 2010.
• [7] S. Chojnacki and M. Klopotek. Random graphs for bipartite networks modeling. Journal of Control and Cybernetics, 40(3), 2011.
• [8] S. Chojnacki and M. A. Klopotek. Random graphs for performance evaluation of recommender systems. Journal of Control and Cybernetics, 40(2), 2011.
• [9] A. S. Das, M. Datar, A. Garg, and S. Rajaram. Google news personalization: scalable online collaborative filtering. InWWW’07: Proceedings of the 16th international conference onWorldWideWeb, pages 271–280. ACM, 2007.
• [10] C. Desrosiers and G. Karypis. A comprehensive survey of neighborhood-based recommendation methods. In F. Ricci, L. Rokach, B. Shapira, and P. B. Kantor, editors, Recommender Systems Handbook, pages 107–144. Springer US, 2011.
• [11] P. Erdös and A. Rényi. On the evolution of random graphs. In Publication of the Mathematical Institute of the Hungarian Academy of Sciences, pages 17–61, 1960.
• [12] M. Hall, E. Frank, G. Holmes, B. Pfahringer, P. Reutemann, and I. H. Witten. The WEKA data mining software: an update. SIGKDD Explorations, (1):10–18.
• [13] J. L. Herlocker, J. A. Konstan, A. Borchers, and J. Riedl. An algorithmic framework for performing collaborative filtering. In Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, pages 230–237. ACM Press, 1999.
• [14] J. L. Herlocker, J. A. Konstan, L. G. Terveen, and J. T. Riedl. Evaluating collaborative filtering recommender systems. ACM Trans. Inf. Syst., 22:5–53, January 2004.
• [15] M. Jahrer, A. Töscher, and R. Legenstein. Combining predictions for accurate recommender systems. In KDD ’10, pages 693–702. ACM, 2010.
• [16] R. Jäschke, F. Eisterlehner, A. Hotho, and G. Stumme. Testing and evaluating tag recommenders in a live system. In D. Benz and F. Janssen, editors, Workshop on Knowledge Discovery, Data Mining, and Machine Learning, pages 44–51, 2009.
• [17] Y. Koren. Factorization meets the neighborhood: a multifaceted collaborative filtering model. In Proc. Int. Conf. on Knowledge Discovery and Data Mining, pages 426–434, 2008.
• [18] M. Lipczak, Y. Hu, Y. Kollet, and E. Milios. Tag sources for recommendation in collaborative tagging systems. In Proceedings of the ECML/PKDD 2009 Discovery Challenge Workshop, 2009.
• [19] M. Lipczak and E. Milios. Learning in efficient tag recommendation. In RecSys ’10: Proc. the 4th ACM Conference on Recommender Systems, pages 167–174. ACM, 2010.
• [20] M. Newman, S. Strogatz, and D. J. Watts. Random graphs with arbitrary degree distributions and their applications. 64(026118), July 2001.
• [21] S. Owen, R. Anil, T. Dunning, and E. Friedman. Mahout in action (MEAP). Manning, 2011.
• [22] S. Rendle and L. Schmidt-thieme. Factor models for tag recommendation in bibsonomy. In Proceedings of the ECML/PKDD 2009 Discovery Challenge Workshop, 2009.
• [23] R. Salakhutdinov, A. Mnih, and G. Hinton. Restricted boltzmann machines for collaborative filtering. In Proceedings of the 24th International Conference on Machine Learning. International Conference on Machine Learning, 2007.
• [24] B. M. Sarwar, G. Karypis, J. A. Konstan, and J. Riedl. Item-based collaborative filtering recommendation algorithms. In WWW, pages 285–295, 2001.
• [25] G. Shani and A. Gunawardana. Evaluating recommendation systems. In F. Ricci, L. Rokach, B. Shapira, and P. B. Kantor, editors, Recommender Systems Handbook, pages 257–297. Springer US, 2011.