En la visualización de información y la computació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 da un rectángulo, que luego se coloca en mosaico con rectángulos más pequeños que representan subramas. El rectángulo de un nodo de hoja tiene un área proporcional a una dimensión específica de los datos . [1] A menudo, los nodos de las hojas se colorean para mostrar una dimensión separada de los datos.
Cuando las dimensiones de color y tamaño están correlacionadas 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 si un determinado color es particularmente relevante. Una segunda ventaja de los treemaps es que, por construcción, hacen un uso eficiente del espacio. Como resultado, pueden mostrar de forma legible miles de elementos en la pantalla de forma simultánea.
Algoritmos de mosaico
Para crear un mapa de árbol, se debe definir un algoritmo de ordenamiento en teselas , 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:
- 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]
- Conserve cierto sentido del orden en los datos de entrada.
- Cambie para reflejar los cambios en los datos subyacentes.
Desafortunadamente, estas propiedades tienen una relación inversa. A medida que se optimiza la relación de aspecto, el orden de ubicació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 seis algoritmos de mapas de árbol rectangulares primarios:
Algoritmo | Pedido | Relaciones de aspecto | Estabilidad |
---|---|---|---|
Árbol binario | parcialmente ordenado | elevado | estable |
Mapas de árbol mixtos [4] | desordenado | más bajo | estable |
Ordenado y cuántico [5] | parcialmente ordenado | medio | estabilidad media |
Cortar y cortar [6] | ordenado | muy alto | estable |
Cuadrado [7] | desordenado [ se necesita más explicación ] | más bajo | estabilidad media |
Tira [8] | ordenado | medio | estabilidad media |
Mapas de árboles convexos
Los mapas de árbol 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 uno con peso , entonces la relación de aspecto del niño más pequeño será , que puede ser arbitrariamente alto. 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.
- Onak y Sidiropoulos [9] demostraron un límite superior de.
- De-Berg y Onak y Sidiropoulos [10] mejoran el límite superior ay probar un límite inferior de .
- De-Berg y Speckmann y van-der-Weele [11] mejoran el límite superior a, coincidiendo con el límite inferior teórico. (Para el caso especial donde la profundidad es 1, presentan un algoritmo que usa solo cuatro clases de polígonos de 45 grados (rectángulos, triángulos rectángulos, trapezoides rectángulos y pentágonos de 45 grados), y garantiza una relación de aspecto de como máximo 34/7.)
Los dos últimos algoritmos operan en dos pasos (muy simplificados para mayor claridad):
- 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.
- 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 probar que, si todos los bordes de un polígono convexo están separados 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 divide 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 Orthoconvex [11] . Allí, todas las regiones son orthoconvex polígonos rectilíneas con relación de aspecto en la mayoría de 64; y las hojas son rectángulos con una relación de aspecto como máximo de 8, o en forma de L o en forma de S con una relación de aspecto como máximo de 32.
Para el caso especial donde la profundidad es 1, presentan un algoritmo que usa solo rectángulos y formas en L, y la relación de aspecto es como máximo ; los nodos internos usan solo rectángulos con una relación de aspecto como máximo.
Otros mapas de árboles
- Mapas de árboles de Voronoi
- [12] basado en cálculos del diagrama de Voronoi . El algoritmo es iterativo y no proporciona ningún límite superior en la relación de aspecto.
- Jigsaw Treemaps [13]
- basado en la geometría de las curvas que llenan el espacio. Asumen 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 es de 4 como máximo.
- GosperMaps
- [14] basado en la geometría de las curvas de Gosper . Está ordenado y estable, pero tiene una relación de aspecto muy alta.
Historia
Las visualizaciones basadas en áreas han existido durante décadas. Por ejemplo, las parcelas de mosaico (también conocidas como diagramas de Marimekko) usan mosaicos rectangulares para mostrar distribuciones de juntas (es decir, más comúnmente son esencialmente parcelas 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. [15] [3] Shneiderman y sus colaboradores luego profundizaron la idea al introducir una variedad de técnicas interactivas para filtrar y ajustar mapas de árbol.
Todos estos primeros mapas de árbol usaban el algoritmo de ordenamiento en teselas "cortar y cortar". 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 "cuadratura", más tarde popularizado 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 "cuadratura" que llamó "pivote y corte" para crear el primer mapa de árbol basado en la web, el Mapa del mercado SmartMoney, que mostraba datos sobre cientos de empresas en el mercado de valores estadounidense. Después de su lanzamiento, treemaps disfrutó de un gran interés, especialmente en contextos financieros. [ cita requerida ]
Una tercera ola de innovación treemap llegó alrededor de 2004, después de Marcos Weskamp creó el Newsmap , un mapa de árbol que muestra los 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 requerida ] En los últimos años, los mapas de árboles se han abierto camino en los medios de comunicación principales, incluido el uso por parte del New York Times. [16] [17] El Proyecto de Arte Treemap produjo 12 imágenes enmarcadas para las Academias Nacionales (Estados Unidos) , se muestra la exhibición Every AlgoRiThm has ART in It en Washington, DC y otro conjunto para la colección del Museo de Arte Moderno de Nueva York .
Ver también
- Analizador de espacio en disco
- Visualización de información
- Lista de países por complejidad económica , que incluye una lista de Treemaps de exportación de productos.
- Gráfico de Marimekko , un concepto similar con un nivel de jerarquía explícita.
Referencias
- ^ Li, Rita Yi Man; Chau, Kwong Wing; Zeng, Frankie Fanjie (2019). "Ranking de Riesgos de Obras Existentes y Nuevas" . Sustentabilidad . 11 (10): 2863. doi : 10.3390 / su11102863 .
- ^ Kong, N; Heer, J; Agrawala, M (2010). "Pautas de percepción para la creación de mapas de árbol 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 .
- ^ a b Ben Shneiderman ; Catherine Plaisant (25 de junio de 2009). "Treemaps para visualización de jerarquías con limitaciones de espacio ~ incluida la historia de la investigación de Treemap en la Universidad de Maryland" . Consultado el 23 de febrero de 2010 .
- ^ Roel 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 .
- ^ Bederson, Benjamin B .; Shneiderman, Ben; Wattenberg, Martin (2002). "Treemaps ordenados y cuánticos: haciendo un uso efectivo del espacio 2D para mostrar jerarquías". Transacciones ACM en gráficos . 21 (4): 833. CiteSeerX 10.1.1.145.2634 . doi : 10.1145 / 571647.571649 . S2CID 7253456 .
- ^ Shneiderman, Ben (2001). "Diseños ordenados de mapas de árbol" (PDF) . Infovis : 73.
- ^ Bruls, Mark; Huizing, Kees; van Wijk, Jarke J. (2000). "Treemaps cuadriculados". En de Leeuw, W .; van Liere, R. (eds.). Visualización de datos 2000: Proc. Conjunto Eurographics y IEEE TCVG Symp. sobre visualización (PDF) . Springer-Verlag. págs. 33–42 {{citas inconsistentes}}CS1 maint: posdata ( enlace ).
- ^ Benjamin, Bederson; Shneiderman, Ben; Wattenberg, Martin (2002). "Treemaps ordenados y cuánticos: hacer un uso efectivo del espacio 2D para mostrar jerarquías" (PDF) . Transacciones ACM en gráficos . 21 (4): 833–854. CiteSeerX 10.1.1.145.2634 . doi : 10.1145 / 571647.571649 . S2CID 7253456 .
- ^ Krzysztof Onak; Anastasios Sidiropoulos. "Particiones circulares con aplicaciones para visualización e incrustaciones" . Consultado el 26 de junio de 2011 .
- ^ Mark de Berg; Onak, Krzysztof; Sidiropoulos, Anastasios (2010). "Particiones poligonales gordas con aplicaciones para visualización e incrustaciones". arXiv : 1009,1866 [ cs.CG ].
- ^ a b De Berg, Mark; Speckmann, Bettina ; Van Der Weele, Vincent (2014). "Treemaps con relación de aspecto delimitada". Geometría computacional . 47 (6): 683. arXiv : 1012.1749 . doi : 10.1016 / j.comgeo.2013.12.008 . S2CID 12973376 .. Versión conferencia: Treemaps convexos con relación de aspecto limitada (PDF) . EuroCG. 2011.
- ^ Balzer, Michael; Deussen, Oliver (2005). "Voronoi Treemaps". En Stasko, John T .; Ward, Matthew O. (eds.). Simposio de IEEE sobre visualización de información (InfoVis 2005), 23-25 de octubre de 2005, Minneapolis, MN, EE. UU. (PDF) . Sociedad de Informática IEEE. pag. 7..
- ^ Wattenberg, Martin (2005). "Una nota sobre visualizaciones que llenan el espacio y curvas que llenan el espacio". En Stasko, John T .; Ward, Matthew O. (eds.). Simposio de IEEE sobre visualización de información (InfoVis 2005), 23-25 de octubre de 2005, Minneapolis, MN, EE. UU. (PDF) . Sociedad de Informática IEEE. pag. 24..
- ^ Auber, David; Huet, Charles; Lambert, Antoine; Renoust, Benjamin; Sallaberry, Arnaud; Saulnier, Agnes (2013). " Mapa de Gosper : utilizando una curva de Gosper para trazar 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 ..
- ^ Shneiderman, Ben (1992). "Visualización de árboles con mapas de árboles: enfoque de llenado de espacio 2-d". Transacciones ACM en gráficos . 11 : 92–99. doi : 10.1145 / 102377.115768 . hdl : 1903/367 . S2CID 1369287 .
- ^ Cox, Amanda; Fairfield, Hannah (25 de febrero de 2007). "La salud del mercado de automóviles, furgonetas, SUV y camiones" . The New York Times . Consultado el 12 de marzo de 2010 .
- ^ Carter, Shan; Cox, Amanda (14 de febrero de 2011). "Propuesta de presupuesto 2012 de Obama: cómo se gastan $ 3,7 billones" . The New York Times . Consultado el 15 de febrero de 2011 .
enlaces externos
- Treemap Art Project produjo una exhibición para las Academias Nacionales en Washington, DC
- Un artículo de Ben Shneiderman sobre el uso de treemaps (como invitado en www.perceptualedge.com [1] )
- Estudio completo y bibliografía de técnicas de visualización de árboles
- Mapas de árboles generalizados
- Historia de Treemaps por Ben Shneiderman.
- Exploración hipermedia con mapas dinámicos interactivos Papel de Zizi y Beaudouin-Lafon que presenta el algoritmo de diseño de mapa de árbol cuadriculado (llamado "diseño de mapa de árbol mejorado" en ese momento).
- Descripción de la Universidad de Indiana
- Mapa de árbol interactivo en vivo basado en ofertas con descuento de fuentes colectivas de Flytail Group
- Ejemplo de mapa de árbol en inglés de The Hive Group
- Varios ejemplos de mapas de árbol hechos con Macrofocus TreeMap
- Visualizaciones que utilizan mapas de árboles dinámicos y software de creación de mapas de árboles de drasticdata
- Treemaps de exportaciones de productos desarrollados por el Observartory of Economic Complexity de Harvard-MIT
- newsmap.jp es un diagrama de árbol de las noticias de Google