트리밍

Treemapping
2012년 싱가포르 수출품목별 트리맵.Product Exports Treemaps는 Harvard-MIT Observatory of Economic Complexity가 개발한 이러한 종류의 시각화의 최신 응용 프로그램 중 하나입니다.

정보 시각화 컴퓨팅에서 트리밍은 중첩된 그림(일반적으로 직사각형)을 사용하여 계층 데이터를 표시하는 방법입니다.

트리맵은 계층형(트리 구조화) 데이터를 중첩된 직사각형 세트로 표시합니다.트리의 각 가지에는 직사각형이 주어지고, 그 직사각형이 하위 가지를 나타내는 작은 직사각형으로 타일링됩니다.리프 노드의 직사각형에는 데이터의 [1]지정된 차원에 비례하는 영역이 있습니다.종종 리프 노드는 데이터의 개별 차원을 표시하기 위해 색상이 지정됩니다.

색상 및 크기 치수가 트리 구조와 어떤 식으로든 상관되어 있으면 특정 색상이 특별히 관련이 있는지 여부 등 다른 방법으로 발견하기 어려운 패턴을 쉽게 볼 수 있습니다.나무 맵의 두 번째 장점은 구조상 공간을 효율적으로 사용할 수 있다는 것입니다.그 결과, 수천 개의 아이템을 화면에 동시에 표시할 수 있습니다.

타일링 알고리즘

트리맵을 작성하려면 타일링 알고리즘을 정의해야 합니다.즉, 영역을 지정된 영역의 하위 영역으로 분할하는 방법을 정의합니다.트리맵 알고리즘은 다음 기준을 충족하는 영역을 작성하는 것이 이상적입니다.

  1. 작은 애스펙트비.이상적으로는 1에 가깝습니다.종횡비가 작은 영역(, 뚱뚱한 물체)은 인지하기 [2]쉽다.
  2. 입력 데이터(순서)의 순서 감각을 유지합니다.
  3. 기본 데이터의 변경 사항을 반영하여 변경(고안정성)

유감스럽게도 이러한 속성은 반비례 관계를 가지고 있습니다.애스펙트비가 최적화됨에 따라 배치 순서는 예측하기 어려워진다.순서가 안정될수록 석면비는 저하됩니다.[example needed]

직사각형 트리맵

지금까지 15개의 주요 직사각형 트리맵알고리즘이 개발되었습니다.

트리맵 알고리즘[3]
알고리즘. 주문 석면비 안정성.
바이너리 트리 부분적으로 순서가 매겨졌다 높은 안정적인.
슬라이스 앤 다이스[4] 주문된 매우 높은 안정적인.
벗다[5] 주문된 중간의 중간 안정성
가운데로 피벗[6] 주문된 중간의 중간 안정성
분할로 피벗[7] 주문된 중간의 저안정성
크기별 피벗[8] 주문된 중간의 중간 안정성
분열되다[9] 주문된 중간의 중간 안정성
나선형[10] 주문된 중간의 중간 안정성
힐베르트[11] 주문된 중간의 중간 안정성
무어[12] 주문된 중간의 중간 안정성
사각형[13] 질서 없는 낮다 저안정성
혼합 트리맵[14] 질서 없는 낮다 중간 안정성
근사치[15] 질서 없는 낮다 중간 안정성
Git[16] 질서 없는 중간의 안정적인.
로컬 이동[17] 질서 없는 중간의 안정적인.

볼록한 나무잎

직사각형 트리맵은 최악의 경우 가로 세로 비율이 임의로 높을 수 있다는 단점이 있습니다.간단한 예로 트리 루트에 1/1 - 1 / - / 두 아이만 있는 경우 작은 아이의 애스펙트비는 nn이되며 는 임의로 높을 수 있습니다.이 문제에 대처하기 위해 직사각형이 아닌 일반적인 볼록 다각형 영역을 사용하는 여러 알고리즘이 제안되었다.

