Publié par : ecome | juin 23, 2011

Quelques travaux en cours

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]).

Publicités

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s

Catégories