Extraction des règles dassociation à partir dun corpus spécialisé Jérôme AZÉ & Mathieu ROCHE Laboratoire de Recherche en Informatique EGC, Lyon 22-24 janvier

Extraction des règles d’association à partir d’un

corpus spécialisé

Jérôme AZÉ & Mathieu ROCHE

Laboratoire de Recherche

en Informatique

EGC, Lyon 22-24 janvier 2003

EGC, Lyon 22-24 janvier 2003 2

Motivations(1/5)

Extraire des connaissances spécifiques au corpus étudié : règles d’association.

BUT : Permettre à l’expert du domaine de mieux comprendre les interactions entre les différents concepts du corpus étudié.


Motivations(2/5)

4 corpus étudiés :• Corpus de 100 introductions d’articles en anglais

écrits par des auteurs anglophones sur le domaine de la « fouille de données » (369 Ko).

• Corpus de plus de 6000 résumés d’articles en anglais sur la biologie Moléculaire (9424 Ko).

• Corpus en français de plus de 1000 Curiculum Vitae (VediorBis, 2470 Ko)

• Corpus en français relatif aux Ressources Humaines (PerfomanSe, 3784 Ko).


Motivations(3/5)

Extraction paramétrée de la terminologie du domaine Mathieu Roche, EGC2003 - p 295-306

Une nouvelle mesure de qualité pour l’extraction de pépites de connaissances - Jérôme Azé, EGC2003 - p171-182

Classification conceptuelle

Règles d’association

Corpus

Remarque : intervention de l’expert tout au long du processus


Motivations(4/5)

1ère étape : Terminologie et classification conceptuelle

Influenceavis-extérieur

esprit-de-conquête

Expansioncaractère-expansif

personne-aussi-communicative

RelationAction


Motivations(5/5)

2ème étape : Extraction des connaissances

Corpus des Ressources Humaines :

stress environnement

Corpus de la Fouille de données :

NatofInput Output


Plan de l’exposé Motivations Classification conceptuelle• Recherche terminologique• Construction des classes

Extraction des connaissances• Discrétisation• Extraction des règles d’association

Validations Conclusions et perspectives


Construction des classes

- - - - - - - - - - - - - - - - - - - - - - - - - -- - - - - - - - - - - - - - - - - - - - - - - - - -


Corpus brut


Étapes de notre travail(1/3)

- - - - - - - - - - - - - - - - - - - - - - - - - -

1ère étape :Nettoyage

Corpus brut Corpus nettoyé

- - - - - - - - - - - - - - - - - - - - - - - - - -


Le nettoyage Types de nettoyage :

- Enlever les noms, prénoms, coordonnées, etc. (pour les articles et les CVs)

- Uniformiser les référencesCORPUS FOUILLE DE DONNEES :Remplacer ([lettres+année], [numéro], etc.) par « a paper » ou « papers » si ces références sont précédées de la préposition « in », sinon on supprime ces références.

- Généraliser certains noms : CORPUS DE BIOLOGIE MOLECULAIRE Remplacer : carboxyl-terminal carboxyl-termini, C00H-terminal, C02H-terminal, etc. par C-term.



- - - - - - - - - - - - - - - - - - - - - - - - - -



- - - - - - - - - - - - - - - - - - - - - - - - - -

2ème étape :Recherche de termes

Corpus avec termes

- - - - - - - - - - - - - - - - - - - - - - - - - -

Exemple de prise en compte de la terminologie du domaine : Considérer le terme « solution miracle » plutôt que chacun des mots « solution » et « miracle ».



- - - - - - - - - - - - - - - - - - - - - - - - - -


2ème étape :Recherche de termes

3ème étape :Construction

des classesClassification conceptuelle Corpus avec termes


- - - - - - - - - - - - - - - - - - - - - - - - - -

- - - - - - - - - - - - - - - - - - - - - - - - - -


- - - - - - - - - - - - - - - - - - - - - - - - - -- - - - - - - - - - - - - - - - - - - - - - - - - -

Corpus nettoyé

2ème étape

activité professionnelle

tête froide

circuit fermé

intérêt général

