Marc Plantevit

User Tools

Site Tools

Trace:
prim1314triggering

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision 		Previous revision
Next revision Both sides next revision
prim1314triggering [2013/10/15 17:09]
mplantev 		prim1314triggering [2013/10/15 17:12]
mplantev
Line 13: Line 13:
 ==== Existant ==== ==== Existant ====
 Dans ce contexte, l'équipe Data Mining and Machine Learning (DM2L, LIRIS) s'intéresse à expliquer les changements des valeurs de mesures topologiques d'un noeud dans un graphe dynamique par la variation des valeurs de ses attributs dans le passé. En d'autre termes, on cherche à répondre à la question suivante "Quels sont les changements des propriétés d'un noeud qui vont, plus tard, changer aussi son rôle dans le graphe ?". Pour cela, un algorithme a été défini afin d'extraire des motifs gâchettes illustrés dans la figure 1. On note a+ la variation positive (supérieure à 2) des valeurs de l'attribut a entre deux pas de temps consécutifs. On observe alors le motif [ {a+,b+},{c-},{deg+} ] qui se lit "La variation positive forte de la valeur de a et b est suivie d'une variation négative forte de c, finalement suivie par une variation positive forte du degré du noeud considéré. Sur la figure, on voit que ce motif est supporté par 2 noeuds. Etant donnée un graphe dynamique attribué, l'objectif de l'algorithme est alors d'extraire tous les motifs gâchettes respectant certaines propriétés bien définies. Dans ce contexte, l'équipe Data Mining and Machine Learning (DM2L, LIRIS) s'intéresse à expliquer les changements des valeurs de mesures topologiques d'un noeud dans un graphe dynamique par la variation des valeurs de ses attributs dans le passé. En d'autre termes, on cherche à répondre à la question suivante "Quels sont les changements des propriétés d'un noeud qui vont, plus tard, changer aussi son rôle dans le graphe ?". Pour cela, un algorithme a été défini afin d'extraire des motifs gâchettes illustrés dans la figure 1. On note a+ la variation positive (supérieure à 2) des valeurs de l'attribut a entre deux pas de temps consécutifs. On observe alors le motif [ {a+,b+},{c-},{deg+} ] qui se lit "La variation positive forte de la valeur de a et b est suivie d'une variation négative forte de c, finalement suivie par une variation positive forte du degré du noeud considéré. Sur la figure, on voit que ce motif est supporté par 2 noeuds. Etant donnée un graphe dynamique attribué, l'objectif de l'algorithme est alors d'extraire tous les motifs gâchettes respectant certaines propriétés bien définies.
 +
 +
 +{{ ::r.png?800 |Deux exemples du graphe induit par les noeuds supportant un motif extrait à partir de données réelles}}
 +
 +
 +==== Travail Demandé ====
 +
 +Tout d'abord, il s'agira de se familiariser avec les notions classiques de fouilles de motifs (séquentiels), et des propriétés de graphes. Il faudra ensuite comprendre l'algorithme, composé de trois étapes : description de chaque noeud par une séquence de variations de valeurs d'attributs, fouille de motifs caractéristiques, et post-traitement de ces motifs. Il sera demandé de programmer les étapes une et deux en C++ (Code java existant dans un certaine mesure) et d'expérimenter l’algorithme sur trois jeu de données existants : un réseau de co-auteurs de publications scientifiques (DBLP), un réseau du trafic aérien aux États-Unis (RITA), et enfin des données issues du site del.ico.us. L'interprétation des résultats d'expérimentation vous pousserons à vous questionner sur les choix faits pour caractériser ce qu'est une "variation de valeur d'attribut".
 +
 +==== Bibliographie ====
 +  * Dong, G. et J. Li (1999). Efficient mining of emerging patterns : discovering trends and dif- ferences. In Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, KDD ’99, New York, NY, USA, pp. 43–52. ACM.
 +  * Pei, J., J. Han, B. Mortazavi-Asl, H. Pinto, Q. Chen, U. Dayal, et M. Hsu (2001). Prefixspan : Mining sequential patterns by prefix-projected growth. In D. Georgakopoulos et A. Buch- mann (Eds.), ICDE, pp. 215–224. IEEE Computer Society.
 +  * Yan, X., J. Han, et R. Afshar (2003). Clospan : Mining closed sequential patterns in large databases. In D. Barbará et C. Kamath (Eds.), SDM. SIAM.
 +  * E. Desmier, M. Plantevit, C. Robardet, and J.-F. Boulicaut. Trend mining in dynamic attributed graphs. In ECML/PKDD, pages 654–669, 2013.
 +
 +
prim1314triggering.txt · Last modified: 2013/10/15 17:15 by mplantev

Page Tools

CNRS INSA de Lyon Université Lyon 1 Université Lyon 2 École centrale de Lyon