This paper describes the participation of LIG lab, in the batch filtering task for the INFILE (INformation FILtering Evaluation) campaign of CLEF 2009. As opposed to the online task, where the server provides the documents one by one, all of the documents are provided beforehand in the batch task, which explains the fact that feedback is not possible in the batch task. We propose in this paper a batch algorithm to learn category specific thresholds in a multiclass environment where a document can belong to more than one class. The algorithm uses k-nearest neighbor algorithm for filtering the 100,000 documents into 50 topics. The experiments were run on the English corpus. Our experiments gave us a precision of 0.256 while the recall was 0.295. We had participated in the online task in INFILE 2008 where we had used an online algorithm using the feedbacks from the server. In comparison with INFILE 2008, the recall is significantly better in 2009, 0.295 vs 0.260. However the precision in 2008 were 0.306. Furthermore, the anticipation in 2009 was 0.43 as compared with 0.307 in 2008.
The goal of the INFILE (INformation FILtering Evaluation) [
The k-nearest neighbor (kNN) algorithm is a largely investigated supervised learning algorithm due to its simplicity and performance. It aims at finding the k nearest neighbors of an example x (based either on similarity or distance) and then finding the most represented class in the nearest neighbors in order to classify x. Similarity has deemed to be more appropriate as compared to distance, specially while dealing with texts. In such case, the cosine measure is used instead of euclidean or mahanalobis distances.
In this paper, we develop a batch algorithm to learn category-specific thresholds in a multiclass environment. Our algorithm uses kNN algorithm along with cosine similarity, in order to filter the documents into various topics.
The rest of the paper is organized as follows: Section 2 describes the batch algorithm developed for the INFILE campaign, experiments and results are discussed in Section 3 while we conclude in Section 4. 2
Batch Algorithm for the INFILE Campaign
In order to filter the documents into various topics, we use a similarity measure between new
documents and topics, along with a set of thresholds on this similarity that evolve over time. The
similarity between a new document d, to be filtered, and a topic ti can given as:
sim(ti, d) = α ∗ cos(ti, d) +(1 − α) max(d′6=d,d′∈ti)cos(d, d′)
| {z } | {z }
s1(ti,d) s2(ti,d)
(1)
where α ∈ [
Construction of initial set: for each topic i (i ∈{101,102,...,150} find 10 nearest neighbors based on s1 = cos(ti, d) for each nearest neighbor found
ti ⇐ N N Assignment of remaining documents to topics: α = 0.7 for each topic i
θi = mind∈ti sim(ti, d)) for each document d for each topic i if (sim(ti, d) ≥ θi)
ti ⇐ d θi = min(θi, mind∈tisim(ti, d))
Yang et al. [
We present here, a detailed comparison between the batch algorithm of 2009 and the online algorithm developed for the online campaign, 08. For time constraints, we were not able to participate in the online task this year. The online algorithm is presented below: Construction of initial set: α = 0.7, θ1 = 0.42 for each new document d for each topic i (i ∈ {101,102,...,150} if ( li < 10 ) if (s1(ti, d) > θ1)
Ask for feedback (if possible) and ti ⇐ d if feedback positive Assignment of remaining documents to topics: for each new document d for each topic i (i ∈{101,102,...,150} if (sim(ti, d) > θi2)
ti ⇐ d θi2 = mind∈tisim(ti, d) where li represents the number of documents assigned to a topic i. For each topic, two thresholds are used: the first one (θ1) allows filtering the documents in the early stages of the process (when only a few documents have been assigned to the topic). The value chosen for this threshold was 0.42. The second threshold (θ2), however, works with the global similarity, after a certain number of documents have been assigned to the topic. In addition, the algorithm makes use of the feedbacks (50 in total), so that only relevant documents are placed in the different topics.
The main difference between the two algorithms (batch and online) lies in the manner in which we construct the initial set of documents pertinent to the topics. In batch algorithm, we just rely on finding the 10 nearest neighbors for each topic, with the assumption that the nearest neighbors for a topic, would in general, belong to the topic under consideration. However, for the online algorithm, we use feedbacks if the similarity between a topic ti and a document d, is greater than a certain threshold (θ1). The rest of the algorithms are almost the same. 4
We have run our algorithm on INFILE English corpus. For all of the documents, stemming was
performed using Porter’s algorithm. This was followed by the removal of stop-words, XML tags
skipping and the building of a document vector (which associates each term with its frequency)
using Rainbow [
There are 1597 documents relevant to one or more topics in the INFILE data. The results for
the different runs were evaluated based on different measures, namely, precision, recall, F-measure,
linear utility, anticipation (added in 2009) and detection cost (see [
Table 1 describes the different runs along with the number of documents retrieved and the number of relevant documents found. The average score (the values are first computed for each of the 50 profiles and then averaged) is given in Table 2. We can note that Run 1 has the best recall (0.295) as compared with the second run. The F-measure for the two runs is roughly the same. However, Run 2 surpasses Run 1 in terms of average precision. The overall detection cost is very low in these two runs, with Run 1, being more economical. This is a strong point for these runs. The linear utility of Run 2 is greater than that of Run 1. On contrary, the anticipation for Run 1 (0.430) is significantly better than that of Run 2 (0.307).
We can easily conclude from these results, that for the online algorithm, the initial set of documents can be constructed in the same manner as that for the batch algorithm. In this case, we can find 10 nearest neighbors for each topic instead of relying on feedbacks from the server. 5
We have presented, in this paper, a simple extension of the kNN algorithm using thresholds to define a batch filtering algorithm. The results obtained can be deemed encouraging as the Fmeasure equals approximately 20%, for a collection of 100,000 documents and 50 topics, out of which only 1597 documents are relevant. In comparison with online results of 2008, we have a much better recall (almost 30% against 26% in 2008) along with a lower detection cost (0.002 vs 0.007) and a much better anticipation (0.430 vs 0.307). Considering the evolution of different measures, we had observed that the values for all of the measures increase, with the increase in the number of documents filtered. Furthermore, the comparison between batch and online algorithms indicate that, while building the initial set of documents, one can use the nearest neighbors for each topic, rather than relying on feedbacks from the server.