Applying associative retrieval techniques to alleviate the sparsity problem in collaborative filtering

ABSTRACT

Recommender systems are being widely applied in many application settings to suggest products, services, and information items to potential consumers. Collaborative filtering, the most successful recommendation approach, makes recommendations based on past transactions and feedback from consumers sharing similar interests. A major problem limiting the usefulness of collaborative filtering is the sparsity problem, which refers to a situation in which transactional or feedback data is sparse and insufficient to identify similarities in consumer interests. In this article, we propose to deal with this sparsity problem by applying an associative retrieval framework and related spreading activation algorithms to explore transitive associations among consumers through their past transactions and feedback. Such transitive associations are a valuable source of information to help infer consumer interests and can be explored to deal with the sparsity problem. To evaluate the effectiveness of our approach, we have conducted an experimental study using a data set from an online bookstore. We experimented with three spreading activation algorithms including a constrained Leaky Capacitor algorithm, a branch-and-bound serial symbolic search algorithm, and a Hopfield net parallel relaxation search algorithm. These algorithms were compared with several collaborative filtering approaches that do not consider the transitive associations: a simple graph search approach, two variations of the user-based approach, and an item-based approach. Our experimental results indicate that spreading activation-based approaches significantly outperformed the other collaborative filtering methods as measured by recommendation precision, recall, the F-measure, and the rank score. We also observed the over-activation effect of the spreading activation approach, that is, incorporating transitive associations with past transactional data that is not sparse may "dilute" the data used to infer user preferences and lead to degradation in recommendation performance.

REFERENCES