Corpus avec prise en compte de la terminologie

- - - - - - - - - - - - - - - - - - - - - - - - - -- - - - - - - - - - - - - - - - - - - - - - - - - -

Liste de termes

Détection de la terminologie(1/5)


- - - - - - - - - - - - - - - - - - - - - - - - - -

Étiqueteurgrammatical

Corpus nettoyé Corpus étiqueté

- - - - - - - - - - - - - - - - - - - - - - - - - -


Mais pour des personnes très spontanées ...

Mais/COO pour/PREP des/DTN:pl personnes/SBC:pl très/ADV spontanées/ADJ...

Étiqueteur de Brill


- - - - - - - - - - - - - - - - - - - - - - - - - -



- - - - - - - - - - - - - - - - - - - - - - - - - -


Améliorations de l’étiqueteur de Brill :

Ajouter :

- des règles lexicales et contextuelles propres au domaine

- ajout d’étiquettes spécifiques au domaine


- - - - - - - - - - - - - - - - - - - - - - - - - -


Extraction des candidats-termes


- - - - - - - - - - - - - - - - - - - - - - - - - -


Candidats termes extraits :

Nom-Nom

Adjectif-Nom

Nom-Adjectif

Nom-Préposition-Nom

Formule-Nom ...

tête froide


circuit fermé

intérêt général


- - - - - - - - - - - - - - - - - - - - - - - - - -


Extraction des candidats-termes

Sélection des “meilleurs” candidats-termes


- - - - - - - - - - - - - - - - - - - - - - - - - -

tête froide


circuit fermé

intérêt général


activité pofessionnelle

tête froide

circuit fermé

intérêt général


Sélection des meilleurscandidats-termes du domaine

(1/2)

Information Mutuelle : calcul du degré d’indépendance entre les deux mots qui composent les candidats-termes (Church, 1990).

P(x)P(y)

x,y)PyxI

