Travail noté sur la recherche d’informations

Consignes du travail noté 3

Vous devez rédiger un court rapport (en format « pdf », « Word 97/2000/XP », « RTF », « OpenDocument » ou « texte ») que vous transmettrez, par courriel, au chargé d’encadrement. Vous devez transmettre votre travail en utilisant l’outil de dépôt.

Le présent travail est noté sur 20 points [1]. Il faut prévoir environ 6 heures pour le faire.

Question 1 (10 points)

Supposons qu’après avoir appliqué un antidictionnaire et un algorithme de lemmatisation à 4 documents, vous obteniez les listes de mots suivantes (en Java) :

String[] D1= {"Lucie", "crayon", "roule"};

String[] D2= {"maison", "rouge"};

String[] D3= {"crayon", "rouge", "maison", "rouge"};

String[] D4= {"policier", "rouge", "congé", "soulier", "rouge"};

Si nous déterminons que pour la requête par mots-clefs « rouge », seuls les documents D1 et D3 sont pertinents, quels seront la précision et le rappel du modèle booléen ?

Écrivez un programme Java qui calcule, pour chaque mot, son facteur idf. Donnez votre résultat dans un tableau.

Avec ce même programme Java, transformez chaque document en vecteur tf.idf. Par exemple, s’il y a 10 mots distincts dans l’ensemble des documents, créez des tableaux de valeurs à virgule flottante (double[] v1 = new double[10] ;) et remplissez les tableaux avec les valeurs tf.idf correspondantes : la position 0 pourrait correspondre au mot « Lucien », la position 1 au mot « crayon », etc. Donnez le résultat dans un tableau.

On peut définir la similarité entre deux documents comme étant le cosinus entre deux vecteurs tf.idf. Calculez la similarité entre tous les documents (il y a $4 \times 4$ similarités à calculer) et présentez le résultat dans un tableau.

Étant donné la requête par mots-clefs « maison rouge », quel document sera jugé comme étant le plus pertinent selon le modèle vectoriel tf.idf ? Faites en sorte que votre programme fasse ce calcul et donnez la réponse. Dans le même esprit, calculez le
score de Hiemstra et al. simplifié $Score(Q,D)=P(D) \prod_{t\in Q} P(t|D)$ en estimant $P(t|D)$ par vraisemblance maximale ( $tf(t,D)/\vert D \vert$ ) et en fixant $P(D)=\vert D \vert / \vert C \vert$ pour chaque document.

Nous appliquerons maintenant à tous les termes une troncature ne retenant que les trois premiers caractères :

String[] D1= {"Luc", "cra", "rou"};

String[] D2= {"mai", "rou"};

String[] D3= {"cra", "rou", "mai", "rou"};

String[] D4= {"pol", "rou", "con", "sou", "rou"};

Si, pour la requête par mots-clefs « rouge » (ou « rou »), seuls les documents D1 et D3 sont pertinents, quels sont la précision et le rappel du modèle booléen avec cette troncature ? Quel a été l’effet de la troncature sur la précision et le rappel ?

Répétez maintenant toutes les opérations en commençant par le calcul du facteur idf et en terminant par le calcul de pertinence, mais cette fois avec cette nouvelle troncature.

Vous devez remettre le code source de votre programme Java (sous la forme d’un fichier .java). Nous vous demandons de ne pas mettre tout le contenu dans une archive (zip,rar) : utilisez un fichier pour votre rapport et d’autres fichiers pour les codes Java.

Question 2 (5 points)

Supposons que $P(rel|D_i)=0,2$ pour tous les documents d’un ensemble. Qu’est-ce que cela signifie pour un ingénieur qui doit appliquer le Probability Ranking Principle ? Calculez $\log P(D_i|rel)/P(D_i/nrel)$ en fonction de $P(rel)$ .

Question 3 (5 points)

Écrivez un programme Java capable de calculer le tableau de suffixes, sans structure auxiliaire, de toute chaîne de caractères. Par exemple, compte tenu de la chaîne « Ler », vous devriez obtenir :

– er
– Ler
– r

ou la séquence de nombres 2,1,3.

Il n’est pas nécessaire que votre implémentation soit particulièrement rapide. Cependant, testez-la avec des chaînes d’une longueur de 10, de 100, de 1000 et de 10 000 caractères en mesurant le temps de calcul. Quelle est la complexité de votre algorithme ? ( $O(n^2)$ , $O(n \log n)$ , etc.)

Vous devez remettre votre code source.
Vous devez remettre le code source de votre programme Java (sous la forme d’un fichier .java).

Les travaux du cours INF 6104 ne sont pas sous une licence Creative Commons.

[1] Il représente 10 % de la note finale du cours.

Semaine 8

Travail noté sur la recherche d’informations