Building bridges for web query classification

ABSTRACT

Web query classification (QC) aims to classify Web users' queries, which are often short and ambiguous, into a set of target categories. QC has many applications including page ranking in Web search, targeted advertisement in response to queries, and personalization. In this paper, we present a novel approach for QC that outperforms the winning solution of the ACM KDDCUP 2005 competition, whose objective is to classify 800,000 real user queries. In our approach, we first build a bridging classifier on an intermediate taxonomy in an offline mode. This classifier is then used in an online mode to map user queries to the target categories via the above intermediate taxonomy. A major innovation is that by leveraging the similarity distribution over the intermediate taxonomy, we do not need to retrain a new classifier for each new set of target categories, and therefore the bridging classifier needs to be trained only once. In addition, we introduce category selection as a new method for narrowing down the scope of the intermediate taxonomy based on which we classify the queries. Category selection can improve both efficiency and effectiveness of the online classification. By combining our algorithm with the winning solution of KDDCUP 2005, we made an improvement by 9.7% and 3.8% in terms of precision and F1 respectively compared with the best results of KDDCUP 2005.

REFERENCES

• 1: Doug Beeferman , Adam Berger, Agglomerative clustering of a search engine query log, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.407-416, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347176]
• 2: Steven M. Beitzel , Eric C. Jensen , Ophir Frieder , David Grossman , David D. Lewis , Abdur Chowdhury , Aleksandr Kolcz, Automatic web query classification using labeled and unlabeled training data, 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.1076138]
• 3: Luis Gravano , Vasileios Hatzivassiloglou , Richard Lichtenstein, Categorizing web queries according to geographical locality, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956925]
• 4: In-Ho Kang , GilChang Kim, Query type classification for web document retrieval, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860449]
• 5: Zsolt T. Kardkovács , Domonkos Tikk , Zoltán Bánsághi, The Ferrety algorithm for the KDD Cup 2005 problem, ACM SIGKDD Explorations Newsletter, v.7 n.2, p.111-116, December 2005 [doi>10.1145/1117454.1117468]
• 6: Ying Li , Zijian Zheng , Honghua (Kathy) Dai, KDD CUP-2005 report: facing a great challenge, ACM SIGKDD Explorations Newsletter, v.7 n.2, p.91-99, December 2005 [doi>10.1145/1117454.1117466]
• 7: A. McCallum and K. Nigam. A comparison of event models for naive bayes text classication. In AAAI-98 Workshop on Learning for Text Categorization, 1998.
• 8: G. Miller, R. Beckwith, C. Fellbaum, D. Gross, and K. Miller. Introduction to wordnet: an on-line lexical database. International Journal of Lexicography, 3(4):23--244, 1990.
• 9: Fuchun Peng , Dale Schuurmans , Shaojun Wang, Augmenting Naive Bayes Classifiers with Statistical Language Models, Information Retrieval, v.7 n.3-4, p.317-345, September-December 2004 [doi>10.1023/B:INRT.0000011209.19643.e2]
• 10: J. Platt. Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. In A. Smola, P. Bartlett, B. Scholkopf, and D. Schuurmans, editors, Advances in Large Margin Classifiers. MIT Press, 1999.
• 11: Dou Shen , Rong Pan , Jian-Tao Sun , Jeffrey Junfeng Pan , Kangheng Wu , Jie Yin , Qiang Yang, Q²C@UST: our winning solution to query classification in KDDCUP 2005, ACM SIGKDD Explorations Newsletter, v.7 n.2, p.100-110, December 2005 [doi>10.1145/1117454.1117467]
• 12: R. C. van. Information Retrieval. Butterworths, London, second edition edition, 1979.
• 13: David Vogel , Steffen Bickel , Peter Haider , Rolf Schimpfky , Peter Siemen , Steve Bridges , Tobias Scheffer, Classifying search engine queries using the web as background knowledge, ACM SIGKDD Explorations Newsletter, v.7 n.2, p.117-122, December 2005 [doi>10.1145/1117454.1117469]
• 14: Ji-Rong Wen , Jian-Yun Nie , Hong-Jiang Zhang, Query clustering using content words and user feedback, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.442-443, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.384083]
• 15: Yiming Yang , Jan O. Pedersen, A Comparative Study on Feature Selection in Text Categorization, Proceedings of the Fourteenth International Conference on Machine Learning, p.412-420, July 08-12, 1997

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.m Miscellaneous

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

General Terms:
Algorithms, Experimentation

Keywords:
KDDCUP 2005, bridging classifier, category selection, web query classification