03/12/2003 GEREC-F

Classification automatiquede textes

Pascal Vaillant

GEREC-F / DEMOLI

(Groupe d’Études et de Recherches en Espace Créolophone et Francophone,équipe Description et Modélisation Linguistique)

Université des Antilles et de la GuyaneB.P. 7207

97275 Schœlcher

Martinique

03/12/2003 GEREC-F

Classification automatique

• La classification automatique de textes consiste à attribuer une catégorie à chaque texte.

03/12/2003 GEREC-F

Textes et catégories

• L’ensemble des textes est donné, au moins en partie ;

• L’ensemble des catégories peut être ou ne pas être donné.

• Quand l’ensemble des catégories n’est pas donné au départ, il s’agit de le créer en regroupant les textes en classes qui possédent un certain degré de cohérence interne

• On parle alors de clustering

03/12/2003 GEREC-F

Clustering

• Exemple fictif (2 variables) :

03/12/2003 GEREC-F

Catégories connues

• Dans le cas où on connaît à l’avance les catégories :

• Contraintes possibles :– un texte peut appartenir à plusieurs catégories à la fois

(ex. rubriques thématiques d’un index de bibliothèque) ;

– ... ou un texte doit appartenir à une catégorie et une seule (ex. rubriques de classement Dewey d’une bibliothèque).

03/12/2003 GEREC-F

Cas de figure de base

• On traite en général comme cas de figure de base le second cas (une seule catégorie par texte) ;

• ... en effet le premier cas peut s’y ramener :• on peut traiter la question

« à quelles catégories (parmi l’ensemble {C1...Cn}) appartient ce texte ? »comme la combinaison de n questions binaires : « ce texte appartient-il à la catégorie Ck ou non (i.e. ou à sa catégorie complémentaire Ck) ? »

03/12/2003 GEREC-F

Catégorisation déterministe ou floue

• On peut également souhaiter dans certains cas :– avoir une réponse définitive pour chaque texte

(oui ou non, le texte ti appartient à la catégorie Ck) ;– ... ou avoir simplement une évaluation des catégories

les plus adéquates — dans l’ordre — pour y classer le texte ti

• Certaines méthodes (qui évaluent une distance d’un texte à une catégorie) permettent facilement le deuxième type de classement, d’autres pas.

03/12/2003 GEREC-F

Comment classer ?• Il faut fournir à l’ordinateur une fonction lui

permettant d’associer une catégorie à un texte• Il faut d’abord déterminer les variables

pertinentes• Puis un type de fonctions de classement :

– règles de décision– arbres de décision– classificateurs linéaires– autres fonctions ...

03/12/2003 GEREC-F

Quelles variables ? (1)

• N’importe quel paramètre observable du document peut constituer une variable.

• On peut compter le nombre d’occurrences :– de caractères, combinaisons de 2, de 3 caractères ...– de mots, combinaisons de 2 mots, 3 mots ...– d’étiquettes morphologiques (N,V,Adj ...)– de combinaisons mot + étiquette morphologique ...

• Ou compter des co-occurrences de cesdifférentes choses

03/12/2003 GEREC-F

Quelles variables ? (2)

• On peut normaliser ces données :– fréquence d’occurrence de tel ou tel mot, caractère ...– fréquence de co-occurrence de tel mot avec tel autre ...

• On peut rapporter à un corpus plus vaste pour obtenir des paramètres plus spécifiques :– fréquence d’occurrence de tel mot divisée par sa

fréquence globale ;– fréquence de co-occurrence du mot m1 avec le mot m2

divisée par la fréquence d’occurrence de m1 ...

03/12/2003 GEREC-F

Quelles fonctions ?

03/12/2003 GEREC-F

Règles de décision

• Si (x=1) et (y=0) alors C1

• Si (x=1) et (y=1) alors C2

• Si ((x=0) et (y=1)) ou ((x=0) et (z=1)) alors C3

etc.

• Avantage : forme de fonction de décision la plus interprétable par des humains

03/12/2003 GEREC-F

Arbres de décision

x < 2 x > 2

–1 < y < –½

–½ < y < +½

z = 0 z = 1+½ < y < +1

C1 C2 C3 C2 C4

03/12/2003 GEREC-F

Classificateurs linéaires (1)

• Inconvénient des règles ou arbres de décision :on ne peut prendre que des décisions binaires

