Machine Learning Approach to Search Query Classification

Machine Learning Approach to Search Query Classification

Isak Taksa (Baruch College, City University of New York, USA), Sarah Zelikovitz (The College of Staten Island, City University of New York, USA) and Amanda Spink (Queensland University of Technology, Australia)
Copyright: © 2009 |Pages: 16
DOI: 10.4018/978-1-59904-974-8.ch016
OnDemand PDF Download:


Search query classification is a necessary step for a number of information retrieval tasks. This chapter presents an approach to non-hierarchical classification of search queries that focuses on two specific areas of machine learning: short text classification and limited manual labeling. Typically, search queries are short, display little class specific information per single query and are therefore a weak source for traditional machine learning. To improve the effectiveness of the classification process the chapter introduces background knowledge discovery by using information retrieval techniques. The proposed approach is applied to a task of age classification of a corpus of queries from a commercial search engine. In the process, various classification scenarios are generated and executed, providing insight into choice, significance and range of tuning parameters.
Chapter Preview


Machine learning for text classification is an active area of research, encompassing a variety of learning algorithms (Sebastiani, 2002), classification systems (Barry et al., 2004) and data representations (Spink and Jansen, 2004). Classification of search queries is one example of text classification that is particularly complex and challenging. Typically, search queries are short, reveal very few features per single query and are therefore a weak source for traditional machine learning. This chapter focuses on two specific areas of machine learning: short text classification problems and using a small set of labeled documents. We examine the issues of non-hierarchical (Cesa-Bianchi et al., 2006) classification and introduce a method that combines limited manual labeling, computational linguistics and information retrieval to classify a large collection of search queries. We discuss classification proficiency of the proposed method on a large search engine query log, and the implication of this approach on the advancement of short-text classification.

For this discussion we view query logs as sets of textual data on which we perform classification (Jansen, 2006). Observed in this way, each query in a log can be seen as a document that is to be classified according to some pre-defined set of labels, or classes. The approach described in this chapter classifies a corpus of search queries from the Excite search engine, by retrieving from the Web a set of background knowledge to learn additional features that are indicative of the classes. Viewing the initial log with the search queries as a document corpus D = {d1, d2,…di,...dn}, we create a set of classes that indicate a personal demographic characteristic of the searcher, C = {c1, c2,…cj,}. We present an approach that allows classification or the assignment of a class from the set C to many of the documents in the set D. This approach consists of the following five steps:

  • I.

    Select (from the print and the online media) a short set of manually chosen terms Tinit = {t1, t2,…,tj,…,tm} consisting of terms tj that are known a priori to be descriptive of a particular class cj

  • II.

    Use this initial set T to classify a small subset of (search queries) set D thereby creating an initial set of classified queries Qinit = {q1, q2,…qj...ql}

  • III.

    Submit these queries qj to a commercial search engine and use the returned search results to build a temporary corpus of background knowledge Btemp = {b1, b2,…*10}

  • IV.

    Use an algorithm to select from B more class related terms T

  • V.

    Use this newly created set T to classify more documents (search queries) in corpus D thereby adding more classified queries to set Q.

While steps I and II are executed only once, steps III through V are repeated continuously until the classification process is terminated (Figure 1).

Figure 1.

Steps in a classification process

We focus on validating our approach to the classification of a set of short documents, namely search queries. This approach uses a combination of techniques: we first look at developing a method to obtain relevant background knowledge for a set of web queries; then we build the background knowledge to acquire ranked terms for improved information retrieval; we then investigate the impact of the new terms’ selection algorithms on the effectiveness of the classification process.

Key Terms in this Chapter

Information Gain: The amount of information in a given set of data can be defined as (1 – entropy). If any observation about the given data is made, new information can then be recomputed. The difference between the two information values is the “information gain”. In other words, the change of entropy is the information that is gained by the observation. If we partition a set T into T1 and T0, based upon some characteristic of the data then the information gain of that partition can be defined as .

Machine Learning: The area of artificial intelligence that studies the algorithms and processes that allow machines to learn. These algorithms use a combination of techniques to learn from examples, from prior knowledge, or from experience.

Text Classification: Process of assigning classes (or labels) to textual data. Textual data can range from short phrases to much longer documents. Sometimes referred to as “text categorization”, a text classification task can be defined as follows: Given a set of documents D = {d1, d2,…,dn} and a set of classes C = {c1,c2,…,cm} assign a label from the set C to each element of set D.

Background Knowledge: Body of text, images, databases, or other data that is related to a particular machine learning classification task. The background knowledge may contain information about the classes; it may contain further examples; it may contain data about both examples and classes.

Labeled Set: Set of item-label pairs. The item consists of an actual example that can be classified, and the label is the classification. In a supervised learning paradigm this set is sometimes referred to as the “training set”.

Entropy: Measurement that can be used in machine learning on a set of data that is to be classified. In this setting it can be defined as the amount of uncertainty or randomness (or noise) in the data. If all data is classified with the same class, the entropy of that set would be 0. The entropy of a set T that has a probability distribution of classes {p1, p2,…pn} can be defined as .

Unlabeled Set: Set of examples whose labels or classes are unknown. If the class of an unlabeled example is learned, it can then be added to a “labeled set”.

Complete Chapter List

