Treemapping

Метод визуализации иерархических данных

В визуализации информации и вычислениях, treemapping - это метод отображения иерархических данных с использованием вложенных фигур, обычно прямоугольников.

Древовидная карта результатов президентских выборов в США 2016 во Флориде по округу, на цветовом спектре от Демократический от синего до республиканского красный Древовидная карта экспорта Сингапура по категориям продуктов, 2012 г. Древовидные карты экспорта товаров - одно из самых последних приложений такого рода визуализаций, разработанное Гарвардом -MIT Обсерватория экономической сложности.

• 1 Основная идея
• 2 Алгоритмы мозаичного изображения
  • 2.1 Прямоугольные древовидные карты
  • 2.2 Выпуклые древовидные карты
    • 2.2.1 Ортовыпуклые древовидные карты
  • 2.3 Другое карты дерева
• 3 История
• 4 См. также
• 5 Ссылки
• 6 Внешние ссылки

Карты дерева отображают иерархические (древовидные ) данные как набор вложенных прямоугольников. Каждой ветви дерева дается прямоугольник, который затем выложен меньшими прямоугольниками, представляющими подветви. Прямоугольник конечного узла имеет площадь, пропорциональную указанному измерению данных. Часто листовые узлы окрашены, чтобы показать отдельное измерение данных.

Древовидная карта предпочтений безалкогольных напитков в небольшой группе людей. Цвета и градиенты используются для группировки элементов, при этом идентифицируя отдельные элементы. TreeSize -генерированная древовидная карта, визуализирующая использование места на жестком диске

Когда размеры цвета и размера каким-то образом коррелируют с древовидной структурой, один часто можно легко увидеть узоры, которые было бы трудно обнаружить другими способами, например, является ли определенный цвет особенно актуальным. Второе преимущество древовидных карт заключается в том, что они эффективно используют пространство. В результате они могут разборчиво отображать на экране тысячи элементов одновременно.

Чтобы создать древовидную карту, необходимо определить алгоритм tiling , то есть способ разделить регион на под- регионы указанных областей. В идеале алгоритм древовидной карты должен создавать области, удовлетворяющие следующим критериям:

1. Небольшое соотношение сторон - идеально близко к единице. Области с малым соотношением сторон (т. Е. толстые объекты ) легче воспринимаются.
2. Сохранение некоторого смысла порядка во входных данных.
3. Изменение для отражения изменений в базовых данных.

К сожалению, эти свойства имеют обратную связь. По мере оптимизации соотношения сторон порядок размещения становится менее предсказуемым. По мере того, как порядок становится более стабильным, соотношение сторон ухудшается.

Прямоугольные древовидные карты

На сегодняшний день разработано шесть основных алгоритмов прямоугольных древовидных карт:

Древовидные алгоритмы

Алгоритм	Порядок	Соотношения сторон	Стабильность
BinaryTree	частично упорядоченный	высокий	стабильный
Смешанные карты дерева	неупорядоченный	низший	стабильный
упорядоченный и Quantum	частично упорядоченный	средний	средний стабильный
Slice And Dice	упорядоченный	очень высокий	стабильный
квадратичный	неупорядоченный	самый низкий	средняя стабильность
полоса	упорядоченный	средний	средняя стабильность

Выпуклые древовидные карты

Прямоугольные древовидные карты имеют тот недостаток, что в худшем случае их соотношение сторон может быть произвольно высоким. В качестве простого примера, если у корня дерева только два дочерних элемента, один с весом $1\; /\; n\; \{\backslash \; displaystyle\; 1\; /\; n\}$и один с весом $1-1\; /\; n\; \{\backslash \; displaystyle\; 1-1\; /\; n\}$, то соотношение сторон меньшего дочернего элемента будет $n\; \{\backslash \; displaystyle\; n\}$, которое может быть произвольно большим. Чтобы справиться с этой проблемой, было предложено несколько алгоритмов, которые используют области, которые обычно являются выпуклыми многоугольниками, не обязательно прямоугольными.