• 1: Charu C. Aggarwal , Joel L. Wolf , Kun-Lung Wu , Philip S. Yu, Horting hatches an egg: a new graph-theoretic approach to collaborative filtering, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.201-212, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312230]
• 2: Albert, R. and Barabasi, A.-L. 2002. Statistical mechanics of complex networks. Rev. Mod. Phys. 74, 47--97.
• 3: Anderson, J. R. 1983. A spreading activation theory of memory. J. Verb. Learn. Verb. Behav. 22, 261--295.
• 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: Chumki Basu , Haym Hirsh , William Cohen, Recommendation as classification: using social and content-based information in recommendation, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.714-720, July 1998, Madison, Wisconsin, United States
• 6: 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
• 7: Bollen, J., Vandesompel, H., and Rocha, L. M. 1999. Mining associative relations from website logs and their application to context-dependent retrieval using spreading activation. In Proceedings of the Workshop on Organizing Web Space (WOWS). ACM Digital Libraries 99.
• 8: Breese, J. S., Heckerman, D., and KADIE, C. 1998. Empirical analysis of predictive algorithms for collaborative filtering. In Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence (Madison, Wisc.). Morgan-Kaufmann, Reading, Mass. 43--52.
• 9: Burke, R. 2000. Semantic ratings and heuristic similarity for collaborative filtering. In Proceedings of the 17th National Conference on Artificial Intelligence.
• 10: Hsinchun Chen , Vasant Dhar, Cognitive process as a basis for intelligent retrieval systems design, Information Processing and Management: an International Journal, v.27 n.5, p.405-432, 1991 [doi>10.1016/0306-4573(91)90060-Y ]
• 11: Hsinchun Chen , Kevin J. Lynch , Koushik Basu , Tobun Dorbin Ng, Generating, integrating, and activating thesauri for concept-based document retrieval, IEEE Expert: Intelligent Systems and Their Applications, v.8 n.2, p.25-34, April 1993 [doi>10.1109/64.207426 ]
• 12: H. Chen , T. Ng, An algorithmic approach to concept exploration in a large knowledge network (automatic thesaurus consultation): symbolic branch-and-bound search vs. connectionist Hopfield net activation, Journal of the American Society for Information Science, v.46 n.5, p.348-369, June 1995 [doi>10.1002/(SICI)1097-4571(199506)46:5<348::AID-ASI6>3.0.CO;2-1]
• 13: Claypool, M., Gokhale, A., Miranda, T., Murnikov, P., Netes, D., and Sartin, M. 1999. Combining content-based and collaborative filters in an online newspaper. In Proceedings of the ACM SIGIR Workshop on Recommender Systems. ACM, New York.
• 14: Paul R. Cohen , Rick Kjeldsen, Information retrieval by constrained spreading activation in semantic networks, Information Processing and Management: an International Journal, v.23 n.4, p.255-268, July 1987 [doi>10.1016/0306-4573(87)90017-3 ]
• 15: Collins, A. M. and Loftus, E. F. 1975. A spreading activation theory of semantic processing. Psych. Rev. 82, 6, 407--428.
• 16: J. Ben Schafer , Joseph Konstan , John Riedi, Recommender systems in e-commerce, Proceedings of the 1st ACM conference on Electronic commerce, p.158-166, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337035]
• 17: Fabio Crestani , Puay Leng Lee, Searching the Web by constrained spreading activation, Information Processing and Management: an International Journal, v.36 n.4, p.585-605, July 2000 [doi>10.1016/S0306-4573(99)00073-4 ]
• 18: Carolyn J. Crouch , Bokyung Yang, Experiments in automatic statistical thesaurus construction, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.77-88, June 21-24, 1992, Copenhagen, Denmark [doi>10.1145/133160.133180]
• 19: 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 ]
• 20: Nathaniel Good , J. Ben Schafer , Joseph A. Konstan , Al Borchers , Badrul Sarwar , Jon Herlocker , John Riedl, Combining collaborative filtering with personal agents for better recommendations, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.439-446, July 18-22, 1999, Orlando, Florida, United States
• 21: M. Gordon, Probabilistic and genetic algorithms in document retrieval, Communications of the ACM, v.31 n.10, p.1208-1218, Oct. 1988 [doi>10.1145/63039.63044]
• 22: Will Hill , Larry Stead , Mark Rosenstein , George Furnas, Recommending and evaluating choices in a virtual community of use, Proceedings of the SIGCHI conference on Human factors in computing systems, p.194-201, May 07-11, 1995, Denver, Colorado, United States [doi>10.1145/223904.223929]
• 23: Zan Huang , Wingyan Chung , Hsinchun Chen, A graph model for E-commerce recommender systems, Journal of the American Society for Information Science and Technology, v.55 n.3, p.259-274, February 2004 [doi>10.1002/asi.10372]
• 24: Zan Huang , Wingyan Chung , Thian-Huat Ong , Hsinchun Chen, A graph-based recommender system for digital library, Proceedings of the 2nd ACM/IEEE-CS joint conference on Digital libraries, July 14-18, 2002, Portland, Oregon, USA [doi>10.1145/544220.544231]
• 25: Jung, G. and Raghavan, V. 1990. Connectionist learning in constructing thesaurus-like knowledge structure. In Proceedings of the AAAI Spring Symposium on Text-based Intelligent Systems.
• 26: George Karypis, Evaluation of Item-Based Top-N Recommendation Algorithms, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502627]
• 27: Kevin Knight, Connectionist ideas and algorithms, Communications of the ACM, v.33 n.11, p.58-74, Nov. 1990 [doi>10.1145/92755.92764]
• 28: 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]
• 29: Weiyang Lin , Sergio A. Alvarez , Carolina Ruiz, Efficient Adaptive-Support Association Rule Mining for Recommender Systems, Data Mining and Knowledge Discovery, v.6 n.1, p.83-105, January 2002 [doi>10.1023/A:1013284820704 ]
• 30: Mirza, B. J. 2001. Jumping connections: A graph-theoretic model for recommender systems. Computer Science Department, Virginia Polytechnic Institute and state university, (http://scholar.lib.vt.edu/theses/available/etd-02282001-175040/unrestricted/etd.pdf).
• 31: Batul J. Mirza , Benjamin J. Keller , Naren Ramakrishnan, Studying Recommendation Algorithms by Graph Analysis, Journal of Intelligent Information Systems, v.20 n.2, p.131-160, March 2003 [doi>10.1023/A:1021819901281 ]
• 32: Mobasher, B. H., Dai, T. L., Nakagawa, M., Sun, Y., and Wiltshire, J. 2000. Discovery of aggregate usage profiles for web personalization. In Proceedings of the Workshop on Web Mining for E-Commerce---Challenges and Opportunities.
• 33: Nasraoui, O., Frigui, H., Joshi, A., and Krishnapuram, R. 1999. Mining web access logs using relational competitive fuzzy clustering. In Proceedings of the 8th International Fuzzy Systems Association World Congress---IFSA 99.
• 34: Michael J. Pazzani, A Framework for Collaborative, Content-Based and Demographic Filtering, Artificial Intelligence Review, v.13 n.5-6, p.393-408, Dec. 1999
• 35: Michael Pazzani , Daniel Billsus, Learning and Revising User Profiles: The Identification ofInteresting Web Sites, Machine Learning, v.27 n.3, p.313-331, June 1997 [doi>10.1023/A:1007369909943 ]
• 36: Peter Pirolli , James Pitkow , Ramana Rao, Silk from a sow's ear: extracting usable structures from the Web, Proceedings of the SIGCHI conference on Human factors in computing systems: common ground, p.118-125, April 13-18, 1996, Vancouver, British Columbia, Canada [doi>10.1145/238386.238450]
• 37: 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]
• 38: G. Salton , C. Buckley, On the use of spreading activation methods in automatic information, Proceedings of the 11th annual international ACM SIGIR conference on Research and development in information retrieval, p.147-160, May 1988, Grenoble, France [doi>10.1145/62437.62447]
• 39: Badrul Sarwar , George Karypis , Joseph Konstan , John Riedl, Analysis of recommendation algorithms for e-commerce, Proceedings of the 2nd ACM conference on Electronic commerce, p.158-167, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352887]
• 40: Sarwar, B., Karypis, G., Konstan, J., and Riedl, J. 2000b. Application of dimensionality reduction in recommender systems: A case study. In Proceedings of the WebKDD Workshop at the ACM SIGKKD. ACM, New York.
• 41: Badrul M. Sarwar , Joseph A. Konstan , Al Borchers , Jon Herlocker , Brad Miller , John Riedl, Using filtering agents to improve prediction quality in the GroupLens research collaborative filtering system, Proceedings of the 1998 ACM conference on Computer supported cooperative work, p.345-354, November 14-18, 1998, Seattle, Washington, United States [doi>10.1145/289444.289509]
• 42: 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]
• 43: J. Ben Schafer , Joseph A. Konstan , John Riedl, E-Commerce Recommendation Applications, Data Mining and Knowledge Discovery, v.5 n.1-2, p.115-153, January-April 2001
• 44: Andrew I. Schein , Alexandrin Popescul , Lyle H. Ungar , David M. Pennock, Methods and metrics for cold-start recommendations, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564421]
• 45: Upendra Shardanand , Pattie Maes, Social information filtering: algorithms for automating “word of mouth”, Proceedings of the SIGCHI conference on Human factors in computing systems, p.210-217, May 07-11, 1995, Denver, Colorado, United States [doi>10.1145/223904.223931]
• 46: 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]
• 47: Loren Terveen , Will Hill , Brian Amento , David McDonald , Josh Creter, PHOAKS: a system for sharing recommendations, Communications of the ACM, v.40 n.3, p.59-62, March 1997 [doi>10.1145/245108.245122]
• 48: S. K. M. Wong , Wojciech Ziarko , Patrick C. N. Wong, Generalized vector spaces model in information retrieval, Proceedings of the 8th annual international ACM SIGIR conference on Research and development in information retrieval, p.18-25, June 05-07, 1985, Montreal, Quebec, Canada [doi>10.1145/253495.253506]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.2 User/Machine Systems
          Subjects: Human information processing

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Retrieval models; Relevance feedback; Information filtering

General Terms:
Algorithms, Design, Experimentation

Keywords:
Recommender system, associative retrieval, collaborative filtering, sparsity problem, spreading activation