Memoire Online - Algorithmes d'apprentissage pour la classification de documents

La recherche accorde ces dernières années, beaucoup d'importance au traitement des données textuelles. Ceci pour plusieurs raisons : un nombre croissant de collections mises en réseau et distribuées au plan international, le développement de l'infrastructure de communication et de l'Internet. Les traitements manuels de ces données s'avèrent très coûteux en temps et en personnel, ils sont peu flexibles et leur généralisation à d'autres domaines est presque impossible ; c'est pour cela que l'on cherche à mettre au point des méthodes automatiques.

Le domaine de la fouille de textes (text mining) s'est développé pour répondre à volonté à la gestion par contenu des sources volumineuses de textes. A l'heure actuelle, de nombreux logiciels de classification de textes sont disponibles, ils ont fait l'objet de publications et leurs champs d'application s'élargit de jour en jour. En général, ces systèmes sont basés sur des algorithmes d'apprentissage automatique (approche statistique, approche syntaxique et approche connexionniste).

Nous nous intéressons ici plus particulièrement aux algorithmes d'apprentissage et nous avons utilisé et comparé deux algorithmes : les K plus proches voisins (Kppv) et l'algorithme de Rocchio. Pour pouvoir utiliser de tels algorithmes, il est nécessaire de transformer les données, initialement en format texte, en une représentation numérique. Nous avons choisi pour ce faire, la méthode de sélection des termes les plus pertinents. Une fois ce prétraitement terminé, nous pouvons effectuer la classification à l'aide de nos algorithmes ; ensuite nous ferons une étude comparative entre les deux méthodes.

· Le chapitre I : résume l'explication de la catégorisation de texte et ses domaines d'applications.

· Le chapitre II : expose les différents algorithmes d'apprentissage utilisé pour la catégorisation de textes et expose en détail les deux algorithmes d'apprentissage utilisés : les K plus proches voisins (Kppv) et l'algorithme de Rocchio.

· Le chapitre III, expose l'architecture du logiciel conçu et son fonctionnement.

· Le chapitre IV, est consacré à l'implémentation de notre logiciel et quelques exemples de démonstration

CHAPITRE I

L'objet d'étude de ce mémoire : la catégorisation automatique de textes ; c'est un problème qui intéresse les chercheurs depuis relativement longtemps. On retrouve des travaux portant sur ce sujet depuis au moins le début des années 1960.

La recherche dans ce domaine est toujours très pertinente, car les résultats obtenus aujourd'hui sont encore sujets à amélioration. Pour certaines tâches, les classificateurs automatiques performent presque aussi bien que les humains, mais pour d'autres, l'écart est encore grand. Au premier abord, l'essentiel du problème est facile à saisir. D'un côté, on est en présence d'une banque de documents textuels et de l'autre, d'un ensemble prédéfini de catégories. L'objectif est de rendre une application informatique capable de déterminer de façon autonome, dans quelle catégorie classer chacun des textes, à partir de leur contenu, tel qu'illustré à la figure 1. [Sim, 2005].

Malgré cette première définition très simple, la solution n'est pas immédiate et plusieurs facteurs sont à prendre en considération. Ce chapitre vise donc à définir plus en profondeur de quoi il en retourne. En premier lieu, il précise la tâche de Catégorisation (classification), et le deuxième point présente le choix d'un mode de représentation adéquat des instances à traiter, en l'occurrence les textes. Il s'agit d'une étape incontournable en apprentissage automatique : on doit opter pour une façon uniforme et judicieuse d'abstraire les données avant de les soumettre à un algorithme. Comme l'apprentissage joue un rôle dans la catégorisation automatique de textes, le choix d'un mode de représentation y devient un enjeu. Par la suite, il sera question de la sélection d'attributs, presque toujours impliqués en catégorisation automatique de textes et on éliminera les attributs jugés inutiles à la classification. [Sim, 2005].

Le but de la catégorisation automatique de textes est d'apprendre à une machine à classer un texte dans la bonne catégorie en se basant sur son contenu. Habituellement, les catégories font référence aux sujets des textes, mais pour des applications particulières, elles peuvent prendre d'autres formes. En effet, on peut résoudre, par des techniques de catégorisation, des problèmes tels que l'identification de la langue d'un document, le filtrage du courrier électronique pertinent ou indésirable, ou encore la désambiguïsation de termes. Un autre aspect du problème qui varie selon les applications est la présence ou non d'une contrainte concernant le nombre de catégories assignables à un document donné. Il se peut qu'on désire qu'un même texte ne soit associé qu'à une seule catégorie ou bien on peut permettre que plusieurs catégories accueillent un même document. Aussi, une précision supplémentaire est à faire : dans le cadre de la catégorisation de textes, l'ensemble de catégories possibles est déterminé à l'avance. Il est à noter que le problème consiste à regrouper des documents selon leur similarité.

