Scalable collaborative filtering using cluster-based smoothing

ABSTRACT

Memory-based approaches for collaborative filtering identify the similarity between two users by comparing their ratings on a set of items. In the past, the memory-based approach has been shown to suffer from two fundamental problems: data sparsity and difficulty in scalability. Alternatively, the model-based approach has been proposed to alleviate these problems, but this approach tends to limit the range of users. In this paper, we present a novel approach that combines the advantages of these two approaches by introducing a smoothing-based method. In our approach, clusters generated from the training data provide the basis for data smoothing and neighborhood selection. As a result, we provide higher accuracy as well as increased efficiency in recommendations. Empirical studies on two datasets (EachMovie and MovieLens) show that our new proposed approach consistently outperforms other state-of-art collaborative filtering algorithms.

REFERENCES

• 1: Daniel Billsus , Michael J. Pazzani, Learning Collaborative Information Filters, Proceedings of the Fifteenth International Conference on Machine Learning, p.46-54, July 24-27, 1998
• 2: Peter F. Brown , Peter V. deSouza , Robert L. Mercer , Vincent J. Della Pietra , Jenifer C. Lai, Class-based n-gram models of natural language, Computational Linguistics, v.18 n.4, p.467-479, December 1992
• 3: J. S. Breese, D. Heckerman, and C. Kadie. Empirical analysis of Predictive Algorithms for Collaborative Filtering. In Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence, 1998. 43--52.
• 4: Marko Balabanović , Yoav Shoham, Fab: content-based, collaborative recommendation, Communications of the ACM, v.40 n.3, p.66-72, March 1997 [doi>10.1145/245108.245124]
• 5: M. Claypool, A. Gokhale, T. Miranda, P. Murnikov, D. Netes, and M. Sartin. Combining Content-based and Collaborative Filters in an Online Newspaper. In Proceedings of ACM SIGIR Workshop on Recommender, August 1999.
• 6: M. O. Conner and J. Herlocker. Clustering Items for Collaborative Filtering. In Proceedings of the ACM SIGIR Workshop on Recommender Systems, Berkeley, CA, August 1999.
• 7: Danyel Fisher , Kris Hildrum , Jason Hong , Mark Newman , Megan Thomas , Rich Vuduc, SWAMI (poster session): a framework for collaborative filtering algorithm development and evaluation, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.366-368, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345658]
• 8: Ken Goldberg , Theresa Roeder , Dhruv Gupta , Chris Perkins, Eigentaste: A Constant Time Collaborative Filtering Algorithm, Information Retrieval, v.4 n.2, p.133-151, July 2001 [doi>10.1023/A:1011419012209]
• 9: Jonathan L. Herlocker , Joseph A. Konstan , Al Borchers , John Riedl, An algorithmic framework for performing collaborative filtering, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.230-237, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312682]
• 10: Jonathan L. Herlocker , Joseph A. Konstan , Loren G. Terveen , John T. Riedl, Evaluating collaborative filtering recommender systems, ACM Transactions on Information Systems (TOIS), v.22 n.1, p.5-53, January 2004 [doi>10.1145/963770.963772]
• 11: Zan Huang , Hsinchun Chen , Daniel Zeng, Applying associative retrieval techniques to alleviate the sparsity problem in collaborative filtering, ACM Transactions on Information Systems (TOIS), v.22 n.1, p.116-142, January 2004 [doi>10.1145/963770.963775]
• 12: Thomas Hofmann , Jan Puzicha, Latent Class Models for Collaborative Filtering, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.688-693, July 31-August 06, 1999
• 13: A. Kohrs and B. Merialdo. Clustering for Collaborative Filtering Applications. In Proceedings of CIMCA'99. IOS Press, 1999.
• 14: Joseph A. Konstan , Bradley N. Miller , David Maltz , Jonathan L. Herlocker , Lee R. Gordon , John Riedl, GroupLens: applying collaborative filtering to Usenet news, Communications of the ACM, v.40 n.3, p.77-87, March 1997 [doi>10.1145/245108.245126]
• 15: David M. Pennock , Eric Horvitz , Steve Lawrence , C. Lee Giles, Collaborative Filtering by Personality Diagnosis: A Hybrid Memory and Model-Based Approach, Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence, p.473-480, June 30-July 03, 2000
• 16: Paul Resnick , Neophytos Iacovou , Mitesh Suchak , Peter Bergstrom , John Riedl, GroupLens: an open architecture for collaborative filtering of netnews, Proceedings of the 1994 ACM conference on Computer supported cooperative work, p.175-186, October 22-26, 1994, Chapel Hill, North Carolina, United States [doi>10.1145/192844.192905]
• 17: Alexandrin Popescul , Lyle H. Ungar , David M. Pennock , Steve Lawrence, Probabilistic Models for Unified Collaborative and Content-Based Recommendation in Sparse-Data Environments, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, p.437-444, August 02-05, 2001
• 18: B.M. Sarwar, G. Karypis, J.A. Konstan, and J. Riedl. Application of Dimensionality Reduction in Recommender Systems: a Case Study. In ACM WebKDD Workshop,2000.
• 19: Badrul Sarwar , George Karypis , Joseph Konstan , John Reidl, Item-based collaborative filtering recommendation algorithms, Proceedings of the 10th international conference on World Wide Web, p.285-295, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372071]
• 20: Ian Soboroff , Charles Nicholas, Collaborative filtering and the generalized vector space model (poster session), Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.351-353, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345646]
• 21: L. H. Ungar and D. P. Foster. Clustering Methods for Collaborative Filtering. In Proc. Workshop on Recommendation Systems at the 15th National Conf. on Artificial Intelligence. Menlo Park, CA: AAAI Press.
• 22: K. Yu, Z. Wen, X.W Xu, and M. Ester. Feature Weighting and Instance Selection for Collaborative Filtering, in Proceedings of 2nd International Workshop on Management of Information on the Web: Web Data and Text Mining (MIW'01), 2001.
• 23: Chun Zeng , Chun-Xiao Xing , Li-Zhu Zhou, Similarity measure and instance selection for collaborative filtering, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775243]
• 24: MovieLens. http://www.cs.umn.edu/Research/GroupLens/data/.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Information filtering

General Terms:
Algorithms, Experimentation, Performance

Keywords:
clustering, collaborative filtering, smoothing, sparsity data