Home

Découvertes de motifs pertinents par l`implémentation d`un réseau

1. 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 a Ek PSS Re ne CI Gl eS ER 41 ig Re Bk AO OR hh we a LU AR ee es 48 2 6 chelle de probabilit 53 3 1 Activit Processus de d couverte de connaissances 66 3 2 Activit Mod liser les d pendances du domaine 67 ctivit Extraire les r gles d associations 68 3 4 Activit Exploiter le r seau bay sien 69 3 5 Activit Analyser les r gles d association 70 Vii 3 6 Activit Mettre jour le r seau bay sien 71 3 7 Proposition de processus de d couverte de connaissances 73 3 8 R seau bay sien de r f rence sur le domaine Visit Asia RB ref 74 DR D ee WOR CL We he eh a ow a nn 75 Wh hae A 86 3 11 R seau bay sien Visit Asia RB_0 utilis pour la 187 it ration du Seok She Wb a he eo OR 91 ee 99 4 2 Extrait de la requ te SQL pour le pr traitement des donn es 100 4 3 R seau bay sien initial RBO1 sur les donn es IO 103
2. 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 ts 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 D 0 2 TAB 2 2 Exemples de r gles d asso
3. tableau 2 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 MinMaxEzxact 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 s
4. Tomasz Imielinski and Heikki Mannila A database perspective on knowledge discovery Communications of the ACM 39 11 58 64 1996 Tomasz Imielitiski and 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 PhD thesis Uni versit Lyon I INSA de Lyon december 2002 Michael I Jordan Zoubin Ghahramani Tommi Jaakkola and 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 and 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 and Marta Vomlelova The sasco methodology for troubleshooting complex systems S Jaroszewicz and 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 May 2002 BIBLIOGRAPHIE 129 JS04 JS05 K1e99 KMRt 94 Kra98 LAK 01 LHM99 LK9S LMV 04 LPT04 LS88 Szymon Jaroszewicz and Dan
5. 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 58 CHAPITRE 2 DECOUVERTE DE REGLES PERTINENTES 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 a 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 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 par tudier les
6. 00 2000 Ramesh C Agarwal Charu C Aggarwal and 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 Imieli ski and Arun Swami Mining associa tion rules between sets of items in large databases In Peter Buneman and Sushil Jajodia editors Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data pages 207 216 Wa shington D C 26 28 1993 J r me Az and 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 and 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 Toivo nen and A Inkeri Verkamo Fast discovery of association rules chap ter 12 pages 307 328 American Association for Artificial Intelligence Menlo Park CA USA 1996 Rakesh Agrawal and Ramakrishnan Srikant Fast algorithms for mining association rules In Jorge B Bocca Matthias Jarke and Carlo Za niolo editors Proceedings of the 1994 VLDB International Conference on Very Large Data Bases pages 487 4
7. 78 CHAPITRE 3 LE TRAVAIL DE RECHERCHE Plus g n ralement 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 0 soit au moins strictement inf rieur Freq S card X En effet dans le cas contraire cela signifierait que la 6 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 Etude 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 a des seuils de fr quence relativement bas BBROO Maintenant quand 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
8. 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 Nowe A X X l QMV de 21 A i zk pa i Ty i j k S Ni jk o Ni jk 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 donn 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 TMHOI L algorit
9. 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 105 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 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 ST alors on observe souvent l en semble des faits suivant on se trouve au moyen orient zone ME l interruption 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 l 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 annotation L tape suivante de notre processus consiste pour l expert du domaine tudier les r gles g n r es p
10. 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 perti 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
11. 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 a 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 de la fouille de donn es et de l ing nierie de la connaissance afin de faciliter la
12. 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 4 5 pr sente quant a 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 Int rgo2 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 phase d
13. 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 consignes 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 pouvaient prendre B 4 3 EXPERIMENTATIONS REALISEES 103 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 A partir de cette structure et des donn es d IO nous effectuant un apprentissage automatique des tables de probabilit s conditionnelles grace 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 BBRO0 Les param tres utilis s sont Freq 100 et 6 20 Sur notre jeu de donn es le temps d extracti
14. quipement a plus de chances d entrainer 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 Enfin nous avons demand
15. 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 ainsi pour une lecture plus d taill e de ces diff rentes approches on pourra se reporter NWL 04 ainsi qu pour une compara
16. 3 2 R gles extraites sur bd pour minfreq 2etd 1 79 3 3 Exemples de r gles d association extraites sur Visit Asia partir de TU TR le 2 ee be es 2 83 3 4 Exemples de r gles d association fictives sur Visit Asia 87 3 7 Annotations collect es sur les r gles Visit Asia 93 4 2 R gles ayant la plus forte valeur d int r t vis vis de RBO1 4 3 Exemple d annotations collect es la premi re it ration du processus 44 Evolution de la mesure d int r t avant et apr s modification RBO1 et Peo sor adere ook RE ep Oe ho eee a a A 4 5 R gles d association ayant la plus forte valeur d int r t vis vis de RBO2 4 6 Exemples d annotations collect es la deuxi me it ration du processus 4 7 R gles d associations valu es par rapport RB03 et aux annotations Introduction Ce manuscrit pr sente nos travaux de recherche sur la d couverte de r gles d as sociation pertinentes par l exploitation d un R seau Bay sien Ces travaux sont ap pliqu s un cas d application industriel qui concerne l aide l analyse de donn es d interruptions op rationnelles dans l industrie a ronautique P P 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 interruptions op rationnelles pour le compte d un grand constructeur a ronautique nous nous sommes
17. 3 7 VALIDATION SUR LES DONNEES VISIT ASIA 89 des tables de probabilit s est un probl me d licat et cofiteux lorsque les variables manipul 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
18. 4 4 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 119 A 2 Interface de configuration du serveur onglet de configuration de l al gorithme d extraction 119 A 3 Interface de configuration du serveur onglet permettant la configura tion du r seau bay sien initial 120 A 4 Interface d analyse des r gles d association 120 A 5 Annotation de r gles d association 121 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 2 1 es one es aan de amas 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 Ne RU GA ho CNT don ee A S 38 2 6 Ensemble des r gles min max approximatives g n r es partir de bd 38 de Saha ees Hee vA ee LINE CR 76
19. Extraction de connaissances ing nierie de la connaissace r gles d associaiton r seaux bay siens Table des mati res Introductionl sas e a 8 a eG oS BREE 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 gles 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 gd ea digas 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 redond
20. agir pour nous du RB de r f rence on le d signera 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 REGLES D ASSOCIATION NON REDONDANTES 75 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
21. approche KARD Notre premi re contribution de recherche est partie du constat suivant les ap proches actuelles pour la d couverte de connaissances n exploitent pas ou peu les connaissances existantes sur le domaine d application quelles soient pr sentes de ma ni 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 foui
22. connus non valides non pertinents ou 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 et 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 71 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 la 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
23. 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 MODELES 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 crit une propri t locale des donn es qui ne se v rifie peut tre
24. quence relativement bas tout en conservant une collection de r gles extr mement compacte 3 5 Exploitation d un R seau Bay sien pour la d couverte de r gles d associations 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 effet Un r seau bay sien mod lis avec soin permet de d crire et donc de mesurer 82 CHAPITRE 3 LE TRAVAIL DE RECHERCHE 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 Ti 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 I
25. 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 OPERATIONNELLES 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 des taux d interruptions op rationnelles Concernant cette probl matique les bes
26. 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 AA07 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 vu 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 cherche d couvrir ou
27. sign s par des lettres minuscules correspondants aux attri buts Notons Pr la distribution de probabilit jointe de l ensemble d attributs J De m me notons Py la distribution de probabilit de I 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 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 TT 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 fini la fr quence d un itemset I i calcul par rapport au RB de la mani re suivante FrglI i PFP i 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 puisque l encodage d
28. un motif ou en l occurence d un itemset fr quent est d termin par sa divergence vis a vis des connaissances du domaine 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 ali ser ici un tat de l art exhaustif sur le domaine mais bien de mettre en
29. une approche pour faciliter la tache d analyse 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 ralement 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 connaissances est int ressante En particulier 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 du processus d
30. 2000 Springer Verlag Silja Renooij Probability elicitation for belief networks issues to consi der Cambridge University Press 16 255 269 2001 Jr Roberto J Bayardo and Rakesh Agrawal Mining the most inter esting 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 net works through removal of weak dependences In Proceedings of the 10th conference on uncertainty in Artificial Intelligence pages 374 382 As sociation for Uncertainty in Artificial Intelligence Morgann Kaufmann Publishers 1994 S Renooij and C Witteman Talking probabilities communica ting probabilistic information with words and numbers International Journal of Approximate Reasoning 22 169 194 1999 Ramakrishnan Srikant and Rakesh Agrawal Mining quantitative asso ciation rules in large relational tables In SIGMOD 96 Proceedings 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 and Shen Hongbin Fuzzy taxo nomy quantitative database and mining generalized association rules Intell Data Anal 9 2 207 217 2005 P Smyth and R M Goodman An infor
31. 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 and Tobias Scheffer Fast discovery of unexpected 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 PhD thesis University of Helsinki 1999 Mika Klemettinen Heikki Mannila Pirjo Ronkainen Hannu Toivonen and 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 and S S Duri Personalization of supermarket product recommendations Data Min Knowl Discov 5 1 2 11 32 2001 Bing Liu Wynne Hsu and Yiming Ma Pruning and summarizing the discovered associations In KDD 99 Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining pages 125 134 New York NY USA 1999 ACM Press D
32. CB02 CCK 00 CDLS03 CGK 02 CHM04 Chr75 Warehousing and Knowledge Discovery pages 293 302 London UK 1999 Springer Verlag Bernadette Bouchon Meunier and Christophe Marsala Logique floue principes aide la d cision Editions Hermes 2003 Sergey Brin Rajeev Motwani Jeffrey D Ullman and Shalom Tsur Dynamic itemset counting and implication rules for market basket data In Joan Peckham editor 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 and 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 and 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 and 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 and Lotfi Lakhal Pascal un algorithme d extraction de motifs fr quents Techniques et Science Informatiques 21 1 65 95 2002 Bruno Cr milleux and Jean Francois Boulicaut Simplest rules cha racterizing classes generated by 6 free sets In Springer editor Proceedings of the twenty
33. 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 4 appr hender telle quelle Ainsi on pourra la formuler de la facon 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 A 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 X Z Y 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 A nsi supposons que X et Y soient d s par s par Z et que Z soit connun et 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 l ensemb
34. Guillet Pascale Kuntz R mi Lehn and Philippe Peter Quelques crit res pour une mesure de qualit de r gles d asso ciation un exemple l intensit d implication Revue des Nouvelles Technologies de l Information RNTI E 1 2004 W R Gilks S Richardson and D J Spiegelhalter Markov Chain Monte Carlo In Practice Chapman amp Hall 1996 Bart Goethals and Mohammed J Zaki Proceedings of the IEEE ICDM Workshop on Frequent Itemset Mining Implementations FIMI 2003 Melbourne USA 2003 John D Holt and 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 and Andr Cabarbaye Applica tin 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 Technical report Microsoft Research 1995 David Heckerman Bayesian networks for data mining Data Mining and Knowledge Discovery 1 1 79 119 1997 Jiawei Han and 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 Francisco CA USA 1995 Morgan Kaufmann Publish
35. 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 est pas li mi
36. 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 48 CHAPITRE 2 DECOUVERTE DE REGLES PERTINENTES Le chemin passe par Z et est soi divergent soit en s rie au n ud Z 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 gt B gt D Le chemin A C D est convergent en C A C D e A D
37. cas o toutes les va riables Y et X sont binaires Dans ce cas l expert devra estimer 2 valeurs ce qui 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 2 5 COMMENT PRENDRE EN COMPTE LA CONNAISSANCE DU DOMAINE 753 certain 100 probable 85 attendu 75 50 50 50 incertain 25 improbable 15 impossible 0 FIG 2 6 Echelle de probabilit On peut calculer facilement la probabilit suivante p p y 1 Z2 Xi En 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 il XiEXp 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 ODW0O0 ou le diagnostic de pannes BRMO 2 Enfin le dernier type de probl me li l ing nierie des connaissances
38. d association tel que R X gt Y X C Items 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 2 on peut constater que certaines r gles sont redondantes entre elles 3 4 REGLES D ASSOCIATION NON REDONDANTES 79 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 6 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 redon
39. 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 pas de travaux formalis s sur l aide l analyse de donn es d interruptions op
40. de par Z signifie alors que la pr 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 ot le nombre d items de X est strictement sup rieur a 1 on tudie la matrice bool enne qui contient tous les r sultats des tests de d s paration entre les X et les Yj 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 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 de d s paration
41. 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 Notamment 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 A pr sent que l on dispose de techniques permettant la fois de g n rer un en semble 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 luti lisateur 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
42. des itemsets fr quents et la part importante de redondance entre les r gles et par rapport au domaine d application Ceci est d autant plus vrai lorsque les donn es sont denses ou fortement corr l es BAGOO BMUT97 On a vu qu il tait possible de g n rer un ensemble restreint de r gles d association 40 CHAPITRE 2 DECOUVERTE DE REGLES PERTINENTES La diminution du volume de r gles repr sente un premier pas pour faciliter l analyse 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 Vutilisateur Pour cela il nous apparait 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 rarc
43. et une r gle association X Y ont une repr sentation 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 associations 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 e l information quelles 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 7 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
44. formation port e par les r gles d association extraites est donc 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 P L R 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 e T d C Tpd est l ensemble des mesures objectives associ es R Tib est l ensemble des mesures subjectives associ es R partir de RB D sep et 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 8 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 70 CHAPITRE 3 LE TRAVAIL DE RECHERCHE Importance du r le de l expert Comme nous l avons pr cis l expert est situ
45. gles d association AX BY contenant ce motif Apr 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 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 74 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 90 CHAPITRE 3 LE TRAVAIL DE RECHERCHE
46. gles font tat d une association forte en terme de confiance Comme notre mesure est d pendante de la confiance la valeur d int r t reste lev mais diminue par rapport celle calcul e sur RB_ 0 3 7 VALIDATION SUR LES DONNEES VISIT ASIA 95 Num R gle d association Intrg o Intrg 1 1 Tuberculosis TbOrCa XRay 0 01 0 01 2 VisitAsia 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 96 CHAPITRE 3 LE TRAVAIL DE RECHERCHE 3 7 4 Critique des r sultats obtenus Par rapport aux objecti
47. 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 OPERATIONNELLES 5 Entreprise Ing nieur IO D finir des cibles de taux d lO 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 exploiter le retour d exp rience sur des programmes pass s pour pr dire le taux d
48. 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 la 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 processus de fouille qui selon la m thodologie propos e pr c demment Chapitre 3 aux don n es d interruptions op rationnelles 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 4 2 Mise en place du c
49. max approx 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 i e il n existe pas d itemset Z tel que X D Z D Y 2 4 EXPLOITER LA SUBJECTIVITE 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 l op rateur de 6 fermeture Pour 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 3 sera l occasion de revenir plus en d tails sur les propri t s des item sets d libres et
50. notation sous la forme d une grammaire BNF telle que pr sent e dans la figure 3 10 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 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 A X Y de R telle que X C X Y CY et card Y 1 3 6 LE R LE DE L EXPERT DANS LE PROCESSUS DE D COUVERTE 87 Le but de cette notation est de permettre l expert de distinguer la nature des 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 A l it ration suivante du processus l utilisateur ne verra plus appara tre ce type de r gles car elles ser
51. notre application a t d velopp 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 d
52. par la pr sence d un arc orient reliant le n ud VisitAsia 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 76 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
53. par le biais de contraintes sp cifi es par l utili 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 67 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 t
54. 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 Vexploitation 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 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 de la connaissance et de la fouille de donn es ainsi que les voies que nous avons d cid d aborder Ensuite le chapitre 2 est l occasion de pr senter le cadre des r gles d associa 2 I
55. 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 existants entre les diff rentes variables tudi es Les pr cisions successivement apport es au RB ont permis un filtrage de plus en plus efficace d s 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 116 CHAPITRE 5 CONCLUSION ensemble de r gles Au final la d couverte de ces d pendances et les modifications qui en ont d coul es 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 associations extraites et ainsi faciliter leur tude Ces r sultats soul vent n anmoins quelques nouvelles interrogations notamment sur la gestion des cas de faux positifs La solution actuellement apport e est uni quement vi
56. r gles 110 CHAPITRE 4 APPLICATION PRATIQUE gt Ata2d_type K gt Effect Airline_zone Station Fault Fia 4 5 R seau bay sien l issue de la deuxi me mise jour RBO3 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 comparant avec le r s
57. r seau bay sien d observer les attributs de la partie 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 confyg R conf R Pal X UY o confyg R bal Poa X et conf R ea E i 1 3 5 EXPLOITATION D UN RESEAU BAYESIEN 83 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 74 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 conf 4 conf re f 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 a partir de RB ref Commen ons par expliciter le calcul de Int sur la r gle n 1 conf ref p Xray Abnormal Dyspnea Present Visit Asia Visit Les calculs d inf rence bay siennd nous donnent alors confrp ref 0 24 La confiance calcul e partir des donn es tant de conf 4 0 98 on a Intra 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 g
58. re 90 Hohe note HA De thee ee 91 WAGE Bad Swe be eS Bae oe dla 96 97 DO Ses We he Ye Pook eit Gets He Bee 97 42 Mise en place du cadre de test 2 ee 98 4 2 1 Description du jeu de donn es 98 4 2 2 Pr traitements 100 4 2 3 Exploitation du texte librel 101 4 3 Exp rimentations r alis es 102 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 annotation 105 4 3 5 Mise jour du r seau bay sien 4 3 6 Nouvelles it rations du processus 4 4 Critique des r sultats obtenus A Pr sentation de l application 119 Table des figures 1 1 Diagramme de s quence simplifi pr sentant la probl matique du cas d application cs 44 3 4 4 4 Rw Paw ee we ee dut 5 1 2 Diagramme de s quence simplifi pr sentant la probl matique d apphcationl san i 2 amp a 22 Sew Sok Bh Rah Bee Se SAR RE 6 1 3 Pr sentation de l approche envisag e pour la d couverte de facteurs contribuant aux IO 4 4 4 eee au su sages ide ne dau 9 1 4 Processus simplifi d Extraction de Connaissances partir des Donn es 1 5 Collaboration des approches mod les et motifs
59. 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 aa e ie contient SNS i con
60. 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 A PRIORI est ici anecdotique puisque comme on l a dit APRIORI 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 tr s en vogue a
61. taxonomies Dans certains cas d application il peut 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 plication est pr sent dans la figure 2 4 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 plusieurs types d approches La premi re approche est dite top down avec un seuil de support uniforme pour tous les niveaux Pour parcourir la hierarchie 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 fr quent alors
62. 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 association plus int ressantes Ceci tant la disponibilit et la
63. 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 On d signe ici par clique le graphe induit par un ensemble de sommets deux deux adjacents 2 5 COMMENT PRENDRE EN COMPTE LA CONNAISSANCE DU DOMAINE 751 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 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 Apprentissage des param tres partir de donn es compl tes
64. 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 princi palement sur l utilisation de mesures dites objectives Comme pr cis pr c demment la majorit de ces mesures valuent 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 proba bilit d apparition sous l hypoth se d ind pendance Le d faut principal de ce type de mesures est qu elles ont tendance a faire apparaitre des r gles d ja 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 a 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 si il est surprenant pour l expert ou innatendu 2 5 COMMENT PRENDRE EN COMPTE LA CONNAISSANCE DU DOMAINE 47 Le caract re innatendu d
65. 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 permit 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 donc 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 F1G 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 manquantes champ
66. 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 F1G 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 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 li bert 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 ELIMINER LA REDONDANCE DES REGLES FREQUENTES ET VALID
67. 375 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 a un cas d application donn Autrement dit il devient important de d finir des crit res permettant d valuer ces mesures Ainsi LMV 04 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 ment 2 2 6
68. 6 10 Bronchitis Cancer Dyspnea 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 DONNEES VISIT ASIA 93 Etape 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
69. 98 Mohammed Javeed Zaki and 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 ZPOL97 Mohammed Javeed Zaki S Parthasarathy M Ogihara and W Li New algorithms for fast discovery of association rules In Proceedings of the KDD conference pages 283 286 1997
70. 99 Morgan Kaufmann 12 15 1994 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 123 124 BAGO Bay98 BB00 BBJ 02 BBROO BBR03 BGH 02 BGS 00 BKGG04 BKM99 BIBLIOGRAPHIE R J Bayardo Rakesh Agrawal and 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 and 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 of LNAI pages 62 73 Kyoto JP April 2000 Springer Verlag C line Becquet Sylvain Blachon Baptiste Jeudy Jean Francois Bou licaut and Olivier Gandrillon Strong association rule mining 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 and Christophe Rigotti Ap proximation of frequency queries by means of free sets In Proceedings of the 2000 PKDD European Conference on Principles and Practice of Knowledge Discovery in
71. 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 es 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 associations 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 non va
72. 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 ELIMINER LA REDONDANCE DES REGLES FREQUENTES ET VALIDES31 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 4 mettre en place et a 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 a mettre en place et a 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 as sociation 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 Ce pendant l approche classique conna t plusieurs limitations qui 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 utilisateur Les r gles obtenues sont tr s nombreuses La d couverte de r gles r ellement int ressantes est donc d autan
73. D finition 2 10 libre Un itemset est libre si 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 DECOUVERTE DE REGLES 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 a 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 1 ACDE
74. Databases pages 75 85 2000 Jean Francois Boulicaut Artur Bykowski and 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 Partanen and 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 and Geert Wets A data mining framework for optimal product selection in retail supermarket data the generalized PROFSET model In R Ramakri shnan S Stolfo R Bayardo and I Parsa editors 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 and R gis Gras Me sure de qualit des r gles d association par l intensit d implication en tropique Revue Nationale des Technologies de l Information E 1 33 44 2004 Jean Francois Boulicaut Mika Klemettinen and Heikki Mannila Mo deling kdd processes within the inductive database framework In DaWak 99 Proceedings of the First International Conference on Data BIBLIOGRAPHIE 125 BMM03 BMUT97 BP98 BRM02 BTP 00 BTP 02
75. ES35 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 4 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 BB00 Lorsque les donn es s
76. IBUTIONS ENVISAGEES 63 ont montr que les R seaux Bay siens 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
77. La r gle n 2 nous dit que Lorsqu 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
78. Lin and 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 Beno t Vaillant Picouet P and 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 and 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 of Revue des Nouvelles Technologies de Vinformation RNTI E 2 pages 193 217 2004 Steffen Lauritzen and 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 130 LSM00 LT03 LT04 MAA05 MPC96 MPC98 MT96 MT97 MTV94 Nea93 NH98 NLHP98 NWL 04 BIBLIOGRAPHIE Wenke Lee Salvatore J Stolfo and Kui W Mok Adaptive intrusion detection A data mining approach Artificial Intelligence Review 14 6 533 567 2000 S Lallich and O Teytaud Evaluation et validation de l int r t des r gles d association Revue des Nouvelles Technologies de l I
79. N D ORDRE 2007 ANNEE 2007 THESE 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 L IMPL MENTATION D UN R SEAU BAYESIEN APPLICATION L INDUSTRIE A RONAUTIQUE Soutenue publiquement le XX XX 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 au CCR EADS Bart GOETHALS Chercheur l Universit d Anvers Belgique Fran ois JACQUENET Professeur l Universit de Saint Etienne Rapporteur Alain MILLE Professeur l Universit Lyon 1 Co directeur A tous un grand Merci R sum Dans un contexte industriel un ing nieur est souvent confront analyser un ensemble de donn es relatives 4 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
80. NonSmoker 0 1 4 La variable Bronchitis n est plus directement reli e Dyspnea 5 Du fait de la modification n 4 les tables de probabilit s de Dyspnea sont adapt es en cons quence 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 3 7 VALIDATION SUR LES DONNEES VISIT ASIA 91 Fia 3 11 R seau bay sien Visit Asia RB_0 utilis pour la 197 it ration du processus 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 confiance minimale de 0 90 Il s agit de la collection L R T 4 0 0 Les mesures ob jectives calcul es sont la confiance et la mo
81. RB de converger vers un maximum local de l indice de performance du RB 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 Cet 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 contribution
82. a partir des donn es Dans ce contexte la mise en place d un processus d extraction de connaissances a 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 4 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 instrumentation d un processus ECD permettant de telles d couvertes Comme
83. able 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 n y 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 a 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 102 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 que la pose d pose d un
84. acteurs 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 textes libres 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 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 VIO 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 cha ne de traitement cap
85. adre 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 ATA 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 99 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 ST2 CS DY 2 37 212651
86. ages 181 192 1994 R M Neal Probabilistic inference using Markov chain Monte Carlo methods Technical Report CRG TR 93 1 University of Toronto 1993 R Neal and G Hinton A view of the em algorithm that justifies incre mental sparse and other variants In M I Jordan editor Learning in Graphical Models Kluwer 1998 Raymond T Ng Laks V S Lakshmanan Jiawei Han and 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 Pour ret and Anna Becker R seaux bay siens Eyrolles 05 2004 BIBLIOGRAPHIE 131 ODW00 Pas00 PBTL98 PBTL99a PBTL99b Pea88 PHM00 PKS 03 Pol66 PPMH94 PT9S PT00 Agnieska Onisko Marek Druzdzel and Hanna Wasyluk Learning baye sian 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 scien tifique des C seaux F 63177 Aubi re cedex France december 2000 Nicolas Pasquier Yves Bastide Rafik Taouil and Lotfi Lakhal Pruning closed itemset lattices for association rules In Proceedings of the BDA Conference pages 177 196 1998 Nicolas Pasquier Yv
87. ainsi R Taouil et N Pas quier PTB 05 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 MIN 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 ELIMINER LA REDONDANCE DES REGLES FREQUENTES ET VALIDES37 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
88. ances sur les d pendances du domaine mais aussi vers la d couverte 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 66 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 vu 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
89. ant la plus adapt e pour l analyse de r gles d association 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 Fic 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 lisation 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 r seau bay sien initial ne demande pas un investissement initial 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 volut
90. ante de r gles 36 TELET 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 RS a hk ac Fee Ie R ae ad ec aS 43 2 5 Comment prendre en compte la connaissance du domaine 43 2 5 1 D finition du probl mel 43 fe Gide Bok Wek a ee ee a ek Be ae die 47 E E nt de ee 55 2 6 1 Conclusion 57 2 7 Discussion sur l tat de l art 58 61 3 1 Positionnement rappel des contributions envisag es 61 3 2 Processus de d couverte de connaissances KARD 64 3 2 1 Pr sentation de notre approche 65 3 2 2 Le processus KARD d taill l 71 eee Ge Sees A on ee 74 ie Pe aod we ed Oe ee aS 75 SN Eh ae to oe es at eH ao 81 3 5 1 D finition d une mesure de pertinence des r gles vis vis d un RE e PRE Gong es eee Got 81 3 5 2 Extraction des parties d s par es d pendances principales 84 errs 85 3 6 1 N cessit des annotations 86 a ee eer ee de ta 86 3 6 3 Prise en compte des annotations 88 bape fe eats Sete ta chee aa ben ek 89 3 7 1 Objectifs de notre d marche exp rimentale 89 ee ee
91. approximatives et 6 g n rale notamment lorsqu une approximation 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 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 Dor 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
92. arek J Druzdzel and Linda C Van Der Gaag Building probabi listic networks where do the numbers come from guest editors introduction IEEE Transactions on Knowledge and Data Engineering 12 4 481 486 2000 Guozhu Dong and 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 and 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 and 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 Faur Sylvie Delprat Jean Fran ois Boulicaut and Alain Mille Iterative bayesian network implementation by using annotated association rules In EKAW pages 326 333 2006 Cl ment Faur Sylvie Delprat Alain Mille and Jean Francois Bouli caut 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 Cl ment Faur Sylvie Delprat Alain Mille and Jea
93. as 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 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 46 CHAPITRE 2 DECOUVERTE DE REGLES PERTINENTES 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 d extraire une collection minimale de r gles tonnantes par rapport 4 un ensemble de croyances exprim es
94. ations 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 109 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 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 A 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 choisi donc de signaler ce motif comme tant non pertinent On verra l it ration n 3 de notre processus qu
95. au centre de notre processus Ainsi nous avons t amen s d 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 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
96. ce 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 apparaissent dans les m mes transactions que X Cependant cette mesure est a 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 rentes approches pour la s lection de r gles r ellement pertine
97. ce de deux n ud 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 W ND FH 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 JS05 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 56 CHAPITRE 2 DECOUVERTE DE REGLES PERTINENTES Soit bd une base de donn es binaire de sch ma lt Tj4 Z gt Les valeurs possibles pour les attributs sont d
98. ciation g n r es partir des itemsets fr quents extraits tableau 2 1 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 2 1 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 associations pouvant tre g n r es partir de ces itemsets 26 CHAPITRE 2 DECOUVERTE DE REGLES PERTINENTES itemset fr quent 1 i to Fic 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 min freq en effectuant un parcours en largeur du treillis des et en calculant les fr quences par comptage dans la base ce qui impose une passe sur la base cha
99. 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 biai s es Ainsi proposent 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 54 CHAPITRE 2 D COUVERTE DE R GLES PERTINENTES 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 BMMO03 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 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 structure de RB
100. constater des examens de rayons X anormaux 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 94 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 Tubercolis
101. dantes entre elles la r gle 7 est cependant plus 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 6 approrimative de r gles d association de la fa on suivante 6 approt R X ferms X X X Libre Ainsi dans notre exemple la base 6 approximative de r gles d association est constitu e par l ensemble des r gles 1 2 3 5 6 7 9 10 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 4 1 on retrouve alors le r sultat pr sent par Pas00 sur la m me base de donn es 80 CHAPITRE 3 LE TRAVAIL DE RECHERCHE Cette base est int ressante car elle offre un bon compromis entre compaci
102. de 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 outils qu il a d velopp s pour estimer la probabilit d IO de cet q
103. dent si nous avions effectu les calculs de d s paration sur tous les sous ensembles d itemsets nous aurions eu en plus effectuer les tests suivants 4 AB C D 5 AC BID 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 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 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 associations 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 per 86 CHAPITRE 3 LE TRAVAIL DE RECHERCHE mettre d acqu rir une compr hension plus fine des r gles manipul es et implicitement 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
104. e Sur la base de donn es bd repr sent e dans la table 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
105. e d couverte Dans le troisi me chapitre nous avons choisi de positionner nos contributions sur trois axes Tout d abord sur le domaine des collection de r gles d association non redondantes Nous avons tudi les propri t s des ensembles de r gles g n r es par tir des itemsets d 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 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 inter 113 114 CHAPITRE 5 CONCLUSION actions avec le mod le de connaissance utilis pour faciliter la d couverte de r gles pertinentes construction exploitation volution Nous avons aussi montr l impor tance 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 inter ruptions op rationnelles Ce chapitre apporte une confrontation de nos contributions des probl mes concrets de l industrie G n ration d un ensemble non redondants 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 redondantes actuel
106. e 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 F1G 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 101 A Vissue 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 la recherche de nouveaux f
107. e 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 enre gistrements 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 i i2 i C Items est appel itemset ou k itemset s il contient k l ments Par exemple A B C est un 3 itemset pour simplifier l criture on utilisera galement la notation ABC L ensemble des itemsets est not 21tems 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 t te le cons quent ou la partie droite Une r gle repr s
108. e 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 50 CHAPITRE 2 DECOUVERTE DE REGLES PERTINENTES 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 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 m thod
109. e 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 ata4d 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 4 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 dix premi res
110. e r gles tudi es 72 CHAPITRE 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 73 KARD PROCESSUS DE DECOUVERTE 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 sajueulied lt 00 EAE Pq I H gt 7 suoneloosse 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 ab
111. eau 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 111 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 RB03 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 pertinentes
112. eillera ce que 6 soit tr s inf rieur minfreq card Items 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 6 gt 0 on constate que les r gles extraites sont plus g n rales le volume de r gles pr sent es l utilisateur et 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 0 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 ont un corps minimal 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
113. ensemble de r gles d association pertinentes sur 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 a 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 modifica tions 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 tables 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 p Cancer Present Smoking Smoker 0 1 p Cancer Present Smoking
114. ent dans le tableau 2 5 Ensemble minimal de r gles partir duquel on peut g n rer l ensemble des r gles d association 38 CHAPITRE 2 DECOUVERTE DE REGLES 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 MinMarAppror 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 A 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 si 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 surensemble R gle min
115. ent 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 ma collection des motifs les plus g n raux qui ne sont pas dans S Bd S ming 2 S p SI u S u lt 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 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 base pour chaque niveau du treillis Pou
116. ente 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 DECOUVERTE DE REGLES 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 S 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 de 2 et que le nombre total de transactions est de 6 la fr quen
117. erruptions 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 guider et valider le processus de d veloppement Enfin pour aider les experts mesurer l
118. ers Inc Peter E Hart and Jamey Graham Query free information retrieval In Conference on Cooperative Information Systems pages 36 46 1994 David Heckerman Dan Geiger and David Maxwell Chickering Lear ning bayesian networks The combination of knowledge and statistical data In KDD Workshop pages 85 96 1994 128 HGN00 HH99 HK00 HKMT95 HMS01 HMWG98 IM96 IV99 Jeu02 JGJIS99 JJJ96 Jor98 JrK JS02 BIBLIOGRAPHIE Jochen Hipp Ulrich G ntzer and Gholamreza Nakhaeizadeh Algo rithms for association rule mining a general survey and comparison SIGKDD Explor Newsl 2 1 58 64 2000 Robert J Hilderman and Howard J Hamilton Knowledge discovery and interestingness measures a survey Technical report Department of Computer Science University of Regina 1999 Jiawei Han and Micheline Kamber Data mining concepts and techniques Morgan Kaufmann Publishers Inc San Francisco CA USA 2000 Marcel Holsheimer Martin L Kersten Heikki Mannila and Hannu Toivonen A perspective on databases and data mining In 128 page 10 Centrum voor Wiskunde en Informatica CWT ISSN 0169 118X 30 1995 David Hand Heikki Mannila and Padhraic Smyth Principles of data mining The MIT Press 2001 Jochen Hipp Andreas Myka Rudiger Wirth and Ulrich Guntzer A new algorithm for faster mining of generalized association rules pages 74 82 1998
119. es dites de propagation des messages tendues par des algorithmes de coupe ou de conditionnement et les m thodes utilisant des groupements de n uds y 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 et qui permet 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 seulement sur une partie du graphe d autre part les algorithmes qui utilisent 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 engendrant
120. es Bastide Rafik Taouil and Lotfi Lakhal Disco vering frequent closed item for association rules In Catriel Beeri and Peter Buneman editors Proceedings of the 7th international conference on knowledge discovery and data mining pages 398 416 Jerusalem Is ra l January 1999 Berlin Springer Verlag Nicolas Pasquier Yves Bastide Rafik Taouil and Lotfi Lakhal Efficient mining of association rules using closed itemset lattices Information Systems 24 1 25 46 January 1999 Judea Pearl Probabilistic reasoning in intelligent systems networks of plausible inference Morgan Kaufmann Publishers Inc San Francisco CA USA 1988 Jian Pei Jiawei Han and Runuying Mao Closet an efficient algorithm for mining frequent closed itemsets In Dimitrios Gunopulos and Ra jeev Rastogi editors 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 and 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 Lon don 1966 M Pradhan G Provan B Middleton and M Henrion Knowledge engineering for large belief networks In Uncertainty in AI Proceedings of the Tenth Conference 1994 Balaji Padmanabhan and Alexander Tuzhilin A belief d
121. es de l ing nierie de la connaissance au sein d un processus de d couverte de connaissances d finition du mod le initial annotation des r gles d association volution du mod le des d pendances 61 62 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 c
122. essjusidde p 2 seeuuoq al anol e amon a Se 1 S PON Y gH SLIEWOPNP oPessn seoues p dx4 u dde p SIEUU09 elBoye ns s y dxqg 74 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 rationnelle 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
123. est la suivante D finition 3 1 R gle 6 forte tant donn une base de donn es bd d finie sur Items un seuil de fr quence minimale 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 REGLES D ASSOCIATION NON REDONDANTES 77 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 0 libre s il n existe pas de r gle 6 forte X Y telle que XUY CS Y 4 Exempl
124. fs que nous avions fix Ces r sultats mettent en avant plusieurs points suivants La d couverte de deux r gles int ressantes a entra n une modification du RB et a permit d inverser 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 A 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 celle ci pl
125. g em for large databases 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 Mor gan Kaufmann Publishers Inc R Taouil N Pasquier Y Bastide and L Lakhal Mining bases for as sociation rules using closed sets In Proceedings of the ICDE conference page 307 2000 L van der Gaag S Renooij C Witteman B Aleman and B Taal Probabilities for a probabilistic network A case study in oesophageal cancer 2002 Ian H Witten and Eibe Frank Data Mining Practical machine learning tools and techniques Morgan Kaufmann San Francisco 2nd edition edition 2005 Hui Xiong Xiaofeng He Chris Ding Ya Zhang Vipin Kumar and 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 134 BIBLIOGRAPHIE ZH02 Mohammed Javeed Zaki and Ching Jui Hsiao Charm an efficient algo rithm for closed itemset mining In Robert Grossman Jiawei Han Vi pin Kumar Heikki Mannila and Rajeev Motwani editors Proceedings of the 2nd international SIAM conference on data mining SDM 02 2002 ZO
126. gles de 6 approx partir de cette r gle et nous allons voir les erreurs d estimation de fr quence apport es par cette repr sentation On sait gr ce 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 fini 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 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 RESEAU BAYESIEN 81 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 v
127. 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 telles sortes 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 pouvait 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 rents algor
128. h 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 paraitre 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 a r gle zone E last _action swap CS DY swap peut se lire de la fa on suivante Si la compagnie qui op re l
129. hie de concepts tablie sur le domaine 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 Aji Ak Apa o chaque A est soit un nom d attribut un nom de classe ou une expression CT ou C C tant le nom d une classe Ici C 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 sou haite 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 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 2 4 EXPLOITER LA SUBJECTIVITE Al Exploitation des
130. hme EM s applique 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 52 CHAPITRE 2 DECOUVERTE DE REGLES PERTINENTES De plus de nombreux travaux de recherche ont mis en avant diff rentes heuristiques 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 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 le deux
131. i 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 tenant en compte de 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 tant de trouver un expert la fois fiable disponible puis de le fami liariser 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 Cet outil a 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 pro babilit 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 X Pour simplifier prenons le
132. ient 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 a 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 libre
133. ient 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 TobOrCa 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 88 CHAPITRE 3 LE TRAVAIL DE RECHERCHE 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 2 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 FIXME compl ter 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 im
134. ieure min freq et une confiance sup rieure mincon f o min freq 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 inin 24 CHAPITRE 2 DECOUVERTE DE REGLES PERTINENTES t ressantes ou redondantes entre elles et vis vis du domaine d application Il faut donc pouvoir d finir un crit re d int r t des r gles On va commencer par re
135. indre contradiction Le temps d ex cution est n gligeable un total de 16 r gles d association sont extraites 92 CHAPITRE 3 LE TRAVAIL DE RECHERCHE Etape C partir de et de RB_0 on calcule ensuite L R Tpq gt Lrv_0 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 a 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 a 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 XRay 0 98 0 01 0 8
136. ion du mod le sur les diff rentes it rations de notre 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 68 CHAPITRE 3 LE TRAVAIL DE RECHERCHE syntaxiques Le r sultat de la fonction d extraction que nous appellerons o 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 ob
137. ion 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 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 de celles qui paraissent surprenantes car non mod li s 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 115 cela nous avons souhait d velopper une interface sp cifique regroupant int grant diff rentes fonctionnalit 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 correspondants aux attributs des r gles tudi es Ces motifs sont cat goris s selon le jugement port par l expert motif connu non valide non pertinent ou pertinent Ces motifs so
138. is une l g re influence sur la pr sence de tuberculose lorsque le patient d clare avoir visit l Asie Mais comment quantifier cette influence En effet il serait invraisemblable de mo d 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 dispo sition 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 partir de RB 1 on obtient le r sultat pr sent dans le tableau 3 8 En tudiant ce tableau on peut l gitement 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
139. ison synth tiques des algorithmes d apprentissage de la structure Il peut par contre tre important de retenir que les techniques d apprentissage au tomatique bien qu int ressantes ne peuvent pas tre utilis es telles quelles les r sultats obtenus n cessitent imp rativement d tre valid s par un expert En effet on se rend 2 6 EXPLOITATION DES RESEAUX BAYESIENS 55 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 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 a priori D claration d un noeud racine sans parents D claration d un noeud feuille sans enfants Existence ou absence d un arc entre deux n uds pr cis Ind pendan
140. ithmes 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 maximaurx 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 ELIMINER LA REDONDANCE DES REGLES FREQUENTES ET VALIDES33 Ce type de repr sentation regroupe donc les techniques qui cherchent a calculer directement cette fronti re positive vis a 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 a arriver le plus vite possible a la fronti re positive en n explorant pas de mani re exhaustive les diff rents niveaux du treillis Leur int r t dev
141. jectives associ es Extraire les r gles d associations BD base de donn es Contraintes Fr quence Confiance syntaxiques minimale minimale Fic 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 tache 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 des l art des algorithmes capables de pousser les contraintes 3 2 PROCESSUS DE D COUVERTE DE CONNAISSANCES KARD 69 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
142. 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 pour int r t de rendre prati cable l algorithme d extraction du fait de la propri t d antimonotonie 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 r gle d association El
143. 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 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 2 5 COMMENT PRENDRE EN COMPTE LA CONNAISSANCE DU DOMAINE 743 Les auteurs de Direct introduisent aussi d autres contraintes dans le cas ot 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 etc L algorithme CAP NLHP98 propose une approche diff rente pour pousser des contraintes anti monotones syntaxiques ainsi que certaines contraintes utilisant les f
144. le constitu de ses 2 5 COMMENT PRENDRE EN COMPTE LA CONNAISSANCE DU DOMAINE 749 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 facon suivante 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 X1 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 II Pasta 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 la mis
145. 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 industrielle 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 aux taux d interruptions op rationnelles partir de gra
146. le mais cette fois les n uds VisitAsia et 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 n 2 La formule nous donne CON rb 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 00 x 0 98 0 98 Int ref 0 97 0 98 0 01 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 proj J Visit Asiaest lui aussi disponible via l application 84 CHAPITRE 3 LE TRAVAIL DE RECHERCHE 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
147. le 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 Y 800 200 1000 B B TAB 2 3 R partition des achats sur un groupe de 1000 personnes partir de ces donn es il est possible d valuer la r gle 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 pendemment 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 donc n cessaire pour rep
148. les 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 auxquelles ont peut r pondre par l utilisation de techniques adapt es Un probl me nous pourtant apparu comme ouvert com ment liminer la redondance intrins que au domaine d application et faire ressortir par la 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 d une part par la d finit
149. lide est pr sent e diff remment l expert Il faut donc r fl chir au filtrage de 112 CHAPITRE 4 APPLICATION PRATIQUE ces motifs autrement que par la mesure d int r t Un deuxi me probl me a prendre en compte dans des travaux futurs est l tude de Vimpact potentiel que peut avoir la modification de la structure ou des param tres du RB sur l ensemble 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 nceuds 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 avons propos
150. lle de donn es Les sections suivantes 3 2 PROCESSUS DE D COUVERTE DE CONNAISSANCES KARD 65 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 voluen
151. ls 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 autre part permettre
152. mation theoretic approach to rule induction from databases IEEE Transactions on Knowledge and Data Engineering 4 4 301 316 1992 BIBLIOGRAPHIE 133 Sme00 SON95 SSOT 97 ST96 STVNO4 TMHO1 Toi96 TPBLOO vaGRW 02 WF05 XHD 05 Zak00 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 and 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 Ku hara and T Takagi Finding association rules on heterogeneous genome data In Proceedings of the Pacific Symposium on Biocomputing pages 397 408 1997 Avi Silberschatz and Alexander Tuzhilin What makes patterns interes ting in knowledge discovery systems IEEE Transactions on Knowledge and Data Engineering 8 6 970 974 1996 Ansaf Salleb Teddy Turmeaux Christel Vrain and Cyril Nortet Mi ning 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 and David Heckerman Acceleratin
153. 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 Etat 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 sultats Pour chaque grande cat gorie de probl mes nous d taillon
154. n 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 Notamment nous avons vu 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 2 7 DISCUSSION SUR L TAT DE L ART 59 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 a 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 60 CHAPITRE 2 DECOUVERTE DE REGLES PERTINENTES Chapitre 3 Le travail de recherche Dans nos t
155. n Francois Bouli caut Utilisation des r seaux bay siens dans le cadre de l extraction de r gles d association In EGC pages 569 580 2006 Olivier Fran ois and Philippe Leray Etude comparative d algorithmes d apprentissage de structure dans les r seaux bay siens Journal lectronique d intelligence artificielle 5 39 1 19 2004 Takeshi Fukuda Yasuhido Morimoto Shinichi Morishita and 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 BIBLIOGRAPHIE 127 FP 96 FP97 FPSM92 GCB 04 GRS96 GZ03 HC99 HCCO2 Hec95 Hec97 HF95 HG94 HGC94 Tom Fawcett and Foster Provost Combining data mining and machine learning for effective user profiling In Simoudis Han and Fayyad edi tors Proceedings on the Second International Conference on Knowledge Discovery and Data Mining pages 8 13 Menlo Park CA 1996 AAAI Press Tom Fawcett and Foster J Provost Adaptive fraud detection Data Mining and Knowledge Discovery 1 3 291 316 1997 W J Frawley G Piatetsky Shapiro and C J Matheus Knowledge discovery in databases an overview Ai Magazine 13 57 70 1992 R gis Gras Rapha l Couturier Maurice Bernadet Julien Blanchard Henri Briand Fabrice
156. n 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 Vhomme 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 a 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 apparaissent sous une forme tangible dossier papier ou lectronique Ici le mo
157. n 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 A LA PROBLEMATIQUE 21 T a de type entier est la clef 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 ti et d un sous ensemble de Items not t item La figur
158. ndes 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 l 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 traitement des r gles De plus les algorithmes actuels nous au
159. nformation n 2 2003 St phane Lallich and Olivier Teytaud Evaluation et validation de l in t r t des r gles d association Revue des Nouvelles Technologies de V Information RNTI E 1 193 217 2004 Ahmed Metwally Divyakant Agrawal and Amr El Abbadi Using asso ciation rules for fraud detection in web advertising networks In VLDB 705 Proceedings of the 31st international conference on Very large data bases pages 169 180 VLDB Endowment 2005 Rosa Meo Giuseppe Psaila and 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 and Stefano Ceri An extension to sql for mining association rules Data Mining and Knowledge Discovery 2 2 195 224 1998 Heikki Mannila and 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 and Hannu Toivonen Levelwise search and borders of theories in knowledge discovery volume 3 chapter 1 pages 241 258 KluwerAcademic Publishers 1997 Heikki Mannila Hannu Toivonen and A I Verkamo Efficient algo rithms for discovering association rules In Proceedings of the AAAI Workshop on Knowledge Discovery in Databases p
160. nt 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 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 l action C est dire qu elle r unit la fois une information et u
161. nt 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 rieurs 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 processus de d couverte de connaissances aux donn es d interruptions
162. ntes 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 ou 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 transactions d couvrir toutes les r gles qui ont une fr quence sup r
163. ntradiction dans les diff rents cas de figure i e A a B b C c A a B b C c A a B b C c et A a B b C c Une partie des annotations r alis s lors de cette it ration est donn e dans le ta bleau 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 toutes les rel
164. ntroduction 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 de la connaissance 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 de la connaissance et nous d gageons quelques perspectives Chapitre 1 Cadre de travail probl matique de la recherche Les travaux de th se pr sent s dans ce rappo
165. o Aest 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 concern s ou leurs prix de vente Les r gles d associatio
166. oins 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 IO Certains de ces facteurs sont identifi s de mani re informelle a 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 associ s l ensemble des interruptions op ration nelles lesquels contenaient
167. on vidente ou d j connue de l expert A 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 B 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 4 4 pour valuer les modifications apport es en gras dans le graphe FIG 4 4 R seau bay sien issue de la premi re mise jour RB02 4 3 EXPERIMENTATIONS REALISEES 107 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 a 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 avant et apr s la mise
168. on est inf rieur la minute Au total 5633 itemsets 0 libres fr quents ainsi que leur fermeture sont extraits A partir de cet ensemble nous g n rons 4954 r gles 6 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 a la possibilit d tablir des filtres syntaxiques de seuiller selon les diff rentes mesures d int r ts calcul es etc 104 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 RB01 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 Chr75 impl ment dans la bibliot
169. on 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 a 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 119 120 ANNEXE A PRESENTATION 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 PartieA Partie B Support Confiance Moindre Contradiction J Mesure Score bay
170. onctions 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 l utilisateur 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 une connaissance attend
171. onnu lorsque 6 est gal z ro il est int ressant d tudier les 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 ana lyse des r gles d associations En fait parmi les solutions actuellement propos es beaucoup sont trop sp cifiques filtrage base de patrons exploitation de la taxono mie et ne remontent pas la source du probl me qui pose la question suivante comment utiliser de mani re judicieuse les connaissance 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 association 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 pen dances mod 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 auteurs 3 1 POSITIONNEMENT RAPPEL DES CONTR
172. ont 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 e 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 7 fr quent ou qu il n est pas libre BBR0OO a aussi propos un autre type de repr sentation condens e bas e cette fois sur une g n ralisation des itemsets libres les itemsets 6 libres D finition 2 12 6 fermeture JBBROO Soit un entier positif La 6 fermeture d un itemset S not e ferm S est d finie par ferms S I Items Freq S Freq S U I lt 36 CHAPITRE 2 DECOUVERTE DE REGLES PERTINENTES Freq est la fr quence absolue En pratique cela signifie qu on
173. ont jug es inint ressantes NV L annotation pr sente une information fortuite elle d crit en fait la coin 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 domaine 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 3 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 61 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 non Il s agit donc d un motif non valide On sait fait n 3 qu un pat
174. outes pour d faut d tre appliqu es de mani re ad hoc en utilisant des formalismes divers On s int resse souvent un aspect pr cis de ce que recherche Vexpert 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 le connaissance dans le sens o Vutilisateur va de voir 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 sys t 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 ne p
175. pact visuel des annotations En effet nous souhaitons que les 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 a 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 A 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 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
176. 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 d 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 0 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 Zak00
177. plus en plus pertinentes Cette section d crit le r le que 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 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 compose 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 ja 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 fi nition d une syntaxe rapidement assimilable et permettant de d crire les diff rentes informations apport es par une r gles d association Pour cela nous avons sp cifi une
178. pr 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 ABCDE 1 0 0O 1 0 1 2 1 1 1 1 1 1 B A fr quence 0 5 confiance 1 00 3 1 0 1 1 0 j i 4 1 1 2 A B C fr quence 0 33 confiance 0 66 5 0 01 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 Valgorithme APRIORI montrait tr s vite ses limites On verra notamment que ces r flexions ont abouti a la d finition d une repr sentation interm diaire des donn es dite repr sentation condens e Ce type de repr sentation a t introduit la premi re fois en 1996 MT96 puis de nombreuses propo
179. que 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 tout 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 va d finir la fronti re positive respectivem
180. 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 de Principles of Data Mining proposent une analogie avec le domaine de la compression de donn es Pre nons 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 pixels de l image 7 ou b envoyer une version compress e de cette image un r sum en quelque sorte La 14 CHAPITRE 1 CADRE DE TRAVAIL Retour d exp rience Expert Construction d un D couverte de mod le de connaissance connaissances Fic 1 5 Collaboration des approches mod les et motifs 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 application des interruptions op rationnelles Un mod
181. r 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 APRIORI et autre inconv nient toute la base doit pouvoir tenir en m moire Avec Valgorithme Partition les auteurs ont investigu l utilisation des tid listes ensemble des tid ou identifiant unique d une transaction associ s aux transactions qui contiennent un itemset donn interm diaires associ es au treillis de chaque partie tienne en m moire 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 DECOUVERTE DE REGLES 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 a permet de limiter le risque de non exhaustivit Les auteurs de proposent avec V algorithme Dynamic Itemset Counting un parcours niveau par niveau modifi Au niveau k d s qu un itemset a atteint le
182. ravaux de th se nous avons envisag la mise en place d un processus de d couverte 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 frequemment rencontr es lors de la phase d analyse nous ont amen 4 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 analyse et la d couverte de r gles d association pertinentes 3 La prise en compte des probl matiques issu
183. 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 DECOUVERTE DE REGLES 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 Lift A B DCE 0 9
184. riven 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 and Alexander Tuzhilin Small is beautiful dis covering the minimal set of unexpected patterns In Proceedings of the 132 PT06 PTB 05 PuG 02 Rae00 Ren01 RJBA99 Rob96 rul94 RW99 SA96 SCHO5 SG92 BIBLIOGRAPHIE 2000 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining pages 54 63 New York NY USA 2000 ACM Press Balaji Padmanabhan and 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 and 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 and J Blanc Fu sion 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
185. rt 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 de la connaissance du LIRIS Dans ce premier chapitre nous pr sentons le contexte industriel qui a initi les travaux de th se l aide 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 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 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 environnement dans lequel est plong le syst me voluant constamment au cours du temps on
186. s 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 tant 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 DECOUVERTE DE REGLES 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 gle d association s exprime de la fa on suivante A B
187. s dans une approche d ing nierie de la connaissance 64 CHAPITRE 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 i 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 A l tape 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
188. s non renseign s La quantit de bruit est cependant difficile estimer Le nombre d enregistrement 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 homog ne nous avons limit la base de donn es 11819 enregistrements correspondants au programme avion s lectionn par l expert 100 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 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 champs de la base A titr
189. 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 Shea rer and 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 and David J Spiegelhalter Probabilistic Networks and Expert Systems Springer 2003 Jie Cheng Russell Greiner Jonathan Kelly David Bell and Weiru Liu Learning bayesian networks from data An information theory based approach Artificial Intelligence 137 309 347 2002 David Maxwell Chickering David Heckerman and 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 computer science and applied mathematics 1975 126 Coo88 DD00 Dec99 DG00 DL99 DLR77 DP01 FDBM06 FDMB06a FDMBO06b FL04 FMMT96 BIBLIOGRAPHIE G F Cooper Probabilistic inference using belief networks is np hard Technical report Knowledge Systems Laboratory 1988 Marek J Druzdzel and F Diez Criteria for combining knowledge from different sources in probabilistic networks 2000 Rina Dechter Bucket elimination A unifying framework for reasoning Artificial Intelligence 113 1 2 41 85 1999 M
190. 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 tant 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 struc ture sp cifique des donn es de transaction intitul e F P tree avec une recherche en profondeur dans le treillis En parall le a 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 PBTL99a puis l algorithme Pascal fond sur le comptage par inf rence des ensemble cl s BTP 00 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 temps d extraction et par
191. sitions 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 a 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 A 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 principale difficult de cette phase d analyse provient d une part du
192. suelle 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 a prendre en compte dans des travaux futurs est l tude de Vimpact potentiel que peut avoir la modification de la structure ou des param tres du RB sur l ensemble 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 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 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 approches visant concilier mod le de connaissances formel et r gles d association appara t distincte ment dans l tat de l art Il semble donc crucial d tudier l utilisation
193. suivants et uniquement ceux l 3 6 LE R LE DE L EXPERT DANS LE PROCESSUS DE D COUVERTE 85 1 A BC D 2 B ACID 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 pertinentes 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
194. t et pr cision d extraction cependant elle n cessite le calcul 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 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 tablef3 2 uniquement par la r gle n 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 B 1 CE 1 Nous allons maintenant tudier la possibilit de g n rer les r
195. t 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 a 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 exploitation des r sultats consiste interpr ter et analyser les mo
196. t ou lorsque la probl matique est modifi e L volution de la 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 connaiss
197. t 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 X Y CY et le support et la confiance de R et R sont identiques A l chelle d une application r elle un nombre important de r gles g n r es sont re dondantes et viennent parasiter la phase d exploration des r sultats rendant d autant 32 CHAPITRE 2 DECOUVERTE DE REGLES PERTINENTES plus difficile la d couverte de r
198. te 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 par le biais de la fouille de donn es les informations utiles et seulemen
199. 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 une 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 s int resser 117 au probl me de la gestion des volutions de notre mod le de connaissance notam 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 a priori int gr es pour le filtrage de motifs ou encore les connaissances nouvelles 118 CHAPITRE 5 CONCLUSION Annexe A Pr sentati
200. tems l ensemble des arcs du graphe A chaque n ud on associe une distribution de probabilit conditionnelle P A Par A o Par A A V A V 4 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 Pea88 INWL 04 Soit R X Y une r gle d association o X et Y sont des itemsets tels que X Y C Items Y 0 et X NY 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 Pial R conf R X Y bal Poa X 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
201. tient a gt _ M US bo 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 L d FIG A 4 Interface d analyse des r gles d association 121 rr 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 122 ANNEXE A PRESENTATION DE L APPLICATION Bibliographie AAO7 AAP00 AAPO AIS93 AKO AL99 AMS 96 AS94 Az 03 D J Newman A Asuncion UCI machine learning repository 2007 Ramesh C Agarwal Charu C Aggarwal and V V V Prasad Depth first generation of long patterns In Proceedings of the 6th international conference on knowledge discovery and data mining KDD
202. tifs 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 rir ou construire un mod le des connaissances On a commenc
203. torisent 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 envi sager 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 de la connais sance il nous faudra donc tudier comment l expert consid re une r gle d association et comment il envisage 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 A B peut se lire de la fa on suivante Lorsque j observe la pr sence des v nements 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 partir des donn es 16 CHAPITRE 1 CADRE DE TRAVAIL Le Tableau 1 1 montre un exemple de base de donn es binaire Dans cet exemple les colonnes repr sentent les diff rents attributs de la base chaque ligne re
204. 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 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 42 CHAPITRE 2 DECOUVERTE DE REGLES PERTINENTES Prenons les deux r gles d association ci dessous 1 Syst mes vrai Attr2 vrai Attr3 vrailF 0 06 conf 0 7 2 Syst mes vrai Attr2 vrai Electro m canique vrai Attr3 vrai 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 ud Syst mes a 3 fi
205. 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 l expert doit tre en mesure de v rifier que le motif en ques tion n est pas le fait d une simple co ncidence sur les donn es Pour ce faire il a sa disposition des outils de tests qui vont lui permettre d valuer plus finement le motif en question sur l ensemble 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 108 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 moindre co
206. u 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 J 72 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 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 2 6 EXPLOITATION DES RESEAUX BAYESIENS 57 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 partie 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 L UT et TE J et 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 a partir d un seul attribut int
207. u 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 l utilisateur 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 2 5 COMMENT PRENDRE EN COMPTE LA CONNAISSANCE DU DOMAINE 745 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 t
208. ue 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 44 CHAPITRE 2 DECOUVERTE DE REGLES PERTINENTES la r gle suivante Bi re Chips 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 connaissances du domaine o
209. uipement 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 diction de la fr quence des IO Ainsi non seulement il est pris en comp
210. uire 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 disfonctionnement 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 97 98 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 ristiques communes avec
211. uis 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 exceptions une informa 106 CHAPITRE 4 APPLICATION PRATIQUE ti
212. 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 a leur v rification Probl matique du cas d application Pour faciliter cette tache 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 collect es le deuxi me est celui de la d couverte de connaissances
213. us 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 rents 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 concourante afin de r d
214. 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 quipement et donc du temps additionnel n cessaire pour y acc der sur les taux d int
215. venir 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 ap puient 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 quent alors tout sous ensemble de S est aussi y fr quent

Découvertes de motifs pertinents par l`implémentation d`un réseau

Contents

Download Pdf Manuals

Related Search

Related Contents

D&eacute;couvertes de motifs pertinents par l`impl&eacute;mentation d`un r&eacute;seau

Contents

Download Pdf Manuals

Related Search

Related Contents

Découvertes de motifs pertinents par l`implémentation d`un réseau