In this paper we present an unsupervised approach to Query Classi cation. The approach exploits the Wikipedia encyclopedia as a corpus and the statistical distribution of terms, from both the category labels and the query, in order to select an appropriate category. We have created a classi er that works with 55 categories extracted from the search section of the Bridgeman Art Library website. We have also evaluated our approach using the labeled data of the KDD-Cup 2005 Knowledge Discovery and Data Mining competition (800,000 real user queries into 67 target categories) and obtained promising results.
In Information Science logs analysis and more speci cally Query Classi cation
(QC) has been used to help detecting users web search intent. Query classi
cation studies have shown the di culty of achieving accurate classi cation due to
the inevitably short queries. A common practice is to enrich query with external
information, and to use an intermediate taxonomy to bridge the enriched query
and the target categories. A good summary of such approaches is made by the
KDDCUP 2005 organizers [
In Section 2 we present this approach. In Section 3 we provide a evaluation of its capabilities.
Our approach is based on the vector space model (VSM). The core of the VSM is representing text documents as vectors of identi ers, such as index terms. Each element of the vectors corresponds to a separate term found in the document. If a term occurs in the document, its value in the vector is non-zero. The dimensionality of the vector is the number of words in the vocabulary (the number of distinct words occurring in the corpus). In VSM, weights associated with the terms are calculated based on a heuristic functions. Some of the more popular approaches are term frequency and inverse document frequency.
Using the VSM a similarity function between the vectors of two documents and a query can be de ned. The standard function used is the cosine similarity coe cient, which measures the angle between two vectors.
We have adapted the vector space model to the query classi cation task using the following approach: First, we associate a document that describes the category with each category Ck. We name this document category document CD. For example a CD for the category Basketball must contain information about: the rules of the game, National Basketball Association, FIBA and famous players etc. A CD for the Arts must contain information about i) paining; ii) sculptures; 3) art museums etc. In the second stage of the approach we associate to each query a set of relevant documents found in a document collection. We de ne the category score of query q for category Ck as the maximum value of the cosine similarity between term vectors of the CD of the category and a document relevant to the query Qi. For example we expect to nd a lot of common terms between a document relevant to the query Michael Jordan and the CD for category Basketball and few common terms with the CD of the category Art. Finally as output the approach returns the categories which CD has the highest cosine similarity with a relevant document of the query.
We use relevant documents for a query and not the query because we compare the query terms with CD documents that are not relevant to the query itself. For example the CD of the category Arts does not contain a mentioning of Pablo Picasso but the intersection between it and documents relevant to Pablo Picasso contain a lot of common terms like painting, art, surrealism etc.
In order to make our approach feasible we need a document collection that contains su cient number of documents in order to: 1) Find a big enough CD document for each category. 2) Find documents relevant to the classi ed queries.
The advantage of the proposed approach is that it does not require training data and it is language dependent. The approach will be t greatly from a short category description as this will allow a more correct selection of a CD. 3
In our experiments we used the Wikipedia, a free, web-based, collaborative, multilingual encyclopedia1. We assign as CD for the category with the name X the Wikipedia page with the same title. For example the Wikipedia Page with title Basketball can be used as a CD for the category Basketball. The page describes almost all the important aspect of the game and has a lot of terms in common with documents relevant to queries like: Michael Jordan, NBA Playo s and Chicago Bulls. Respectively the page with the title Hardware contains a lot of terms in common with documents relevant for queries like: intel processors, computer screens and nvida vs intel. 1 http://wwww.wikipedia.org
For some categories the CD assigned by the approach contains short texts that are not su cient for a complete overview of the category. We expand the CD for these categories by concatenating the texts of the pages that contain the name of the category as sub part of the page title. For example the CD for the category Arts can be expanded by concatenating the text of the pages: Liberal arts, Visual arts, Arts College, Art Education, Islamic Arts etc. If the approach does not nd a page with the same title as the category it assigns as CD for the category the concatenation of pages with the name of the category as sub part of the page title or pages that contain the category name in the rst sentence of the page text. 3.1
Bridgeman Art Library
Our rst evaluation is done using the taxonomy and query dataset created
for the ART domain in the Galateas Project [
Our approach was evaluated on the 100 queries annotated by the three annotators into upto 3 categories. The queries were in four languages English , French, German, Dutch and Italian. We have created a classi cation instance for each language by manually translating the name of the categories in each language. For each of these queries we automatically assign the top 3 categories returned by the classi er. Example:
Query: navajo turquoise Category1: Semi-precious Stones Score: 0.228 Category2: Silver, Gold & Silver Gilt: 0.1554 Category3: Botanical Score: 0.1554
In this example the category assigned to the query is Category1 Semi-precious Stones. The results of the evaluation are summarized in Table 1.
KDD Cup 2005
To evaluate our approach we have experimented also with the KDD-Cup 2005
data [
We have evaluated our approach against a gold standard provided by the
organizers (800 queries). Our approach obtained an average F-Measure of 32:2
(Table 1). The state of the art system [
The results obtained are encouraging having in prospective the unsupervised nature of the approach. One of the main di culties were the generic names of categories like Icons and The Arts and Entertainment. The documents for these categories contained terms that were not relevant to the art domain. Also a signi cant problem for the system posed queries that are named entities. These queries were classi ed based on their descriptions into categories relevant to their peculiarities and not in People and Society, Personalities and Places categories. A possible solution to this problem will be to map DBPedia3 hierarchy to the domain categories and use it as a additional source of knowledge.
The results we obtained is encouraging particularly because we did not associated additional information to each queries apart of the documents obtained using Wikipedia. Many of the queries did not produce relevant Wikipedia documents, which is one of the main limitations of our approach. Additional domain corpora will decrease its e ect.