트리맵핑

섬네일|2012년 제품 카테고리별 싱가포르 수출 트리맵. 제품 수출 트리맵은 하버드-MIT 경제 복잡성 관측소(Harvard-MIT Observatory of Economic Complexity)에서 개발한 이러한 종류의 시각화 중 가장 최신 응용 사례 중 하나이다.

정보 시각화 및 컴퓨팅에서 **트리맵핑**()은 보통 직사각형인 네스팅된 도형을 사용하여 계층적 데이터를 표시하는 방법이다.

트리맵은 계층적(트리 구조) 데이터를 일련의 중첩된 직사각형으로 표시한다. 트리의 각 분기(branch)에는 직사각형이 할당되고, 그 안에 하위 분기를 나타내는 더 작은 직사각형들이 타일링된다. 리프 노드(leaf node)의 직사각형 면적은 데이터의 지정된 차원에 비례한다. 종종 리프 노드에 색상을 입혀 데이터의 별도 차원을 나타내기도 한다.

색상과 크기 차원이 트리 구조와 어떤 방식으로든 상관관계가 있을 때, 특정 색상이 특히 두드러지는지 여부와 같이 다른 방식으로는 발견하기 어려운 패턴을 쉽게 확인할 수 있는 경우가 많다. 트리맵의 두 번째 장점은 구조상 공간을 효율적으로 사용한다는 것이다. 결과적으로 수천 개의 항목을 화면에 동시에 가독성 있게 표시할 수 있다.

## 타일링 알고리즘
트리맵을 만들려면 영역을 지정된 면적의 하위 영역으로 나누는 방법인 타일링 알고리즘을 정의해야 한다. 이상적으로 트리맵 알고리즘은 다음 기준을 만족하는 영역을 생성해야 한다.
# 작은 가로세로비—이상적으로는 1에 가까워야 한다. 가로세로비가 작은 영역(즉, 지방 객체)은 시각적으로 인지하기 더 쉽다.
# 입력 데이터의 순서 감각을 유지해야 한다(ordered).
# 기본 데이터의 변화를 반영하여 변경되어야 한다(높은 안정성).
이러한 속성들은 역관계에 있다. 가로세로비가 최적화될수록 배치 순서를 예측하기 어려워진다. 순서가 더 안정적이 될수록 가로세로비는 나빠진다.

### 직사각형 트리맵
현재까지 15개의 주요 직사각형 트리맵 알고리즘이 개발되었다.

### 볼록 트리맵
직사각형 트리맵은 최악의 경우 가로세로비가 임의로 높아질 수 있다는 단점이 있다. 간단한 예로, 트리의 루트에 자식이 둘만 있고 하나는 가중치가 1/n, 다른 하나는 1-1/n인 경우, 작은 쪽 자식의 가로세로비는 n이 되어 임의로 커질 수 있다.
이 문제를 해결하기 위해, 반드시 직사각형이 아닌 일반적인 볼록 다각형 영역을 사용하는 여러 알고리즘이 제안되었다.

**볼록 트리맵**은 여러 단계에 걸쳐 개발되었으며, 각 단계마다 가로세로비의 상한선이 개선되었다. 상한선은 트리의 전체 노드 수 n과 트리의 전체 깊이 d에 대한 함수로 주어진다.

# 오나크(Onak)와 시디로풀로스(Sidiropoulos)는 O((d\log{n})^{17})의 상한선을 증명했다.
# 데베르그(De-Berg), 오나크, 시디로풀로스는 상한선을 O(d+\log{n})으로 개선하고, O(d)의 하한선을 증명했다.
# 데베르그, 스펙만(Speckmann), 판더베일레(van-der-Weele)는 상한선을 O(d)로 개선하여 이론적 하한선과 일치시켰다. (깊이가 1인 특수한 경우에 대해, 그들은 4가지 클래스의 45도 다각형(직사각형, 직각삼각형, 직각사다리꼴, 45도 오각형)만을 사용하고 가로세로비를 최대 34/7로 보장하는 알고리즘을 제시했다.)

후자의 두 알고리즘은 두 단계로 작동한다(명확성을 위해 대폭 단순화함).
# 원래 트리는 이진 트리로 변환된다. 자식이 둘 이상인 각 노드는 각 노드가 정확히 두 개의 자식을 갖는 하위 트리로 대체된다.
# 노드를 나타내는 각 영역(루트부터 시작)은 모서리 사이의 각도를 가능한 한 크게 유지하는 선을 사용하여 둘로 나뉜다. 볼록 다각형의 모든 모서리가 최소 \phi의 각도로 분리되어 있으면 가로세로비가 O(1/\phi)임을 증명할 수 있다. 깊이 d인 트리에서 각도가 최대 d의 인수로 나뉘도록 보장할 수 있으므로 가로세로비 보장이 가능하다.

#### 직교 볼록 트리맵
볼록 트리맵에서 가로세로비는 상수가 될 수 없으며 트리의 깊이에 따라 커진다.
일정한 가로세로비를 얻기 위해 **직교 볼록 트리맵**을 사용할 수 있다. 여기서 모든 영역은 가로세로비가 최대 64인 직교 볼록 직교 다각형이며, 리프 노드는 가로세로비가 최대 8인 직사각형이거나 가로세로비가 최대 32인 L자형 또는 S자형이다.