• Classificateurs linéaires :

a1x x+a1y y+a1z z pour la catégorie C1a2x x+a2y y+a2z z pour la catégorie C2...

• La réponse n’est pas forcément 0 ou 1, elle est intermédiaire (quand la fonction est normalisée)

03/12/2003 GEREC-F

Classificateurs linéaires (2)

• Le classificateur linéaire crée un hyperplan (i.e. coupe l’espace en deux) : d’un côté, ce qui est dans la catégorie, de l’autre côté, ce qui n’y est pas.

• Modélisation simpliste mais facile (et rapide) à calculer par une machine.

• Les coefficients ne sont en revanche pas interprétables « intuitivement » par des humains.

03/12/2003 GEREC-F

Classificateurs bayésiens

• Fondés sur l’idée qu’on peut estimer la probabilité qu’un document appartient à une catégorie en connaissant la probabilité qu’une catégorie corresponde à ce document.

Formule de Bayes :

P(Ci|dj) =P(Ci).P(dj|Ci)

P(dj)

03/12/2003 GEREC-F

Réseaux neuronaux

• « Boîte noire » constituée d’éléments extrêmement simples (neurones) se comportant comme des fonctions de seuil ;

• Chaque neurone prend en entrée une combinaison des signaux de sortie de plusieurs autres neurones, affectés de coefficients (les poids) ;

• La combinatoire des combinaisons linéaires et des fonctions de seuil appliquées récursivement donne un classificateur complexe.

03/12/2003 GEREC-F

Méthodes géométriques

• Méthode du centroïde : on calcule le centroïde de chaque catégorie, puis on attribue à chaque document la catégorie du centroïde le plus proche.

• Méthode des « k plus proches voisins » : on attibue à chaque document la catégorie majoritaire parmi les k documents les plus proches dont la catégorie est déjà connue.

03/12/2003 GEREC-F

Méthodes géométriques

03/12/2003 GEREC-F

Comment déterminer la fonction ?• Dans tous ces cas de figure, il faut déterminer les

paramètres de la fonction de classement utilisée :– Règles dans les règles de décision– Conditions et branchements dans les arbres de décision– Coefficients dans les classificateurs linéaires– Distributions de probabilité dans les classificateurs

probabilistes– Poids dans les réseaux de neurones

…• Seules les deux premières approches se prêtent à une

modélisation « manuelle » (faite par un expert).

03/12/2003 GEREC-F

Apprentissage automatique (1)

• Mais l’approche manuelle est coûteuse en temps de travail, peu générique, et relativement peu efficace.

• L’autre solution consiste à faire apprendre automatiquement à l’ordinateur, sur la base d’un corpus de textes qui servent d’exemple, les paramètres de la fonction.

03/12/2003 GEREC-F

Apprentissage automatique (2)

• Pour cela, on constitue un corpus d’apprentissage, qui va servir d’entrée à un algorithme d’apprentissage.

• On sélectionne un autre corpus qui sert pour l’évaluation (corpus de test)

• On infère, à partir des données, et par des méthodes mathématiques complexes, les paramètres des fonctions de classement.

03/12/2003 GEREC-F

Apprentissage automatique (3)

• On se fonde sur la connaissance préalable des bonnes catégories pour les documents du corpus d’apprentissage (apprentissage supervisé).

• Le clustering est un cas d’apprentissage non supervisé.• En outre, il existe des méthodes pour combiner les

résultats de classifieurs simples (et pas très bons) pour donner des classifieurs plus complexes (et bien meilleurs) :– Procédures de vote– Boosting

03/12/2003 GEREC-F

Applications

• Classification de documents en catégories thématiques …

• Lorsque ceci se déroule en ligne, analyse de flots de données comme : dépêches d’agence de presse, messages de courrier électronique (filtres de spam), pages web …

• Indexation automatique sur des catégories d’index de bibliothèques.

03/12/2003 GEREC-F

Autres applications en recherche

• Identification de langue (linguistique) ;• Identification d’auteurs de textes d’origine

douteuse ou inconnue (recherches littéraires) ;• Moteurs de recherche ;• Notation automatique des copies d’étudiants …

03/12/2003 GEREC-F

Retour de connaissance

• Les paramètres qui ont été appris automatiquement fournissent des connaissances utiles sur la nature exacte des catégories connues auparavant intuitivement.