Dans une catégorisation de texte : la classification s'apparente au problème de l'extraction de la sémantique d'un texte, puisque l'appartenance d'un document à une catégorie est étroitement liée à la signification de ce texte. C'est en partie ce qui rend la tâche difficile puisque le traitement de la sémantique d'un document écrit en langage naturel n'est pas encore solutionné. Une observation mérite aussi d'être faite concernant le fait que la nature des textes à traiter influence significativement la difficulté de la tâche de classification. Prenons l'exemple d'articles de journaux écrits généralement dans un style direct et contenant de l'information purement factuelle. Le vocabulaire utilisé s'avère précis et souvent relativement restreint pour faciliter la compréhension. A l'opposé, imaginons un corpus de textes d'un style plus littéraire, utilisant un vocabulaire très varié et imagé. On peut aisément prévoir que la classification automatique de ce dernier corpus présentera plus de difficultés que pour l'autre. Entre ces deux extrêmes, on peut aussi retrouver des textes scientifiques (où chaque catégorie aura potentiellement un vocabulaire caractéristique), des pages Web, du courrier électronique, etc. Chacun de ces types de textes possède des particularités qui rendent la tâche de classification plus ou moins ardue. [Sim, 2005].

Le processus de catégorisation intègre la construction d'un modèle de prédiction qui, en entrée, reçoit un texte et, en sortie, lui associe une ou plusieurs étiquettes.

Pour identifier la catégorie ou la classe à laquelle un texte est associé, un ensemble d'étapes est habituellement suivies. Ces étapes concernent principalement la manière dont un texte est représenté, le choix de l'algorithme d'apprentissage à utiliser et comment évaluer les résultats obtenus pour garantir une bonne généralisation du modèle appris.

Le processus de catégorisation, intégrant la phase de classement de nouveaux textes, est résumé dans la figure 2. Il comporte deux phases que l'on peut distinguer comme suit :

1. l'apprentissage, qui comprend plusieurs étapes et aboutit à un modèle de prédiction:

a) nous disposons d'un ensemble de textes étiquetés (pour chaque texte nous connaissons sa catégorie) ;

b) à partir de ce corpus, nous extrayons les k descripteurs (mots, termes) (t₁; ..; t_k) les plus pertinents au sens du problème à résoudre ;

c) nous disposons alors d'un tableau « descripteurs × individus », et pour chaque texte nous connaissons la valeur de ses descripteurs et son étiquette;

a) recherche puis pondération des occurrences (t₁; ...; t_k) des termes dans le texte d_x à classer ;

b) application d'un algorithme d'apprentissage sur ces occurrences et le tableau précédent afin de prédire l'étiquette de ce texte d_x. [Rad, 2003].

Notons que les k descripteurs les plus pertinents (t₁; ...; t_k) sont extraits lors de la première phase par analyse des textes du corpus d'apprentissage. Dans la seconde phase, celle du classement d'un nouveau texte, nous cherchons simplement la fréquence de ces k descripteurs (t₁; ...; t_k) dans le texte à classer.

Un codage préalable du texte est nécessaire, comme pour l'image, le son, etc., car il n'existe pas actuellement de méthode d'apprentissage capable de traiter directement des données non structurées, ni dans la phase de construction du modèle, ni lors de son utilisation en classement.

Pour la majorité des méthodes d'apprentissage, il faut transformer l'ensemble des textes en un tableau croisé « Individus-Variables » :

- L'individu est un texte (un document) d_j, étiqueté lors de la phase d'apprentissage, il est classé dans la phase de prédiction.

- Les variables sont les descripteurs (les termes) t_k qui sont extraits des données textuelles.

- Le contenu du tableau (les éléments w_kj), au croisement du texte j et du terme k, représente le poids de ce terme k dans le document j.

Le principal enjeu de la catégorisation de texte, par rapport à un processus d'apprentissage classique, réside dans la recherche des descripteurs (ou termes) les plus pertinents pour le problème à traiter. Différentes méthodes sont proposées pour le choix des descripteurs et des poids associés à ces descripteurs. Certains chercheurs utilisent, à titre d'exemples, les mots comme descripteurs, tandis que d'autres préfèrent utiliser les lemmes (racines lexicales); ou encore des stemmes (la suppression d'affixes). [Rad, 2003].

La catégorisation de textes est utilisée dans de nombreuses applications. Parmi ces domaines figurent : l'identification de la langue, la reconnaissance d'écrivains, la catégorisation de documents multimédia, et bien d'autres.

La catégorisation de textes peut être un support pour différentes applications parmi lesquelles le filtrage, qui consiste à déterminer si un document est pertinent ou non (décision binaire), par exemple la détection de spams (les courriers indésirables) pour ensuite les supprimer, le routage qui permet d'affecter un document à une ou plusieurs catégories parmi n, par exemple la diffusion sélective d'information. Lors de la réception d'un document l'outil choisit à quelles personnes le faire parvenir en fonction de leurs centres d'intérêt. Ces centres d'intérêt correspondent à des profils individuels. [Rad, 2003].

La catégorisation de texte est proche de la recherche documentaire. En recherche documentaire, on doit retrouver les documents qui correspondent à une requête, ce qui revient à classer tout le corpus en deux classes : les textes correspondant à la requête d'une part, les autres d'autre part. En catégorisation, il s'agit d'attribuer les documents à un ou plusieurs groupes, en fonction des informations qu'ils contiennent.

La recherche documentaire est à l'origine de nombreux modèles de catégorisation de textes. La distinction entre les deux domaines n'est pas facile à établir car ils peuvent être vus tout deux comme des problèmes de classement. [Rad, 2003].

Les algorithmes d'apprentissage ne sont pas capables de traiter directement les textes, plus généralement, les données non structurées comme les images, les sons et les séquences vidéo. C'est pourquoi une étape préliminaire dite représentation est nécessaire. Cette étape consiste généralement en la représentation de chaque document par un vecteur, dont les composantes sont par exemple les mots contenus dans le texte, afin de le rendre exploitable par les algorithmes d'apprentissage. Une collection de textes peut être ainsi représentée par une matrice dont les lignes sont les termes qui apparaissent au moins une fois et les colonnes sont les documents de cette collection. [Rad, 2003].