Search this Book:
Table of Contents
Bernard J. Jansen, Amanda Spink, Isak Taksa
Chapter 1
Bernard J. Jansen, Isak Taksa, Amanda Spink
This chapter outlines and discusses theoretical and methodological foundations for transaction log analysis. We first address the fundamentals of... Sample PDF
Research and Methodological Foundations of Transaction Log Analysis
Chapter 2
W. David Penniman
This historical review of the birth and evolution of transaction log analysis applied to information retrieval systems provides two perspectives.... Sample PDF
Historic Perspective of Log Analysis
Chapter 3
Lee Rainie, Bernard J. Jansen
Every research methodology for data collection has both strengths and limitations, and this is certainly true for transaction log analysis.... Sample PDF
Surveys as a Complementary Method for Web Log Analysis
Chapter 4
Sam Ladner
This chapter aims to improve the rigor and legitimacy of Web-traffic measurement as a social research method. I compare two dominant forms of... Sample PDF
Watching the Web: An Ontological and Epistemological Critique of Web-Traffic Measurement
Chapter 5
Kirstie Hawkey
This chapter examines two aspects of privacy concerns that must be considered when conducting studies that include the collection of Web logging... Sample PDF
Privacy Concerns for Web Logging Data
Chapter 6
Bernard J. Jansen
Exploiting the data stored in search logs of Web search engines, Intranets, and Websites can provide important insights into understanding the... Sample PDF
The Methodology of Search Log Analysis
Chapter 7
Anthony Ferrini, Jakki J. Mohr
As the Web’s popularity continues to grow and as new uses of the Web are developed, the importance of measuring the performance of a given Website... Sample PDF
Uses, Limitations, and Trends in Web Analytics
Chapter 8
Danielle Booth
This chapter is an overview of the process of Web analytics for Websites. It outlines how visitor information such as number of visitors and visit... Sample PDF
A Review of Methodologies for Analyzing Websites
Chapter 9
Gi Woong Yun
This chapter discusses validity of units of analysis of Web log data. First, Web log units are compared to the unit of analysis of television to... Sample PDF
The Unit of Analysis and the Validity of Web Log Data
Chapter 10
Kirstie Hawkey, Melanie Kellar
This chapter presents recommendations for reporting context in studies of Web usage including Web browsing behavior. These recommendations consist... Sample PDF
Recommendations for Reporting Web Usage Studies
Chapter 11
Seda Ozmutlu, Huseyin C. Ozmutlu, Amanda Spink
This chapter summarizes the progress of search engine user behavior analysis from search engine transaction log analysis to estimation of user... Sample PDF
From Analysis to Estimation of User Behavior
Chapter 12
Gheorghe Muresan
In this chapter, we describe and discuss a methodological framework that integrates analysis of interaction logs with the conceptual design of the... Sample PDF
An Integrated Approach to Interaction Design and Log Analysis
Chapter 13
Brian Detlor, Maureen Hupfer, Umar Ruhi
This chapter provides various tips for practitioners and researchers who wish to track end-user Web information seeking behavior. These tips are... Sample PDF
Tips for Tracking Web Information Seeking Behavior
Chapter 14
Sandro José Rigo
Adaptive Hypermedia is an effective approach to automatic personalization that overcomes the difficulties and deficiencies of traditional Web... Sample PDF
Identifying Users Stereotypes for Dynamic Web Pages Customization
Chapter 15
Brian K. Smith, Priya Sharma, Kyu Yon Lim, Goknur Kaplan Akilli, KyoungNa Kim, Toru Fujimoto
Computers and networking technologies have led to increases in the development and sustenance of online communities, and much research has focused... Sample PDF
Finding Meaning in Online, Very-Large Scale Conversations
Chapter 16
Isak Taksa, Sarah Zelikovitz, Amanda Spink
Search query classification is a necessary step for a number of information retrieval tasks. This chapter presents an approach to non-hierarchical... Sample PDF
Machine Learning Approach to Search Query Classification
Chapter 17
Seda Ozmutlu, Huseyin C. Ozmutlu, Amanda Spink
This chapter emphasizes topic analysis and identification of search engine user queries. Topic analysis and identification of queries is an... Sample PDF
Topic Analysis and Identification of Queries
Chapter 18
Elmer V. Bernstam, Jorge R. Herskovic, William R. Hersh
Clinicians, researchers and members of the general public are increasingly using information technology to cope with the explosion in biomedical... Sample PDF
Query Log Analysis in Biomedicine
Chapter 19
Michael Chau, Yan Lu, Xiao Fang, Christopher C. Yang
More non-English contents are now available on the World Wide Web and the number of non-English users on the Web is increasing. While it is... Sample PDF
Processing and Analysis of Search Query Logs in Chinese
Chapter 20
Udo Kruschwitz, Nick Webb, Richard Sutcliffe
The theme of this chapter is the improvement of Information Retrieval and Question Answering systems by the analysis of query logs. Two case studies... Sample PDF
Query Log Analysis for Adaptive Dialogue-Driven Search
Chapter 21
Mimi Zhang
In this chapter, we present the action-object pair approach as a conceptual framework for conducting transaction log analysis. We argue that there... Sample PDF
Using Action-Object Pairs as a Conceptual Framework for Transaction Log Analysis
Chapter 22
Paul DiPerna
This chapter proposes a new theoretical construct for evaluating Websites that facilitate online social networks. The suggested model considers... Sample PDF
Analysis and Evaluation of the Connector Website
Chapter 23
Marie-Francine Moens
This chapter introduces information extraction from blog texts. It argues that the classical techniques for information extraction that are commonly... Sample PDF
Information Extraction from Blogs
Chapter 24
Adriana Andrade Braga
This chapter explores the possibilities and limitations of nethnography, an ethnographic approach applied to the study of online interactions... Sample PDF
Nethnography: A Naturalistic Approach Towards Online Interaction
Chapter 25
Isak Taksa, Amanda Spink, Bernard J. Jansen
Web log analysis is an innovative and unique field constantly formed and changed by the convergence of various emerging Web technologies. Due to its... Sample PDF
Web Log Analysis: Diversity of Research Methodologies
About the Contributors