Pavage et magie, rotations et symétries

(oui, mon fils voulait une rime dans le titre… promis on va tenter de faire une comédie musica…

(oui, mon fils voulait une rime dans le titre… promis on va tenter de faire une comédie musicale à partir de mes billets). La semaine passée, un article intéressant était publié (http://www.bbc.co.uk/news/…) sur sciences et magie. Cet article m’a fait penser à une réflexion que je m’étais faite lors de notre visite au MoMaths, cet hiver. Pour revenir sur l’histoire que j’avais raconté il y a quelques mois, sur la fin de la visite, les enfants avaient joué avec les pavages, à la Escher (les pièces étaient magnétiques, et s’assemblaient sur un grand tableau blanc)

Le soucis c’est qu’à aucun moment je n’ai pu voir d’explication du  pourquoi ça marche ? ou pour être plus explicite comment a été construit le singe pour que tout s’emboîte aussi bien. Car il y a un truc… La magie ça n’existe pas ! ce sont juste des maths (c’est un peu ce que racontent Persi Diaconis et Ron Graham dans Magical Mathematics, même si j’avoue ne pas l’avoir fini, faute de temps, et d’avoir laissé des chapitres en attente). Mon fils travaillant les rotations et les symétries, à l’école, j’ai voulu qu’on prenne le temps de revenir sur les pavages. Mais avant de me lancer avec lui, j’ai essayé de m’entraîner un peu tout seul (dimanche après midi, pendant le temps calme).

La difficulté (ou la magie) est qu’il y a des symétries dans tous les sens. Regardons un exemple simple (ou disons pas trop compliqué) avec des chinois (identifiés par les chapeaux dits chinois). En regardant rapidement, on note que le triangle ci-dessous est reproduit à l’infini, par un jeu de rotations. Il suffit donc d’avoir un tel triangle. Le soucis est que le découpage (parfaitement symétrique) n’est pas trivial (il est délicat de faire un personnage en faisant un découpage dans un triangle, même si c’est la méthode retenue dans l’activité mentionnée sur https://irem.univ-lille1.fr/…)

Le secret part de l’observation suivante: sur le graphique de gauche, en dessous, les trois points (qui sont des intersections des trois personnages, ou disons des trois couleurs) sont les sommets d’un triangle équilatéral. C’est là que la magie va opérer, car c’est cette figure (avec une autre, juxtaposée) que l’on va tenter de reproduire. En fait, un personnage (disons un petit chinois bleu) c’est deux triangles collés (on doit pouvoir parler de parallélogramme isocèle).

On ne le voit pas très bien, mais pourtant, au départ, on avait un parallélogramme isocèle (dont les contours sont tracés en noir) qui était  tout bleu. Bien entendu, on a découpé des parties et en les a envoyé ailleurs (par rotation autour d’un sommet). Le plus simple est de construire la figure, à la main. On part donc du parallélogramme suivant, tout bleu :

Oui, j’ai repris les fonctions de base utilisées l’autre jour pour expliquer R aux enfants,

source("http://freakonometrics.free.fr/RforKIDZ.R")

En fait, j’ai souhaité définir une fonction créant un polynôme à partir d’une liste de points (ou de sommets).

polyg=function(L,couleur="blanc",tour=couleur,ep=1,st=1,...){
  b=unlist(L)
  n=length(b)
  polygon(b[seq(1,n,by=2)],b[seq(2,n,by=2)],col=couleurc(couleur),border=couleurc(tour),lwd=ep,lty=st,...)}

La fonction pour faire une rotation d’une liste de points est ici

rotation=function(L,angle=90,centre=L[[1]]){
  b=unlist(L)
  n=length(b)
  X=cbind(b[seq(1,n,by=2)]-centre[1],b[seq(2,n,by=2)]-centre[2])
  Y=matrix(c(cos(angle/180*pi),sin(angle/180*pi),-sin(angle/180*pi),cos(angle/180*pi)),2,2)%*%t(X)
  Z=Y+centre
  L2=L
  for(i in 1:(n/2)){L2[[i]]=Z[,i]}
  return(L2)}

On a alors ici les quatre sommets

A=c(4,0)
B=c(4,10)
C=c(4+sqrt(3)*5,5)
D=c(4+sqrt(3)*5,15)

et on peut tracer le parallélogramme avec

L1=list(A,B,D,C)
polyg(L1,"bleu",tour="noir",ep=3)

On peut alors jouer à découper des parties, puis à les pivoter (on va faire des rotations, quoi). Par exemple, le prend le triangle en haut à droite, et je pivote de 240 degrés autour d’un des sommets du parallélogramme. C’est la figure ci-dessus à droite.  Le triangle, il est défini par le code suivant

E=c(10,10)
F=c(7,10+sqrt(3)) 
L1=list(B,E,F)
polyg(L1,tour="rouge",ep=3)

ce qui enlève la portion – en traçant un triangle blanc – et pour faire la rotation, j’utilise le code suivant

L2=rotation(L1,240)
polyg(L2,"bleu","rouge",ep=3)

(la seconde ligne permet de tracer le triangle bleu). Il va de soi qu’on peut découper des objets plus complexes que des triangles, voire non connexes. Par exemple, je peux découper la forme verte ci-dessous, puis la pivoter par rapport au sommet en haut à gauche, de 240 degrés.

G=c(10,2*sqrt(3)+10)
H=c(4+sqrt(3)*5,2*sqrt(3)+10)
F1=c(8,10+2/sqrt(3))
F2=c(8,10+4/sqrt(3))
L1=list(B,E,F1,F2,B,G,H,D,G)
polyg(L1,"vert",tour=NA)
L2=rotation(L1,240)
polygL(L2,"bleu",tour=NA)

(il n’est pas nécessaire de revenir au point B, mais peu importe). Ou la figure jaune, qui va pivoter autour du sommet en bas à droite, de 120 degrés.

F3=c(8,10-2/sqrt(3))
F4=c(8,10-4/sqrt(3))
G2=c(10,-2*sqrt(3)+10)
H2=c(4+sqrt(3)*5,-2*sqrt(3)+10)
L1=list(H,G,F2,F1,E,F3,F4,G2,H2,H)
polyg(L1,"jaune",tour=NA)
L2=rotation(L1,120,centre=C)
polygL(L2,"bleu",tour=NA)

Avec des ciseaux, ça sera plus simple, mais le but est aussi de voir que programmer, c’est facile. En gros, on a deux fonctions de base: une qui trace un polynôme et l’autre qui fait des rotations.

Si on fait les deux en même temps (à peu près), on enlève toute la partie en haut à droite, et on la répartie: une partie à gauche, et une partie en bas à droite.  On a alors une forme qui ressemble à un chinois. Non ? On peut aller creuser un peu sous les bras, pour améliorer les mains, mais on y est presque, me semble-t-il…

On peut continuer à améliorer, par exemple en enlevant des parties, puis en faisant des rotations par rapport à un des sommets initiaux. Comme le petit triangle jaune, qui va pivoter de 120 degrés par rapport au sommet en bas à droite. Puis le triangle vert par rapport au sommet en bas à gauche (on note qu’on pivote par rapport aux sommets du triangle équilatéral qu’on avait repéré, initialement)

S=c(8-.4,-2*sqrt(3)+10-.4)
L1=list(F4,G2,S,F4)
polyg(L1,"jaune")
L2=rotation(L1,120,centre=C)
polyg(L2,"bleu")

Bon, là on fait une pause, parce qu’on a, par morceaux, notre chinois ! On un paquet de lettre (voire un paquet de sommets qu’il va falloir nommer, suite à nos rotations). On les nomme avec un code qui ressemble à (oui, on aurait pu pu les nommer dès le départ, lors des rotations)

rE=rotation(list(E),240,centre=B)[[1]]
rF1=rotation(list(F1),240,centre=B)[[1]]
rH=rotation(list(H),240,centre=B)[[1]]

Une fois qu’on a identifié nos sommets, on a notre chinois,

chinois=list(B,rE,rF1,LG,S2,LF2,rH,A,r2H,r2G,r2S2,
        r2F2,r2F1,r2E,rF3,rF4,r2S,rG2,rH2,C,H2,G2,S,F4,F3,E,B)

Bon, ensuite, reste à paver, ce qui est est le plus simple. Par exemple, on peut faire des rotations,

r1chinois=rotation(chinois,120,centre=A)
polyg(r1chinois,couleur="jaune")

voire définir une translation,

translation=function(L,h){
b=unlist(L)
n=length(b)
X=cbind(b[seq(1,n,by=2)]+h[1],b[seq(2,n,by=2)]++h[2])
L2=L
for(i in 1:(n/2)){L2[[i]]=X[i,]}
return(L2)}

puis translater notre chinois,

r1chinois=rotation(chinois,120,centre=A)
polyg(r1chinois,couleur="jaune")
polyg(translation(r1chinois,15/sqrt(3),15),couleur="jaune")

Il manque l’autre, le vert. On peut vérifier qu’il se superpose parfaitement :

Bon, ben ça y est, on a constitué notre pavage. Reste à travailler un peu le code, essentiellement sur la forme, et on pourra jouer avec les enfants, à faire les lézards, des singes, et toutes sortes de pavages possibles, à la Escher. En notant qu’on peut utiliser d’autres formes de bases plus complexes, comme expliqué sur http://xavier.hubaut.info/…

Arthur Charpentier

Arthur Charpentier, professor in Montréal, in Actuarial Science. Former professor-assistant at ENSAE Paristech, associate professor at Ecole Polytechnique and assistant professor in Economics at Université de Rennes 1.  Graduated from ENSAE, Master in Mathematical Economics (Paris Dauphine), PhD in Mathematics (KU Leuven), and Fellow of the French Institute of Actuaries.

More Posts - Website - Twitter - LinkedIn - Google Plus

Synthétiser l’évolution socio-démographique des 36 000 communes françaises depuis 1968

Dans le cadre de ma thèse portant sur le vote pour le Front national en région PACA, je me suis posé…

Dans le cadre de ma thèse portant sur le vote pour le Front national en région PACA, je me suis posé la question de savoir si la trajectoire socio-démographique d’une commune influe sur le niveau du vote FN dans cette commune. En d’autres termes, la manière dont les effectifs des différentes catégories socio-professionnelles évolue au cours du temps a-t-elle un impact politique ? Spontanément, je tendrais à faire l’hypothèse que oui. On peut imaginer plusieurs mécanismes reliant les deux phénomènes : par exemple, que l’évolution locale objective de la structure sociale influe sur la perception subjective de l’évolution de la société par les habitants d’une commune. Ou encore, que le déclin numérique de la classe sociale à laquelle on appartient induit un sentiment de déclin généralisé. Il y aurait bien évidemment encore bien d’autres hypothèses possibles.

En réalité, j’avais déjà examiné cette question dans une communication que j’avais faite au congrès de l’AFSP, en 2009. J’utilisais la variable de l’évolution socio-démographique de la commune comme variable indépendante dans des modèles multi-niveaux ayant pour variable dépendante le vote en faveur du Front national. Mais, déjà lorsque j’avais rédigé ce texte, je n’étais pas très content de la manière dont j’avais procédé.

En effet, habitué à manier des variables quantitatives continues (l’habitude de travailler sur des données agrégées…), je cherchais à avoir ce type de variable. En partant de la composition de la population active par catégorie sociale (nomenclature CS en six positions) à tous les recensements de 1968 à 1999, j’avais estimé un modèle multiniveau de croissance pour chaque CS. Ce modèle est un modèle linéaire – c’est là mon premier souci : rien ne permet de penser a priori que les évolutions socio-démographiques, sur une durée de trente ans, sont linéaires. Un groupe social peut croître puis décroître, la croissance d’un autre peut être exponentielle plutôt qu’arithmétique. J’avais bien envisagé de faire une modélisation quadratique, mais je me sentais beaucoup moins à l’aise pour utiliser ces coefficients comme variables par la suite, car leur interprétation est moins directe.
Les coefficients issus de cette modélisation linéaire multiniveau (12 coefficients par commune tout de même) étaient ensuite passés à la moulinette d’une ACP, afin d’en dégager les dimensions les plus significatives (toujours le même problème d’ordonner et synthétiser des données trop abondantes pour être interprétées). La position de chaque commune sur les trois premières composantes issues de l’ACP étaient ensuite utilisée comme variable explicative dans le “gros” modèle multiniveau. Cette analyse donnait des résultats substantiels, mais demeurait pourtant problématique. Outre le problème de la modélisation linéaire déjà évoqué, les données sont fragiles : elles sont issues de l’exploitation complémentaire du recensement, c’est-à-dire d’un sondage au quart. Ce qui signifie que, dans les petites communes au moins, les données sont très bruitées. La procédure que j’ai utilisée ne supprime pas ce bruit. Ce n’est pas dramatique en soi, car s’il y a du bruit, il n’y a pas de biais, mais ça diminue la puissance explicative (ou prédictive, comme on voudra) de cette variable indépendante. De plus, c’est une procédure très analytique, qui étudie les effets distincts de plusieurs composantes de l’évolution socio-démographique des communes, mais sans permettre facilement de revenir à des cas typiques, des sortes d’idéal-types permettant d’appréhender quelques profils d’évolution. Plus je vais et plus je tends à préférer les procédures permettant de comparer les effets de quelques cas plutôt que donnant des coefficients abstraits – l’influence d’Andrew Gelman et Gary King, sûrement.

En revenant sur cette question durant la rédaction de ma thèse, je me suis dit qu’il serait sans doute plus simple, et plus intéressant substantiellement, de dégager quelques types de trajectoire socio-démographique des communes. Je n’avais pas d’outil précis en tête, alors j’ai un peu farfouillé, notamment du côté des analyses de séquence en histoire. Mais, pour ce que j’en ai compris – corrigez-moi si je me trompe, amis historiens ! -, ce type d’analyse ne s’applique qu’à des variables qualitatives, discrètes. Ca ne faisait donc pas mon affaire. J’ai aussi été voir du côté de la modélisation de classes latentes, mais je ne suis pas très à l’aise avec les équations structurelles, donc tant que je ne les comprendrai pas mieux, je ne les utiliserai pas.

Et puis je me suis dit qu’il suffisait de faire simple. J’ai donc décidé de calculer, sur chaque période intercensitaire, un taux de croissance pour chaque CS (sur la base des effectifs absolus). Ensuite, il suffit de faire tourner une procédure classificatoire sur ces variables. Facile, a priori. Sauf que mon premier réflexe a été de recourir à une classification ascendante hiérarchique (CAH), notamment en raison de sa proximité méthodologique avec l’analyse géométrique des données (le directeur de mon labo, Frédéric Lebaron, en est un des spécialistes, donc je suis tombé dedans quand j’étais petit). Sauf que… c’est une méthode relativement lourde d’un point de vue computationnel (O(n3), je crois), et ni mon ordinateur personnel, ni une instance Amazon avec 16 Go de RAM ne s’en sortis. J’ai donc changé mon fusil d’épaule, et j’ai essayé une K-means (vous connaissez une bonne traduction française pour cela ?). Mais, outre la difficulté classique (et facile à résoudre empiriquement) de savoir combien de classes il faut chercher, cette procédure ne convient pas en l’espèce car les effectifs des classes produites sont très dissemblables – l’algorithme est très sensible aux outliers, et comme les données sont fortement bruitées… En cherchant, j’ai découvert l’existence d’un autre algorithme, les K-médoïdes. L’idée est globalement la même que celle consistant à substituer la médiane à la moyenne comme mesure de centralité : c’est un algorithme plus robuste, moins sensible aux outliers. Exactement ce qu’il me fallait… Seul inconvénient : c’est plus gourmand en temps de calcul que les K-means (presque deux heures sur une instance AWS avec 16 Go de RAM, sur un tableau de 36000 lignes et 60 colonnes). Et puis, comme les K-means, ce n’est pas un algorithme déterministe, donc idéalement il faudrait l’estimer plusieurs fois, mais vu le temps de calcul requis, on s’en passera.

Une fois que j’ai dégagé mes classes, il n’y a plus qu’à les analyser. Pour cela, le plus simple est de les visualiser. On peut faire de l’ACP (là aussi, il va falloir tricher un peu, car l’ACP est aussi intense computationnellement ; un moyen est de faire une K-means dégageant, mettons, 1000 groupes, et d’ensuite faire l’ACP sur les centres de ces groupes – on perd de fait très peu d’information), mais en l’occurrence je n’ai pas trouvé cela très parlant. Je préférais voir, vraiment, les différentes trajectoires. Après avoir tâtonné un peu (oui, ça a beaucoup tâtonné, cette histoire…), j’ai décidé de tracer une courbe par CS par groupe. Avec R et ggplot2, ce n’est pas trop compliqué de faire ça à peu près proprement. Et voilà le résultat (cliquez sur l’image pour la télécharger en pdf) :

Maintenant, reste à interpréter… mais c’est une autre histoire !

Les données de l’INSEE utilisées pour l’analyse sont , et mes données et mon code complets pour dupliquer l’analyse sont sur mon github (poke François !).

Si vous avez en tête d’autres manières de mener ce genre d’analyse, dites-le moi en commentaire !

EDIT : j’ai oublié de préciser deux choses, nécessaires à la compréhension du graphique :

  • Le jeu de données de l’INSEE que j’ai utilisé ne concerne que les actifs de 25 à 54 ans (en raison de changements méthodologiques au fil du temps), et distingue entre chômeurs et actifs occupés. La tranche d’âge concernée explique le faible niveau de chômage.
  • J’ai ajouté aux graphiques, outre la moyenne, les 1er et 3e quartiles, afin de visualiser la dispersion interne à chacun des groupes. Comme la moyenne a été pondérée par la population active des communes, elle peut parfois ne pas être comprise entre les 1er et 3e quartiles – ou pourquoi la moyenne n’est pas toujours un bon indicateur de centralité…