Выпуклые древовидные карты были разработаны в несколько шагов, каждый шаг улучшал верхнюю границу соотношения сторон. Границы задаются как функция от $n\; \{\backslash \; displaystyle\; n\}$- общего количества узлов в дереве, и $d\; \{\backslash \; displaystyle\; d\}$- общая глубина дерева.

1. Онак и Сидиропулос доказали верхнюю границу $O\; ((d\; log\; \; n)\; 17)\; \{\backslash \; displaystyle\; O\; ((d\; \backslash \; log\; \{n\})\; ^\; \{17\})\}$.

2. Де-Берг, Онак и Сидиропулос улучшают верхнюю границу до $O\; (d\; +\; log\; \; n)\; \{\backslash \; displaystyle\; O\; (d\; +\; \backslash \; log\; \{n\})\}$и доказывают нижнюю границу $О\; (d)\; \{\backslash \; displaystyle\; O\; (d)\}$.

3. Де-Берг, Спекманн и Ван-дер-Виле улучшают верхнюю границу до $O\; (d)\; \{\backslash \; displaystyle\; O\; (d)\}$, что соответствует теоретической нижней границе.

• Для особого случая, когда глубина равна 1, они представляют алгоритм, который использует только четыре класса 45-градусных многоугольников (прямоугольники, прямоугольные треугольники, прямоугольные трапеции и 45-градусные пятиугольники) и гарантирует соотношение сторон не более 34/7.

Последние два алгоритма работают в два этапа (значительно упрощены для ясности):

• A. Исходное дерево преобразуется в двоичное дерево: каждый узел с более чем двумя дочерними элементами заменяется поддеревом, в котором каждый узел имеет ровно два дочерних элемента.
• B. Каждая область, представляющая узел (начиная с корня), делится на две части с помощью линии, которая сохраняет углы между краями как можно большими. Можно доказать, что если все ребра выпуклого многоугольника разделены углом не менее $\varphi \; \{\backslash \; displaystyle\; \backslash \; phi\}$, то его соотношение сторон будет $O\; (1\; /\; \varphi )\; \{\backslash \; Displaystyle\; О\; (1\; /\; \backslash \; phi)\}$. Можно гарантировать, что в дереве глубины $d\; \{\backslash \; displaystyle\; d\}$угол делится не более чем на $d\; \{\backslash \; displaystyle\; d\}$, следовательно, гарантируется соотношение сторон.

Ортовыпуклые карты дерева

В выпуклых древовидных картах соотношение сторон не может быть постоянным - оно увеличивается с глубиной дерева. Чтобы добиться постоянного соотношения сторон изображения, можно использовать ортовыпуклые карты дерева . Здесь все регионы представляют собой ортоковыпуклые прямолинейные многоугольники с соотношением сторон не более 64; а листья представляют собой либо прямоугольники с соотношением сторон не более 8, либо L-образные или S-образные формы с соотношением сторон не более 32.

• Для особого случая, когда глубина равна 1, они представляют алгоритм, который использует только прямоугольники и L-образные формы с соотношением сторон не более $2\; +\; 2/3\; \approx \; 3,15\; \{\backslash \; displaystyle\; 2\; +\; 2\; /\; \{\backslash \; sqrt\; \{3\}\}\; \backslash \; приблизительно\; 3,15\}$; внутренние узлы используют только прямоугольники с соотношением сторон не более $1\; +\; 3\; \approx \; 2,73\; \{\backslash \; displaystyle\; 1\; +\; \{\backslash \; sqrt\; \{3\}\}\; \backslash \; приблизительно\; 2,73\}$.

Другие карты дерева

Карты дерева Вороного - на основе по диаграмме Вороного расчеты. Алгоритм является итеративным и не дает верхней границы соотношения сторон.

