Classification supervisée de documents

1. Introduction
La classification automatique supervisée de document devient nécessaire à cause du volume de documents échangés et stockés sur support électronique. A la différence de la classification non supervisée où l’ordinateur doit découvrir lui-même des groupes de documents, la classification supervisée suppose qu’il existe déjà une classificationde documents. C’est le cas par exemple d’une bibliothèque ou d’un moteur de recherche comme Yahoo !. Le but est alors de classer automatiquement un nouveau document. Comme les documents sont nombreux ou que leur nombre augmente sans cesse, il serait difficile de programmer à l’avance des règles de décision pour déterminer la classe d’un nouveau document. Même si cela était possible, ces règlesdevraient être régulièrement modifiées par l’utilisateur pour qu’elles reflètent la réalité actuelle. Nous présentons donc des méthodes d’apprentissage qui, à partir de documents déjà classés, permettent de classer de nouveaux documents. Nous nous intéressons donc ici aux algorithmes d’apprentissage supervisés, c’est à dire où les réponses du programme sont fixées à l’avance (la hiérarchie de Yahooou la catalogue de la bibliothèque). De façon simple, le but de l’algorithme est de découvrir pourquoi chaque document d’exemple a été rangé dans telle ou telle classe, afin de prédire la classe de nouveaux documents à ranger dans le futur. La plupart des algorithmes d’apprentissage supervisés tentent donc de trouver un modèle — une fonction mathématique – qui explique le lien entre des donnéesd’entrée et les classes de sortie. Ces jeux d’exemples sont donc utilisés par l’algorithme. Dans le cas de la classification de documents, on fournit donc à la machine des exemples sous la forme (Document, Classe). Cette méthode de raisonnement est appelée inductive car on induit de la connaissance (le modèle) à partir des données d’entrée (les Documents) et des sorties (leurs Catégories). Grâce àce modèle, on peut alors déduire les classes de nouvelles données : le modèle est utilisé pour prédire. Le modèle est bon s’il permet de bien prédire. Une méthode ne cherche pas à calculer de modèle : c’est le cas du raisonnement à partir d’exemples (K plus proches voisins, Category-based Search). Il existe de nombreuses méthodes d’apprentissage supervisé : – K plus proches voisins (et sesvariantes : Category-based Search et Cluster-based Search) – arbres de décisions (http://www.dbmsmag.com/9807m05.html) – Naïve Bayes (ou encore Simple Bayes) – réseaux de neurones – machines à support de vecteurs (ou SVM) – Programmation génétique Vous trouverez une très bonne documentation dans le livre de Tom Mitchell « Machine Learning » (ISBN 0071154671). Nous décrivons succinctement ces différentesméthodes et détaillons les plus utilisées pour la classification supervisée de documents : K plus proches voisins, arbres de décision et Naïve Bayes. Parmi toutes les méthodes, Naïve Bayes l’emporte souvent dans les expériences menées jusqu’ici par les équipes de recherche. Pourtant, très récemment (1999), une nouvelle technique appelée Support Vector Machine (SVM) semble donner de meilleursrésultats.

1. K plus proches voisins et ses améliorations
Plus connus en anglais sous le nom K-nearest neighbor (K-NN) [Weiss and Kulikowski 1990], ou encore Memory Based Reasoning [Stanfill and Waltz 1986] Cette méthode diffère des traditionnelles méthodes d’apprentissage car aucun modèle n’est induit à partir des exemples. Les données restent telles quelles : elles sont simplement stockées enmémoire. Pour prédire la classe d’un nouveau cas (où ranger un nouveau document ?), l’algorithme cherche les K plus proches voisins de ce nouveau cas et prédit (s’il faut choisir) la réponse la plus fréquente de ces K plus proches voisins. La méthode utilise donc deux paramètres : le nombre K et la fonction de similarité pour comparer le nouveau cas aux cas déjà classés.

Ces valeurs sont…