WOW !! MUCH LOVE ! SO WORLD PEACE !
Fond bitcoin pour l'amélioration du site: 1memzGeKS7CB3ECNkzSn2qHwxU6NZoJ8o
  Dogecoin (tips/pourboires): DCLoo9Dd4qECqpMLurdgGnaoqbftj16Nvp


Home | Publier un mémoire | Une page au hasard

 > 

Algorithmes d'apprentissage pour la classification de documents


par yasmine Hanane zeggane Mokhtar -
Université de Mostaganéme -Algérie- - licence 2009
  

sommaire suivant

INTRODUCTION

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.

Nous résumons la présentation de notre travail ainsi :

· 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

1- Introduction :

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]. 

Programme informatique

Texte

Texte classifié, étiqueté

Ensemble de catégories, hiérarchisées ou non

Figure 1 - La tâche de classification

2- Définition de la catégorisation de textes :

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]. 

3- Comment catégoriser un texte ?

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) (t1; ..; tk) 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;

2. le classement d'un nouveau texte dx, qui comprend deux étapes :

a) recherche puis pondération des occurrences (t1; ...; tk) des termes dans le texte dx à 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 dx. [Rad, 2003].

Textes catégorisés

Textes à classifier

Représentation

Textes d'apprentissage

Représentation

Modèle de catégorisation

Prédiction de la catégorie

Figure 2: Processus de la catégorisation de textes

Notons que les k descripteurs les plus pertinents (t1; ...; tk) 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 (t1; ...; tk) dans le texte à classer.

Les deux phases seront développées dans le chapitre 2.

La figure 3 illustre le processus de classification d'un nouveau document. 

Sélection d'attributs et Représentation des documents

Texte à classer

ti

Représentation abstraite du texte {ai,k}

Classification par le programme

Texte classifié, étiqueté

<ti, f(ai,k)>

Figure 3 - Classification d'un nouveau document

4- Représentation et codage des textes :

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) dj, étiqueté lors de la phase d'apprentissage, il est classé dans la phase de prédiction.

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

- Le contenu du tableau (les éléments wkj), 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].

5- Applications de la catégorisation de texte:

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].

6- Lien avec la recherche documentaire:

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].

7- Approches pour la représentation des textes :

7-1- Introduction :

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.

7-2- Choix de termes :

Dans la catégorisation de textes, comme dans la recherche documentaire, on transforme le document dj en un vecteur dj = (w1j, w2j, ...,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 wkj correspond à la contribution du termes tk à la sémantique du texte dj. [Rad, 2003].

7-3- Représentation en « sac de mots » :

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.

6

3

3

...

...

...

...

...

2

1

1

langage

informatique

ordinateur

protocole

instruction

communi

Figure 4 - Exemple de la représentation d'un texte en « sac de mots »

7-4- Représentation des textes par des phrases :

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].

7-5- Représentation des textes avec des racines lexicales et des lemmes :

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].

7-6- Codage des termes :

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 dj.

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

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

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

Soient :

· #(tk, dj) le nombre d'occurrences du terme tk dans le texte dj ,

· |Tr| le nombre de documents du corpus d'apprentissage,

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

Selon les deux observations précédentes, un terme tk 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(#(tk, dj)), où la fonction f reste à déterminer. [Rad, 2003].

Deux approches peuvent être utilisées :

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

Wkj = #(tk, dj) (1)

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

1 Si #(tk, dj) > 1

Wkj = (2)

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]. 

Le poids d'un terme tk dans un document dj est calculé ainsi :

(3)

· # (tk, dj) : Nombre d'apparition de terme tk dans le document dj.

· |Tr| le nombre de documents du corpus d'apprentissage,

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

7-8- Codage TFC :

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].

(4)

sommaire suivant