Upload
gael-maury
View
104
Download
0
Embed Size (px)
Citation preview
09/12/03 séminaire LIR 1
Recherche de structures latentes dans des partitions de " textes " de 2
à k classes
Michèle Jardino
09/12/03 séminaire LIR 2
• Page de présentation rapport d’activité
• BQR 2002
• LREC 2004
• JADT 2004
• PASCAL workshop
09/12/03 séminaire LIR 3
Problème
• Réaliser partition thématique non supervisée cohérente de « textes »– sans connaître a priori le nombre de classes – en faisant émerger une structure hiérarchique
si elle existe
• méthode générique pour tout type de données représentables par des vecteurs
09/12/03 séminaire LIR 4
Etat de l’art (1)
• Méthodes de classification non supervisées – la classification hiérarchique (ascendante ou descendante) – partitionnement direct en un nombre de classes spécifié à
l’avance
• Logiciel libre, R (The R Project for Statistical Computing, http://www.r-project.org/).
• Livres : – Duda R.O. and Hart P.E. (1973). Pattern classification and
Scene Analysis. Wiley & sons.– Kaufman L., Rousseeuw P.J.(1990). Finding groups in
data.Wiley & sons.– Lebart L., Morineau A., Piron M. (1995). Statistique exploratoire
multidimensionnelle. Dunod.
09/12/03 séminaire LIR 5
Etat de l’art (2)Choix du nombre de classes
• Quand?– coupure de l’arbre généré par la classification hiérarchique – pour le partitionnement direct.
• Comment?– généralement résolu soit par des connaissances a priori sur les
données soit par une combinaison de méthodes de classification et d’analyse factorielle (Lebart et al. 1995).
• Inconvénients
– pas prise en compte la structuration réelle des données qui peuvent être éventuellement représentées par un arbre déséquilibré, avec des degrés de ramifications différents, comme par exemple pour les ontologies.
• Alors?
09/12/03 séminaire LIR 6
Classification hiérarchique ascendante
Démographie états USA
09/12/03 séminaire LIR 7
Proposition :• partitions successives de 2 à k classes (dessin)• recherche classes stables d’une partition à une autre =
classes qui conservent les mêmes « textes »• comment?
– d‘abord - visuellement• treillis des relations observées entre classes de textes • analyse visuelle du treillis permet d’extraire, quand elle
existe, une structure particulière sous forme d’arbre, sans connaissance a priori de cette structure, par fusion et élagage. – Ensuite - automatiquement,
• le critère de partitionnement lui-même (Duda and Hart 1973), • le nombre de chemins observés entre les différentes
partitions.
09/12/03 séminaire LIR 8
Méthode
• Partitions successives des textes, de 2 à K classes
• Observation des textes dans ces partitions– Création du treillis des chemins des textes– Recherche de classes stables dans ce treillis
09/12/03 séminaire LIR 9
Corpus d’ étude
• 1 100 fiches de descriptions de sites, de circuits ou de séjours touristiques
09/12/03 séminaire LIR 10
Exemple de fiche (début)
• <Product>• <aeroport>LYS</aeroport>• <Arrivee>CIRCUIT 8 JOURS / 7 NUITS</Arrivee>• <AssuranceA>[[nil]]</AssuranceA>• <AssuranceB>[[nil]]</AssuranceB>• <Budget>2</Budget>• <Circuit>1</Circuit>• <cleunique>39893</cleunique>• <codeafreteur>999</codeafreteur>• <Complet>N</Complet>• <Continent>EUROPE-RUSSIE</Continent>• <Croisiere>0</Croisiere>• <DateDeb>19/06/2000</DateDeb>• <Datesdepart>Done</Datesdepart>• <Desccourt>PRAGUE ET LA BOHEME DU SUD EN PENSION
COMPLETE</Desccourt>
09/12/03 séminaire LIR 11
Exemple de fiche (milieu)
• <Desclong>Lundi : France/Prague@Mardi : Prague/Vysherad et Stare Mesto@Mercredi : Prague/Hrdacany@Jeudi : Prague/Mala strana @Vendredi : Prague/Konopiste/Ceske Budejovice@Samedi : Ceske Budejovice/Trebon/Jindrichuv Hradec/Ceske Budejovice@Dimanche : Ceske Budejovice/Monastère de Vyssi Brod/Cesky Krumlov/Ceske Budejovice@Lundi : Ceske Budejovice/Prague/France.@<BR><B>Nos prix comprennent:</B>@La transport aérien France/Prague/France sur vol charter@Les transferts aéroport/hôtel/aéroport@Le logement en hôtel 3*** normes locales avec petit déjeuner sous forme de buffet@La pension complète du dîner du jour 1 au petit déjeuner du jour 8 avec repas composé de 3 ….
@Le transport terrestre est assuré en autocar Karosa, Daf, Volvo@Les assurances assistance, rapatriement@<B>Nos prix ne comprennent pas:</B>@L'assurance bagages-annulation : 2,5 % du montant total.@Les taxes d'aéroport obligatoires à rajouter au forfait (200 F à ce jour).@Les frais à caractère personnel. @Les pourboires au guide local et au chauffeur.@Supplément single:800 F</Desclong>
09/12/03 séminaire LIR 12
Exemple de fiche (fin)
• <Duration>8</Duration>• <Epuration>19/06/2000</Epuration>• <IDUnique>TCHEACI01808LYS02990</IDUnique>• <JulianDate>36696</JulianDate>• <libopt1>Supplément single</libopt1>• …• <prixsup4>[[nil]]</prixsup4>• <Sejour>0</Sejour>• <Titre>Circuit 8 jours / 7 nuits Prague et la Bohème du sud</Titre>• <Typevoyage>4</Typevoyage>• <URL>http://www.c-online.fr/cgi-bin/cvacances.storefront/FR/
product/V1008_1</URL>• <Valid>V</Valid>• <Validite>19/06/2000</Validite>• <VolSec>0</VolSec>• </Product>
09/12/03 séminaire LIR 13
Phrasettes
• Phrasette = = « chunks » • Pourquoi des phrasettes?
– faciliter la recherche d’information dans ces fiches, par exemple pour répondre à la question « je cherche un séjour avec vue sur lagon »
• Réalisation des phrasettes– découpage descriptions longues en phrasettes – phrasette = segment de texte compris entre deux points ou entre
un début de description et un point
• Corpus obtenu– 4 700 phrasettes différentes, longueur moyenne = 8 mots– nombre total de mots = 120 000, – vocabulaire V = 6 300 mots
09/12/03 séminaire LIR 14
Partitions successives
• Partitionnement par classification non supervisée
• Enchaînement des partitions
09/12/03 séminaire LIR 15
Classification non supervisée
• autour des centres mobiles (Lebart et al. 1995)
• originalité– critère de distance entropique – une recherche aléatoire de la meilleure
classification (Jardino 2000)
09/12/03 séminaire LIR 16
Représentation vectorielle des textes dans l’espace des mots
• Sac de mots– T textes, V mots de vocabulaire – les textes sont indexés par i (i variant de 1 à T) et
notés ti, – les mots par j (j variant de 1 à V) et notés mj.
• Le texte ti est représenté par le vecteur { fij } – les éléments fij sont les fréquences relatives des mots
dans le texte : fij = nij /lj – On obtient ainsi une matrice de T lignes et V
colonnes, chaque ligne correspond au profil d'un texte.
09/12/03 séminaire LIR 17
Représentation des classes Centres mobiles
• Centre mobile d’une classe = barycentre des textes de la classe.
• Profil de la classe de textes fkj. – tient compte ainsi à la fois de la distribution des mots
dans les textes (du profil du texte) et de la longueur de ces textes.
• expression du barycentre :lk*fkj = ∑i inclus dans k li*fij
• lk est la somme des longueurs des textes de la classe k
• et fkj la proportion du mot mj dans la classe de textes k.
09/12/03 séminaire LIR 18
Entropie, critère de classification• Entropie = Quantité d’information contenue dans les textes ~
nombre moyen de mots qui permettent de prédire un texte ( « sac de mots »)
• Entropie des textes non classés :H(T) = -(1/f ) ∑ nij*log(fij)f = nombre total de mots du corpus
• 0 (déterminisme) <= H(T) <= - log(V) (uniformité). • Entropie des textes regroupés en k classes et représentés par leurs
centres de gravité :H(K) = -(1/f ) ∑ nkj*log(fkj)
• On montre que l’entropie des textes regroupés H(K) >= H(T) • Intérêt :
– Temps de calcul : ce critère ne nécessite que de connaître les positions des centres de gravité et non pas leurs positions relatives
– Pas d’hypothèse sur la forme des classes
09/12/03 séminaire LIR 19
Algorithme de classification
• k donné, la classification automatique cherche parmi les environ Tk
configurations possibles, celle qui minimise H(K)• Algorithme itératif qui, à chaque étape, choisit une classification
simplement meilleure que la précédente en cherchant aléatoirement les nouvelles configurations. – Initialisation : à chaque texte est attribuée une classe, de 1 à k, les
centres de gravité des classes sont calculées ainsi que l’entropie H(K) correspondante.
– Itérations : • un texte est choisi au hasard • une nouvelle classe lui est attribuée également au hasard. • Les centres de gravité de la classe initiale et de la nouvelle classe sont
recalculés• la variation d’entropie associée s’en déduit• Si l’entropie décroît, le texte est affecté à la nouvelle classe, si elle croît, le
texte reste dans la classe initiale. – Fin : quand il n’y a plus de variation d’entropie.
09/12/03 séminaire LIR 20
Création de partitions de 2 à k classes
• Partitions successives de 2 à k classes• La première partition est initialisée avec tous les textes
regroupés dans une seule classe, • Les suivantes avec les résultats de classification obtenus
dans la partition précédente : – la partition 3, P3, est initialisée avec le classement obtenu lors
de la partition P2. Les dénominations P2, P3, …, Pk sont réservées aux partitions optimales en 2, 3,…, k classes.
• Léger biais du fait que les partitions ne sont pas complètement optimales mais elle permet de mettre en évidence facilement les classes stables, car celles-ci conservent leur indice d’une partition à l’autre.
09/12/03 séminaire LIR 21
Partitions de 2 à 10 classes
Nombre de textes, T
4 700 phrasettes
Taille du vocabulaire, V
6 300 mots
Nombre total de mots, f
120 000 mots
Entropie maximale
377 mots
Entropie minimale
25 mots
Entropie H(2) 295 mots
Temps de calcul
2 s
Entropie H(10) 162 mots
Temps de calcul
28 s
09/12/03 séminaire LIR 22
Récapitulatif
• Partitions successives des phrasettes, de 2 à K classes
• Observation des phrasettes dans ces partitions– Création du treillis des chemins des
phrasettes– Recherche de classes stables dans ce treillis
09/12/03 séminaire LIR 23
Chemins les plus fréquentés par les phrasettes dans les partitions de 2 à 10 classes. La suite de 9 chiffres dans la première colonne est la suite des numéros des classes des partitions de 2 à 10 classes, le premier chiffre de la suite varie entre 1 et 2, le deuxième entre 2 et 3 …
chemins nombre de chemins
1 1 1 1 1 1 1 1 1
737
2 2 2 2 2 2 2 2 2
609
1 1 4 4 4 4 4 4 4
536
2 2 2 2 6 6 6 6 6
411
2 3 3 3 3 3 3 3 3
343
2 3 3 5 5 7 7 7 7
264
2 2 2 2 2 2 2 9 9
216
1 3 3 5 5 7 7 7 7
146
1 3 4 5 5 5 5 5 5
136
2 2 2 2 6 6 6 6 9
110
09/12/03 séminaire LIR 24
Analyse des chemins
• Classes reliées par 295 chemins différents alors qu’il y a 10 ! possibilités (soit plus de 3 millions de chemins), chemins privilégiés
• Certaines classes n’apparaissent pas dans les 10 chemins les plus fréquentés : ce sont les classes 8 et 10.
• Aux dix premiers chemins sont associés 3 508 phrasettes, soit 75% du corpus.
09/12/03 séminaire LIR 25
09/12/03 séminaire LIR 26
Arbre extrait
09/12/03 séminaire LIR 27
Critère 1 de stabilité des classes = nombre de chemins observés entre 2 partitions successives
09/12/03 séminaire LIR 28
Critère 1 de stabilité des classes = entropie des classes
09/12/03 séminaire LIR 29
Evaluation classification
– 102 phrasettes classées manuellement dans 4 classes de référence R1,R2,R3,R4
– Comparaison avec les 4 classes trouvées automatiquement A1,A2,A3 et A4
09/12/03 séminaire LIR 30
A1 A2 A3 A4 Fréquences marginale
Erreurs
R1 17 0 1 3 21 4
R2 1 28 0 3 32 4
R3 2 10 16 5 33 17
R4 0 3 0 13 16 3
Fréquences marginale
20 41 17 24 102
Erreurs 3 13 1 11
09/12/03 séminaire LIR 31
Evaluation structure
• Recherche d’information:
Question : « séjour avec vue sur lagon »
– 19 fiches trouvées, fiches structurées– 48 fiches trouvées pour les fiches non
structurées
Piscines à lagon
09/12/03 séminaire LIR 32
Conclusion
• Méthode générale de recherche de structures latentes dans les données, permet de répondre aux problèmes de– La détermination du nombre optimal de classes, pour une
classification à plat– Le choix de la coupure dans une classification hiérarchique
• Reste à automatiser complètement la procédure, 2 choix:– Isoler les classes dès qu’elles paraissent stables, et continuer
les partitionnements en parallèle – S’arrêter à un niveau de partitionnement où toutes les classes
paraissent stables et reconstituer l’arbre jusqu’à la racine
09/12/03 séminaire LIR 33
Questions ouvertes
• Quel genre de structure obtient-on? – En thèmes– En style– …
• Dépend de l’espace de projection– Mots, étiquettes syntaxiques, sémantiques …
• Comment représenter les classes?– Textes proches du centre de gravité– Mots discriminants
09/12/03 séminaire LIR 34
En marge
• Utiliser cette méthode – Pour trouver les mots discriminants des
classes– Ou de manière complémentaire, faire une
stop-liste
09/12/03 séminaire LIR 35
Quelques applications
• Reuters (criminologie)
• Dialogues (transcriptions de mots, sémantique,dialogique)
• Pages Web (SensNet)