Un grand nombre de chercheurs dans le domaine ont choisi d'utiliser une représentation vectorielle dans laquelle chaque texte est représenté par un vecteur de n termes pondérés. A la base, les n termes sont tout simplement les n différents mots apparaissant dans les textes de l'ensemble d'entraînement.

Dans la catégorisation de textes, comme dans la recherche documentaire, on transforme le document d_j en un vecteur d_j = (w_1j, w_2j, ...,w_|T|j), où T est l'ensemble de termes (descripteurs) qui apparaissent au moins une fois dans le corpus (la collection) d'apprentissage. Le poids w_kj correspond à la contribution du termes t_k à la sémantique du texte d_j. [Rad, 2003].

La représentation de textes la plus simple a été introduite dans le cadre du modèle vectoriel elle porte le nom de « sac de mots ». L'idée est de transformer les textes en vecteurs dont chaque composante représente un mot. Les mots ont l'avantage de posséder un sens explicite. Cependant, plusieurs problèmes se posent.

Il faut tout d'abord définir ce qu'est « un mot » pour pouvoir le traiter automatiquement.

On peut le considérer comme étant une suite de caractères appartenant à un dictionnaire, ou bien, de façon plus pratique, comme étant une séquence de caractères non délimiteurs encadrés par des caractères délimiteurs.

Les composantes du vecteur sont une fonction de l'occurrence des mots dans le texte. Cette représentation des textes exclut toute analyse grammaticale et toute notion de distance entre les mots : c'est pourquoi cette représentation est appelée « sac de mots » (figure 4) ; d'autres auteurs parlent d'« ensemble de mots » lorsque les poids associés sont binaires. [Rad, 2003].

