Ce site est en jachère. Vous pouvez me retrouvez par la : http://www.comeetie.fr

Je cherche un étudiant de master  recherche pour faire un stage, sur l’étude de graphe de mobilité. Si cela vous intéresse, n’hésitez pas à me contacter. Le sujet un peu détaillé suit.

Etude de données de mobilité (matrice-origine destination) à l’aide d’outils d’analyse de graphes.

Les données de mobilités (domicile-travail, domicile lieu d’étude, …) peuvent être représentées sous la forme d’un graphe orienté valué donnant pour chaque couple de zones géographiques (communes ou autres) le flux estimé entre ces deux zones. Ces données présentent différentes particularités intéressante liées à leur nature multi-échelle (c’est à dire présentant différentes échelles d’analyse pertinentes). De plus elles sont disponibles pour différents pays et différentes dates (FRANCE 2007, USA 2000, USA 1990 par exemple).

Pour explorer et analyser ces données de grande taille de manière pertinente, les avancées théoriques obtenues ces dernière années dans le domaine de l’analyse des réseaux [1,2,3] peuvent être mobilisées. Celles-ci sont appliquées dans des domaines aussi divers que la biologie [4], l’étude du web [5], … et proposent un cadre formel fédérateur et pertinent dans le contexte des données de mobilités. Ces méthodes permettent par exemple de rechercher des modules ou communautés de nœuds densément connectés dans un graphe ou bien encore de proposer une modélisation fine du réseau faisant intervenir différentes groupes de noeuds aux propriétés structurels différentes [4].

L’objectif de se stage consiste à tester et évaluer différentes méthodes issues de la théorie des réseaux telles que les algorithmes de clustering hiérarchique de graphe [6, 7,3] et les modèle de mélange d’Erdos-Renyi et dérivés [4, 5] sur les données de mobilité en vue de leur exploration et de leur analyse comparative (à différentes échelles). L’extraction d’aires d’influences à différentes échelles sera l’un des objectifs visés ainsi que leur caractérisation et
comparaison (temporelle ou spatiale).

Les connaissances scientifiques requises sont relatives aux champs de l’apprentissage statistique et de l’analyse des réseaux. Une bonne connaissance des environnements de calculs R ou Matlab et de la programmation est également nécessaire pour aborder ce stage. De plus le candidat devra se montrer intéressé par des thèmes connexes (ville, mobilité).

Une indemnité de stage est prévue.

Mots-clefs : mobilité, graphe, clustering de graph, hiérarchique, modèle de mélange d’Erdos Renyi
Bibliographie

[1] A. Barabasi. Linked: The New Science of Networks, Plume Book editor, 2002
[2] M. Newman. Network an introduction, Oxford University Press, 2010
[3] S. Fortunato, Community detection in graphs, Physics Reports Volume 486, Issues 3-5, February 2010, Pages 75-174
[4] P. Latouche. Modèles de graphes aléatoires à structure cachée pour l’analyse des réseaux. Thèse de l’université d’Evry Val d’Essone. 2011.
[5] H. Zanghi. Approches modèles pour la structuration du Web vu comme un graph. Thèse de l’université d’Evry Val d’Essone. 2010.
[6] D. Gleich. Hierarchical directed spectral graph partitionning. Technical report, Standford University, 2006.
[7] J. Baro, Etude préliminaire des méthodologies d’extraction de structures urbaines a partir de données de population sur grille régulières et de données relatives au transport sous forme de graphe, Rapport de Master M2 MVA Cachan, 2011.

Lieu du stage :

IFSTTAR, Institut Français des Sciences et Technologies des Transports de l’aménagement et des Réseaux.
Unité de Recherche GRETTIA
2, rue de la Butte Verte ;
93160 Noisy-le-Grand

Contact :

Etienne Côme, Patrice Aknin
Tél : 01 45 92 56 57, 01 45 92 56 38
E-mail : etienne.come@ifsttar.fr, patrice.aknin@ifsttar.fr