Jigsaw Treemaps - на основе геометрии кривых заполнения пространства. Они предполагают, что веса - целые числа, а их сумма - квадратное число. Области карты - это прямолинейные многоугольники и сильно неортвыпуклые. Их соотношение сторон гарантированно не превышает 4.

GosperMaps - на основе геометрии кривых Gosper. Он упорядочен и стабилен, но имеет очень высокое соотношение сторон.

Зональные визуализации существовали десятилетиями. Например, на мозаичных графиках (также известных как диаграммы Маримекко) используются прямоугольные мозаики для отображения совместных распределений (т.е. чаще всего они представляют собой по существу составленные столбцы графиков, в которых столбцы имеют разную ширину). Однако главной отличительной особенностью древовидной карты является рекурсивная конструкция, которая позволяет расширить ее до иерархических данных с любым количеством уровней. Эта идея была изобретена профессором Беном Шнейдерманом из лаборатории взаимодействия человека с компьютером Мэрилендского университета в начале 1990-х годов. Затем Шнейдерман и его сотрудники углубили идею, представив различные интерактивные методы фильтрации и настройки древовидных карт.

Во всех этих ранних древовидных картах использовался простой алгоритм мозаики «срезы и кости». Несмотря на многие желательные свойства (он стабилен, сохраняет порядок и прост в реализации), метод нарезки и кости часто дает мозаику с большим количеством длинных тонких прямоугольников. В 1994 году Маунтас Хаскоет и Мишель Бодуэн-Лафон изобрели алгоритм «квадратификации», который впоследствии популяризировал Ярке ван Вейк, который создавал мозаики, прямоугольники которых были ближе к квадрату. В 1999 году Мартин Ваттенберг использовал вариант алгоритма «разбиения на квадраты», который он назвал «поворот и срез», чтобы создать первую древовидную карту на базе Интернета, SmartMoney Map of the Market, которая отображала данные по сотням компаний. на фондовом рынке США. После запуска древовидные карты вызвали всплеск интереса, особенно в финансовом контексте.

Третья волна инноваций в древовидных картах пришла примерно в 2004 году после создания древовидной карты, на которой отображались заголовки новостей. Этот пример неаналитической древовидной карты вдохновил многих подражателей и представил древовидные карты новой широкой аудитории. В последние годы древовидные карты стали использоваться в основных средствах массовой информации, в том числе в New York Times. В рамках проекта Treemap Art Project было создано 12 изображений в рамке для Национальных академий (США), показаны На каждой выставке AlgoRiThm есть АРТ в Вашингтоне, округ Колумбия, и на другой набор для коллекции Музея современного искусства в Нью-Йорке.

• Анализатор дискового пространства
• Визуализация информации
• Список стран по экономической сложности, который включает список древовидных карт экспорта товаров.
• Диаграмма Marimekko, аналогичная концепция с одним уровнем явной иерархии.

На Викискладе есть медиафайлы, связанные с Treemaps.

• Treemap Art Project, созданной для национальных академий в Вашингтоне, округ Колумбия
• Статья Бена Шнейдермана об использовании карт деревьев (в качестве гостя на www.perceptualedge.com [1] )
• Всесторонний обзор и библиография методов визуализации деревьев
• Обобщенные древовидные карты
• История древовидных карт Бена Шнейдермана.
• Исследование гипермедиа с интерактивными динамическими картами Статья Зизи и Бодуэна-Лафона, представляющая алгоритм раскладки квадратной карты дерева (названный «улучшенная компоновка карты дерева» в то время).
• Университет Индианы описание
• Интерактивная древовидная карта в реальном времени, основанная на коллективных скидках d относится к из
• Образец карты дерева на английском языке из The Hive Group
• Несколько примеров карты дерева, созданных с помощью
• Визуализации с использованием динамических карт дерева и программного обеспечения для создания карт дерева by drasticdata
• Древовидные карты экспорта товаров, разработанные Обсерваторией экономической сложности Гарвардского технологического института
• newsmap.jp - древовидная карта новостей Google