Home

Découvertes de motifs pertinents par l - LIRIS

1. Num R gles Fr quence Confiance 1 BC 4 1 00 2 AE BC 2 1 00 3 E B 2 1 00 4 E C 2 1 00 5 E BC 2 1 00 TAB 2 4 Exemple d un ensemble de r gles d association pouvant tre simplifi Toutes ces r gles sont dites exactes car elles ont une confiance de 1 Comme on peut le voir les r gles 3 et 4 peuvent tre directement d duites des r gles 2 et 5 La r gle 5 est appel e r gle min max exacte selon l expression utilis e dans PTB 05 Il s agit de la r gle la plus g n rale par rapport 2 3 et 4 on va donc la conserver D finition 2 16 R gle d association min max La r gle R X Y est une r gle d association min maz ssi il n existe pas de r gle R X Y plus g n rale que R Pour g n rer l ensemble des r gles min max on fait la distinction entre les r gles min max exactes et les r gles min max approximatives de confiance lt 1 D finition 2 17 Base min max exactes Soit Ferm l ensemble des itemsets fer m s fr quents et Librex l ensemble des libres de la m me classe d quivalence que X Alors la basd des r gles min max exactes est exactement MinMaxExact R Y X Y X FermAY Librex AY X On a vu pr c demment un exemple d extraction d itemsets libres et de leur fer meture sur les donn es de bd En repartant de cet exemple on va g n rer les r gles min max exactes Le r sultat est pr sent dans le tabl
2. tudier les r gles g n r es puis proposer des annotations en utilisant la syntaxe ad quate Dans un premier temps les r gles sont class es selon la mesure d int r t calcul e par rapport au RB On d cide arbitrairement de fixer la contrainte d int r t minimal 0 75 408 r gles satisfont cette contrainte L expert constate imm diatement un probl me avec ces premiers r sultats en effet le lien last action action n a pas t mod lis dans le RB alors qu il s agit d une relation logique entre deux variables En cons quence toutes les r gles faisant intervenir ce lien sont jug es int ressantes C est parfaitement en accord avec le fonc tionnement attendu du RB Comme il s agit d une modification importante l expert d cide d annoter directement cette relation comme tant une relation connue K avec pour consigne de modifier la structure du RB de telle fa on que ces annotations soient prises en compte Num Annotations de l expert R gles impact es 1 last_action swap swap K certain 1 7 9 2 last_action mel mel K certain 8 3 last_action nff nff K certain 10 TAB 4 3 Exemple d annotations collect es la premi re it ration du processus Un examen montre que 1335 r gles ont un int r t proche de z ro Intrpo1 lt 0 1 et peuvent tre limin es car elles repr sentent toutes sans exception une informa 104
3. PT98 PT00 PT06 PTB 05 PuG 02 Rae00 Ren01 RJBA99 Rob96 rul94 RW99 SA96 BIBLIOGRAPHIE Balaji PADMANABHAN et Alexander TUZHILIN A belief driven method for discovering unexpected patterns In Proceedings of the 1998 KDD International Conference on Knowledge Discovery and Data Mining pages 94 100 1998 Balaji PADMANABHAN et Alexander TUZHILIN Small is beautiful discovering the minimal set of unexpected patterns In Proceedings of the 2000 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining pages 54 63 New York NY USA 2000 ACM Press Balaji PADMANABHAN et Alexander TUZHILIN On characterization and discovery of minimal unexpected patterns in rule discovery IEEE Trans Knowl Data Eng 18 2 202 216 2006 Nicolas PASQUIER Rafik TAOUIL Yves BASTIDE Gerd STUMME et Lotfi LAKHAL Generating a condensed representation for association rules Journal of Intelligent Information Systems 24 1 29 60 2005 S POPULAIRE T DenceuX A GUILIKENG P GINESTE et J BLANC Fusion of expert knowledge with data using belief functions a case study in wastewater treatment In Proceedings of the 5th international Conference on Information Fusion 2002 Luc De RAEDT A logical database mining query language In ILP 00 Proceedings of the 10th International Conference on Inductive Logic Programming pages 78 92 London UK 20
4. le deuxi me concerne l estimation d un v nement conditionnellement un grand nombre de variables le troisi me probl me consiste tre capable d int grer diff rentes sources d in formations multiples en prenant en compte la fiabilit de diff rents experts et de diff rentes sources De nombreux travaux existent sur l licitation de probabilit s Ren01 La t che la plus difficile est de trouver un expert la fois fiable disponible puis de le familiariser la notion de probabilit Ensuite il faut tenir compte des biais ventuels par exemple un expert peut surestimer la probabilit de r ussite d un projet le concernant etc La deuxi me tape consiste fournir l expert des outils associant des notions qualitatives et quantitatives pour qu il puisse associer une probabilit aux diff rents v nements L outil le plus connu et le plus facile mettre en place est l chelle de probabilit pr sent e dans la figure 2 6 Cet outil t introduit par et il permet aux experts d utiliser des informations la fois textuelles et num riques pour assigner un degr de r alisation telle ou telle affirmation puis de comparer les probabilit s des v nements pour les modifier pr sente une tude d taill e des techniques d licitation de probabilit s Le deuxi me probl me concerne le cas o un expert doit estimer la probabilit conditionnelle p Y X1 X2 Xn Pour simpl
5. Enfin nous avons demand l expert de mod liser les d pendances du domaine qui lui paraissaient importantes Plus pr cis ment nous nous sommes concentr s sur la d finition d une premi re structure du RB par l expert Cependant il est relativement d licat d interpr ter la structure seule du RB de ce fait nous avons donn pour consigne l expert d tablir un lien de causalit entre deux variables A et B lorsqu il pensait que la connaissance de la valeur prise par apportait une connaissance suppl mentaire sur les valeurs que pouvait prendre B 4 3 EXPERIMENTATIONS REALISEES 101 Le r sultat obtenu est pr sent dans la Figure On part du principe que ce premi re mod le capture certaines d pendances du domaine d application d autres restent pr ciser ou d couvrir gr ce notre approche Ata2d_type FIG 4 3 R seau bay sien initial RB01 sur les donn es IO partir de cette structure et des donn es d IO nous effectuons un apprentissage automatique des tables de probabilit s conditionnelles gr ce l algorithme d appren tissage implant dans l API Weka WF05 4 3 2 G n ration d un ensemble concis de r gles d association Pour calculer une collection de r gles d association non redondantes nous utilisons Ac LIKE une impl mentation de l algorithme AC MINER BBR00 Les param tres utilis s sont Freq 100 et 6 20 Sur notre jeu de
6. diteur Proceedings of the twenty second Annual International Conference Knowledge Based Systems and Applied Artificial Intelligence ES 02 pages 33 46 December 2002 P CHAPMAN J CLINTON R KERBER T KHABAZA T REINARTZ C SHEARER et R WIRTH Crisp dm 1 0 step by step data mining guide CRISP DM Consortium 2000 Robert G COWELL A Philip DAWID Steffen L LAURITZEN et Da vid J SPIEGELHALTER Probabilistic Networks and Expert Systems Springer 2003 Jie CHENG Russell GREINER Jonathan KELLY David BELL et Weiru Liu Learning bayesian networks from data An information theory based approach Artificial Intelligence 137 309 347 2002 124 CHM04 Chr75 C0088 DD00 Dec99 DG00 DL99 DLR77 DP01 FDBM06 FDMB06a FDMBO06b FL04 BIBLIOGRAPHIE David Maxwell CHICKERING David HECKERMAN et Christopher MEEK Large sample learning of bayesian networks is np hard Journal of Machine Learning Research 5 1287 1330 2004 Nicos CHRISTOFIDES Graph theory An algorithmic approach com puter science and applied mathematics 1975 G F COOPER Probabilistic inference using belief networks is np hard Rapport technique Knowledge Systems Laboratory 1988 Marek J DRUZDZEL et F DIEZ Criteria for combining knowledge from different sources in probabilistic networks 2000 Rina DECHTER Bucket elimination A unifying framework for reaso ning
7. e A D E Tous les chemins de A E passent par D Le chemin A B D E est en s rie en D B D gt E Le chemin A C D E est divergent en D C D gt E Fic 2 5 Exemple de graphe orient On notera que la d finition de la d s paration pr sent e ci dessus peut tre tendue facilement dans le cas o Z est un ensemble de n uds Cette notion purement graphique est cependant difficile appr hender telle quelle Ainsi on pourra la formuler de la fa on suivante le fait que X et Y sont d s par s par Z signifie que Z bloque le passage de l information entre X et Y dans le cas o Z est la seule information connue dans le graphe partir de cette propri t Verma et Pearl ont d montr le deuxi me r sultat important des RB si X et Y sont d s par s par Z alors X et Y sont ind pendants sachant Z Ce r sultat est fondamental il d termine en fait la propri t suivante XIZIY gt p XIY Z p X Z Ce r sultat permet de limiter les calculs de probabilit s gr ce des propri t s du graphe Ainsi supposons que X et Y soient d s par s par Z et que Z soit connu Supposons par ailleurs que l on vienne de calculer p X Z Si une nouvelle information sur Y est alors connue le r sultat ci dessus permet de conserver le calcul de p X Z et de le r utiliser comme valeur de p X Z Y Combin avec un autre r sultat qui tablit qu un n ud est d s par du reste du graphe par
8. Cl ment FAURE Sylvie DELPRAT Alain MILLE et Jean Fran ois BOU LICAUT Utilisation des r seaux bay siens dans le cadre de l extraction de r gles d association In EGC pages 569 580 2006 Olivier FRANCOIS et Philippe LERAY Etude comparative d algo rithmes d apprentissage de structure dans les r seaux bay siens Journal lectronique d intelligence artificielle 5 39 1 19 2004 BIBLIOGRAPHIE 125 FMMT96 FP 96 FP97 FPSM92 GCB 04 GRS96 GZ03 HC99 HCCO2 Hec95 Hec97 HF95 Takeshi FUKUDA Yasuhido MORIMOTO Shinichi MORISHITA et Ta keshi TOKUYAMA Mining optimized association rules for nume ric attributes In PODS 96 Proceedings of the fifteenth ACM SIGACT SIGMOD SIGART symposium on Principles of database systems pages 182 191 New York NY USA 1996 ACM Press Tom FAWCETT et Foster PROVOST Combining data mining and machine learning for effective user profiling In SIMOUDIS HAN et FAYYAD diteurs Proceedings on the Second International Conference on Knowledge Discovery and Data Mining pages 8 13 Menlo Park CA 1996 AAAT Press Tom FAWCETT et Foster J PROVOST Adaptive fraud detection Data Mining and Knowledge Discovery 1 3 291 316 1997 W J FRAWLEY G PIATETSKY SHAPIRO et C J MATHEUS Know ledge discovery in databases an overview Ai Magazine 13 57 70 1992 R gis GRAS Rapha l COUTURIER Maurice BERNADET Julien BLAN C
9. application des interruptions op rationnelles Un mod le est construit partir du retour d exp rience et de l expertise du domaine Ce mod le permet de simuler le comportement g n ral du syst me Des motifs sont quant eux un moyen de repr senter des conditions inhabituelles qui entra nent des interruptions op rationnelles Il est important de bien insister sur le fait que les approches base de mod les ou base de motifs ne sont pas en contradiction ni en comp tition On se rend compte ici de l importance de disposer de ces deux approches cela nous permet de nous poser les questions auxquelles on va r pondre dans ces travaux de th se est il possible d utiliser le mod le pour faciliter la d couverte de motifs Et r ciproquement la d couverte de motifs peut elle contribuer l laboration du mod le Nous avons envisag la collaboration de ces deux approches dans le cadre de la d couverte de r gles d associations pertinentes 1 5 La probl matique de la d couverte de r gles d asso ciation utiles l expert 1 5 1 Choix des r gles d association pour notre cas d application Il ne faut pas perdre de vue les diff rents objectifs que nous nous sommes fix s dans le cadre de ces travaux de th se En particulier une des contributions industrielles 1 5 D COUVERTE DE R GLES D ASSOCIATION UTILES L EXPERT 15 envisag e est de pouvoir faciliter la d couverte de facteurs qui contribuent au
10. est pas li min e de mani re syst matique il n y a pas toujours de r elle am lioration apport e la phase d analyse des r gles Concernant l limination de la redondance vis vis des connaissances du domaine nous avons d crit plusieurs approches qui ont en commun une tape de mod lisation puis d exploitation d un mod le de la connaissance du domaine Nous avons vu no tamment l utilisation de r seaux bay siens pour mesurer l int r t d itemsets fr quents Cette derni re proposition ouvre des perspectives int ressantes sur la collaboration entre r seau bay sien et r gles d association perspectives que nous avons d cid d ap profondir dans ces travaux de th se A notre connaissance il n y a pas encore de r flexion sur la compl mentarit de ces diff rentes approches Il s agit la d un r el manque pour la litt rature sur le domaine qui donne le sentiment que les solutions propos es sont isol es et s occupent d une cat gorie de probl mes bien sp cifiques Nos travaux se sont donc attach s d crire la compl mentarit de diff rentes techniques et outils qu il est n cessaire de mettre en uvre lorsque l on s int resse la d couverte de r gles d association r ellement int ressantes sur des domaines et des donn es relativement complexes Chapitre 3 Le travail de recherche Dans nos travaux de th se nous avons envisag la mise en place d un processus de d co
11. tat de l art Il semble donc crucial d tudier l utilisation de techniques de fouille au sein d une approche englobant part enti re le facteur humain et les connaissances disposition sur le domaine d application Le but tant de faciliter la d couverte de connaissances toujours plus pertinentes sur de grands volumes de donn es Nous avons aussi r alis que ces deux approches pouvaient se montrer compl mentaires une premi re bauche d un mod le de connaissance initie des d couvertes locales sur les donn es qui elles m mes participent l laboration du mod le Nous pensons que cette d marche est tr s prometteuse d autant plus qu elle vise rassem bler deux axes de recherches majeurs l ing nierie de la connaissance et la fouille de donn es Un autre axe de recherche potentiellement int ressant pourrait tre de r fl chir au probl me de la gestion des volutions de notre mod le de connaissance notam 115 ment dans un contexte o ce mod le serait partag entre plusieurs experts Comment garder une trace des modifications effectu es au fil du temps pour signaler ven tuellement des changements de structure contradictoires Comment diff rencier et pr senter sans ambigu t un instant t du processus l ensemble des connaissances implicitement contenues dans le r seau bay sien mod lis es priori int gr es pour le filtrage de motifs ou encore les connaissances no
12. Szymon JAROSZEWICZ et Dan A SIMOVICI Interestingness of frequent itemsets using bayesian networks as background knowledge In Proceedings of the 2004 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining pages 178 186 New York NY USA 2004 ACM Press Szymon JAROSZEWICZ et Tobias SCHEFFER Fast discovery of unex pected patterns in data relative to a bayesian network In Proceedings of the 2005 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining New York NY USA 2005 ACM Press Mika KLEMETTINEN A Knowledge Discovery Methodology for Telecommunication Network Alarm Databases Th se de doctorat Uni versity of Helsinki 1999 Mika KLEMETTINEN Heikki MANNILA Pirjo RONKAINEN Hannu TOIVONEN et A Inkeri VERKAMO Finding interesting rules from large sets of discovered association rules In CIKM 94 Proceedings of the third international conference on Information and knowledge management pages 401 407 New York NY USA 1994 ACM Press P KRAUSE Learning probabilistic networks 1998 R D LAWRENCE G S ALMASI V KOTLYAR M S VIVEROS et S S DURI Personalization of supermarket product recommendations Data Min Knowl Discov 5 1 2 11 32 2001 Bing Liu Wynne Hsu et Yiming MA Pruning and summarizing the discovered associations In KDD 99 Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mi
13. algorithme EM s applique a la recherche des param tres du r seau bay sien en r p tant jusqu convergence les deux tapes Esp rance et Maximisation Il s utilise aussi bien dans le cadre de l estimation statistique que pour l estimation bay sienne De plus de nombreux travaux de recherche ont mis en avant diff rentes heuris tiques pour acc l rer la convergence de l algorithme NH98 Acquisition des connaissances Dans de nombreuses applications r elles on dispose g n ralement de tr s peu de donn es Dans ces situations l apprentissage des param tres du RB passe par l utilisa tion des connaissances d experts pour tenter d estimer les probabilit s conditionnelles 52 CHAPITRE 2 DECOUVERTE DE REGLES PERTINENTES Une premi re difficult souvent appel e licitation de probabilit s dans la litt ra ture et de mani re plus g n rale dans le domaine de l acquisition de connaissances consiste associer une probabilit de r alisation un fait r alisation d une va riable Les difficult s li es cette probl matique rel vent g n ralement de l ing nierie de la connaissance et de nombreuses m thodes ont t propos es au fil des ann es Ci dessous on d taillera trois types de probl mes sp cifiques ainsi que les solutions que l on peut trouver dans la litt rature le premier probl me concerne l estimation de la probabilit d un v nement par un expert
14. autre part permettre l utilisateur de sp cifier ce qui l int resse par le biais de contraintes ou de crit res de recherche Un exemple d algorithme utilisant des contraintes autres que la fr quence minimale est fourni par Srikant et al SA 96 il s agit de Direct Les auteurs proposent d extraire les itemsets fr quents qui satisfont une contrainte syntaxique donn e par l utilisateur Une contrainte syntaxique est par d finition une contrainte qui ne d pend pas des donn es Soit S un itemset la contrainte A S est un exemple de contrainte syntaxique Ces contraintes s tendent naturellement aux r gles d association Cela va permettre l utilisateur de s lectionner les r gles qui sont utiles pour son probl me Il peut par exemple pr ciser qu il est int ress uniquement par les r gles d association dont la t te contient un attribut de classe Les auteurs de Direct introduisent aussi d autres contraintes dans le cas o il existe une taxonomie sur les items Rappelons qu une taxonomie est une relation acyclique qui sert classifier des items en plusieurs cat gories un exemple classique est celui de la grande surface qui classe ses produits en diff rentes cat gories puis sous cat gories 2 5 PRENDRE EN COMPTE LA CONNAISSANCE DU DOMAINE 43 etc L algorithme CAP NLHP98 propose une approche diff rente pour pousser des contraintes anti monotones syntaxiques ainsi que certaines contr
15. cha ne de traitement capable d effectuer ce d coupage et d extraire les mots cl s per tinents De plus nous avons d cid d un commun accord avec l expert d accorder une importance particuli re la derni re action r alis e car elle est bien souvent synonyme d action correctrice par rapport au probl me initialement d tect Exemple Si l on repart du texte pr sent dans la Figure 4 1 on va d tecter qu un probl me est intervenu sur un syst me particulier troubles with entertainment sys tem Ici il ny a pas d informations suppl mentaires par rapport au num ro d ATA qui accompagne le texte Ensuite nous d tectons deux interventions de l quipage une remise z ro de l quipement qui ne permet pas de r soudre le probl me reset nil fiz puis un remplacement de l quipement incrimin EPESC replaced Cela nous permet de remplir le champ actions en mettant les mots cl s reset et replace vrai La derni re action est d tect e comme tant hors contexte puisqu il s agit de la r paration de l quipement en dehors du cycle op rationnel de l avion On assigne 100 CHAPITRE 4 APPLICATION PRATIQUE donc au mot cl last_ action la valeur replace L int r t de cette d marche est vident pour l expert car cela permet de faire intervenir pour chaque enregistrement plus de pr cisions sur interruption op ra tionnelle En effet pour un probl me donn il est vident qu
16. d une part par la d finition d une mesure d int r t permettant le filtrage des r gles d j connues d autre part par l utilisation des propri t s graphiques du r seau bay sien savoir la propri t de d s paration Cette propri t a t tudi e dans le but de faire ressortir partir de l ensemble des r gles pr sent es l expert une d composition des d pendances pr sentes dans les r gles et prises en compte dans le r seau Il est alors possible d identifier les r gles qui paraissent surprenantes car non mod lis es Le but est l aussi de fournir un outil l utilisateur qui doit analyser l ensemble des r gles Nous avons aussi r fl chi aux interactions de l expert vis vis des r gles Pour cela 113 nous avons souhait d velopper une interface sp cifique regroupant diff rentes fonc tionnalit s que nous avons jug es comme tant indispensables au bon d roulement de l tape d tude des r sultats filtrages syntaxiques tris multiples tests d hypoth ses c est dire la possibilit de valider ou d infirmer le caract re pertinent d une r gle Enfin pour m moriser les diff rentes interactions et interpr tations de l expert nous avons labor un syst me d annotations D un c t il permet de collecter un ensemble de sous motifs correspondant aux attributs des r gles tudi es Ces motifs sont cat goris s selon le jugement port par l expert
17. introduit la premi re fois en 1996 MT96 puis de nombreuses propositions ont suivi Le principe des repr sentations condens es est de calculer une repr sentation plus succincte des donn es initiales tout en contr lant dans certains cas la perte d information Ceci permet de r aliser le calcul de la fonction d valuation de mani re plus efficace et ouvre ainsi la porte l extraction de r gles d association sur des jeux de donn es de plus en plus denses et faisant intervenir de nombreux attributs Pour nos travaux de th se nous avons retenu l utilisation de la repr sentation condens e utilisant des itemsets aux propri t s particuli res les itemsets 6 libres et leur fermeture BBR03 Cette repr sentation calcul e gr ce l algorithme AC MINER BBROO permet par la suite de g n rer un ensemble concis de r gles d as sociation dites d fortes 1 5 D COUVERTE DE R GLES D ASSOCIATION UTILES L EXPERT 17 1 5 3 D couverte de connaissances partir de r gles d association Quel que soit l algorithme utilis le nombre de r gles qui vont tre g n r es d pend fortement de la densit de la matrice du nombre d attributs colonnes et du seuil de fr quence minimale Une fois ces param tres d finis on collecte un ensemble de r gles d association Ces r gles doivent ensuite tre analys es par l expert afin qu il puisse s lectionner les r gles qu il jugera pertinentes La princip
18. par tudier les algorithmes d extraction d itemsets fr quents Les propositions actuelles sont performantes m me dans les cas o les donn es sont fortement corr l es et font intervenir de nombreux attributs M me si cet axe de recherche est toujours actif les propositions actuelles s attachent plus l optimisation de leurs algorithmes qu une remise en cause des principes utilis s pour l extraction Vient ensuite le probl me de la g n ration des r gles d association et leur ana lyse par un expert Nous avons vu qu il tait possible de g n rer des ensembles non redondants de r gles Pas00 mais aussi qu on disposait d un ensemble de mesures objectives qui facilitent l tude des r gles En pratique cependant ces me sures ne sont pas toujours suffisantes pour garantir la d couverte de r gles r ellement int ressantes pour l expert du domaine D autres approches ont alors montr qu il tait possible d introduire une part de subjectivit plus importante notamment par la d finition et l exploitation de taxo nomies du domaine SCHO5 ou encore par le biais de contraintes syntaxiques Ces approches constituent un premier pas vers l utilisation de connais sances en int grant le jugement de l expert au processus d extraction de r gles Ce pendant nous sommes convaincus que cette mani re de proc der conna t rapidement des limites Ainsi la redondance par rapport au domaine d application n
19. pour assurer une erreur d approximation de la fr quence r duite Discussion Nous avons pr sent deux repr sentations de r gles d association param tr es par un entier positif 6 Il s agit de bases qui permettent de g n rer un ensemble de r gles d association valides Lorsque 6 0 ces bases sont quivalentes aux r sultats pr sent s par l algorithme CLOSE propos par N Pasquier et al Lorsque gt 0 on constate que les r gles extraites sont plus g n rales le volume de r gles pr sent es Vutilisateur est donc plus r duit En contrepartie la pr cision des r gles obtenues est incertaine d une part la confiance est born e par 6 d autre part pour la collection utilisant les 6 libres la fr quence du corps des r gles que l on peut g n rer est elle aussi incertaine Ces bases sont int ressantes car elles contiennent des r gles ayant un corps mi nimal pour une fr quence donn e et une t te maximale ce sont donc les r gles les plus informatives pour l utilisateur De plus le programme AC Like qui est une impl mentation de l algorithme MIN Ex BBR00 permet d extraire l ensemble des itemsets 0 libres ainsi que leur 6 fermeture Cet algorithme s est r v l tr s efficace en termes de temps d extraction sur les donn es de notre cas d application industriel Il nous effectivement permis de fixer des seuils de fr quence relativement bas tout en conservant une collec
20. t devient vident pour des applications o il est n cessaire d extraire de tr s longs itemsets En effet si dans une application sp cifique il existe un itemset fr quent de taille n un algorithme de parcours niveau par niveau devra d abord consi d rer les 2 sous ensembles de cet itemset avant de pouvoir le trouver En pratique on consid re que ce n est plus praticable quand n est sup rieur 20 Cependant ces algorithmes n ayant pas le m me objectif qu APRIORI ils ne per mettent pas de connaitre la fr quence de tous les itemsets fr quents De ce fait il est impossible de g n rer toutes les r gles d association car on ne connait pas pr cis ment les fr quences de tous les sous itemsets Il est videmment possible de partir des itemsets maximaux pour d river tous les sous ensembles et leur fr quence mais cette strat gie n est pas efficace il a t montr que ce calcul tait au moins aussi co teux que d utiliser l algorithme APRIORI Extraction d itemsets ferm s fr quents libres fr quents D finition 2 9 fermeture ferm La fermeture d un itemset ferm S est le plus grand sur ensemble de S qui a la m me fr quence que S Un itemset S est ferm ou clos s il est gal sa propre fermeture Il d coule de cette d finition qu un itemset ferm est un itemset dont la fr quence est diff rente de tous ses sur ensembles De la m me fa on on d finit ce qu est un itemset
21. ti et d un sous ensemble de Items not t item La figure 2 1 pr sente deux repr sentations quivalentes d une base de donn es bd de sch ma Tia Items Ici l ensemble Items est gal A B C D E et la base comporte un total de 6 transactions Dans le tableau de droite chaque enregistrement est repr sent par l ensemble des attributs observ s Dans la partie gauche ces en registrements sont pr sent s sous une forme binaire un 1 repr sente la pr sence d un attribut un 0 son absence On se r f rera fr quemment ces donn es lors des exemples pr sent s dans ce chapitre Tia tiitem Ta A B C DE 1 A B C D E 1 1 1 1 1 1 2 4 A B C E 2 1 1 1 0 1 3 C 3 0 0 1 0 0 4 B C 4 0 1 1 0 0 5 A B C D 5 1 1 1 1 0 6 A B C 6 1 1 1 0 0 F1G 2 1 Exemple de base de donn es transactionnelles T gauche et repr sen tation binaire associ e droite 2 1 3 Itemsets et r gles d association D finition 2 2 Itemset r gle d association L ensemble S ii i2 i C Items est appel itemset ou k itemset s il contient k l ments Par exemple A B C est un 8 itemset pour simplifier l criture on utilisera galement la notation ABC L ensemble des itemsets est not 2 S Une r gle d association IR est un motif X gt Y o X et Y sont des itemsets sur Items tels que Y Det X NY O X est appel le corps l ant c dent ou la partie gauche de la r gle et Y la
22. 1 ACDE 1 BCDE 1 ABC 2 ABD 2 ABE 2 ACD 3 ACE 1 ADE 1 BCD 2 BCE 1 BDE 1 CDE 1 AB 3 AC 3 AD 3 AE 2 BC 2 BD 2 BE 2 CD 4 CE 2 DE 1 FIG 2 3 Treillis des itemsets Pour r aliser l extraction des itemsets ferm s fr quents diff rents algorithmes ont t propos s En particulier on va diff rencier deux types d approches l approche niveau par niveau PBTL99a BTP 02 et l approche en profondeur d abord PHMOO ZH02 Approche niveau par niveau La notion de classe d quivalence introduite pr c demment nous permet de comprendre facilement les points suivants Tous les sous ensembles d un itemset libre sont libres La propri t de libert associ e un itemset est dite anti monotone Par contre la propri t de fermeture n est ni monotone ni anti monotone on peut d ailleurs s en rendre compte en examinant la figure 2 3 Dans ce cas comment extraire efficacement les itemsets ferm s Heureusement il a t montr que pour extraire les itemsets ferm s fr quents il suffisait d extraire les itemsets libres fr quents et de calculer leur fermeture Les algorithmes CLOSE PBTL98 et PASCAL BTP 02 sont deux exemples de ce type d approche utilisant cette propri t Le parcours du treillis est effectu niveau par niveau mais au lieu de retourner les itemsets fr quents on retourne les itemsets libres 2 3 REDONDANCE DES R GLES FR QUENTES ET VALID
23. 3 LE TRAVAIL DE RECHERCHE Ainsi plut t que d imaginer un r seau bay sien fix a priori nous avons envisag l tude de la construction it rative de ce RB L id e que nous avons d velopp e est la suivante une am lioration du mod le l it ration 4 du processus apportera une aide l expert dans la phase d analyse des r gles l it ration i 1 Les informations pr sent es par les r gles sont alors un peu plus pertinentes c est dire plus en phase avec les intentions de l expert et plus surprenantes par rapport aux connaissances a priori Une annotation structur e de ces informations permet de capturer de nouvelles d pendances et ainsi de continuer am liorer le mod le avant de passer une nouvelle it ration de notre processus l tape i 2 la pertinence des r gles pr sent es est assur e par les modifications apport es au mod le et l utilisation des annotations pr c demment collect es Ainsi notre processus permet les am liorations successives d un mod le des d pendances du domaine Il s agit en quelque sorte de l application d un cercle vertueux pour la production de r gles toujours plus pertinentes gr ce un mod le capturant de mieux en mieux les d pendances du domaine et une collection d annotations toujours plus riches 3 2 Proposition de processus de d couverte de connais sances l approche KARD Notre premi re contribution de recherche est partie du con
24. Artificial Intelligence 113 1 2 41 85 1999 Marek J DRUZDZEL et Linda C Van Der GAAG Building proba bilistic networks where do the numbers come from guest editors introduction IEEE Transactions on Knowledge and Data Engineering 12 4 481 486 2000 Guozhu DONG et Jinyan LI Efficient mining of emerging patterns discovering trends and differences In KDD 99 Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining pages 43 52 New York NY USA 1999 ACM Press Arthur DEMPSTER Nan LAIRD et Donald RUBIN Maximum likeli hood from incomplete data via the em algorithm Journal of the Royal Statistical Society Series B 39 1 1 38 1977 William DUMOUCHEL et Daryl PREGIBON Empirical bayes screening for multi item associations In KDD 01 Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining pages 67 76 New York NY USA 2001 ACM Press Cl ment FAURE Sylvie DELPRAT Jean Fran ois BOULICAUT et Alain MILLE Iterative bayesian network implementation by using annotated association rules In EKAW pages 326 333 2006 Cl ment FAURE Sylvie DELPRAT Alain MILLE et Jean Fran ois BOU LICAUT Utilisation des r seaux bay siens dans le cadre de extraction de r gles d association In Actes de la conf rence EGC 2006 pour 1 Extraction et la Gestion des connaissances 2006
25. Confiance 1 A ABC BC 1 00 2 D ABCDE D ABCE 0 50 3 E ABCDE E ABCD 0 50 TAB 2 6 Ensemble des r gles min max approximatives g n r es partir de bd D finition 2 19 Base min max approximative non transitive MinMazReduc R Y X Y X FermAY Libres ferm Y lt ferm X X lt Y d signe le fait que X est un pr d cesseur imm diat de Y C est a dire qu il n existe pas d itemset Z tel que X D Z D Y 2 4 EXPLOITER LA SUBJECTIVIT 39 2 3 5 Conclusion Comme on le voit la question de la g n ration de r gles non redondantes a t bien tudi e notamment dans le cas de la fermeture d itemsets Il peut cependant tre int ressant d tudier ce qui se passe si l on utilise op rateur de 6 fermeture Pour 6 gal 0 on sait d j que la 6 fermeture se comporte comme la fermeture Intuitivement il para t alors possible de g n raliser la g n ration de r gles min max non redondantes lorsque le param tre devient strictement sup rieur 0 i e consi d rer l ensemble des itemsets 6 libres et leur 6 fermeture comme une repr sentation condens e des itemsets fr quents Une des principales difficult s prendre en compte est que la delta fermeture contrairement la fermeture n est pas idempotente i e ferm X 4 6 ferm 6 ferm X Le chapitre B sera l occasion de revenir plus en d tails sur les propri t s des item sets d libre
26. PartieA Partie B Support Confiance Moindre Contradiction J Mesure Score bay sien Cancer Present TbOrCa True 556 1 000000 0 814056 1 QNAN0 1 000000 Tuberculosis Present TbOrCa True XRay AbNormal 3 119 0 975410 0 173653 0 030815 0 980000 Sonen Cancer Present TbOrCa True XRay AbNormal 9 324 0 972973 0 471557 0 083601 0 980000 Bone ThOrCa True XRay AbNormal 10 376 0 974093 0 037336 0 000035 0 980000 Cancer Present Dyspnea Present ThOrCa True 487 1 000000 0 713031 1 2QNANO 1 000000 Cancer Present Smoking Smoket TbOrCa True 513 1 000000 0 751098 1 QNAN0 1 000000 5 Cancer Present XRay AbNormal TbOrCa True 543 1 000000 0 795022 1 QNAN0 1 000000 Dyspnea Present Tuberculosis Present TbOrCa True XRay AbNormal 3 107 0 972727 0 155689 0 027599 0 980000 Dyspnea Present VisitAsia Visit XRay AbNormal 2 112 0 982456 0 011221 0 000001 0 212704 Bronchitis Present Cancer Present Dyspnea Present TbOrCa True XRay AbNormal 8 283 0 972509 0 411677 0 072973 0 980000 SOn Cancer Present Smoking omoket TbOrCa True XRay AbNormal 9 312 0971963 0 453593 0 080387 0 980000 onene Dyspnes Present ThOrCa True XRay AbNormal 9 329 0 973373 0 032643 0 000038 0 980000 La ponema peN Sman SMOKE ThOrCa True XRay AbNormal 10 343 0971671 0 033969 0 000060 0 980000 Cancer Present Dyspnea Present Smoking Smoker TbOrCa True 450 1 000000 0 658858 1 QNANO 1 000000 Cancer Present Dyspnea Present XRay AbNormal TbhOrCa True 475 1 000000 0 695461 1 QNAN0 1 000000
27. Y ferms X X Y 0 Il s agit donc d un ensemble de r gles d association dont la confiance est a priori born e de la fa on suivante 1 x card Y lt conf R X Y lt 1 maz sy Exemple La table 3 2 montre l ensemble des r gles d association calcul es partir des 1 fermetures de tous les itemsets 2 fr quents Les valeurs de confiance indiqu es entre parenth ses sont compt es sur les donn es En effet comme nous l avons vu la 6 fermeture ne permet de donner qu une approximation born e de la valeur r elle Si on tudie maintenant les r gles pr sent es dans le tableau 3 2 on peut constater que certaines r gles sont redondantes entre elles 3 4 R GLES D ASSOCIATION NON REDONDANTES 77 Num R gle R X Y Freq X Conf R RE 6 approx d gen 1 B C 1 E 5 0 8 oui non 2 C B 1 E 1 5 0 8 oui non 3 E BC 1 5 0 8 oui non 4 BE C 1 5 0 8 non non 5 BC E 4 1 0 oui non 6 CE B 4 1 0 oui non 7 A gt B 1 CE 1 3 0 66 oui oui 8 AC B 1 E 1 3 0 66 non non 9 AB CE 2 1 0 oui non 10 AE BC 2 1 0 oui non 11 ABC E 2 1 0 non non 12 ABE C 2 1 0 non non 13 ACE B 2 1 0 non non TAB 3 2 R gles extraites sur bd pour minfreq 2 et 1 La r gle n 4 peut tre g n r es partir des r gles 1 et 3 Les r gles 7 et 8 sont redondantes entre elles la r gle 7 est cependant plus
28. a Se 1 S PON Y gH Suter np oPessn seoues p dx4 u dde p SIEUU09 elBoye ns s y dxqg 72 CHAPITRE 3 LE TRAVAIL DE RECHERCHE 3 3 Le cas d application Visit Asia Afin de pr senter les techniques et la m thodologie propos es on consid re dans un premier temps un cas d application sur des donn es simul es Ce cas d application va nous permettre dans la suite de ce chapitre d illustrer nos contributions par le biais d exemples concrets En dernier lieu il nous permettra de valider de mani re exp rimentale l ensemble du cycle de d couverte de connaissances propos Pour cela on s int resse au RB de r f rence tel qu il est d fini pour le domaine Visit Asia bien connu de la communaut des r seaux bay siens Cet exemple a initialement t pr sent pour la premi re fois dans LS88 Nous avons d cid de partir de Visit Asia car bien que faisant intervenir un nombre restreint de variables il pr sente des similarit s avec le cas d application sur les donn es d interruptions op rationnelles que nous tudions au chapitre 4 Le contexte associ ce RB est une simulation de l tude de pathologies parti culi res chez un patient ainsi que les causes possibles qui favorisent leur apparition La figure 3 8 ci dessous nous montre le RB qui repr sente le mieux les connaissances relatives ce domaine Il va donc s agir pour nous du RB de r f rence on le d sig
29. aa e ie contient SNS i contient a gt _ M Pre Filtrer Partie de litre Support Filtrer gauche ne contient pas droite ne contient pas ES Partie A PartieB Support Confiance Moindre Contradiction J Mesure Score bay sien Creer une hypoth se Effacer le panel d hypoth ses s Current record 0 lt Previous i 20 rules loaded d FIG A 4 Interface d analyse des r gles d association 119 FE 4 Cr ation d une annotation pee Lx _ Dyspnea Present Tuberculosis Present gt XRay AbNormal Ne Cliquez sur un l ment une ou deux fois pour l ajouter a l annotation Une troisi me fois l enlever tonne Lian FIG A 5 Annotation de r gles d association Bayesian Network tools in Java File Edit View effect CN gt delay_interval 6 0_inf Known la xi 0 7 0 1 0 7 0 1 0 7 0 1 97 9 99 8 Fic A 6 Mise jour du r seau bay sien partir des annotations 120 ANNEXE A PR SENTATION DE L APPLICATION Bibliographie AAO7 AAP00 AAPO AIS93 AKO1 AL99 AMS 96 AS94 D J Newman A ASUNCION UCI machine learning repository 2007 Ramesh C AGARWAL Charu C AGGARWAL et V V V PRASAD Depth first generation of long patterns In Proceedings of the 6th inte
30. base pour chaque niveau du treillis Pour cela l int gralit de la base est mise en m moire et chaque niveau on repr sente les transactions par les k itemsets candidats qu elle contient Ainsi une seule passe est d sormais n cessaire Cependant la sensibilit de cette approche aux jeux de donn es fortement corr l s restent la m me que pour APRIORIet autre inconv nient toute la base doit pouvoir tenir en m moire Avec l algorithme Partition les auteurs ont investigu l utilisation des tid listes interm diaires associ es au treillis de chaque partie tienne en m moire en semble des tid ou identifiant unique d une transaction associ s aux transactions qui contiennent un itemset donn Dans une premi re passe on travaille en largeur et on extrait les tid listes des itemsets du niveau k pour construire les itemsets fr quents 28 CHAPITRE 2 D COUVERTE DE R GLES PERTINENTES de chaque partie par intersection des tid listes du niveau k 1 dans une seconde passe on v rifie pour chaque ensemble localement fr quent qu il est bien globalement fr quent L algorithme Sampling construit quant lui l ensemble des itemsets fr quents ainsi que sa bordure n gative partir d un chantillon repr sentatif de la base Cette m thode permet de limiter le risque de non exhaustivit Les auteurs de proposent avec l algorithme Dynamic Itemset Counting un parcours niveau par niveau modifi Au ni
31. ce qui impose une passe sur la base chaque niveau du treillis 2 Puis pour chaque itemset fr quent X on conserve les seules r gles du type X Y gt Y avec Y D X dont la confiance d passe le seuil minconf On re marque que les r gles ainsi conserv es ont n cessairement une valeur de confiance sup rieure au seuil de fr quence dans la mesure o F A B gt conf A B Ainsi chaque niveau du treillis cet algorithme exploite l anti monotonicit de la contrainte de fr quence minimale pour ne traiter qu une partie de l ensemble des itemsets candidats La fonction de g n ration des candidats d termine quelle partie du treillis va tre explor e en liminant les candidats non fr quents ainsi que tous leurs sur ensembles Si ce type d approche est efficace pour traiter des donn es faiblement corr l es comme les donn es transactionnelles pour lesquelles il tait destin les performances chutent terriblement sur des donn es plus denses et corr l es BMUT97 2 2 EXPLOITER LES MESURES D INTERET OBJECTIVES 27 En effet le principe m me de cet algorithme est d extraire tous les itemsets qui satisfont le seuil de fr quence sp cifi par l utilisateur Ainsi toute la difficult de l extraction des itemsets fr quents consiste identifier le plus efficacement possible la bordure entre les itemsets fr quents et les itemsets non fr quents dans le treillis des itemsets JHGNOO Ainsi on
32. celle ci plus na ve est que dans le second cas il va tre beaucoup plus difficile de d couvrir l association int ressante qui implique l attribut VisitAsia Ceci est d notamment au fait que beaucoup de r gles dont beaucoup sont redondantes sont pr sent es l expert celui ci va devoir parcourir la totalit des r gles avant de d couvrir l association pertinente Dans le prochain chapitre nous abordons un cas d application plus complexe qui justifie les diff rentes techniques et outils mis en place autour de notre processus Chapitre 4 Application l analyse des donn es d interruptions op rationnelles Au chapitre pr c dent nous avons d crit les contributions apport es sur le plan scientifique Des exp rimentations r alis es sur des donn es simul es nous ont permis une premi re validation de ces travaux de recherche Ce chapitre est maintenant l oc casion de voir l application de nos propositions sur une probl matique r elle l aide l analyse des donn es d interruptions op rationnelles dans l a ronautique Apr s un rappel et une pr sentation du cas d application nous d roulerons notre processus de fouille sur le jeu de donn es L analyse des r sultats obtenus nous permettra de conclure sur l efficacit de notre approche 4 1 Description du cas d application Le d veloppement d un projet avion est actuellement bas sur les principes de l ing nierie concouran
33. champs de la base titre d illustration on ne pr sente qu un extrait de la requ te globale Figure 4 2 2 el UPDATE operational_interruption SET effect DY WHERE effect IS NULL AND code_effect LIKE DY UPDATE operational_interruption SET effect CN WHERE effect DY AND delay gt 6 UPDATE operational_interruption SET delay_interval 0 0_0 5 WHERE delay lt 0 5 eae Fic 4 2 Extrait de la requ te SQL pour le pr traitement des donn es Ici ces commandes ont pour effet d affecter une valeur particuli re l attribut effect selon la composition de la variable code_ effect et de discr tiser la variable delay en diff rents intervalles sp cifi s par l expert Le champ de texte libre a quant lui b n fici d un traitement particulier Sec tion 4 2 3 L objectif tant d en retirer le maximum d information sous la forme de nouveaux attributs que l expert souhaite voir appara tre dans les r gles d association 4 2 MISE EN PLACE DU CADRE DE TEST 99 l issue de la phase de pr traitement on dispose de 21 attributs discr tis s au total en 2004 valeurs diff rentes et de 11819 enregistrements La matrice d entr e est donc de taille 2004 colonnes par 11819 lignes La taille moyenne d un enregistrement c est dire le nombre moyen d v nements observ s est de 14 6 Cet ensemble de donn es est jug suffisant par l expert du domaine pour travailler sur l
34. collect es le deuxi me est celui de la d couverte de connaissances partir des donn es Dans ce contexte la mise en place d un processus d extraction de connaissances partir des donn es est potentiellement int ressante L application de ces techniques sur les donn es en service doit permettre la d couverte de nouveaux facteurs qui pourraient tre int gr s aux mod les de pr diction de la fr quence des IO Plus pr cis ment on d finit la d couverte d une connaissance utile comme tant un l ment de connaissance qui une fois pr sent l expert par le biais des techniques de fouille va faciliter la formalisation de nouveaux facteurs d IO Pour ce faire on s oriente vers l utilisation de techniques issues de la fouille de donn es permettant de d couvrir des associations de facteurs relatifs des situations particuli res d IO Cette proposition est pr sent e dans la figure 1 3 Probl matique de la d couverte de r gles d association Enfin le troisi me point concerne la contribution scientifique de ce travail de th se Telle qu elle a t d finie la probl matique industrielle nous porte r fl chir sur des probl mes que l on peut exprimer en des termes plus g n riques Ainsi on va se poser la question de la d couverte de connaissances utiles l expert par l exploitation du retour d exp rience et des connaissances du domaine En particulier on va s int resser l in
35. concern s ou leurs prix de vente Les r gles d association ont t tudi es et employ es dans de nombreux contextes et pour des domaines d applications vari s On peut citer notamment la d tection d intrusion ou d attaques sur un r seau informatique LSMO00 la fouille de grands volumes de donn es textuelles HC99 l analyse de donn es atmosph riques PKS 03 dans le domaine de la g nomique SSO 97 ou encore pour faciliter la d couverte de modules fonctionnels dans des associations de prot ines KHD 05 2 1 2 Repr sentation binaire des donn es Cette section reprend la terminologie utilis e dans le domaine de l analyse de r gles d association et pr sente une d finition formelle de la probl matique d extraction de r gles D finition 2 1 Base de donn es binaire Soit Tia Items le sch ma d une base de donn es binaire Items est un ensemble de n attribut A B C L attribut Dans le cadre d une base de donn es binaire et dans notre contexte on s int resse uniquement la pr sence d un v nement dans les donn es Ainsi pour simplifier la notation on d signera un item uniquement par son attribut sa valeur tant suppos e a 1 2 1 INTRODUCTION LA PROBL MATIQUE 21 T a de type entier est la cl de la relation Une base de donn es binaire qui instancie ce sch ma est un ensemble de lignes ou transactions dont chacune est compos e d un identifiant unique not
36. couverte de connaissances d finition du mod le initial annotation des r gles d association volution du mod le des d pendances 59 60 CHAPITRE 3 LE TRAVAIL DE RECHERCHE du domaine Les paragraphes qui suivent d taillent notre positionnement par rapport l tat de l art Puis dans la suite de ce chapitre nous d veloppons notre travail de recherche pour finir par la validation exp rimentale de nos contributions sur le domaine Visit Asia G n ration d un ensemble concis de r gles d association partir des libres et de la 6 fermeture Cette premi re contribution est inspir e des travaux de recherche de BBRO3 Ils ont tudi les propri t s des repr sentations condens es utilisant les item sets 0 libres fr quents et l op rateur de fermeture On a aussi vu qu il tait possible de g n rer un ensemble concis de r gles d association partir d une repr sentation uti lisant les libres Un autre axe de recherche consid rait quant lui l utilisation de r gles dites 6 fortes corps minimal confiance contr l e dans le cadre de la classification Dans nos travaux nous avons envisag une g n ralisation de ces diff rentes ap proches En effet nous utilisons un algorithme capable d extraire une re pr sentation condens e utilisant les itemsets libres fr quents et la 6 fermeture Si le comportement est connu lorsque 6 est gal z ro il est int ressant d tudier les
37. d autant plus d licate que de nombreuses r gles s av rent inint ressantes et ou redondantes Les mesures dites objectives ne permettent pas par d finition de s affranchir de la redondance li e au domaine d application 2 3 liminer la redondance des r gles fr quentes et va lides 2 3 1 D finition du probl me La g n ration des r gles d association par le biais d un algorithme de type A PRIORI g n re un grand nombre de r gles Une bonne partie de ces r gles sont redondantes Par exemple partir de la base de donn e T il est possible de g n rer les r gles suivantes de fr quence gale 2 et de confiance 1 E C E BC AE gt C et AE BC Ces r gles sont toutes valides mais on voit bien qu il est possible de les regrouper en une seule et unique r gle exprimant la m me information la r gle AE BC De mani re plus g n rale on d finit la redondance de la fa on suivante D finition 2 7 Redondance d une r gle d association Une r gle d association R X Y est redondante s il existe une autre r gle R X Y telle que X C X Y CY et le support et la confiance de R et R sont identiques l chelle d une application r elle un nombre important de r gles g n r es sont 32 CHAPITRE 2 D COUVERTE DE R GLES PERTINENTES redondantes et viennent parasiter la phase d exploration des r sultats rendant d au tant plus difficile la d couv
38. de d s paration suivants et uniquement ceux l 1 A BC D 2 BlACID 3 C AB D Si 1 est vrai et 2 et 3 sont faux alors D sep R A On peut traduire cela par sachant qu on observe B et C A n apporte rien de plus sur la connaissance de C L expert doit alors tudier la r gle R pour savoir si l itemset A pr sente ou non un int r t Par contre si 1 2 et 3 sont vrais alors on a D sep R ABCD On traduira ici Les variables A B et C sont ind pendantes entre elles La aussi le fait de mettre en avant la pr sence d une r gle dont la partie d s par e est non vide va inciter l expert du domaine intervenir pour valider ou infirmer la pertinence de la r gle en question i e par le biais des annotations Puisqu il y a une diff rence entre l association constat e partir de donn es et la mod lisation de cette association dans le RB alors l expert doit d terminer si la r gle d association est fortuite ou si au contraire une d couverte pertinente a t mise en avant Cependant on remarquera que l algorithme que nous proposons donne seulement une approximation de la d composition de la r gle en parties d s par es d pendances principales En effet toutes les combinaisons d itemsets i e les sous ensembles de X et de Y ne sont pas test es pour la d s paration Reprenons l exemple pr c dent si nous avions effectu les calculs de d s par
39. diction de la fr quence des IO Ainsi non seulement il est pris en compte chaque fois qu on souhaite r aliser une estimation des IO mais il a aussi un impact important sur la pr cision de l estimation Dans le cadre de la fouille de donn es on parlera de motifs pertinents pour d signer un motif qui a entra n la d couverte d une connaissance utile pour l expert 1 3 3 D couverte de connaissances utiles partir de donn es L action de d couvrir une connaissance consiste pr senter de mani re explicite ce qui tait implicitement contenu dans les donn es Il y a de nombreuses m thodes envisageables pour r aliser cette t che Dans nos travaux de th se on s int resse plus particuli rement au domaine de l extraction de connaissances partir des donn es on utilisera l acronyme ECD Cette expression a t introduite pour la toute premi re fois dans FPSM92 en tant que processus d extraction non triviale de connais sances implicites non connues l avance et potentiellement int ressantes partir des donn es Par rapport notre probl matique la mise en place d un processus ECD pr sent dans la figure 1 4 pose les objectifs suivants tre capable de formaliser dans une certaine mesure des savoirs sp cifiques au domaine d application de l expert savoirs souvent non formalis s tels les savoir faire et proc dures complexes r sultant de l exp rience fournir p
40. dix premi res r gles 108 CHAPITRE 4 APPLICATION PRATIQUE gt Ata2d_type K gt Effect Airline_zone Station Fault F1G 4 5 R seau bay sien l issue de la deuxi me mise jour RB03 obtenues Cette fois on applique visuellement l impact des annotations K NP et I sur les r gles tableau 4 6 Nous avons choisi ici d utiliser un code typographique sp cifique chaque type d annotation Ainsi les parties de la r gle qui correspondent une annotation seront mises en italique barr es ou soulign es si elles sont respecti vement d j connues non pertinentes ou int ressantes L application d un code visuel aux r gles en fonction des annotations permet l expert de se repr senter plus rapi dement quelles sont les diff rentes informations apport es par les r gles Le r sultat est pr sent dans le tableau 4 7 Cette troisi me it ration nous confirme les r gles qui avaient t jug es int res santes l tape pr c dente De plus comme pour le passage de l it ration n 1 la n 2 cette nouvelle mise jour du RB limine les r gles d j connues 4 4 Critique des r sultats obtenus Nous avons appliqu notre processus de d couverte de connaissances aux donn es d IO dans le domaine a ronautique Le r seau bay sien finalement obtenu est pr sent dans la Figure 1 5 En le comparan
41. donn es le temps d extraction est inf rieur la minute Au total 5633 itemsets 6 libres fr quents ainsi que leur fermeture sont extraits A partir de cet ensemble nous g n rons 4954 r gles 5 fortes Ces r gles ne vont pas tre charg es en totalit dans notre application Afin de faciliter l tape d analyse par l expert celui ci a la possibilit d tablir des filtres syntaxiques de seuiller selon les diff rentes mesures d int r ts calcul es etc 102 CHAPITRE 4 APPLICATION PRATIQUE 4 3 3 Exploitation du r seau bay sien sur les r gles extraites Num R gle d association Confiance Intrgo1 1 last action swap swap 1 00 0 96 2 delay lt 1h last action swap DY swap 1 00 0 96 3 effect DY last action swap swap 1 00 0 96 4 last action swap CS DY swap 0 94 0 92 5 zone E last action swap CS DY swap 0 95 0 92 6 Electro Mechanical last action swap CS DY swap 0 94 0 91 7 delay lt 1h last action swap CS DY swap 1 00 0 95 8 last__action mel OP1 MB zone E DY mel STI 0 99 0 94 9 last action swap CS MB DY swap 0 95 0 92 10 Electro Mechanical last _action nff CS MB DY nff 0 99 0 91 TAB 4 2 R gles ayant la plus forte valeur d int r t vis vis de RBO1 On calcule la mesure d int r t des r gles d association par rapport au RB utilis pour ce premier cycle du processus Pour cela un algorithme Kruskal bas sur la r duction en polyarbres C
42. du processus de d couverte Dans le troisi me chapitre nous avons choisi de positionner nos contributions sur trois axes Tout d abord sur le domaine des collections de r gles d association non redondantes Nous avons tudi les propri t s des ensembles de r gles g n r es a partir des itemsets 6 libres et de la 6 fermeture Cette tude nous a permis d tablir une base pour la g n ration de r gles approximatives i e dont on ne peut d terminer pr cis ment la confiance Le deuxi me axe de contribution concerne notre apport au domaine de l ing nierie de la connaissance en particulier sur l tude des interactions 111 112 CHAPITRE 5 CONCLUSION avec le mod le de connaissance utilis pour faciliter la d couverte de r gles pertinentes construction exploitation volution Nous avons aussi montr l importance du r le de l expert dans ce processus notamment par le biais des annotations sur les r gles d association En effet nous avons appliqu notre approche sur un cas d application concret de l industrie a ronautique l aide l analyse de donn es d interruptions op rationnelles Ce chapitre apporte une confrontation de nos contributions des probl mes concrets de l industrie G n ration d un ensemble non redondant de r gles d association la confiance contr l e Notre premi re contribution consist tudier les propri t s des collections de r gles non red
43. et la moindre contradiction Le temps d ex cution est n gligeable un total de 16 r gles d association sont extraites tape C partir de et de RB_0 on calcule ensuite L R Ta Zro_o D sep qui comporte le r sultat de la mesure d int r t vis vis de RB_ 0 ainsi que l ensemble des parties d s par es des r gles de R Les r sultats obtenus sont r sum s dans le tableau 3 6 Avant de regarder de plus pr s ces r sultats il faut se rappeler que les r gles d associations ne sont g n r es qu partir de la pr sence d un v nement particulier Par exemple la r gle n 18 peut tre lue de la fa on suivante Si l on observe que le patient est fumeur Smoker que l on effectu le diagnostic de la pr sence de dyspn e Dyspnea et d une bronchite Bronchitis ainsi que l activation du n ud sp cifique TbOrCa alors des examens aux rayons X r v lent souvent des r sultats anormaux Num R gle d association conf C min Intrpoi 1 Tuberculosis TbOrCa XRay 0 98 0 17 0 01 2 VisitAsia XRay 0 98 0 01 0 89 3 Bronchitis Cancer TbOrCa XRay 0 97 0 47 0 01 4 Bronchitis TbOrCa XRay 0 97 0 04 0 01 5 Cancer Dyspnea TbOrCa 1 00 0 71 0 00 6 Cancer Smoking TbOrCa 1 00 0 75 0 00 7 Cancer XRay TbOrCa 1 00 0 80 0 00 8 Dyspnea Tuberculosis TbOrCa XRay 0 97 0 16 0 01 9 Dyspnea VisitAsia gt XRay 0 98 0 01 0 86 10 Bronchitis Cancer Dyspnea
44. fr quent alors tous ses fils sont non fr quents Par exemple si la cat gorie Syst mes n est pas fr quente alors tous ses enfants i e Avionique Electro m canique M canique ne seront pas fr quents non plus Le probl me g n ralement pos par ce type d approche est que l on peut rater des r gles au niveau inf rieur La litt rature est assez abondante sur les optimisations a apporter On peut par exemple vouloir r aliser une exploration avec un support d croissant faire l hypoth se d ind pendance entre les niveaux du point de vue de la fr quence utiliser un filtrage sur un item ou sur k items Dans tous les cas de figures il faut bien comprendre qu il y a un surplus de r gles g n r es inutilement d la pr sence de cette hi rarchie En effet certaines r gles peuvent tre redondantes cause des relations de parent entre les cat gories d finies par la taxonomie Prenons les deux r gles d association ci dessous 1 Syst mes vrai Attr2 vrai Attr3 vrailF 0 06 conf 0 7 42 CHAPITRE 2 D COUVERTE DE R GLES PERTINENTES 2 Syst mes vrai Attr2 vrai Electro m canique vrai Attr3 vrailF 0 02 conf 0 72 Dans ce cas on dit que la r gle 1 est un anc tre de la r gle 2 Une r gle est redondante si sa valeur de fr quence est tr s proche du support que l on pourrait pr voir en se basant sur la fr quence de la r gle anc tre Dans notre exemple si le n
45. fr quents et la part importante de redondance entre les r gles ainsi qu au domaine d application Ceci est d autant plus vrai lorsque les donn es sont denses ou fortement corr l es BMUT97 On a vu qu il tait possible de g n rer un ensemble restreint de r gles d association La diminution du volume de r gles repr sente un premier pas pour faciliter l analyse 40 CHAPITRE 2 D COUVERTE DE R GLES PERTINENTES des r sultats De plus de nombreuses mesures objectives ont t propos es dans la litt rature Ces mesures permettent d valuer certains crit res statistiques des r gles d association permettant ainsi une analyse plus fine de chaque r gle Mais pour autant elles ne sont pas toujours suffisantes pour s lectionner les r gles r ellement int ressantes du point de vue de l utilisateur Pour cela il nous appara t n cessaire d introduire des crit res subjectifs dans le processus de d couverte Ils peuvent tre utilis s d s la phase d extraction afin de r duire l espace de recherche Une autre approche qui n est pas indissociable de la premi re consiste effectuer des post traitements sur les r sultats et de s lectionner des r gles plus pertinentes vis vis des crit res sp cifi s par l utilisateur On s int ressera aussi aux mesures d int r t dites subjectives De telles mesures peuvent par exemple tre d finies pour prendre en compte une hi rarchie de concepts tablie sur le d
46. g n rale car son corps est minimal par rapport 8 c est donc celle l qu on souhaite conserver Les r gles 11 12 13 peuvent tre g n r es partir des r gles 9 et 10 Pour liminer la redondance il nous faut donc s lectionner les r gles qui pour une fr quence donn e ont un corps minimal En fait l ensemble des r gles non redondantes de la collection issue de la table est exactement l ensemble des r gles dont le corps est un itemset 2 fr quents libres Ce r sultat se d montre facilement en exploitant les propri t s des itemsets libres qui sont les itemsets minimaux des classes d quivalence Cela nous am ne naturellement la d finition d une premi re base g n ratrice de r gles d association D finition 3 4 Base 6 approximative de r gles d association La base ap prozimative de r gles d association de la fa on suivante 6 approt R X ferms X X X Libre Ainsi dans notre exemple cette base est constitu e par l ensemble des r gles 1 2 3 5 6 7 9 10 dites d approximatives Dans le cas o 6 0 la base calcul e est exactement la base des r gles d association exactes i e de confiance gale 1 on retrouve alors le r sultat pr sent par Pas00 sur la m me base de donn es 78 CHAPITRE 3 LE TRAVAIL DE RECHERCHE Cette base est int ressante car elle offre un bon compromis entre compacit et pr cision d extraction Cependant elle n cessite le calcu
47. gle d association s exprime de la fa on suivante B o est la partie gauche aussi appel e ant c dent pr misse ou corps de la r gle elle repr sente les donn es examin es B est la partie droite de la r gle ou cons quent c est la propri t qui a t d couverte en relation avec la partie gauche de la r gle A et B sont tous deux appel s des itemsets Ils repr sentent un ensemble non vide de couples attribut valeur observ s sur les donn es L exemple classique montre la d couverte de la r gle d association couches bi res partir d une base de donn es constitu e des diff rents paniers achet s dans une grande surface Cette r gle d association nous dit que lorsqu un client ach te des couches il ach te souvent de la bi re Une possible explication de cette d couverte serait que les jeunes hommes en charge d un enfant en bas ge n ont plus assez de temps pour sortir boire de la bi re ils profiteraient donc de l achat d ustensiles pour b b s pour satisfaire leur soif Cette d couverte d crit un comportement totalement inattendu mais pourtant valide dans le sens o cette association s appuie sur un nombre suffisant d enregistrements Elle est de plus potentiellement int ressante en effet le responsable des ventes peut par la suite utiliser cette r gle pour optimiser sa strat gie commerciale par exemple en modifiant la proximit des produits
48. l action C est dire qu elle r unit la fois une information et un mode d emploi permettant d utiliser cette information M Polanyi Pol66 a distingu deux types de connaissances les connaissances ta cites et les connaissances explicites Les connaissances tacites sont les connaissances qui appartiennent au monde des objets et des repr sentations mentales Elles re 10 CHAPITRE 1 CADRE DE TRAVAIL groupent les comp tences inn es ou acquises le savoir faire et l exp rience Elles sont g n ralement difficiles formaliser Dans le cas de connaissances tacites le mode d emploi n cessaire pour utiliser une information est en quelque sorte incorpor chez l homme Par exemple un pilote d avion qui doit prendre la d cision de ne pas partir sous certaines conditions tat du train d atterrissage valve anti gel remplacer m me si les conditions sont jug es acceptables par les quipes de maintenance au sol et donc en accord avec les autorit s de r gulation Dans ce cas de figure c est l exp rience du pilote qui joue celui ci est au courant des faits tat de l appareil feu vert des quipes de maintenance mais son propre mode d emploi lui dicte la conduite suivre Par opposition les connaissances explicites sont les connaissances clairement ar ticul es au niveau d un document crit ou d un syst me informatique Ces connais sances sont transf rables physiquement car elles apparais
49. l ensemble constitu de ses parents de ses enfants et des autres parents de ses enfants cette propri t permet de rendre locaux tous les calculs de probabilit s dans un graphe causal On d finit un RB de la fa on suivante 2 5 PRENDRE EN COMPTE LA CONNAISSANCE DU DOMAINE 49 D finition 2 21 R seau bay sien B G 0 est un r seau bay sien si G X E est un graphe acyclique orient dont les sommets repr sentent un ensemble de variables al atoires X Xj Xn et si 0i P Xi Xpax est la matrice des probabilit s conditionnelles du n ud i connaissant l tat de ses parents Pa X dans G Utilisation et difficult s A partir des propri t s du RB et de la d finition nonc e ci dessus on peut d duire une propri t importante des RB qui est de d finir de mani re unique et condens e la distribution de probabilit jointe de H n RB _ PH En Il Paia i 1 Cette propri t va permettre d effectuer les calculs de probabilit s conditionnelles d v nements reli s les uns aux autres par des relations de cause effet l int rieur du graphe Cette utilisation du RB s appelle l inf rence En termes d utilisation du mod le l avantage essentiel des r seaux bay siens par rapport d autres techniques est de permettre une formalisation assist e par l expert des connaissances du domaine sous forme d une repr sentation graphique lisible N anmoins la construction et l
50. non valide est pr sent e diff remment l expert Il faut donc r fl chir au filtrage de 110 CHAPITRE 4 APPLICATION PRATIQUE ces motifs autrement que par la mesure d int r t Un deuxi me probl me prendre en compte dans des travaux futurs est l tude de l impact potentiel que peut avoir la modification de la structure ou des param tres du RB sur l ensemble des r gles Il s agit en quelque sorte de pouvoir contr ler et mesurer les effets de bord provoqu s par la mise jour du RB Il peut par exemple tre int ressant de pr senter l expert uniquement les r gles qui ont t impact es par la modification du mod le On a aussi vu que les calculs de mesures d int r t effectu s dans ce chapitre pou vaient tre longs lorsqu on travaille sur des jeux de donn es r els relativement com plexes En fait il faut savoir que le temps de calcul est lin aire en fonction de la taille du RB nombre de n uds nombre d arcs du cardinal moyen des itemsets de la partie gauche des r gles et bien s r du nombre total de r gles traiter Avec la mise en place d un syst me de cache appropri il est envisageable de r duire le temps de calcul total de plusieurs ordres de grandeurs N ayant pas de contraintes de temps de calculs sp cifiques pour notre application nous n avons pas cherch creuser cette voie Chapitre 5 Conclusion et perspectives Principales contributions Dans ce m moire nous a
51. phase d tude des r gles permet l expert de commencer d cou vrir des relations d association Cependant avant d annoter un motif comme tant r ellement int ressant I expert doit tre en mesure de v rifier que le motif en question n est pas le fait d une simple coincidence sur les donn es Pour cela il a sa disposition des outils de tests qui vont lui permettre d valuer plus finement le motif en question sur l ensemble des donn es Exemple Prenons la r gle A a B b C c L expert pense que le motif A a C c est potentiellement int ressant Afin de pouvoir confirmer la validit de ce motif il doit valuer le comportement de la r gle lorsque les variables B b et C c ne 106 CHAPITRE 4 APPLICATION PRATIQUE Num R gle d association Intrpoi 1 zone ME delay lt 1h CS MB DY OP2 ST2 0 87 2 801120 80 8011 DY 0 87 3 4900 Engine 49 490000 DY CS 0 85 4 2851 nff Electro Mechanical 28 285134 DY CS 0 83 5 CS ST3 zone ME DY OP3 other 0 82 6 Avionic smoke 26 DY 0 80 7 4900 delay lt 1h Engine 49 490000 DY CS 0 79 8 delay lt 1h OP4 ST4 zone NA DY other 0 79 9 zone ME last _action remove MB DY remove OP2 ST2 0 77 10 2851 delay lt 1h Electro Mechanical 28 285134 DY CS 0 76 TAB 4 5 R gles d association ayant la plus forte valeur d int r t vis vis de RB02 sont pas pr sentes Pour ce faire il tudie l volution des mesures de confiance et de moind
52. pour permettre les modifications du RB Il n y a cependant aucune automatisation dans ce processus une fois les r gles annot es l expert du domaine enregistre les r sultats de son analyse qui sont alors visualis es par l expert en RB Comme on va le voir section la syntaxe des annotations a t pens e pour faciliter leur interpr tation en vue d une int gration au mod le ajout modification ou suppression d arcs ou de n ud du graphe Le cas ch ant il faut red finir les tables de probabilit s impact es par les modifications il alors possible de s appuyer sur les donn es et sur les recommandations de l expert du domaine via les annotations 3 2 2 Le processus KARD d taill La figure 3 7 d crit l enchainement des diff rentes activit s pr c demment d crites et pr sente une vision globale de notre approche pour la d couverte de connaissances Ce sch ma montre la boucle vertueuse que l on a mise en place au fur et mesure des it rations le mod le est de plus en plus complet son utilisation permet de filtrer de plus en plus de motifs non pertinents r duisant ainsi la collection de r gles pr sent e l expert et facilitant par la m me le travail Le postulat pris est que la capacit d couvrir des r gles r ellement pertinentes augmente en m me temps que la proportion de motifs parasites donc perturbateurs diminue dans la collection de r gles tudi es 70 CHAPITRE
53. rents algorithmes qui permettent de les g n rer Extraction d itemsets maximaux fr quents Pour obtenir tous les itemsets qui satisfont une contrainte anti monotone comme la contrainte de fr quence minimale il nous suffit de calculer la fronti re positive de cette collection Les itemsets ainsi trouv s sont appel s itemsets maximauz En effet si un itemset X v rifie une contrainte anti monotone alors tout itemset plus g n ral que X v rifiera galement cette contrainte D finition 2 8 Itemset maximal fr quent Un itemset maximal fr quent est un itemset fr quent dont aucun de ses sur ensembles imm diats n est fr quent Exemple Consid rons le treillis des itemsets pr sent dans la figure 2 2 Pour chaque itemset fr quent situ sur la bordure positive on regarde si tous ses sur ensembles imm diats sont infr quents Au final les seuls itemsets maximaux fr quents de notre exemple sont ABCD et ABCE 2 3 REDONDANCE DES R GLES FR QUENTES ET VALIDES 33 Ce type de repr sentation regroupe donc les techniques qui cherchent calculer directement cette fronti re positive vis vis d une contrainte anti monotone donn e Max clique et Max eclat ZPOL97 Max miner Bay98 Pincer search LK98 Depth Project sont autant d approches diff rentes cherchant arriver le plus vite possible la fronti re positive en n explorant pas de mani re exhaustive les diff rents niveaux du treillis Leur int r
54. rir ou construire un mod le des connaissances On a commenc faire la distinction entre la fouille de donn es orient e mod le et la fouille de donn es pour la d couverte de motifs Cette section pr sente les principales diff rences entre ces deux types d approches et argumente le choix qui a t fait dans 1 4 MOD LES DES CONNAISSANCES 13 3 Interpr tation valuation des motifs mod les 2 Extraction de motifs mod les 1 S lection pr traitement Connaissances Motifs Mod les extraits Donn es pr par es Donn es s s bw wee ee eee bec Senecio ee Fic 1 4 Processus simplifi d Extraction de Connaissances partir des Donn es le cadre des travaux de th se Il faut garder l esprit que ces deux approches bien que distinctes dans leur philosophie ne s excluent pas mutuellement dans la pratique Un mod le tout d abord est une vision haut niveau une description g n rale du jeu de donn es sur lequel on travaille Cette vision peut tre descriptive vue condens e et pratique sur les donn es ou utilis e pour ses capacit s d inf rence c est dire que cette approche donne la possibilit l utilisateur de tirer des conclusions factuelles sur la population issue des donn es Des exemples de mod les couramment employ s sont les mod les de r gression les mod les de m langes gaussiens les r seaux bay siens etc Un motif quant lui d cri
55. s application du filtre la r gle appara t sous la forme B Enfin consid rons les annotations de type NP Les motifs non pertinents ne vont pas par d finition n cessiter une modification de la structure du r seau Par contre on leur associe un code couleur afin que l expert puisse facilement rep rer les motifs qu il a jug comme non pertinents au sein de la collection de r gles 3 7 Validation exp rimentale de l approche KARD sur le domaine Visit Asia 3 7 1 Objectifs de notre d marche exp rimentale L objectif de cette d marche exp rimentale est de montrer qu en partant d un ensemble de donn es d crivant le domaine et d un RB d grad c est dire qu il capture la plupart des principales d pendances du domaine d application mais cer 88 CHAPITRE 3 LE TRAVAIL DE RECHERCHE taines sont manquantes ou erron es il est possible de retrouver le RB qui repr sente le mieux le domaine d application en l occurrence ici il s agit du RB de r f rence que nous avons pr sent dans la figure page 72 Dans la suite de cette section nous raisonnerons comme si RB ref nous tait inconnu les seules traces que nous avons de ce RB sont des donn es g n r es A partir du RB d grad nous tenterons d une part de retrouver quelles modifications ont t apport es la structure et aux param tres du RB mais aussi de d couvrir un ensemble de r gles d association pertinentes sur
56. tables de probabilit s est un probl me d licat et co teux lorsque les variables mani pul es ont un nombre lev de valeurs possibles Or dans un cas d application r el certaines variables peuvent prendre une centaine de valeurs possibles rendant toute modification manuelle de la structure du r seau relative ces variables extr mement co teuse et d licate La solution propos e consiste effectuer un apprentissage automatique des tables de probabilit s conjointes puis soumettre le r sultat obtenu l expert pour vali dation Il pourrait tre int ressant de mesurer quantitativement le temps n cessaire pour effectuer ce type d op rations et r fl chir sur les modalit s d interactions avec l expert qui permettraient de faciliter et d acc l rer cette tape La deuxi me cat gorie d annotations motifs jug s non valides NV est prise en compte ind pendamment du r seau bay sien Chaque motif class comme non valide est ajout une base de r gles dont la construction ne sera pas pr sent e ici Cet ensemble de r gles peut alors servir de filtre pour le post traitement des r gles d assocations Si l expert juge le motif X Y comme tant non valide il peut d cider de masquer ce type d association en appliquant un filtre sur la collection de r gles d association extraites Soit le motif X Y jug non valide par l expert et une r gles d association AX BY contenant ce motif Apr
57. taient un bon support pour mod liser et exploiter les connaissances du domaine dans le but de favoriser la d couverte de motifs divergents par rapport ce mod le Nos travaux se diff rencient de ceux de S Jaroszewicz et al sur plusieurs points L tude des mesures d int r t sur les r gles d association et en particulier sur les r gles g n r es partir d une repr sentation condens e utilisant les 6 libres Les articles pr sent s jusqu pr sent ont choisi de se limiter la d couverte d ensembles d attributs int ressants L exploitation de la structure du RB i e les in d pendances graphiques entre les variables pour la d composition d une r gle d association en sous parties que nous appelerons motifs qui refl tent respectivement ce qui est mod lis par le RB et ce qui ne l est pas Ce point n a pas t abord par les auteurs des propositions sur l utilisation des RB pour la fouille de r gles d association mais nous pensons que l utilisation explicite de la propri t de d s paration peut permettre une d composition plus fine de l information port e par les r gles La d finition et l volution du RB au cours du processus de d couverte de connaissances Sur ce point aussi les articles actuels sont relativement vasifs il a t montr qu il tait possible par ditions successives du RB de converger vers un maximum local de l indice de performance du R
58. tr s en vogue une certaine poque on sait aujourd hui qu il est extr mement difficile de d finir et de g rer une base de connaissance constitu e de r gles logiques Utilisation d un r seau bay sien pour mesurer le caract re inattendu d un itemset fr quent Cette approche a t propos e pour la premi re fois dans JS04 Les auteurs partent du constat suivant le post traitement des r gles d association est bas prin cipalement sur l utilisation de mesures dites objectives Comme pr cis pr c demment la majorit de ces mesures value l int r t comme une fonction de la divergence entre la probabilit d apparition d une r gle calcul e sur les donn es et sa probabilit d ap parition sous l hypoth se d ind pendance Le d faut principal de ce type de mesures est qu elles ont tendance faire appara tre des r gles d j connues de l expert ou videntes En effet les motifs s lectionn s par ces m thodes peuvent tre d couvert par le biais de m thodes classiques ou ils peuvent se d duire intuitivement partir de l exp rience de l utilisateur S Jaroszewicz et al pensent que la meilleure fa on d aborder ce probl me est de prendre en compte les connaissances du domaine dans le processus de fouille de donn es Un motif sera int ressant s il est surprenant pour l expert ou inattendu Le caract re inattendu d un motif ou en l occurence d un itemset fr
59. travail probl matique de la recherche Les travaux de th se pr sent s dans ce rapport r sultent de la collaboration entre l quipe Ing nierie et syst mes apprenants du centre commun de recherche EADS et les d partements Fouille de donn es et Ing nierie des connaissances du LIRIS Dans ce premier chapitre nous pr sentons le contexte industriel qui a initi les travaux de th se l aide a l analyse des donn es d interruptions op rationnelles pour le compte d un grand constructeur a ronautique 1 1 Le contexte industriel Dans un contexte industriel un ing nieur est souvent confront a l analyse de grands volumes de donn es produites et stock es des fins de test de validation ou encore dans le but de tracer le fonctionnement d un processus op rationnel Ces donn es peuvent notamment servir a faciliter la d tection de comportements non pr vus du syst me Dans ce cas de figure il s agit de retrouver les particularit s de fonctionnement qui diff rent des mod lisations initiales En effet tout processus op rationnel tant soumis aux al as du monde r el il n est pas rare que malgr toutes les pr cautions prises lors des phases de conception du syst me celui ci diff re du comportement attendu Une des principales causes l origine de ce constat vient du d calage temporel qui existe entre la phase de conception initiale et exploitation en milieu op rationnel L environ
60. ud Syst mes a 3 fils dont Electro M canique alors une fr quence de 0 02 est pr visible i e 0 06 3 0 02 ici la r gle 2 est jug e redondante par rapport la 1 La description d une taxonomie sur les donn es est en fait un cas particulier de description des connaissances du domaine d application Dans ce cas il s agit de d pendances logiques parfaitement document es dont on souhaite tirer parti Il peut tre int ressant comme nous l avons formul pour l approche par templates de r fl chir une mod lisation plus syst matique des connaissances En effet s il est utile de pouvoir repr senter et exploiter une taxonomie existant sur certains attributs il est d autant plus int ressant de mod liser et d utiliser les relations quantitatives et qualitatives sur l ensemble des diff rents attributs du domaine 2 4 3 Extraction sous contraintes On peut voir APRIORI comme le premier algorithme d extraction sous contrainte En effet il utilise la contrainte de fr quence minimale pour laguer le treillis des itemsets On peut facilement g n raliser APRIORI afin d utiliser n importe quelle contrainte anti monotone Ainsi de nombreux algorithmes ont t d velopp s utilisant des contraintes vari es L objectif de ces travaux est double d une part optimiser la phase d extraction de motifs en introduisant des contraintes qui vont r duire l espace de recherche et d
61. velopper une interface sp cifique pour l aide l analyse des r gles d association Le but de cette interface est de permettre l tude d un volume potentiellement important de r gles et de faciliter leur manipulation L activit asso ci e est d taill e dans la figure 3 5 Nous pensons en effet que sans interface adapt e cette phase d analyse est extr mement laborieuse A collection d annotations Analyser les r gles d associations L lt P _bd _rb D sep gt L collection de regles d associations pertinentes Expert IHM du domaine FIG 3 5 Activit Analyser les r gles d association Par le biais de cette interface l utilisateur va pouvoir effectuer les diff rentes it rations du processus de d couverte de connaissance L tape d analyse des r gles ex traites est celle qui requiert le plus d interactions avec l expert du domaine Pour cela nous avons impl ment les fonctionnalit s suivantes tri et seuillage sur les mesures d int r ts filtrage syntaxique tests d hypoth ses annotations des r gles visualisation des parties d s par es et de impact des annotations et s lection d un ensemble de r gles pertinentes Nous reviendrons sur chacune de ces fonctions mais on peut retenir que les an notations sont un moyen de m moriser la pr sence dans la collection de r gles de motiff d j connus non valides non pertinents ou
62. 00 Springer Verlag Silja RENOOIJ Probability elicitation for belief networks issues to consider Cambridge University Press 16 255 269 2001 Jr ROBERTO J BAYARDO et Rakesh AGRAWAL Mining the most in teresting rules In Proceedings of the 1999 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining pages 145 154 New York NY USA 1999 ACM Press Christian P ROBERT The Bayesian Choice A Decision Theoretic Motivation Springer Verlag 1996 Uffe Kj RULFF Reduction of computational complexity in bayesian networks through removal of weak dependences In Proceedings of the 10th conference on uncertainty in Artificial Intelligence pages 374 382 Association for Uncertainty in Artificial Intelligence Morgann Kauf mann Publishers 1994 S RENOOI et C WITTEMAN Talking probabilities communica ting probabilistic information with words and numbers International Journal of Approximate Reasoning 22 169 194 1999 Ramakrishnan SRIKANT et Rakesh AGRAWAL Mining quantitative as sociation rules in large relational tables In SIGMOD 96 Proceedings BIBLIOGRAPHIE 131 SCHO5 SG92 Sme00 SON95 SSOT 97 ST96 STVNO4 TMHO1 Toi96 TPBLOO vaGRW 02 of the 1996 ACM SIGMOD international conference on Management of data pages 1 12 New York NY USA 1996 ACM Press Wang SHITONG Korris F L CHUNG et Shen HONGBIN Fuzzy ta
63. 3 LE TRAVAIL DE RECHERCHE Le graphe fait de plus ressortir les deux r sultats attendus l issue de notre processus de fouille un r seau bay sien et une collection de r gles d association annot es comme pertinentes Le RB repr sente les principales d pendances du domaine et il pourra tre r uti lis ult rieurement par exemple si l on souhaite effectuer nouveau le processus de d couverte de connaissances sur de nouvelles donn es Les d pendances d couvertes sur le domaine sont donc capitalis es La collection de r gles pertinentes pr sente de part sa nature un int r t pour les experts du domaine Ainsi la d couverte de r gles peut permettre d expliquer un comportement inattendu ou remettre en cause un fonctionnement jusqu alors per u comme tabli etc 71 KARD PROCESSUS DE D COUVERTE DE CONNAISSANCES 3 2 SOOURSSIRUUOD Op 9H9ANOI9P op SNSS09014 ap uorysodorg L E OIA aulewop np feLUIUIUU jewuju fewlu u senbixejui s WHI yadxy 1919U vueLuog u nb 4 SejUIeJJUON lt das q lt 0 0 sajueulied os meat Pae pqa gt 1 suone1osse p sab u sg L suoleloosse ap uon ajlo 1 suolyeloosse p IS9AEq 1e P seeuuop se bai se neesal 2 solbel sp sed jaskyeuy q Je o dx 9 Se 21121X3 g suolyejouue p U0198 109 Y ejuewubne eurewop np uaisexeq ne s sone ices aurewop np u gH Sop a seouepuedep abessjusidde p 2 seeuuoq al anol e amon
64. 3 1 on extrait l en semble des itemsets 2 fr quents libres i e minfreq 2 6 0 A B C E AB AE BC CE L ensemble des itemsets 2 fr quents 1 libre est quant lui compos uniquement de A En effet on peut voir par exemple que AF n est pas un itemset 1 libre car la r gle A E admet 1 exception de m me B n est pas 1 libre car il admet 1 exception sur bd etc Le concept de 6 libre est intimement li la notion de 6 fermeture ou quasi fermeture introduite par BBROO D finition 3 3 5 fermeture Soit S un itemset C Items et un entier positif La 6 fermeture de S est le plus grand sur ensemble de S d finit comme suit ferms S I Items Freq S Freq S U T lt Exemple Si l on poursuit notre exemple sur les donn es de la table 3 1 on peut calculer la 1 fermeture de A qui est donn e par fermi A A B 1 C E 1 Pour chaque item X de la 6 fermeture on note entre parenth ses la diff rence entre Freq A et Freq AU X e g Freq A 3 et Freq AB 2 d o sp 1 Ainsi l op rateur de 6 fermeture permet d extraire un ensemble d itemsets dont le support est born Si on note respectivement sg sc Sg le nombre d exceptions des itemsets qui composent la 6 fermeture de A alors on peut en d duire que Freq A maz sp sc se lt Freq fermi A lt Freq A sg sc se 76 CHAPITRE 3 LE TRAVAIL DE RECHERCHE Plus g n ra
65. 4 2 Mise en place du cadre de test 4 2 1 Description du jeu de donn es Il existe diff rentes sources de donn es relatives aux interruptions op rationnelles La base de donn es principale regroupe les d tails de tous les probl mes techniques survenus en op ration Un extrait de cette base est pr sent dans le tableau 4 1 Le jeu de donn es est principalement compos d attributs cat goriques comme le champ EngineType par exemple On note aussi que le champ Delay est une valeur num rique qu il va nous falloir discr tiser Certains champs ne sont pas exploitables tels quels d autres n cessitent d tre enrichis le champ ATA par exemple d signe par un code 6 chiffres un quipement de l appareil Ce chiffre fait partie d une taxonomie utilis e par les ing nieurs a ronautiques Par exemple VATA 212351 est un sous ensemble du syst me 2123 qui est lui m me un sous syst me de la cat gorie 21 4 2 MISE EN PLACE DU CADRE DE TEST 97 ATA Date Op rateur MSN Moteur A roport Phase Effet D lai Classe 0 29 12 1998 OPI 11 EngXXA ST3 TX DY 0 50 NM 0 30 12 1998 OPI 29 EngXXA ST4 CS DY 083 NA 212351 03 02 1998 OP2 11 EngXXA ST4 CS DY 0 68 212600 07 10 1998 OPI 50 EngXXA STI CS DY 0 39 212634 21 03 1998 OP2 142 EngXXA ST4 TX DY 0 85 212634 23 03 1998 OPI 34 EngXXA _ ST3 CS DY 1 15 212634 09 07 1998 OPI 87 EngXXA ST3 CS DY 0 25 212634 04 09 1998 OP3 50 EngXXA ST8 TO DY 16 00 NM 212634 13 09 1998 OP4 42 EngXXA S
66. 4 VLDB International Conference on Very Large Data Bases pages 487 499 Morgan Kauf mann 12 15 1994 121 122 Az 03 BAGO Bay98 BB00 BBJ 02 BBRO0 BBR03 BGH 02 BGS 00 BKGG04 BIBLIOGRAPHIE J r me AZ Extraction de connaissances partir de donn es num riques et textuelles th se de doctorat Universit Paris Sud de cember 2003 R J BAYARDO Rakesh AGRAWAL et D GUNOPULOS Constraint based rule mining in large dense databases Data mining and knowledge discovery 4 30 59 2000 R J BAYARDO Efficiently mining long patterns from databases In Proceedings of the SIGMOD conference pages 85 93 1998 Jean Francois BOULICAUT et Artur BYKOWSKI Frequent closures as a concise representation for binary data mining In Proceedings of the 2000 PAKDD Pacific Asia Conference on Knowledge Discovery and Data Mining volume 1805 de LNAI pages 62 73 Kyoto JP April 2000 Springer Verlag C line BECQUET Sylvain BLACHON Baptiste JEUDY Jean Francois BOULICAUT et Olivier GANDRILLON Strong association rule mi ning for large gene expression data analysis a case study on human SAGE data Genome Biology 12 2002 See http genomebio logy com 2002 3 12 research 0067 Jean Francois BOULICAUT Artur BYKOWSKI et Christophe RIGOTTI Approximation of frequency queries by means of free sets In Proceedings of the 2000 PKDD European Conference o
67. B e g rapport la distribution de probabilit calcul e sur les donn es et celle induite par la confi guration du r seau Cependant le crit re de convergence utilis est purement objectif et les modifications du r seau ne refl tent pas forc ment l volution des connaissances du domaine D autre part le processus de mise jour du RB n est ni encadr ni facilit ce qui implique de nombreux essais avant de converger vers une solution locale Une r flexion g n rale sur le processus de d couverte de r gles pertinentes le r le de l expert la mod lisation du RB initial et le suivi de son volution ainsi que sur les outils impl menter pour encadrer ce processus et faciliter l analyse des r gles Ce point de vue n a pas non plus t abord par les auteurs de ces travaux Enfin une exp rimentation et une validation de nos contributions sur des don n es r elles les travaux de Jaroszewicz et al tant pour l instant uniquement pr sent s sur des donn es simul es D finition d un ensemble d outils et de m thodes pour accompagner le processus de d couverte de connaissances La principale originalit de nos travaux par rapport aux pratiques actuelles en ECD et plus particuli rement dans le domaine de la d couverte de r gles d associa tion pertinentes est que nous avons inscrit nos diff rentes contributions dans une approche d ing nierie de la connaissance 62 CHAPITRE
68. CHAPITRE 4 APPLICATION PRATIQUE tion vidente ou d j connue de l expert la premi re it ration du processus cela repr sente 27 de la collection de r gles g n r e On peut aussi noter comme on l avait remarqu pour l exemple Visit Asia pr sent au Chapitre 3 qu il n y a aucune corr lation entre notre mesure et les autres mesures d int r t confiance j mesure moindre contradiction 4 3 5 Mise jour du r seau bay sien Les annotations pr c demment collect es r sum es dans le tableau ont t pass es un autre expert dont la t che tait d apporter des modifications au RB Ici nous avons d cid de faire une int gration directe de toutes les annotations K Les tables de probabilit s ont galement t modifi es en cons quence Pour des raisons videntes de place et de confidentialit elles ne peuvent pas tre pr sent es ici Le lecteur peut n anmoins se reporter la Figure pour valuer les modifications apport es en gras dans le graphe FIG 4 4 R seau bay sien l issue de la premi re mise jour RB02 4 3 EXPERIMENTATIONS REALISEES 105 4 3 6 Nouvelles it rations du processus It ration n 2 Apr s la mise jour du RB une nouvelle it ration du processus est initi e On retourne donc l tape 3 c est dire au calcul des mesures d int r t par rapport au nouveau RB Le tableau 4 4 montre l volution de la mesure d int r t avan
69. CONNAISSANCES KARD 63 d crivent les principales tapes de notre approche avant de d tailler le processus g n ral 3 2 1 Pr sentation de notre approche D un point purement applicatif le processus de d couverte de connaissances que nous proposons peut tre repr sent par la figure 3 1 Cette figure permet de visualiser les entr es partie gauche du sch ma les contr les partie inf rieure ou sup rieure et les sorties partie droite d une activit donn e bo te centrale En l occurrence nous avons choisi d orienter notre tude selon le contexte suivante partir d un ensemble de donn es d finir un processus de d couverte qui aboutit la construction d un mod le de connaissance le r seau bay sien et la d couverte d une collection L de r gles d association pertinentes aux yeux de l expert Ce processus est contr l par une probl matique sp cifique les connaissances ainsi que l expertise disponible sur le domaine d application Le r seau bay sien cr au cours du processus n est pas l objectif principal de notre processus Cependant il peut tre consid r comme un effet de bord int ressant d une part il mod lise un ensemble de d pendances du domaine d application et d autre part il pourra tre r utilis sur des probl matiques similaires lorsque par exemple les donn es du syst me voluent ou lorsque la probl matique est modifi e L volution de la
70. D 0 2 TAB 2 2 Exemples de r gles d association g n r es partir des itemsets fr quents extraits tableau La figure 2 2 pr sente le treillis des itemsets obtenu partir de la base de donn es bd figure 2 1 Cette repr sentation permet de visualiser l impact de l application de la propri t d anti monotonie pour la contrainte de fr quence minimale Par exemple l itemset DE n est pas fr quent ce qui nous permet d liminer tous les itemsets de niveau sup rieur qui contiennent DE CDE BDE ADE ABDE ACDE BCDE et ABCDE Les tableaux et 2 2 nous montrent l ensemble des itemsets fr quents calcul s pour une fr quence absolue sup rieure ou gale 2 ainsi que quelques exemples de r gles d association pouvant tre g n r es partir de ces itemsets 26 CHAPITRE 2 D COUVERTE DE R GLES PERTINENTES itemset fr quent 1 i to F1G 2 2 Treillis des itemsets et partition des itemsets fr quents 2 2 3 Algorithmes d extraction de tous les itemsets fr quents APRIORI AMS 96 est le premier algorithme efficace pour l extraction d itemsets fr quents il proc de en deux temps 1 On recherche les itemsets fr quents ceux dont la fr quence est sup rieure au seuil minfreq en effectuant un parcours en largeur du treillis des itemsets et en calculant les fr quences par comptage dans la base
71. ES 39 fr quents Une fois les itemsets libres fr quents r cup r s on calcule leurs fermetures et on obtient la collection des ferm s fr quents Ainsi par rapport APRIORI tous les itemsets non libres sont lagu s il y a donc une diminution du nombre d itemsets trait s Dans le pire des cas cependant si tous les itemsets sont libres on va par courir autant d itemsets qu avec APRIORI mais avec un l ger sur co t engendr par la v rification de la contrainte sur les itemsets libres En pratique sur des donn es fortement corr l es beaucoup d itemsets sont libres et l lagage se r v le efficace Approche en profondeur d abord Cette classe d algorithme effectue un par cours en profondeur de l espace de recherche Lorsque l algorithme a fini de traiter un itemset S il examine ses fils par ordre croissant de fr quence Les fils de S sont les itemsets de la forme S Uz ou est un item qui n a pas encore t examin dans d autres branches de l arbre constitu par les itemsets Closet PHMOO et Charm ZH02 sont les deux algorithmes les plus efficaces concernant l extraction des itemsets ferm s fr quents par un parcours en profondeur d abord 2 3 3 Diff rentes repr sentations condens es des itemsets fr quents Les repr sentations condens es utilisant les itemsets ferm s fr quents que nous in troduisons ici ont t pr sent es pour la premi re fois par BBO0 Lorsque les donn es
72. HARD Henri BRIAND Fabrice GUILLET Pascale KUNTZ R mi LEHN et Philippe PETER Quelques crit res pour une mesure de qualit de r gles d association un exemple l intensit d implication Revue des Nouvelles Technologies de l Information RNTI E 1 2004 W R GILKS S RICHARDSON et D J SPIEGELHALTER Markov Chain Monte Carlo In Practice Chapman amp Hall 1996 Bart GOETHALS et Mohammed J ZAKI Proceedings of the IEEE ICDM Workshop on Frequent Itemset Mining Implementations FIMI 2003 Melbourne USA 2003 John D HOLT et Soon M CHUNG Efficient mining of association rules in text databases In CIKM 99 Proceedings of the eighth international conference on Information and knowledge management pages 234 242 New York NY USA 1999 ACM Press Emmanuel HUGUES Eric CHARPENTIER et Andr CABARBAYE Ap plicatin of markov processes to predict aircraft operational reliability In Proceedings of the 3rd European systems engineering conference 2002 D HECKERMAN A tutorial on learning with bayesian networks Rap port technique Microsoft Research 1995 David HECKERMAN Bayesian networks for data mining Data Mining and Knowledge Discovery 1 1 79 119 1997 Jiawei HAN et Yongjian FU Discovery of multiple level association rules from large databases In VLDB 795 Proceedings of the 21th International Conference on Very Large Data Bases pages 420 431 San Francisc
73. L estimation de distributions de probabilit s ou les param tres des lois corres pondantes partir de donn es disponibles est un sujet vaste et complexe On peut conseiller en particulier la lecture de Hec95 Kra98 Jor98 Dans le cas o toutes les variables sont observ es la m thode la plus simple et la plus utilis e est l estimation statistique qui consiste estimer la probabilit d un v nement dans la base de donn es Cette approche appel e maximum de vraisemblance nous donne Ni j k p X Xi E AEE 2 1 BUX an pal Xi 25 Ok KN oe o Nije est le nombre d v nements dans la base de donn es pour lesquels la variable X est dans l tat x et ses parents dans l tat zj Le lecteur pourra aussi consulter l approche par estimation bay sienne d crite dans Rob96 Elle consiste trouver les param tres 0 les plus probables sachant que les donn es ont t observ es en utilisant des a priori sur les param tres Apprentissage des param tres 4 partir de donn es incompl tes Lorsque ce qui est souvent le cas dans les bases de donn es r elles les don n es sont incompl tes la probl matique d apprentissage des param tres est diff rente Dans ce cas l la m thode la plus utilis e repose sur l algorithme it ratif Expectation Maximisation EM propos par A Dempster et al en 1977 et appliqu aux r seaux bay siens dans ainsi que dans TMHO1 L
74. N D ORDRE 2007 ISAL 0077 ANN E 2007 TH SE pr sent e devant L INSTITUT NATIONAL DES SCIENCES APPLIQUEES DE LYON pour obtenir LE GRADE DE DOCTEUR Sp cialit INFORMATIQUE Ecole Doctorale Informatique et Information pour la Soci t par Cl ment FAUR D COUVERTES DE MOTIFS PERTINENTS PAR VIMPLEMENTATION D UN R SEAU BAYESIEN APPLICATION L INDUSTRIE A RONAUTIQUE Soutenue publiquement le 20 11 2007 devant le jury Jean Fran ois BOULICAUT Professeur l INSA de Lyon Co directeur Jean CHARLET Chercheur HDR AP Hopitaux de Paris Rapporteur Sylvie DEPRAT Chercheur EADS France Bart GOETHALS Professeur l Universit d Anvers Belgique Fran ois JACQUENET Professeur l Universit de Saint Etienne Rapporteur Alain MILLE Professeur l Universit Lyon 1 Co directeur Je tiens tout d abord remercier tr s chaleureusement Sylvie Delprat Jean Fran ois Boulicaut et Alain Mille qui ont rendu cette th se tr s enrichissante aussi bien sur le plan scientifique qu humain Ce travail doit aussi beaucoup mes coll gues d EADS IW c toy s tout au long de ma th se et notamment Michel Dureigne Christian Trinquier pour leurs discussions clair es et leurs conseils avis s Je tiens aussi remercier particuli rement Emmanuel Hugues pour son professionnalisme et la confiance qu il m a accord e dans l tude des donn es d interruptions op rationnelles Merci aus
75. QUIER Yves BASTIDE Rafik TAOUIL et Lotfi LAKHAL Discovering frequent closed item for association rules In Catriel BEERI et Peter BUNEMAN diteurs Proceedings of the 7th international conference on knowledge discovery and data mining pages 398 416 Jerusalem Isra l janvier 1999 Berlin Springer Verlag Nicolas PASQUIER Yves BASTIDE Rafik TAOUIL et Lotfi LAKHAL Efficient mining of association rules using closed itemset lattices Information Systems 24 1 25 46 janvier 1999 Judea PEARL Probabilistic reasoning in intelligent systems networks of plausible inference Morgan Kaufmann Publishers Inc San Fran cisco CA USA 1988 Jian PEI Jiawei HAN et Runuying Mao Closet an efficient algorithm for mining frequent closed itemsets In Dimitrios GUNOPULOS et Rajeev RASTOGI diteurs Proceedings of the ACM SIGMOD workshop on research issues in data mining and knowledge discovery DMKD 00 2000 C POTTER S KLOOSTER M STEINBACH P TAN V KUMAR S SHEKHAR R NEMANI et R MYNENI Global teleconnections of ocean climate to terrestrial carbon flux Journal of Geophysical Research Atmospheres 108 D17 September 2003 Michael POLANYI Tacit Dimension Routledge amp Kegan Paul Ltd London 1966 M PRADHAN G PROVAN B MIDDLETON et M HENRION Know ledge engineering for large belief networks In Uncertainty in AI Proceedings of the Tenth Conference 1994 130
76. T2 CS DY 2 37 212651 07 09 1998 OP3 151 EngXXA STI CS DY 0 51 NS 212651 16 10 1998 OP5 170 EngXXA ST3 CS DY 0 42 TAB 4 1 Extrait de la base de donn es d interruptions op rationnelles syst me lectrom canique L expert souhaite qu une analyse du num ro ATA puisse s effectuer ses diff rents niveaux de d composition i e 2 4 et 6 chiffres Enfin une des sp cificit s de ce jeu de donn es est la pr sence d un champ de texte libre qui d crit l incident et donne ventuellement des d tails suppl mentaires sur l interruption op rationnelle quelles pannes ont t d tect es Quelles actions ont permis la remise op rationnelle de l appareil Les informations contenues dans ce texte libre ne sont malheureusement pas toutes report es dans les autres champs de la base De plus ces textes tant r dig s par des op rateurs de maintenance diff rents sans formalisme impos leur structure et leur s mantique n est pas homog ne Un exemple de texte libre est pr sent dans la Figure Troubles with entertainment system after installation of new software Crew tried reset nil fix EPESC enhanced pax entertainment system controller replaced Old software loaded System repaired by MAS representant Fic 4 1 Exemple de texte d taillant une interruption op rationnelle Enfin il faut aussi savoir que les donn es utilis es sont relativement bruit es et que quelques donn es sont
77. TbOrCa XRay 0 97 0 41 0 01 11 Bronchitis Cancer Smoking TbOrCa XRay 0 97 0 45 0 01 12 Bronchitis Dyspnea TbOrCa XRay 0 97 0 03 0 01 13 Bronchitis Smoking TbOrCa XRay 0 97 0 03 0 01 14 Cancer Dyspnea Smoking TbOrCa 1 00 0 66 0 00 15 Cancer Dyspnea XRay TbOrCa 1 00 0 69 0 00 16 Cancer Smoking XRay TbOrCa 1 00 0 73 0 00 17 Bronchitis Cancer Dyspnea Smoking TbOrCa XRay 0 97 0 40 0 07 18 Bronchitis Dyspnea Smoking TbOrCa XRay 0 97 0 03 0 01 19 Cancer Dyspnea Smoking XRay TbOrCa 1 00 0 64 0 00 20 Cancer TbOrCa 1 00 0 84 0 00 TAB 3 6 R gles d association extraites partir de Visit Asia RB_01 Les items soulign s appartiennet D sep R 3 7 VALIDATION SUR LES DONN ES VISIT ASIA 91 tape D Dans la r alit l expert dispose de l outil d aide l analyse que nous avons d velopp Ici nous allons devoir analyser les r gles partir du tableau Dans ce tableau nous avons soulign les parties des r gles qui appartiennent D core elles d notent ce que l on appelle les d pendances principales de la r gle Les parties de la r gle qui ne sont pas soulign es contiennent quant elles des informations qui n ont pas t mod lis es par le RB actuellement utilis ce sont les parties appartenant D sep En regardant ces r sultats deux r gles d association ont une valeur d int r t lev e il s agit des r gles n 2 et n 9 La r gle n 2 nous dit que Lor
78. XRay sont compl tement d connect s du reste du graphe les tables de probabilit s conditionnelles sont videmment red finies en cons quence Le m me cal cul d int r t vis vis de ce RB consisterait alors d terminer p X Ray Abnormal soit 0 11 ce qui nous donnerait Int 0 87 Dans ce cas l int r t par rapport au RB est plus lev puisque l association exprim e par la r gle ne se retrouve pas dans le mod le Cela correspond parfaitement au comportement attendu de notre mesure tudions pr sent la r gle 2 La formule nous donne conf ref p TbOrCa True Bronchitis Present Cancer Present Dyspnea Present Smoking Smoker x p X Ray Abnormal Bronchitis Present Cancer Present Dyspnea Present Smoking Smoker 1 00x 0 98 Tous les calculs d inf rence peuvent tre reproduits en utilisant le logiciel libre Bayesian Network Tools in Java disponible l adresse suivante http sourceforge net projects bnj Le r seau P P g pro J Visit Asia est lui aussi disponible via l application 82 CHAPITRE 3 LE TRAVAIL DE RECHERCHE 0 98 Intr ref 0 97 0 98 0 01 3 5 2 Extraction des parties d s par es d pendances principales Il est int ressant de pouvoir exploiter les composantes graphiques du RB dans le cadre de l analyse de r gles d association Un arc orient reliant deux variables X et Y d un RB et une r gle association X Y ont une repr s
79. a mise au point du r seau bay sien sont consid r es comme des probl mes difficiles Le probl me de l apprentissage ou construction d un RB doit permettre de r pondre ces deux questions Comment estimer les lois de probabilit s conditionnelles Comment trouver la structure du r seau bay sien Ainsi on va naturellement diviser le probl me de l apprentissage en deux par ties l apprentissage des param tres avec une structure fix e et l apprentissage de la structure Inf rence dans les r seaux bay siens Le mod le repr sent par le RB n est pas un mod le statique ferm Il est capable d int grer de nouvelles informations exog nes Celles ci en modifiant la vraisemblance de certains n uds vont modifier les probabilit s a posteriori de l ensemble du sys t me Tout calcul portant sur la distribution de probabilit associ e un RB rel ve de l inf rence En fait il ne s agit pas d un probl me th orique la distribution de probabilit tant enti rement d finie mais d un probl me de calcul 50 CHAPITRE 2 DECOUVERTE DE REGLES PERTINENTES Cette op ration l inf rence probabiliste a t prouv e NP difficile dans le cas g n ral Coo88 Pour r soudre ce probl me on peut distinguer deux classes d algo rithmes d inf rence les m thodes exactes et les m thodes approch es Dans la cat gorie des m thodes exactes on peut faire la distinction entre les
80. a recherche de nouveaux facteurs ayant un impact sur la fr quence des interruptions op rationnelles Tous les calculs ont t effectu s partir d un ordinateur standard processeur 2 GHz 1 Go de m moire 4 2 3 Exploitation du texte libre Une analyse manuelle de plusieurs champs de texte libre ainsi qu une discussion avec l expert mis en avant l importance de ce champ dans l tude des donn es d IO Il est effectivement porteur d informations int ressantes pour l expert Ceci nous a pouss s mettre en place une analyse assez fine de son contenu L objectif tant de pouvoir extraire certaines caract ristiques de ce texte lorsqu elles sont pr sentes Le sujet de la th se n tant pas la fouille de texte on restera toutefois assez brefs quant aux techniques employ es On ne pr tend pas non plus que la m thode utilis e est la plus adapt e notre cas d application La d marche est simple on va chercher extraire de chaque texte diff rentes informations relatives au contexte de IO au probl me effectivement constat par les quipes de maintenance ainsi qu aux actions qui ont t men es pour tenter de remettre l avion en op ration chacun de ces champs correspond un ensemble de mots cl s dans le texte libre et un ensemble d attributs que l on souhaite utiliser pour la fouille de donn es Gr ce un ensemble de r gles fournies par notre expert nous avons tabli une
81. aintes utilisant les fonctions d agr gats e g SOMME S lt 100 Ces algorithmes sont int ressants car ils permettent de pousser les contraintes c est dire de les utiliser pour limiter l espace de recherche lors de la phase d extrac tion des itemsets fr quents 2 4 4 Conclusion L introduction de contraintes sp cifi es par lutilisateur permet de r duire encore un peu plus le nombre de r gles analyser en se focalisant sur ce qui int resse Vutilisateur donc en liminant les motifs qui ne l int ressent pas ceux qu il conna t d j On distingue alors deux fa ons de proc der soit on exprime ces contraintes de mani re ce qu elles puissent tre exploit es au moment de l extraction ouvrant ainsi la porte des bases de donn es toujours plus complexes soit ces contraintes sont utilis es en post traitement Nous pensons que ces approches constituent en quelque sorte une fa on d gui s e de d crire et de mettre profit certaines connaissances du domaine Il peut tre int ressant de voir s il est possible de g n raliser ce type d approche en introduisant un mod le plus formel des connaissances exprim es par l expert 2 5 Comment prendre en compte la connaissance du do maine 2 5 1 D finition du probl me On peut effectuer une distinction entre diff rents types de r gles d association 1 Une r gle d association peut correspondre une connaissance du domaine ou
82. aire les r gles d associations 66 3 4 Activit Exploiter le r seau bay sien gt 67 3 5 Activit Analyser les r gles d association gt 68 Vii 3 6 Activit Mettre jour le r seau bay sien gt 69 3 7 Proposition de processus de d couverte de connaissances 71 3 8 R seau bay sien de r f rence sur le domaine Visit Asia RB ref 72 CREA BA ee OEM EU So Ae eh ee Ee NE 73 ai ot 85 3 11 R seau bay sien Visit Asia RB_ 0 utilis pour la 1 it ration du ae gree nee ee 89 re 97 4 2 Extrait de la requ te SQL pour le pr traitement des donn es 98 4 3 R seau bay sien initial RBO1 sur les donn es IO 101 44 R seau bay sien l issue de la premi re mise jour RB02 4 5 R seau bay sien l issue de la deuxi me mise jour RB03 A 1 Interface de configuration du serveur onglet permettant la configura tion des sources de donn es 117 A 2 Interface de configuration du serveur onglet de configuration de l al gorithme d extraction 117 A 3 Interface de configuration du serveur onglet permettant la configura tion du r seau bay sien initial a 118 A 4 Interface d analyse des r gles d association 118 A 5 Annotation de r gles d asso
83. aissances concerne le cas o l ing nieur doit faire face des sources d informations de diverses natures experts donn es collect es selon des moyens vari s etc La prise en compte de ces diff rentes sources doit se faire avec pr caution pour viter d utiliser des donn es biais es Ainsi propose un crit re pour v rifier si les diff rentes sources d in formations ont t utilis es dans les m mes conditions Supposons maintenant que plusieurs experts proposent une estimation sur les m mes valeurs Comment combi ner ces diff rents r sultats La prise en compte de donn es incertaines a t abord e sous diff rents angles la logique floue BMM03 ou la th orie des croyances Sme00 Les auteurs de proposent quant eux une m thode qui permet de combi ner l estimation des probabilit s faite par un expert avec celle obtenue partir des donn es 54 CHAPITRE 2 D COUVERTE DE R GLES PERTINENTES Apprentissage de la structure Comment trouver la structure de r seau bay sien qui repr sentera le mieux le probl me L apprentissage de la structure partir des donn es est aussi consid r comme tant un probl me NP difficile Une premi re approche consiste rechercher les diff rentes relations causales qui existent entre les variables Les autres approches essaient de quantifier l ad quation d un r seau bay sien au probl me r soudre c est dire en associant un score chaque struc
84. aissances du domaine ou des connaissances attendues ainsi que des r gles redondantes ou non pertinentes vis vis du contexte alors il y a de fortes chances pour que les r gles restantes soient porteuses d informations valides et int ressantes Nous avons voqu s jusque l diff rentes techniques qui peuvent se montrer com pl mentaires pour mener bien cette t che D une part on sait qu il est possible de travailler partir d un ensemble concis de r gles on limine ainsi la redondance in trins que r gles de la cat gorie 3 De plus lutilisateur a la possibilit de pr ciser diff rentes contraintes filtrage syntaxique approches bas es sur les patrons exploi tation des taxonomies qui vont lui permettre d liminer une part des r gles inutiles cat gorie 2 Enfin tout un ventail de mesures objectives va faciliter l valuation des r gles restantes savoir les r gles des cat gories 1 et 4 Comme on peut le voir le probl me de la redondance au domaine d application n a pas encore t r solu En appliquant des contraintes sp cifi es par l utilisateur on fait intervenir un biais dans le processus de d couverte de r gles pertinentes Ce biais est essentiel car sur des cas d application complexes les r sultats sont trop nombreux et la redondance par rapport au domaine d application est trop importante Seulement les m thodes pr sent es ont toutes pour d faut d tre appliqu es de
85. ale difficult de cette phase d analyse provient d une part du tr s grand nombre de r gles d association extraites et d autre part de la redondance par rap port au domaine d application port e par un grand nombre de r gles Ainsi les r gles r ellement int ressantes sont litt ralement noy es dans la masse des r sultats issus de l algorithme d extraction Les contributions apport es ce probl me restent limit es dans leur efficacit notamment lorsqu il s agit de g rer efficacement la redondance intrins que au domaine d application Une autre voie de recherche consiste utiliser les connaissances du domaine pour faire ressortir les r gles pr sentant une informa tion qui appara t comme contradictoire Les travaux de S Jaroszewicz et al JS04 en particulier ont pos les premiers jalons quant la possible utilisation d un r seau bay sien comme mod le des connaissances du domaine Dans leurs travaux ce r seau est exploit pour mettre en vidence des ensembles d attributs potentiellement int ressants au regard des connaissances d j mod lis es par le r seau bay sien Dans FDMB06a nous sommes partis de cette proposition pour d crire une m thodologie d extraction de r gles d association pertinentes sous l hypoth se qu un r seau bay sien capture de la connaissance experte sur certaines d pendances entre les variables du domaine il est alors possible de pr senter des r gles d asso
86. alized association rules pages 74 82 1998 Tomasz IMIELINSKI et Heikki MANNILA A database perspective on knowledge discovery Communications of the ACM 39 11 58 64 1996 Tomasz IMIELINSKI et Aashu VIRMANI Msql A query language for database mining Data Min Knowl Discov 3 4 373 408 1999 Baptiste JEUDY Optimisation de requ tes inductives application a l extraction sous contraintes de r gles d association Th se de doctorat Universit Lyon I INSA de Lyon december 2002 Michael I JORDAN Zoubin GHAHRAMANI Tommi JAAKKOLA et Law rence K SAUL An introduction to variational methods for graphical models Machine Learning 37 2 183 233 1999 Finn V JENSEN F V V JENSEN et F V JENSEN Introduction to Bayesian Networks Springer Verlag New York Inc Secaucus NJ USA 1996 M I JORDAN Learning in Graphical Models MIT Press 1998 Finn V JENSEN Uffe Kj RULFF Brian KRISTIANSEN Claus Skaan ning Helge LANGSETH Jiri VOMLEL et Marta VOMLELOVA The sasco methodology for troubleshooting complex systems BIBLIOGRAPHIE 127 JS02 JS04 JS05 K1e99 KMRt 94 Kra98 LAK 01 LHM99 LK9S LMV 04 LPT04 S JAROSZEWICZ et D A SIMOVICI Pruning redundant association rules using maximum entropy principle In Advances in Knowledge Discovery and Data Mining 6th Pacific Asia Conference PAKDD 02 pages 135 147 Taipei Taiwan mai 2002
87. ant donn une base de donn es bd d finie sur Items un seuil de fr quence minimal y et un entier 6 gt 0 une r gle 6 forte sur bd Il s agit du m me exemple que celui pr sent dans Pas00 il nous permettra de comparer les diff rentes collections de r gles 3 4 R GLES D ASSOCIATION NON REDONDANTES 75 est une r gle d association X Y et Freg XUY gt y Freq X Freg X UY lt 6 XUY C Items avec Y Exemple Une r gle 6 forte accepte donc au plus 6 exceptions sur sa partie droite Dans bd un exemple de r gle 1 forte est AC E par contre BE A n est pas une r gle 1 forte Un sous ensemble des r gles 6 fortes sont les r gles 6 fortes dont la partie droite est compos e d un seul item Ces r gles sont particuli rement int ressantes pour des probl matiques de classification car il est possible partir de crit res sur 6 et sur le seuil de fr quence minimale d obtenir un ensemble de r gles au corps minimal caract risant des classes i e la partie droite des r gles est une classe L ensemble des r gles 6 fortes peut tre construit partir de l ensemble des item sets d libres qui forment le corps de la r gle On rappelle la d finition d un itemset 6 libre D finition 3 2 Itemset 6 libre Soit S un itemset libre S est d libre s il n existe pas de r gle 6 forte X Y telle que XUY CS Y 4 Exemple Sur la base de donn es bd repr sent e dans la table
88. ante Si la compagnie qui op re l avion est en zone europ enne zone E que le probl me survient pendant la phase de v rification de l appareil http sourceforge net projects bnj 4 3 EXPERIMENTATIONS REALISEES 103 check list ou CS et que la derni re action effectu e par l quipe de maintenance est un change standard de l quipement incrimin last_ action swap alors on observe tr s souvent un d lai inf rieur six heures DY et le fait qu un change standard a t effectu swap Prenons un autre exemple ainsi CS ST3 zone ME DY OP3 other nous dit que Si le probl me a lieu au moment de la phase de v rification au sol CS et que l on se trouve l a roport d sign par le sigle S73 alors on observe souvent l ensemble des faits suivants on se trouve au Moyen Orient zone ME l interrup tion est un retard inf rieur six heures DY la compagnie qui op re l avion est d sign e par OP3 et l a roport o a lieu l interruption n est ni la base principale de la compagnie MB ni celle d une autre compagnie other Enfin les codes 2 4 ou 6 chiffres repr sentent ATA de l quipement incrimin dans l IO diff rents niveaux de d composition Pour une raison de confidentialit tous les num ros ont t maquill s 4 3 4 tude des r gles d association et annotations L tape suivante de notre processus consiste pour l expert du domaine
89. appel des contributions envisag es 59 3 2 Processus de d couverte de connaissances KARD 62 3 2 1 Pr sentation de notre approche 63 3 2 2 Le processus KARD d taill l 69 ee a aa ae E A Noh oe OS 72 ee ee ee ee ee 73 SN POL be to ee at ew ee g 79 3 5 1 D finition d une mesure de pertinence des r gles vis vis d un PR teh Sates Ai Myce du ai om Te ee 79 3 5 2 Extraction des parties d s par es d pendances principales 82 ere rae 84 3 6 1 N cessit des annotations 84 io bade woe Se ha de de 84 3 6 3 Prise en compte des annotations 86 hae fio Ge ahs Sete Aha thee D Get 87 3 7 1 Objectifs de notre d marche exp rimentale 87 DT Re ke eM Gee 88 foe US de De Go 89 GR BAG amp on bE S dit ali 94 95 mc teats Ses We he Ye Pook eit Gets He Bee 95 42 Mise en place du cadre de test 2 ee 96 4 2 1 Description du jeu de donn es 96 4 2 2 Pr traitements 98 4 2 3 Exploitation du texte librel 99 4 3 Exp rimentations r alis es 100 4 3 1 D finition du r seau bay sien initial 4 3 2 G n ration d un ensemble concis de r gles d association 4 3 3 Exploitation du r seau bay sien sur les r gles extraites 4 3 4 Etude des r gles d association et annotatio
90. ar le biais de la fouille de donn es les informations utiles et seulement elles avec un minimum d intervention de la part de l expert et enfin permettre de capitaliser les informations collect es gr ce la fouille de donn es de mani re organis e afin de les p renniser Classiquement le processus ECD fait ressortir trois tapes savoir 12 CHAPITRE 1 CADRE DE TRAVAIL 1 La phase de pr paration des donn es consiste dans un premier temps d velopper une bonne compr hension du domaine d application des connaissances pertinentes du domaine ainsi que des objectifs de l utilisateur final Ensuite il faut mettre en place le jeu de donn es s lection des donn es r duction du nombre de variables nettoyage et pr traitements en vue des algorithmes des fouilles gestion des donn es manquantes etc Cette phase est g n ralement tr s co teuse en temps 2 La t che d extraction de mod les et motifs Le choix de l algorithme d ex traction refl te les objectifs de fouille qui ont t fix s Est ce que le processus de fouille a pour but la classification la r gression le clustering l extraction de r gles Une fois la technique choisie il faut d cider quels param tres sont les plus appropri s par rapport aux donn es tudi es Ainsi on peut distinguer deux types d approche pour la fouille de donn es la construction de mod les des donn es et l extraction de motifs locaux 3 Enfin l
91. as de travaux formalis s sur l aide l analyse de donn es d interruptions op rationnelles Les outils employ s par les ing nieurs sont des outils commerciaux tableurs syst mes de bases de donn es relationnelles ainsi qu un en semble de m thodes ad hoc qui permettent de valider certains facteurs sugg r s par l expert Il y a n anmoins un int r t marqu quant l tude et la mise en place de 1 2 ANALYSE DES INTERRUPTIONS OP RATIONNELLES 7 techniques permettant de faciliter cette phase d analyse des donn es Un des objec tifs tant de pouvoir faire merger les conditions op rationnelles pouvant entra ner de mani re r p t e des interruptions op rationnelles Dans nos travaux nous nous sommes concentr s sur l extraction de motifs locaux pertinents pour l enrichissement des connaissances li es aux IO On d signe par motif local une particularit ob serv e sur les donn es Ce motif peut s exprimer sous diff rentes formes notamment comme une association de facteurs co occurants au sein d un sous ensemble des don n es tudi es Probl matique des experts pour la pr diction des taux d interrup tions op rationnelles Le premier point concerne le travail des ing nieurs a ronautiques charg s de d finir et de maintenir le mod le de pr diction Ce besoin concerne l int gration des connaissances du domaine et du retour d exp rience pour l am lioration du mod le de pr diction de
92. ases Mach Learn 45 3 279 299 2001 Hannu TOIVONEN Sampling large databases for association rules In VLDB 796 Proceedings of the 22th International Conference on Very Large Data Bases pages 134 145 San Francisco CA USA 1996 Morgan Kaufmann Publishers Inc R TAOUIL N PASQUIER Y BASTIDE et L LAKHAL Mining bases for association rules using closed sets In Proceedings of the ICDE conference page 307 2000 L van der GAAG S RENOOIJ C WITTEMAN B ALEMAN et B TAAL Probabilities for a probabilistic network A case study in oesophageal cancer 2002 132 WF05 XHD 05 Zak00 ZH02 Z098 ZPOL97 BIBLIOGRAPHIE Ian H WITTEN et Eibe FRANK Data Mining Practical machine learning tools and techniques Morgan Kaufmann San Francisco 2nd edition dition 2005 Hui XIONG Xiaofeng HE Chris DING Ya ZHANG Vipin KUMAR et Stephen R HOLBROOK Identification of functional modules in protein complexes via hyperclique pattern discovery In Proceedings of Pacific Symposium on Biocomputing volume 10 2005 Mohammed Javeed ZAKI Generating non redundant association rules In Proceedings of the KDD Conference FIXME 2000 Mohammed Javeed ZAKI et Ching Jui HSIAO Charm an efficient algorithm for closed itemset mining In Robert GROSSMAN Jiawei HAN Vipin KUMAR Heikki MANNILA et Rajeev MOTWANI diteurs Proceedings of the 2nd international SIAM conference on da
93. ation sur tous les sous ensembles d itemsets nous aurions eu en plus effectuer les tests suivants 4 AB C D 5 AC B D 6 BC A D Suivant les r sultats de ces tests la composition des parties d s par es de la r gle peut tre diff rente Ainsi dans le cas ot les tests 1 et 2 sont vrais mais que 4 est faux on peut donner l interpr tation suivante Sachant que j observe C le fait d observer A et B simultan ment m apporte une connaissance suppl mentaire sur C Dans ce cas D sep 0 84 CHAPITRE 3 LE TRAVAIL DE RECHERCHE 3 6 Le r le de l expert dans le processus de d couverte Nous disposons d un algorithme capable d extraire une collection concise de r gles d association partir de grands volumes de donn es d un formalisme pour mod liser certaines connaissances priori de l expert ainsi que d une mesure prenant en compte ces connaissances pour valuer l int r t des r gles d association g n r es Tous ces outils sont mis au service de l expert en charge de l analyse des r gles Ils vont lui permettre d acqu rir une compr hension plus fine des r gles manipul es et implicite ment une meilleure compr hension du domaine L expert doit tre en mesure de transf rer sa compr hension des r gles vers le mod le des d pendances utilis De cette fa on on pense d couvrir des r gles de plus en plus pertinentes Cette section d crit le r le q
94. c n cessaire pour rep rer les r gles r elle ment int ressantes Dans la section suivante nous voquons diff rentes contributions issues de la litt rature sur les mesures d int r t dites objectives 2 2 5 Autres mesures de l int r t objectif d une r gle d association Nous avons vu que les algorithmes du type APRIORI fond s sur la fr quence et la confiance des r gles ont apport une premi re solution au probl me de l extraction 30 CHAPITRE 2 D COUVERTE DE R GLES PERTINENTES de r gles mais ils produisent une trop grande masse de r gles s lectionnant certaines r gles sans int r t et ignorant des r gles int ressantes Ainsi de nombreux travaux de recherche visent d finir de nouvelles mesures pour compl ter le support et la confiance Le sujet est trop vaste pour que toutes ces mesures soient num r es ici On peut n anmoins citer les mesures les plus utilis es Le Lift par exemple est une fa on de r gler le probl me d interpr tation de la confiance que nous avons vu dans l exemple pr c dent Il se d finit de la fa on suivante Lift conf A B F AB 1 F B F A x F B Le fait de faire intervenir la fr quence de B par rapport a la confiance revient comparer la fr quence de l itemset AB constat e par rapport sa fr quence sous Vhypoth se d ind pendance statistique entre A et B Ainsi en appliquant le Lift notre exemple tableau 2 3 on obtient Li
95. ces exprim es sous la forme de r gles logiques L algorithme d velopp a t valid exp rimentalement en comparaison avec l algorithme APRIORI M me si la comparaison des performances avec PRIORI est ici anecdotique puisque comme on Va dit A PRIORI a t con u pour extraire toutes les r gles sup rieures un certain seuil de fr quence on se rend compte de l int r t des approches visant r duire le nombre de r gles extraites D une part cela permet de travailler des seuils de fr quences plus bas et donc potentiellement plus int ressants aux yeux d un expert et d autre part le nombre de r gles analyser tant plus faible on tend plus rapidement vers la d couverte de r gles int ressantes On peut cependant formuler un premier probl me vis vis de ces travaux En effet ici l int r t d une r gle est trait localement ce qui rend impossible la prise en compte de la transitivit Si l on prend les r gles B et B C comme repr sentant les connaissances du domaine alors la r gle C pourra tre jug e int ressante alors m me que les connaissance du domaine nous indiquent par transitivit que cette relation est d j connue Un deuxi me probl me que l on voit se dessiner pour ce type d approche est l tape de d finition de l ensemble des croyances ou plus g n ralement des connaissances a priori M me si l approche de type syst me expert a t
96. cessus de d couverte de connaissances aux donn es d interruptions pour le compte d un grand constructeur a ronautique En partant d une bauche de mod le des d pendances du domaine nous avons labor un r seau bay sien dont la structure finale est une bonne repr sentation des liens existant entre les diff rentes variables tudi es Les pr cisions successivement apport es au RB ont permis un filtrage de plus en plus efficace des r gles connues non valides ou non int ressantes la derni re it ration de notre processus des r gles ayant un fort int r t par rapport au RB ont effectivement t jug es comme porteuses d informations pertinentes par l expert Un des avantages constat s exp rimentalement par notre approche r side dans la possibilit d liminer un grand nombre de r gles qui ne pr sentent pas d int r t pour l expert De plus dans nos exp riences aucun faux n gatif n a t d tect parmi cet ensemble de r gles 114 CHAPITRE 5 CONCLUSION Au final la d couverte de ces d pendances et les modifications qui en ont d coul confortent le principe propos par notre approche qui est de mod liser par interaction avec l expert les d pendances du domaine et les exploiter pour am liorer le filtrage des r gles d association extraites et ainsi faciliter leur tude Ces r sultats soul vent n anmoins quelques nouvelles interrogations notamment sur la gestion des cas de faux pos
97. ci s l ensemble des interruptions op ration nelles lesquels contenaient une r f rence l application d une proc dure de mainte nance particuli re la Master Minimum Equipment List ou MMEL Apr s une tude approfondie des donn es il s est av r que cette proc dure avait effectivement une in fluence forte sur les taux d IO Cette analyse conduite par les experts du domaine a d une part permis de quantifier importance de l application de cette proc dure dif f rents niveaux d quipements et d autre part a pouss l int gration de cet l ment au mod le de pr diction 8 CHAPITRE 1 CADRE DE TRAVAIL Cet exemple montre bien qu actuellement les m thodes utilis es peuvent tre qua lifi es d ad hoc En pratique il s agit par exemple de partir d un export d une base de donn es d interruptions puis d effectuer un ensemble de statistiques et de requ tes manuelles pour confirmer ou non les hypoth ses prises La d couverte de nouveaux l ments contributeurs des taux d IO d pend donc presque exclusivement des intuitions formul es par l expert et du nombre d heures qu il peut consacrer leur v rification Probl matique du cas d application Pour faciliter cette t che d analyse du retour d exp rience on va diff rencier deux types de besoin le premier est celui du test d hypoth se qui doit permettre l expert de corro borer des propri t s sur les donn es
98. ciation 119 A 6 Mise jour du r seau bay sien partir des annotations Liste des tableaux 1 1 Exemple de matrice bool enne et de r gles d association extraites 16 2 1 Itemsets fr quents minfreq 2 extraits partir de la base bd 25 2 2 Exemples de r gles d association g n r es partir des itemsets fr quents extraits tableau 1 eau ne es ao ha a aa 25 2 3 R partition des achats sur un groupe de 1000 personnes 29 2 4 Exemple d un ensemble de r gles d association pouvant tre simplifi 37 2 6 Ensemble des r gles min max approximatives g n r es partir de bd 3 1 Exemple de base de donn es 74 3 2 R gles extraites sur bd pour minfreq 2etd 1 77 3 3 Exemples de r gles d association extraites sur Visit Asia partir de 4 2 R gles ayant la plus forte valeur d int r t vis vis de RBO1 Introduction Ce manuscrit pr sente nos travaux de recherche sur la d couverte de r gles d asso ciation pertinentes par l exploitation d un r seau bay sien Ces travaux sont appliqu s un cas d application industriel qui concerne l aide l analyse de donn es d inter ruptions op rationnelles dans l industrie a ronautique Contributions de la th se organisation du m moire Dans le cadre des travaux r alis s sur l aide l analyse des donn es d interr
99. ciation plus int ressantes Ceci tant la disponibilit et la mise jour de tels mod les peuvent constituer de nouveaux verrous Pour un expert dans un domaine d application par exemple les interruptions op rationnelles des avions construire mais aussi exploiter et faire voluer une mod lisation par r seau bay sien n est pas simple Cette difficult est aggrav e lorsqu il faut traiter de grands volumes de donn es issues de sources d informations souvent h t rog nes et impliquant de tr s nombreuses variables Nous avons donc tudi plus pr cis ment les interactions entre l expert d une part et le r seau bay sien qui mod lise une partie de sa connaissance d autre part La validation de ces travaux a t poursuivie dans FDBMO06 o nous avons tudi l application plus syst matique de notre approche sur des donn es simul es 18 CHAPITRE 1 CADRE DE TRAVAIL Chapitre 2 tat de l art sur la d couverte de r gles d associations pertinentes Ce chapitre dresse un tat de l art des approches pour la d couverte de connais sances par le biais de l extraction de r gles d association qui se r v lent pertinentes aux yeux d un expert Nous allons pr senter plusieurs axes de recherche relatifs cette probl matique Pour cela il appara t important de commencer par une pr sentation des r gles d association ainsi que des probl mes pos s par les phases d extraction et d analyse des r su
100. connaissance du domaine c est dire l tat des connaissances avant et apr s le d roulement du processus de d couverte de connaissances va d terminer l efficacit de notre approche Comme il nous est impossible d tablir une mesure pr cise des connaissances du domaine un instant t on se fiera plut t l impact potentiel que peuvent avoir les motifs d couverts d un point de vue op ra tionnel La question qu il faut se poser est donc la suivante les motifs d couverts sont ils d une quelconque utilit Ainsi si l expert reconna t qu une r gle ou qu un ensemble de r gles lui est b n fique dans son activit que ce soit en relation directe avec la probl matique initiale ou non alors on pourra dire que la connaissance du domaine est augment e On remarque la pr sence d une boucle sur une des entr es de notre processus Ce point sera videmment explicit dans ce chapitre Sur le principe il faut juste comprendre que notre approche est it rative on d marre le processus de d couverte de connaissances partir d un mod le initial le r seau bay sien RB_ 0 puis l issue de chaque it ration on obtient un nouveau mod le RB_i qui sera r utilis la place du mod le RB_ i 1 Le but de nos travaux est de montrer que cette boucle permet la fois de converger vers l laboration d un mod le augment des connaissances sur les d pendances du domaine mais aussi vers la d couv
101. crit re d int r t des r gles On va commencer par revenir sur la fr quence et la confiance puis on voquera diff rentes mesures d int r t qui ont t propos es dans la litt rature Nous qualifierons ces crit res d objectifs car ils s appuient uniquement sur les donn es pour valuer la qualit d une r gle ils ne prennent donc pas en compte le jugement de l expert ou les connaissances du domaine 2 2 2 Le cas particulier de la mesure de fr quence Dans un premier temps nous allons voir comment la mesure de fr quence est utilis e pour permettre une extraction efficace des itemsets Pour cela on d finit la propri t de fr quence d un itemset relativement un seuil y D finition 2 4 Itemset y fr quent Un itemset S est y fr quent sur bd s il satis fait la contrainte de fr quence minimale L ensemble des itemsets y fr quents sur bd est donn par Freq bd y X C Items Freq X bd gt y Cette d finition s tend naturellement aux r gles d association La propri t de fr quence d un itemset qui est la base de l efficacit des algo rithmes d extraction s exprime de la fa on suivante Proposition 2 1 La fr quence est une fonction d croissante par rapport l inclusion ensembliste Soit bd une base de donn es binaire S et T deux itemsets alors SCT Freq S bd gt Freq T bd De ce fait pour un itemset S donn et un seuil de fr quence y Si S est y fr qu
102. de 2 et que le nombre total de transactions est de 6 la fr quence absolue de cette r gle est de 2 6 soit 0 33 On obtient la confiance en divisant la fr quence de ABE par celle de AB Cela nous donne 2 4 soit 0 5 La mesure de fr quence nous donne une information importante sur les r gles Si la fr quence est tr s faible cela peut vouloir dire que la conjonction d v nements qu elle repr sente est le fruit du hasard D un autre c t les r gles ayant une fr quence tr s lev e ont de grandes chances d tre d j connues par les experts du domaine tudi Comme on va le voir la fr quence poss de une propri t int ressante que l on va exploiter pour pouvoir extraire efficacement les r gles La confiance d une r gle X Y mesure la fiabilit de l implication entre X et Y Plus grande est la confiance et plus grande sera la probabilit que Y apparaisse dans les m mes transactions que X Cependant cette mesure est manipuler avec beaucoup de pr cautions En effet la notion d association port e par la r gle n est pas synonyme de causalit Elle sugg re simplement une forte co occurence des l ments de la partie gauche de la r gle avec ceux de la partie droite Les sections suivantes vont pr senter un tat de l art orient par notre pro bl matique tout d abord sur les techniques d extraction d itemsets fr quents et la g n ration des r gles d association puis sur les diff
103. de l Information n 2 2003 St phane LALLICH et Olivier TEYTAUD valuation et validation de Vint r t des r gles d association Revue des Nouvelles Technologies de l Information RNTI E 1 193 217 2004 Ahmed METWALLY Divyakant AGRAWAL et Amr El ABBADI Using association rules for fraud detection in web advertising networks In VLDB 05 Proceedings of the 31st international conference on Very large data bases pages 169 180 VLDB Endowment 2005 Rosa MEo Giuseppe PSAILA et Stefano CERI A new sql like operator for mining association rules In VLDB 96 Proceedings of the 22th International Conference on Very Large Data Bases pages 122 133 San Francisco CA USA 1996 Morgan Kaufmann Publishers Inc Rosa MEo Giuseppe PSAILA et Stefano CERI An extension to sql for mining association rules Data Mining and Knowledge Discovery 2 2 195 224 1998 Heikki MANNILA et Hannu TOIVONEN Multiple uses of frequent sets and condensed representations In Proceedings of the 1996 KDD International Conference on Knowledge Discovery and Data Mining pages 189 194 1996 Heikki MANNILA et Hannu TOIVONEN Levelwise search and borders of theories in knowledge discovery volume 3 chapitre 1 pages 241 258 KluwerAcademic Publishers 1997 Heikki MANNILA Hannu TOIVONEN et A I VERKAMO Efficient al gorithms for discovering association rules In Proceedings of the AAAI Workshop on K
104. de la fouille de donn es et de l ing nierie des connaissances afin de faciliter la d couverte de facteurs contributeurs des taux d IO 3 et enfin les questions li es la probl matique de fouille de donn es que l on se propose d aborder Le premier axe qui occupe particuli rement les ing nieurs sp cialistes de la fia bilit op rationnelle porte sur l laboration d un mod le de pr diction de la fiabilit op rationnelle Pour une application au domaine de l a ronautique le lecteur se re portera aux travaux de HCC02 L approche adopt e par les auteurs est bas e sur la r solution avec l outil Supercab d velopp par Cab Innovation d un processus de Markov p riodique et born Les r sultats obtenus par le biais de ce mod le montrent qu il est possible de pr dire l impact des param tres de conception sur les perfor mances op rationnelles globales de l avion Cependant pour que ce mod le soit le plus pr cis possible il doit int grer un grand nombre de param tres issus des pra tiques de maintenance et de la sp cification des syst mes et des quipements L axe de recherche qui nous concerne plus directement est l identification des dif f rents facteurs qui contribuent aux taux d interruptions op rationnelles et donc directement aux performances op rationnelles partir de grandes bases de donn es d taillant les incidents survenus en op ration Actuellement il n existe p
105. e la pose d pose d un quipement a plus de chances d entra ner une interruption op rationnelle de longue dur e que la simple remise z ro de l quipement incrimin 4 3 Exp rimentations r alis es Notre d marche exp rimentale suit le processus de fouille que l on a pr sent pr c demment Pour rappel il se d compose en diff rentes tapes 1 D finition de la structure initiale du r seau bay sien 2 G n ration d un ensemble concis de r gles d association 3 Calcul de l int r t et des parties d s par es des r gles vis vis du r seau bay sien 4 Etude des r gles et annotation par l expert 5 Mise jour de la structure et des param tres du r seau bay sien partir des annotations Nous allons tudier le d roulement de ces diff rentes tapes sur les donn es d IO 4 8 1 D finition du r seau bay sien initial La premi re tape consiste donc mod liser en utilisant le formalisme propre aux r seaux bay siens les principales d pendances du domaine Afin de pr parer cette mod lisation initiale nous avons commenc par sensibiliser l expert des donn es IO aux r seaux bay siens Ainsi nous avons fait la d monstration de la circulation de l information dans le graphe pr sent le m canisme d inf rence partir d exemples concrets et expliqu la signification et la d finition des tables de probabilit s conditionnelles associ es aux n uds du graphe
106. eau 2 5 Ensemble minimal de r gles partir duquel on peut g n rer l ensemble des r gles d association 38 CHAPITRE 2 D COUVERTE DE R GLES PERTINENTES Num Libres Fermeture R gle min max exacte Fr quence 1 A ABC BC 4 2 B BC B C 5 3 D ABCD D ABC 2 4 E ABCE E ABC 2 TAB 2 5 Ensemble des r gles min max exactes obtenues partir de la base de donn es bd De m me on d finit la base des r gles min max approximatives compos e de r gles d association de confiance strictement inf rieure 1 D finition 2 18 Base min max approximative MinMaxAppror R Y X Y X FermAY Libres A ferm Y gt ferm X Cela revient dire que Y est un libre et X un ferm appartenant une classe d quivalence diff rente de celle de Y et telle que ferm Y gt X partir de cette base il est encore possible d effectuer une r duction sans perte d information i e en conservant la base Le but de cette r duction est de s lectionner parmi les r gles transitives celles qui ont la plus grande valeur de confiance i e les r gles les plus pr cises Une r gle min max approximative de la forme R Y X Y est dite transitive s il existe un itemset ferm fr quent X tel que ferm Y gt X D X Le tableau 2 6 nous montre un exemple de r gles min max approximatives obte nues partir des donn es de bd Num Libres Fermeture du sur ensemble R gle min max approx
107. en avant les principes ainsi que les principales contributions qui se rattachent l utilisation des r seaux bay siens sur des cas d applications r els En particulier on s int ressera aux limites que pr sentent leur utilisation lorsque les donn es envisag es sont complexes nombreuses variables elles m mes d compos es en de multiples valeurs Pr sentation des r seaux bay siens Un RB est un graphe causal auquel on associe une repr sentation probabiliste sous jacente La circulation de l information l int rieur de ce graphe ob it des r gles tr s pr cises en particulier la r gle de d s paration initialement propos e par J Pearl en 1988 Pea88 D finition 2 20 d s paration Soit un graphe orient G compos d un ensemble de n uds Soit X Y et Z diff rents n uds de G On dira que X et Y sont d s par s par Z on notera X Z Y si pour tous les chemins entre X et Y l une au moins des deux conditions suivantes est v rifi e Le chemin converge en un n ud W tel que W 4 Z et W n est pas une cause directe de Z Le chemin passe par Z et est soit divergent soit en s rie au n ud Z 48 CHAPITRE 2 D COUVERTE DE R GLES PERTINENTES Exemple Les affirmations suivantes illustrent la notion de d s paration et sont directement d duites de la figure 2 5 e A B D Le chemin A B D est en s rie en B A B D Le chemin A C D est convergent en C A gt C D
108. ent alors tout sous ensemble de S est aussi y fr quent Inversement si S n est pas y fr quent alors tout sur ensemble de S ne sera pas y fr quent Plus g n ralement on d finit les notions de contraintes monotones et anti monotone de la fa on suivante D finition 2 5 Contrainte monotone anti monotone Une contrainte Ca est anti monotone si et seulement si pour chaque itemset S si S ne satisfait pas Ca alors aucun de ses sur ensembles ne satisfait Ca R ciproquement Cm est monotone si et seulement si pour chaque S si S satisfait Cm alors chacun de ses sur ensembles satisfait Cm 2 2 EXPLOITER LES MESURES D INTERET OBJECTIVES 25 La contrainte de fr quence minimale est donc une contrainte anti monotone Pour comprendre plus concr tement l impact de cette propri t sur l extraction d itemsets fr quents prenons la base de donn es transactionnelles bd introduite pr c demment et l ensemble Items A B C D E associ Pour notre exemple de g n ration des itemsets fr quents nous prendrons un seuil de fr quence absolue mini male gal 2 Items Support Fr quence B t1 ta ta ts te 5 A t1 t2 ts te 4 A B C t1 t2 ts te 4 A B E t1 to 2 B D t1 ts 2 B C D t t5 2 TAB 2 1 Itemsets fr quents minfreq 2 extraits partir de la base bd R gles d association Fr quence Confiance B 0 5 A 0 4 A B C 0 4 A B E 0 2 B D 0 2 B C
109. entation graphique tr s proche Dans les deux cas une notation d orientation intervient Intuitivement on pourrait traduire cette orientation par la phrase Le fait d observer X m apporte une connaissance suppl mentaire sur Y Il y a donc un flot d information qui circule entre ces deux variables Ainsi partir d un RB et d une collection extraites sur le domaine du RB i e les variables du RB sont les m mes que les variables utilis es par les r gles d association on peut se poser la question de savoir si ce flot d information est repr sent de mani re identique dans le RB et dans les r gles d association Quelles sont pr cis ment les diff rences que l on peut constater Ces diff rences permettront alors de d identifier si les r gles sont non valides i e l information qu elles portent est contraire la d finition des d pendances du RB ou au contraire si elles peuvent tre potentiellement pertinentes i e d couverte d une r gle qui montre une association valide mais non prise en compte dans le RB Comme nous l avons voqu la circulation de l information dans le RB ob it la propri t de d s paration section 2 5 2 page 47 Pour rappel le test de d s paration entre X et Y conditionnellement Z o X Y et Z sont des sous ensembles disjoints de l ensemble des n uds associ s au graphe du RB s crit X Z Y X est d s par de Y par Z signifie alors que la pr
110. erte de r gles d association de plus en plus pertinentes aux yeux de l expert On notera aussi qu on suppose la base de donn es d entr e comme tant pr alable 64 CHAPITRE 3 LE TRAVAIL DE RECHERCHE RB_0 r seau ie A RB r seau bay sien initial Processus de bay sien d couverte de connaissances L collection de r gles d association pertinentes BD donn es Probl Expertise matique connaissances Fic 3 1 Activit Processus de d couverte de connaissances ment consolid e et pr par e pour les algorithmes d extraction de r gles d association Ces diff rents pr traitements ne constituant pas l objet de nos travaux ils ne seront pas d taill s ici Cette activit se d compose en plusieurs sous activit s l mentaires que nous d taillons dans les paragraphes suivants la premi re d entre elles consiste en l initiali sation de notre mod le RB 0 Enfin le cycle complet regroupant toutes les activit s sera pr sent la fin de cette section Une mod lisation des d pendances du domaine L approche que nous proposons a pour objectif la d couverte de r gles qui se r v lent int ressantes au regard des connaissances du domaine L tude sur l tat de l art a montr qu une partie des contributions actuelles visait introduire la subjectivit n cessaire la d couverte de ces r gles par le biais de contraintes sp cifi es par l utili
111. erte de r gles int ressantes Cette redondance que nous qualifions d intrins que peut tre abord e a poste riori par un post traitement sur l ensemble des r gles obtenues ce sujet on pourra consulter les contributions suivantes JS02 Une autre fa on d envisager le probl me consiste g n rer les r gles de telle sorte qu elles ne soient pas redondantes entre elles Pas00 Nous allons nous int resser plus particuli rement ce dernier type d approche en introduisant les repr sentations condens es 2 3 2 Repr sentations condens es des itemsets fr quents Le concept des repr sentations condens es a t introduit en 1996 MT96 dans le cadre plus g n ral de la fouille de donn es On a voqu dans la section pr c dente l int r t que pouvaient pr senter ces types de repr sentations pour le calcul des itemsets fr quents et des r gles d association Elles peuvent tre extraites plus efficacement que l ensemble des itemsets fr quents tout en permettant de les r g n rer pas de perte d information Elles contiennent la m me information que les collections d itemsets fr quents tout en tant plus concises Il existe plusieurs types de repr sentations condens es BBROO Ici nous d taillons les repr sentations utilisant les itemsets maximaux fr quents puis plus particuli rement les repr sentations utilisant les ferm s les libres et les 6 libres ainsi que les diff
112. es r sultats mettent en avant les points suivants La d couverte de deux r gles int ressantes a entra n une modification du RB et a permis d inverser l orientation d un arc du r seau partir des r gles tudi es il n a pas paru possible de retrouver le lien de parent entre Bronchitis et Dyspnea modification n 1 De plus comme nous nous int ressons uniquement la pr sence des v nements e g le fait d tre fumeur et non leur absence e g le fait d tre non fumeur les r gles pr sent es ne permettent pas de couvrir la modification n 3 r alis e sur la CPT de Smoking Le principal r sultat a retenir ici est bien la d couverte partir de l laboration d un mod le m me incomplet des d pendances du domaine et son exploitation via la mesure d int r t subjective de motifs r ellement pertinents On peut noter que dans les exp riences que nous avons men es aucune des mesures objectives utilis es ne permettait de retrouver facilement ces r gles titre de comparaison nous avons essay une approche similaire mais cette fois en utilisant un algorithme de type APRIORI avec les m mes contraintes et sur le m me jeu de donn es Au total 115 r gles d association sont g n r es Parmi cette collection trois r gles mentionnent diff rentes variantes de la relation qui associe VisitAsia avec XRay et Dyspnea La principale diff rence entre notre approche et
113. exploitation des r sultats consiste interpr ter et analyser les motifs ou mod les extraits lors de l tape 2 Il s agit de faire correspondre les r sultats obtenus avec les objectifs initialement fix s par l utilisateur du syst me donc de r interpr ter les r sultats de la fouille par rapport la probl matique afin d en tirer une nouvelle connaissance On peut aussi ajouter cette tape la consolidation des d couvertes et leur ventuelle int gration aux mod les utilis s par l expert Le processus ECD est it ratif de nombreux cycles doivent tre r alis s sur les tapes 1 et 2 avant de pouvoir obtenir des r sultats exploitables dans la phase 3 L information extraite par les algorithmes de fouille pourra 1 soit tre organis e par un expert du domaine sous forme de mod le de classification ou de pr diction 2 soit tre utilis e pour pr ciser la d finition de mod les existants 3 ou encore fournir une repr sentation synth tique des donn es tudi es Dans les auteurs d fi nissent les algorithmes de fouille de donn es de la mani re suivante un algorithme de fouille de donn es est une proc dure bien d finie qui prend des donn es en entr e et qui produit une sortie sous la forme de mod les ou de motifs L expression bien d finie indique ici que la proc dure de fouille de donn es doit se terminer en un temps raisonnable sur une chelle humaine 1 4 Apprendre et acqu
114. exploiter le retour d exp rience sur des programmes pass s pour pr dire le taux d interruptions op rationnelles d un avion en phase de conception Par retour d ex p rience on entend ici aussi bien l ensemble des donn es produites par les avions en op ration d tails des incidents caract ristiques de l avion heures de vol etc que l ensemble des informations dont disposent les ing nieurs sp cialistes des taux d in terruptions op rationnelles L objectif tant de d velopper le mod le de pr diction le plus pr cis possible 1 2 Pratiques actuelles sur les donn es d interruptions op rationnelles Il faut bien faire la distinction entre les diff rentes probl matiques qui inter viennent autour de nos travaux de recherche 1 d une part la probl matique des ing nieurs a ronautiques pour le probl me d crit c est en quelque sorte le travail quotidien des experts charg s de l tude et de la pr diction des IO 2 d autre part la contribution que l on va apporter au cas d application c est a 6 CHAPITRE 1 CADRE DE TRAVAIL I PA F Retour Expert moge 5 Expert rae exp rience 16 pr diction quip quipemen l l l l l Est analys l l l l D finit l Est utiis Fic 1 2 Diagramme de s quence simplifi pr sentant la probl matique du cas d ap plication dire la mise en uvre d un ensemble d outils et de m thodes issus
115. ft A B DCE 0 9375 Ce r sultat peut s interpr ter comme une faible corr lation n gative entre les acheteurs des produits et B Le coefficient de corr lation de Pearson la J Mesure ou encore l intensit d im plication BKGG04 sont d autres exemples de mesures objectives pouvant tre cal cul es sur les r gles d association Chacune d entre elles permet d valuer un crit re statistique bien pr cis qui pourra avoir un int r t ou non aux yeux de l expert Le lecteur d sirant une description plus d taill e de ces mesures pourra se r f rer aux travaux de synth ses r alis s sur le sujet en particulier la th se de Az 03 ou encore les travaux de LT04 GCB 04 De plus face au grand nombre de mesures propos es et la multitude de r gles candidates qu il faut analyser un autre probl me merge celui du choix des mesures d int r ts les plus adapt es un cas d application donn Autrement dit il devient important de d finir des crit res permettant d valuer ces mesures Ainsi pr sente une approche multicrit res pour l aide la d cision dans le choix des me sures utiliser propose une m thode de validation qui utilise les outils de la th orie de l apprentissage statistique notamment la VC dimension L objectif de cette derni re contribution est de permettre la construction de bornes uniformes non asymptotiques pour toutes les r gles et toutes les mesures simultan men
116. he d couvrir ou ne pas d couvrir Cependant l utilisation de chacune de ces m thodes se fait de mani re ad hoc ce qui rend d autant plus difficile leur r utilisation sur de nouveaux jeux de donn es De plus on cr e un biais relativement important quant l espace qui va tre lagu ce qui r duit l int r t d une approche fouille de donn es non supervis e Enfin on se rend compte qu il manque une r flexion globale sur la mod lisation et la prise en compte des comptes des connaissances du domaine pour faciliter cette tape de d couverte Les approches pr sent es PT98 JS04 sont un premier pas vers une utilisation plus syst matique des connaissances de l expert dans le but de faciliter la d couverte de r gles inattendues et donc potentiellement int ressantes Il appara t important de r fl chir un processus d extraction qui prendrait en compte les connaissances du domaine et permettrait de visualiser les r gles d associa tion qui apparaissent inattendues vis vis de ce qui t mod lis Cette approche doit pouvoir englober aussi bien le traitement des taxonomies ou des implications logiques au sein des donn es que des connaissances plus fines de l expert 58 CHAPITRE 2 DECOUVERTE DE REGLES PERTINENTES 2 7 Discussion sur l tat de l art Cet tat de l art fait appara tre une volution des approches pour la d couverte de r gles d association Nous avons commenc
117. hr75 impl ment dans la biblioth que Bayesian Network Tools in Javd a t utilis pour r aliser des calculs d inf rence approch s Ce proces sus a dur approximativement 20 heures pour traiter l ensemble des 4954 r gles soit un temps moyen de 14 55 secondes par r gle Le temps de calcul peut para tre long mais il faut savoir qu au moment ot les calculs ont t r alis s aucune optimisation n tait utilis e En particulier il n y a pas de syst me de cache qui permettrait d conomiser de nombreux calculs d inf rence Prenons l exemple de deux r gles 1 A a B b X x et 2 A a B b C c X x Y y Notre calcul d int r t implique que nous calculions pour ces deux r gles la distribution de probabilit p X sachant la partie droite de la r gle Maintenant admettons que pour la r gle 2 la variable C c n intervienne pas dans le calcul de p X alors on va effectuer deux fois le m me calcul d inf rence Le tableau 4 2 montre les 10 premi res r gles class es selon la valeur de leur mesure d int r t par rapport au RB initial ou RBO1 Ces r sultats font intervenir des codes et des sigles propres au domaine des IO ce qui les rend difficile interpr ter Nous allons expliciter quelques r gles pour faciliter la compr hension g n rale des r sultats pr sent s dans ce chapitre Par exemple la r gle zone E last _action swap CS DY swap peut se lire de la fa on suiv
118. ifier prenons l hypoth se o toutes les variables Y et X sont binaires L expert devra alors estimer 2 valeurs cela devient rapidement irr aliste d s que n est grand ce qui est le cas pour de nombreux cas d applications r els L id e est alors de simplifier cette probabilit conditionnelle en posant les hypoth ses suivantes On peut calculer facilement la probabilit suivante p p y 1 T2 Zi n Xi cause Y est ind pendant des autres variables X Le mod le OU bruit nous dit alors que Si un des X est vrai alors Y est presque toujours vrai avec la probabilit p Si plusieurs X sont vrais alors la probabilit que Y soit vrai est donn e par pylX 1 J 0 2 2 2 ilXiEXp 2 5 PRENDRE EN COMPTE LA CONNAISSANCE DU DOMAINE 53 certain 100 probable 85 attendu 75 50 50 50 incertain 25 improbable 15 impossible 0 Fic 2 6 Echelle de probabilit o est l ensemble des X vrais Ce mod le propos initialement par J Pearl Pea88 a t tendu au cas o Y peut tre vrai sans qu une seule des causes soit vraie leaky noisy OR gate et aux variables multi valu es generalized noisy OR gate Cette mod lisation simplifi e des probabilit s a t utilis e avec succ s dans des domaines tels que le diagnostic m dical PPMH94 ODW00 ou le diagnostic de pannes BRM02 Enfin le dernier type de probl me li l ing nierie des conn
119. ils qu il a d velopp s pour estimer la probabilit d IO de cet quipement embarqu sur un avion de type A3Y0 1 3 2 Connaissance utile Les motifs extraits vont rev tir des caract res diff rents aux yeux de l expert On s int resse plus particuli rement la d couverte de motifs que l on qualifiera 1 3 D COUVERTE DE CONNAISSANCES UTILES 11 d utile Cette utilit introduit la notion d une plus value engendr e par la d cou verte de ce motif par rapport la compr hension initiale que l on a sur le domaine On peut la mesurer en fonction de la facult que va avoir ce motif tre exploit c est dire tre r interpr t dans le formalisme de l expert et int gr aux mod les existants On peut aussi valuer l utilit en fonction du nombre ou de l importance des actions concern es par la d couverte Une connaissance se r v le utile par rapport un contexte donn Le caract re d utilit est donc intrins quement subjectif Dans notre contexte une connaissance est jug e utile si potentiellement elle permet ou facilite la d couverte de nouveaux facteurs contribuant aux taux d interruptions op rationnelles Si on reprend l exemple utilis pr c demment concernant l impact de l application d une proc dure de maintenance particuli re sur la fr quence des 10 on voit bien qu il s agit d une connaissance utile ce facteur a t int gr au mod le de pr
120. int ressants Ces annotations sont ensuite interpr t es visuellement sur l ensemble des r gles tudi es La deuxi me fonction de ces annotations est d alimenter l tape qui consiste faire voluer le r seau bay sien en fonction des d couvertes r alis es par l expert Cette application a t d velopp e en partenariat avec un tudiant de l Universit Paul Sabatier Toulouse Mehdi Rabah Elle est pr sent e dans l annexe A On utilise ici le terme de motif afin de distinguer la r gle qui constitue annotation et la r gle d association en elle m me 3 2 PROCESSUS DE D COUVERTE DE CONNAISSANCES KARD 69 volution du mod le des d pendances du domaine Cette activit figure 3 6 prend en entr e la collection d annotation issue de la phase d analyse des r gles ainsi que le r seau bay sien RB RB i Mettre a jour le mod le des d pendances du domaine RB_ i 1 r seau bay sien mis a jour A collection d annotations Expert Expert du domaine RB Fic 3 6 Activit Mettre jour le r seau bay sien L objectif de cette phase est de d cider si l on va int grer ou non les diff rentes connaissances port es par les annotations Ainsi la d finition d une nouvelle it ration de notre mod le va n cessiter la collaboration d un expert du domaine et d un expert sur les RB Pour cela un deuxi me composant de notre application t d velopp
121. ion pr sente une information fortuite elle d crit en fait la co n cidence statistique de certains attributs mais l expert peut affirmer qu elle n a pas de valeur en tant que nouvelle connaissance NP Ces annotations d crivent une relation valide mais non pertinente par rap port au contexte dans lequel se situe l expert I L annotation est int ressante C est dire qu elle surprend l expert du do maine et va demander une analyse approfondie e g une nouvelle it ration du processus voire un retour sur la collecte et la pr paration des donn es par exemple en introduisant une nouvelle variable Exemple Afin d illustrer ces diff rentes cat gories d annotations consid rons les r gles 1 4 du tableau B 4 Num R gle d association 1 Smoking XRay Bronchitis 2 Dyspnea Tuberculosis TbOrCa 3 Visit Asia TbOrCa Tuberculosis 4 Smoking Bronchitis Visit Asia TAB 3 4 Exemples de r gles d association fictives sur Visit Asia Si l on tudie ces r gles au regard des faits pr c demment voqu s sur le domaine Visit Asia voir page 59 on peut formuler les remarques suivantes Un examen aux rayons X r v lant des r sultats anormaux ne permet pas de conclure avec certitude sur le fait que le patient ait une bronchite fait n 4 ou 86 CHAPITRE 3 LE TRAVAIL DE RECHERCHE non Il s agit donc d un motif non valide On sait fait n 3 qu un patie
122. ipement et donc du temps additionnel n cessaire pour y acc der sur les taux d interruptions op rationnelles de l appareil Une IO peut avoir des causes diverses Certaines sont difficilement pr visibles ou vitables comme des conditions m t orologiques extr mes par exemple d autres sont inh rentes au fonctionnement des compagnies a riennes disponibilit des pi ces et ou des quipes de maintenance d cisions prises par le pilote d autres enfin sont directement imputables l avionneur choix technologiques fiabilit des quipements utilis s positionnement de certains quipements pour une maintenance plus rapide redondance des syst mes embarqu s etc Comme on peut s en rendre compte il existe de nombreux param tres qui rendent le domaine de l analyse des interruptions op rationnelles complexe L avionneur s int resse videmment la part des IO qui lui sont imput es Ainsi il doit pouvoir anticiper ces v nements en donnant aux compagnies a riennes une estimation des performances op rationnelles de leurs appareils Lors du lancement de nouveaux projets avions les ing nieurs doivent fournir d s la phase de conception une pr diction la plus r aliste possible de la fr quence des interruptions op rationnelles lors de la future exploitation commerciale des avions Dans la pratique une part des IO est directement li e aux choix de conception De ce fait les objectifs IO vont initier guide
123. ir les erreurs d estimation de fr quence apport es par cette repr sentation On sait grace la 6 fermeture que Freq AB Freq A 1 2 on peut donc estimer la confiance de la r gle AB CE qui sera d au moins TO soit Conf AB CE gt 0 5 En r alit la confiance de cette r gle est gale 1 Dans ce cas on a donc une erreur d estimation sur la borne inf rieure de l ordre de 50 Ce r sultat n est pas tonnant car dans notre exemple 6 ne respecte pas les crit res que nous avons d finis il ne faut donc pas perdre de vue qu il s agit la d un exemple didactique qui vise montrer qu il est possible d estimer la fr quence des diff rentes r gles partir de l ensemble des itemsets 6 libre et de leur 6 fermeture En pratique lorsque 6 est plus faible par rapport au seuil de fr quence utilis l erreur d estimation est elle aussi plus faible Autre exemple de calcul on sait que Freq BC gt Freq A 1 2 et que Freq BCE gt 1 on peut donc estimer Conf BC E gt 0 5 3 5 EXPLOITATION D UN R SEAU BAYESIEN 79 On a vu qu il tait possible de g n rer l ensemble des r gles 6 approx partir des r gles de 6 gen On utilise pour cela une approximation sur les fr quences des itemsets qui composent ces r gles partir des informations de la 6 fermeture et de la fr quence des itemsets 6 libres En pratique on veillera ce que 6 soit tr s inf rieur minfreq card Items
124. isitAsia en direction du n ud Tuber culosis Si l on s int resse la table de probabilit conditionnelle ou CPT du n ud Tuberculosis on voit qu elle d finit explicitement et quantitativement l influence de la valeur de VisitAsia Visit ou No Visit sur les valeurs que peut prendre Tuberculosis savoir Present ou Absent Absent os 099 Fic 3 9 Exemple de repr sentation de l influence d une variable dans le RB Visit Asia On peut traduire en langage naturel la relation entre ces deux variables de la fa on suivante Si le patient a voyag en Asie alors la probabilit pour qu il soit atteint de tuberculose sera plus lev e i e que s il n avait pas effectu ce voyage 3 4 G n ration d un ensemble concis de r gles d associa tion partir des libres 0 libres Cette section pr sente une tude de diff rentes collection de r gles non redon dantes On va pour cela tudier les propri t s de repr sentations qui permettent de 74 CHAPITRE 3 LE TRAVAIL DE RECHERCHE g n rer un ensemble de r gles valides mais dont la confiance est approximative i e elle ne peut tre calcul e avec certitude L objectif de cette section est d apporter une meilleure compr hension des propri t s de ces ensembles de r gles Nous pro posons aussi quelques pistes pour l extraction de collections de r gles d association 0 approximatives et 6 g n rale notamment lorsqu une appro
125. itifs La solution actuellement apport e est uni quement visuelle Il faut donc r fl chir au filtrage de ces motifs autrement que par la mesure d int r t Un deuxi me probl me prendre en compte dans des travaux futurs est l tude de l impact potentiel que peut avoir la modification de la structure ou des param tres du RB sur l ensemble des r gles Il s agit en quelque sorte de pouvoir contr ler et mesurer les effets de bord provoqu s par la mise jour du RB Il peut par exemple tre int ressant de pr senter a l expert uniquement les r gles qui ont t impact es par la derni re modification du mod le Perspectives Ces travaux ont ouvert une perspective int ressante quant l tude des liens entre r seau bay sien et r gles d association Le premier axe consisterait travailler sur un approfondissement des liens entre r seaux bay siens et r gles d association On peut par exemple r fl chir l utilisation des r gles d association en compl ment de l apprentissage de la structure et des param tres d un r seau bay sien Le but serait de proposer des modifications du r seau partir des r gles et des annotations Plus g n ralement nous avons constat les limites des approches algorithmiques pures lorsqu elles sont appliqu es des cas concrets Le manque d approche visant concilier mod le de connaissance formel et r gles d association appara t distincte ment dans l
126. l des itemsets libres ce qui n est pas toujours possible selon que les donn es sont ou non fortement corr l es et que l on souhaite extraire des r gles avec une fr quence relativement faible tude des r gles d association g n r es partir des itemsets 6 libres et de la 6 fermeture Il est possible de g n raliser encore plus la base pr c dente en utilisant cette fois les itemsets 6 libres Si l on regarde les r sultats pr c dents on constate que les r gles 5 et 6 sont redondantes par rapport 1 et 2 l erreur de confiance pr s Il en est de m me pour les r gles 9 et 10 par rapport la r gle 7 Enfin les r gle 1 2 3 sont moins g n rales que la r gle 8 toujours l erreur de confiance pr s qui elle m me est moins g n rale que la r gle 7 En conclusion si l on tol re une erreur sur la confiance des r gles g n r es on peut repr senter l ensemble des r gles de la table 3 2 uniquement par la r gle 7 Le corps de la r gle 7 est en fait le seul itemset 2 fr quent 1 libre calcul sur bd Cela nous permet de d finir la base des r gles approximatives les plus g n rales sur bd 6 gen R X ferms X X X Libres Exemple Comme on vient de le voir une seule r gle constitue cette base il s agit de la r gle R A B 1 CE 1 Nous allons maintenant tudier la possibilit de g n rer les r gles de 6 approx partir de cette r gle et nous allons vo
127. le domaine 3 7 2 Pr paration du cas d application A partir de RB_ ref on produit un jeu de donn es compos de 10000 enregistre ments Ces donn es sont consid r es comme tant les donn es du domaine Visit Asia Comme nous cherchons extraire des r gles d association on se focalise uniquement sur la pr sence des v nements au sein des donn es Exemple Si l enregistrement est compos des attributs suivants Smoker True VisitAsia False et Dyspnea Absent alors on le codera uniquement par Smoker On modifie ensuite RB_ ref le RB qui a servi a g n rer les donn es de telle sorte qu on retrouve les diff rents cas de figures associ s l tude d un RB Les mo difications apport es sont les suivantes 1 Le n ud VisitAsia n est plus directement connect au n ud Tuberculosis 2 Du fait de la modification n 1 la table de probabilit s conditionnelles de Tu berculosis est modifi e de telle sorte qu on a maintenant p Tuberculosis Present 0 03 3 Les distributions de probabilit s associ es au n ud Cancer ont t modifi es afin que les valeurs de la variable Smoking n influent pas sur Cancer Plus pr cis ment RB_ ref d finissait p Cancer Present Smoking Smoker 0 1 p Cancer Present Smoking NonSmoker 0 01 RB_ 0 d finit maintenant 0 1 0 1 p Cancer Present Smoking Smoker p Cancer Present Smoking NonSmoker 4 La variable B
128. lement on pourra dire qu tant donn un itemset S et X X1 Xo Xn sa 6 fermeture alors la fr quence de X sera Freq S max sx lt Freq X lt Freq S X sxe i 1 On v rifiera facilement que Freq S max sx lt Freq S 5 sx De plus on en d duit que pour obtenir des r sultats coh rents il faut que pour tout ferms S X f soit au moins strictement inf rieur Freq S card X En effet dans le cas contraire cela signifierait que la fermeture calcul e aurait ventuellement une fr quence nulle ou n gative i e il ne serait pas support par les donn es de bd Ainsi dans notre exemple pr c dent la fr quence de la 1 fermeture de A peut tre gale 0 tant donn que Freq A 3 6 1 et card BCE 3 en pratique ce n est pas le cas tude des r gles d association form es partir des itemsets libres et de la 0 fermeture L utilit de la 6 fermeture a t d montr e dans le cadre de l extraction de re pr sentations condens es d itemsets fr quents lorsque l on travaille sur des donn es fortement corr l es des seuils de fr quence relativement bas BBROO Maintenant qu en est il d une collection de r gles utilisant les itemsets 0 ferm s Soit minfreq un seuil de fr quence minimum et 6 un entier positif tels que 6 lt minfreq card Items On envisage alors l ensemble de r gles d association tel que R X gt Y X C Items
129. libre D finition 2 10 libre Un itemset est libre s il n est pas inclus dans la fermeture d un de ces sous ensembles stricts On introduit maintenant le concept de classe d quivalence pour la fermeture D finition 2 11 classe d quivalence BTP O02 Deux itemsets S et T sont qui valents dans la base de donn es bd s ils ont m me la fermeture dans bd Pour mieux appr hender la notion de classe d quivalence d itemsets ferm s et d itemsets libres on peut se reporter la figure Le treillis repr sent dans cette 34 CHAPITRE 2 D COUVERTE DE R GLES PERTINENTES figure a t instanci partir des donn es pr sent es dans le tableau 2 1 Les itemsets en gras repr sentent les itemsets ferm s ils sont les itemsets maximaux des classes d quivalence Les itemsets en italique sont les itemsets libres ils sont les itemsets minimaux des classes d quivalence Les diff rentes classes d quivalences relatives la fermeture sont entour es Une premi re lecture de ce treillis permet de se rendre compte qu il nous suffit de conna tre l ensemble des itemsets libres et leurs fermetures pour qu il soit possible de g n rer l ensemble des itemsets fr quents C est pourquoi on parle de repr sentations condens es il n y a pas de perte d information sur les itemsets et leur fr quence mais il y a une possible r duction de nombre de motifs prendre en compte ABCDE 1 ABCD 2 ABCE 1 ABDE
130. ltats Pour chaque grande cat gorie de probl mes nous d taillons les contributions issues de la litt rature Cela nous m nera en particulier d crire l exploitation de mod les de connaissance tels que les r seaux bay siens dans le cadre de la d couverte de r gles d association r ellement int ressantes 2 1 Introduction la probl matique 2 1 1 Philosophie de l extraction de r gles d association Les techniques d extraction de r gles d association ont t introduites pour la premi re fois en 1993 dans le but de calculer des motifs fr quents partir de donn es dites transactionnelles Historiquement on cherchait mettre en vidence des comportements valides et inattendus d acheteurs partir de grandes bases de donn es de transactions Ces comportements sont pr sent s sous la forme de r gles d association Plus g n ralement les r gles d association sont utilis es lorsque l on veut d couvrir des ensembles de couples attribut valeur appel s itemsets qui apparaissent lEn anglais la d nomination fr quemment employ e est market basket data 19 20 CHAPITRE 2 D COUVERTE DE R GLES PERTINENTES fr quemment ensemble au sein d un m me jeu de donn es et sont li s entre eux par une relation d association L observation des v nements de la partie gauche de la r gle est souvent associ e l observation des v nements de la partie droite Une r
131. m thodes dites de propagation des messages tendues par des algorithmes de coupe ou de conditionnement et les m thodes utilisant des groupements de n uds am lior es par la suite par JJJ96 Les premi res proposent un m canisme de calcul utilisant la propagation de messages le long des arcs d un graphe sans cycle les se condes op rent d abord des modifications sur le graphe pour obtenir une structure secondaire d arbre de jonction dans laquelle chaque n ud repr sente une clique du r seau bay sien permettant d appliquer un algorithme simplifi de propagation des messages Les algorithmes de calcul d inf rence approch e se divisent en deux branches d une part les algorithmes qui utilisent des m thodes exactes mais op rent seule ment sur une partie du graphe et d autre part les algorithmes utilisant des m thodes stochastiques simulations Dans la premi re cat gorie on retrouvera les contributions de qui exploitent le fait que certaines d pendances sont faibles c est dire que qualitativement il existe un arc entre des n uds X et Y parce que ces variables ne sont pas exacte ment ind pendantes l une de l autre mais que quantitativement cette d pendance est insignifiante autrement dit X et Y se comportent presque comme si elles taient ind pendantes L id e de cet algorithme est donc d liminer ce type d arc afin de sim plifier les calculs de propagation des messages tout en e
132. mani re ad hoc en utilisant 2 5 PRENDRE EN COMPTE LA CONNAISSANCE DU DOMAINE 45 des formalismes divers On s int resse souvent un aspect pr cis de ce que recherche l expert ce qui peut avoir pour effet de trop laguer l espace de recherche ou au contraire de ne pas assez le r duire En fait par le biais de ces contraintes l utilisateur du syst me cherche mod liser ce qu il sait de telle sorte que les connaissances qu il exprime ne soient pas pr sentes dans les r gles d association qu il va examiner Cette approche s inscrit donc dans une d marche d ing nierie dans la connaissance au sens o l utilisateur va devoir exprimer ses connaissances afin qu elles puissent tre traduites sous formes de contraintes sur les r gles d associations Il s agit en quelque sorte d aborder le filtrage des r gles attendues ou connues de mani re plus syst matique Dans cette section nous allons examiner les principales contributions qui se rap prochent de cette d marche D couverte de motifs inattendus Les auteurs de l approche Small is beautiful partent du constat suivant les techniques de fouille de donn es traditionnelles n exploitent pas de mani re syst matique les connaissances a priori de l expert Lorsqu on dispose potentiellement de nombreux experts et analystes qui ont des intuitions sur la probl matique tudi e intuitions bas es sur leur exp rience il peut sembler regrettable de
133. manquantes champs non renseign s La quantit de bruit est cependant difficile estimer Le nombre d enregistrements incomplets tant faible nous avons simplement d cid de retirer ces donn es du jeu de d part L expert souhaitant concentrer ses recherches sur une famille de produit homo g ne nous avons limit la base de donn es 11819 enregistrements correspondant au programme avion s lectionn par l expert 98 CHAPITRE 4 APPLICATION PRATIQUE 4 2 2 Pr traitements Les pr traitements effectuer sur ces donn es sont de trois ordres Enrichissement d un attribut c est dire cr er un ou plusieurs attributs qui vont enrichir ou remplacer l attribut en question par exemple en croisant les donn es avec d autres tables Modification simplification des valeurs prises selon des r gles pr cis es par l expert Discr tisation partir des attributs cat goriques ou num riques Pour effectuer ces pr traitements nous avons utilis uniquement les requ tes SQL Cela nous a permis d automatiser les traitement pour la fois convertir certains champs de la base initiale et pour croiser les donn es avec d autres tables Cette approche a l avantage d tre relativement flexible dans le cas o on voudrait modifier les donn es utilis es Exemple Les commandes SQL ci dessous nous permettent d appliquer des r gles d finies par l expert pour la pr paration des diff rents
134. motif connu non valide non pertinent ou pertinent Ces motifs sont interpr t s par le moteur d affichage des r gles apportant ainsi une aide suppl mentaire l expert dans la reconnaissance des r gles et dans leur analyse Deuxi me int r t faciliter la phase de mise jour du mod le La collection d annotations est ainsi envoy e aux experts charg s de faire voluer le r seau bay sien en fonction des d couvertes Si l analyse des r gles extraites r v lent de nombreux motifs connus ces motifs doivent tre pris en compte dans la structure du r seau afin de faciliter l analyse des r gles pour les it rations ult rieures filtrage des motifs connus Si l tape d analyse fait appara tre des motifs pertinents il faut alors se poser la question suivante s agit il d un dysfonctionnement du syst me D une erreur dans les donn es tudi es ou d une connaissance particuli re que l on souhaite alors int grer au mod le existant Dans nos travaux nous avons essay de mettre en avant la constitution d un cycle vertueux qui tend converger la fois vers un mod le de plus en plus riche des d pendances du domaine mais aussi vers la d couverte de r gles r ellement pertinentes pour l expert du domaine Une premi re validation exp rimentale a t r alis e sur le cas Visit Asia une deuxi me sur le cas d application industriel Cas d application industriel Nous avons appliqu notre pro
135. n Principles and Practice of Knowledge Discovery in Databases pages 75 85 2000 Jean Francois BOULICAUT Artur ByYKOWSKI et Christophe RIGOTTI Free sets A condensed representation of boolean data for the approxi mation of frequency queries Data Min Knowl Discov 7 1 5 22 2003 R Barco R GUERRERO G HYLANDER L NIELSEN M PARTA NEN et S PATEL Automated troubleshooting of mobile networks using bayesian networks In IASTED International Conference on Communication Systems and Networks Malaga Spain 2002 Tom BRIJS Bart GOETHALS Gilbert SWINNEN Koen VANHOOF et Geert WETS A data mining framework for optimal product selec tion in retail supermarket data the generalized PROFSET model In R RAMAKRISHNAN S STOLFO R BAYARDO et I PARSA diteurs Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining August 20 23 2000 Boston MA USA ACM 2000 pages 300 304 2000 Julien BLANCHARD Pascale KUNTZ Fabrice GUILLET et R gis GRAS Mesure de qualit des r gles d association par l intensit d implication entropique Revue Nationale des Technologies de l Information E 1 33 44 2004 BIBLIOGRAPHIE 123 BKM99 BMM03 BMUT97 BP98 BRM02 BTP 00 BTP 02 CB02 CCK 00 CDLS03 CGK 02 Jean Francois BOULICAUT Mika KLEMETTINEN et Heikki MANNILA Modeling kdd processes within the ind
136. n associe une distribution de probabilit conditionnelle P A Par A o Par A A V 4 V Ai E repr sente les parents du n ud A Pour une discussion d taill e sur les r seaux bay siens le lecteur pourra consulter Pea88l NWL 04 Soit R X Y une r gle d association ot X et Y sont des itemsets tels que X Y C Items Y 0 et XAY La fr quence d un itemset X dans bd not e Poa X est l ensemble des lignes de bd qui contiennent X par rapport la taille de bd Cette fr quence d note sous r serve que la taille de bd soit suffisamment grande la probabilit que tous les items X de l itemset X C Items soient observ s dans les donn es de bd i e ils prennent la valeur vrai De m me on d finit Pal R X Y pal X UY la probabilit qu une r gle d association soit observ e sur les donn es Il s en suit que la confiance d une r gle R exprim e en termes de probabilit s s crit de la facon suivante Poa R Poal X confpg R X gt Y Ainsi tant donn une base de donn e bd et un r seau bay sien RB nous avons d fini une mesure subjective de l int r t d une r gle d association vis vis d un r seau bay sien Cette mesure est inspir e de Elle se base sur le calcul de la diff rence entre la confiance de la r gle estim e partir des donn es et la probabilit inf r e par le r seau bay sien d observer les attributs de la par
137. n seul attribut int ressant Ces contraintes sont alors appliqu es par un algorithme de type APRIORI et illus tr es sur un jeu de donn es exemple tir du r pertoire UCI Machine Learning AAO7 Les r sultats pr sent s dans sont prometteurs mais restent cependant peu d taill s Un premier RB est mod lis par une personne non experte L algorithme cal cule ensuite les ensembles d attributs e int ressants Ces d couvertes sont alors utili s es pour apporter des modifications manuelles au RB structure et ou param tres Une modification est valid e si le score du RB modifi est sup rieur au score du RB pr c dent Mais ce score est purement objectif et ne fait que mesurer la probabilit attendue d avoir les donn es a partir de la structure il ne donne aucune indication sur une meilleure ad quation du r seau par rapport aux connaissances expertes du domaine En l absence de cas d application concret les auteurs semblent privil gier l am lioration des temps de calculs de leur approche JSO5 2 6 1 Conclusion On a vu qu il existait un ensemble d approches visant liminer les r gles inint res santes du point de vue de l expert En effet une grande partie des r gles d association g n r es contiennent des informations d j connues pr visibles inint ressantes ou redondantes Ces techniques ont t mises en place pour permettre l utilisateur de formuler explicitement ce qu il cherc
138. nc compar e celle que l on peut inf rer du r seau bay sien RB d fini pour l it ration en cours Pour cela on d finit la fonction suivante PER Th 0 0 RBi LR Ti g Trb D Sep o est le seuil d int r t subjectif par rapport au r seau bay sien RB Elle retourne une nouvelle collection telle que R CR est l ensemble de r gles d association qui satisfont la fois les crit res objectifs et le crit re subjectif Th q Tpq est l ensemble des mesures objectives associ es R Tib est l ensemble des mesures subjectives associ es 7 partir de RB D sep est l ensemble des d s parations calcul es pour chaque r gle partir de RB La fonction de calcul d int r t subjectif vis vis du r seau bay sien ainsi que le calcul de ce que nous appelons les parties d s par es d une r gle font l objet de la section 3 5 1 L activit li e cette fonction est repr sent e dans la figure 3 4 L lt R _bd 0 0 gt L lt R l_bd l_ rb D sep gt collection de r gles et calculs d int r ts associ s Exploiter le r seau RB bay sien Int r t minimal FIG 3 4 Activit Exploiter le r seau bay sien 68 CHAPITRE 3 LE TRAVAIL DE RECHERCHE Importance du r le de l expert Comme nous l avons pr cis l expert est situ au centre de notre processus Ainsi nous avons t amen s d
139. nd pendance de deux n uds conditionnellement certains autres D claration d un ordre partiel ou complet sur les variables D claration d un n ud cible pour les applications de type classification ND Oh ND F Existence d une variable latente entre deux n uds Quel que soit le type de connaissances apport es par l expert il est souvent n cessaire d utiliser des donn es pour initier la structure du RB Les a priori de 1 5 peuvent tre facilement int gr s aux algorithmes d apprentissage de structure bas s sur l optimisation d un score Les points 6 et 7 font l objet d une tude plus sp cifique pr sent e dans section 6 2 4 2 6 Exploitation des r seaux bay siens pour mesurer l in t r t d ensembles d attributs fr quents Nous avons vu comment construire et exploiter le RB en tant que mod le des connaissances du domaine revenons maintenant aux travaux pr sent s dans JSO5 et JS04 L approche envisag e par les auteurs repose sur l estimation de la fr quence des itemsets partir du RB et la comparaison de cette estimation avec la fr quence consta t e sur le jeu de donn es Les itemsets dont la fr quence estim e diverge fortement de la fr quence constat e sont consid r s comme int ressants Soit bd une base de donn es binaire de sch ma lt Tj4 Z gt Les valeurs possibles pour les attributs sont d sign es par des lettres minuscule
140. ne pas pouvoir exploiter ces ressources Ce probl me a initi de nombreux travaux de recherche dont le but tait la d couverte d un ensemble de motifs qu on qualifiera d inattendus La notion d inattendu ou d tonnement ne peut se d finir que par rapport un contexte pr cis Dans le cas des travaux de PT06 les auteurs ont trouv une d finition de motifs inattendus par rapport une croyance exprim e sous forme de r gle logique Soit une r gle A B cette r gle sera jug e inattendue par rapport la croyance X Y si elle respecte les conditions suivantes a BET YE FALSE ce qui signifie que B et Y sont contradictoires logi quement b A ET X cette proposition est v rifi e par un ensemble d enregistrements suffisants vis vis d un crit re utilisateur dans une base de donn es bd c La r gle A X B est v rifi e sur bd La cl de l utilisation de cette d finition est l hypoth se de monotonicit des croyances En particulier comme le montrent les auteurs si la croyance Y B est v rifi e sur un ensemble D alors la propri t de monotonicit nous dit que cette croyance sera aussi v rifi e sur tout sur ensemble de D En utilisant cette propri t les auteurs mettent au point un algorithme capable 46 CHAPITRE 2 D COUVERTE DE R GLES PERTINENTES d extraire une collection minimale de r gles tonnantes par rapport un ensemble de croyan
141. nement dans lequel est plong le syst me voluant constamment au cours du temps on va constater de mani re in vitable des diff rences entre ce qui tait attendu http liris cnrs fr 4 CHAPITRE 1 CADRE DE TRAVAIL et ce qui est observ Il faut donc pouvoir d tecter ces volutions et le cas ch ant les prendre en compte au sein du syst me Le contexte des interruptions op rationnelles illustre bien ce probl me Dans le domaine a ronautique une interruption op rationnelle est un retard au d part d collage de plus de quinze minutes une annulation ou une interruption de vol suite un probl me technique panne ou dysfonctionnement De tels v nements sont au jourd hui consid r s avec un r elle importance par les compagnies a riennes du fait des co ts lev s qu ils g n rent Tout au long de ce document on utilisera l abr viation IO pour d signer une interruption op rationnelle Les ing nieurs vont devoir analyser un ensemble de donn es relatives aux incidents afin d en retirer un mod le de pr diction d coulant du fonctionnement des appareils en service Pour ce faire ils utilisent les connaissances non formalis es du domaine rapports d incidents discussions mels chang s comptes rendus de r unions ainsi qu un ensemble de m thodes propres leur m tier qui ciblent des probl mes bien sp cifiques Par exemple ils vont devoir mesurer l impact du positionnement d un qu
142. nera par RB ref TbOrCa FIG 3 8 R seau bay sien de r f rence sur le domaine Visit Asia RB_ ref L utilisation qui est faite de ce r seau consiste diagnostiquer une maladie partir d un ensemble de sympt mes et de faits contertuels ou r ciproquement d terminer les causes les plus probables de cette maladie Le r seau Visit Asia mod lise les faits m dicaux suivants 3 4 R GLES D ASSOCIATION NON REDONDANTES 73 1 La dyspn e dyspnea traduit une difficult respirer Elle peut tre due la tuberculose au cancer du poumon une bronchite ou aucune de ces maladies 2 Un voyage r cent en Asie augmente les chances de tuberculose 3 Un patient fumeur aura plus de risques d tre atteint d un cancer et ou d une bronchite 4 Les r sultats d un examen aux rayons X ne permettent pas de discriminer entre un patient atteint d un cancer du poumon ou d une bronchite 5 La pr sence ou l absence de dyspn e ne permet pas non plus de discriminer ces deux maladies Une des sp cificit s de ce r seau est la variable VisitAsia qui nous renseigne sur le fait que le patient ou non effectu un voyage r cent en Asie Comme on peut le voir figure 3 9 le RB de r f rence mod lise une relation de cause effet entre le fait d avoir visit l Asie et le fait d tre atteint de la tuberculose Cela se traduit par la pr sence d un arc orient reliant le n ud V
143. ngendrant un taux d erreur raisonnable La deuxi me cat gorie concerne un ensemble de m thodes qui reposent sur des principes stochastiques L id e de d part des m thodes stochastiques est d utiliser ce que l on conna t de la loi tudi e pour g n rer automatiquement des chantillons d une base de donn es repr sentative de cette loi g n ration d exemples Il suffit ensuite d utiliser cette base simul e pour calculer les diff rents estimateurs Ainsi diff rentes m thodes sont apparues qui se distinguent par leur fa on de me ner les simulations de g n rer la base d exemples en fonction de diff rentes connais sances de la loi tudi e On peut citer par exemple les m thodes dites probabilistic logic sampling ou encore les m thodes dites MCMC Markov Chain Monte Carlo Plus pr cis ment les MCMC sont une famille de m thodes stochastiques comprenant entre autres Metropolis et l chantillonneur de Gibbs Nea93 Pour conclure on peut dire que l inf rence dans les RB est un probl me ma tris et suivant les cas on pourra faire appel a des m thodes exactes ou approch es selon que l on souhaite privil gier la performance temps de calcul ou la pr cision des r sultats On d signe ici par clique le graphe induit par un ensemble de sommets deux deux adjacents 2 5 PRENDRE EN COMPTE LA CONNAISSANCE DU DOMAINE 51 Apprentissage des param tres partir de donn es compl tes
144. ning pages 125 134 New York NY USA 1999 ACM Press D LIN et Z M KEDEM Pincer search a new algorithm for discovering the maximum frequent set In Proceedings of the EBDT conference pages 105 119 1998 Philippe LENCA Patrick MEYER Benoit VAILLANT Picouet P et St phane LALLICH Evaluation et analyse multi crit res des mesures de qualit des r gles d association Revue des Nouvelles Technologies de l Information RNTI E 1 219 246 2004 St phane LALLICH Elie PRUDHOMME et Olivier TEYTAUD Contr le du risque multiple pour la s lection de r gles d association signifi catives In Actes de la 4e Conf rence EGC Extraction et Gestion des Connaissances volume 2 de Revue des Nouvelles Technologies de Vinformation RNTI E 2 pages 193 217 2004 128 LS88 LSM00 LT03 LT04 MAA05 MPC96 MPC98 MT96 MT97 MTV94 Nea93 NH98 BIBLIOGRAPHIE Steffen LAURITZEN et David SPIEGELHALTER Local computations with probabilities on graphical structures and their application to expert systems Journal of the Royal Statistical Society Series B 50 2 157 224 1988 Wenke LEE Salvatore J STOLFO et Kui W Mok Adaptive intrusion detection data mining approach Artificial Intelligence Review 14 6 533 567 2000 S LALLICH et O TEYTAUD Evaluation et validation de l int r t des r gles d association Revue des Nouvelles Technologies
145. nowledge Discovery in Databases pages 181 192 1994 R M NEAL Probabilistic inference using Markov chain Monte Carlo methods Rapport technique CRG TR 93 1 University of Toronto 1993 R NEAL et G HINTON A view of the em algorithm that justifies incremental sparse and other variants In M I JORDAN diteur Learning in Graphical Models Kluwer 1998 BIBLIOGRAPHIE 129 NLHP98 NWL 04 ODW00 Pas00 PBTL98 PBTL99a PBTL99b Pea88 PHMO00 PKS 03 Pol66 PPMH94 Raymond T Na Laks V S LAKSHMANAN Jiawei HAN et Alex PANG Exploratory mining and pruning optimizations of constrained associa tions rules pages 13 24 1998 Patrick NA M Pierre Henri WUILLEMINN Philippe LERAY Olivier POURRET et Anna BECKER R seaux bay siens Eyrolles 05 2004 Agnieska ONISKO Marek DRUZDZEL et Hanna WASYLUK Learning bayesian network parameters from small data sets Application of noisy or gates 2000 Nicolas PASQUIER Data mining algorithmes d extraction et de r duction des r gles d association dans les bases de donn es th se de doctorat Universit Clermont Ferrand II LIMOS Complexe scienti fique des C seaux F 63177 Aubi re cedex France december 2000 Nicolas PASQUIER Yves BASTIDE Rafik TAOUIL et Lotfi LAKHAL Pruning closed itemset lattices for association rules In Proceedings of the BDA Conference pages 177 196 1998 Nicolas PAS
146. ns 103 4 3 5 Mise jour du r seau bay sien 104 4 3 6 Nouvelles it rations du processus 105 4 4 Critique des r sultats obtenus 108 111 A Pr sentation de l application 117 Table des figures 1 1 Diagramme de s quence simplifi pr sentant la probl matique du cas d application ss 444 4 4444 Le Paw be we A are runs dut 5 1 2 Diagramme de s quence simplifi pr sentant la probl matique d apphcationl san ea a 22 Sew S08 Bh Rah Bee Se DA RES 6 1 3 Pr sentation de l approche envisag e pour la d couverte de facteurs contribuant aux Q 4 4 4 see ba ee eee ee Pe ee 9 1 4 Processus simplifi d Extraction de Connaissances partir des Donn es 1 5 Collaboration des approches mod les et motifs 14 2 1 Exemple de base de donn es transactionnelles T gauche et repr sentation binaire associ e droite 21 2 2 Treillis des itemsets et partition des itemsets fr quents 26 2 3 Treillis des itemsets 34 2 4 Exemple simplifi d une taxonomie pr sente pour le cas d application DT PRIS CR A OR NRA INR ee 41 piue Gor ae Rae eRe a An ne 48 ee ree 53 3 1 Activit Processus de d couverte de connaissances 64 3 2 Activit Mod liser les d pendances du domaine 65 3 3 Activit Extr
147. nt des r gles De plus les algorithmes actuels nous autorisent travailler sur des jeux de donn es arbitrairement grands ce qui correspond bien aux pr requis fix s par la probl matique initiale On verra par la suite que les propri t s de ces r gles vont nous permettre d en visager leur utilisation pour faire voluer dans une certaine mesure un mod le des connaissances du domaine Ce probl me se rapproche de l ing nierie des connais sances il nous faudra donc tudier comment l expert consid re une r gle d asso ciation et comment il envisage de l utiliser pour mettre jour les connaissances du domaine 1 5 2 Les r gles d association Elles ont t initialement introduites par R Agrawal en 1993 Ces r gles sont g n ralement extraites partir d une matrice bool enne ou base de donn es binaire Une r gle d association B peut se lire de la fa on suivante Lorsque j observe la pr sence des v nements A dans les donn es alors les v nements B sont souvent observ s On lui associe g n ralement des fonctions d valuation permettant en particulier de quantifier les termes observe et souvent respectivement la fr quence et la confiance mais aussi de mesurer diff rents crit res statistiques calcul s 16 CHAPITRE 1 CADRE DE TRAVAIL partir des donn es Le Tableau 1 1 montre un exemple de base de donn es binaire Dans cet exemple les colonnes
148. nt fumeur aura plus de risques d tre atteint de bronchite Si on observe un patient atteint d une bronchite alors on sait avec certitude que la variable TbOrCa sera instanci e dans les donn es Par contre il est int ressant de s apercevoir qu un certain nombre de patients qui d clarent avoir r cemment effectu un voyage en Asie montrent les sympt mes li s la tuberculose fait n 2 Enfin on juge comme non pertinent de constater qu une certaine population de patients fumeurs aient voyag en Asie r cemment Ces remarques se traduisent par un ensemble d annotations r sum es par le ta bleau Num Annotations de l expert R gles impact es 1 XRay Bronchitis NV 1 3 Smoking Bronchitis K assez probable 1 2 Tuberculosis TbOrCa K certain 12 3 4 VisitAsia TbOrCa Tuberculosis I 3 5 Smoking Visit Asia NP 4 TAB 3 5 Annotations collect es sur les r gles Visit Asia Lorsqu il r dige ces annotations l expert a pour objectif qu un maximum de r gles contenant uniquement des motifs de type K NP et NV soient filtr s lors de la prochaine it ration du processus Ce filtrage peut intervenir par le biais de la mesure d int r t subjective une modification du RB en fonction des annotations collect es doit diminuer l int r t de ces r gles ou de mani re graphique impact visuel des annotations En effet nous souhaitons que les
149. o CA USA 1995 Morgan Kaufmann Publishers Inc 126 HG94 HGC94 HGNOO HH99 HK00 HKMT95 HMSo1 HMWG98 IM96 TV99 Jeu02 JGJS99 JJJ96 Jor98 JrK BIBLIOGRAPHIE Peter E HART et Jamey GRAHAM Query free information retrieval In Conference on Cooperative Information Systems pages 36 46 1994 David HECKERMAN Dan GEIGER et David Maxwell CHICKERING Learning bayesian networks The combination of knowledge and sta tistical data In KDD Workshop pages 85 96 1994 Jochen HIPP Ulrich GUNTZER et Gholamreza NAKHAEIZADEH Algo rithms for association rule mining a general survey and comparison SIGKDD Explor Newsl 2 1 58 64 2000 Robert J HILDERMAN et Howard J HAMILTON Knowledge discovery and interestingness measures a survey Rapport technique Depart ment of Computer Science University of Regina 1999 Jiawei HAN et Micheline KAMBER Data mining concepts and techniques Morgan Kaufmann Publishers Inc San Francisco CA USA 2000 Marcel HOLSHEIMER Martin L KERSTEN Heikki MANNILA et Hannu TOIVONEN A perspective on databases and data mining In 128 page 10 Centrum voor Wiskunde en Informatica CWI ISSN 0169 118X 30 1995 David HAND Heikki MANNILA et Padhraic SMYTH Principles of data mining The MIT Press 2001 Jochen Hipp Andreas MYKA Rudiger WIRTH et Ulrich GUNTZER A new algorithm for faster mining of gener
150. ociation que d exploiter le mod le de connaissances le plus complet possible sur le domaine La figure 3 2 montre les entr es sorties ainsi que les contr les li s l activit qui consiste mod liser un premier ensemble des d pendances du domaine Mod liser les d pendances du domaine Donn es d apprentissage RB r seau bay sien Expertise Strat gie connais d appren sances tissage FIG 3 2 Activit Mod liser les d pendances du domaine Un point int ressant noter ici est la notion de strat gie d apprentissage envisag e Ainsi si nous avons choisi d int grer des connaissances du domaine au processus de d couverte notre approche se distingue de la litt rature par le fait que la mod lisa tion des connaissances n est pas fig e Le mod le initial volue au cours du processus en b n ficiant des interactions de l expert sur les motifs extraits De ce fait l tape de d finition d un premier r seau bay sien ne demande pas un investissement d mesur pour l expert en pratique il va lui tre demand de d crire les principales d pendances entre les variables qui d finissent le domaine de mani re qualitative et quantitative Il s agit la d une particularit essentielle de notre approche l objectif tant de r duire au minimum le co t de construction initial puis de r partir l volu tion du mod le sur les diff rentes it rations de not
151. omaine ou un mod le de connaissance plus labor dans le but de filtrer les r gles videntes d j connues ou encore celles qui ne sont pas utiles pour l utilisateur 2 4 2 Post traitement des r gles extraites Filtrage syntaxique approches bas es sur les patrons L approche consistant utiliser des patrons de r gles ou templates en anglais a t formalis e par dans le cadre du filtrage des r gles d association Cette approche est utile pour filtrer un ensemble de r gles qui ne correspondent pas aux crit res d finis par un expert Les patrons servent sp cifier ces crit res Un patron de r gle est d fini par l expression Ai Ak gt Agia o chaque A est soit un nom d attribut soit un nom de classe ou une expression CT ou C C tant le nom d une classe Ici CT et C correspondent respectivement une ou plus et z ro ou plus instances de la classe C En pratique cette approche s utilise tr s souvent lorsque l expert des donn es souhaite guider le processus de d couverte de r gles Elle est de plus assez naturelle puisqu elle se rapproche de requ tes que l on peut effectuer sur une base de donn es ou du filtrage par expressions r guli res Ici l expert introduit un biais plus ou moins fort dans les d couvertes qu il va pouvoir r aliser partir de l ensemble des r gles extraites Exploitation des taxonomies Dans certains cas d application il peu
152. on forte en terme de confiance Comme notre mesure est d pendante de la confiance la valeur d int r t reste lev e mais diminue par rapport celle calcul e sur RB_ 0 3 7 VALIDATION SUR LES DONN ES VISIT ASIA 93 Num R gle d association Intrg o Intrg 1 1 Tuberculosis TbOrCa XRay 0 01 0 01 2 Visit Asia XRay 0 89 0 83 3 Bronchitis Cancer TbOrCa XRay 0 01 0 01 4 Bronchitis TbOrCa XRay 0 01 0 01 5 Cancer Dyspnea TbOrCa 0 00 0 00 6 Cancer Smoking TbOrCa 0 00 0 00 7 Cancer XRay TbOrCa 0 00 0 00 8 Dyspnea Tuberculosis TbOrCa XRay 0 01 0 01 9 Dyspnea VisitAsia XRay 0 86 0 76 10 Bronchitis Cancer Dyspnea TbOrCa XRay 0 01 0 01 11 Bronchitis Cancer Smoking TbOrCa XRay 0 01 0 01 12 Bronchitis Dyspnea TbOrCa XRay 0 01 0 01 13 Bronchitis Smoking TbOrCa XRay 0 01 0 01 14 Cancer Dyspnea Smoking TbOrCa 0 00 0 00 15 Cancer Dyspnea XRay TbOrCa 0 00 0 00 16 Cancer Smoking XRay TbOrCa 0 00 0 00 17 Bronchitis Cancer Dyspnea Smoking TbOrCa XRay 0 07 0 01 18 Bronchitis Dyspnea Smoking TbOrCa XRay 0 01 0 01 19 Cancer Dyspnea Smoking XRay TbOrCa 0 00 0 00 20 Cancer TbOrCa 0 00 0 00 TAB 3 8 Evolution de la mesure d int r t et des parties d s par es calcul es sur les r gles d association RB_0 et RB_1 94 CHAPITRE 3 LE TRAVAIL DE RECHERCHE 3 7 4 Critique des r sultats obtenus Par rapport aux objectifs que nous avions fix s c
153. ondantes actuelles et de voir s il tait possible d aller plus loin en sacrifiant une petite part de pr cision sur la confiance des r gles Pour cela nous sommes partis des travaux de et nous avons vu qu il tait possible de d finir deux nouvelles bases pour la g n ration de r gles d association dont la confiance est born e par un param tre 6 Les r gles ainsi g n r es ont t utilis es sur notre cas d application aux donn es d interruptions op rationnelles M thodes issues de l ing nierie de la connaissance Le deuxi me axe de contribution est particuli rement int ressant nos yeux puisque nous avons t amen s r fl chir sur l laboration d un processus capable d int grer et d exploiter les connaissances d un expert dans le but de faciliter l ana lyse de r gles d association Il n y a pas de solution unique En effet la fouille de r gles d association fait intervenir diff rentes probl matiques auxquelles ont peut r pondre par l utilisation de techniques adapt es Un probl me nous pourtant apparu comme ouvert comment liminer la redondance intrins que au domaine d application et faire ressortir par l m me les r gles les plus pertinentes sur le domaine L approche propos e consiste mod liser une premi re bauche des d pendances du domaine par le biais d un r seau bay sien Nous avons ensuite pr cis les moda lit s d exploitation de ces d pendances
154. ormaux n est que la cons quence d une maladie qui a t contract e Apr s r flexion il est donc plus judicieux de reformuler la r gle d couverte en une annotation pertinente reliant VisitAsia a Tuberculosis La collection d annotations r dig e lors de cette tape est pr sent e dans le ta bleau Num Annotations de l expert R gles impact es 1 VisitAsia Tuberculosis I 2 9 2 Cancer TbhOrCa K 1 5 7 10 11 14 17 19 20 3 Tuberculosis TbOrCa K 1 8 TAB 3 7 Annotations collect es sur les r gles Visit Asia 92 CHAPITRE 3 LE TRAVAIL DE RECHERCHE Les annotations n 2 et 3 t moignent d un motif r current qui vient polluer la clart des r gles pr sent es En effet la variable logique TbOrCa est activ e chaque fois que Tuberculosis Present ou Cancer Present sont observ s tape E Finalement ces annotations sont transmises l expert charg de la mise jour du RB L examen des annotations permet de faciliter les ventuelles modifications de la structure et ou des param tres du RB On commence par s int resser l annotation n 1 En comparant ce motif avec la structure de RB_0 on remarque qu aucun lien n est mod lis entre VisitAsia et Tuberculosis Ce motif tant marqu comme int ressant l expert en charge de la mise jour du r seau va relier VisitAsia et Tuberculosis en assignant la CPT de Tubercolisis une l g re influence sur la p
155. peut se passer de calculer la fr quence de certains itemsets en les approchant par la fr quence de leur 6 fermeture De la m me fa on que pour la propri t de libert un itemset 6 libre se d finit comme suit D finition 2 13 6 libre Un itemset est 6 libre s il n est pas inclus dans la 6 fermeture de l un de ses sous ensembles stricts La contrainte d libre est anti monotone Elle peut donc tre exploit e par un algo rithme de type CLOSE C est ce que fait l algorithme MIN E xf qui sera employ tout au long des travaux de th se pour g n rer les r gles d association dites 6 fortes D finition 2 14 r gle 6 forte Soit un entier positif une r gle d association est dite d forte si elle admet au plus 6 exceptions Pour une r gle d association X Y on qualifie d exception toute transaction de la base de donn es qui supporte X mais pas Y Tout comme CLOSE MIN EX fait un parcours niveau par niveau du treillis des itemsets mais au lieu de calculer la fermeture il calcule la 6 fermeture lors de la passe sur les candidats Si vaut 0 MIN EX fonctionne de la m me fa on que CLOSE 2 3 4 G n ration d une collection non redondante de r gles d asso ciation fr quentes et valides Il est admis que la collection de r gles g n r es partir de tous les itemsets fr quents comporte une large part de redondance Plut t que de chercher supprimer cette redondance a posteriori M J Zaki ainsi q
156. propri t s de ces itemsets et des r gles g n r es lorsque 6 est strictement sup rieur Zero D couverte de r gles d association pertinentes par l exploitation d un r seau bay sien Ce deuxi me axe de contribution vient du manque actuel constat par notre tude sur l tat de l art de techniques g n riques visant faciliter la phase d analyse des r gles d association En fait parmi les solutions actuellement propos es beaucoup sont trop sp cifiques filtrage base de patrons exploitation de la taxonomie et ne remontent pas la source du probl me qui pose la question suivante comment utiliser de mani re judicieuse les connaissances du domaine pour la phase d analyse des nombreuses r gles extraites La proposition que nous avons faite dans consiste int grer la connais sance sur les principales d pendances du domaine au calcul de l int r t des r gles d as sociation L expert mod lise les connaissances qui vont lui servir liminer les motifs connus Il utilise pour cela le formalisme des r seaux bay siens Les d pendances mo d lis es permettent de filtrer les motifs t moins dans les donn es de ces d pendances et facilite ainsi la d couverte de r gles plus pertinentes Une approche similaire JS04 JS05 a inspir nos travaux de recherche Les au 3 1 POSITIONNEMENT RAPPEL DES CONTRIBUTIONS ENVISAG ES 61 teurs ont montr que les r seaux bay siens
157. ps d extraction et par l m me de rendre la t che d extraction possible sur des jeux de donn es qui ne pouvaient jusque l pas tre abord s par des approches de type APRIORI On reviendra plus en d tails sur ces contributions dans la section 2 3 2 2 4 L approche support confiance L approche intitul e support confiance fait intervenir les mesures de fr quence et de confiance pour valuer l int r t potentiel d une r gle d association Dans cette optique l utilisation d un seuil minimal de fr quence a pour int r t de rendre prati cable l algorithme d extraction du fait de la propri t d anti monotonie du treillis des itemsets fr quents La confiance doit permettre quant elle de s lectionner les r gles potentiellement int ressantes parmi celles qui satisfont la condition de fr quence 2 2 EXPLOITER LES MESURES D INTERET OBJECTIVES 29 La condition de fr quence qui est le moteur m me du processus d extraction carte les r gles ayant une faible fr quence alors que certaines peuvent avoir une tr s forte confiance et pr senter un r el int r t Comme nous l avons pr cis les algorithmes classiques ne permettent pas l extraction des seuils de fr quence int ressants pour l utilisateur La mesure de confiance est une fonction d valuation objective classique Cepen dant comme le montre l exemple ci dessous elle ne permet pas elle seule de garantir la qualit d une
158. que l encodage du RB d pend d attributs et non d itemsets De ce fait ils d finissent l int r t d un ensemble d attributs J de la fa on suivante Int I max Int 1 i 8eDom 1 Cette mesure d int r t est ensuite utilis e pour filtrer et trier les ensembles d at tributs fr quents afin de faciliter la lecture des r sultats un ensemble d attribut I est jug e int ressant si sa valeur d int r t par rapport au RB est sup rieure au seuil e Cependant les auteurs ont constat que le nombre de motifs ayant un int r t lev tait trop important Ainsi ils ont envisag deux contraintes afin d laguer plus finement l espace des attributs e int ressants La premi re contrainte est une contrainte hi rarchique Elle nous dit qu un en semble d attributs est hi rarchiquement e int ressant si aucun de ses sous ensembles n est e int ressant La deuxi me contrainte tire quant elle parti de la topologie du graphe associ au RB Un ensemble d attributs J sera topologiquement e int ressant si J est e int ressant et s il n existe pas d ensemble d attributs J tels que J Canc Z UT et I J et 2 6 EXPLOITATION DES R SEAUX BAY SIENS 57 J est e int ressant Anc JZ est l ensemble des attributs anc tres de J dans le graphe G Cette contrainte permet donc de limiter le fait que la topologie du graphe entra ne une cascade d at tributs int ressants partir d u
159. quent est d termin par sa divergence vis vis des connaissances du domaine 2 5 PRENDRE EN COMPTE LA CONNAISSANCE DU DOMAINE 47 Contrairement l approche qui consiste mod liser les connaissances par un ensemble d implications logiques puis utiliser ces connaissances de mani re lo cale les auteurs de proposent de mod liser et d exploiter la loi jointe de proba bilit sur l ensemble des donn es Pour cela ils exp rimentent l utilisation d un r seau bay sien en tant que mod le des connaissances du domaine Avant d entrer plus en d tails dans la description de cette approche qui a en partie inspir nos travaux de th se une pr sentation des r seaux bay siens est n cessaire Qu est ce qu ils repr sentent Comment sont ils utilis s Comment les mod liser pour qu ils refl tent avec pr cision les connaissances de l expert Ces questions sont essentielles car elles sont au c ur de nos travaux de th se Une fois abord es on reviendra sur l utilisation des r seaux bay siens propos e par S Jaroszewicz et al dans le cadre de la d couverte d itemsets fr quents inattendus 2 5 2 Les r seaux bay siens comme mod le de la connaissance du domaine Cette section a pour objectif de pr senter les r seaux bay siens en tant que mod le de connaissance nous utiliserons l abr viation RB Il ne s agit pas de r aliser ici un tat de l art exhaustif sur le domaine mais bien de mettre
160. r gle d association Elle peut de plus tre la source d erreurs d inter pr tation des r sultats Prenons le cas o la confiance d une r gle B est gale la probabilit de B Selon la d finition de la confiance on a alors P B A P B c est dire une ind pendance entre A et B Cette r gle qui peut avoir une forte confiance ne nous apporte aucune information elle ne doit donc pas tre jug e comme int ressante L exemple suivant permet d illustrer ce propos Exemple Supposons que l on souhaite analyser la relation qui existe entre des personnes achetant les produits A et B Le tableau montre la r partition des achats sur la population tudi e A gt 150 50 200 650 150 800 800 200 1000 M wb TAB 2 3 R partition des achats sur un groupe de 1000 personnes A partir de ces donn es il est possible d valuer la r gle A B F 0 15 conf 0 75 Les valeurs raisonnablement lev es pour les mesures de fr quence et de confiance nous invitent penser que les personnes qui ach tent le produit A ach tent aussi le produit B Cependant la part des personnes achetant B ind pendamment du fait qu elles ach tent aussi A est de 0 80 alors que la r gle nous dit que la proportion de personnes consommant A et B est inf rieure puisqu elle est gale 0 75 La r gle A B qui semblait int ressante s av re donc trompeuse L utilisation d autres mesures para t don
161. r gles affich es int grent un maximum d informations relatives aux annotations dans le but de faciliter les tapes ult rieures d analyse L id e est d affiner progressivement le mod le de connaissance utilis pour le fil trage des r gles d association en y int grant les d pendances r cemment d couvertes Cependant l interpr tation des motifs extraits et le choix des modifications apporter au RB ne sont pas des t ches faciles r aliser 3 6 3 Prise en compte des annotations et mise jour du r seau bay sien Consid rons d abord le cas des annotations de type K partir de ces annota tions on doit mettre jour la structure et les param tres du r seau bay sien Pour cette tape il faut r pondre principalement deux types de probl mes 3 7 VALIDATION SUR LES DONN ES VISIT ASIA 87 La premi re cat gorie de probl me est relative la traduction d une annotation en l ments de modifications du r seau bay sien La syntaxe que nous avons propos e facilite ce passage Soit les variables X Y et Z Une annotation X et Y gt Z C p sera prise en compte par la cr ation d un arc de X vers Z et d un autre de Y vers Z La table des probabilit s est alors modifi e en cons quence en fixant p Z X Y p On proc dera de la m me fa on pour traiter les associations simples de type X Y Le second probl me est li la modification du r seau bay sien La d finition des
162. r sence de tuberculose lorsque le patient d clare avoir visit l Asie Mais comment quantifier cette influence En effet il serait invraisemblable de mod liser le fait que tous les gens ayant effectu un voyage en Asie soient atteints de tuberculose Pour cela l expert peut s aider d outils que nous avons mis sa dis position par exemple en tudiant pour les r gles concern es le r sultat des mesures objectives qui prennent en compte le nombre de contre exemples e g la moindre contradiction ou encore en utilisant le module de test d hypoth se il est possible de tester partir des donn es le support et la confiance des r gles Visit Asia NoVisit Tuberculosis Absent VisitAsia Visit Tuberculosis Absent etc Les r sultats de cette analyse permettent d tablir la CPT associ e au n ud Tuberculosis Nouvelle it ration du processus La premi re it ration de notre processus est termin e On peut alors initier une nouvelle it ration sur les m mes r gles mais cette fois 4 partir de RB_ 1 on obtient le r sultat pr sent dans le tableau 3 8 En tudiant ce tableau on peut l gitimement se demander pourquoi l int r t des r gles n 2 et 9 est toujours lev Il ne faut pas oublier que l influence de Visit Asia sur Tuberculosis et donc directement sur XRay que nous avons mod lis e est bien qu int ressante m dicalement faible Or ces deux r gles font tat d une associati
163. r et valider le processus de d veloppement Enfin pour aider les experts mesurer l impact des d cisions techniques prises en termes de taux d IO un outil informatique t mis en place Il impl mente un mod le math matique stochastique int grant les param tres dont les impacts sur la fr quence des IO sont connus Cet outil est calibr et param tr par le retour d exp rience obtenu partir d avions de syst mes ou d quipements en service comparables La figure 1 1 pr sente sous la forme d un diagramme d activit UML une vue simplifi e du processus li la 1 2 ANALYSE DES INTERRUPTIONS OP RATIONNELLES 5 Entreprise Ing nieur IO D finir des cibles de taux d IO Mod le de pr diction a taux d IO R aliser un compromis global Fic 1 1 Diagramme de s quence simplifi pr sentant la probl matique du cas d ap plication Ing nieur quipement D finir les sp cifications de l quipement R aliser un compromis pr diction cible fix e au niveau quipement Concevoir un nouveau programme avion Donn es IO et retour d exp rience programmes similaires mod lisation des performances en termes de taux d IO d un nouveau programme avion Cette vue simplifi e du cas d application nous permet d introduire une des probl matiques rencontr es par un industriel a ronautique Celui ci doit tre en me sure d
164. r une Comparaison synth tiques des algorithmes d apprentissage de la structure Il peut par contre tre important de retenir que les techniques d apprentissage automatique bien qu int ressantes ne peuvent pas tre utilis es telles quelles les r sultats obtenus n cessitant imp rativement d tre valid s par un expert En effet on se rend compte que m me sur des cas d applications relativement simples chaque m thode obtient des r sultats de structure l g rement diff rents Malheureusement ce qui en termes de distance d dition ne repr sente qu une diff rence singuli re pr sence ou non d un arc inversion du sens d un arc peut avoir pour l expert du domaine un sens bien plus critique De plus la structure qui satisfait un crit re de score vrai semblance de la structure par rapport aux donn es d apprentissage ne repr sente pas forc ment dans la r alit les connaissances que souhaite mod liser l expert 2 6 EXPLOITATION DES R SEAUX BAY SIENS 55 Incorporation des connaissances pour l apprentissage de la structure Dans la plupart des cas d applications les connaissances de l expert sur la struc ture que peut avoir le RB ne sont que partielles CGK 02 INWL 04 ont fait une liste de ces connaissances priori D claration d un n ud racine sans parents D claration d un n ud feuille sans enfants Existence ou absence d un arc entre deux n uds pr cis I
165. re contradiction dans les diff rents cas de figure i e A a B b C c amp A a B b gt C c x A a B b C c et A a B ab gt C6 Une partie des annotations r alis es lors de cette it ration est donn e dans le tableau Certains motifs sous partie d une r gle d association sont jug s non valides par l expert C est le cas par exemple de la relation zone ME OP2 ST2 ou de mani re plus g n rale zone X OP ST qui nous dit que lorsque l on conna t la zone g ographique dans laquelle op re une compagnie alors on peut d duire le nom de cette compagnie et l a roport o a eu lieu l interruption Ce type de relation n a pas caract re de connaissance valide selon l expert il s agit d une sp cificit du jeu de donn es pour le triplet zone ME OP2 ST2 Les annotations correspondantes sont alors r dig es dans la cat gorie NV D autres motifs sont annot s comme tant connus K car ils repr sentent une relation vidente En l occurrence ces relations sont souvent pr sentes l int rieur d une r gle et d j mod lis es par le RB L annotation syst matique de ces motifs va se r percuter sur l affichage des r gles Le but est de permettre l expert une visualisation imm diate des parties de la r gle qui repr sentent une information d j connue par rapport celles qui n ont pas t annot es C est le cas par exemple pour tou
166. re processus de fouille Ce faisant on introduit cependant une autre probl matique notre contexte celle de la mise jour du r seau bay sien Extraction de motifs locaux Les r gles d association sont au centre des interactions de notre syst me Elles sont extraites partir d une base de donn es bd de sch ma T4 Items en sp cifiant un seuil de fr quence minimal minfreq un param tre 6 qui limite la confiance des r gles g n r es au seuil minconf et ventuellement un ensemble Cg de contraintes 66 CHAPITRE 3 LE TRAVAIL DE RECHERCHE syntaxiques Le r sultat de la fonction d extraction que nous appellerons bd minfreg Cs et du calcul de n mesures objectives est la collection LR Tq IRB P sep L R est l ensemble des r gles d association qui satisfont les contraintes de fr quence minimale de confiance minimale et de syntaxe De plus pour toute r gle d association Rx L R il n existe pas de r gle d association R L R telle que R soit plus g n rale que Rx L Tha est l ensemble des mesures associ es aux r gles d association de L R A chaque r gle Ry on associe n mesures objectives calcul es sur bd On acc de la 42 mesure d int r t de la KME r gle de la fa on suivante Tia Cette activit est repr sent e par la figure 3 3 L lt R I_bd 0 0 gt collection de r gles et mesures objectives associ es Extraire les r gles d associa
167. rentes approches pour la s lection de r gles r ellement pertinentes pour l utilisateur 2 2 EXPLOITER LES MESURES D INTERET OBJECTIVES 23 2 2 Exploiter les mesures d int r t objectives 2 2 1 D finition du probl me Apr s avoir tabli un cadre formel aux r gles d association nous allons mainte nant nous int resser la phase d extraction de ces r gles ainsi qu aux diff rentes probl matiques qui en d coulent Une approche na ve consisterait calculer le support et la confiance de toutes les r gles possibles Cette approche n est pas r alisable car le nombre de r gles R pouvant tre extraites partir d une base de donn es est exponentiel en fonction du nombre d items d qui composent le jeu de donn es Rag 21 44 Ainsi en appliquant cette formule sur un petit jeu de donn es constitu de 6 items figure 2 1 on se rend compte qu il est possible de g n rer 36 27 1 soit 602 r gles diff rentes Cependant de nombreuses r gles ont une fr quence ou une confiance faible voire nulle Ces r gles ne sont pas int ressantes pour l utilisateur final exploiter ces deux mesures fr quence et confiance en fixant par exemple des seuils minimaux pour Vextraction permettrait d viter de nombreux calculs inutiles ainsi que de pr senter Putilisateur un trop grand nombre de r gles Le probl me de l extraction peut donc se reformuler de la fa on suivante tant donn un ensemble de tran
168. repr sentent les diff rents attributs de la base et chaque ligne repr sente un enregistrement ou transaction Un 1 l intersection d une ligne l et d une colonne c indique que l on observe la pr sence de l attribut c pour l enregistrement l Par exemple si les colonnes repr sentent diff rents produits d un supermarch et chaque ligne le panier d un client alors les 1 y permettent d identifier le contenu de ces paniers Ce tableau fait aussi appara tre deux exemples de r gles d association pouvant tre extraites partir de la matrice bool enne Ta BCDE 1 0 0O 1 0 1 2 1 1 1 1 1 1 B A fr quence 0 5 confiance 1 00 3 10 110 i i 4 1 1 1 1 0 2 A B C fr quence 0 33 confiance 0 66 5 0 1 0 6 1 1 0 0 1 TAB 1 1 Exemple de matrice bool enne et de r gles d association extraites Depuis que l algorithme APRIORI a t propos AMS 96 une des principales pr occupations des diff rentes quipes de recherche a t l am lioration des perfor mances d extraction Plus pr cis ment il s agissait d tre en mesure de calculer la collection d itemsets fr quents sur des jeux de donn es arbitrairement grands la o l algorithme APRIORI montrait tr s vite ses limites On verra notamment que ces r flexions ont abouti la d finition d une repr sentation interm diaire des donn es dite repr sentation condens e Ce type de repr sentation a t
169. rge data While the environment associated with this process evolves constantly one inevitably notices the appearance of differences between what was expected and what is really observed By using the collected data and available ex pertise it is then necessary to detect these differences and thus to update the model being used Accordingly we propose knowledge discovery process that integrates the defini tion and the exploitation of a bayesian network to facilitate the analysis of a concise set of association rules The evolution of this model is controlled by the discovery of relevant rules themselves made more accessible by the exploitation from the proper ties of this model Finally we show a practical application of our proposals to the field of operational interruptions in the aircraft industry Mots cl s Data mining knowledge engineering association rules bayesian networks Table des mati res Introductionl sas e a 8 a eG NE RUE Meee OS ORES Se RE GS 1 Cadre de travail 1 1 Le contexte industriel 1 2 Analyse des interruptions op rationnelles 1 3 D couverte de connaissances utiles 1 3 1 Connaissance 1 3 2 Connaissance utile 1 3 3 D couverte de connaissances utiles partir de donn es 1 4 Mod les des connaissances 1 5 D couverte de r gle
170. rnational conference on knowledge discovery and data mining KDD 00 2000 Ramesh C AGARWAL Charu C AGGARWAL et V V V PRASAD A tree projection algorithm for generation of frequent item sets Journal of Parallel and Distributed Computing 61 3 350 371 2001 Rakesh AGRAWAL Tomasz IMIELINSKI et Arun SWAMI Mining as sociation rules between sets of items in large databases In Peter Bu NEMAN et Sushil JAJODIA diteurs Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data pages 207 216 Washington D C 26 28 1993 J r me AZ et Yves KODRATOFF Evaluation de la r sistance au bruit de quelques mesures d extraction de r gles d assocation Extraction des connaissances et apprentissage 1 4 143 154 2001 Yonatan AUMANN et Yehuda LINDELL A statistical theory for quan titative association rules In KDD 99 Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining pages 261 270 New York NY USA 1999 ACM Press Rakesh AGRAWAL Hiekki MANNILA Ramakrishnan SRIKANT Hannu TOIVONEN et A Inkeri VERKAMO Fast discovery of association rules chapitre 12 pages 307 328 American Association for Artificial Intelli gence Menlo Park CA USA 1996 Rakesh AGRAWAL et Ramakrishnan SRIKANT Fast algorithms for mining association rules In Jorge B Bocca Matthias JARKE et Carlo ZANIOLO diteurs Proceedings of the 199
171. rocessus que les annotations de type NP ont un impact visuel lors de l affichage des r gles d association Enfin on constate que les motifs du type ata2d ata6d sont jug s int ressants En effet ce type de relation va l encontre de ce qui est mod lis dans le RB i e si par d finition il est certain d avoir la relation ata6d ata2d l inverse n est a priori pas vrai Il s agit en fait d une particularit int ressante du jeu de donn es L exploitation de ce type de d couvertes est alors laiss e la discr tion de l expert du domaine Num Annotations de l expert R gles impact es 1 zone gt OP NV 1 9 2 zone ST NV 1 9 3 ata6d 801120 gt Engine wy 2 4 ata6d 801120 ata2d 80 NP 2 5 ata6d 801120 atadd 8011 NP 2 6 operator station station _ a K certain 8 7 ata2d ata_type K certain 8 atadd ata6d I 3 4 7 10 9 atadd action ata6d I 4 10 ne type fault ata2d I 6 TAB 4 6 Exemples d annotations collect es la deuxi me it ration du processus Les annotations sont ensuite utilis es pour effectuer la mise jour du RB Le r sultat est pr sent dans la Figure 4 5 les modifications apparaissent en gras It ration n 3 L expert peut d cider de visualiser les nouveaux calculs d int r t qui d coulent de l utilisation de RB03 A titre d illustration on pr sente l aussi les
172. ronchitis n est plus directement reli e Dyspnea 5 Du fait de la modification n 4 les tables de probabilit s de Dyspnea sont adap t es en cons quence 3 7 VALIDATION SUR LES DONN ES VISIT ASIA 89 Les changements apport s sont affich s en gras dans la figure qu il s agisse de l ajout d un arc ou de la modification d une CPT Ce RB correspond au r seau initial ou RB_ 0 Dans un contexte applicatif c est ce r seau qui aurait t d fini par un expert afin d tre utilis en entr e de la 1 it ration de notre processus FIG 3 11 R seau bay sien Visit Asia RB_ 0 utilis pour la 1 it ration du pro cessus d couverte de connaissances 3 7 3 D roulement de l approche KARD On se propose maintenant de suivre pas pas les diff rentes tapes de la m thode pr sent e dans la figure 3 7 tape A Le r seau Visit Asia RB_0 sert de base pour nos exp rimentations Nous avons d crit pr c demment les modifications apport es par rapport RB ref tape B partir du jeu de donn es g n r es on extrait une collection concise de r gles d association minfreq 100 soit 0 01 du nombre total d enregistrements de la base de donn es et nombre maximal d exceptions 10 i e ce qui nous garantit une 90 CHAPITRE 3 LE TRAVAIL DE RECHERCHE confiance minimale de 0 90 Il s agit de la collection L R Th q 0 0 Les mesures ob jectives calcul es sont la confiance
173. rtinentes A nsi la troisi me it ration de notre processus les r gles ayant un fort int r t par rapport au RB sont effectivement porteuses d informations jug es int ressantes par l expert Le deuxi me avantage de notre approche est la possibilit d liminer les r gles qui ne pr sentent pas d int r t pour l expert Un aspect rassurant vis vis du filtrage des r gles tr s faible valeur d int r t seuil arbitrairement fix Intrg lt 0 1 provient du fait que sur nos exp riences aucun faux n gatif n a t d tect C est dire qu il n y avait pas de r gles que l on aurait pu juger int ressantes parmi les r gles filtr es Au final la d couverte de ces d pendances et les modifications qui en ont d coul confortent le principe propos par notre approche qui est de mod liser par interaction avec l expert les d pendances du domaine et les exploiter pour am liorer le filtrage des r gles d association extraites et ainsi faciliter leur tude Ces r sultats soul vent n anmoins quelques nouvelles interrogations La premi re vient du fait que certaines r gles qui poss dent un motif non valide peuvent avoir une valeur d int r t lev e C est notamment le cas de la r gle d association n 1 pr sent e dans le tableau 4 7 Il s agit de cas de faux positifs La solution actuellement ap port e est uniquement visuelle la sous partie de la r gle qui contient une information
174. s communes avec le projet en cours Actuellement les besoins de recherche tendent se focaliser sur l am lioration des mod les de calcul utilis s par l outil de pr diction des performances op rationnelles Dans ce contexte la fouille de donn es en service est particuli rement int ressante puisqu elle vise d couvrir des facteurs qui jusque l n taient pas connus Ces facteurs pourraient alors tre int gr s aux mod les pour obtenir des pr dictions encore plus fid les Les sections suivantes pr sentent l application des diff rentes tapes du proces sus de fouille aux donn es d interruptions op rationnelles La m thodologie propos e pr c demment Chapitre 3 sera appliqu e L objectif est de faciliter la d couverte de r gles d association int ressantes et potentiellement exploitables apr s reformulation en tant que nouveaux contributeurs des taux d interruptions op rationnelles Pour des raisons de confidentialit toutes les donn es pr sent es par la suite ont t maquill es de telle sorte que les r f rences les num ros d ATA les num ros de s rie etc ne puissent pas tre reconnus ou r utilis s l insu de la compagnie qui les d tient Les travaux d taill s dans ce chapitre ont donn lieu deux publications une dans le domaine de l extraction de connaissances J FDMB06a l autre plus ax e sur les probl matiques d ing nierie de la connaissance FDMBO6b
175. s correspondant aux attri buts Notons Pr la distribution de probabilit jointe de l ensemble d attributs J De m me notons Pyy la distribution de probabilit de J conditionn e par J La notation Pr i d signe la probabilit pour que J i La distribution de probabilit estim e partir des donn es sera not e en ajoutant le symbole du chapeau par exemple Pr Ainsi la fr quence d un itemset I i s crit F I i Pr i 56 CHAPITRE 2 DECOUVERTE DE REGLES PERTINENTES Prenons maintenant un r seau bay sien RB sur un ensemble d attributs H et un graphe G on rappelle que RB d finit de mani re unique la distribution de probabilit jointe de H PRY IL Pa par Avec par l ensemble des attributs parents directs de A dans G Afin de calculer la mesure d int r t d un ensemble d attribut on d finit la fr quence d un itemset I i calcul par rapport au RB de la mani re suivante FrglI i PF L int r t d un itemset I i par rapport RB est alors donn par la diff rence en valeur absolue entre la fr quence de l itemset constat e sur les donn es et celle estim e partir de RB Intrg I i F I i Frg I i Les auteurs pensent que les motifs qui ne sugg rent pas une direction d influence sont les plus appropri s dans un contexte de fouille Ainsi ils s int ressent uniquement l int r t des itemsets fr quents voire d ensemble d attributs puis
176. s d association utiles l expert 1 5 1 Choix des r gles d association pour notre cas d application a ame HEE hts dn He beet 2 D couverte de r gles pertinentes 2 1 Introduction la probl matiquel 2 1 1 Philosophie de l extraction de r gles d association 2 1 2 Repr sentation 2 1 3 Itemsets et r gles d association 2 2 Exploiter les mesures d int r t objectives 2 2 1 D finition du probl mel iii o OT ow 26 28 29 30 he oe eb i eee eo 31 2 3 1 D finition du probl mel 31 32 2 3 3 Diff rentes repr sentations condens es des itemsets fr quents 35 2 3 4 G n ration d une collection non redondante de r gles 36 TELET E wee ae ea a ee ee Gee EE 39 ih ee I A Rah ea ee hah eh eS 39 2 4 1 D finition du probl mel 39 2 4 2 Post traitement des r gles extraites 40 2 4 3 Extraction sous contraintes 42 See eh hk ere EO ed IR ea ee a 43 2 5 Prendre en compte la connaissance du domaine 43 2 5 1 D finition du probl mel 43 RE Wi he A we a oe Ba ae we ie 47 dE ee eS 55 2 6 1 Conclusion 4 4 4 44 raana rrasa arada dr es 57 2 7 Discussion sur l tat de l art oaoa a 2 0 02 0204 58 59 3 1 Positionnement r
177. s et de la 6 fermeture et des r gles g n r es C est un probl me qui ce jour n a pas t tudi Cela peut tre int ressant car le param tre 6 apporte un bon compromis entre rapidit d ex cution taille et pr cision des r sultats On dispose pr sent de techniques permettant la fois de g n rer un ensemble concis de r gles d association limination de la redondance intrins que mais aussi de travailler des seuils de fr quence bas sur des donn es complexes une autre piste de r flexion se dessine En effet pour des applications r elles les r gles pr sent es sont toujours trop nombreuses et difficiles analyser Elles comportent des informations d j parfaitement connues de l expert ou au contraire elles pr sentent des motifs qui n ont pas de rapport avec les objectifs de recherche fix s par l utilisateur Dans la prochaine section on va donc r fl chir aux techniques permettant d introduire la subjectivit dans le processus de d couverte de r gles int ressantes ainsi qu celles dont le but est de limiter la redondance au domaine d application 2 4 Exploiter la subjectivit pour s lectionner les r gles pertinentes 2 4 1 D finition du probl me Un autre sujet de recherche majeur est le probl me de la d couverte de r gles r ellement pertinentes partir de l ensemble des r gles g n r es Ce probl me est troitement li la taille de la collection des itemsets
178. s taux d interruptions op rationnelles Concernant cette probl matique les besoins de recherche portent sur l am lioration des mod les de calcul utilis s par le mod le de pr diction et notamment la d tection et la validation de nouveaux facteurs contribuant aux 10 Certains de ces facteurs sont identifi s de mani re informelle la suite de discussions d changes de mails ou de r unions entre les experts du domaine D autres ont t identifi s mais n ont pas pu tre int gr s au mod le de pr diction faute de pouvoir les v rifier sur les donn es D autres enfin restent d couvrir partir du retour d exp rience sur les programmes avions en service Une des voies envisag e par les experts dans le domaine des IO pour la d cou verte de nouveaux facteurs d interruptions passe par une analyse pouss e des don n es en service la prise en compte des volutions techniques ainsi que l acquisition de nouvelles connaissances du domaine et leurs int grations au mod le de pr diction Cependant il n y a actuellement pas de processus bien d fini pour la recherche de ces nouvelles connaissances L expert met un ensemble d hypoth ses qu il va ensuite v rifier manuellement sur les donn es Un exemple concret est la d couverte et la prise en compte d un facteur ayant une grande influence sur les taux d IO L intuition initiale de l expert tait de regarder dans les rapports de maintenance asso
179. sactions d couvrir toutes les r gles qui ont une fr quence sup rieure minfreq et une confiance sup rieure minconf minfreq et minconf correspondent respectivement aux seuils de fr quence et de confiance fix s par l utili sateur Pour r soudre ce probl me les approches classiques fonctionnent en deux tapes Tout d abord une phase d extraction des itemsets fr quents et de leur support Les itemsets fr quents sont tous les ensembles de couples attribut valeur qui satis font un seuil de fr quence minimale minsup sp cifi par l utilisateur Puis la deuxi me tape consiste en la g n ration des r gles d association de forte confiance sup rieure minconf partir des itemsets fr quents et de leur support extraits l tape pr c dente La premi re difficult d coule du fait que l extraction des itemsets demande des temps de calculs importants puisqu on doit g n ralement effectuer plusieurs passes sur les donn es pour arriver calculer le support des itemsets Il s agit donc d tre en mesure de calculer ces itemsets quel que soit le jeu de donn es abord Le deuxi me point concerne la g n ration des r gles ainsi que leur valuation Cette phase a pour objectif d liminer le plus grand nombre possible de r gles inint ressantes 24 CHAPITRE 2 D COUVERTE DE R GLES PERTINENTES ou redondantes entre elles et vis vis du domaine d application Il faut donc pouvoir d finir un
180. sateur D autres approches ont pr sent une vision plus syst matique de l exploitation de ces connaissances en introduisant une mod lisation pr alable des connaissances Les probl matiques de mod lisation de la connaissance pr sentent videmment de nombreuses difficult s Il faut tre en mesure de trouver un consensus entre les diff rents experts du domaine et mobiliser des quipes pour la formalisation et la construction du mod le Il s agit d une activit qui demande g n ralement un inves tissement important en termes de temps et d nergie d pens e De plus les b n fices r els que l on pourra retirer de l utilisation du mod le s av rent difficile valuer a priori ce qui rend le choix de s investir dans une telle entreprise la fois strat gique et risqu Pour ces raisons on pr f rera utiliser le terme de d pendances du domaine plu t t que de parler directement de mod le des connaissances ou encore d ontologie du 3 2 PROCESSUS DE D COUVERTE DE CONNAISSANCES KARD 65 domaine Le r seau bay sien n est pas pour autant consid r comme une sous ap proche pour la mod lisation des connaissances sa d finition requiert du temps de l expertise et elle doit faire face de nombreux probl mes d ing nierie de la connais sance Dans notre cas il s agit plus d tudier une cat gorie de mod le que nous pensons comme tant la plus adapt e pour l analyse de r gles d ass
181. sence de Z bloque le cheminement de l information de X vers Y Formul diff remment on dira qu en pr sence de Z le fait d observer X n apporte pas de connaissances suppl mentaires sur Y Ainsi pour d terminer les diff rences en termes de circulation de l information entre les r gles et le RB nous allons appliquer la propri t de d s paration sur la collection de r gles extraites par rapport la structure du RB Pour chaque r gle d association R X Y on calcule le test de d s paration X X X Y pour tous les X X et pour tous les Y Y i e X et Y sont des items de la r gle Si X est de taille 1 alors Z est gal et aucun Y n est d s par de X Dans le cas o le nombre d items de X est strictement sup rieur 1 on tudie la matrice bool enne qui contient tous les r sultats des tests de d s paration entre les X et les Y Si pour un item X ou Y donn tous les r sultats de d s paration sont positifs alors cet item est ajout l ensemble que nous appelons partie d s par e de la r gle ou D sep Concr tement cela signifie qu une association a t 3 5 EXPLOITATION D UN R SEAU BAYESIEN 83 trouv e dans les donn es mais qu elle n est pas mod lis e dans le RB Son ensemble compl mentaire est appel ensemble des d pendances principales on le note D core Exemple Soit la r gle d association R ABC D Notre algorithme calcule les tests
182. sent sous une forme tangible dossier papier ou lectronique Ici le mode d emploi est d crit de fa on a pouvoir tre ex cut Le cas typique de connaissance explicite est le manuel de recherche de pannes TSM ou troubleshooting manual destin aux quipes de maintenance Il s agit v ritablement d un mode d emploi sous forme de document crit qui va permettre partir de son ex cution de d finir l origine d une panne Par ailleurs il est aussi important de bien faire la distinction entre l information les donn es brutes et la connaissance qui elle est appropriation et l interpr tation des informations par les hommes Cette information elle m me contenue l tat brut dans les donn es Dans les entreprises la connaissance correspond au capital d expertise que d tiennent les hommes dans les diff rents domaines qui constituent le c ur de m tier de l entreprise Dans notre contexte on d finit une connaissance comme tant un fait pouvant se v rifier sur les donn es issues d un processus exp rimental ou de donn es r elles Par exemple un expert des donn es IO va savoir que la probabilit pour qu il y ait une IO li e l quipement n 212042 est de 0 001 lorsqu il est embarqu sur un avion de type A3X0 Cette connaissance peut se v rifier sur les donn es en service du programme avion A3X0 et elle va pouvoir tre utilis e grace aux connaissances de l expert et aux out
183. si tous les membres de l quipe Data Mining et Bases de Donn es In ductives de PINSA Aleksander S Sa di J r my Besson Ruggero G Pensa et ceux de l quipe de SILEX Supporting Interaction and Learning by Experience du LIRIS pour les discussions amicales et scientifiques que nous avons pu avoir ensemble Je souhaite aussi remercier les membres de mon jury pour leur travail et les conseils qu ils m ont promulgu s Et enfin je remercie sp cialement ma compagne Nelly Delecroix et ma famille qui ont su me soutenir et m encourager dans les moments de doute A tous un grand Merci R sum Dans un contexte industriel un ing nieur est souvent confront analyser un ensemble de donn es relatives un processus op rationnel L environnement dans lequel est plong le mod le voluant constamment au cours du temps on va constater de mani re in vitable l apparition de diff rences entre ce qui tait attendu et ce qui est r ellement observ Plus inqui tant certains comportements peuvent tre masqu s dans la masse des donn es Il faut alors tre en mesure de d celer ces diff rences et le cas ch ant de mettre jour le mod le utilis Un apport combin des techniques d extraction de la connaissance ECD et de m thodes issues de l ing nierie de la connaissance permet de r pondre ce besoin Dans cette th se nous avons envisag la d couverte de r gles d association per
184. sont fortement corr l es le gain de taille par rapport la repr sentation de tous les itemsets fr quents peut tre de plusieurs ordres de grandeur Comme on le verra cette collection est aussi tr s int ressante car elle permet de g n rer un ensemble concis de r gles d association section 2 3 4 Une propri t essentielle de ce type de collection a t propos e dans PBTL99a En substance elle nous dit qu partir de l ensemble des itemsets ferm s y fr quents il est possible de calculer la fr quence de n importe quel itemset y fr quent Un autre type de repr sentation condens e cette fois utilisant les itemsets libres fr quents a t pr sent dans BBR00 Les auteurs montrent que pour retrouver la fr quence de n importe quel itemset S y fr quent il faut d abord pouvoir montrer que cet itemset est bien y fr quent c est dire qu il n appartient pas l ensemble des itemsets des non y fr quent ou qu il n est pas libre BBROO a aussi propos un autre type de repr sentation condens e bas cette fois sur une g n ralisation des itemsets libres les itemsets 6 libres D finition 2 12 6 fermeture BBR00 Soit un entier positif La 6 fermeture d un itemset S not e ferms S est d finie par ferms S I Items Freq S Freq S U I lt 6 36 CHAPITRE 2 D COUVERTE DE R GLES PERTINENTES Freq est la fr quence absolue En pratique cela signifie qu on
185. squ on observe qu une personne visit l Asie alors on observe aussi des r sultats de rayons X anor maux Clairement cette r gle apporte une information port e par les donn es mais qui n est pas mod lis e en tant que d pendance par le RB Ce fait est aussi corrobor par le fait que XRay est graphiquement s par de VisitAsia dans le r seau RB_0 l information ne circule pas entre ces deux n uds Ainsi il est possible de trouver des r gles qui pr sentent une diff rence entre le mo d le de connaissance disponible et les donn es On peut n anmoins se demander si de telles d couvertes d associations sont r ellement int ressantes et si c est le cas quelles modifications peuvent tre apport es au RB actuel pour refl ter ces observations faites sur les donn es La phase d annotation doit permettre de pr parer une r ponse cette question Dans notre cas nous avons effectu nous m me les annotations au regard des va leurs d int r t et des d compositions des r gles en parties d s par es d pendances principales C est en fait ce moment qu intervient le jugement de l expert Prenons l exemple des r gles n 2 et 9 qui exhibent un int r t lev vis vis de RB 0 Ces r gles nous donnent une indication sur le sens de circulation de l infor mation entre VisitAsia et XRay Mais si l on se replace dans un contexte strictement m dical le fait de constater des examens de rayons X an
186. stat suivant les ap proches actuelles pour la d couverte de connaissances n exploitent pas ou peu les connaissances existantes sur le domaine d application qu elles soient pr sentes de mani re implicite ou non Les difficult s li es l utilisation de ces mod les s articulent principalement autour de trois axes La d finition du mod le en lui m me est g n ralement consid r e comme une entreprise lourde n cessitant des moyens importants Il pourra donc tre int ressant de trouver un compromis entre la pr cision du mod le et les ressources d ploy es pour sa cr ation La d finition de mesures et d outils permettant l exploitation de ce mod le au sein d un processus de d couverte dans le but de s lectionner des r gles per tinentes c est dire des r gles qui pr sentent une divergence par rapport au mod le Et enfin la prise en compte des probl matiques d volution et de la maintenance du mod le au cours du temps Notre contribution s articule autour de ces trois points L approche propos e s in titule KARD pour Knowledge driven Association Rules Discovery elle place l expert et les connaissances du domaine au c ur de la probl matique de d couverte de r gles L id e est de r unir deux domaines que nous pensons compl mentaires celui de l in g nierie de la connaissance et celui de la fouille de donn es Les sections suivantes 3 2 PROCESSUS DE D COUVERTE DE
187. strumentation d un processus ECD permettant de telles d couvertes Comment exploiter la connaissance du domaine pour faciliter la d couverte de connaissances utiles Et inversement comment int grer les connaissances d couvertes dans les mo d les repr sentant la connaissance du domaine Quelles techniques mettre en place pour y arriver 1 3 D COUVERTE DE CONNAISSANCES UTILES 9 Entreprise Expert IO Expert fouille de donn es Donn es IO et retour d exp rience programmes similaires Pr parer la fouille de donn es M thodes et outils pour la fouille de donn es Mod liser le ph nom ne des IO l Mod le de pr diction taux d lO Fic 1 3 Pr sentation de l approche envisag e pour la d couverte de facteurs contri buant aux IO 1 3 D couvrir des connaissances utiles l expert partir du retour d exp rience Nous avons introduit l expression d couverte de connaissances utiles l expert Avant de continuer il convient d expliciter cette formule que l on emploiera fr quem ment tout au long de ce document Plut t que de donner une d finition g n rale on pr f re faire le lien avec notre cas d application La d finition que l on propose se d compose en plusieurs parties puisqu elle fait intervenir les termes de connaissance et d utilit ainsi que l action d couvrir 1 3 1 Connaissance Une connaissance peut tre vue en tant qu objet permettant
188. suite le chapitre 2 est l occasion de pr senter le cadre des r gles d associa 2 Introduction tion les repr sentations condens es ainsi que les techniques actuelles pour le post traitement de la collection de r gles extraites On y d taille plus particuli rement l approche qui a initi nos travaux de recherche savoir les travaux de S Jaroszewicz JS04 Notre approche reposant sur la technique des r seaux bay siens ce chapitre donne galement l opportunit d introduire cette technique utilis e ici pour capturer et exploiter les principales d pendances du domaine Le chapitre 3 d crit les travaux r alis s il reprend les diff rents points de notre approche et les principales contributions sur les deux axes qui sont l analyse de r gles d association et l ing nierie des connaissances Ces travaux sont illustr s et valid s sur un exemple exp rimental issu de la litt rature des r seaux bay siens le r seau VisitAsia Nous verrons ensuite au chapitre 4 un application pratique de notre approche sur les donn es d interruptions op rationnelles Nous tirerons les conclusions quant aux limites actuelles rencontr es sur des donn es r elles Enfin le chapitre 5 pr sente une discussion dans laquelle nous replacons nos contri butions dans le cadre de la d couverte de r gles d association et de l ing nierie des connaissances et nous d gageons quelques perspectives Chapitre 1 Cadre de
189. t 2 2 6 Conclusion La g n ration d itemsets par le biais d un parcours niveau par niveau exploitant uniquement la contrainte de fr quence minimale n est pas efficace sur des jeux de don 2 3 REDONDANCE DES R GLES FR QUENTES ET VALIDES 31 n es de r els L approche de type APRIORI a n anmoins t populaire car les crit res utilis s fr quence et confiance semblent faciles mettre en place et interpr ter L algorithme en lui m me demeure int ressant car il est l impl mentation d un algo rithme g n rique de parcours niveau par niveau pour la contrainte de fr quence simple mettre en place et adapter pour d autres contraintes anti monotones Nous avons aussi vu qu il tait n cessaire de donner l utilisateur les moyens de choisir d autres crit res prenant en compte la nature particuli re des r gles d associa tion tout en tant les plus adapt s au probl me trait La visualisation et le classement des r gles sur la base de diff rents crit res est une piste int ressante Cependant l ap proche classique conna t plusieurs limitations que nous abordons dans les sections suivantes Les algorithmes qui suivent cette approche ne sont pas efficaces sur des donn es fortement corr l es et ou des seuils de fr quence int ressants pour l utilisa teur Les r gles obtenues sont tr s nombreuses La d couverte de r gles r ellement int ressantes est donc
190. t tre int ressant de mod liser certains at tributs sous la forme d une hi rarchie Un exemple simplifi tir de notre cas d ap 2 4 EXPLOITER LA SUBJECTIVIT 41 plication est pr sent dans la figure 2 4 Avion Syst mes Structure Moteur Avionique Electro m canique M canique Fic 2 4 Exemple simplifi d une taxonomie pr sente pour le cas d application des donn es IO On peut noter qu au sein d une hi rarchie les items de niveau inf rieur ont des supports inf rieurs ou gaux aux niveaux qui leur sont sup rieurs Cet tat de fait peut tre avantageusement utilis par les algorithmes d extraction mais aussi dans le but d extraire des r gles d association multi niveaux L int r t est vident de cette mani re il est possible d extraire des r gles contenant des attributs plus haut niveau lorsque les attributs de bas niveau sont peu repr sent s dans les donn es On obtient des r gles plus g n rales mais que la pr sence d attributs compl mentaires peut rendre int ressantes Pour r aliser une extraction multi niveaux de r gles d association il existe plu sieurs types d approches La premi re approche est dite top down avec un seuil de support uniforme pour tous les niveaux Pour parcourir la hi rarchie des items on utilise la propri t de non monotonie de la contrainte de fr quence si un concept ou ensemble de concepts est non
191. t te le cons quent ou la partie droite Une r gle repr sente une association entre deux itemsets Cette association peut tre quantifi e par un ensemble de mesures Les deux mesures les plus classiques sont la fr quence et la confiance D finition 2 3 Support fr quence confiance Soit bd une base de donn es bi naire de sch ma Tia Items Soit S un itemset S Items une transaction t supporte S si S C t item Le support de S dans bd not supp S bd est l ensemble 22 CHAPITRE 2 D COUVERTE DE R GLES PERTINENTES des transactions de bd qui supportent S supp S bd t bd S C t item La fr quence absolue de S dans bd est d finie comme le cardinal du support de S Freq sS bd supp S bd La fr quence relative est la proportion des lignes qui supportent S par rapport len semble des enregistrements de la base supp S bd Freq 5 bd re Soit R la r gle d association telle que X Y Le support et la fr quence de R sont d finis comme le support et la fr quence de X UY La confiance de R dans bd est donn e par Freq X Y bd Freq X bd La fr quence et la confiance sont deux mesures permettant d valuer la force d une r gle Une r gle d association est dite exacte lorsque sa confiance est gale 1 conf X Y bd Exemple Consid rons la r gle AB E extraite partir de la base de donn es bd figure 2 1 Comme le cardinal du support de ABE est
192. t avec le r seau construit initialement Figure 4 3 on s aper oit que notre processus a permis l ajout de plusieurs arcs qui n avaient pas 44 CRITIQUE DES R SULTATS OBTENUS 109 Id R gle d association IntrB03 1 801120 gt Engine 89 SHH DY 0 87 2 4900 Engine 49 490000 DY CS 0 85 3 2851 nff gt Electro Mechanical 28 285134 DY CS 0 83 4 7200 DY gt Engine 72 720000 0 80 5 Avionic smoke gt 26 DY 0 80 6 4900 delay lt 1h Engine 49 490000 DY CS 0 79 7 2851 delay lt 1h gt Electro Mechanical 28 285134 DY CS 0 76 8 2793 last_ action remove Avionic 27 279334 DY remove 0 74 9 zone AP last_action nff CS delay lt 1h DY nf 0 52 9 Electro Mechanical delay gt 6h CS remove CN last _action remove 0 52 10 mel ST1 gt zone E DY last_action mel OP1 MB 0 50 TAB 4 7 R gles d associations valu es par rapport RBO3 et aux annotations t trouv s C est le cas par exemple de la d pendance logique entre les n uds Last_ action et action mais aussi pour les liens entre operator station et station_ cat Cela montre qu un oubli lors de la mod lisation initiale est rapidement d tect par notre syst me et il peut tre corrig tr s facilement De plus les pr cisions successivement apport es au RB ont non seulement permis un filtrage de plus en plus efficace d s r gles connues videntes ou non int ressantes mais cela aussi clairement facilit la d couverte de r gles pe
193. t et apr s la mise jour du RB sur le m me ensemble de r gles Il appara t clairement que les modifications effectu es permettent de filtrer toutes les r gles qui avaient t jug es int ressantes Int gt 0 75 lors de la premi re it ration Num R gle d association Intro IntrB02 1 last action swap swap 0 96 0 03 2 delay lt 1h last action swap DY swap 0 96 0 02 3 effect DY last action swap swap 0 96 0 02 4 last action swap CS DY swap 0 92 0 31 5 zone E last action swap CS DY swap 0 92 0 32 6 Electro Mechanical last action swap CS DY swap 0 91 0 25 7 delay lt 1h last action swap CS DY swap 0 95 0 02 8 last _action mel OP1 MB zone E DY mel ST1 0 94 0 50 9 last action swap CS MB DY swap 0 92 0 26 10 Electro Mechanical last_action nff CS MB DY nf 0 91 0 21 TAB 4 4 Evolution de la mesure d int r t avant et apr s modification RBO1 et RB02 Le tableau pr sente quant lui les dix meilleures r gles selon la nouvelle valeur d int r t Des 408 jug es int ressantes la premi re it ration il ne reste plus que 39 r gles telles que Intrgo2 gt 0 75 En fait ce seuil nous a servi dans le but de composer un jeu de r gles talon que l on va suivre tout au long du processus de fouille l expert lui peut s int resser un ensemble un peu plus vaste de r gles en pratique les r gles dont l int r t est sup rieur 0 25 Cette nouvelle
194. t une propri t locale des donn es qui ne se v rifie peut tre que sur quelques individus enregistrements et ou pour quelques variables Il peut s agir par exemple d un point d inflexion sur une courbe de r gression d un en semble d l ments prenant des valeurs inhabituelles dans certaines conditions etc De m me que pour les mod les on peut rechercher des motifs pour leur aspect descriptif ou leur capacit d inf rence Pour illustrer ces deux approches les auteurs du livre Principles of Data Mi ning proposent une analogie avec le domaine de la compression de donn es Prenons un metteur E qui doit envoyer une image ou des donn es J un r cepteur R Il y a deux strat gies possibles a envoyer toutes les donn es pirels de l image 1 ou b envoyer une version compress e de cette image un r sum en quelque sorte 14 CHAPITRE 1 CADRE DE TRAVAIL Retour d exp rience Expert Construction d un D couverte de mod le de connaissance connaissances F1G 1 5 Collaboration des approches mod les et motifs La fouille de donn es au sens large correspond la seconde approche la compression est r alis e par le biais de techniques de fouille de donn es soit en repr sentant les donn es d origine en tant que mod le soit mais ce n est pas exclusif en identifiant les caract ristiques inhabituelles des donn es par le biais de motifs Prenons le cas d
195. ta mining SDM 02 2002 Mohammed Javeed ZAKI et M OGIHARA Theoritical foundations of association rules In Proceedings of the DMKD Workshop on Research Issues in Data Mining and Knowledge Discovery pages 7 1 7 8 1998 Mohammed Javeed ZAKI S PARTHASARATHY M OGIHARA et W LI New algorithms for fast discovery of association rules In Proceedings of the KDD conference pages 283 286 1997
196. te afin de r duire autant que possible la dur e du cycle de d veloppement Une des cons quences de cette approche est que les performances op rationnelles de l avion doivent tre estim es en amont du processus de conception de telle fa on que les exigences du client puissent piloter la conception du produit Une interruption op rationnelle IO arrive lorsqu un probl me technique panne dysfonctionnement emp che un avion de d coller lors d une mission au moins quinze minutes apr s l heure de d part initialement fix e Ces v nements sont tr s impor tants pour les compagnies a riennes car les co ts engendr s sont loins d tre n gli geables Ainsi tr s t t dans le processus de conception de l avion les ing nieurs a ronautiques doivent r aliser une estimation r aliste de la fr quence des interruptions op rationnelles qui se v rifiera lorsque l avion sera en op ration Ces pr dictions ainsi qu un ensemble de contraintes sp cifiques initialisent guident et valident les choix 95 96 CHAPITRE 4 APPLICATION PRATIQUE de conception Pour cela les ing nieurs utilisent un outil qui impl mente un mod le stochastique int grant tous les param tres qui sont connus pour avoir un impact sur la fr quence des interruptions op rationnelles Cet outil est calibr et configur partir du retour d exp rience des avions en service dont les syst mes et les quipements ont des caract ristique
197. telle que pr sent e dans la figure 3 10 Ainsi si l on ne consid re que les attributs et non pas les couples attribut valeur toute annotation d une r gle d association R X Y se pr sente sous la forme d une sous partie X Y de R telle que X C X Y CY et card Y 1 Le but de cette notation est de permettre l expert de distinguer la nature des 3 6 LE R LE DE L EXPERT DANS LE PROCESSUS DE D COUVERTE 85 liste annotation liste annotation annotation annotation annotation liste l ment gt l ment categorie liste l ment liste l ment et l ment l ment l ment attribut attribut valeur categorie K probabilit NV NP 1 Fic 3 10 Grammaire BNF pour l annotation des r gles d association d pendances exprim es dans les r gles dans le cadre de la d couverte de r gles d as sociation pertinentes Les d pendances et donc les annotations peuvent tre de quatre types K La r gle contient une association connue de l expert mais non prise en compte par la mod lisation actuelle du r seau bay sien Il est alors possible de modifier la structure du RB afin d int grer la notion de causalit l origine de ce motif Vit ration suivante du processus l utilisateur ne verra plus appara tre ce type de r gles car elles seront jug es inint ressantes NV L annotat
198. tes les relations du type ata4d ata2d ata6d ata2d ata4d etc Un autre exemple d annotation de type K est l annotation operator station station _ cat qui repr sente une information qui n est pas mod lis e dans le RB mais qui est connue de l expert L expert remarque que la r gle n 2 tableau 4 5 a une valeur d int r t lev e alors qu elle repr sente une information qui a priori est d finie dans le RB Cela est d au 4 3 EXPERIMENTATIONS REALISEES 107 fait que nous avons r alis un apprentissage automatique des tables de probabilit s jointes L algorithme utilis ayant naturellement tendance 4 lisser la distribution des probabilit s certains cas peuvent para tre int ressants alors que l expert a explicite ment mod lis la d pendance qu ils repr sentent Pour y rem dier une annotation de type NP est r dig e concernant cette r gle la diff rence des annotations de type NV le motif repr sente bien une d pendance valide mais celle ci ne fait pas sens par rapport aux objectifs de recherche de l expert On ne souhaite pas non plus r valuer les probabilit s associ es la variable Ata6d 801120 car la r gle n 1 ne fait que mettre une sp cificit du jeu de donn es utilis Cette particularit n a pas lieu d tre explicitement prise en compte dans le RB on choisit donc de signaler ce motif comme tant non pertinent On verra l it ration n 3 de notre p
199. ti nentes partir d un ensemble de donn es on est capable d extraire un ensemble de motifs d crivant les particularit s locales des donn es Cependant l tude de ces r sultats d extraction se r v le souvent laborieuse de part la complexit des motifs manipul s et de part le manque d outils qui permettraient de faciliter leur analyse Dans un premier temps nous avons tudi une g n ralisation des approches pour la g n ration de r gles d association non redondantes Cela nous a permis de travailler a partir d ensembles concis ne contenant pas de redondance intrins que Puis nous avons propos la mise en place d un processus de d couverte de connaissance qui int gre la d finition et l exploitation d un r seau bay sien pour faciliter l analyse de r gles extraites L volution de ce mod le est facilit e par la d couverte de r gles pertinentes elles m mes rendues plus accessibles gr ce l volution du mod le Nous avons galement d fini le r le et l importance de l expert au sein de ce processus Enfin nous avons montr l application de nos propositions au domaine des interruptions op rationnelles dans l industrie a ronautiques Mots cl s Extraction de connaissances ing nierie de la connaissace r gles d associaiton r seaux bay siens R sum en anglais Abstract The study of an operational process often runs up against the analysis of hetero geneous and la
200. tie droite de cette r gle sachant que l on observe les attributs de la partie gauche Pour une r gle d association R X Y cette mesure d int r t s crit Int R conf a R conf R Poal X U Y Poal X o confial R 3 5 EXPLOITATION D UN R SEAU BAYESIEN 81 m et confs R p VilXi Xi Xn i l Exemple Pour illustrer le calcul de cette formule prenons l exemple de Visit Asia et son r seau RB_ ref tel qu il est pr sent dans la figure 3 8 page 72 A partir de donn es disponibles sur le domaine nous extrayons titre d exemple les r gles d association de la table Num R gle d association confpq Confro ref 1 Dyspnea VisitAsia XRay 0 98 0 86 2 Bronchitis Cancer Dyspnea Smoking TbOrCa XRay 0 97 0 07 TAB 3 3 Exemples de r gles d association extraites sur Visit Asia partir de RB_ ref Commen ons par expliciter le calcul de Int sur la r gle 1 COnf6 ref p Xray Abnormal Dyspnea Present Visit Asia Visit Les calculs d inf rence bay siennd nous donnent alors confrg ref 0 24 La confiance calcul e partir des donn es tant de conf 4 0 98 on a Int 0 98 0 24 0 74 La r gle est donc jug e valide et potentiellement int ressante puisqu elle repr sente un v nement qui est statistiquement relativement rare Imaginons maintenant que l on extraie la m me r gle mais cette fois les n uds VisitAsia et
201. tion de r gles extr mement compacte 3 5 Exploitation d un r seau bay sien pour la d couverte de r gles d association pertinentes 3 5 1 D finition d une mesure de pertinence des r gles vis vis d un r seau bay sien Concernant les r gles d association nous savons qu il peut tre tr s tentant de vouloir les interpr ter comme une formulation de la causalit entre deux ensembles de variables Mais pour d terminer si cette notion de causalit existe r ellement il nous manque des informations contextuelles que les donn es seules ne peuvent pas fournir La premi re utilisation du RB est l inf rence qui consiste calculer des probabi lit s conditionnelles d v nements reli s les uns aux autres par des relations de cause 80 CHAPITRE 3 LE TRAVAIL DE RECHERCHE effet Un r seau bay sien mod lis avec soin permet de d crire et donc de mesurer de mani re quantitative le lien de causalit pouvant exister entre deux variables Ainsi on voit qu il peut tre int ressant de comparer la mesure de causalit estim e par le biais de la confiance d une r gle d association avec celle qui est mod lis e dans le RB Soit bd une base de donn es binaires de sch ma Tia Items tel que Items A1 42 An Soit RB un r seau bay sien d fini par un ensemble de noeuds correspondants aux attributs de Items et par E C Items x Items l ensemble des arcs du graphe chaque n ud o
202. tions BD base de donn es Contraintes Fr quence Confiance syntaxiques minimale minimale Fia 3 3 Activit Extraire les r gles d associations L extraction se d roule en deux tapes La premi re consiste extraire une repr sentation condens e des itemsets fr quents L outil que nous utilisons pour cette t che est AC like d velopp par J Besson Il s agit d une impl mentation de l algorithme MIN EXx Cet algorithme calcule une repr sentation utilisant les itemsets 6 libres et leur fermeture La deuxi me tape repose sur une de nos contributions savoir la g n ration de L R ensemble non redondant de r gles d association partir de ce type de l ensemble des 6 libres fr quents et de leur fermeture Nous calculons a posteriori les contraintes syntaxiques ainsi qu un ensemble de mesures d int r ts objectives qui serviront lors de l tape d analyse des r sultats Nous avons voqu dans l tat de l art des algorithmes capables de pousser les contraintes 3 2 PROCESSUS DE D COUVERTE DE CONNAISSANCES KARD 67 syntaxiques c est dire de n extraire que les r gles qui se conforment aux contraintes Pour notre application cette optimisation ne s est pas r v l e cruciale Exploitation des d pendances du domaine On cherche s lectionner des r gles pertinentes pour l expert du domaine L in formation port e par les r gles d association extraites est do
203. ture de RB tudi e Puis elles recherchent la structure qui donnera le meilleur score dans l espace de recherche des graphes acycliques orient s Une approche exhaustive est impossible en pratique en raison de la taille de les pace de recherche En effet le nombre de structures possibles partir de n n uds est super exponentiel Par exemple pour 10 n uds le nombre de structures possibles est de 4 2 x 1018 Pour r soudre ce probl me un certain nombre d heuristiques ont t propos es Elles ont pour but de restreindre cet espace l espace des arbres MWST d ordonner les n uds pour limiter la recherche des parents possibles pour chaque variable K2 ou d effectuer une recherche gloutonne GS En partant du principe que plusieurs structures encodent la m me loi de probabi lit quivalence de Markov et poss dent le m me score d autres m thodes proposent de parcourir l espace des quivalents de Markov espace toujours super exponentiel mais poss dant de meilleures propri t s Enfin il existe aussi des m thodes permettant d incorporer des connaissances a priori sur le probl me r soudre en d taillant le plus possible les contraintes que l on souhaite formuler sur l espace de recherche La litt rature concernant cette probl matique est trop abondante pour figurer ici Par cons quent on pourra se reporter pour une lecture plus d taill e de ces diff rentes approches ainsi qu pou
204. uctive database framework In DaWak 99 Proceedings of the First International Conference on Data Warehousing and Knowledge Discovery pages 293 302 London UK 1999 Springer Verlag Bernadette BOUCHON MEUNIER et Christophe MARSALA Logique floue principes aide a la d cision Editions Hermes 2003 Sergey BRIN Rajeev MOTWANI Jeffrey D ULLMAN et Shalom TSUR Dynamic itemset counting and implication rules for market basket data In Joan PECKHAM diteur SIGMOD 1997 Proceedings ACM SIGMOD International Conference on Management of Data May 13 15 1997 Tucson Arizona USA pages 255 264 ACM Press 05 1997 Sergey BRIN et Lawrence PAGE The anatomy of a large scale hyper textual Web search engine Computer Networks and ISDN Systems 30 1 7 107 117 1998 M BRODIE I RISH et S MA ntelligent probing A cost effective ap proach to fault diagnosis in computer networks IBM Systems Journal 41 2002 Yves BASTIDE Rafik TAOUIL Nicolas PASQUIER Gerd STUMME et Lotfi LAKHAL Mining frequent patterns with counting inference SIGKDD Explorations 2 2 66 75 D cembre 2000 Yves BASTIDE Rafik TAOUIL Nicolas PASQUIER Gerd STUMME et Lotfi LAKHAL Pascal un algorithme d extraction de motifs fr quents Techniques et Science Informatiques 21 1 65 95 2002 Bruno CR MILLEUX et Jean Fran ois BOULICAUT Simplest rules cha racterizing classes generated by free sets In SPRINGER
205. ue R Taouil et N Pasquier ont montr qu il tait possible de g n rer une repr sen tation non redondante des r gles d association partir des itemsets ferm s fr quents et des itemsets libres aussi appel s g n rateurs Dans le cas des travaux de N Pasquier cette repr sentation contient un ensemble de r gles d association ayant une partie gauche minimale et une partie droite maximale au sens de l inclusion Ces r gles sont appel es r gles d association min maz Les auteurs pensent que ce type de repr sentation est le plus pertinent car l information pr sent e par les r gles est la plus g n rale possible Les d finitions qui suivent sont inspir es de PTB 05 SL impl mentation de M1n Ex utilis e est le programme AC like d velopp par J r my Besson Il est disponible l adresse suivante http liris cnrs fr jeremy besson AC like AC like html 2 3 REDONDANCE DES R GLES FR QUENTES ET VALIDES 37 D finition 2 15 R gle d association g n rale Une r gle d association R X gt Y est plus g n rale qu une r gle R X Y si les conditions suivantes sont r unies 1 F R F R et conf R conf R 2 XcCX eYoy R est alors une sur r gle de R et R une sous r gle de R Afin d illustrer ce propos examinons les r gles pr sent es dans le tableau Elles ont t extraites 4 partir de la base de donn es bd pr sent e pr c demment tableau 2 1
206. ue joue l expert dans notre approche ainsi que le syst me d annotations propos 3 6 1 N cessit des annotations La t che de l expert est d analyser et d interpr ter les r gles extraites Pour cela on met sa disposition un syst me d annotation qui va lui permettre de porter un jugement sur les r gles et en particulier sur les motifs qui la composent Par motif d une r gle d association R X Y on entend ici une sous r gle d association M X Y telle que X C X et Y X X UY En pratique il n est pas rare de retrouver un motif d j connu ou inint ressant dans un grand nombre de r gles d association L expert sait reconnaitre ces motifs et il nous est apparu n cessaire de lui donner les moyens de les indiquer par le biais d une syntaxe bien d finie Ces annotations vont avoir un int r t double d une part le moteur d affichage des r gles va pouvoir rendre compte de la nature des diff rents motifs qui composent chaque r gle d autre part ces annotations sont utilis es pour faciliter la mise jour du mod le 3 6 2 Diff rents types d annotation Un des probl mes pour rendre possible l tape d annotation des r gles est la d finition d une syntaxe rapidement assimilable et permettant de d crire les diff rentes informations apport es par une r gle d association Pour cela nous avons sp cifi une notation sous la forme d une grammaire BNF
207. une connaissance attendue Ainsi dans le cas o une base de donn es enregistre les achats de clients d une grande surface on s attend voir appara tre un certain nombre de r gles d crivant des achats typiques Comme par exemple la r gle suivante Bi re Chips 44 CHAPITRE 2 D COUVERTE DE R GLES PERTINENTES La d couverte de telles associations que l on suppose ici d j connues va tre nuisible l tape d analyse des r sultats car aucune information nouvelle n est pr sent e l utilisateur 2 Une r gle d association peut aussi faire r f rence des attributs ou des combi naisons d attributs inint ressants La r gle Pantalon Chemise est jug e inutile dans le cas o l utilisateur ne s int resse qu aux r gles contenant au moins un produit alimentaire 3 Les r gles peuvent tre redondantes entre elles Pantalon Chausettes Chemise Pantalon Chausettes Calecon Chemise 4 Enfin une r gle d association peut contenir des informations valides et po tentiellement int ressantes du point de vue de l expert comme la r gle Bi re Couches Cette premi re nomenclature des r gles d association met en vidence la n cessit de bien s parer les diff rents niveaux de traitement qu il va falloir mettre en place si l on veut pouvoir converger rapidement vers des r gles pertinentes En effet si on peut se d barrasser des r gles d crivant les conn
208. uptions op rationnelles pour le compte d un grand constructeur a ronautique nous nous sommes particuli rement int ress s l laboration d une boucle vertueuse permettant la d couverte de r gles d association int ressantes L approche que nous proposons est bas e sur l extraction d une collection de r gles non redondantes aux propri t s particu li res l utilisation d un r seau bay sien pour la mod lisation des d pendances connues du domaine d application la d finition et l exploitation de mesures d int r t prenant en compte les connais sances du domaine l exploitation d annotations r alis es par l expert sur les r gles d association Ces diff rents points sont regroup s au sein d un processus it ratif dont le principal objectif est d arriver faciliter la d couverte de r gles d association int ressantes mais aussi par effet de bord permettre la d finition et la consolidation d un r seau bay sien qui capture les principales d pendances du domaine Tout d abord le premier chapitre introduit le contexte industriel des travaux de la th se l savoir l aide l analyse des donn es d interruptions op rationnelles On y pr sente aussi les diff rents niveaux de la probl matique aussi bien du point de vu industriel qu au niveau de l ing nierie des connaissances et de la fouille de donn es ainsi que les voies que nous avons d cid d aborder En
209. uvelles 116 CHAPITRE 5 CONCLUSION Annexe A Pr sentation de l application A Server interface amp Events Rules Bayesian Network Events from ARFF file C experiments datalasia 100000 arff Events from database h27 0 0 1 3306 Table Query file Choose file Username sos D eme O C Disable preliminary computations Fic A 1 Interface de configuration du serveur onglet permettant la configuration des sources de donn es er interface ole X eee ae Events Rules Bayesian Network oss a ere eee a ere Rules from a file Choose file C Save rules in a file gt Choose file C Disable preliminary computations Fic A 2 Interface de configuration du serveur onglet de configuration de l algo rithme d extraction 117 118 ANNEXE A PR SENTATION DE L APPLICATION Bayesian Network Learn bayesnet from events RepeatedHillClimber l Create bayes net with unlinked no Load bayesnet from a XML Bif File Choose file Save bayesnet to a file C Disable preliminary computations Fic A 3 Interface de configuration du serveur onglet permettant la configuration du r seau bay sien initial 4 Annotation de r gles es Envoyer les annotations Supprimer une annotation Montrer les annotations
210. uverte de connaissances partir de l extraction et de l tude de r gles d asso ciation aux propri t s particuli res Les difficult s fr quemment rencontr es lors de la phase d analyse nous ont amen s r fl chir aux m thodes et techniques n cessaires au d roulement optimal de cette tape cruciale au sein du processus de d couverte de connaissances Nous nous sommes notamment int ress s la d finition l exploitation et l volution d un r seau bay sien comme mod le des principales d pendances du domaine 3 1 Positionnement par rapport l tat de l art contri butions envisag es Concernant la d couverte de r gles d association pertinentes diff rentes approches de la litt rature ont t d taill es au Chapitre B Les probl mes li s aux performances des extracteurs ainsi qu la compacit des repr sentations obtenues i e et donc indirectement la redondance des r gles pr sent es ont t r solus Parmi les probl matiques de recherches demeurant ouvertes nous avons choisi d aborder les axes suivants 1 La g n ration d un ensemble concis de r gles partir des itemsets 6 libres fr quents et de la 6 fermeture 2 L exploitation d un r seau bay sien pour faciliter l analyse et la d couverte de r gles d association pertinentes 3 La prise en compte des probl matiques issues de l ing nierie de la connaissance au sein d un processus de d
211. va d finir la fronti re positive respectivement n gative de l ensemble des itemsets fr quents D finition 2 6 Fronti re positive n gative Soit S une collection d itemsets La fronti re positive de S est la collection des itemsets les plus sp cifiques de S Bd S mar lt S p S wES y lt u O lt est une relation d ordre partiel sur les itemsets telle que Vitemset p est plus g n ral que u sip lt u La fronti re n gative de S est la collection des motifs les plus g n raux qui ne sont pas dans S Bd S ming 2 S p SI uw ES x p APRIORI est l algorithme fondateur de cette cat gorie d autres contributions ont suivi par la suite En effet le parcours du treillis peut se faire en largeur ou en pro fondeur Dans les deux cas on peut proc der par comptage direct de la fr quence de chaque itemset dans la base ou proc der par intersection des deux itemsets qui constituent litemset candidat Diff rentes am liorations ont t propos es dans la litt rature afin d acc l rer l tape de construction des ensembles fr quents dans cer taines situations Nous pr sentons de mani re chronologique les plus significatives d entre elles Premi re am lioration l algorithme AprioriTID AS94 vise limiter les acc s directs la base de donn es en pratique les temps d acc s s av rent d autant plus p nalisant que l algorithme classique effectue une passe sur la
212. veau k d s qu un itemset a atteint le seuil de fr quence on introduit les itemsets candidats de niveau k 1 qu il contribue g n rer ce qui diminue le nombre de passes n cessaires sur la base Autre approche pour l extraction des itemsets fr quents Eclat effectue cette fois un parcours du treillis en profondeur par intersection rapide des tid listes La proc dure est interrompue d s que l on est s r que l itemset candidat ne peut plus tre fr quent L algorithme FP Growth am liore quant lui les capacit s d extraction des itemsets fr quents ainsi que les performances globales en associant une structure sp cifique des donn es de transaction intitul e FP tree avec une recherche en profondeur dans le treillis En parall le ces diff rentes propositions un autre axe de recherche a t tu di Il s agit de l extraction d une partie g n ratrice des itemsets fr quents et de leur support les repr sentations condens es Ces recherches ont abouti a diff rents algo rithmes On citera notamment Close et son d riv A Close PBTL99al puis algorithme Pascal fond sur le comptage par inf rence des ensemble cl s Les ensembles ferm s et les ensembles libres ont aussi t tudi s par J F Boulicaut et al qui ont tendu ces notions a celles d ensembles 6 ferm s et 6 libres Les approches visant calculer des repr sentations condens es ont l avantage de r duire les tem
213. vons propos une approche pour faciliter la t che d ana lyse des r sultats d extraction de r gles d association Nous avons d abord pr sent dans le chapitre 1 le cadre g n ral de la d couverte de connaissances ainsi que le contexte industriel qui a motiv les travaux de th se Dans un processus op rationnel le mod le et les donn es voluent tous les deux dans le temps On constate g n ra lement un d calage entre ces deux entit s Parfois les diff rences sont connues des experts parfois elles restent identifier Pour ce deuxi me cas de figure la mise en place de techniques de d couverte de la connaissance est int ressante En particu lier nous nous sommes int ress s l utilisation d un r seau bay sien pour faciliter la d couverte de r gles d association pertinentes sur de grands volumes de donn es Le deuxi me chapitre a t l occasion de r aliser un tat de l art sur les techniques actuelles pour l extraction de r gles d association Nous avons mis en avant les pro bl mes ouverts sur le domaine savoir les limites des approches dites objectives pour la d couverte de r gles r ellement int ressantes Nous avons aussi vu que mal gr les r centes propositions sur cette probl matique il n y avait pas de prise de recul visant tablir une r flexion sur une utilisation plus syst matique des connaissances du domaine ainsi que sur la d finition du r le de l expert au sein
214. x taux d interruptions op rationnelles partir de grandes bases de donn es d crivant les retards des appareils en service Dans notre cas il n y a pas de classes proprement parl tous les enregistrements repr sentent des interruptions op rationnelles expert souhaite simplement voir ap para tre des relations entre les attributs de la base caract ristiques de situations de retard On se situe donc dans un contexte non supervis le processus de fouille n est pas n cessairement dirig par le choix d une classe d attribut ou par des hypoth ses prises par l expert De plus la taille et la nature des donn es est aussi un facteur d terminant dans le choix des techniques utilis es Les r gles d association sont un exemple de motif local particuli rement tudi dans la litt rature relative la fouille de donn e On reviendra plus en d tails sur les arguments qui ont motiv leur utilisation le postulat de d part tant que face un probl me de fouille de donn es non supervis e il est tr s raisonnable de penser que les r gles d association peuvent tre utilis es pour permettre la d couverte de connaissances utiles l expert Les r gles d associations pr sentent l avantage d tre facilement compr hensibles par un utilisateur ayant re u un minimum de sensibilisation Une fois g n r es luti lisateur peut donc tre relativement autonome pour la phase d analyse et de post traiteme
215. ximation de la fr quence de la partie droite de la r gle et donc indirectement de la mesure de confiance n est pas r dhibitoire pour l utilisateur Contexte itemsets 6 libres fermeture a pr sent une collection de r gles non redondantes g n r es a partir des itemsets libres et des ferm s Cependant dans certains cas donn es fortement cor r l es n cessit d extraire a des seuils de fr quence tr s faible il n est pas possible de g n rer l ensemble des itemsets libres Ainsi nous avons choisi d tudier d autres types de repr sentation pour la g n ration de r gles non redondantes offrant plus de souplesse vis a vis de la contrainte de fr quence Pour cela nous allons commencer par introduire rapidement les principales notions relatives l extraction de r gles non redondantes Consid rons la base de donn es suivante Tia tiitem A C D B C E A B C E BE A B C E B C E D ND FH TAB 3 1 Exemple de base de donn es Des r gles d association utilisant les itemsets d libres ont t introduites pour la premi re fois dans il s agit des r gles dites 6 fortes Le param tre est cens tre petit par rapport au seuil de fr quence utilis pour l extraction ce qui assure des r gles forte confiance i e peu d exceptions sur la partie droite La d finition d une r gle d forte est la suivante D finition 3 1 R gle 6 forte t
216. xo nomy quantitative database and mining generalized association rules Intell Data Anal 9 2 207 217 2005 P SMYTH et R M GOODMAN An information theoretic approach to rule induction from databases IEEE Transactions on Knowledge and Data Engineering 4 4 301 316 1992 P SMETS Data fusion in the transferable belief model In in Proceedings of the Third International Conference on Information Fusion 2000 Ashoka SAVASERE Edward OMIECINSKI et Shamkant B NAVATHE An efficient algorithm for mining association rules in large databases In Proceedings of the 21th International Conference on Very Large Data Bases 1995 K SATOU G SHIBAYAMA T ONO Y YAMAMURA E FURUICHI S KUHARA et T TAKAGI Finding association rules on hetero geneous genome data In Proceedings of the Pacific Symposium on Biocomputing pages 397 408 1997 Avi SILBERSCHATZ et Alexander TUZHILIN What makes patterns interesting in knowledge discovery systems IEEE Transactions on Knowledge and Data Engineering 8 6 970 974 1996 Ansaf SALLEB Teddy TURMEAUX Christel VRAIN et Cyril NORTET Mining quantitative association rules in a atherosclerosis dataset In PKDD Discovery Challenge 2004 co located with the 6th European Conference on Principles and Practice of Knowledge Discovery in Databases pages 98 103 september 2004 Bo THIESSON Christopher MEEK et David HECKERMAN Accelerating em for large datab

Découvertes de motifs pertinents par l - LIRIS

Contents

Download Pdf Manuals

Related Search

Related Contents

D&eacute;couvertes de motifs pertinents par l - LIRIS

Contents

Download Pdf Manuals

Related Search

Related Contents

Découvertes de motifs pertinents par l - LIRIS