Use of Kemeny median in the algorithm of forming recommendation

Authors

DOI:

https://doi.org/10.20535/SRIT.2308-8893.2020.4.05

Keywords:

recommender system, consensus ranking, Kemeny median

Abstract

The relevant nowadays question of development of the algorithmic support of recommender systems is considered. The article is devoted to the solution of the problem of forming recommendations to new users, which is based on the ideas of transition from the matrix "user-object" to the ranking of objects and the formation of recommendations to the user of the active cluster based on the construction of the resulting ranking, which is a Kemeny median on a set of rankings. The choice of Kemeny median as the resulting ranking and the choice of algorithm for its construction are justified. To reduce the complexity of calculations, it is suggested to perform aggregation of information and to use it in forming of ranking recommendations, which are based on a set of "generalized experts" for this cluster. The efficiency of the developed algorithmic support was studied and the results and recommendations were given.

Author Biographies

Oksana Zhurakovska, National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Kyiv

Oksana S. Zhurakovska,

Candidate of Technical Sciences (Ph.D.), an associate professor at the Department of Computer-Aided Management and Data Processing Systems of the Faculty of Informatics and Computer Science of the National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Kyiv, Ukraine.

Illa Kochubey, National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Kyiv

Illa Yu. Kochubey,

a student at the Department of Computer-Aided Management and Data Processing Systems of the Faculty of Informatics and Computer Science of the National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Kyiv, Ukraine.

References

J. Lu, D. Wu, M. Mao, W. Wang, and G. Zhang, “Recommender system application developments: A survey”, Decision Support Systems, vol. 74, pp. 187–192, 2015. doi:10.1016/j.dss.2015.03.008.

C.A. Gomez-Uribe and N. Hunt, “The Netflix Recommender System: Algorithms, Business Value, and Innovation”, ACM Transactions on Management Information Systems, vol. 6, no. 4, pp. 1–19, 2015. doi:10.1145/2843948.

F. Ricci, L. Rokach, and B. Shapira, “Introduction to Recommender Systems Handbook”, in Recommender Systems Handbook, Boston, MA: Springer, 2011, pp. 1–35.

P. Melville et al., “Content-Boosted Collaborative Filtering for Improved Recommendations”, in National Conference on Artificial Intelligence, Edmonton, Canada, 2016, pp. 187–192.

V. Srikar and R. Sudha, “Examining Lists on Twitter to Uncover Relationships Between Following, Membership and Subscription”, in Proceedings of the 22nd international conference on World Wide Web, Rio de Janeiro, Brazil, 2013, pp. 673–676.

I.Yu. Kochubey and O.S. Zhurakovska, “Modified algorithm of collaborative filtering for forming user recommendations”, KPI Science News, vol. 3, pp. 43–49, 2020. doi:10.20535/kpi-sn.2020.3.209842.

D.T. Pham, S.S. Dimov, and C.D. Nguyen, “Selection of K in K-means clustering”, Proceedings of the Institution of Mechanical Engineers, Part C: Journal of Mechanical Engineering Science, vol. 219 (1), pp. 103–119, 2005. doi:10.1243/ 095440605x8298.

W. Prinz et al., “PolyLens: A Recommender System for Groups of Users”, in Proceedings of the Seventh European Conference on Computer-Supported Cooperative Work, Bonn, Germany, 2001, pp. 199–218. doi:10.1007/0-306-48019-0_11.

A. Shepitsen, J. Gemmell, B. Mobasher, and R. Burke, “Personalized Recommendation in Social Tagging Systems Using Hierarchical Clustering”, in Proceedings of the ACM Conference on Recommender Systems — RecSys ’08, 2008, pp. 259–266. doi:10.1145/1454008.1454048.

C. Gentile et al., “On Context-Dependent Clustering of Bandits”, in Proceedings of the 34th International Conference on Machine Learning, 2017, pp. 1253–1262.

B. Litvak, Ekspertnaya informatsiya. Metody polucheniya i analiza [Expert information. Methods of obtaining and analysis]. Moscow, 2009

C. List and C. Puppe, “Judgement aggregation: a survey”, in Oxford handbook of rational and social choice, Oxford, 2009, pp. 457–482. doi:10.1007/s11229-011-0025-3.

H. Bury and D. Vagner, “Judgement With Ties. Distance-Based Methods”, New Approaches in Automation and Robotics, Vienna, 2008, pp. 153–172.

O. Hudry, “Complexity of computing median linear orders and variants”, Electronic Notes in Discrete Mathematics, vol. 42, pp. 57–64, 2013. doi:10.1016/j.endm. 2013.05.146.

O. Hudry, “NP-hardness results on the aggregation of linear orders into median orders”, Annals of Operations Research, vol. 163, pp. 63–88, 2008. doi:10.1007/s10479-008-0353-y

S. Amodio, A. D'Ambrosio, and R. Siciliano, “Accurate algorithms for identifying the median ranking when dealing with weak and partial rankings under the Kemeny axiomatic approach”, Journal of Operational Research, vol. 249, pp. 667–676, 2015. doi:10.1016/j.ejor.2015.08.048.

E. Emond and D. Mason, “A new rank correlation coefficient with application to the consensus ranking problem”, Journal of Multi-Criteria Decision Analysis, vol. 11, pp. 17–28, 2002.

W.D. Cook, B. Golany, M. Penn, and T. Raviv, “Creating a consensus ranking of proposals from reviewers partial ordinal rankings”, Computers & Operations Research, vol. 43, pp. 954–965, 2007.

A. Alnur and M. Meila, “Experiments with Kemeny Ranking: What Works When?”, Mathematical Social Sciences, vol. 64, pp. 28–40, 2012. doi:10.1016/j.mathsocsci. 2011.08.008.

Published

2020-12-29

Issue

Section

Problem- and function-oriented computer systems and networks