stringtranslate.com

Mapeo de árboles

Treemap de las exportaciones de Singapur por categoría de producto, 2012. Los Treemaps de Exportaciones de Productos son una de las aplicaciones más recientes de este tipo de visualizaciones, desarrolladas por el Observatorio de Complejidad Económica de Harvard-MIT .

En informática y visualización de información , el mapeo de árboles es un método para mostrar datos jerárquicos utilizando figuras anidadas , generalmente rectángulos.

Los mapas de árbol muestran datos jerárquicos ( estructurados en árbol ) como un conjunto de rectángulos anidados. A cada rama del árbol se le asigna un rectángulo, que luego se recubre con rectángulos más pequeños que representan subramas. El rectángulo de un nodo hoja tiene un área proporcional a una dimensión específica de los datos . [1] A menudo, los nodos de las hojas están coloreados para mostrar una dimensión separada de los datos.

Cuando las dimensiones de color y tamaño se correlacionan de alguna manera con la estructura del árbol, a menudo se pueden ver fácilmente patrones que serían difíciles de detectar de otras maneras, como por ejemplo si un determinado color es particularmente relevante. Una segunda ventaja de los mapas de árboles es que, por construcción, hacen un uso eficiente del espacio. Como resultado, pueden mostrar de forma legible miles de elementos en la pantalla simultáneamente.

Algoritmos de mosaico

Para crear un mapa de árbol, se debe definir un algoritmo de ordenamiento en mosaico , es decir, una forma de dividir una región en subregiones de áreas específicas. Idealmente, un algoritmo de mapa de árbol crearía regiones que satisfagan los siguientes criterios:

  1. Una relación de aspecto pequeña , idealmente cercana a uno. Las regiones con una relación de aspecto pequeña (es decir, objetos gruesos ) son más fáciles de percibir. [2]
  2. Preservar cierto sentido del orden en los datos de entrada (ordenados).
  3. Cambie para reflejar cambios en los datos subyacentes (alta estabilidad).

Estas propiedades tienen una relación inversa. A medida que se optimiza la relación de aspecto, el orden de colocación se vuelve menos predecible. A medida que el orden se vuelve más estable, la relación de aspecto se degrada. [ ejemplo necesario ]

Mapas de árboles rectangulares

Hasta la fecha, se han desarrollado quince algoritmos primarios de mapas de árboles rectangulares:

Mapas de árboles convexos

Los treemaps rectangulares tienen la desventaja de que su relación de aspecto puede ser arbitrariamente alta en el peor de los casos. Como ejemplo simple, si la raíz del árbol tiene solo dos hijos, uno con peso y otro con peso , entonces la relación de aspecto del hijo más pequeño será , que puede ser arbitrariamente alta. Para hacer frente a este problema, se han propuesto varios algoritmos que utilizan regiones que son polígonos convexos generales , no necesariamente rectangulares.

Los mapas de árbol convexos se desarrollaron en varios pasos, cada paso mejoró el límite superior de la relación de aspecto. Los límites se dan en función de - el número total de nodos en el árbol y - la profundidad total del árbol.

  1. Onak y Sidiropoulos [15] demostraron un límite superior de .
  2. De-Berg, Onak y Sidiropoulos [16] mejoran el límite superior y demuestran un límite inferior de .
  3. De-Berg, Speckmann y van-der-Weele [17] mejoran el límite superior a , igualando el límite inferior teórico. (Para el caso especial donde la profundidad es 1, presentan un algoritmo que utiliza sólo cuatro clases de polígonos de 45 grados (rectángulos, triángulos rectángulos, trapecios rectángulos y pentágonos de 45 grados), y garantiza una relación de aspecto de como máximo 34 horas al día, 7 días a la semana.)

Los dos últimos algoritmos funcionan en dos pasos (muy simplificados para mayor claridad):

  1. El árbol original se convierte en un árbol binario: cada nodo con más de dos hijos se reemplaza por un subárbol en el que cada nodo tiene exactamente dos hijos.
  2. Cada región que representa un nodo (comenzando desde la raíz) se divide en dos, usando una línea que mantiene los ángulos entre los bordes lo más grandes posible. Es posible demostrar que, si todas las aristas de un polígono convexo están separadas por un ángulo de al menos , entonces su relación de aspecto es . Es posible asegurar que, en un árbol de profundidad , el ángulo se divida por un factor de como máximo , de ahí la garantía de relación de aspecto.