(log),( 2


Sélection des meilleurscandidats-termes du domaine

(2/2)

Mesure d’association : isobarycentre des valeurs normalisées de l’information mutuelle et du nombre d’occurrences (Jacquemin, 1997).

Rapport de Vraisemblance (Dunning, 1993).


Évaluation des résultats obtenus(1/3)

Évaluation des résultats

La courbe d’élévation (“lift chart”) donne la précision en fonction de la proportion de termes extraits.

extraits termesde nombre

extraits pertinents termesde nombreprécision


Corpus de la Fouille de Données



Corpus des Ressources Humaines



Paramètres ajoutés pour privilégier les termes du domaine

(1/2)

Élagage progressif

Privilégier les termes qui apparaissent dans des textes différents.

Privilégier les termes déjà reconnus par des auteurs.


Paramètres ajoutés pour privilégier les termes du domaine

(2/2)

A la n-ième itération de la recherche terminologique, privilégier les termes composés des mots issus des termes retenus à la (n-1)-ième itération.


Construction des classes(1/3)

- - - - - - - - - - - - - - - - - - - - - - - - - -- - - - - - - - - - - - - - - - - - - - - - - - - -

Classes

Corpus avec prise en compte de la terminologie

3ème étape

Termes +

Relations syntaxiques

(“Shallow Parser”) +

ROWAN



Pour lutter contre la polysémie, on ne caractérise pas la présence de concepts par la présence de noms, mais par celles de termes ou de relations syntaxiques.



- - - - - - - - - - - - - - - - - - - - - - - - - -

Analyse syntaxique

Relations grammaticales

- - - - - - - - - - - - - - - - - - - - - - - - - -

Ce sentiment n'empêche pas une inquiétude…

SUBJ(3@sentiment 5@empêcher)

DOBJ(5@empêcher 8@inquiétude) …

Analyse de

Shallow Parser

Corpus nettoyéavec terminologie



Extrait d’une classification

0 (tempérament:Nom,démonstratif:Adjectif) expansion0 (promouvoir:Verbe,ambiance:Objet) influence0 (précaution:Nom,excessif:Adjectif) influence0 (rôle:Sujet,dynamiser:Verbe) influence0 (solliciter:Verbe,conseil:Objet) influence0 caractère-expansif expansion0 prétexte-de-progrès influence0 rôle-moteur influence1 expansion RelationAction1 influence RelationAction2 RelationAction ToutesRelations


Prochaine étape : extraction des connaissances


Règles d’association

Corpus


Extraction des connaissances

Classes conceptuelles

0.2 0.45 0.01 0 0 0.054 …

0.015 0.121 0 0.108 … ….….

Représentation fréquentielle du corpus

2 2 1 0 0 1 …

1 2 0 2 … ….….

Représentation discrète du corpus

Concept_1 concept_15Concept_3 concept_8 concept_6…

Règles


Données manipulées

Extrait de la matrice des fréquences d’occurrence des concepts dans le corpus des Ressources Humaines

Influence Implication JugementdeValeur Communication Savoirtexte1 0 0.1 0.2 0.011 0texte2 0.15 0 0.04 0 0.0168texte3 0.00125 0.039 0 0.1 0.18texte4 0 0 0.01 0.048 0texte5 0 0 0.011 0.15 0texte6 0.2 0.2 0 0.0012 0texte7 0.078 0.14 0 0.013 0.0015texte8 0.106 0 0.08 0.1 0


Discrétisation des donnéesPourquoi ?

Règles d’association attributs discrets (booléens)

Données discrètes plus compréhensibles que données continues

• [Freq(influence) < 0.08] [Freq(activité) > 0.03]• [Faible présence influence] [Forte présence activité]


Discrétisation des donnéesComment ?

Problème non supervisé – (peu de méthodes (Liu et al.,journal of DM and KD 2002))

Utilisation d’informations a priori sur les résultats

recherchés (Chickering, ICDM ’01)

• a priori sur la distribution des données (uniforme, binomiale, gaussienne, etc.)

• a priori sur le nombre de valeurs discrètes


Discrétisation : Notre approche

Discrétisation de chaque concept indépendamment les uns des autres

Isoler les valeurs nulles = absence du concept dans les textes

Equi-répartir les valeurs non nulles dans k valeurs discrètes (k fixé par l’expert)– Utilisation d’une interface permettant de contrôler les

différents paramètres (k, concepts à discrétiser)


DiscrétisationUn exemple

0

00

2

2

1

11

k=2


Influence Implication JugementdeValeur Communication Savoir


DiscrétisationUn exemple


Influence Implication JugementdeValeur Communication Savoirtexte1 0 1 2 1 0texte2 2 0 2 0 1texte3 1 1 0 2 1texte4 0 0 1 2 0texte5 0 0 1 2 0texte6 2 2 0 1 0texte7 1 2 0 1 1texte8 1 0 2 2 0


Interface de discrétisation


Interface de discrétisation


Extraction des connaissances

2 2 1 0 0 1 …1 2 0 2 … ….….

Représentation discrète du corpus

activite_2 relationnel_1relationnel_2 activite_1 communication_2…

Règles


Connaissances recherchées

Pépites de connaissances– Règles d’association : AB– Peu contredites par les données– Pas de contrainte sur le support

Connaissances nouvelles pour l’expert


Actuellement

Extraction des règles d’association en deux étapes– Extraction des “Frequent Item Sets” (FIS)

• Contrainte sur le support des FIS (à “la Apriori”)

– Extraction des règles à partir des FIS à l’aide d’une mesure de qualité


Notre approche

Objectifs– pouvoir extraire des pépites de

connaissances dans les données– minimiser l’intervention de l’expert dans le

processus d’extraction– extraire le sous-ensemble de règles les

moins-contredites par les données


Moindre-Contradiction(Azé,Kodratoff, EGC’02)

)(

),(),()(

Bn

BAnBAnBAmc

A

B


Moindre-Contradiction

)(

),(),()(

Bn

BAnBAnBAmc

B

A

B

A


Propriétés

Ni monotone, ni anti-monotone…– pas d’élagage possible du treillis – besoin de nouvelles conditions d’élagage

• règles AB où B est réduit à un concept et A est une conjonction d’au plus K concepts

• ne pas spécialiser les « meilleures » règles • utiliser un seuil d’élagage « contextuel »


Moindre Contradiction

Seuil d’élagage « contextuel »– Soit = { R / mc(R) > 0 } (confiance > 0.5)

– soit E= moyenne () et E=écart-type()

– seuil d’élagage T= E+ E

Élagage des règles– Soit R une règle, si mc(R) > T alors R est présentée

à l’expert mais aucune spécialisation de R ne sera calculée (Sahar, KDD’99)


Exemple

Soit une base de données contenant 6 attributs (A, B, C, D, E et F). Considérons les règles concluant sur F (voir treillis des prémisses).

BCD CDEBDEBCEABC ACD ADEABD ABE ACE

BCDEABCD ACDEABDEABCE

AB BC CD DEBD BEAC AD AE CE

ABCDE

A B C D E


Exemple

Soit = {AB, AC, AD, BC, BE, CD, DE} {R, mc(R) > 0)} et {AD, CD} situées au delà de T = E+ E

