Based on the idea that the closer the query terms in a document are, the more relevant this document is, we propose a information retrieval method based on a fuzzy proximity degree of term occurences to compute document relevance to a query. Our model is able to deal with Boolean queries, but contrary to the traditional extensions of the basic Boolean information retrieval model, it does not explicitly use a proximity operator. A single parameter allows to control the proximity degree required. We explain how we construct the queries and we report the results of the experiments of the CLEF 2005 campaign before the conclusion.
In information retrieval domain, systems are founded on three basic ones models: The Boolean model, the vector model and the probabilistic model which were derived within many variations (extended Boolean models, models based on fuzzy sets theory, generalized vector space model,. . . ) [1]. Though they are all based on weak representations of documents: either sets of terms or bags of terms. In the first case, what the information retrieval system knows about a document is if it contains or not a given term. In the second case, the system knows the number of occurence -term frequency, tf -of a given term in each document. So whatever is the order of the terms in the documents, they share the same index representation if they use the same terms. The worthy of note exceptions are most of the Boolean model implementations which propose a near operator [10]. This operator is a kind of and but with the constraint that the different terms are within a window of size n, where n is an integral value. The set of retrieved documents can be restricted with this operator, for instance, it is possible to discriminate documents about "data structures" and those about "data about concrete structures". The result is an increase in precision of the system [5]. But the Boolean systems that implement a near operator share the same limitation as any basic Boolean system : These systems are not able to rank the retrieved documents because with this model a document is or is not relevant to a query. In fact, different extensions were proposed to the basic Boolean systems to circumvent this limitation. These extensions represents the documents with some kind of term weights most of the time computed on a tf basis. Then they apply some combining formulas to compute the document score given the term weigths and the query tree. But these extensions are not compatible with the near operator. So some works defined models that attempt to directly score the documents by taking into account the proximity of the query terms within them.
Three methods were proposed to score the documents by taking into account some set of intervalls containing the query terms. These methods differ in the set of intervalls that are selected in a first step, and then in the formulas used to compute a score for a given interval. The method of Clarke and al. [2] selects the shortest intervals that contains all the query terms (This constraint is relaxed if there are not enough retrieved documents), so the intervals can not be nested. In the methods of Hawking and al. [4], for each query term occurence, the shortest interval containing all the query terms is selected, thus the selected intervals can nest. Rasolofo and al. [8] chose to select intervals only containing two terms of the query, but with the additionnal constraint that the interval is shorter than five words. Moreover, the passage retrieval methods use indirectly the notion of proximity. In fact, in several methods, document ranking is doing by selecting documents which have passages with high density of query terms that-is-to-say documents where the query terms are closed [11,3,6]. The next section presents our method based on term proximity to score the documents.
To address the problem of scoring the documents by taking into account the relative order of the words in the document, we have defined a new method based on a fuzzy proximity between each position in the document text and a query. First, given a document d and a term t, we define a term proximity function w d,t . We can use different types of kernel (hamming, rectangular, gaussian) for the function but a triangular one is computed. A k constant controls the support of the function and this support represents the extent of each term occurence influence. This function reaches its maximum (value 1) at each occurence of the term t in the document d and linearly decreases on each side down to 0. So for each query term t, we determine the fuzzy proximity at each position of the document d retrieved. When the zone of influence of two terms occurrences overlaps in a document position x the value of the nearest term occurrence is taken so:
where Occ(t, d) is the set of occurrence positions of term t in the document d and f the influence function kernel.
The figures 1 and 2 show the fuzzy proximity function w A (resp. w B ) for the term A (resp. B) in the document d 0 and d 1 .
The query model is that of the classical Boolean model: A tree with terms on the leaves an OR or AND operators on the internal nodes. Given a query q, the term proximity functions located on the query tree leaves are combined in the query tree with usual formulas pertaining to the fuzzy set theory. We compute here the fuzzy proximity of the query. So the fuzzy proximity is computed by : w q OR q = max(w q , w q ) for a disjunctive node and by w q AND q = min(w q , w q ). for a conjunctive node. So we obtain a function w d,q from the set of positions in the document text to the interval [0, 1]. The result of the integration of this function is used as the score of the document :
Finally, the computed score s(q, d) depends on fuzzy proximity function and allows to rank document according to query term proximity.
We carried out experiments on the CLEF 2004 evaluation campaign1 test collection. We use the retrieval tool Lucy that which is based on the Okapi BM-25 information retrieval model [9]. to index this collection. This tool is adapted to our method because it keeps in the index the terms positions of the documents. thus, we extend the tool to compute similarity values for our fuzzy proximity matching function. Documents in the CLEF 2005 test collection are newspapers articles in XML format SDA and Le Monde of the years 1994 and 1995. For each document (tag <DOC>), we keep the fields <DOCNO> with the tag and the document number by Lucy, the textual contents of the tags <TX>, <LD>, <TI>, <ST> for SDA French and <TEXT>, <LEAD1>, <TITLE> for Le Monde 1995. We used the topics and the relevance judgements to evaluate the different methods by the trec eval program.
Each topic has three tags: <FR-title>, <FR-desc>, <FR-narr>. We built three set of queries for our experiments. Queries are either manually or automatically built from the textual contents of the "title" and the "description" tags.
For automatic built queries (two sets): For the first set, a query is made of terms from the "title" field; for the second set, a query is made of terms from the "description" field, stop words2 are removed. Below we give the results for the first set of queries. Let show the steps for building an automatic query using the "title" by giving an example with the topic 278. The original topic is expressed by : <top> <num> 278 </num> <FR-title> Les moyens de transport pour handicaps </FR-title> <FR-desc> A quels problmes doivent faire face les personnes handicapes physiques lorsquelles empruntent les transports publics et quelles solutions sont proposes ou adoptes? </FR-desc> <FR-narr> Les documents pertinents devront dcrire les difficults auxquelles doivent faire face les personnes diminues physiquement lorsquelles utilisent les transports publics et/ou traiter des progrs accomplis pour rsoudre ces problmes. </FR-narr> </top> First, the number and the title fields are extracted so we have : <num> C278 </num> <FR-title> Les moyens de transport pour handicaps </FR-title> And we compact like this : 278 moyens transport handicapes From this query, we make some derivations "automatically" : Manual built queries, (one set): are made of terms from the "title" field and additionnaly terms from the "description" field. Moreover, we add the plurial form of the terms and the terms derivation to compensate the Lucy tool lack of stemming. We thus obtain queries that are conjunction of disjunctions of the different derivations of the terms. On the other hand, the evaluation by the Lucy tool uses flat queries that are of different derivations of the terms. We give an example with the topic 278 as previously:
We compare the Okapi model and our fuzzy method with different values of k. As we know on one hand that the Okapi method is one of the best performing one and on the other hand a previous study showed that the proximity based methods improve retrieval [7], we decide to merge the Okapi results list with the results lists provided by proximity based methods. Consequently, if one of the proximity based method does not retrieve enough documents, then its results list is supplemented by the documents from the Okapi results list that have not yet been retrieved by proximity based methods; the maximum number of documents retrieved is 1, 000.
In the officials runs, the queries are constructed : With the values chosen for the officials runs, unfortunally, the Lucy method performs better than the fuzzy proximity ones but when manuals queries are used the result are better or equal to the Lucy ones.
Amount the unofficial runs, we change the value of the k constant to enlarge the area of influence of a term occurrence. In the figure we notice that the largest the area is the better the results are. The fuzzy proximity method perform better with manual queries (run RIMLemme*) because we retrieved more documents with our method so the proximity between query terms is the main factor to select and rank documents.
We have presented and experimented our information retrieval model which takes into account the position of the term occurences in the document to compute a relevance score on the CLEF 2005 Ad-Hoc french test collection. We notice that the higher the area of influence of term is the better the results are. In futher experiments, we are going to use another influence function more flexible which allows to adapt the value of k constant to the number of retrieved documents. We think also that the results can be improved by using stemming step before indexing and by use