Grocery shopping recommendations based on basket-sensitive random walk

ABSTRACT

We describe a recommender system in the domain of grocery shopping. While recommender systems have been widely studied, this is mostly in relation to leisure products (e.g. movies, books and music) with non-repeated purchases. In grocery shopping, however, consumers will make multiple purchases of the same or very similar products more frequently than buying entirely new items. The proposed recommendation scheme offers several advantages in addressing the grocery shopping problem, namely: 1) a product similarity measure that suits a domain where no rating information is available; 2) a basket sensitive random walk model to approximate product similarities by exploiting incomplete neighborhood information; 3) online adaptation of the recommendation based on the current basket and 4) a new performance measure focusing on products that customers have not purchased before or purchase infrequently. Empirical results benchmarking on three real-world data sets demonstrate a performance improvement of the proposed method over other existing collaborative filtering models.

REFERENCES

• 1: 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]
• 2: J. Breese, D. Heckerman, and C. Kadie. Empirical analysis of predictive algorithms for collaborative filtering. In Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence, 1998.
• 3: Tom Brijs , Gilbert Swinnen , Koen Vanhoof , Geert Wets, Using association rules for product assortment decisions: a case study, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.254-260, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312241]
• 4: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 5: Mukund Deshpande , George Karypis, Item-based top-N recommendation algorithms, ACM Transactions on Information Systems (TOIS), v.22 n.1, p.143-177, January 2004 [doi>10.1145/963770.963776]
• 6: Taher H. Haveliwala, Topic-sensitive PageRank, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511513]
• 7: Chun-Nan Hsu , Hao-Hsiang Chung , Han-Shen Huang, Mining Skewed and Sparse Transaction Data for Personalized Shopping Recommendation, Machine Learning, v.57 n.1-2, p.35-59, October-November 2004 [doi>10.1023/B:MACH.0000035471.28235.6d]
• 8: D. Z. Huang, Z. and H. Chen. A link analysis approach to recommendation with sparse data. In Americas Conference on Information Systems, New York, NY, USA, 2004.
• 9: Glen Jeh , Jennifer Widom, Scaling personalized web search, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775191]
• 10: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.668-677, January 25-27, 1998, San Francisco, California, United States
• 11: 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]
• 12: Ming Li , Benjamin Dias , Wael El-Deredy , Paulo J. G. Lisboa, A probabilistic model for item-based recommender systems, Proceedings of the 2007 ACM conference on Recommender systems, October 19-20, 2007, Minneapolis, MN, USA [doi>10.1145/1297231.1297253]
• 13: Nathan N. Liu , Qiang Yang, EigenRank: a ranking-oriented approach to collaborative filtering, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore [doi>10.1145/1390334.1390351]
• 14: Jia-Yu Pan , Hyung-Jeong Yang , Christos Faloutsos , Pinar Duygulu, Automatic multimedia cross-modal correlation discovery, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014135]
• 15: 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]
• 16: 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]
• 17: C. M. Sordo-Garcia, M. B. Dias, M. Li, W. El-Deredy, and P. J. G. Lisboa. Evaluating retail recommender systems via retrospective data: Lessons learnt from a live-intervention study. In The 2007 International Conference on Data Mining, DMIN'07, 2007.
• 18: Derry Tanti Wijaya , Stéphane Bressan, A random walk on the red carpet: rating movies with user reviews and pagerank, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA [doi>10.1145/1458082.1458207]
• 19: Hilmi Yildirim , Mukkai S. Krishnamoorthy, A random walk method for alleviating the sparsity problem in collaborative filtering, Proceedings of the 2008 ACM conference on Recommender systems, October 23-25, 2008, Lausanne, Switzerland [doi>10.1145/1454008.1454031]
• 20: T. Zhou, J. Ren, M. Medo, and Y. C. Zhang. Bipartite network projection and personal recommendation. Physical Review E (Statistical, Nonlinear, and Soft Matter Physics), 76(4), 2007.

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Algorithms, Experimentation, Performance

Keywords:
basket sensitive random walk, grocery shopping recommendation, popularity based performance evaluatoin