Collaborative filtering with information-rich and information-sparse entities

摘要

In this paper, we consider a popular model for collaborative filtering in recommender systems. In particular, we consider both the clustering model, where only users (or items) are clustered, and the co-clustering model, where both users and items are clustered, and further, we assume that some users rate many items (information-rich users) and some users rate only a few items (information-sparse users). When users (or items) are clustered, our algorithm can recover the rating matrix with \(\omega (MK \log M)\) noisy entries while \(MK\) entries are necessary, where \(K\) is the number of clusters and \(M\) is the number of items. In the case of co-clustering, we prove that \(K^2\) entries are necessary for recovering the rating matrix, and our algorithm achieves this lower bound within a logarithmic factor when \(K\) is sufficiently large. Extensive simulations on Netflix and MovieLens data show that our algorithm outperforms the alternating minimization and the popularity-among-friends algorithm. The performance difference increases even more when noise is added to the datasets.