Catégorisation automatique de textes

Partie I

INTRO

Références

● Cours en-ligne :

– Michèle Jardino, classification automatiquehttp://www.limsi.fr/Individu/jardino/c3-ii05.ppthttp://www.limsi.fr/Individu/jardino/c2-ii05.ppt

– Fabrizio Sebastiani, Machine Learning Text Categorizationhttp://citeseer.ist.psu.edu/518620.html

– Jose Maria Gomez Hidalgo; Text representation for Automatic Text Categorizationhttp://www.esi.uem.es/~jmgomez/tutorials/eacl03/index.html

Classification

● assigner une ou plusieurs classes à un document (ou assigner un ensemble de documents à une classe)

● opération couteuse car le plus souvent manuelle

● Besoin d'outils informatiques

classification supervisée vs. non supervisée

● supervisée :

– on part d'un ensemble de classes ou catégories établies, étiquetées et pré-remplies de textes.

– on assigne un texte à une ou plusieurs categorie

● non supervisée (tout automatique) :

– on part d'un ensemble de textes, pas de classes prédéfinies

– on regroupe les textes en classes (non étiquetées)

– souvent, un texte n'appartient qu'a une seule classe

classification supervisée vs. non supervisée (2)

● supervisée => catégorisation

– avantage : lisible par l'homme

– désavantage : besoin humain important

● non supervisée => clustering

– avantage : tout automatique

– désavantage : plus difficilement lisible par l'homme

● aujourd'hui, catégorisation

Angles d'attaque du problème

● Etant donné un document d, lui assigner une ou plusieurs categorie(s) c

ex. le cas où on a des documents arrivants en temps réel (courriers électroniques => courrier indesirable ?)

● Etant donnée une catégorie, lui assigner plusieurs documents d

Ex. On a déjà une collection de textes. On veut rajouter une catégorie supplémentaire

Définition formelle

● Soient

– C un ensemble de catégories

– T un ensemble de textes

● Le but est d'assigner une valeur booléenne à chaque paire (c,t) ∈ C x T

● Approximer une fonction f : C x D → {vrai, faux}

Méthodes

● manuel

– précision

– couteux (experts et longs)

● automatique

– peu couteux

– erreurs

Classification aplatie vs. hiérarchique

● aplatie

● hiérarchique

– chaque noeud de l'arbre est une catégorie

– les feuilles sont des références à des documents

ex. google

Hypothèses pour la suite

● On suppose que l'on a une collection de textes Tr déjà classés (dans un ensemble de classes C)

● Les textes sont des vecteurs dans l'expace de termes T de dimension |T|

● cette collection est utile :

– soit pour défrichement d'experts

– soit pour apprentissage automatique de classifieurs

Plan

● Représentation des textes

● Méthodes de catégorisation automatique

● Evaluation

Partie II :

Représentation des textes et

réduction de l'espace

Représentation de textes

● concepts de base = termes

● texte = sac de termes

● terme = mot simple ou séquence multi-mots

● un texte est un vecteur; chaque composante est un nombre (réel ou entier) qui correspond au poids d'un terme donné dans le texte

● Besoin de réduction de l'espace car le nombre de termes |T| est très grand

Termes sous la forme de mots simples

● repérage par tokenisation

● filtrage

– par liste de stopword

– après analyse morpho-syntaxique

● réduction

– racinisation

– lemmatisation

Termes sous la forme de séquences multi-mots

● repérage de séquences multi-mots

– linguistiques : chunks, mots composés; entités nommées

– statistiques : séquences de mots simples apparaissant souvent ensemble (souvent longueur 2)

● réduction

– séquences linguistiques : lemmatisation

– séquences statistiques : filtrage, racinisation et normalisation

ex. information retrieval ; retrieval of information => inform_retriev

– mélange hybride intéressant

Poids des termes

● poids binaire: 1 si terme est dans le document; 0 sinon

● fréquence du terme dans le document

● mesure de tf.idf du terme dans le document (cf. cours précédent)

● autres mesures (tf.idf normalisé, ...)