Mapas de árboles ortoconvexos

En los mapas de árboles convexos, la relación de aspecto no puede ser constante: crece con la profundidad del árbol. Para lograr una relación de aspecto constante, se pueden utilizar mapas de árbol ortoconvexos [17] . Allí, todas las regiones son polígonos rectilíneos ortoconvexos con una relación de aspecto como máximo de 64; y las hojas son rectángulos con una relación de aspecto de como máximo 8, o formas de L o de S con una relación de aspecto de como máximo 32.

Para el caso especial donde la profundidad es 1, presentan un algoritmo que usa solo rectángulos y formas de L, y la relación de aspecto es como máximo ; los nodos internos utilizan sólo rectángulos con una relación de aspecto como máximo .

Otros mapas de árboles

Mapas de árboles de Voronoi
[18] basado en cálculos del diagrama de Voronoi . El algoritmo es iterativo y no proporciona ningún límite superior a la relación de aspecto.
Mapas de árboles de rompecabezas [19]
basado en la geometría de curvas que llenan el espacio. Suponen que los pesos son números enteros y que su suma es un número cuadrado. Las regiones del mapa son polígonos rectilíneos y muy no ortoconvexos. Se garantiza que su relación de aspecto será como máximo de 4.
GosperMapas
[20] basado en la geometría de las curvas de Gosper . Es ordenado y estable, pero tiene una relación de aspecto muy alta.

Historia

Uso del espacio en el disco duro visualizado en TreeSize, software lanzado por primera vez en 1996

Las visualizaciones basadas en áreas existen desde hace décadas. Por ejemplo, los diagramas de mosaico (también conocidos como diagramas de Marimekko) utilizan mosaicos rectangulares para mostrar distribuciones conjuntas (es decir, lo más común es que sean esencialmente diagramas de columnas apiladas donde las columnas tienen diferentes anchos). Sin embargo, la principal característica distintiva de un mapa de árbol es la construcción recursiva que permite extenderlo a datos jerárquicos con cualquier número de niveles. Esta idea fue inventada por el profesor Ben Shneiderman en el Laboratorio de Interacción Humano-Computadora de la Universidad de Maryland a principios de la década de 1990. [21] [22] Shneiderman y sus colaboradores luego profundizaron la idea introduciendo una variedad de técnicas interactivas para filtrar y ajustar mapas de árboles.

Todos estos primeros mapas de árboles utilizaban el sencillo algoritmo de ordenamiento en mosaico de "cortar y dividir". A pesar de muchas propiedades deseables (es estable, conserva el orden y es fácil de implementar), el método de cortar y cortar a menudo produce mosaicos con muchos rectángulos largos y delgados. En 1994, Mountaz Hascoet y Michel Beaudouin-Lafon inventaron un algoritmo de "cuadrificación", popularizado más tarde por Jarke van Wijk , que creaba mosaicos cuyos rectángulos estaban más cerca del cuadrado. En 1999, Martin Wattenberg utilizó una variación del algoritmo de "cuarificación" al que llamó "pivote y corte" para crear el primer mapa de árbol basado en la Web, el SmartMoney Map of the Market, que mostraba datos sobre cientos de empresas en el mercado de valores de Estados Unidos. Tras su lanzamiento, los treemaps gozaron de un gran interés, especialmente en contextos financieros. [ cita necesaria ]

Una tercera ola de innovación en mapas de árbol se produjo alrededor de 2004, después de que Marcos Weskamp creara Newsmap, un mapa de árbol que mostraba titulares de noticias. Este ejemplo de un mapa de árbol no analítico inspiró a muchos imitadores e introdujo los mapas de árbol a una audiencia nueva y amplia. [ cita necesaria ] En los últimos años, los mapas de árboles se han abierto camino en los principales medios de comunicación, incluido el New York Times. [23] [24] El Treemap Art Project [25] produjo 12 imágenes enmarcadas para las Academias Nacionales (Estados Unidos) , mostradas en la exposición Every AlgoRiThm has ART in It [26] en Washington, DC y otro conjunto para la colección del Museo. de Arte Moderno de Nueva York.

