13/12/041 Fouille de donnes dans les corpus de textes Michle
Jardino [email protected] Groupe Langues, Information et
Reprsentations http://www.limsi.fr/Recherche/LIR
Page 2
13/12/042 Quest ce que cest? Acqurir des connaissances (donnes)
enfouies (fouille) dans des corpus de textes Extraire des
informations dans la mine des textes lectroniques disponibles en
abondance aujourdhui. Corpus = recueil de documents concernant une
mme discipline (Petit Robert) Un corpus gant : le Web, " THE WEB AS
A CORPUS ", confrence CORPUS LINGUISTICS 2005 En anglais : text
data mining
Page 3
13/12/043 Un 1er exemple Socit de mesure daudience a enregistr
les sites visits par un panel dinternautes. Elle veut mettre en
relation les parcours de ces internautes avec leur description
sociologique Corpus = pages Web visites Objectif : cibler au mieux
une clientle Moyen : chercher traits caractristiques dans les
textes des pages visites par les internautes Projet national RNRT
mlant industriels et laboratoires publiques (FT, Paris 3, LIMSI,
NetValue)
Page 4
13/12/044 Un 2me exemple Rpondre une question prcise : A partir
de textes lectroniques mais de plus en plus partir du Web Encore au
stade de recherche (ex : systme question- rponse dvelopp cette anne
au LIMSI) Comptitions internationales sur extraction dinformations
: Text Retrieval Conference, mlant laboratoires et industries et
Cross-Language Evaluation Forum http://trec.nist.gov, en 2003, 25
comptiteurs (mondial) http://clef.isti.cnr.it/, en 2004, 18
comptiteurs (europen)/
Page 5
13/12/045 Une question de TREC(2003) Qid 2322: Who is Absalom?
2322 1vitalSon of biblical David 2322 2vitalTraitor to his father
2322 3okayName in title of Faulkner novel Number: 2322 Type:
definition Description: Who is Absalom?
Page 6
13/12/046 Un 3me exemple : rsumeur de textes Copernic
summarizer, (algorithmes statistiques et linguistiques),
tlchargeable en anglais, franais et allemand (30 jours)
http://www.copernic.comhttp://www.copernic.com Pertinence
Summarizer (techniques linguistiques), multilingue
http://www.pertinence.nethttp://www.pertinence.net Rsum dun
document
Page 7
13/12/047 Datation Domaine de recherche rcent, prolongement de
travaux en Recherche documentaire par mots-cls Reprsentation des
connaissances en Intelligence Artificielle Adaptation pour grer de
grandes masses de donnes facilement accessibles
Page 8
13/12/048 Fouille de donnes dans les textes / Recherche dans
Bases de Donnes Donnes non ou peu structures, par opposition aux
bases de donnes o les donnes sont structures et stockes dans des
tables avec des champs particuliers Recherche de connaissances
implicites et non explicites
Page 9
13/12/049 Domaines de connaissances Statistiques Analyse des
donnes Apprentissage, infrence Intelligence artificielle Traitement
automatique de la langue
Page 10
13/12/0410 Plan gnral (I) 1er cours : Analyse robuste des
textes Quels textes? Quels constituants du texte (traits) utiliser
pour extraire des informations des textes (prsence, frquence) ?
Quelles mthodes pour fouiller? Reprsentation des textes 2me cours :
Description dun systme de question-rponse
Page 11
13/12/0411 Plan gnral (II) 3me cours : Classification
automatique non supervise de textes Classification hirarchique
Partition de documents en k classes 4me cours : Classifieur SVM
(Support Vector Machine) Apprentissage d'une frontire entre
documents partags initialement en 2 classes (recherche des vecteurs
support) Classification de documents non tiquets de part et d'autre
de cette frontire
Page 12
13/12/0412 Plan 1er cours Quels textes? Du document au texte
Pr-traitements Quels traits (ou lments) du texte utiliser?
Caractres, mots, liens, balises, Enrichissement (synonymes) Quelles
mthodes pour fouiller? Mthodes dAnalyse des donnes (Statistiques,
Logique) Moteurs de recherche Reprsentation des textes,
distances
Page 13
13/12/04Quels textes?13 Quels textes? Documents structurs ou
non Texte brut : Extrait du journal Le Monde, dcembre 1996
Transcriptions d'oral Pages WEB (HTML), images et textes Textes
structurs (XML) Prtraitements des textes
Page 14
13/12/04Quels textes?14 Documents structurs ou non Textes bruts
Journaux Pages WEB, accs par moteur de recherche Livres
lectroniques Revues scientifiques en ligne Transcriptions d'oral
Textes structurs TEI, Text Encoding Initiative, production de
textes baliss, ( http://www.tei-c.org ) : SGML,XML, prsentation
hirarchise de documents RDF, Resource Description Framework,
(http://www.w3.org/RDF) : Web smantique
Page 15
13/12/04Quels textes?15 Texte brut : Extrait du journal Le
Monde, dcembre 1996 {\rtf1\ansi \deff0\plain Document soumis aux
dispositions du droit d'auteur. Tous droits r\'E9serv\'E9s. \par
------------ \par \b\fs34 Le Monde\b0\fs24 \par \par 31 d\'E9cembre
1996, page 1\par \par \par HORIZONS - ANALYSES ET DEBATS\par
\b\fs34 L'Allemagne se sent plut\'F4t bien\b0\fs24 \par \par \b
DELATTRE LUCAS\b0 \par \par C'\'C9TAIT, il y a peu, \'E0 Bonn.
Vendredi, 15 h 30. Helmut Kohl, seul, quitte son bureau et traverse
tranquillement le parc de la chancellerie. Sa semaine de travail
est termin\'E9e. Le chancelier allemand se rend dans sa villa
priv\'E9e, au fond du jardin, ce que l'on appelle ici le
"bungalow". L\'E0, quelques lectures d'agr\'E9ment l'attendent un
roman historique ou une biographie, sans doute. \par \par
Surprenante image.
Page 16
13/12/04Quels textes?16 Transcription d'oral, un dialogue sur
une hot-line oui euh c' est encore moi Madame Morichon oui bonjour
c' est vous que j' ai eu tout l' heure oui oui c' est moi oui bon
bah alors figurez -vous que je suis coine parce que l je suis
toujours sur mes mails en train de les regarder de les supprimer
oui et puis il vient de s' ouvrir une petite fentre euh dont le
titre c' est modem modem on hold tat de l' appel reprise de la
communication rpond de la connection modem rpondre ou ignorer alors
euh j' ai beau cliquer sur rpondre ou sur ignorer ou sur la petite
croix pour fermer rien ne marche d' accord donc vous ne pouvez pas
vous dbarrasser de ce message -l non et euh si vous faites control
alt euh et a veut dire quoi d' abord ce truc -l control c' est les
touches sur votre clavier
Page 17
13/12/04Quels textes?17 Quelques pages WEB Foire aux questions
(FAQ) sur traducteur de google Prsentation du LIMSI Discours sur le
site de la CNIL (Commission Nationale Informatique et Libert)
Page 18
13/12/04Quels textes?18 Textes lectroniques Exemple Le petit
Prince CHAPITRE II J'ai ainsi vcu seul, sans personne avec qui
parler vritablement, jusqu' une panne dans le dsert du Sahara, il y
a six ans. Quelque chose s'tait cass dans mon moteur, Et comme je
n'avais avec moi ni mchanicien, ni passagers, je me prparai essayer
de russir, tout seul, une rparation difficile. C'tait pour moi une
question de vie ou de mort. J'avais peine de l'eau boire pour huit
jours. Le premier soir je me suis donc endormi sur le sable mille
milles de toute terre habite. J'tais bien plus isol qu'un naufrag
sur un rideau au milieu de l'ocan. Alors vous imaginez ma surprise,
au lev du jour, quand une drle de petite voix m'a rveill. Elle
disait: -S'il vous plat... dessine-moi un mouton! -Hein!
-Dessine-moi un mouton...
Page 19
13/12/04Quels textes?19 Revues scientifiques en ligne
http://www.atala.org/tal
Page 20
13/12/04Quels textes?20
Page 21
13/12/04Quels textes?21 Textes structurs : XML Cafe croissants
*5.95 Caf crme avec deux croissants, beurre et confiture 650 Pain
fromage *5.95 Choix de fromage, pain de seigle, beurre 750 Petit
djeuner anglais *10.95 Oeufs avec bacon, pain et confiture, tranche
de pud-ding maison 750
Page 22
13/12/04Quels textes?22 Pr-traitements des textes Extraire le
texte des documents Enlever images, tableaux, balises Conserver ou
non la casse Tout en majuscule ou en minuscule Diffrenciation
majuscules, minuscules Traitement de la ponctuation Lisoler des
mots (virgule) Traitement des chiffres en mots
Page 23
13/12/04Quels traits?23 Que peut on utiliser dans les textes? A
partir du texte original : - Caractres - Mots : vocabulaire,
dictionnaire, stop-list - Ensembles de mots : entits nommes, n-
grammes de mots, co-occurrences, collocations - Balises (XML, liens
hypertextes) Texte enrichi - Etiquettes grammaticales - Concepts,
rseau smantique
Page 24
13/12/04Quels traits?24 Les caractres Identification de la
langue Par frquence de succession de caractres Typage de textes Par
frquence des caractres
Page 25
13/12/04Quels traits?25 Identification de la langue par les
caractres Systme Qu? (http://www.alis.com) tri-grammes de caractres
appris sur de gros corpus, pour chaque langue L identifier pour
chaque triplet de caractres prsents dans ces corpus, on incrmente
trois compteurs : les frquences de trouver ces trois caractres
conscutifs, de trouver les deux derniers caractres ensemble et de
trouver le dernier caractre. 1 modle probabiliste par langue =
{p(L|triplet)} ~100 caractres pour reconnatre une langue
Page 26
13/12/04Quels traits?26 Projection des textes sur les caractres
Fiction Presse Divers Non-Fiction e,t,a,o, ESP RC
Page 27
13/12/04Quels traits?27 Les mots: lesquels? Mots simples, chane
de caractres entre blancs (tokenisation) Mots composs Formes
composes : Y-a-t-il? Mots inflchis ou non (lemmatisation)
Page 28
13/12/04Quels traits?28 Les mots : loi de Zipf Dans les annes
30, un scientifique de l'universit de Harvard, G.K. Zipf, a montr
qu'en classant les mots d'un texte par frquence dcroissante, on
observe que la frquence d'utilisation d'un mot est inversement
proportionnelle son rang, r. Cette loi peut s'exprimer de la manire
suivante : Frquence d'un mot de rang r = (Frquence du mot de rang
1) / r
Page 29
13/12/04Quels traits?29 Loi de Zipf
Page 30
13/12/04Quels traits?30 Loi de Zipf du Petit Prince
Page 31
13/12/04Quels traits?31 Stop-list Mots ts du vocabulaire
Lesquels? Mots trs frquents (statistique), mots-outils
(linguistique : article, coordination, pronom ) En franais sur 2
ans du Monde, les mots les plus frquents sont : de, la, l, le, ,
les, et, des, d, en, un,du, une, Le Petit Prince : le, de, je, il,
et, les, un, la, petit, pas, , prince, ne, Les mots-outils sont-ils
vraiment inutiles? Utiles, pour le typage de textes Utiles, pour la
reconnaissance de la parole Inutiles, en indexation de
documents
Page 32
13/12/04Quels traits?32 n-grammes de mots (I) Succession de n
mots conscutifs Trs utiliss en reconnaissance de la parole partir
des frquences de successions de n mots dans un corpus, on cre un
modle de langage: P(mot| (n-1) mots prcdents) Probabilit de trouver
mot connaissant les n-1 mots qui le prcdent Modle markovien
Page 33
13/12/0433 n-grammes de mots (II) Exemple : Le pre Nol est une
ordure 1-gramme (unigramme) : Le, pre, Nol, est, une, ordure
2-grammes (bigrammes) : Le pre, pre Nol, Nol est, est une, une
ordure 3-grammes (trigrammes) : Le pre Nol, pre Nol est, Nol est
une, est une ordure 4-grammes (quadrigrammes) : Le pre Nol est, pre
Nol est une, Nol est une ordure 5-grammes (pentagrammes) : Le pre
Nol est une, pre Nol est une ordure Probabilit 3-grammes : p(Nol|
Le pre )
Page 34
13/12/04Quels traits?34 Informations de plus haut niveau
Co-occurrences de mots Collocations Entits nommes Classes
grammaticales groupe verbal, groupe nominal, adjectif Rseaux
smantiques Famille : parents, enfants Emotions : colre, joie
Page 35
13/12/04Quels traits?35 Cooccurrences de mots Frquence
dapparition de deux mots dans une fentre Exemple : dans un mme
paragraphe on parlera de sport, de ski, de champion, mots que lon
pourra associer dans un rseau, si on les retrouve frquemment dans
un corpus de textes Intrt : enrichissement des connaissances,
cration de rseaux smantiques (exemple : matrice des frquences)
Page 36
13/12/04Quels traits?36 Collocations Cas particulier des
co-occurrences Mots qui, lorsquils apparaissent ensemble, ont un
nouveau sens par rapport aux sens initial des mots qui le composent
Exemple : pomme de terre
Page 37
13/12/04Quels traits?37 Entits nommes Lieux : la gare Saint
Michel Noms de personnes : la prsidente de luniversit Paris XI,
Anita Bersellini Dates : 13 dcembre 2004 Chiffres : 3000
Page 38
13/12/04Quels traits?38 Classes grammaticales Analyseurs
syntaxiques base de rgles, ventuellement quelques informations
statistiques (commerciaux et acadmiques) Analyse fine, ne peut pas
analyser toutes les phrases (relles~ventuellement mal formes)
Analyse robuste (partielle, moins de dtail, analyse des
questions)
Page 39
13/12/04Quels traits?39 Rseaux smantiques WordNet :
http://www.cogsciprincetonedu/~wnhttp://www.cogsciprincetonedu/~wn
base de donnes lexicales pour lAnglais Synonymes Ontologies
Description simplifie des connaissances du domaine (coteux
faire)
Page 40
13/12/04Mthodes et outils40 Fouille dans les textes Mthodes
Statistiques Logique Visualisation Moteurs de recherche Approche
sac de traits Slection de traits caractristiques
Page 41
13/12/04Mthodes et outils41 Quelles mthodes? Statistiques
Modles vectoriels : 1 texte = 1vecteur Comptages sur des corpus,
mthode adapte des donnes abondantes Frquence des caractres, des
mots, des cooccurrences de mots, des successions de mots
(n-grammes) (Prsence/absence des caractres, des mots, des
cooccurrences de mots, des successions de mots (n-grammes) pour des
donnes moins frquentes) ACP (Analyse en composantes principales)
des donnes pour extraire traits dominants - Latent Semantic
Indexing/Latent Semantic Analysis (voir cours M.Roche)
Classification automatique Documents, Paragraphes,Traits
Page 42
13/12/04Mthodes et outils42 Quelles mthodes? Logique Traitement
du langage naturel Analyse syntaxique (analyseur de Brill)
Grammaire partielle Reprsentation des connaissances (Intelligence
Artificielle) pour des donnes rduites pour des tches partielles, de
haut niveau
Page 43
13/12/04Mthodes et outils43 Visualisation Squentielle 3D-XV
Projection Dun espace N dimensions 2 ou 3 dimensions (plan ou
volume) Quelques images : http://nd.loopback.org/hyperd/
Page 44
13/12/04Mthodes et outils44 Outils commerciaux : moteurs de
recherche sur le WEB Moteurs de recherche Indexation (stat) qq
mots-cls Classification (manuelle) Logique (et ou ) Exemples :
Classes de google Classes de yahoo
Page 45
13/12/04Mthodes et outils45 Slection de traits caractristiques
Trop de traits, complexit Mesure de complexit : Entropie, poids du
trait et distribution dans les textes Tf-Idf (Recherche
dinformation) Recherche des traits dominants par Analyse en
composantes principales Par Regroupement de traits en classes de
traits pour simplifier la reprsentation
Page 46
13/12/04Reprsentation vectorielle des documents 46
Reprsentation vectorielle des documents I Choix : Un document = un
texte = une suite de mots (ou de caractres, ou dtiquettes
grammaticales ) Un vecteur = une suite de chiffres : V2= {16, 39,
13, 7, 3, 70, 2, 13, 1, 2, 5, 1 }
Page 47
13/12/04Reprsentation vectorielle des documents 47 Illustration
I Reprsentation simplifie dans un espace 2 dimensions = 2 mots! Un
bgue prononce les 3 phrases suivantes : T1 : je je vais T2 : je je
je je vais vais T3 : je vais vais Dans lespace deux dimensions,
correspondant aux frquences des deux mots je et vais , on associe
aux phrases, T1, T2, T3, les vecteurs T1{2,1}, T2{4,2}, T3
{1,2}
Page 48
13/12/04Reprsentation vectorielle des documents 48 Illustration
II Roman Le petit Prince , Saint-Exupry Compos de 27 chapitres
Chaque chapitre sera considr comme 1 document Classification
automatique des 27 chapitres
Page 49
13/12/04Reprsentation vectorielle des documents 49
Reprsentation vectorielle des documents II Exemple : chapitre 2 du
Petit Prince ( Jai ainsi vcu seul, sans personne ) On compte les
mots du chapitre (chapitre 2 : 814 mots, 309 mots diffrents) Le
vecteur associ au chapitre 2 est un ensemble de 309 chiffres,
correspondant au nombre de fois o chaque mot est vu V2= {16 39 13 7
3 70 2 13 1 2 5 1 } Mots = -, : ! ?. a absurde ainsi alors ami
Vecteur (309D) pas dessinable sur une feuille (2D)
Page 50
13/12/04Reprsentation vectorielle des documents 50
Reprsentation vectorielle des documents III On a perdu la
squentialit des mots Chaque texte est devenu un sac de mots Les
composantes dun vecteur texte, T j f 1 Tj,f 2 Tj, ,f V Tj frquences
des mots dans le document T j Si le document contient n mots
diffrents (n=n)
Page 51
13/12/04Reprsentation vectorielle des documents 51 Similarit
des documents Les textes qui se ressemblent contiennent les mmes
mots ou des mots qui apparaissent dans les mmes contextes (hypothse
distributionnelle de Harris : les mots qui ont des contextes
identiques sont similaires) Dans lespace vectoriel, ils
correspondent des vecteurs proches.
Page 52
13/12/04Reprsentation vectorielle des documents 52 Chapitres 2
et 7 Intersection = mots communs = 101 Union = 507 mots diffrents
Nombre total de mots Nombre de mots diffrents Mots non communs
Chapitre 2814309208 Chapitre 7884299198
Page 53
13/12/04Reprsentation vectorielle des documents 53 Mots communs
aux chapitres 2 et 7
Page 54
13/12/04Reprsentation vectorielle des documents 54
Reprsentation dans lespace, Projection Dans lespace vectoriel de
dimension V, les vecteurs reprsentant les textes forment un
faisceau dorigine 0 regrouper les vecteurs proches , cest trouver
les vecteurs qui ont des directions quasi-identiques ou dont les
extrmits sont proches
Page 55
13/12/04Reprsentation vectorielle des documents 55 Comparaison
de deux textes Comparaison de 2 vecteurs T1 et T2 sont deux
vecteurs colinaires, ils ont la mme direction et la mme proportion
de je et vais (2/3 de je et 1/3 de vais) T3 et T2 sont deux
vecteurs de directions diffrentes, avec des proportions diffrentes
de je et vais On norme les vecteurs Les vecteurs T1N et T2N sont
similaires, leurs extrmits sont confondues Les extrmits des
vecteurs T1N et T3N sont spares dune distance qui est la longueur
T1N, T3N
Page 56
13/12/0456 Normes des vecteurs Norme habituelle = longueur du
vecteur = norme L2 L2 ={ (f 1 Tj ) 2 + (f 2 Tj ) 2 + + (f V Tj ) 2
} Norme L1 = somme des coordonnes du vecteur, utilise pour obtenir
des probabilits, distributions ou profils L1 = f 1 Tj + f 2 Tj + +
f V Tj Exemple L1 = longueur du document
Page 57
13/12/04Reprsentation vectorielle des documents 57 Comparaison
par similarit ou par distance Similarit entre deux textes mesure
par le cosinus de l'angle form entre les vecteurs associs les
textes T1 et T2 ont des directions similaires : s= cos (T1,T2) = 1
ils contiennent les mmes proportions de mots. Distance entre deux
textes distance sparant les extrmits des vecteurs associs intrt de
normer les textes par leur longueur
Page 58
13/12/04Reprsentation vectorielle des documents 58 Distances
gomtriques entre vecteurs Distances entre vecteurs T j1 et T r2
dans espace multi-dimensionnel Distance euclidienne D(T j,T r ) = i
(f i Tj f i Tr ) 2 Distance de Manhattan (City-block ) D(T j,T r )=
i |f i Tj f i Tr | i varie de 1 V
Page 59
13/12/04Reprsentation vectorielle des documents 59
Reprsentation des distances en 2D D euclidienne (T j,T r ) = (f 1
Tj f 1 Tr ) 2 + (f 2 Tj f 2 Tr ) 2 D Manhattan (T j,T r ) = | f 1
Tj f 1 Tr | + | f 2 Tj f 2 Tr Exemple : f 1 Tj = 1 f 2 Tj = 4 f 1
Tr = 3 f 2 Tr =1 D euclidienne ((1,4),(3,1)) est la ligne droite
entre (1,4) et (3,1) D manhattan ((1,4),(3,1)) = dist1((1,4),(3,1))
est la ligne brise en pointill entre (1,4) et (3,1)
Page 60
13/12/04Reprsentation vectorielle des documents 60 Autre mesure
de similarit Indice de Jaccard Comparaison de 2 vecteurs : on
compte mots communs aux 2 textes, les mots du texte 1, m1, les mots
du texte 2, m2 Indice de ressemblance, s := s= (m1 m2)/(m1+m2- m1
m2) Distance : d=1-s, varie entre 0 et 1 Convient des donnes
binaires
Page 61
13/12/04Reprsentation vectorielle des documents 61 Comparaison
de T1N et T3N Distance euclidienne = ( 2)/3 Distance de Manhattan =
2/3 Indice de Jaccard = s = 1 Avec cet indice, les deux textes sont
semblables, car ils contiennent les mmes mots
Page 62
13/12/04Reprsentation vectorielle des documents 62 Distance de
Kullback-Leibler Traitement de linformation, approche probabiliste,
Utilise vecteurs norms par L1 (proportions ou profils) A partir des
lments du vecteur, on peut calculer la probabilit du vecteur comme
le produit des probabilits davoir ce texte tant donn chaque mot qui
le constitue (approche sac de mots) Cette valeur est un indicateur
discriminant Deux vecteurs peuvent tre compars avec cet indicateur
distance de Kullback-Leibler
Page 63
13/12/04Reprsentation vectorielle des documents 63 Remarques Si
2 textes contiennent les mmes mots, dans les mmes proportions, ils
sont similaires (indpendamment de lordre des mots) Si ils
contiennent les mmes mots dans des proportions diffrentes, ils sont
dissemblables Si ils nont aucun mot en commun, ils sont compltement
dissemblables
Page 64
13/12/04Reprsentation vectorielle des documents 64 Lien entre
similarit et distance 2 mesures de comparaison des vecteurs qui
varient en sens inverse Pour des vecteurs norms : Similarit
(cosinus) S = 1, les documents sont similaires, ils ont les mmes
proportions de mots S = 0, les documents nont aucun mot en commun
Distance D = 0, les documents sont similaires, ils ont les mmes
proportions de mots D = D max, les documents nont aucun mot en
commun
Page 65
13/12/0465 Ouvrage de rfrence Brief Contents 1.Preliminaries
2.Introduction 3.Mathematical Foundations 4.Linguistic Essentials
5.Corpus-Based Work 6.Words 7.Collocations 8.Statistical Inference:
n-gram models over sparse data 9.Word Sense Disambiguation
10.Lexical Acquisition 11.Grammar 12.Markov Models
13.Part-Of-Speech Tagging 14.Probabilistic Context Free Grammars
15.Probabilistic Parsing 16.Applications and Techniques
17.Statistical Alignment and Machine Translation 18.Clustering
19.Topics in Information Retrieval 20.Text Categorization Published
May 1999 by The MIT Press, Cambridge, Massassuchets
Page 66
13/12/0466 Quelques rfrences Livre : Statistique textuelle, L.
Lebart A. Salem, 1994, Dunod Cours
http://www.stanford.edu/class/cs276b/syllabus.html, Manning,
Raghavan et Schtze,
2003http://www.stanford.edu/class/cs276b/syllabus.html Article : A
comparative Study on Feature Selection in Text Categorization ,
Yang et Pedersen, 1997, Proceedings of ICML-97, 14 th International
Conference on Machine Learning