Réduction (statistique) de la dimension de l'espace

● Certaines méthodes de catégorisation nécessitent une réduction de l'espace de termes pour des raisons d'efficacité

● Plusieurs méthodes:

– sélection de termes pertinents

– extraction de nouvelles entités représentatives(ex. clustering de termes, Latent Semantic Indexing, ...)

Réduction par sélection

● Garder les meilleurs termes en fonction d'une mesure de qualité

● Soit une catégorie c, un concept parfait pour c devrait apparaître dans un texte t si et seulement si t ∈ C ou si et seulement si t C∉

Mesures de qualité

● Mesures indépendantes de la classe

– le nombre de documents dans lequel apparaît le terme (df: document frequency)

● Mesures dépendantes de la classe

– IG (Information Gain)

– 2 (Chi)

Mesures dépendantes de la classe

● Formules: ci une categorie et t

k un terme de l'espace

● Mesure globale avec f comme mesure de qualité

IG t k , ci=P t k , c i logP t k , ci

P c i . P t k P t k , ci log

P t k , c i

P ci . P t k

X 2t k , ci=

∣Tr∣. [P t k ,c i. P t k , ci−P t k , c i . P t k ,c i]2

P t k . P t k . P ci. P ci

f g t k=∑i=1

∣T∣P ci f t k , ci

Partie III :

Méthodes de catégorisation automatique

Ecriture manuelle de règles

● écriture de règles par des experts

● étant donné un document, le système applique les règles pour assigner une catégorie

● avantage: règles fines

● désavantage: couteux

● Les experts peuvent être aidés par des outils de la recherche d'information

Exemple

● exemple de règle (règle booléenne):

occurr(1,X) ET (in_window(10, Z,Y) OU occurr(2,W)) => c Si X apparaît au moins 1 fois etsi Z et Y apparaissent ensemble dans une fenêtre de 10 mots, ou W apparaît au moins 2 fois, alors le document appartient à la catégorie c

Méthodes par apprentissage

● Une méthode par apprentissage consiste à utiliser la collection de textes classés pour approximer un classifieur CSV

i pour chaque categorie c

i de C.

● Pour un nouveau texte t, CSVi indique si t doit être placé

dans la catégorie ci ou pas.

● Formellement, CSVi retourne

– soit un booléen

– soit un réel (t est dans ci ssi cette valeur est supérieure à un

seuil fixé au préalable).

Méthodes par apprentissage

● méthodes probabilistes

● méthodes lineaires

● méthodes par apprentissage paresseux

● méthodes par régression, par SVM

● méthodes par arbres de décision, par induction de règles...

● méthodes par comités

Méthodes probabilistes (1)

● Un classifieur probabiliste CSVi(t

j) peut être vu comme P(c

i|

tj), c-a-d la probabilité qu'un texte representé par un vecteur

de termes (binaire ou pondéré) appartienne à la catégorie ci

● Le but est de résoudre la formule (théorème de Bayes) :

P ci∣t j=P ci . P t j∣c j

P t j

Méthodes probabilistes (2)

● L' estimation de cette équation de Bayes est problématique

● Solution : faire une hypothèse « naive » => les coordonnées des vecteurs de textes sont considérées comme deux à deux indépendantes

P t j∣ci=∏k=1

∣T∣P w kj∣ci

Méthodes probabilistes (3)

● Classifieur le plus connu : classifieur à indépendance binaire

● texte = vecteur binaire de termes

● On a alors (après calcul) :

CSV i t j =∑k=1

∣T∣w kj . log

pki 1 − pki

pki 1 − pki

avec pki=P wkx=1 ∣ci

et pki=P w kx=1 ∣ci

Méthodes probabilistes (4)

● Extensions

– représentation non binaire des textes

– introduire une normalisation par rapport à la longueur des textes (pas évident)

– relachement de l'hypothèse d' indépendance

Méthodes linéaires (1)

● Principe de base: une catégorie ci est representée dans le

même espace de termes que les textes

● Les classifieurs sont définis par (au choix) :

CSV i t j=cos ci , t j [cosinus]

