A new collaborative filtering algorithm using near-clique bipartite graph clusters

Thesis Type: Postgraduate

Institution Of The Thesis: Orta Doğu Teknik Üniversitesi, Faculty of Engineering, Department of Computer Engineering, Turkey

Approval Date: 2014




Recommendation systems are becoming increasingly crucial for everyday tasks such as choosing movies, discovering new songs, connecting to other people. These systems try to give the best recommendations as quickly as possible. In order to achieve this target,they employ similarity metrics and clustering for better suggestions, parallel algorithms and dimensionality reduction for fast running time. In this study, we propose prediction algorithms that complete missing values using former user preferences and user information. Our algorithms utilize hierarchical clustering with bottom-up approach to find nearly complete bipartite graphs(near-clique). Near-clique graphs indicate strong connectivity between users and items. However, finding complete bipartite graph is an NP-Complete problem. Therefore, hierarchical clustering and similarity metrics are used for detecting near-clique graphs as much as possible. Predictions are made by using near-clique graphs. To evaluate the algorithms performance, the experiments are held on the MovieLens dataset. The results show that, we achieved high accuracy for overall predictions and especially initial predictions are remarkable.