Mining User preference using Spy voting for search engine personalization

ABSTRACT

This article addresses search engine personalization. We present a new approach to mining a user's preferences on the search results from clickthrough data and using the discovered preferences to adapt the search engine's ranking function for improving search quality. We develop a new preference mining technique called SpyNB, which is based on the practical assumption that the search results clicked on by the user reflect the user's preferences but does not draw any conclusions about the results that the user did not click on. As such, SpyNB is still valid even if the user does not follow any order in reading the search results or does not click on all relevant results. Our extensive offline experiments demonstrate that SpyNB discovers many more accurate preferences than existing algorithms do. The interactive online experiments further confirm that SpyNB and our personalization approach are effective in practice. We also show that the efficiency of SpyNB is comparable to existing simple preference mining algorithms.

REFERENCES

• 1: Rakesh Agrawal , Edward L. Wimmers, A framework for expressing and combining preferences, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.297-306, May 15-18, 2000, Dallas, Texas, United States
• 2: Brian T. Bartell , Garrison W. Cottrell , Richard K. Belew, Automatic combination of multiple ranked retrieval systems, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.173-181, July 03-06, 1994, Dublin, Ireland
• 3: Avrim Blum , Tom Mitchell, Combining labeled and unlabeled data with co-training, Proceedings of the eleventh annual conference on Computational learning theory, p.92-100, July 24-26, 1998, Madison, Wisconsin, United States [doi>10.1145/279943.279962]
• 4: Deng, L., Chai, X., Ng, W., and Lee, D. 2004. Spying out real user preferences for metasearch engine adaptation. In Proceedings of the 6th ACM SIGKDD Workshop on Web Mining and Web Usage Analysis (WebKDD 04, WA). Seattle, 71--82.
• 5: Goulden, C. 1956. Methods of Statistics Analysis, 2nd ed. John Wiley & Sons, New York, NY.
• 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: Jeffrey Heer , Ed H. Chi, Separating the swarm: categorization methods for user sessions on the web, Proceedings of the SIGCHI conference on Human factors in computing systems: Changing our world, changing ourselves, April 20-25, 2002, Minneapolis, Minnesota, USA [doi>10.1145/503376.503420]
• 8: Klaus-U. Höffgen , Hans-U. Simon , Kevin S. van Horn, Robust trainability of single neurons, Journal of Computer and System Sciences, v.50 n.1, p.114-125, Feb. 1995 [doi>10.1006/jcss.1995.1011]
• 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: Thorsten Joachims, Making large-scale support vector machine learning practical, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 11: Joachims, T. 2002a. Evaluating retrieval performance using clickthrough data. In Proceedings of the SIGIR Workshop on Mathematical/Formal Methods in Information Retrieval.
• 12: Thorsten Joachims, Optimizing search engines using clickthrough data, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775067]
• 13: Thorsten Joachims , Laura Granka , Bing Pan , Helene Hembrooke , Geri Gay, Accurately interpreting clickthrough data as implicit feedback, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076063]
• 14: Yiping Ke , Lin Deng , Wilfred Ng , Dik-Lun Lee, Web dynamics and their ramifications for the development of web search engines, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.10, p.1430-1447, 14 July 2006 [doi>10.1016/j.comnet.2005.10.012]
• 15: Werner Kießling, Foundations of preferences in database systems, Proceedings of the 28th international conference on Very Large Data Bases, p.311-322, August 20-23, 2002, Hong Kong, China
• 16: Bing Liu , Yang Dai , Xiaoli Li , Wee Sun Lee , Philip S. Yu, Building Text Classifiers Using Positive and Unlabeled Examples, Proceedings of the Third IEEE International Conference on Data Mining, p.179, November 19-22, 2003
• 17: Bing Liu , Wee Sun Lee , Philip S. Yu , Xiaoli Li, Partially Supervised Classification of Text Documents, Proceedings of the Nineteenth International Conference on Machine Learning, p.387-394, July 08-12, 2002
• 18: Fang Liu , Clement Yu , Weiyi Meng, Personalized web search by mapping user queries to categories, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584884]
• 19: Fang Liu , Clement Yu , Weiyi Meng, Personalized Web Search For Improving Retrieval Effectiveness, IEEE Transactions on Knowledge and Data Engineering, v.16 n.1, p.28-40, January 2004 [doi>10.1109/TKDE.2004.1264820]
• 20: McCallum, A. and Nigam, K. 1998. A comparison of event models for naive bayes text classification. In Proceedings of the AAAI/ICML-98 Workshop on Learning for Text Categorization. 41--48.
• 21: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 22: Alexander Pretschner , Susan Gauch, Ontology Based Personalized Search, Proceedings of the 11th IEEE International Conference on Tools with Artificial Intelligence, p.391, November 08-10, 1999
• 23: Kazunari Sugiyama , Kenji Hatano , Masatoshi Yoshikawa, Adaptive web search based on user profile constructed without any effort from users, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988764]
• 24: Tan, Q., Chai, X., Ng, W., and Lee, D. 2004. Applying co-training to clickthrough data for search engine adaptation. In Proceedings of the 9th International Conference on Database Systems for Advanced Applications (DASFAA 04). 519--532.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services

General Terms:
Algorithms, Performance

Keywords:
Personalization, clickthrough data, search engine, user preferences