Mind the gaps: weighting the unknown in large-scale one-class collaborative filtering

ABSTRACT

One-Class Collaborative Filtering (OCCF) is a task that naturally emerges in recommender system settings. Typical characteristics include: Only positive examples can be observed, classes are highly imbalanced, and the vast majority of data points are missing. The idea of introducing weights for missing parts of a matrix has recently been shown to help in OCCF. While existing weighting approaches mitigate the first two problems above, a sparsity preserving solution that would allow to efficiently utilize data sets with e.g., hundred thousands of users and items has not yet been reported. In this paper, we study three different collaborative filtering frameworks: Low-rank matrix approximation, probabilistic latent semantic analysis, and maximum-margin matrix factorization. We propose two novel algorithms for large-scale OCCF that allow to weight the unknowns. Our experimental results demonstrate their effectiveness and efficiency on different problems, including the Netflix Prize data.

REFERENCES

• 1: Gediminas Adomavicius , Alexander Tuzhilin, Toward the Next Generation of Recommender Systems: A Survey of the State-of-the-Art and Possible Extensions, IEEE Transactions on Knowledge and Data Engineering, v.17 n.6, p.734-749, June 2005 [doi>10.1109/TKDE.2005.99]
• 2: Yossi Azar , Amos Fiat , Anna Karlin , Frank McSherry , Jared Saia, Spectral analysis of data, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.619-626, July 2001, Hersonissos, Greece [doi>10.1145/380752.380859]
• 3: Gustavo E. A. P. A. Batista , Ronaldo C. Prati , Maria Carolina Monard, A study of the behavior of several methods for balancing machine learning training data, ACM SIGKDD Explorations Newsletter, v.6 n.1, June 2004 [doi>10.1145/1007730.1007735]
• 4: J. S. Breese, D. Heckerman, and C. M. Kadie. Empirical analysis of predictive algorithms for collaborative filtering. In UAI, pages 43--52. Morgan Kaufmann, 1998.
• 5: Leo Breiman, Bagging predictors, Machine Learning, v.24 n.2, p.123-140, Aug. 1996 [doi>10.1023/A:1018054314350]
• 6: Don Coppersmith , Shmuel Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, v.9 n.3, p.251-280, March 1990 [doi>10.1016/S0747-7171(08)80013-2]
• 7: Abhinandan S. Das , Mayur Datar , Ashutosh Garg , Shyam Rajaram, Google news personalization: scalable online collaborative filtering, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242610]
• 8: C. Drummond and R. Holte. C4.5, class imbalance, and cost sensitivity: why under-sampling beats over-sampling. In Proc. ICML'2003 Workshop on Learning from Imbalanced Data Sets II, 2003.
• 9: Thomas Hofmann, Latent semantic models for collaborative filtering, ACM Transactions on Information Systems (TOIS), v.22 n.1, p.89-115, January 2004 [doi>10.1145/963770.963774]
• 10: M. Kurucz, A. A. Benczur, T. Kiss, I. Nagy, A. Szabo, and B. Torma. Who rated what: a combination of SVD, correlation and frequent sequence mining. In Proc. KDD Cup and Workshop, 2007.
• 11: Xu-Ying Liu , Jianxin Wu , Zhi-Hua Zhou, Exploratory Under-Sampling for Class-Imbalance Learning, Proceedings of the Sixth International Conference on Data Mining, p.965-969, December 18-22, 2006 [doi>10.1109/ICDM.2006.68]
• 12: B. Marlin, R. Zemel, S. Roweis, and M. Slaney. Collaborative filtering and the missing at random assumption. In UAI, 2007.
• 13: Rong Pan , Yunhong Zhou , Bin Cao , Nathan N. Liu , Rajan Lukose , Martin Scholz , Qiang Yang, One-Class Collaborative Filtering, Proceedings of the 2008 Eighth IEEE International Conference on Data Mining, p.502-511, December 15-19, 2008 [doi>10.1109/ICDM.2008.16]
• 14: Bhavani Raskutti , Adam Kowalczyk, Extreme re-balancing for SVMs: a case study, ACM SIGKDD Explorations Newsletter, v.6 n.1, June 2004 [doi>10.1145/1007730.1007739]
• 15: Jasson D. M. Rennie , Nathan Srebro, Fast maximum margin matrix factorization for collaborative prediction, Proceedings of the 22nd international conference on Machine learning, p.713-719, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102441]
• 16: N. Srebro and T. Jaakkola. Weighted low-rank approximations. In International Conference on Machine Learning (ICML), 2003.
• 17: N. Srebro, J. D. M. Rennie, and T. Jaakkola. Maximum-margin matrix factorization. In NIPS, 2004.
• 18: Jeffrey Scott Vitter, Faster methods for random sampling, Communications of the ACM, v.27 n.7, p.703-718, July 1984 [doi>10.1145/358105.893]
• 19: Gary M. Weiss, Mining with rarity: a unifying framework, ACM SIGKDD Explorations Newsletter, v.6 n.1, June 2004 [doi>10.1145/1007730.1007734]
• 20: Yifan Hu , Yehuda Koren , Chris Volinsky, Collaborative Filtering for Implicit Feedback Datasets, Proceedings of the 2008 Eighth IEEE International Conference on Data Mining, p.263-272, December 15-19, 2008 [doi>10.1109/ICDM.2008.22]
• 21: Yunhong Zhou , Dennis Wilkinson , Robert Schreiber , Rong Pan, Large-Scale Parallel Collaborative Filtering for the Netflix Prize, Proceedings of the 4th international conference on Algorithmic Aspects in Information and Management, p.337-348, June 23-25, 2008, Shanghai, China [doi>10.1007/978-3-540-68880-8_32]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Least squares approximation

General Terms:
Algorithms

Keywords:
collaborative filtering, large-scale, one-class