깊이가 1인 특수한 경우에 대해, 그들은 직사각형과 L자형만을 사용하는 알고리즘을 제시했으며, 가로세로비는 최대 2 + 2 /\sqrt{3} \approx 3.15이다. 내부 노드는 가로세로비가 최대 1+\sqrt{3} \approx 2.73인 직사각형만을 사용한다.

### 기타 트리맵
;보로노이 트리맵: 보로노이 다이어그램 계산에 기반한다. 알고리즘은 반복적이며 가로세로비에 대한 상한선을 제공하지 않는다.
;직소(Jigsaw) 트리맵: 공간 채움 곡선의 기하학적 구조에 기반한다. 가중치가 정수이고 그 합이 제곱수라고 가정한다. 지도의 영역은 직교 다각형이며 매우 비직교 볼록하다. 가로세로비는 최대 4로 보장된다.
;GosperMaps: 고스퍼 곡선의 기하학적 구조에 기반한다. 순서가 있고 안정적이지만 가로세로비가 매우 높다.

## 역사
섬네일|1996년에 처음 출시된 소프트웨어인 TreeSize에서 시각화된 하드 디스크 공간 사용량
면적 기반 시각화는 수십 년 동안 존재해 왔다. 예를 들어, 모자이크 플롯(Marimekko 다이어그램으로도 알려짐)은 직사각형 타일링을 사용하여 결합 분포를 보여준다(즉, 가장 일반적으로 너비가 다른 열이 쌓인 열 차트이다). 그러나 트리맵의 주요 특징은 모든 레벨의 계층적 데이터로 확장할 수 있게 해주는 재귀적 구조이다. 이 아이디어는 1990년대 초 메릴랜드 대학교 인간-컴퓨터 상호작용 연구소의 벤 슈나이더먼 교수에 의해 발명되었다. 슈나이더먼과 그의 동료들은 트리맵을 필터링하고 조정하기 위한 다양한 상호작용 기술을 도입하여 아이디어를 심화시켰다.

이러한 초기 트리맵은 모두 단순한 "slice-and-dice" 타일링 알고리즘을 사용했다. 여러 바람직한 특성(안정적이고 순서를 유지하며 구현이 쉬움)에도 불구하고, slice-and-dice 방법은 종종 길고 가느다란 직사각형이 많은 타일링을 생성한다. 1994년 몽타즈 하스코에(Mountaz Hascoet)와 미셸 보두앵라퐁은 "squarifying" 알고리즘을 발명했고, 이후 야르케 판베이크에 의해 대중화되어 직사각형이 정사각형에 더 가까운 타일링을 만들게 되었다. 1999년 마틴 와텐버그는 "pivot and slice"라고 부르는 "squarifying" 알고리즘의 변형을 사용하여 최초의 웹 기반 트리맵인 SmartMoney Map of the Market을 만들었으며, 이는 미국 주식 시장의 수백 개 기업에 대한 데이터를 표시했다. 출시 이후 트리맵은 특히 금융 분야에서 큰 관심을 끌었다.

트리맵 혁신의 세 번째 물결은 2004년경 마르코스 웨스캄프가 뉴스 헤드라인을 표시하는 트리맵인 뉴스맵을 만든 후에 나타났다. 이 비분석적 트리맵의 예는 많은 모방자에게 영감을 주었으며 트리맵을 새롭고 광범위한 청중에게 소개했다. 최근 몇 년 동안 트리맵은 뉴욕 타임즈에서의 사용을 포함하여 주류 미디어에 진출했다.
트리맵 아트 프로젝트(Treemap Art Project)는 미국 국립 과학 아카데미를 위해 12점의 프레임 이미지를 제작하여 워싱턴 DC의 "Every AlgoRiThm has ART in It" 전시회에서 선보였고, 뉴욕 뉴욕 근대미술관 컬렉션을 위해 또 다른 세트를 제작했다.

## 같이 보기

* 디스크 공간 분석기
* 데이터 및 정보 시각화
* Marimekko 차트: 하나의 명시적 계층 레벨을 가진 유사한 개념.

## 각주

## 외부 링크

* Treemap Art Project: 워싱턴 DC의 국립 아카데미 전시를 위해 제작됨
* "Discovering Business Intelligence Using Treemap Visualizations", 벤 슈나이더먼, 2006년 4월 11일
* Comprehensive survey and bibliography 트리 시각화 기술에 대한 종합적인 설문 및 참고 문헌
* 
* History of Treemaps: 벤 슈나이더먼 작성.
* Hypermedia exploration with interactive dynamic maps: 지지(Zizi)와 보두앵라퐁의 논문으로, squarified 트리맵 레이아웃 알고리즘(당시 명칭 "improved treemap layout")을 소개함.
* 인디애나 대학교 설명
* Live interactive treemap based on crowd-sourced discounted deals: Flytail Group 제공
* Treemap sample in English: The Hive Group 제공
* Several treemap examples: Macrofocus TreeMap으로 제작된 예시들
* Visualizations using dynamic treemaps 및 online treemapping software: drasticdata 제공

분류:인포그래픽
분류:사용자 인터페이스 기술
분류:통계 차트와 다이어그램
분류:시각화
분류:트리 구조