Hispanopedia Wiki
Articulo de referencia

Mapeo de árboles

Diagrama de árbol de las exportaciones de Singapur por categoría de producto, 2012. Los diagramas de árbol de exportaciones de productos son una de las aplicaciones más reciente...

Hispanopedia WikiContenido en espanolLectura gratuita
Diagrama de árbol de las exportaciones de Singapur por categoría de producto, 2012. Los diagramas de árbol 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 visualización de información e informática , 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 forma de árbol ) como un conjunto de rectángulos anidados. A cada rama del árbol se le asigna un rectángulo, que luego se cubre con rectángulos más pequeños que representan subramas. El área del rectángulo de un nodo hoja es proporcional a una dimensión específica de los datos . [ 1 ] A menudo, los nodos hoja se colorean para mostrar una dimensión distinta de los datos.

Cuando el color y el tamaño se correlacionan de alguna manera con la estructura del árbol, a menudo se pueden observar patrones que serían difíciles de detectar de otra forma, como por ejemplo, si un color determinado predomina. Una segunda ventaja de los mapas de árbol es que, por su diseño, hacen un uso eficiente del espacio. Como resultado, pueden mostrar miles de elementos en la pantalla de forma legible y simultánea.

Algoritmos de teselado

Para crear un mapa de árbol, es necesario definir un algoritmo de teselado , 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. Conservar cierto sentido del orden en los datos de entrada (ordenados).
  3. Modificar para reflejar los cambios en los datos subyacentes (alta estabilidad).

Estas propiedades presentan 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 estabiliza, la relación de aspecto se degrada.

mapas de árbol rectangulares

Hasta la fecha, se han desarrollado quince algoritmos principales de mapas de árbol rectangulares:

Mapas de árbol 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 peso1/norte{\displaystyle 1/n}y uno con peso1−1/norte{\displaystyle 1-1/n}, entonces la relación de aspecto del niño más pequeño seránorte{\displaystyle n}, 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 como una función denorte{\displaystyle n}- el número total de nodos en el árbol, yd{\displaystyle d}- la profundidad total del árbol.

  1. Onak y Sidiropoulos [ 15 ] demostraron una cota superior deO((dregistro⁡norte)17){\displaystyle O((d\log {n})^{17})}.
  2. De-Berg y Onak y Sidiropoulos [ 16 ] mejoran el límite superior deO(d+registro⁡norte){\displaystyle O(d+\log {n})}y demostrar una cota inferior deO(d){\displaystyle O(d)}.
  3. De-Berg y Speckmann y van-der-Weele [ 17 ] mejoran el límite superior aO(d){\displaystyle O(d)}, coincidiendo con el límite inferior teórico. (Para el caso especial en que la profundidad es 1, presentan un algoritmo que utiliza solo 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/7).

Los dos últimos algoritmos operan 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 todos los bordes de un polígono convexo están separados por un ángulo de al menosϕ{\displaystyle \phi }, entonces su relación de aspecto esO(1/ϕ){\displaystyle O(1/\phi )}. Es posible asegurar que, en un árbol de profundidadd{\displaystyle d}, el ángulo se divide por un factor de como máximod{\displaystyle d}, de ahí la garantía de la relación de aspecto.

mapas de árbol ortoconvexos

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

Para el caso especial en el que la profundidad es 1, presentan un algoritmo que utiliza solo rectángulos y formas de L, y la relación de aspecto es como máximo2+2/3≈3.15{\displaystyle 2+2/{\sqrt {3}}\approx 3.15}; los nodos internos utilizan solo rectángulos con una relación de aspecto como máximo1+3≈2,73{\displaystyle 1+{\sqrt {3}}\approx 2.73}.

Otros mapas de árbol

Mapas de árbol de Voronoi
[ 18 ] basado ende diagramas de Voronoi. El algoritmo es iterativo y no proporciona ningún límite superior para la relación de aspecto.
Mapas de árbol en rompecabezas [ 19 ]
Basándose en la geometría de curvas que llenan el espacio, asumen que los pesos son enteros y que su suma es un cuadrado perfecto. Las regiones del mapa son polígonos rectilíneos y altamente no ortoconvexos. Su relación de aspecto está garantizada para ser como máximo 4.
GosperMaps
[ 20 ] basado en la geometría delas curvas de Gosper. Es ordenado y estable, pero tiene una relación de aspecto muy alta.

Historia

El uso del espacio en disco duro se visualiza en TreeSize, un 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 teselaciones 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 al introducir una variedad de técnicas interactivas para filtrar y ajustar mapas de árbol.

