ATTESTATION SUR L’HONNEUR J’atteste sur l’honneur que ce mémoire a été réalisé par moi-même et que les données et les résultats qui y sont présentés sont exacts et n’ont jamais été publiés ailleurs La source des informations citées dans ce mémoire a été bien précisée LỜI CAM ĐOAN Tôi cam đoan công trình nghiên cứu riêng Các số liệu, kết nêu Luận văn trung thực chưa công bố công trình khác Các thông tin trích dẫn Luận văn rõ nguồn gốc Signature de l’étudiant DƯƠNG MINH ĐỨC Table des mati` eres Remerciements iii R´ esum´ e iv Abstract vi Introduction 1.1 Contexte g´en´eral et probl´ematique 1.2 Motivation et objectifs 1.3 Approche propos´ee 1.4 Contributions 1.5 Organisation du m´emoire ´ Etat de l’art 2.1 2.2 Revue de la bibliographie 2.1.1 Chromatic correlation clustering 2.1.2 Exceptional Model Mining 12 2.1.3 Discussions 15 S´erie temporelle et mesures de distance 16 2.2.1 Introduction de s´erie temporelle 16 2.2.2 Dynamic Time Warping 17 2.2.3 Symbolic Aggregate approXimation 21 i M´ ethodes et solutions propos´ ees 26 3.1 Graphe d’arˆetes attribu´ees et mod´elisation du probl`eme 26 3.2 Formulation du probl`eme 28 3.2.1 D´efinitions pr´ealables 28 3.2.2 ´ Evaluation statistique d’une arˆete 29 3.2.3 Contexte particulier 29 3.2.4 Formulation la tˆache de fouille des motifs 29 Algorithme FastRabbit 31 3.3 Exp´ erimentation et r´ esultats 33 4.1 R´esultats quantitatifs 33 4.2 R´esultats qualitatifs et Comparaison avec EMM 35 4.2.1 R´esultats qualitatifs 35 4.2.2 Comparaison avec EMM 40 Conclusion 42 R´ ef´ erences 44 ii Remerciements Tout d’abord, j’adresse mes remerciements au Laboratoire d’InfoRmatique en Image et Syst`emes d’information (LIRIS) d’avoir financ´e ce travail Je tiens a` remercier tout particuli`erement mes encadrants Marc Plantevit et C´eline Robardet Ils m’ont guid´e et support´e dans tous les ´etapes de ce stage La dur´ee mois de travail avec eux n’est pas beaucoup mais il m’a suffit d’avoir confiance a` continuer des ´etudes dans l’avenir Je remercie ´egalement Albrecht Zimmermann ainsi que tous les membres de l’´equipe DM2L pour des discussions et suggestions Finalement, je remercie sinc`erement mes parents et mes camarades pour leurs soutiens pendant cette p´eriode iii R´ esum´ e Les graphes sont une abstraction math´ematique qui permet de repr´esenter naturellement de nombreux ph´enom`enes r´eels La fouille de graphes est un domaine majeur de la fouille de donn´ees De nombreux travaux se sont int´eress´es a` fournir des m´ethodes pour analyser des grands graphes en se focalisant sur sa structure R´ecemment, face `a l’h´et´erog´en´eit´e des sources de donn´ees continues comme par exemple des donn´ees temporelles provenant de diff´erents types de capteurs (e.g., temp´erature, humidit´e, vent, position), des propositions visant a` travailler sur des structures de graphes plus sophistiqu´ees telles que les graphes d’arˆetes-attribu´ees sont apparues, apportant des ´eclairages nouveaux sur de telles donn´ees L’objectif de ce stage de master est de concevoir une m´ethode originale d’extraction de connaissances pertinentes dans des donn´ees temporelles et h´et´erog`enes que nous mod´eliserons sous forme de graphes d’arˆetes-attribu´ees Il s’agit donc de d´efinir une m´ethode g´en´erique permettant d’extraire des comportements p´eriodiques dans des graphes d’arˆetes-attribu´ees Le mod`ele global ainsi construit pourra ˆetre ensuite utilis´e pour d´ecouvrir et expliquer des comportements anormaux/exceptionnels dans les donn´ees Ce sujet de master qui s’inscrit dans le domaine de l’extraction de connaissances dans des grandes bases de donn´ees s’appuiera donc sur une mod´elisation sous forme de graphes d’arˆete-attribu´es L’approche d´evelopp´ee devra faire avancer l’´etat de l’art sur la fouille de donn´ees sous contraintes, les m´ethodes d’extraction de motifs, la fouille de donn´ees interactive Des exp´erimentations iv sur des donn´ees issues de centrales photovolta¨ıques seront men´ees Mots-cl´es : graphe d’arˆetes-attribu´ees, s´eries temporelles, FastRabbit, fouille des motifs locaux v Abstract Graph is a mathematical abstraction that can naturally represent many real phenomena The graph mining is a major field of data mining Many studies have focused on providing methods to analyze large graphs by focusing on its structure Recently, the heterogeneity of continuous sources of data such as temporal data from different types of sensors (eg, temperature, humidity, wind, position), proposals to work on more sophisticated graph structures such as edge-attributed graphs The aim of this master intership is to design an original method of extraction knowledge in temporal and heterogeneous data that we will model as edge-attributed graphs It is therefore to define a generic method for extracting periodic behavior in the edge-attributed graphs The global model thus constructed can then be used to explore and explain abnormal/exceptional behavior in the data This topic master who is in the field of knowledge discovery in large databases will rely on modeling as edge-attributed graphs The developed approach will advance the state of the art data mining with constraints, the methods of motif extraction, interactive data mining Experiments on data from photovoltaic central will be conducted Keywords : edge-attributed graphs, time series, FastRabbit, local pattern mining vi Table des figures 1.1 Structure des capteurs photovolta¨ıques [1] 1.2 Des arbres devant la fa¸cade et sur l’horizon [1] 2.1 Un exemple de Chromatic correlation clustering [2] 2.2 Un exemple de r´eseau social [3] 2.3 Une partition de Chromatic Correlation Clustering [3] 2.4 Coˆ ut de Chromatic Correlation Clustering [3] 2.5 Un exemple de graphe d’arˆetes-´etiquett´es [2] 10 2.6 Un exemple de clustering par Chromatic pivot [3] 11 2.7 Un exemple de clustering par Lazy Chromatic pivot [3] 12 2.8 Exemple d’un r´eseau bay´esien [4] 14 2.9 Exemple d’une s´erie temporelle 17 2.10 La diff´erence entre distance Euclidienne et distance DTW [5] 18 2.11 Un grid DTW [6] 18 2.12 Condition monotone [5] 19 2.13 Condition de continuit´e [5] 19 2.14 Condition de fronti`ere [5] 20 2.15 Condition de Warping Window [5] 20 2.16 Condition d’angle [5] 20 2.17 Une s´equence de la taille 128 est r´eduite en dimensions [7] 23 2.18 Le tableau statistique pour diviser la courbe Gaussienne [7] 23 2.19 Discretisation avec le nombre de symbol a = [7] 24 vii Algorithme : FastRabbit Input : C : the current context, Cand : the elements restrictions of C, S : the skyline - current set of patterns, M : the quality measures Output : The current skyline begin Compute the graph GC Y ← Y \ {e ∈ EC | χ2 (e, C) < 3.84 or q(e, C) < 0} for (X , Y ) ∈ connected components(GC = (X, Y ) for m ∈ M Calculate m(C, (X , Y )) if s ∈ S | s >M (C, (X , Y )) then S ← S ∪ (C, (X , Y )) \ {s ∈ S | (C, (X , Y )) >M s } 10 Σ Compute upper bounds qub (C), qubΣ (C) and q¯ub (C) if ∃s ∈ S such that |EC | ≤ me (s) and |VC | ≤ Σ mv (s) and qub (C) ≤ q Σ (s) and 11 12 13 qubΣ (C) ≤ q Σ (s) and q¯ub (C) ≤ q¯(s) then return S else 14 for l ∈ Cand 15 C ← C ∪ {l} 16 Cand ← Cand \ {l} 17 FastRabbit(C,Cand,S,M ) 18 C ← C \ {l} 19 return S 32 Chapitre Exp´ erimentation et r´ esultats Dans ce chapitre, nous pr´esentons des exp´erimentations et r´esultats pour montrer l’int´erˆet de l’approche propos´ee Tous les exp´erimentations sont effectu´ees sur un ordinateur avec le processeur Dual Core 2×2.6 GHz, GB de RAM et sous syst`eme d’exploitation Linux L’algorithme FastRabbit est impl´ement´e par langage C++ 4.1 R´ esultats quantitatifs Nous avons r´ealis´e des exp´erimentations avec plusieurs seuils de corr´elation pour ´evaluer la performance de l’algorithme en terme de temps d’ex´ecution et nombre de motifs d´etect´es Figure 4.1 montre le r´esultat : Le temps le plus grand pour ex´ecuter l’algorithme est heures 42 minutes, le temps d’ex´ecution moyen est heures 48 minutes Avec un seuil de corr´elation est grand, le graphe d’arˆetes-attribu´ees contient seulement des arˆetes qui sont bien corr´el´ees, il est moins dense que les graphes avec des corr´elations faibles, le temps d’ex´ecution est donc diminu´e Nous en concluons que plus petit le seuil de corr´elation, plus temps d’ex´ecution de33 Figure 4.1 – Performance de l’algorithme FastRabbit mand´e, autrement dit, le temps d’ex´ecution diminue lin´eairement avec la corr´elation Maintenant, observons le nombre de motifs de skyline, il est vari´e de 74 `a 89 motifs Nous n’avons pas une relation monotone entre le nombre de motifs avec le temps d’ex´ecution ou la corr´elation Apr`es avoir calcul´e le r´esultat, nous avons regroup´e des motifs similaires Le changement de nombre de motifs est pr´esent´e dans le figure suivante : Figure 4.2 – Nombre de motifs avant et apr`es post-traitement Nous voyons que le nombre de motifs a fortement diminu´e apr`es une tˆache de post-traitement Observons une exemple, avec le seuil de corr´elation 34 0.6, nous avons au d´ebut 79 motifs mais apr`es la post-traitement, il reste 29 motifs qui sont vraiment diff´erents Comme dans l’´etape d’´enum´eration des contextes pour explorer des motifs, nous avons des contextes similaires et ils donnent des mˆemes motifs C’est la raisons pour laquelle nous obtenons des r´esultats redondants 4.2 R´ esultats qualitatifs et Comparaison avec EMM 4.2.1 R´ esultats qualitatifs Nous explorons et analysons des motifs sp´eciaux sur le jeu de donn´ees du projet RESSOURCES-HBS Tout d’abord, nous essayons de visualiser la positions des capteurs (figure 4.3) d’apr`es la structure r´eelle, des capteurs en mˆemes types ont la mˆeme couleur Nous avons deux fa¸cades : l’ext´erieur et l’int´erieur Les capteurs qui commencent le nom par lettre ”T” mesure la temp´erature, lettre ”V” mesure le vente On n’a pas la position de certains capteurs sp´eciaux qui mesurent l’humidit´e, le soleil 35 Figure 4.3 – Visualisation des positions de capteurs Ensuite, nous ex´ecutons l’algorithme avec le seuil de corr´elation 0.6 Au d´ebut, avec le contexte g´en´eral , le graphe est tr`es dense (figure 4.4) Apr`es avoir finit l’algorithme, nous obtenons 29 motifs diff´erents Dans le figure 4.5, un motif exceptionnel pr´esente des interactions entre les capteurs Le contexte correspondant est : C = nonEnsoleillee, V entee, ∗ (Chaude ou pasChaude), correlation P earson ∈ [0.6; 1], distanceSAX ∈ [0; 5], distanceDT W ∈ [0; 15] Les qualit´es de ce motif sont : qualit´e totale d’arˆetes q Σ (Σe∈C (q(e, C)) = 78.38, qualit´e moyenne q¯ = 0.13, le nombre de sommet |V | = 95, le nombre d’arˆetes |V | = 572 Les jours correspondants avec le ph´enom`ene sont aussi filtr´es ` la fa¸cade de l’ext´erieur, nous proposons beaucoup de ph´enom`enes entre A les types de capteur diff´erents Concernant des capteurs sp´eciaux (le point noir en bas), nous n’avons pas beaucoup de ph´enom`enes int´eressants dans ce contexte Parmi les capteurs en mˆeme type et proches, nous avons pas des arˆetes entre eux Comme des arˆetes entre mˆeme type de capteur sont toujours tr`es 36 Figure 4.4 – Graphe d’arˆetes-attribu´ees avec contexte g´en´erale bien corr´el´es et ind´ependants avec le contexte, l’hypoth`ese null de teste du χ2 (e, C) est donc accept´e, on refuse ces arˆetes Autrement dit, des arˆetes entre des capteurs en mˆeme type ont la valeur χ2 (e, C) < 3.84 et ils sont rejet´es Figure 4.5 – Un motif d´etect´e par l’algorithme FastRabbit Observons un autre motif dans le figure 4.6, on voit beaucoup de interactions entre des capteurs (en bas) qui mesurent l’humidit´e, le soleil avec des autres Les physiciens du CETHIL peuvent cr´eer des hypoth`eses et consid´erer le r´esultat de ces capteurs 37 Figure 4.6 – Un motif d´etect´e par l’algorithme FastRabbit L’algorithme explore des autres types de motifs Figure 4.7 pr´esente un motif qui contient seulement capteurs Consid´erons les jours ”Ensoleill´ee”, nous d´etectons un motif comme dans le figure 4.8 Autre exemple, avec le jour type ”non vent´ee”, le motif comme dans le figure 4.9 est d´etect´e Figure 4.7 – Un graphe qui a seulement sommets 38 Figure 4.8 – Un motif avec le jour type ”Ensoleill´ee” Figure 4.9 – Un motif avec le jour type ”non Vent´ee” 39 4.2.2 Comparaison avec EMM Maintenant, nous comparons notre r´esultat avec le r´esultat effectu´e par l’approche Exceptional Model Mining (EMM) Avec EMM, il calcule d’abord le r´eseau bay´esien du jeu de donn´ees et puis d´etecte des sousgroupes qui ont le r´eseau bay´esien anormal Par exemple, avec l’entr´ee est distance SAX (EMM accepte seulement un attribut de l’entr´ee), le r´eseau bay´esien global est : Figure 4.10 – R´eseau bay´esien du jeu de donn´ees Juillet 2012 L’interd´ependence de ce mod`ele est : V entee → Ensoleillee → Chaude Des groupes exceptionnel ont le mod`ele diff´erent, par exemple : Figure 4.11 – Un groupe exceptionnel d´etect´e par EMM En comparant avec le mod`ele global, nous n’avons aucune relation entre des attributs cibl´es Une autre type de groupe exceptionnel d´etect´e par EMM : 40 Figure 4.12 – Un autre r´esultat exceptionnel Nous voyons que ce groupe pr´esente des jours o` u l’interd´ependence est : Chaude → V entee, vraiment diff´erent avec le mod`ele du jeu de donn´ees Chaque groupe est d´ecrit par condition de l’attribut entr´e, par exemple, avec le groupe dans figure 4.12, sa condition est : distance de capteurs ”II-Vd5” et ”II-Vg2” est inf´erieure que 4.196467 Figure 4.13 – Conditions pour d´eterminer un groupe En conclusion, notre algorithme FastRabbit et l’approche EMM font le mˆeme tˆache : d´etection des sous-groups anormaux dans un jeu de donn´ees Chaque sous-groupe est d´etermin´e par des conditions sur l’attribut entr´e et l’int´erˆet d’un motif est identifi´e par des mesures de qualit´e Le point diff´erent entre deux approches, EMM n’accepte qu’un attribut de l’entr´e alors que FastRabbit peut travailler avec un ensemble d’attributs comme l’entr´ee En plus, EMM montre seulement le mod`ele g´en´eral d’un groupe exceptionnel, il ne pr´esente pas des interactions entre des ´el´ements du groupe Par contre, en utilisant des technique du graphe, FastRabbit montre clairement le structure du motif exceptionnel, les interactions entre des ´el´ements ansi que le changement, l’´evolution des sous-groupes dans les conditions diff´erents 41 Chapitre Conclusion Dans ce m´emoire, nous avons pr´esent´e une m´ethode pour extraire des motifs d’optimum Pareto (skyline) dans le graphe d’arˆetes-attribu´ees Notre objectif est de trouver des composantes connexes extrˆemes significatives en donnant certains contraintes Ce probl`eme a beaucoup d’applications dans des domaines diff´erents, particuli`erement dans des syst`eme de recommandation [13, 14, 15, 16] Pour obtenir le r´esultat dans ce projet, nous avons calcul´e les distances DTW et SAX entre des capteurs afin de d´efinir des attributs d’une arˆete dans le graphe d’arˆetes-attribu´ees En effectuant le teste statistique χ2 , nous v´erifions une valeur significative d’un motif Et puis, nous introduisons mesures pour ´evaluer la qualit´e d’un motifs Ensuite, l’algorithme FastRabbit est pr´esent´e pour explorer des motifs sous contraintes L’espace de recherche est r´eduit en utilisant des upper-bounds Des exp´erimentations, qui sont effectu´ees sur le jeu de donn´ees du laboratoire thermique CETHIL, montrent l’efficacit´e de l’algorithme au niveau quantitatif et qualitatif Grˆace des motifs d´etect´es, nous pourrions ´eliciter des nouvelles hypoth`eses qu’on ne peut pas faire avec des approches existantes En perspective pour la suite des travaux, nous voudrions faire une analyse interactive `a plus grand ´echelle, non seulement dans le mois Juillet 42 2012 mais aussi dans tout une ann´ee Autre cˆot´e, des explorations dans une p´eriode plus court, e.g heures, peuvent ˆetre consid´er´ees Une direction importante pour le futur travail est d’am´eliorer la performance de l’algorithme FastRabbit L’identification des contextes diff´erents qui donnent mˆeme motif peut ˆetre une bonne id´ee pour r´eduire le temps d’ex´ecution 43 R´ ef´ erences [1] C Menezo H Pabiou L Gaillard, S Giroux-Julien Experimental evaluation of a naturally ventilated pv double-skin building envelope in real operating conditions, 2014 [2] Francesco Bonchi, Aristides Gionis, Francesco Gullo, and Antti Ukkonen Chromatic correlation clustering In KDD, pages 1321–1329, 2012 [3] Edo Liberty Francesco Bonchi, David Garcia-Soriano Correlation clustering : from theory to practice In ACM SIGKDD, 2014 [4] W Duivesteijn, A Knobbe, A Feelders, and M van Leeuwen Subgroup discovery meets bayesian networks – an exceptional model mining approach In Data Mining (ICDM), 2010 IEEE 10th International Conference on, pages 158–167, Dec 2010 [5] Elena Tsiporkova Dynamic time warping algorithm In SIGKDD, 2012 [6] Steve Cassidy Tutorial matching patterns in time [7] Li Wei Jessica Lin, Eamonn Keogh and Stefano Lonardi Experiencing sax : a novel symbolic representation of time series In DMKD Journal, 2007 44 [8] Dennis Leman, Ad Feelders, and Arno Knobbe Exceptional model mining In Machine Learning and Knowledge Discovery in Databases, volume 5212, pages 1–16 Springer Berlin Heidelberg, 2008 [9] David Heckerman, Dan Geiger, and DavidM Chickering Learning bayesian networks : The combination of knowledge and statistical data Machine Learning, 20(3) :197–243, 1995 [10] Guo-Jun Qi, Charu Aggarwal, Qi Tian, Heng Ji, and Thomas Huang Exploring context and content links in social media : A latent space method IEEE Trans Pattern Anal Mach Intell., 34(5) :850–862, May 2012 [11] Eamonn Keogh A Tutorial on Indexing and Mining Time Series Data In The 2001 IEEE International Conference on Data Mining University of California - Riverside, 2001 [12] Chotirat Ann Ratanamahatana and Eamonn Keogh Everything you know about dynamic time warping is wrong In SIAM International Conference on Data Mining, 2004 [13] W Lee, S Stolfo, and P Chan Learning patterns from unix execution traces for intrusion detection In AAAI workshop on AI methods in Fraud and Risk Management, 1997 [14] W Lee, S Stolfo, and K Mok Data mining framework for building intrusion detection models In IEEE Symposium on Security and Privacy, 1999 [15] S Ma and J Hellerstein Mining partially periodic event patterns with unknown periods In IEEE International Conference on Data Engineering, 2001 45 [16] H Mannila, H Toivonen, and A I Verkamo scovering frequent episodes in sequences In ACM KDD Conference, 1995 46