AB BC CD* DEBD BEAC AD* AE CE

A B C D E



ABCDE


Exemple

Soit = {AB, AC, AD, BC, BE, CD, DE} {R, mc(R) > 0)} et {AD, CD} situées au delà de T= E+ E




ABCDE

A B C D E


Exemple

Soit = {AB, AC, AD, BC, BE, CD, DE} {R, mc(R) > 0)} et {AD, CD} situées au delà de T= E+ E

BDEBCEABC ABE ACE

ABCE


A B C D E


Validations

Expérimentations sur deux corpus – Introductions d’articles sur la fouille de données– Ressources humaines

Classifications réalisées par des experts

Corpus Notre approche AprioriIntroductions Fouille de données 11 372

Ressources Humaines 27 3027


Quelques règles (Ressources Humaines)

Règles Support Confianceactivité_2 -> relationnel_1 0.32 0.67relationnel_1 -> activité_2 0.32 0.64

environnement_2 -> relationnel_1 0.31 0.65relationnel_1 -> environnement_2 0.31 0.62

activité_1 -> relationnel_2 0.3 0.62relationnel_2 -> activité_1 0.3 0.6

relationnel_2 environnement_1 -> communication_2 0.18 0.65implication_2 -> activité_2 0.25 0.63

activité_gestion&administration_1 -> activité_2 0.12 0.84relationnel_2 activité_1 -> communication_2 0.19 0.64

stress_1 -> environnement_1 0.23 0.63influence_1 -> relationnel_1 0.22 0.64

environnement_1 -> relationnel_2 0.28 0.6environnement_1 -> activité_1 0.28 0.59activité_1 -> environnement_1 0.28 0.59expansion_1 -> relationnel_2 0.18 0.66

influence_2 -> activité_1 0.22 0.62implication_2 -> relationnel_1 0.24 0.61

relationnel_2 -> environnement_1 0.28 0.58influence_1 -> activité_2 0.21 0.61


Conclusions et perspectives

Lien entre TALN et Fouille de Données Rôle important l’expert dans le processus de fouille

de textes

Étude de l’effet du bruit sur le processus global– Amélioration de la partie TALN (Brill, etc)– Utilisation de modèles de bruit pour la fouille de données


Annexes


Mesure d’association(Jacquemin, 1997)

Principe de la mesure utilisée : isobarycentre des valeurs normalisées de l’information

mutuelle et du nombre d’occurrences.

),(min),,(max

),(min),,(max

),(

2

1),(

2

1),(

qpnbm

nbqpnbM

nb

qpIm

IqpIM

I

nbnb

yxnb

II

yxIyxa

mMmM


Rapport de Vraisemblance(Dunning, 1993)

L(Lx,Ly) = a log(a) + b log(b) + c log(c) + d log(d)

- (a+b) log(a+b) - (a+c) log(a+c) - (b+d) log(b+d) - (c+d) log(c+d)

+ N log(N)

Ly Ly' avec y' != yLx a b

Lx' avec x' != x c d

Documents

Extraction des règles dassociation à partir dun corpus spécialisé Jérôme AZÉ & Mathieu ROCHE Laboratoire de Recherche en Informatique EGC, Lyon 22-24 janvier