Télécharger le fichier original (Mémoire de fin d’études)
Compromis entre deux mesures de qualit´e : cou-verture et confiance
Motivation
Soit un jeu de donn´ees compos´e d’objets et partitionn´e en plusieurs classes, chaque objet ´etant d´ecrit par des attributs et un motif correspondant a` une conjonction d’at-tributs. Dans ce contexte, l’objectif du Rule Learning [CN89] est de trouver les rela-tions int´eressantes entre les objets et leurs descriptions. En fouille de donn´ees, on peut citer ainsi plusieurs travaux qui entrent dans ce cadre, comme par exemple, les r`egles d’associations [AMS+96], les motifs fr´equents [HCXY07] ou les motifs clos [BHPW10]. Dans ce chapitre, nous nous int´eressons aux Supervised Descriptive Rules (SDRs) qui d´e-crivent le relation entre les descriptions des objets et une classe du jeu de donn´ees. Des travaux importants ont et´ men´es dans le domaine des SDR a` savoir le subgroup disco-very [Wro97, Atz15], les motifs ´emergents [DL99] et le contrast set mining [BP01]. Un motif ´emergent est d´efini comme une conjonction d’attributs dont le support varie signi-ficativement d’une classe `a une autre. En subgroup discovery, l’objectif est de d´ecouvrir les groupes d’objets dont les descriptions qui varient le plus d’une classe a` une autre. Et en contrast set mining, ce sont les conjonctions d’attributs qui diff`erent significativement d’un groupe a` un autre. Ces travaux ayant tous pour objectif d’extraire les conjonc-tions d’attributs fortement corr´el´ees a` une classe, Novak et al. [NLW09] ont donc d´efini un cadre commun nomm´e supervised descriptive rule discovery. Ce cadre permet d’uni-fier la terminologie, les d´efinitions et les m´ethodes de calcul. Les motifs qui concluent
Compromis entre deux mesures de qualit´e : couverture et confiance
fortement sur une classe pr´esentent un int´erˆet particulier en mati`ere de d´ecouverte de connaissances [CC11, KW10, LPHL+10] ou de pr´ediction [GTC14].
Pour ´evaluer la qualit´e des motifs extraits, plusieurs mesures sont utilis´ees. Une liste tr`es compl`ete de ces mesures est donn´ee dans [HCGdJ11, FGL12]. Francisco Herrera et al [HCGdJ11] ont partitionn´e les mesures en quatre cat´egories comme la complexit´e, la g´en´eralit´e, la pr´ecision et l’int´erˆet. On peut citer plusieurs mesures qui sont largement exploit´ees en fouille de donn´ees comme les mesures de couverture [LKFT04a], de sup-port [LKFT04a], de fr´equence [HCXY07] ou de taux d’´emergence [DL99].
Dans ce travail, nous nous concentrons sur les mesures de support, de taux d’´emer-gence. Nous utilisons la notion de r`egle qui correspond, dans notre cas, a` un conjonc-tion d’attributs (motif) comme pr´emisse et dont la conclusion est une classe. A la sec-tion 2.4.4 du chapitre 2, nous avons montr´e exp´erimentalement que les r`egles (JEPs) avec un support elev´ ne couvrent g´en´eralement pas beaucoup d’objets du jeu donn´ees mais ont une confiance importante. Cette affirmation peut se v´erifier dans la litt´era-ture [KCC15, FR02, TW08].
Apr`es avoir accept´ les r`egles avec un fort pouvoir discriminant et beaucoup support´ees par le jeu de donn´ees, la question qui se pose est : comment pourrait-on int´egrer a` cet ensemble d’autres r`egles afin de couvrir une plus grande partie des objets sans pour autant d´egrader la confiance obtenues sur les r`egles accept´ees. Cela permettrait dans un contexte de classification de trouver une explication pour la pr´ediction de la classe des objets qui n’´etaient pas couverts, et ´eventuellement, d’am´eliorer la pr´ecision du classifieur. Pour r´ealiser cet objectif, nous utilisons une m´ethode des plus proches voisins pour valider les r`egles candidates a` l’int´egration.
Un classifieur k-NN (k plus proches voisins) [CH67] pr´edit la classe d’un objet comme ´etant la classe majoritaire parmi ses k voisins (g´en´eralement la distance euclidienne est utilis´ee pour d´eterminer les voisins). Cependant ces classifieurs posent le probl`eme du nombre de voisins a` consulter qui peut ˆetre tr`es important et ainsi des temps de calcul tr`es longs sans oublier la tol´erance au bruit. La s´election `a base de prototypes [PDP06] a et´ appliqu´ee sur les classifieurs k-NN pour r´esoudre ce probl`eme. Les m´ethodes de s´election `a base de prototypes permettent ainsi de s´electionner un ensemble d’objets, qui sont les plus repr´esentatifs, et qui vont ˆetre utilis´es pour calculer le voisinage d’un objet dont la classe doit ˆetre pr´edite. Pour appliquer la s´election a` base de prototypes sur les classifieurs k-NN, plusieurs m´ethodes ont et´e utilis´ees a` l’image de Kcentres [DJdR+04]. Cette approche construit chaque prototype comme ´etant l’objet central (selon la distance par exemple) de tous les objets ayant le mˆeme voisinage. Pekalska et al. [PPD01] ont aussi montr´e qu’un choix al´eatoire des prototypes pouvait donner de bons r´esultats en classification. Pekalska et al. [PDP06] ont aussi montr´e dans leurs r´esultats exp´rimentaux que la s´election de 3
Un nouveau cadre de s´election de r`egles supervis´ees
a` 10% des objets permet d’avoir de meilleurs r´esultats que le classifieur k − N N sans la s´election. Un ´etat de l’art des diff´erentes m´ethodes de s´election a` base de prototypes est donn´e dans [GDCH12]. Notre approche rentre bien dans ce cadre : nous utilisons des r`egles au lieu d’objets et nous validons les r`egles candidates a` l’int´egration par une m´ethode des plus proches voisins. Pour valider une r`egle, nous calculons ses voisins parmi les r`egles avec un fort pouvoir discriminant et bien support´ees (r`egles prototypes).
Dans ce travail, nous utilisons le support et le taux de croissance pour la s´election des r`egles prototypes. En effet ces deux mesures sont de bons gages de fiabilit´e pour une r`egle [AS94, DL99]. Nous consid´erons ainsi les r`egles les plus support´ees comme ´etant les r`egles prototypes. Et nous s´electionnons parmi les autres r`egles (r`egles candidates) celles qui sont les plus proches (similaires) aux r`egles prototypes. L’ensemble de r`egles ainsi obtenu permet d’obtenir une plus grande couverture que celui des r`egles prototypes avec une confiance assez similaire.
M´ethode de s´election
Principe de la s´election
Supposons que l’on dispose d’un jeu de donn´ees partitionn´e en plusieurs classes, sur lequel on souhaite extraire des r`egles dont la conclusion est une classe. Certaines de ces r`egles apparaissent suffisamment fr´equemment dans le jeu de donn´ees pour que l’on puisse ´evaluer leur pouvoir discriminant. Parmi ces r`egles, les r`egles suffisamment discriminantes sont accept´ees et consid´er´ees comme des r`egles prototypes.
Les autres r`egles (non prototypes) sont consid´er´ees comme les r`egles candidates a` ˆetre valid´ees. Les gages de fiabilit´e d’une r`egle candidate proviennent non seulement de son support et de son taux de croissance mais aussi de sa ressemblance avec les r`egles prototypes. La m´ethode de s´election propos´ee se base sur les r`egles prototypes pour ´evaluer les r`egles candidates : une r`egle candidate est valid´ee si elle est suffisamment similaire aux r`egles prototypes.
La validation d’une r`egle candidate s’appuie sur une m´ethode des plus proches voi-sins [CH67,KGG85,CD07]. Etant donn´ee une mesure de similarit´e, on peut d´eterminer les r`egles prototypes qui sont les plus proches d’une r`egle candidate. Si les plus proches r`egles prototypes concluent g´en´eralement sur la mˆeme classe que la r`egle candidate alors cette r`egle candidate est valid´ee. L’ensemble des r`egles s´electionn´ees correspond `a l’union des r`egles prototypes et des r`egles valid´ees. La m´ethode de s´election repose donc sur l’intui-tion que si une r`egle candidate ressemble fortement `a des r`egles prototypes qui concluent
Table des matières
Liste des tableaux
Table des figures
Introduction g´en´erale
1 Contexte
2 Contributions
3 Organisation du m´emoire
1 ´Etat de l’art
1.1 Extraction de motifs en fouille de donn´ees
1.1.1 Terminologie
1.1.2 Mesures sur les motifs
1.1.3 R`egles d’association
1.2 Espace de recherche
1.3 Repr´esentation condens´ee de motifs
1.4 Motifs ´emergents et ´equivalences
1.5 Evaluation d’un classifieur
1.6 Conclusion
2 Nouvelle m´ethode d’extraction des JEPs minimaux
2.1 Notations et pr´eliminaires
2.1.1 Notations
2.1.2 Correspondance entre les compl´ementaires d’objets et les JEPs minimaux
2.2 AMinJEP : une nouvelle m´ethode de calcul des JEPs minimaux
2.2.1 ToMJEPS (Tree of the minimal JEPs) : un arbre de recherche des JEPs minimaux
2.2.2 Diff´erences entre objets
2.2.3 Essential JEPs et topk JEPs minimaux
2.2.4 Apport de la n´egation d’attribut
2.3 Lien avec les traverses minimales d’hypergraphes
2.4 R´esultats exp´erimentaux
2.4.1 Mat´eriels et m´ethodes
2.4.2 Extraction des JEPs minimaux : analyse des r´esultats exp´erimentaux
2.4.3 Comparaison de AMinJEP avec d’autres m´ethodes d’extraction des JEPs minimaux
2.4.4 Les JEPs minimaux comme r`egles exprimant des corr´elations
2.5 Conclusion
Un nouveau cadre de s´election de r`egles supervis´ees
3.1 Compromis entre deux mesures de qualit´e : couverture et confiance
3.1.1 Motivation
3.1.2 M´ethode de s´election
3.2 R´esultats exp´erimentaux
3.2.1 Mat´eriels et m´ethodes
3.2.2 Analyse des r´esultats exp´erimentaux
3.2.3 Utilisation d’un classifieur `a base de r`egles : CPAR
3.3 S´election de r`egles prototypes en plusieurs passes
3.3.1 Principe de la m´ethode
3.3.2 Mat´eriels et m´ethodes
3.3.3 Analyse des r´esultats exp´erimentaux
3.4 Conclusion
D´etection de la toxicit´e a¨ıgue avec la m´ethode de s´election de r`egles supervis´ees
4.1 Contexte
4.2 Mat´eriels et m´ethodes
4.2.1 Jeu de donn´ees Aquatox
4.2.2 Ensembles de r`egles utilis´es :
4.2.3 Param`etres pour la s´election :
4.2.4 Validation crois´ee :
4.2.5 Variation de couverture et de confiance
4.2.6 Classification avec CPAR
4.3 Application de la m´ethode de s´election des r`egles
4.3.1 ´Evaluation de la couverture et de la confiance des ensembles de r`egles
4.4 Classification avec CPAR
4.4.1 R`egles prototypes
4.4.2 R`egles fr´equentes
4.4.3 R`egles s´electionn´ees
4.4.4 R`egles s´electionn´ees associ´ees aux JEPs de support minimum 3
4.5 Analyse qualitative de la m´ethode de s´election appliqu´ee au jeu de donn´ees Aquatox
4.6 Conclusion
Conclusion et perspectives
Bibliographie
