:: Enseignements :: Master :: M1 :: 2009-2010 :: Ingénierie Linguistique 1 ::

Classication supervisée de textes

Dans ce td, nous proposons d'implémenter un outil de classication de textes, utilisant la méthode k-NN et la méthode du centroïde.

Préliminaires

Pour cette séance, vous avez à disposition une collection de dépêches Reuters à l'adresse suivante: /home/ens/mconstan/tal/reuter-collection-tp2 (pour téléchargment, ici). Cette collection de textes bruts a été extraite automatiquement de la collection Reuters-21578. Ces dépêches sont classées dans trois catégories : sugar, coffee et gas. A chaque texte, sont associés la ou les catégories auxquels il appartient. Les différents textes se trouvent dans le répertoire texts.

La collection est divisée en deux sous-collections: l'une pour l'apprentissage (collection-app.lst), l'autre pour l'évaluation (collection-eval.lst). Chacune d'elle est définie par un fichier qui contient la liste des dépêches avec la ou les catégories auxquelles elles appartiennent.

Exercice 1 - Représentation d'un texte

Ecrire une classe CText qui représente un texte catégorisé sous une forme vectorielle. Elle hérite de la classe Text vue au TP précédent (cf. correction). Son constructeur prend le nom du fichier et la liste de ses catégories comme paramètres. Elle possède une méthode supplémentaire: getCategories() qui renvoie la liste des catégories.

Exercice 2 - Représentation d'une collection

Ecrire une classe CTextCollection qui représente une collection de CText. Vous pouvez vous inspirer de la classe TextCollection vue au TP précédent.

Exercice 3 - Algorithme k-NN

Ecrire une fonction knnClassifier qui implémente l'algorithme k-NN. Cette fonction prend trois arguments: un texte t à classifier, une collection d'apprentissage capp et un entier k. Elle calcule les k documents de capp les plus proches de t. Ensuite, elle compte le nombre de fois que chaque catégorie a été attribué à ces k documents. Elle retourne la catégorie la plus fréquente. Tester en faisant varier k.
Modifier la fonction knnClassifier pour qu'elle puisse retourner plus d'une catégorie. Pour cela, rajouter un argument coef qui détermine un seuil à partir duquel les catégories seront attribuées au texte. Ce seuil dépendra du score attribué à la catégorie la plus fréquente dans les k documents les plus proches.
Evaluer le classifieur sur la collection d'évaluation. Indication: tenir compte du fait qu'un document peut être dans plusieurs catégories. Pour cela, calculer la précision et le rappel qui sont définis comme suit:
- Précision (p): le nombre de catégories correctement attribuées par le système divisé par le nombre total de catégories attribuées par le système.
- Rappel (r): le nombre de catégories correctement attribuées par le système divisé par le nombre total de catégories attribuées dans la collection d'évaluation.
Vous pourrez aussi calculer le f-score qui est une moyenne pondérée du rappel et de la précision: f = 2pr/(p+r).

Exercice 4 - Algorithme du centroïde

Implémenter l'algorithme du centroïde. Evaluer et comparer avec la méthode précédente.