On appelle "langage informatique" un langage destiné à décrire l'ensemble des actions consécutives qu'un ordinateur doit exécuter. Les langages naturels (par exemple l'anglais ou le français) représentent l'ensemble des possibilités d'expression partagé par un groupe d'individus. Les langages servant aux ordinateurs à communiquer n'ont rien à voir avec des langages informatiques, on parle dans ce cas de protocoles de communication, ce sont deux notions totalement différentes. Un langage informatique est une façon pratique pour nous (humains) de donner des instructions à un ordinateur.

Malgré la simplicité de l'utilisation de mots comme unité de représentation, certains auteurs proposent plutôt d'utiliser les phrases comme unité. Les phrases sont plus informatives que les mots seuls, car les phrases ont l'avantage de conserver l'information relative à la position du mot dans la phrase.

Logiquement, une telle représentation doit obtenir de meilleurs résultats que ceux obtenus via les mots. Mais les expériences présentées ne sont pas concluantes car, si les qualités sémantiques sont conservées, les qualités statistiques sont largement dégradées. [Rad, 2003].

Dans le modèle précédent (représentation en «sac de mots»), chaque flexion d'un mot est considérée comme un descripteur différent et donc une dimension de plus; ainsi, les différentes formes d'un verbe constituent autant de mots. Par exemple: les mots «déménageur, déménageurs, déménagement, déménagements, déménager, déménage, déménagera, etc.» sont considérés comme des descripteurs différents alors qu'il s'agit de la même racine « déménage »; les techniques de désuffixation (ou stemming), qui consistent à rechercher les racines lexicales, et de lemmatisation cherchent à résoudre cette difficulté.

Pour la recherche des racines lexicales, plusieurs algorithmes ont été proposés; l'un des plus connus pour la langue anglaise est l'algorithme de Porter.

La lemmatisation consiste à remplacer les verbes par leur forme infinitive, et les noms par leur forme au singulier. Un algorithme efficace, nommé TreeTagger, a été développé pour les langues anglaise, française, allemande et italienne.

L'extraction des stemmes repose sur des contraintes linguistiques bien moins fortes; elle se base sur la morphologie flexionnelle mais aussi dérivationnelle. De ce fait, les algorithmes sont beaucoup plus simplistes et mécaniques que ceux permettant l'extraction des lemmes; ils sont donc plus rapides; mais leur précision et leur qualité sont naturellement inférieures. [Rad, 2003].

Une fois que l'on choisit les composantes du vecteur représentant un texte j, il faut décider comment coder chaque coordonnée de son vecteur d_j.

Il existe différentes méthodes pour calculer le poids w_kj. Ces méthodes sont basées sur les deux observations suivantes:

1. Plus le terme t_k est fréquent dans un document d_j, plus il est en rapport avec le sujet de ce document.

2. Plus le terme t_k est fréquent dans une collection, moins il sera utilisé comme discriminant entre documents.

· #Tr(t_k) le nombre de documents de cet ensemble dans lesquels apparaît au moins une fois le terme t_k.

Selon les deux observations précédentes, un terme t_k se voit donc attribuer un poids d'autant plus fort qu'il apparaît souvent dans le document et rarement dans le corpus complet. La composante du vecteur est codée f(#(t_k, d_j)), où la fonction f reste à déterminer. [Rad, 2003].

La première consiste à attribuer un poids égal à l'occurrence du terme dans le document :

Et la deuxième approche consiste tout simplement à associer une valeur binaire (1 si le mot est présent dans le texte, 0 sinon) :

7-7- Codage Term frequency × inverse document frequency (TF × IDF):

Les deux fonctions (1) et (2) précédentes sont rarement utilisées car ces codages appauvrissent l'information : la fonction (2) ne prend pas en compte la fréquence d'apparition du terme dans le texte, (fréquence qui peut constituer un élément de décision important) ; la fonction (1) ne prend pas en compte la fréquence du terme dans les autres textes. [Rad, 2003].

Le codage TF × IDF (acronyme pour «term frequency × inverse document frequency») a été introduit dans le cadre du modèle vectoriel, il donne beaucoup d'importance aux mots qui apparaissent souvent à l'intérieur d'un même texte, ce qui correspond bien à l'idée intuitive que ces mots sont plus représentatifs du document. Mais sa particularité est qu'elle donne également moins de poids aux mots qui appartiennent à plusieurs documents : Pour refléter le fait que ces mots ont un faible pouvoir de discrimination entre les classes. [Sim, 2005].

· #Tr(t_k) le nombre de documents de cet ensemble dans lesquels apparaît au moins une fois le terme t_k.

Le codage TF × IDF ne corrige pas la longueur des documents. Pour ce faire, le codage TFC est similaire à celui de TF×IDF : mais, il corrige la longueur des textes par la normalisation en cosinus, afin de ne pas favoriser les documents les plus longs. [Rad, 2003].

CHAPITRE II

En apprentissage automatique, différents types de classificateurs ont été mis au point, et cela dont le but d'atteindre un degré maximal de précision et d'efficacité, chacun ayant ses avantages et ses inconvénients. Mais, ils partagent toutefois des caractéristiques communes.

Parmi la panoplie de classificateurs existants, on peut faire des regroupements et distinguer des grandes familles.

Dans les pages qui suivent, nous allons exposer quelques algorithmes en détail, le classificateur bayésien naïf algorithme surpassé par d'autres mais il est souvent utilisé comme point de référence à cause de sa simplicité, l'algorithme de Rocchio. Puis, les machines à support vectoriel et l'algorithme des k-voisins les plus proches, qui représentent vraisemblablement à l'heure actuelle les deux meilleurs choix en catégorisation de textes.

Comme son nom l'indique, ce classificateur se base sur le théorème de Bayes permettant de calculer les probabilités conditionnelles. Dans un contexte général, ce théorème fournit une façon de calculer la probabilité conditionnelle d'une cause sachant la présence d'un effet, à partir de la probabilité conditionnelle de l'effet sachant la présence de la cause ainsi que des probabilités a priori de la cause et de l'effet.

On peut résumer son utilisation lorsqu'il est appliqué à la classification de textes ainsi :

- On cherche la classification qui maximise la probabilité d'observer les mots du document.

- Lors de la phase d'entraînement, le classificateur calcule les probabilités qu'un nouveau document appartienne à telle catégorie à partir de la proportion des documents d'entraînement appartenant à cette catégorie. Il calcule aussi la probabilité qu'un mot donné soit présent dans un texte, sachant que ce texte appartient à telle catégorie.

- Par la suite, quant un nouveau document doit être classé, on calcule les probabilités qu'il appartienne à chacune des catégories à l'aide de la règle de Bayes et des chiffres calculés à l'étape précédente.

La probabilité à estimer est donc : P( c_j | a₁ , a₂ , a₃ , ..., a_n )

On peut omettre de calculer le dénominateur, qui reste le même pour chaque catégorie.

En guise de simplification, on calcule P (a₁, a₂, a₃, ..., a_n | c_j) ainsi :

(6)

La probabilité qu'un mot apparaisse dans un texte est indépendante de la présence des autres mots du texte. On sait que cela est faux. Par exemple, la probabilité de présence du mot «artificielle» dépend partiellement de la présence du mot «intelligence». Pourtant, cette supposition n'empêche pas un tel classificateur de présenter des résultats satisfaisants. Et surtout, elle réduit de beaucoup les calculs nécessaires. Sans elle, il faudrait tenir compte de toutes les combinaisons possibles de mots dans un texte, ce qui d'une part impliquerait un nombre important de calculs, mais aussi réduirait la qualité statistique de l'estimation, puisque la fréquence d'apparition de chacune des combinaisons serait très inférieure à la fréquence d'apparition des mots pris séparément. [Sim, 2005].

Pour estimer la probabilité P (a_i| c_j), on pourrait calculer directement dans les documents d'entraînement la proportion de ceux appartenant à la classe c_j qui contiennent le mot a_i. Cependant, l'estimation ne serait pas très valide pour des numérateurs petits.

Dans le cas extrême où un mot ne serait pas du tout rencontré dans une classe, sa probabilité de 0 dominerait les autres dans le produit ci-dessus et rendrait nulle la probabilité globale. Pour pallier ce problème, une bonne façon de faire est d'utiliser le m-estimé qui est calculé ainsi :

La méthode de Rocchio est un classifieur linéaire proposé dans [Rocchio, 1971], un des plus vieux algorithmes de classification déstiné à l'amélioration des systèmes de recherche documentaires.

L'avantage de ce type de classifieurs est la simplicité et l'interprétabilité. Pour un expert, ce profil prototype est plus compréhensible qu'un réseau de neurones par exemple. L'apprentissage de ce type de classifieur est souvent précédé par une sélection et une réduction de termes.

Ce classifieur s'appuie sur une représentation vectorielle des documents : chaque document d_j est représenté par un vecteur d_j de Rⁿ (n est le nombre de termes après sélection et réduction); chaque coordonnée t_kj se déduit du nombre d'occurrences # (t_k, d_j) du terme t_k dans d_j , par :

· #T_r(t_k) : le nombre de documents dans lesquels apparaît au moins une fois le terme t_k.

Un terme t_k se voit donc attribuer un poids d'autant plus fort qu'il apparaît souvent dans le document et rarement dans le corpus complet. Chaque vecteur d_j est ensuite normalisé, par la normalisation en cosinus, afin de ne pas favoriser les documents les plus longs.

Selon la méthode de Rocchio, Chaque catégorie est représentée par un profil «prototypique». Un profil de la classe c_i est une liste de termes pondérés, dont la présence et l'absence discriminent au mieux cette classe c_i. [Mat, 2003].

Pour chaque catégorie c_i, les coordonnées t_ki du profil prototypique c_i = (t_1i, · · · , t|_T|_i) sont calculé ainsi :

t : un paramètre du modèle compris entre 0 et 1. Dans les situations où un document peut être attribué à une seule classe, t est souvent positionné à 1.

Les profils prototypes c_i correspondent donc aux barycentres des exemples (avec un coefficient positif pour les exemples de la classe, et négatif pour les autres). Le classement de nouveaux documents s'opère en calculant la distance euclidienne entre la représentation vectorielle du document et celle de chacune des classes ; le document est assigné à la classe la plus proche. [Mat, 2003].

L'algorithme des k-voisins les plus proches («k-nearest neighbors» ou kNN) est une méthode d'apprentissage à base d'instances.

La méthode ne nécessite pas de phase d'apprentissage; c'est l'échantillon d'apprentissage, associé à une fonction de distance et à une fonction de choix de la classe en fonction des classes des voisins les plus proches, qui constitue le modèle.

Lorsqu'un nouveau document à classer arrive, il est comparé aux documents d'entraînement à l'aide d'une mesure de similarité. Ses k plus proches voisins sont alors considérés : on observe leur catégorie et celle qui revient le plus parmi les voisins est assignée au document à classer. C'est là une version de base de l'algorithme que l'on peut raffiner. Souvent, on pondère les voisins par la distance qui les sépare du nouveau texte.

Un réseau de neurones (ou Artificial Neural Network en anglais) est un modèle de calcul dont la conception est très schématiquement inspiré du fonctionnement de vrais neurones (humains ou non). Les réseaux de neurones sont généralement optimisés par des méthodes d'apprentissage de type statistique grâce à leur capacité de classification et de généralisation, tels que la classification automatique de codes postaux ou la prise de décision concernant un achat boursier en fonction de l'évolution des cours. Ils enrichissent avec un ensemble de paradigmes permettant de générer de vastes espaces fonctionnels, souples et partiellement structurés .Ils appartient d'autre part à la famille des méthodes de l' intelligence artificielle qu'ils enrichissent en permettant de prendre des décisions s'appuyant davantage sur la perception que sur le raisonnement logique formel .

Exemple : Une banque peut générer un jeu de données sur les clients qui ont effectué un emprunt constituées : de leur revenu, de leur âge, du nombre d'enfants à charge... et s'il s'agit d'un bon client. Si ce jeu de données est suffisamment grand, il peut être utilisé pour l'entraînement d'un réseau de neurones. La banque pourra alors présenter les caractéristiques d'un potentiel nouveau client, et le réseau répondra s'il sera bon client ou non, en généralisant à partir des cas qu'il connaît.

Un réseau de neurone est en général composé d'une succession de couches dont chacune prend ses entrées sur les sorties de la précédente. Chaque couche (i) est composée de Ni neurones, prenant leurs entrées sur les Ni-1 neurones de la couche précédente. À chaque synapse est associée un poids synaptique, de sorte que les Ni-1 sont multipliés par ce poids, puis additionnés par les neurones de niveau i, ce qui est équivalent à multiplier le vecteur d'entrée par une matrice de transformation. Mettre l'une derrière l'autre, les différentes couches d'un réseau de neurones reviendrait à mettre en cascade plusieurs matrices de transformation et pourrait se ramener à une seule matrice, produit des autres, s'il n'y avait à chaque couche, la fonction de sortie qui introduit une non linéarité à chaque étape. Ceci montre l'importance du choix judicieux d'une bonne fonction de sortie : un réseau de neurones dont les sorties seraient linéaires n'aurait aucun intérêt [1].

Au delà de cette structure simple, le réseau de neurones peut également contenir des boucles qui en changent radicalement les possibilités mais aussi la complexité. De la même façon que des boucles peuvent transformer une logique combinatoire en logique séquentielle, les boucles dans un réseau de neurones transforment un simple dispositif de reconnaissance d'inputs en une machine complexe capable de toute sortes de comportements [1].

Exemple : Ce neurone calcule la somme de ses entrées puis cette valeur passe à travers la fonction d'activation pour produire sa sortie.

Les machines à support vectoriel («Support Vector Machines» ou SVM) proposée dans [Vapnik, 1995] forment une classe d'algorithmes d'apprentissage qui peuvent s'appliquer à tout problème qui implique un phénomène f et qui, à partir d'un jeu d'entrées x, produit une sortie y = f(x), et où le but est de retrouver f à partir de l'observation d'un certain nombre de couples entrée/sortie. Le problème revient à trouver une frontière de décision qui sépare l'espace en deux régions, à trouver l'hyperplan qui classifie correctement les données et qui se trouve le plus loin possible de tous les exemples. On dit qu'on veut maximiser la marge, la marge étant la distance du point le plus proche de l'hyperplan. (Figure 5) [Sim, 2005].

Des techniques de programmation quadratique permettent de résoudre ce problème. Une propriété intéressante des SVM est que la surface de décision est déterminée uniquement par les points qui en sont les plus proches de vecteurs de support. En présence de ces seuls exemples d'entraînement, la même fonction serait apprise.

Même s'ils cherchent l'hyperplan séparant l'espace vectoriel en deux, l'avantage des SVM est qu'ils s'adaptent facilement aux problèmes non linéairement séparables. Avant de procéder à l'apprentissage de la meilleure séparation linéaire, on transforme les vecteurs d'entrée en vecteurs de caractéristiques de dimension plus élevée. De cette façon, un séparateur linéaire trouvé par un SVM dans ce nouvel espace vectoriel devient un séparateur non linéaire dans l'espace original. Cette transformation des vecteurs se fait à l'aide des foncions appelées fonctions noyaux. [Sim, 2005].

Dans le cas de la classification de textes, les entrées sont des documents et les sorties sont des catégories. En considérant un classificateur binaire, on voudra lui faire apprendre l'hyperplan qui sépare les documents appartenant à la catégorie et ceux qui n'en font pas partie. Les SVM conviennent bien pour la classification de textes [Joa98a]. Une dimension élevée ne les affecte pas puisqu'ils se protègent contre le sur-apprentissage. Dans le même sens, il affirme que peu d'attributs sont totalement inutiles à la tâche de classification et que les SVM permettent d'éviter une sélection agressive qui aurait comme résultat une perte d'information. On peut se permettre de conserver plus d'attributs. Egalement, une caractéristique des documents textuels est que lorsqu'ils sont représentés par des vecteurs, une majorité des entrées sont nulles. Or, les SVM conviennent bien à des vecteurs dits clairsemés. [Sim, 2005].

La catégorisation de textes nécessite un choix de technique d'apprentissage (classifieur). Parmi les méthodes d'apprentissage les plus utilisées figurent le classifieur de Rocchio, Classifieur bayésien naïf, les k-plus proches voisins, et plus récemment les machines à vecteurs supports (SVM).

Nous avons choisi la méthode des k plus proche voisins (k-PPV) pour de nombreuses raisons, que nous expliquerons dans les sections qui suivent.

L'idée de base de l'algorithme des k-plus proches voisins (kPPV), traduction de nearest neighbor (kNN) en anglais, est de prédire la classe d'un texte t en fonction des k textes les plus proches voisins déjà étiquetés en mémoire.

L'algorithme 1 montre comment classer un nouvel exemple par la méthode k-PPV.

Contexte : un échantillon de (l) textes classés en C = c₁, c₂, ..., c_n classes

3: déterminer les k plus proches textes du texte t selon une métrique de distance

Le choix de la distance et du paramètre k est primordial pour le bon fonctionnement de la méthode. Nous présentons maintenant les différents choix possibles pour la distance et pour le mode de sélection de la classe du cas présenté. [Rad, 2003].

Une distance est une application de E × E dans R⁺ qui vérifie les propriétés suivantes:

On peut noter qu'un point A peut avoir un plus proche voisin B qui, lui-même, possède de nombreux voisins plus proches que A (Figure 6).

La distance entre un texte et ses voisins se fait via une métrique de distance. Cette métrique peut être la métrique de Minkowski : [Rad, 2003]

La valeur de k est un des paramètres à déterminer lors de l'utilisation de ce type de classificateur. La valeur que l'on choisit pour k va être plus critique, plus déterminante en rapport avec la performance du classificateur. On peut se permettre de considérer un plus grand nombre de voisins, sachant que plus ils diffèrent du document à classer, moins ils ont d'impact sur la prise de décision. Cependant, il demeure nécessaire de limiter le nombre de voisins pour s'en tenir à un temps de calcul raisonnable. [Sim, 2005].

Une des caractéristiques fondamentales de ce type de classificateur est l'utilisation d'une mesure de similarité entre les documents. Les textes étant représentés sous forme vectorielle, donc comme des points dans un espace à n dimensions.

1) On peut au premier abord penser à déterminer les voisins les plus proches en calculant la distance euclidienne entre ces points.

La similarité cosinusoïdale est préférable en classification de textes pour plusieurs raisons :

- Elle permet de comparer des textes de longueurs différentes en normalisant leur vecteur.

- Elle met l'accent plutôt sur la présence de mots que sur l'absence de mots. (La présence de mots est probablement plus représentative de la catégorie du texte que l'absence de mots). [Sim, 2005].

Regardons à l'aide d'un exemple pourquoi la similarité cosinusoïdale est préférable à la distance euclidienne. Nous allons considérer le vocabulaire et les trois documents suivants :

Par exemple le mot « classification » est présent dans le document 1 (indiqué par 1) et absent dans les documents 2 et 3 (indiqué par 0)

La mesure de distance euclidienne indique que le document 3 est moins distant (plus similaire) du document 2 (distance de 1) que le document 2 ne l'est du document 1 (distance de 1.41).

Pourtant, les documents 2 et 3 n'ont aucun mot en commun, alors que les documents 1 et 2 partagent le mot «similarité».

La mesure de similarité cosinusoïdale, pour sa part, retourne une similarité nulle (0) entre les documents 2 et 3, mais positive (0.57) entre les documents 1 et 2.

Ces derniers résultats sont plus représentatifs de la réalité, puisque les documents 1 et 2 partagent au moins un mot, donc présentent une certaine similarité et sont plus susceptibles d'être classés dans la même catégorie que les documents 2 et 3 qui ne partagent aucun mot. [Sim, 2005].

Comme il a déjà été mentionné, le classificateur kNN n'implique pas de phase d'entraînement en tant que telle. La seule opération préalable est le stockage des exemples d'entraînement. L'apprentissage est repoussé au moment où un nouveau document à classer arrive. Par le fait même, la plus grosse part de l'effort requis en termes de temps de calcul est fourni au moment même de la classification.

Une des caractéristiques de l'apprentissage à base d'instances est qu'il n'y a pas de construction d'une description explicite de la fonction à apprendre (dans notre cas, l'appartenance à une catégorie). L'avantage est qu'on n'estime pas qu'une seule fois la fonction pour tout l'espace, mais on l'estime plutôt localement et différemment pour chaque nouvelle instance. [Sim, 2005].

La méthode ne nécessite pas de phase d'apprentissage. Le modèle est constitué de trois éléments :

Il faut choisir l'échantillon, c'est-à-dire les attributs pertinents pour la tâche de classification considérée et l'ensemble des enregistrements. Il faut veiller à disposer d'un nombre assez grand d'enregistrements par rapport au nombre d'attributs et à ce que chacune des classes soit bien représentée dans l'échantillon choisi.

La distance par variable et le mode de combinaison de ces distances sont choisis en fonction du type des variables et des connaissances préalables concernant le domaine.

Une heuristique fréquemment utilisée pour le choix du nombre k de voisins est de prendre k égal au nombre d'attributs plus 1.

L'emploi de k voisins, au lieu d'un seul, assure une plus grande robustesse à la prédiction.

Classiquement, dans le cas où la variable à prédire comporte deux étiquettes, ce paramètre k est une valeur impaire afin d'avoir une majorité plus facilement décidable. [Rad, 2003].

CHAPITRE III

1. Introduction

Ce chapitre est essentiellement consacré aux grandes lignes qui visent à réaliser l'objectif de ce thème, et les outils exploités pour le développement du logiciel tels que le choix du langage de programmation, l'environnement de programmation, le matériel utilisé, le modèle conceptuel et les principales fonctions de traitement à utiliser.

2. Environnement matériel et logiciel

2.1. Configuration matérielle et logicielle

2.3 L'environnement de programmation

2.1.1 JBuilder :

JBuilder est un environnement de développement intégré (EDI) développé par la société Borland. JBuilder permet de développer des applications Java fonctionnant avec la machine virtuelle de Sun Microsystems. Etant donné que JBuilder est lui-même écrit en Java, il est distribué pour la plupart des systèmes d'exploitation (Windows, Linux, Solaris et MacOS X). JBuilder est à l'origine un outil de développement professionnel destiné à l'entreprise. Néanmoins, Borland a eu l'excellente idée de fournir une version légèrement bridée de son outil pour la communauté Open Source. Vous trouverez de plus amples informations concernant les différences entre les différentes versions sur le site de Borland.

3. Modélisation par une méthode conceptuelle(UML) :

3.1. Définition d'UML :(Unified Modeling Language ) :

UML est un langage de modélisation unifié (créé en 1994), né de la fusion des trois méthodes de modélisation d'objet :

UML est un langage pour visualiser, spécifier, construire et documenter les abstractions d'un système logiciel.

3.2. Les avantages d'UML

· UML est un langage formel et normalisé : il permet un gain de précision et de stabilité.

· UML est un support de communication performant : il permet grâce à sa représentation graphique, d'exprimer visuellement une solution objet, de faciliter la comparaison et l'évolution de solution.

3.3. Les diagrammes d'UML

Un diagramme UML est une représentation graphique, qui permet de modéliser un aspect bien précis du système, chaque type de diagramme UML possède une structure et des concepts prédéfinis.

Un diagramme donne à l'utilisateur un moyen de visualiser et de manipuler des éléments de modélisation.

Au total UML définit treize types de diagrammes. Mais, nous avons eu besoin d'utiliser seulement cinq diagrammes parmi les treize proposés par ce langage.

Ce choix nous a permis de bien comprendre le fonctionnement de ces quatre diagrammes, et de maîtriser leur usage au sein de notre projet de classification des pages web.

· Diagramme de cas d'utilisation représente les fonctions du système du point de vue des utilisateurs ;

· Diagramme de classes montre une collection d'éléments statiques (classes), leur contenu (attributs, opérations, types) et les relations entre eux (associations). Permet de décrire la structure statique d'un système.

· Les diagrammes de composants permettent de décrire l'architecture physique et statique d'une application en terme de modules : fichiers sources, librairies, exécutables, etc.

· Les diagrammes de séquence sont une représentation temporelle des objets et de leurs interactions.

- Permettre de bien comprendre le fonctionnement du système ; modéliser la vie des objets dans le temps et leur chronologie.

· Les diagrammes d'états-transitions représentent le comportement d'un classificateur ou d'une méthode en terme d'états ;

Diagramme d'états-transitions sert à représenter des automates d'états finis, sous forme de graphes d'états, reliés par des arcs orientés qui décrivent les transitions.

- Les diagrammes d'état-transitions permettent de décrire les changements d'états d'un objet ou d'un composant, en réponse aux interactions avec d'autres objets/composants ou avec des acteurs.

- Une transition est déclenchée par un événement. En d'autres termes : c'est l'arrivée d'un événement qui conditionne la transition.

Diagramme de cas d'utilisation:

Sacmot

String Source

Vector vecteur

String Sac_mot

Void RemplirVecteur()

Void Charger_Sacmot()

Class_C
String Texte[]
Boolean TrouveString (String Str, String fichier) Int NbreTexte(String rech)
kPPV
VecteurTexte vTexte
kPPV (VecteurTexte vTexte) decision()

VecteurTexte

String fich

Vector vecteur

VecteurTexte ( String fich,

Rocchio

VecteurTexte vTexte

Rocchio (VecteurTexte vTexte)

decision()

Comparer le vecteur de fréquence de texte à classer avec les vecteurs de fréquences des textes d'apprentissage C1 (médecine)

Comparer le vecteur de fréquence de texte à classer avec les vecteurs de fréquences des textes d'apprentissage (non médecine)

CHAPITRE 4

L'architecture suivante représente le fonctionnement de notre application. Son fonctionnement est composé de plusieurs étapes qui peuvent être visualisées une par une, ces étapes principales sont :

Etape1 : L'utilisateur ouvre l'interface principale (Navigateur, Explorateur). Les vecteurs d'occurrences de textes d'apprentissage interdits et autorisés sont calculés et transformés en vecteurs de fréquences automatiquement après l'exécution de l'application.

Etape3 : L'algorithme choisi charge le vecteur de mots clés et représente le texte à classer (vecteurs d'occurrences).

Etape4 : L'algorithme choisi transforme le vecteur d'occurrences de texte à classer en vecteur de fréquences selon le codage de la méthode.

Etape5 : L'algorithme calcule la similarité entre le texte à classer et les textes d'apprentissage si la méthode choisie est kPPV ou la similarité entre le texte à classer et les profils prototypiques des deux classes (médecine/non médecine) en cas de l'algorithme de Rocchio.

Etape6 : Selon la métrique de prise de décision de l'algorithme choisi, le fichier sera classé.

Notre prototype se compose d'une fenêtre principale à partir de laquelle l'utilisateur peut effectuer les opérations ou les traitements désirés en sélectionnant un élément du menu ou en cliquant sur un bouton de la barre.

CONCLUSION

Nous avons présenté dans ce mémoire, les nouvelles approches d'analyse intelligente de documents qui utilisent les techniques d'apprentissage automatique.

Dans le cadre des méthodes d'apprentissage statistique, nous avons présenté et discuter deux algorithme Rocchio et k les plus proches voisins. La démarche générale est constituée deux étapes, à savoir :

Dans cette dernière phase, la représentation de texte dans un format adapté aux algorithmes d'apprentissage ; on utilise souvent la représentation vectorielle.

Nous avons proposé la méthode Kppv et Rocchio, qui a donné de bons résultats .

L'algorithme Rocchio est simple, en vu des résultat obtenu , on peut conclure que la méthode de Rocchio donne de bons résultats avec un bon taux de précision, l'apprentissage est rapide, permettant de traiter des données volumineuses, elle convient donc particulièrement bien au problème de la fouille de textes.

Il serait maintenant intéressant de poursuivre cette recherche, qui a permis de découvrir les avantages de ces algorithmes dans le cadre de la catégorisation de texte. Nous espérons que cette contribution pourra ouvrir de nouvelles perspectives à d'autres collègues et d'ouvrir un champ de recherche.

BIBLIOGRAPHIE :

· [Sim, 2005] : SIMON RÉHEL : « Catégorisation automatique de textes et cooccurrence de mots provenant de documents non étiquetés »

Mémoire présenté à la Faculté des études supérieures de l'Université Laval, Québec, Janvier 2005

· [Rad, 2003] : RADWAN JALAM : « Apprentissage automatique et catégorisation de textes multilingues » Université Lumière Lyon2, Juin 2003.

· [Mat, 2003] : MATHIEU VALETTE : « Application d'algorithmes de classification automatique pour la détection des contenus racistes sur l'Internet », Juin 2003

· [Sal, 2005] : SALAH BOUKTIF : «Amélioration de la prédiction de la qualité du logiciel par combinaison et adaptation de modèles » Université de Montréal, Mai 2005.

· [Sim Jai, 2003] : SIMON JAILLET : « Catégorisation automatique de documents ». Année 2003.

· [Ouv, 2003] : SIMON JAILLET, Maguelonne Teisseire, Jacques Chauche et Violaine Prince : « Classification automatique de documents, Le coefficient des deux écarts » LIRMM-CNRS - Université Montpellier 2, Année 2003.

· [Phi, 2005] : PHILIPPE PREUX : « Fouille de données, Notes de cours » Université de Lille 3, Juillet 2005.

· [Ant, 2002] : ANTOINE CORNUÉJOLS : « Une nouvelle méthode d'apprentissage : Les SVM. Séparateurs à vaste marge » Université de Paris-Sud, Orsay, Juin 2002.

· [2] : « Projet de fin d'étude " Algorithmes d'apprentissage pour la classification des pages WEB" », 2005-2006

Algorithmes d'apprentissage pour la classification de documents

INTRODUCTION