Treemap

représentation graphique de données hiérarchique

Une carte proportionnelle (abrégée C.P.), carte à cases ou en anglais treemap est une représentation de données hiérarchiques dans un espace limité. Elle est par exemple utilisée pour représenter l'occupation du disque dur sur un ordinateur. De nos jours, elle est aussi utilisée pour visualiser le budget d'un État.

Visualisation de la structure d'un dossier (montrant la dimension de chaque dossier à l'aide d'une carte proportionnelle en TreeSize.
Visualisation en CP des exportations françaises (source : Observatoire de la complexité économique du MIT).
Représentation en CP du nombre de bulletins républicains et démocrates par État lors des élections présidentielles américaines de 2012.

Historique

modifier

Au début des années 1990, Ben Shneiderman, professeur à l'université du Maryland, remarque que le disque dur du serveur commun de son laboratoire est souvent saturé. Il cherche alors une visualisation des données permettant de repérer dans quel dossier ou sous-dossier se trouvent les fichiers les plus volumineux. Il propose alors de représenter l'arborescence des fichiers (tree) dans un plan (map) et publie un premier algorithme permettant d'obtenir cette visualisation en 1992[1],[2]. Il développe l'application TreeViz permettant de visualiser l'occupation de son disque dur sur MacIntosh[2],[3].

L'idée sous-jacente consiste à répartir l'espace de représentation (l'écran ou le papier) entre les différentes entités de l'arborescence et d'associer à chacune d'entre elles un rectangle dont la taille et la couleur réflète des attributs de l'entité correspondante. Cette technique de visualisation d'information permet à l'utilisateur final de reconnaître facilement des motifs graphiques pouvant traduire des relations complexes au sein des données, relations difficiles à déceler autrement.

Algorithme

modifier

Pour créer une carte proportionnelle, il faut définir un algorithme d’assemblage pour diviser un rectangle en sous-rectangles avec des surfaces définies. Dans l’idéal, un algorithme de carte proportionnelle devrait créer des rectangles de proportions similaires, tout en préservant la signification de l’ordre de données représentées, et toute modification devrait refléter les modifications de ces données.

Malheureusement ces propriétés s'opposent : tandis que les proportions sont optimisées, l’ordre de placement devient moins prévisible. Tandis que l’ordre est préservé, les proportions entre les rectangles sont dégradées.

À ce jour six principaux algorithmes de carte proportionnelle rectangulaire ont été développés :

Algorithme Treemap[4]
Algorithme Conservation de l’ordre Respect des proportions Stabilité
Arbre Binaire (BinaryTree) Partiel Important Stable
Carte proportionnelle mixtes (Mixed Treemaps) Conservé Faible Stable
Ordonnancé (Ordered) Partiel Moyen Moyenne
Par eminçage (Slice And Dice) Conservé Très Important Stable
Mise au carré (Squarified) Non conservé Faible Moyen
En Bandes (Strip) Conservé Moyen Moyen

De plus, plusieurs algorithmes ont été proposés pour utiliser des régions non rectangulaires :

  • Carte proportionnelle de Jigsaw - basé sur le remplissage de courbes géométriques
  • GosperMaps - basé sur les courbes géometriques de Gosper, [conservation de l’ordre, très important respect des proportions, stable]
  • Carte proportionnelle de Voronoi - basé sur le calcul des diagrammes de Voronoi
  • Carte proportionnelle convexes - utilisation de polygones convexes a la place de rectangles
  • Carte proportionnelle circulaires - utilisation de cercles a la place de rectangles

Carte proportionnelle de Voronoi

modifier

La CP de Voronoi est une variante de la CP proposée par Michael Balzer et Oliver Deussen en 2005, dans laquelle les éléments sont des polygones, comme dans un diagramme de Voronoi, plutôt que des rectangles[5]. Michael Balzer l'a notamment utilisée pour visualiser les différentes parts de l'inflation américaine et allemande[6],[7].

Bibliographie

modifier
  • (en) Brian Johnson et Ben Shneiderman, « Treemaps: a space-filling approach to the visualization of hierarchical information structures », Proceedings of the 2nd International IEEE Visualization Conference (San Diego, Oct. 1991),‎ , p. 284-291 (lire en ligne)
  • (en) Ben Schneiderman, « Tree visualization with tree-maps: 2-d space-filling approach », ACM Transactions on Graphics, vol. 11, no 1,‎ , p. 92-99 (DOI 10.1145/102377.115768)
  • (en) Michael Balzer et Oliver Deussen, « Voronoi treemaps », IEEE Symposium on Information Visualization (InfoVis), IEEE Press,‎ (lire en ligne)
  • (en) David Auber, Charles Huet, Andrew Lambert, Benjamin Renoust, Arnaud Sallaberry et Agnes Saulnier, IEEE Transactions on Visualization and Computer Graphics, Gospermap: Using a gosper curve for laying out hierarchical data

Notes et références

modifier
  1. Schneiderman 1992
  2. a et b (en) Ben Shneiderman et Catherine Plaisant, « Treemaps for space-constrained visualization of hierarchies », sur cs.umd.edu/hcil/, (consulté le )
  3. « Treeviz », sur www.cs.umd.edu/hcil (consulté le )
  4. (en) Ben Shneiderman et Catherine Plaisant, « Treemaps for space-constrained visualization of hierarchies ~ Including the History of Treemap Research at the University of Maryland », (consulté le )
  5. (en) Isabel Meirelles, Design for Information, Rockport Publishers, , p. 45
  6. (en) Amanda Cox et Michael Balzer, « All of Inflation's Little Parts », New York Times,‎ (lire en ligne)
  7. Michael Balzer, « Preis-Keleidoskop », sur Statistisches Bundesamt (consulté le )

Liens externes

modifier

Sur les autres projets Wikimedia :

  • (en) Collection de représentation de données hiérarchiques