Le cube ordonnable

Une tranche du cube, traitée à la manière de Bertin. Chaque valeur devient un carré, noirci selon son écart à la moyenne de sa colonne ; puis on permute lignes et colonnes jusqu'à ce que les noirs se rassemblent. Cliquez sur deux étiquettes pour les échanger, ou laissez la machine ranger. Le critère est l'énergie de liaison de McCormick : la somme des produits de cases voisines, qui augmente quand les valeurs semblables se regroupent.

Ce que Bertin avait compris. Que l'ordre des lignes d'un tableau n'est pas une donnée mais une variable libre, et qu'en la choisissant bien on rend visible une structure que le calcul mettrait des pages à établir. Sa matrice ordonnable était un objet physique, à lamelles coulissantes, manipulé à la main. Le rangement par moyennes réciproques automatise ce geste et converge vers le premier axe d'une analyse des correspondances : la main et l'algèbre tombent d'accord.

Voici le cube entier, déplié en autant de tranches qu'il a d'instants. La contrainte nouvelle saute aux yeux : permuter une ligne la déplace dans toutes les tranches à la fois. On ne cherche donc pas une bonne mise en ordre par tranche, mais un ordre unique par mode — un pour les individus, un pour les variables, un pour les instants — qui rende toutes les tranches lisibles ensemble. Et l'ordre des tranches elles-mêmes est lui aussi à trouver.

mode 1 — individusmode 2 — variablesmode 3 — instants

Un espace de recherche qui explose. Ranger un tableau de 14 lignes et 10 colonnes, c'est déjà choisir parmi 14! × 10! configurations. Pour le cube, il faut multiplier encore par le nombre d'ordres des tranches. Aucune énumération n'est envisageable, et c'est bien pourquoi Bertin manipulait des lamelles plutôt que de calculer : il lui fallait un procédé qui converge, pas un procédé qui essaie tout.

Le critère se généralise sans effort. Pour une matrice, McCormick additionne les produits de cases voisines horizontalement et verticalement. Pour un cube, on ajoute simplement la troisième direction : chaque case est multipliée par sa voisine en ligne, sa voisine en colonne et sa voisine dans la tranche suivante. Maximiser cette somme, c'est demander que les valeurs proches soient contiguës dans les trois sens à la fois. L'animation ci-dessous améliore l'ordre par échanges successifs, en n'acceptant que ceux qui font monter l'énergie.

La limite de la recherche par échanges. Elle monte toujours, donc elle s'arrête toujours — mais sur un maximum local, dont rien ne dit qu'il est le bon. Le taux d'acceptation qui s'effondre vers zéro signale seulement qu'aucun échange isolé n'améliore plus rien, ce qui n'exclut pas qu'une permutation plus profonde le ferait. C'est le défaut de toute méthode gloutonne, et la raison pour laquelle on lui préfère un procédé qui exploite la structure des données plutôt que de tâtonner.

Voici le procédé qui converge. Donnez-vous des scores provisoires aux variables et aux instants ; calculez pour chaque individu la moyenne pondérée de ses valeurs ; normalisez ; recommencez en tournant les rôles. Chaque mode reçoit ainsi un score, et l'on range chaque mode par score croissant. C'est exactement l'algorithme des moindres carrés alternés qui cherche la meilleure approximation de rang un du cube : le geste de Bertin est, littéralement, une itération de la puissance appliquée à un tenseur.

Pourquoi les moyennes réciproques rangent bien. Parce qu'elles donnent à chaque ligne la position moyenne des colonnes où elle est forte, et à chaque colonne la position moyenne des lignes où elle est forte : à l'équilibre, chacun est au barycentre de ceux qui lui ressemblent. En deux dimensions, cet équilibre est le premier axe de l'analyse des correspondances, et le rangement qui en découle est optimal en un sens précis. En trois dimensions, l'équilibre existe toujours et se calcule aussi vite — mais l'optimalité, elle, se perd, comme la planche suivante le montre.

L'élément décisif, et la seule question qui compte en pratique. Puisqu'on sait ranger un tableau, pourquoi ne pas moyenner les tranches et ranger la matrice obtenue ? L'épreuve ci-dessous compare les deux, sur des cubes tirés au sort dont l'ordre vrai est connu, et mesure le recouvrement par le tau de Kendall. Le résultat dépend entièrement de la structure : quand l'effet est constant dans le temps, la moyenne suffit ; quand il s'inverse, la moyenne l'annule et seul le cube le retrouve.

La règle qui se dégage. Moyenner les tranches revient à supposer que le troisième mode ne fait que répéter la même structure avec plus ou moins d'intensité. Dès que ce mode module la structure — l'inverse, la déplace, l'échange entre groupes — la moyenne détruit précisément ce qu'on cherchait, et rend un tableau sans signal. C'est la situation des séries répétées dans le temps, des mesures avant et après traitement, des comparaisons entre régions : partout où le troisième axe est susceptible de retourner le phénomène plutôt que de l'amplifier, il faut traiter le cube comme un cube.