Voici quelques expérimentations réalisées avec la bibliothèque javascript de visualisation de données d3 pour apprendre à m’en servir. Cette bibliothèque permet de construire différentes visualisations interactives en html/svg assez facilement à partir de jeux de données json où csv. Je m’en suit servie pour construire 4 interfaces permettant d’analyser les résultats du premier tour des primaires socialiste. Les différentes interfaces que j’ai construites visent donc à analyser les votes obtenus par les différents candidats (données disponible sur le site de la primaires ou en csv sur datapublica) en les contextualisant géographiquement (positions des communes, département, région,…) et socialement (Population de la communes (ville/campagne), %Population + de 60 ans, %Ménages imposés, Salaire médian). Pour ce faire j’ai construit un jeu de données contenant les résultats par communes ainsi que des variables de contexte décrivant chaque communes, il est disponible ici et a été généré grâce à des données de l’INSEE (disponibles ici et là) et aux résultats par bureaux de votes. Pour tester les interfaces cliquez sur celle qui vous plaît :

	Carte du nombre de voix de chaque candidat pour chaque communes.
	Box plot interactif des résultats de chaque candidats (possibilité de filtrer les communes considérées suivant différents critères).
	Treemap de la répartition des voix de chaque candidats par région / département
	Sunburst de la répartition des voix de chaque candidats par région / département

Je suis tombé il y a peu sur une représentation sympa du royaume-unis a partir des positions des McDO.

Comme je suis curieux je voulais savoir ce que ça donnerait en France, et voila le résultat :Pas vraiment de grosse surprise, la carte colle aux données de densité de population (la carte suit), à part peut être pour la route des week-end en Normandie qui se détache bien.  McDO a bien pensé aux parisiens pris dans les bouchons, avec un McDO tous les 10 km environ !

Pour finir j’ai réalisé la même carte mais avec les super-marchés discount (LIDL, ED, …), pas de différences énormes : le nord et l’est de la France semblent juste un plus pourvus que les autres.

Random Walks par Justin.

Comme je n’ai pas posté depuis longtemps je profite de la présentation que j’ai faite hier pour donner des nouvelles de quelques travaux entamés avec des géographes. La présentation est disponible sur ma page de présentation via slideshare. J’y raconte ce que nous commençons à faire à partir de données de densité de population sur grille régulière et de graphes de mobilités. Nous, nous intéressons pour le moment à des problèmes de segmentation (ou clustering) multi-échelles.

Pour les données de types graphes orienté, nous avons commencé à tester une implémentation d’un algorithme de clustering spectral récursif (un bon tuto sur les bases du clustering spectral en Matlab est disponible sur l’ancien site de David Gleich). Les articles de bases peuvent quand à eux être trouvés ici [Shi & Malik] et là [Ng & Jordan …] par exemple.

Mais de manière rapide ces méthodes se basent sur les vecteurs propres associés aux plus petites valeurs propre du Laplacien du graphe où du Laplacien normalisé d’où le spectral. Ces vecteurs sont en effet les solutions relâchées (contraintes entières relaxées)  de problèmes de maximisation associés à la recherche de coupes du graphe optimale au sens de la normalized cut … Enfin, l’utilisation d’un algorithme récursif permet d’extraire des structures apparaissant à différentes échelles.

Voici par exemple quelques résultats visuels obtenus sur le graphe de mobilité (domicile/travail) entre plus de 36000 communes fourni par l’insee (téléchargeable ici), les images correspondent à la matrice d’adjacence ré-ordonnées par l’algorithme à différentes échelle d’étude.

Matrice d’adjacence globale ré-ordonnée (la région parisienne se distingue bien par le nombre de navettes quelles génère avec des villes éloignées).

En faisant un premier zoom sur le cluster du bas correspondant au sud-ouest de la France on retrouve le même genre de structure.

Un nouveau zoom pour faire apparaître des structures plus fines.

Dernier zoom on distingue maintenant bien Bordeaux qui génère beaucoup de navettes et son cluster.

Forcément comme le graphe est orienté, nous regardons comment prendre en compte l’orientation. Pour le moment nous n’avons essayé que quelques solutions assez simples basées sur des symétrisations ayant des propriétés sympathiques (détails ici [Gleich] et là [Chung]).