CSV i t j=∑k=1

∣T∣w kj−w ki

2[distance euclidienne ]

CSV i t j=∑k=1

∣T∣

∣w kj−w ki∣ [distance de Manhattan]

Méthodes linéaires (2)

● Deux approches

– apprentissage en une seule fois (ex. Méthode de Rocchio)

– apprentissage incrémentale

but: construire un classifieur à partir d'un texte. Pour chacun des autres textes, affinage incrémental du classifieur

avantage: quand on a pas entièrement Tr dès le départ

Méthode de Rocchio

● Soit POSi, l'ensemble des documents de Tr qui appartiennent à

ci;

NEGAi, l'ensemble des documents de Tr qui ne sont pas dans c

i.

● Le poids wki associé au terme k dans la categorie c

i est défini par

la formule:

● si A = 1 et B = 0, ci est le centroide des documents (points) de c

i

; en général, A grand et B petit

wki=A∑t j∈POS i

wkj

∣POS i∣−B∑t j∈NEGAi

wkj

∣NEGAi∣

Méthode de Rocchio (2)

● Avantages

– facile à implanter

– efficace pour des catégorisations ou un texte ne peut appartenir qu'à une seule catégorie

● Inconvénients

– pas très efficace quand un texte peut appartenir à plusieurs catégories

– certains documents de Tr appartenant à ci initialement ne

seraient pas classé dans ci par le classifieur

Apprentissage incrémental

● Exemple: algorithme du Perceptron

● On initialise tous les wki de c

i à une valeur positive

● pour chaque document tj de c

i, on essaye de le classifier avec la

valeur courante de ci

– si la classification est bonne, on ne fait rien

– sinon

● si tj est un exemple positif de c

i, on augmente les poids

des termes actifs (wkj = 1) d'une valeur donnée

● si tj est un exemple négatif, on les diminue de cette valeur

Méthode par apprentissage paresseux

● pas de construction de la représentation de la catégorie ci

=> apprentissage paresseux

● algorithme le plus connu : algorithme k-NN (k nearest neighbours)

● Pour décider si tj est dans c

i, l'algorithme regarde si les k

documents les plus proches de tj ont été classés dans c

i

– si c'est vrai pour une large part d'entre eux, on place tj dans c

i

– sinon non

Méthode par apprentissage paresseux

● Avantages

– excellente précision de catégorisation (l'un des meilleurs)

– pas de problème avec les textes qui peuvent appartenir à plusieurs catégories

● Inconvénient

– pas très efficace (en temps)

Methode par SVM

● SVM = Support Vector Machine

● Idée: pour chaque catégorie, trouver un hyperplan de l'espace des termes T, qui sépare les exemples positifs des exemples négatifs de Tr, par la plus grande marge possible

● Utilisation de vecteurs de support pour obtenir la marge maximale

● avantage: l'une des meilleures précisions

● inconvénient : ça peut être lent (complexité quadratique)

Apprentissage de règles ou d'un arbre de décision

● Il existe des approches symboliques

● A partir de Tr, on peut faire de

– l'induction de règles;

– l'apprentissage d'un arbre de décision (noeud = terme ; branche: terme présent ou pas ; feuille: appartenance à c

i ou

pas)

● attention : ne pas être trop strict (risque de limitation aux exemples de Tr), relacher certaines contraintes

exemple de solution: réduction de l'espace de termes

Partie IV :

Evaluation

Méthodologie

● On découpe la collection de documents classés en deux sous-ensembles :

– un sous-ensemble pour l'apprentissage (90%)

– un sous-ensemble pour l'évaluation automatique (10%)

● Il est fondamental d'avoir deux ensembles dont l'intersection est vide.

rappel et précision

RéalitéC not C

Système C tp fpnot C fn tn

précision : p=tp

tp fp

rappel : r=tp

tp fn

F1−mesure : F1 =2prpr

Conclusion

● Petit panorama de différentes méthodes de catégorisation automatique de documents

● pour plus de détails,

– cf. références et références des références

– prochaine séance de TP