Analyse Exploratoire De Flots De Liens Pour La Détection D .
Analyse exploratoire de flots de lienspour la détection d’événementsSébastien HeymannThèse encadrée par M. Latapy et C. Magnien pendant 2 ans et parB. Le Grand la 3e année.1 / 45
Flot de liens trace d’interactions ordonnées chronologiquement entredifférentes paires d’entités.1 : (A) -[interagit avec]- (B)2 : (C) -[interagit avec]- (D)3 : (B) -[interagit avec]- (C)4 : (C) -[interagit avec]- (A)5 : (B) -[interagit avec]- (D)6 : (E) -[interagit avec]- (F).2 / 45
Graphe de flot de liens1:2:3:4:5:6:.(A) -[interagit avec]- (B)(C) -[interagit avec]- (D)(B) -[interagit avec]- (C)(C) -[interagit avec]- (A)(B) -[interagit avec]- (D)(E) -[interagit avec]- (F)3 / 45
Représentation du mondeLes graphes représentent des mesures de systèmes complexesréels ou simulés.mesure ? analyse ? visualisation ? modélisation ? prédiction ?4 / 45
Analyse exploratoire de graphes1voir le grapheex : diagramme noeuds-liens32interagir en temps réelex: Gephi (2008)grouper, filtrer, calculer des métriques.construire un langagevisuelcouleurs, volumes, formes.Publications : [chap. Gephi Comp.Net 14]5 / 45
Pourquoi visualiser des données ?« The greatest value of a pictureis when it forces us to noticewhat we never expected to see. »John Tukey (1962)6 / 45
Une visualisation dynamique de flotde liensAndré Panisson - The Egyptian Revolution on Twitter, made with Gephi7 / 45
ProblématiqueConcepts à définir et formaliser Dynamique régulière Événement significatifContraintes Démarche exploratoire sans connaissance a priori Passage à l’échelleObjectifs Quand scruter des événements ? Qui est impliqué dans chaque événement ?8 / 45
Comment détecter desévénements ? Événement anomalie temporelle. Pas de définition claire et universelle. Dépend des cas et des hypothèses de départ. Anomalies : identifier les valeurs qui dévient remarquablementdes autres (Grubbs, 1969).9 / 45
10 / 45
Contributions1Détection automatique d’anomalies. nouvelle méthode statistique : Outskewer validation expérimentale2Détection automatique d’événements. notion de fenêtre temporelle unité de temps : intrinsèque vs extrinsèque largeur de fenêtre3Cadre exploratoire et étude de cas. méthodologie unifiée : statistiques et visualisation prototype application à Github.com11 / 45
Détection d’anomalies : approachesclassiquesHypothèse : données distribution normale.Distance valeurs réelles /valeurs théoriques.12 / 45
Coefficient d’asymétrien(n 1)(n 2) Px Xxx moyenneécart type 3densitydensityγ xFigure: γ 0γ 0Exemple de distributions asymétriques.13 / 45
Coefficient d’asymétriedensity0.40.0 10 4x049Figure: Exemple de distribution normale avec valeurs extrêmes (rouge).Sensible aux valeurs extrêmes (min/max) loin de la moyenne !14 / 45
Postulat de OutskewerNotre définitionAnomalie valeur extrême qui rend la distribution asymétrique.Notre méthodeSignature d’asymétrie évolution du coefficient d’asymétriequand on retire les valeurs extrêmes une à une.Implication (distribution homogène)Si présence d’anomalies : l’asymétrie devrait tendre vers 0.Implication (distribution hétérogène)Si le retrait d’un grand nombre de valeurs ne réduit pasl’asymétrie, alors la distribution est hétérogène, donc il n’existe pasd’anomalie selon notre définition.15 / 45
Détection automatique d’anomaliesAnalyse de la signature d’asymétrie avec seuillage adaptatif.Outskewer classe chaque valeur comme :anomalieanomalie potentiellenormalou ’inconnu’ pour les distributions de valeurs hétérogènes.X { 3, 2, 1, 0, 1, 2, 3, 7}16 / 45
Pertinence pour les graphes réels ?Loi normale (cas homogène)0.4Loi de puissance (cas hétérogène)densitydensity30.00 4x040.01% d’anomalies pour n 1000x50.01% d’anomalies pour n 100017 / 45
Conclusions sur Outskewer Méthode de détection automatique d’anomalies. Pas de connaissance a priori sur les données. Pertinent dans différents cas statistiques.Publication : [ASONAM 12]18 / 45
Contributions1Détection automatique d’anomalies. nouvelle méthode statistique : Outskewer validation expérimentale2Détection automatique d’événements. notion de fenêtre temporelle unité de temps : intrinsèque vs extrinsèque largeur de fenêtre3Cadre exploratoire et étude de cas. méthodologie unifiée : statistiques et visualisation prototype application à Github.com19 / 45
Détection d’événements1. Mesurea) fenêtre temporelle de taillew sur un flot de liens.b) graphe de chaque fenêtre àintervalle i.c) propriété calculée pourchaque graphe : sérietemporelle.20 / 45
Détection d’événements2. Classification OutskewertimeWoa) fenêtre temporelle de taillewo sur la série temporelle.b) chaque valeur est classéewo fois (chaque fenêtre vote).c) classe finale : la plusfréquente pour chaque valeur(vote à la majorité simple).Applicable en tempsréel !21 / 45
Population française au 20e siècleNombre d’habitants par anpopulation60M50M 40M1900 1920 1940 Year 1960 1980 2000 populationDifférence entre les années10000005000000 500000 1000000 1500000statusnot oupotentoutlier190019201940Year19601980200022 / 45
Harry Potter sur eDonkey# outliers / dayNombre d’anomalies par jour75in theatreunknown eventpirate release05015 Jul24 Aug12 OctDateDonnées : recherches sur le réseau P2P eDonkey. # requêtes contenant “half blood prince” par heure, calculéestoutes les 10 minutes. durant 28 semaines. sur 205 millions de requêtes. pour 24,4 millions d’adresses IP. http://antipaedo.lip6.fr23 / 45
Changements de régimex 5010050100t 543210 1 2 200not outlierpotential outlieroutlier unknown 0 150 200not outlier potential outlier outlier unknown 0150t543210 1 250100150t50100t 200 543210 1 2not outlier potential outlier outlier unknown 0 150543210 1 2200not outlier potential outlier outlier unknown 0x 0543210 1 2not outlierpotential outlierunknown x x543210 1 2xxVideo50100t 150200 not outlierpotential outlier050100t15020024 / 45
Données Github.com Exemples d’interactions ajouter du code. rapporter un bug. commenter un bug. éditer le wiki.”qui contribue à quel projet logiciel” 336 000 utilisateurs et projets observés durant 4 mois. 2 200 000 interactions enregistrées séquentiellement (avectimestamps). ”population” complète de Github et non un échantillon. http://www.githubarchive.org25 / 45
Quelle unité de temps ?wtimeMontres, sablier, horloge atomique : du ”temps spatialisé” (E. Klein).26 / 45
Quelle unité de temps ?Temps extrinsèque (temps usuel)Temps mesuré avec des unités comme la seconde, minute, .27 / 45
Temps extrinsèquew 1 heure, i 5 minutes. Cycles journaliers et hebdomadaires. Événements difficilement repérables sans modèle.28 / 45
Quelle unité de temps ?Temps extrinsèque (temps usuel)Temps mesuré avec des unités comme la seconde, minute, .Révèle habituellement des phénomènes exogènes, ex cyclesjour-nuit.Temps intrinsèque (lié à la dynamique du graphe)Temps mesuré avec des unités comme la transition de 2 états dugraphe. Ex. 1 apparition d’un lien dans un flot de liens.Meilleur pour révéler des phénomènes endogènes ?29 / 45
Temps extrinsèque vs tempsintrinsèque30 / 45
Temps intrinsèqueHaute résolutionDisparition de la dynamique exogène.31 / 45
Taille de fenêtre ?Haute résolutionw 1000 liens, i 100 liens.Basse résolutionw 50, 000 liens, i 1000 liens.32 / 45
Conclusions sur la détectionautomatique d’événementsMéthode Applicable en temps réelUnité de temps Notion d’unité de temps : invention humaine Temps intrinsèque : lié à la dynamique du graphe Travaux en coursTaille de fenêtre Semble liée à la résolution des événements Pas de résolution optimale ?Publications : [INFORSID 13] [RCIS 13] [WebSci 13] [ASONAM 13]33 / 45
Contributions1Détection automatique d’anomalies. nouvelle méthode statistique : Outskewer validation expérimentale2Détection automatique d’événements. notion de fenêtre temporelle unité de temps : intrinsèque vs extrinsèque largeur de fenêtre3Cadre exploratoire et étude de cas. méthodologie unifiée : statistiques et visualisation prototype application à Github.com34 / 45
Méthodologie unifiée12345Définir une fenêtre temporelle de taille w liens.Extraire le graphe de chaque fenêtre à intervalle i.Calculer une propriété sur chaque graphe.Détecter des événements dans la série temporelle résultante.Analyser ces événements par la visualisation de graphes.35 / 45
Analyse visuelle des événements1Sélectionner un événement détecté par Outskewer.2Identifier un motif anormal dans le sous-graphe correspondantde taille wv w .Interpréter l’événement. Vérifier que le motif est unique aumoyen d’un diagramme d’activité.3 Si motif unique : événement validé Sinon événement non validé, chercher un autre motif.36 / 45
Diagramme d’activité S’applique à un ensemble de nœuds. Fréquence des liens entre cet ensemble et le graphe. Axe horizontal : temps. Couleur : intensité de l’activité (noir ou nuances de vert).Diagramme d’activité du projet ”mxcl/homebrew” (github.com).Ce projet reçoit des contributions tout au long de la période decapture des données.37 / 45
PrototypeBasé sur le logiciel Linkurious38 / 45
Étude de cas : Github.comSérie temporelle du nombre de noeuds uniques sur le flot de liensde Github, avec w 10000 liens et wo 200 liens.39 / 45
Exemple d’événement validé Lien très récurrent entre l’utilisateur ”mapserver-trac-import”et le projet ”mapserver/mapserver” lors de l’événement 423000(période en vert clair). Migration d’un dépôt logiciel de Trac vers Github grâce à unutilisateur ”bot”. A investiguer : autre période d’activité plus tôt (vert peuintense).40 / 45
Exemple d’événement validéVisualisation des liens de l’utilisateur ”aruiz” lors de l’événement1420000 avec wv 1000 et son diagramme d’activité.41 / 45
Exemples d’événements rejetésDiagramme d’activité entre l’utilisateur ”pjcozzi” et le projet”AnalyticalGraphicsInc/cesium” lors de l’événement 1303000. Lemotif est récurrent.Publications : [CHItaly 13] [EGC 14] [chap. Gephi Comp.Net 14]42 / 45
Conclusions généralesDétection automatique d’anomalies Méthode statistique automatique : Outskewer. Validation sur des données réelles et simulées.Détection d’événements dans des grands flots de liens Paramètres de la fenêtre temporelle et impact sur lesévénements. Analyse des événements par fouille visuelle interactive. Validation possible et interprétation des événements.Cadre exploratoire Prototype interactif. Étude de cas sur Github.com43 / 45
Perspectives Complexité algorithmique et optimisation. Comparer à d’autres méthodes. Hypothèses de départ ? Approfondir l’étude du temps intrinsèque Unité représentative de la dynamique ? ex : triangle observé Évaluer par des utilisateurs réels. Généraliser à d’autres jeux de donnéesex : télécom, détection de fraude.EU COST Action 2013-2017Start-up francilienne44 / 45
PublicationsASONAM 12 Heymann, Latapy and Magnien. Outskewer : Using Skewness toSpot Outliers in Samples and Time Series.CHItaly 13 Uboldi et al., Knot : an Interface for the Study of Social Networks inthe Humanities.INFORSID 13 Heymann and Le Grand. Suivi de la Dynamique Intrinsèque desInteractions entre Utilisateur et SI.RCIS 13 Heymann and Le Grand. Monitoring User-System Interactionsthrough Graph-Based Intrinsic Dynamics Analysis.WebSci 13 Heymann and Le Grand. Towards A Redefinition of Time inInformation Networks ?ASONAM 13 Albano et al., A Matter of Time - Intrinsic or Extrinsic - forDiffusion in Evolving Complex Networks.chap. Gephi Comp.Net 14 Heymann and Le Grand. Exploratory Network Analysis :Visualization and Interaction. à paraı̂tre dans Complex Networks andtheir Applications.Encycl. SNAM 14 Heymann, Gephi. à paraı̂tre dans Encyclopedia of Social Networksand Mining.EGC 14 Heymann and Le Grand. Investigation visuelle d’événements dans ungrand flot de liens. à paraı̂tre à EGC 2014.45 / 45
Pertinence pour les graphes r eels? Loi normale (cas homog ene) x density 0.0 0.4-4 0 4 0.01% d’anomalies pour n 100 Loi de puissance (cas h et erog ene) x density 0 3 0 5 0.01% d’anomalies pour n 1000 17/45
La matrice de variances-covariances de X est une matrice 4x4 (note d 4 NX dans la notation de LISREL). Pour la calculer on utilise le fait que les erreurs sont indépendantes des variables latentes et donc que E( 0. Ainsi, en général, () a une forme semblable à celle rencontrée en analyse factorielle exploratoire,
ANDLER M., BLOCH J.D et MAILLARD B. Exercices corrigés de Mathématiques [Edition Marketing] 1.A Analyse : Topologie 1.B Analyse : Fonctions numériques 2 Analyse : Suites et Séries numériques 3 Analyse : Analyse Fonctionnelle 5 Algèbre générale, polynômes 6 èr
Il s'agit uniquement d'un logiiel d'aide à la décision et il nécessite de la part du directeur de thèse une analyse fine du rapport généré. L'analyse du manuscrit est sous la responsabilité du directeur de thèse qui atteste, via le rapport d'analyse et le formulaire à fournir dans le dossier de soutenance, avoir analysé le
Traitement des données Chapitre 4 : Analyse factorielle des correspondances, rev 11/03 Chapitre 4 : Analyse factorielle des correspondances binaires Objet - L'analyse Factorielle des Correspondances ou AFC constitue une technique d'analyse statistique d'un ou de
L’analyse de l’activité et du risque d’exploitation L’analyse fonctionnelle de la structure financière L’analyse patrimoniale de la structure financière Les ratios Le tableau de financement Les éléments prévisionnels Chapitre 00.qxp_Zoom's
3.9. ANALYSE DES OUTILS PÉDAGOGIQUES MIS EN PLACE 3.9.a) Analyse sur la cohérence des échelles de mesure 3.9.b) Analyse intrinsèque des quatre outils 3.9.c) Analyse des liens potentiels entre notre définition de l'autonomie et les outils 3.9.d) Relation entre les résultats du groupe et les présences. AN
3. Collecte de données, analyse et rapport sur les postes de pesage 33 3.1. Introduction 33 3.2. Collecte, analyse et communication des données 34 3.3. Collecte, analyse et communication des données 36 3.4. Méthode de vérification et d'analyse des données 40 3.5. Présentation des rapports 41 3.6.
Am I my Brother’s Keeper? Acts 15:19-35 Introduction: Since the beginning of time when the first man and woman rebelled against God, mankind has been separated from God. Every person since that time has been born into that rebellion and sin. Because of sin, people are separated from God and are unable to have a right relationship with Him or each other. Ill. of evil and suffering Inside of .