Je suis allé la semaine dernière à Statlearn 2011, une conférence francophone sur l’apprentissage statistique. Beaucoup d’exposés concernaient la sparsité avec en vue des application en bio-statistique. J’en profite pour mettre des liens vers les présentations qui m’ont particulièrement intéressées. L’illustration est tirée des slides de Francis Bach et concerne l’apprentissage de dictionnaires  adapté aux données avec a priori hiérarchique, appliqué à des données textuelles en l’occurrence les abstracts de NIPS si mes souvenirs sont bons.

 

 

Pour ce qui est des présentations que j’ai plus particulièrement appréciées :

• Bach, Francis (INRIA Paris, Ecole Normale Supérieure) : Sparse Hierachical Dictionary Learning [slides.pdf]
  (Voir la partie concernant le « dictionnary learning » en particulier lorsqu’un a priori hiérarchique est utilisé)
• Grandvalet, Yves (CNRS, UTC) : Sparsity in learning [slides.pdf]
  (Voir la conclusion en particulier la problématique sur « l’indexations des modèles »)
• Vert, Jean-Philippe (Mines ParisTech, Institut Curie) : Including prior knowledge in machine learning for genomic data [slides.pdf]
  (Voir la partie sur la segmentation de signaux avec des méthode de type lasso adaptées)
• Antoniadis, Anestis (LJK, Université Joseph Fourier) : Regularizarion and shrinkage for model selection in sparse GLM models[slides.pdf]
  (Pour l’ensemble, les ponts faits entre les différents domaine ondelettes, images, apprentissage statistique)

Un ensemble de support de cours utilisés par des profs du département d’économie du MIT pour parler des graphes, de leurs propriétés théorique (seuil de transition de phase dans des modèle simple e.g. « Erdos-Renyi »), de leurs utilités en modélisation (diffusion,…) assez matheux à l’américaine dans l’ensemble.

 

Lecture Notes:

Lecture 1 – Introduction
Lecture 2 – Graph Theory and Social Networks
Lecture 3 – Erdos-Renyi Graphs and Branching Processes
Lecture 4 – Erdos-Renyi Graphs and Phase Transitions
Lecture 5 – Generalized Random Graphs and Small-World Model
Lecture 6 – Growing Random Networks and Power Laws
Lecture 7 – Search on Networks: Navigation and Web Search
Lecture 8 – Diffusion through Networks
Lecture 9 – Introduction to Game Theory-1
Lecture 10 – Introduction to Game Theory-2
Lecture 11 – Introduction to Game Theory-3
Lecture 12 – Applications of Game Theory to Networks
Lectures 13 and 14 – Evolution and Learning in Games
Lecture 15 – Repeated Games and Cooperation
Lecture 16 – Cooperation and Trust in Networks
Lectures 17 and 18 – Network Effects
Lectures 19-21 – Bayesian Nash Equilibria, Auctions and Introduction to Social Learning
Lectures 22 and 23 – Social Learning in Networks
Lecture 24 – Decisions in Groups

Problem Sets:
Problem Set 1
Problem Set 2
Problem Set 3
Problem Set 4
Problem Set 5

Une nouvelle interface graphique pour R…

R dans sa version classique c’est un terminal + un éditeur de texte quelconque + des fenêtres graphiques et c’est donc pas forcément ce qu’il y a de plus ergonomique. Et ce n’est pas donc pas ce qui mets le plus en confiance des débutants, je le sait pour avoir fait quelque TP de R avec des étudiants un peu perdu. Du coup le projet R-studio qui propose une interface globale intégrant graphiques, ligne de commande, édition de code et même d’article via sweave semble sympathique et pertinente. L’interface ressemble à celle d’un Matlab et intègre tout ce qu’il faut pour bien travailler. Je n’ai pas encore testé mais je le ferais sans doute rapidement et en parlerai donc peut être encore à l’occasion.

Certaines vidéo de présentations NIPS sont sur vidéo lecture :

• Les présentations invités : http://videolectures.net/nips2010_vancouver/ avec M. Jordan …
• Les Workshops : http://videolectures.net/nipsworkshops2010_whistler/ avec Yves Grandvallet et SIMOnE 🙂

Du beau monde et sans doute plein d’idées intéressantes à regarder.