Todos estos primeros mapas de árbol utilizaban el sencillo algoritmo de teselado "rebanar y cortar". A pesar de sus muchas propiedades deseables (es estable, conserva el orden y es fácil de implementar), el método de rebanar y cortar suele producir teselados con muchos rectángulos largos y estrechos. En 1994, Mountaz Hascoet y Michel Beaudouin-Lafon inventaron un algoritmo de "cuadración", popularizado posteriormente por Jarke van Wijk , que creaba teselados cuyos rectángulos se aproximaban más a un cuadrado. En 1999, Martin Wattenberg utilizó una variación del algoritmo de "cuadración" que denominó "pivotar y cortar" para crear el primer mapa de árbol basado en la web, el SmartMoney Map of the Market, que mostraba datos de cientos de empresas del mercado bursátil estadounidense. Tras su lanzamiento, los mapas de árbol experimentaron un auge de interés, especialmente en el ámbito financiero.

Una tercera ola de innovación en mapas de árbol llegó 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 nueva y amplia audiencia. En los últimos años, los mapas de árbol se han abierto camino en los medios de comunicación convencionales, incluido su uso por parte del 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.

Véase también

Referencias

  1. ↑ Li, Rita Yi Man; Chau, Kwong Wing; Zeng, Frankie Fanjie (2019). "Clasificación de riesgos para obras de construcción existentes y nuevas" . Sustainability . 11 (10): 2863. Bibcode : 2019Sust...11.2863L . doi : 10.3390/su11102863 .
  2. ↑ Kong, N; Heer, J; Agrawala, M (2010). "Directrices perceptuales para la creación de mapas de árbol rectangulares". IEEE Transactions on Visualization and Computer Graphics . 16 (6): 990– 8. Bibcode : 2010ITVCG..16..990K . 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 árbol dependientes del tiempo". Computer Graphics Forum . 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. ↑ Benjamin, Bederson; Shneiderman, Ben; Wattenberg, Martin (2002). "Ordered and quantum treemaps: Making effective use of 2D space to display hierarchies" (PDF) . ACM Transactions on Graphics . 21 (4): 833– 854. CiteSeerX 10.1.1.145.2634 . doi : 10.1145/571647.571649 . hdl : 1903/6486 . S2CID 7253456 .  
  6. 1 2 3 Shneiderman, Ben; Wattenberg, Martin (2001). "Diseños de mapas de árbol ordenados". Simposio IEEE sobre visualización de información : 73–78 .
  7. ↑ Engdahl, Björn. Treemaps ordenados y cuánticos: uso efectivo del espacio 2D para mostrar jerarquías .
  8. ↑ Tu, Y.; Shen, H. (2007). "Visualizing changes of hierarchical data using treemaps" (PDF) . IEEE Transactions on Visualization and Computer Graphics . 13 ( 6): 1286– 1293. Bibcode : 2007ITVCG..13.1286T . doi : 10.1109/TVCG.2007.70529 . PMID 17968076. S2CID 14206074. Archivado (PDF) del original el 8 de agosto de 2022.  
  9. 1 2 Tak, S.; Cockburn, A. (2013). "Estabilidad espacial mejorada con mapas de árbol de Hilbert y Moore" (PDF) . IEEE Transactions on Visualization and Computer Graphics . 19 (1): 141– 148. Bibcode : 2013ITVCG..19..141T . 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 a 42. .
  11. ↑ Roël Vliegen; Erik-Jan van der Linden; Jarke J. van Wijk . "Visualización de datos empresariales 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, Martin (2007). "Un algoritmo de aproximación para dividir un rectángulo en rectángulos con áreas específicas" . Matemáticas Aplicadas Discretas . 155 (4): 523– 537. doi : 10.1016/j.dam.2006.08.005 .
  13. ↑ Faccin Vernier, Eduardo; Dihl Comba, Joao Luiz; Telea, Alexandru C. (2018). "Comparación cuantitativa de mapas de árbol dinámicos para la visualización de la evolución del software" (PDF) . Actas de la sexta conferencia de trabajo IEEE sobre visualización de software . VISSOFT 2018. págs. 99–106 . doi : 10.1109/VISSOFT.2018.00018 . hdl : 11370/f2713bfd-5be7-4db4-89f8-cd161b033ce9 . S2CID 53278664. Recuperado el 15 de enero de 2025 .  
  14. ↑ Sondag, M.; Speckmann, B.; Verbeek, K. (2018). "Stable treemaps via local moves" (PDF) . IEEE Transactions on Visualization and Computer Graphics . 24 (1): 729– 738. Bibcode : 2018ITVCG..24..729S . doi : 10.1109/TVCG.2017.2745140 . PMID 28866573. S2CID 27739774 .  
  15. ↑ Krzysztof Onak; Anastasios Sidiropoulos. "Particiones circulares con aplicaciones a la visualización e incrustaciones" . Consultado el 26 de junio de 2011 .
  16. ↑ Mark de Berg; Onak, Krzysztof; Sidiropoulos, Anastasios (2013). "Particiones poligonales gruesas con aplicaciones a la visualización e incrustaciones" . Journal of Computational Geometry . 4 (1): 212– 239. arXiv : 1009.1866 .
  17. 1 2 De Berg, Mark; Speckmann, Bettina ; Van Der Weele, Vincent (2014). "Mapas de árboles con relación de aspecto limitada" . 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 limitada (PDF) . EuroCG. 2011.
  18. ↑ Balzer, Michael; Deussen, Oliver (2005). "Mapas de árbol 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) . IEEE Computer Society. pág. 7. .
  19. ↑ Wattenberg, Martin (2005). "Una nota sobre visualizaciones 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) . IEEE Computer Society. pág. 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 . Bibcode : 2013ITVCG..19.1820A . 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 2D". ACM Transactions on Graphics . 11 : 92–99 . doi : 10.1145/102377.115768 . hdl : 1903/367 . S2CID 1369287 . 
  22. ↑ Ben Shneiderman ; Catherine Plaisant (25 de junio de 2009). "Mapas de árbol para la visualización de jerarquías con limitaciones de espacio ~ Incluyendo la historia de la investigación sobre mapas de árbol en la Universidad de Maryland" . Recuperado 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" . The 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" . The New York Times . Consultado el 15 de febrero de 2011 .
  25. ↑ "Arte de mapas de árboles" . Archivado del original el 5 de diciembre de 2023.
  26. ↑ "Cada algoritmo tiene ARTE: Proyecto de arte de mapas de árbol" . CPNAS . Archivado del original el 8 de octubre de 2023.
  • El proyecto artístico Treemap produjo una exposición para las Academias Nacionales en Washington, D.C.
  • "Descubriendo la inteligencia empresarial mediante visualizaciones de mapas de árbol" , Ben Shneiderman , 11 de abril de 2006
  • Estudio exhaustivo y bibliografía de técnicas de visualización de árboles.
  • Vliegen, Roel; van Wijk, Jarke J.; van der Linden, Erik-Jan (septiembre-octubre de 2006). "Visualización de datos empresariales con mapas de árbol generalizados" ( PDF) . IEEE Transactions on Visualization and Computer Graphics . 12 (5): 789–796 . Bibcode : 2006ITVCG..12..789V . doi : 10.1109/TVCG.2006.200 . PMID 17080801. S2CID 18891326. Archivado del original (PDF) el 24 de julio de 2011.  
  • Historia de los mapas de árbol por Ben Shneiderman.
  • Exploración de hipermedia con mapas dinámicos interactivos. Artículo de Zizi y Beaudouin-Lafon que presenta el algoritmo de diseño de mapa de árbol cuadrado (denominado en su momento "diseño de mapa de árbol mejorado").
  • Descripción de la Universidad de Indiana
  • Mapa interactivo en tiempo real basado en ofertas con descuento recopiladas por los usuarios de Flytail Group.
  • Ejemplo de mapa de árbol en inglés de The Hive Group
  • Varios ejemplos de mapas de árbol creados con Macrofocus TreeMap.
  • Visualizaciones mediante mapas de árbol dinámicos y software de mapeo de árboles en línea de drasticdata
Lecturas relacionadas
6 articulos
Visualización de datos e informaciónVisualización de datos e informaciónLa visualización de datos e información ( data viz/vis o info viz/vis ) [2] es la práctica de diseñar y crear representaciones gráficas o visuales ...Simulación por computadoraComputaciónLa informática es cualquier actividad orientada a objetivos que requiera, se beneficie o cree maquinaria informática . [1] Incluye el estudio y la ...JerarquíaJerarquíaLa scala naturae medieval como escalera, que implica la posibilidad de progreso : [1] La escalera de ascenso y descenso del espíritu de Ramon Llull...Anidamiento (computación)En informática y ciencias de la computación , la anidación [1] es cuando la información se organiza en capas o cuando los objetos contienen otros o...Árbol (estructura de datos)Este árbol no ordenado tiene valores no únicos (por ejemplo, el valor 2 existe en diferentes nodos, no en un solo nodo) y no es binario (solo hasta...AlgoritmoAlgoritmoEn matemáticas y ciencias de la computación , un algoritmo ( / ˈ æ l ɡ ə r ɪ ð əm / ⓘ ) es una secuencia finita deinstruccionesmatemáticamente rigu...