볼록 트리맵은 여러 단계로 개발되었으며, 각 단계는 종횡비 상한을 개선했다.경계는 트리의 총 노드 수인 n과 트리의 총 깊이인 dd의 로 지정됩니다.

  1. Onak 및 Sidiropoulos는[18]O (( d n ) O ( d \{ n 의 상한을 나타내고 있습니다.
  2. De-Berg 및 Onak 및 Sidiropoulos는[19] O+ logn)(\ {로의 상한을 개선하고 O O의 하한을 확인합니다.
  3. De-Berg과 Speckmann과 van-der-Weele[20]는 이론적 낮다.(그 깊이는 1특별한 경우, 그들은 45-degree-polygons(사각형, 직각 삼각형, 직각 여기 보시면 사다리꼴과 45-degree 5각형의 4개밖에 없는 클래스를 사용하여 알고리즘을 제시하게 되어 이 위 O(d){O(d)\displaystyle}에 바인딩을 개선합니다.s),최대 34/7의 애스펙트 비를 보증합니다.)

후자의 2개의 알고리즘은, 다음의 2개의 스텝으로 동작합니다(명확하게 하기 위해서 큰폭으로 심플화).

  1. 원래 트리는 바이너리 트리로 변환됩니다.자식이 2개 이상인 각 노드는 정확히 2개의 자식이 있는 하위 트리로 대체됩니다.
  2. 노드(루트부터 시작)를 나타내는 각 영역은 가장자리 사이의 각도를 가능한 크게 유지하는 선을 사용하여 2개로 분할됩니다.볼록 폴리곤의 모든 가장자리가 { 각도로 분리되어 있는 경우, 그 석면비는 ( 1/ ) { O ( / \ 이며, 깊이의 트리에서 각도는 d의계수로 분할되어 있음을 확인할 수 있습니다. d 즉 애스펙트비가 보증됩니다.

직교 볼록 트리맵

볼록한 나무 지도에서는 가로 세로 비율이 일정할 수 없습니다. 나무의 깊이에 따라 늘어납니다.일정한 종횡비를 얻기 위해 직교 볼록 트리맵[20] 사용할 수 있습니다.여기에서 모든 영역은 아스펙트비가 최대 64인 직각 직선 다각형이며, 잎은 아스펙트비가 최대 8인 직사각형이거나, 석면비가 최대 32인 L자형 또는 S자형이다.

깊이가 1인 특수한 경우에는 직사각형과 L자형만을 사용하는 알고리즘을 제시하며, 아스펙트비는 + / 33})입니다. 노드는 1 + 73 273\약 3.15의 직사각형만을

기타 트리맵

보로노이 트리맵스
[21] Voronoi 다이어그램 계산에 기초합니다.이 알고리즘은 반복적이며 석면비에 상한을 부여하지 않습니다.
직소[22] 트리맵스
공간을 채우는 곡선의 기하학적 구조를 기반으로 합니다.가중치가 정수이고 합계가 제곱수라고 가정합니다.지도의 영역은 직선 다각형과 매우 비정형이다.애스펙트비는 최대 4까지 보장됩니다.
고스퍼맵
[23] 고스퍼 곡선의 기하학적 구조를 기반으로 합니다.질서정연하고 안정적이지만 애스펙트비가 매우 높습니다.

역사

1996년에 처음 출시된 소프트웨어인 Tree Size에 표시된 하드 디스크 공간 사용량

지역 기반 시각화는 수십 년 동안 존재해 왔습니다.예를 들어 모자이크 그림(Marimeko 다이어그램이라고도 함)은 직사각형 타일링을 사용하여 접합 분포를 표시합니다(즉, 기본적으로 열의 너비가 서로 다른 쌓인 열 그림).그러나 트리맵의 주요 구별 기능은 임의의 수의 레벨을 가진 계층형 데이터로 확장할 수 있는 재귀 구조입니다.이 아이디어는 1990년대 초 메릴랜드 대학 인간 컴퓨터 상호작용 연구소의 벤 슈나이더맨 교수에 의해 발명되었다.[24][25] Shneiderman과 그의 협력자들은 나무 맵을 필터링하고 조정하는 다양한 인터랙티브 기술을 도입함으로써 아이디어를 심화시켰습니다.

이러한 초기 트리맵은 모두 단순한 "슬라이스 앤 다이스" 타일링 알고리즘을 사용했습니다.많은 바람직한 특성(안정적이고 순서를 유지하며 구현하기 쉬움)에도 불구하고 슬라이스 앤 다이스 방식은 종종 길고 마른 직사각형으로 타일링을 생성합니다.1994년 Mountaz Hasscoet와 Michel Beaudouin-Lafon은 사각형에 가까운 타일링을 만드는 "제곱화" 알고리즘을 발명했다.1999년 마틴 왓텐버그는 "피봇 앤 슬라이스"라고 부르는 "제곱" 알고리즘을 변형하여 최초의 웹 기반 트리맵인 "스마트머니 시장 지도"를 만들었습니다. 이 맵은 미국 주식 시장에 있는 수백 개의 회사에 대한 데이터를 표시합니다.출시 이후 트리맵은 특히 재정적인 [citation needed]맥락에서 관심이 급증했다.

번째 트리맵 혁신 물결은 Marcos Weskamp가 뉴스 헤드라인을 보여주는 트리맵인 Newsmap을 만든 후 2004년경에 찾아왔다.이 비분석적인 트리맵의 예는 많은 모방자들에게 영감을 주었고, 트리맵을 새롭고 광범위한 [citation needed]청중에게 소개했습니다.최근 몇 년 동안 트리맵은 뉴욕 [26][27]타임즈의 사용을 포함하여 주류 미디어에 진출했다.Treemap Art Project는 미국 국립아카데미(미국)를 위해 12개의 프레임 이미지를 제작했으며, Every AlgoRiThm has ART in It 전시회와 뉴욕의 현대미술관 컬렉션 세트를 선보였습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Li, Rita Yi Man; Chau, Kwong Wing; Zeng, Frankie Fanjie (2019). "Ranking of Risks for Existing and New Building Works". Sustainability. 11 (10): 2863. doi:10.3390/su11102863.
  2. ^ Kong, N; Heer, J; Agrawala, M (2010). "Perceptual Guidelines for Creating Rectangular Treemaps". IEEE Transactions on Visualization and Computer Graphics. 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). "Quantitative Comparison of Time‐Dependent Treemaps". Computer Graphics Forum. 39 (3): 393–404. arXiv:1906.06014. doi:10.1111/cgf.13989. S2CID 189898065.
  4. ^ Shneiderman, Ben (2001). "Ordered treemap layouts" (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. S2CID 7253456.
  6. ^ Shneiderman, Ben; Wattenberg, Martin (2001). "Ordered treemap layouts". IEEE Symposium on Information Visualization: 73–78.
  7. ^ Shneiderman, Ben; Wattenberg, Martin (2001). "Ordered treemap layouts". IEEE Symposium on Information Visualization: 73–78.
  8. ^ Shneiderman, Ben; Wattenberg, Martin (2001). "Ordered treemap layouts". IEEE Symposium on Information Visualization: 73–78.
  9. ^ Engdahl, Björn. "Ordered and quantum treemaps: Making effective use of 2D space to display hierarchies". {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  10. ^ Tu, Y.; Shen, H. (2007). "Visualizing changes of hierarchical data using treemaps". 13 (6): 1286–1293. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  11. ^ Tak, S.; Cockburn, A. (2013). "Enhanced spatial stability with Hilbert and Moore treemaps". Transactions on Visualization and Computer Graphics. 19 (1): 141–148. doi:10.1109/TVCG.2012.108. PMID 22508907. S2CID 6099935.
  12. ^ Tak, S.; Cockburn, A. (2013). "Enhanced spatial stability with Hilbert and Moore treemaps". Transactions on Visualization and Computer Graphics. 19 (1): 141–148. doi:10.1109/TVCG.2012.108. PMID 22508907. S2CID 6099935.
  13. ^ 를 클릭합니다Bruls, Mark; Huizing, Kees; van Wijk, Jarke J. (2000). "Squarified treemaps". In de Leeuw, W.; van Liere, R. (eds.). Data Visualization 2000: Proc. Joint Eurographics and IEEE TCVG Symp. on Visualization (PDF). Springer-Verlag. pp. 33–42..
  14. ^ Roel Vliegen; Erik-Jan van der Linden; Jarke J. van Wijk. "Visualizing Business Data with Generalized Treemaps" (PDF). Archived from the original (PDF) on July 24, 2011. Retrieved February 24, 2010.
  15. ^ Nagamochi, H.; Abe, Y.; Wattenberg, Martin (2007). "An approximation algorithm for dissect-ing a rectangle into rectangles with specified areas". Discrete Applied Mathematics. 155 (4): 523–537. doi:10.1016/j.dam.2006.08.005.
  16. ^ Vernier, E.; Comba, J.; Telea, A. (2018). "Quantitative comparison of dy-namic treemaps for software evolution visualization". Conferenceon Software Visualization: 99–106.
  17. ^ Sondag, M.; Speckmann, B.; Verbeek, K. (2018). "Stable treemaps via local moves". Transactions on Visualization and Computer Graphics. 24 (1): 729–738. doi:10.1109/TVCG.2017.2745140. PMID 28866573. S2CID 27739774.
  18. ^ Krzysztof Onak; Anastasios Sidiropoulos. "Circular Partitions with Applications to Visualization and Embeddings". Retrieved June 26, 2011.
  19. ^ Mark de Berg; Onak, Krzysztof; Sidiropoulos, Anastasios (2013). "Fat Polygonal Partitions with Applications to Visualization and Embeddings". Journal of Computational Geometry. 4 (1): 212–239. arXiv:1009.1866.
  20. ^ a b De Berg, Mark; Speckmann, Bettina; Van Der Weele, Vincent (2014). "Treemaps with bounded aspect ratio". Computational Geometry. 47 (6): 683. arXiv:1012.1749. doi:10.1016/j.comgeo.2013.12.008. S2CID 12973376.. 회의 버전:
  21. ^ 를 클릭합니다Balzer, Michael; Deussen, Oliver (2005). "Voronoi Treemaps". In Stasko, John T.; Ward, Matthew O. (eds.). IEEE Symposium on Information Visualization (InfoVis 2005), 23-25 October 2005, Minneapolis, MN, USA (PDF). IEEE Computer Society. p. 7..
  22. ^ 를 클릭합니다Wattenberg, Martin (2005). "A Note on Space-Filling Visualizations and Space-Filling Curves". In Stasko, John T.; Ward, Matthew O. (eds.). IEEE Symposium on Information Visualization (InfoVis 2005), 23-25 October 2005, Minneapolis, MN, USA (PDF). IEEE Computer Society. p. 24..
  23. ^ 를 클릭합니다Auber, David; Huet, Charles; Lambert, Antoine; Renoust, Benjamin; Sallaberry, Arnaud; Saulnier, Agnes (2013). "Gosper Map: Using a Gosper Curve for laying out hierarchical data". IEEE Transactions on Visualization and Computer Graphics. 19 (11): 1820–1832. doi:10.1109/TVCG.2013.91. PMID 24029903. S2CID 15050386..
  24. ^ Shneiderman, Ben (1992). "Tree visualization with tree-maps: 2-d space-filling approach". ACM Transactions on Graphics. 11: 92–99. doi:10.1145/102377.115768. hdl:1903/367. S2CID 1369287.
  25. ^ Ben Shneiderman; Catherine Plaisant (June 25, 2009). "Treemaps for space-constrained visualization of hierarchies ~ Including the History of Treemap Research at the University of Maryland". Retrieved February 23, 2010.
  26. ^ Cox, Amanda; Fairfield, Hannah (February 25, 2007). "The health of the car, van, SUV, and truck market". The New York Times. Retrieved March 12, 2010.
  27. ^ Carter, Shan; Cox, Amanda (February 14, 2011). "Obama's 2012 Budget Proposal: How $3.7 Trillion is Spent". The New York Times. Retrieved February 15, 2011.

외부 링크