트리밍
Treemapping정보 시각화 및 컴퓨팅에서 트리밍은 중첩된 그림(일반적으로 직사각형)을 사용하여 계층 데이터를 표시하는 방법입니다.
트리맵은 계층형(트리 구조화) 데이터를 중첩된 직사각형 세트로 표시합니다.트리의 각 가지에는 직사각형이 주어지고, 그 직사각형이 하위 가지를 나타내는 작은 직사각형으로 타일링됩니다.리프 노드의 직사각형에는 데이터의 [1]지정된 차원에 비례하는 영역이 있습니다.종종 리프 노드는 데이터의 개별 차원을 표시하기 위해 색상이 지정됩니다.
색상 및 크기 치수가 트리 구조와 어떤 식으로든 상관되어 있으면 특정 색상이 특별히 관련이 있는지 여부 등 다른 방법으로 발견하기 어려운 패턴을 쉽게 볼 수 있습니다.나무 맵의 두 번째 장점은 구조상 공간을 효율적으로 사용할 수 있다는 것입니다.그 결과, 수천 개의 아이템을 화면에 동시에 표시할 수 있습니다.
타일링 알고리즘
트리맵을 작성하려면 타일링 알고리즘을 정의해야 합니다.즉, 영역을 지정된 영역의 하위 영역으로 분할하는 방법을 정의합니다.트리맵 알고리즘은 다음 기준을 충족하는 영역을 작성하는 것이 이상적입니다.
- 작은 애스펙트비.이상적으로는 1에 가깝습니다.종횡비가 작은 영역(즉, 뚱뚱한 물체)은 인지하기 [2]쉽다.
- 입력 데이터(순서)의 순서 감각을 유지합니다.
- 기본 데이터의 변경 사항을 반영하여 변경(고안정성)
유감스럽게도 이러한 속성은 반비례 관계를 가지고 있습니다.애스펙트비가 최적화됨에 따라 배치 순서는 예측하기 어려워진다.순서가 안정될수록 석면비는 저하됩니다.[example needed]
직사각형 트리맵
지금까지 15개의 주요 직사각형 트리맵알고리즘이 개발되었습니다.
알고리즘. | 주문 | 석면비 | 안정성. |
---|---|---|---|
바이너리 트리 | 부분적으로 순서가 매겨졌다 | 높은 | 안정적인. |
슬라이스 앤 다이스[4] | 주문된 | 매우 높은 | 안정적인. |
벗다[5] | 주문된 | 중간의 | 중간 안정성 |
가운데로 피벗[6] | 주문된 | 중간의 | 중간 안정성 |
분할로 피벗[7] | 주문된 | 중간의 | 저안정성 |
크기별 피벗[8] | 주문된 | 중간의 | 중간 안정성 |
분열되다[9] | 주문된 | 중간의 | 중간 안정성 |
나선형[10] | 주문된 | 중간의 | 중간 안정성 |
힐베르트[11] | 주문된 | 중간의 | 중간 안정성 |
무어[12] | 주문된 | 중간의 | 중간 안정성 |
사각형[13] | 질서 없는 | 낮다 | 저안정성 |
혼합 트리맵[14] | 질서 없는 | 낮다 | 중간 안정성 |
근사치[15] | 질서 없는 | 낮다 | 중간 안정성 |
Git[16] | 질서 없는 | 중간의 | 안정적인. |
로컬 이동[17] | 질서 없는 | 중간의 | 안정적인. |
볼록한 나무잎
직사각형 트리맵은 최악의 경우 가로 세로 비율이 임의로 높을 수 있다는 단점이 있습니다.간단한 예로 트리 루트에 1/1 - 1 / - / 의 두 아이만 있는 경우 작은 아이의 애스펙트비는 nn이되며 는 임의로 높을 수 있습니다.이 문제에 대처하기 위해 직사각형이 아닌 일반적인 볼록 다각형 영역을 사용하는 여러 알고리즘이 제안되었다.
볼록 트리맵은 여러 단계로 개발되었으며, 각 단계는 종횡비 상한을 개선했다.경계는 트리의 총 노드 수인 n과 트리의 총 깊이인 dd의 로 지정됩니다.
- Onak 및 Sidiropoulos는[18]O (( d n ) O ( d \{ n 의 상한을 나타내고 있습니다.
- De-Berg 및 Onak 및 Sidiropoulos는[19] O+ logn)(\ {로의 상한을 개선하고 O O의 하한을 확인합니다.
- 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개의 스텝으로 동작합니다(명확하게 하기 위해서 큰폭으로 심플화).
- 원래 트리는 바이너리 트리로 변환됩니다.자식이 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] 고스퍼 곡선의 기하학적 구조를 기반으로 합니다.질서정연하고 안정적이지만 애스펙트비가 매우 높습니다.
역사
지역 기반 시각화는 수십 년 동안 존재해 왔습니다.예를 들어 모자이크 그림(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 전시회와 뉴욕의 현대미술관 컬렉션 세트를 선보였습니다.
「 」를 참조해 주세요.
- 디스크 공간 분석기
- 정보 시각화
- 경제 복잡도에 따른 국가 목록. 여기에는 제품 수출 트리맵 목록이 포함됩니다.
- Marimeko 차트, 한 가지 수준의 명시적 계층 구조를 가진 유사한 개념입니다.
레퍼런스
- ^ 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.
- ^ 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.
- ^ 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.
- ^ Shneiderman, Ben (2001). "Ordered treemap layouts" (PDF). Infovis: 73.
- ^ 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.
- ^ Shneiderman, Ben; Wattenberg, Martin (2001). "Ordered treemap layouts". IEEE Symposium on Information Visualization: 73–78.
- ^ Shneiderman, Ben; Wattenberg, Martin (2001). "Ordered treemap layouts". IEEE Symposium on Information Visualization: 73–78.
- ^ Shneiderman, Ben; Wattenberg, Martin (2001). "Ordered treemap layouts". IEEE Symposium on Information Visualization: 73–78.
- ^ Engdahl, Björn. "Ordered and quantum treemaps: Making effective use of 2D space to display hierarchies".
{{cite journal}}
:Cite 저널 요구 사항journal=
(도움말) - ^ Tu, Y.; Shen, H. (2007). "Visualizing changes of hierarchical data using treemaps". 13 (6): 1286–1293.
{{cite journal}}
:Cite 저널 요구 사항journal=
(도움말) - ^ 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.
- ^ 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.
- ^ 를 클릭합니다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..
- ^ 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.
- ^ 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.
- ^ Vernier, E.; Comba, J.; Telea, A. (2018). "Quantitative comparison of dy-namic treemaps for software evolution visualization". Conferenceon Software Visualization: 99–106.
- ^ 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.
- ^ Krzysztof Onak; Anastasios Sidiropoulos. "Circular Partitions with Applications to Visualization and Embeddings". Retrieved June 26, 2011.
- ^ 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.
- ^ 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.. 회의 버전:
- ^ 를 클릭합니다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..
- ^ 를 클릭합니다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..
- ^ 를 클릭합니다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..
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
외부 링크
- Treemap Art Project는 워싱턴 DC에 있는 국립 아카데미를 위한 전시회를 제작했습니다.
- 트리맵 사용에 관한 Ben Shneiderman의 기사(www.perceptualedge.com의 게스트로서 [1])
- Tree Visualization 기술에 대한 포괄적인 조사
- 일반화된 트리맵
- Ben Shneiderman의 Treemaps 역사.
- 인터랙티브 다이내믹 맵 Paper by Zizi 및 Beaudouin-Lafon을 사용한 하이퍼미디어 탐색으로 사각형 트리맵 레이아웃 알고리즘(당시 "향상된 트리맵 레이아웃"으로 명명됨)이 도입되었습니다.
- 인디애나 대학교 설명
- Flytail Group의 크라우드 소싱 할인된 거래에 기반한 라이브 인터랙티브 트리맵
- The Hive Group의 영어 Treemap 샘플
- Macrofocus TreeMap을 사용한 몇 가지 트리맵 예시
- 과감한 데이터에 의한 동적 트리맵 및 트리밍 소프트웨어를 사용한 시각화
- Harvard-MIT 경제 복잡성 관측소가 개발한 제품 수출용 트리맵
- newsmap.jp은 구글 뉴스의 트리맵입니다.