Ver también

Referencias

  1. ^ Li, Rita Yi Man; Chau, ala Kwong; Zeng, Frankie Fanjie (2019). “Ranking de Riesgos para Obras Nuevas y Existentes”. Sostenibilidad . 11 (10): 2863. doi : 10.3390/su11102863 .
  2. ^ Kong, norte; Heer, J; Agrawala, M (2010). "Pautas de percepción para la creación de mapas de árboles rectangulares". Transacciones IEEE sobre visualización y gráficos por computadora . 16 (6): 990–8. CiteSeerX 10.1.1.688.4140 . doi :10.1109/TVCG.2010.186. PMID  20975136. S2CID  11597084. 
  3. ^ Vernier, E.; Sondag, M.; Comba, J.; Speckmann, B.; Telea, A.; Verbeek, K. (2020). "Comparación cuantitativa de mapas de árboles dependientes del tiempo". Foro de gráficos por computadora . 39 (3): 393–404. arXiv : 1906.06014 . doi :10.1111/cgf.13989. S2CID  189898065.
  4. ^ Shneiderman, Ben (2001). "Diseños de mapas de árbol ordenados" (PDF) . Infovis : 73.
  5. ^ Benjamín, Bederson; Shneiderman, Ben; Wattenberg, Martín (2002). "Mapas de árbol ordenados y cuánticos: uso eficaz del espacio 2D para mostrar jerarquías" (PDF) . Transacciones ACM sobre gráficos . 21 (4): 833–854. CiteSeerX 10.1.1.145.2634 . doi :10.1145/571647.571649. S2CID  7253456. 
  6. ^ abc Shneiderman, Ben; Wattenberg, Martín (2001). "Diseños de mapas de árbol ordenados". Simposio IEEE sobre visualización de información : 73–78.
  7. ^ Engdahl, Björn. "Mapas de árbol ordenados y cuánticos: uso eficaz del espacio 2D para mostrar jerarquías" .
  8. ^ Tu, Y.; Shen, H. (2007). "Visualización de cambios de datos jerárquicos mediante mapas de árbol" (PDF) . Transacciones IEEE sobre visualización y gráficos por computadora . 13 (6): 1286-1293. doi :10.1109/TVCG.2007.70529. PMID  17968076. S2CID 14206074 . Archivado (PDF) desde el original el 8 de agosto de 2022. 
  9. ^ ab Tak, S.; Cockburn, A. (2013). "Estabilidad espacial mejorada con mapas de árboles de Hilbert y Moore" (PDF) . Transacciones IEEE sobre visualización y gráficos por computadora . 19 (1): 141–148. doi :10.1109/TVCG.2012.108. PMID  22508907. S2CID  6099935.
  10. ^ Bruls, Mark; Huizing, Kees; van Wijk, Jarke J. (2000). "Mapas de árboles cuadriculados". En de Leeuw, W.; van Liere, R. (eds.). Visualización de datos 2000: Proc. Simposio conjunto de Eurographics e IEEE TCVG. sobre visualización (PDF) . Springer-Verlag. págs. 33–42..
  11. ^ Roël Vliegen; Erik-Jan van der Linden; Jarke J. van Wijk . "Visualización de datos comerciales con mapas de árbol generalizados" (PDF) . Archivado desde el original (PDF) el 24 de julio de 2011 . Consultado el 24 de febrero de 2010 .
  12. ^ Nagamochi, H.; Abe, Y.; Wattenberg, Martín (2007). "Un algoritmo de aproximación para diseccionar un rectángulo en rectángulos con áreas específicas". Matemática Aplicada Discreta . 155 (4): 523–537. doi : 10.1016/j.dam.2006.08.005 .
  13. ^ Vernier, E.; Comba, J.; Telea, A. (2018). "Comparación cuantitativa de mapas de árboles dinámicos para la visualización de la evolución del software". Conferencia sobre visualización de software : 99–106.
  14. ^ Sondag, M.; Speckmann, B.; Verbeek, K. (2018). "Mapas de árboles estables mediante movimientos locales". Transacciones IEEE sobre visualización y gráficos por computadora . 24 (1): 729–738. doi :10.1109/TVCG.2017.2745140. PMID  28866573. S2CID  27739774.
  15. ^ Krzysztof Onak; Anastasios Sidiropoulos. «Particiones Circulares con Aplicaciones a Visualización e Incrustaciones» . Consultado el 26 de junio de 2011 .
  16. ^ Marcos de Berg; Onak, Krzysztof; Sidiropoulos, Anastasios (2013). "Particiones poligonales gruesas con aplicaciones a visualización e incrustaciones". Revista de geometría computacional . 4 (1): 212–239. arXiv : 1009.1866 .
  17. ^ ab De Berg, Mark; Speckmann, Bettina ; Van Der Weele, Vicente (2014). "Mapas de árbol con relación de aspecto acotada". Geometría Computacional . 47 (6): 683. arXiv : 1012.1749 . doi : 10.1016/j.comgeo.2013.12.008 . S2CID  12973376.. Versión de la conferencia: Treemaps convexos con relación de aspecto acotada (PDF) . EuroCG. 2011.
  18. ^ Balzer, Michael; Deussen, Oliver (2005). "Mapas de árboles de Voronoi". En Stasko, John T.; Ward, Matthew O. (eds.). Simposio IEEE sobre visualización de información (InfoVis 2005), 23-25 ​​de octubre de 2005, Minneapolis, MN, EE. UU. (PDF) . Sociedad de Computación IEEE. pag. 7..
  19. ^ Wattenberg, Martín (2005). "Una nota sobre visualizaciones que llenan el espacio y curvas que llenan el espacio". En Stasko, John T.; Ward, Matthew O. (eds.). Simposio IEEE sobre visualización de información (InfoVis 2005), 23-25 ​​de octubre de 2005, Minneapolis, MN, EE. UU. (PDF) . Sociedad de Computación IEEE. pag. 24..
  20. ^ Auber, David; Huet, Carlos; Lamberto, Antoine; Renoust, Benjamín; Sallaberry, Arnaud; Saulnier, Agnès (2013). "Mapa de Gosper: uso de una curva de Gosper para diseñar datos jerárquicos". Transacciones IEEE sobre visualización y gráficos por computadora . 19 (11): 1820–1832. doi :10.1109/TVCG.2013.91. PMID  24029903. S2CID  15050386..
  21. ^ Shneiderman, Ben (1992). "Visualización de árboles con mapas de árboles: enfoque de llenado de espacio en 2D". Transacciones ACM sobre gráficos . 11 : 92–99. doi :10.1145/102377.115768. hdl : 1903/367 . S2CID  1369287.
  22. ^ Ben Shneiderman ; Catherine Plaisant (25 de junio de 2009). "Treemaps para la visualización de jerarquías con limitaciones de espacio ~ Incluyendo la historia de la investigación de Treemap en la Universidad de Maryland" . Consultado el 23 de febrero de 2010 .
  23. ^ Cox, Amanda; Fairfield, Hannah (25 de febrero de 2007). "La salud del mercado de automóviles, furgonetas, SUV y camiones". Los New York Times . Consultado el 12 de marzo de 2010 .
  24. ^ Carter, Shan; Cox, Amanda (14 de febrero de 2011). "Propuesta de presupuesto de Obama para 2012: cómo se gastan 3,7 billones de dólares". Los New York Times . Consultado el 15 de febrero de 2011 .
  25. ^ "Arte de mapas de árboles". Archivado desde el original el 5 de diciembre de 2023.
  26. ^ "Cada AlgoRiThm contiene ARTE: Treemap Art Project". CPNAS . Archivado desde el original el 8 de octubre de 2023.

enlaces externos

Wikimedia Commons tiene medios relacionados con Treemaps .