Древовидная карта - Treemapping

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

Древовидная карта Президентские выборы в США 2016 результаты во Флориде округ, на цветовой спектр от Демократичный синий к Республиканец красный

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

Главная идея

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

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

TreeSize -сгенерированная древовидная карта, визуализирующая использование места на жестком диске

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

Алгоритмы тайлинга

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

1. Маленький соотношение сторон - идеально близко к единице. Регионы с небольшим соотношением сторон (т. Е. толстые предметы ) легче воспринимаются.^[2]
2. Сохраните некоторый смысл порядка во входных данных.
3. Изменить, чтобы отразить изменения в базовых данных.

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

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

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

Алгоритмы древовидной карты^[3]

Алгоритм	порядок	Соотношения сторон	Стабильность
BinaryTree	частично заказанный	высоко	стабильный
Смешанные карты деревьев[4]	неупорядоченный	самый низкий	стабильный
Заказал и Квантовая[5]	частично заказанный	Средняя	средняя устойчивость
Нарезать и нарезать[6]	заказал	очень высоко	стабильный
В квадрате[7]	неупорядоченный[требуется дальнейшее объяснение ]	самый низкий	средняя устойчивость
Полоса[8]	заказал	Средняя	средняя устойчивость

Выпуклые карты деревьев

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

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

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

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

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

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

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

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

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

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

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

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

Карты деревьев Вороного^[12] - на основе Диаграмма Вороного расчеты. Алгоритм является итеративным и не дает верхней границы соотношения сторон.

Пазлы с деревьями^[13] - на основе геометрии кривых заполнения пространства. Они предполагают, что веса - целые числа, а их сумма - квадратное число. Регионы на карте прямолинейные многоугольники и сильно неорто-выпуклые. Их соотношение сторон гарантированно не превышает 4.

ГосперКарты^[14] - исходя из геометрии Кривые госпера. Он упорядочен и стабилен, но имеет очень высокое соотношение сторон.

История

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

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

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

Смотрите также

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

использованная литература

1. Ли, Рита Йи Ман; Чау, крыло Квонг; Цзэн, Фрэнки Фаньцзе (2019). «Рейтинг рисков для существующих и новых строительных работ». Устойчивость. 11 (10): 2863. Дои:10.3390 / su11102863.
2. Kong, N; Хеер, Дж; Агравала, М. (2010). «Рекомендации по созданию прямоугольных древовидных карт». IEEE Transactions по визуализации и компьютерной графике. 16 (6): 990–8. CiteSeerX  10.1.1.688.4140. Дои:10.1109 / TVCG.2010.186. PMID  20975136. S2CID  11597084.
3. Бен Шнейдерман; Екатерина Плезан (25 июня 2009 г.). «Древовидные карты для визуализации иерархий в ограниченном пространстве ~ Включая историю исследований древовидных карт в Университете Мэриленда». Получено 23 февраля, 2010.
4. Роэль Флиген; Эрик-Ян ван дер Линден; Ярке Й. ван Вейк. «Визуализация бизнес-данных с помощью обобщенных древовидных карт» (PDF). Архивировано из оригинал (PDF) 24 июля 2011 г.. Получено 24 февраля, 2010.
5. Бедерсон, Бенджамин Б.; Шнейдерман, Бен; Ваттенберг, Мартин (2002). «Упорядоченные и квантовые древовидные карты: эффективное использование двумерного пространства для отображения иерархий». Транзакции ACM на графике. 21 (4): 833. CiteSeerX  10.1.1.145.2634. Дои:10.1145/571647.571649. S2CID  7253456.
6. Шнейдерман, Бен (2001). «Упорядоченные макеты древовидной карты» (PDF). Infovis: 73.
7. Брюлс, Марк; Huizing, Kees; ван Вейк, Джарк Дж. (2000). "Квадратные карты деревьев". In de Leeuw, W .; ван Лиере, Р. (ред.). Визуализация данных 2000: Учеб. Совместное издание Eurographics и IEEE TCVG Symp. по визуализации (PDF). Springer-Verlag. стр. 33–42 {{несогласованные цитаты}}.
8. Бенджамин, Бедерсон; Шнейдерман, Бен; Ваттенберг, Мартин (2002). «Упорядоченные и квантовые древовидные карты: эффективное использование двумерного пространства для отображения иерархий» (PDF). Транзакции ACM на графике. 21 (4): 833–854. CiteSeerX  10.1.1.145.2634. Дои:10.1145/571647.571649. S2CID  7253456.
9. Кшиштоф Онак; Анастасиос Сидиропулос. «Круговые перегородки с приложениями к визуализации и вложениям». Получено 26 июня, 2011.
10. Марк де Берг; Онак, Кшиштоф; Сидиропулос, Анастасиос (2010). «Жирные многоугольные перегородки с приложениями для визуализации и встраивания». arXiv:1009.1866 [cs.CG ].
11. Де Берг, Марк; Спекманн, Беттина; Ван дер Виле, Винсент (2014). «Древовидные карты с ограниченным соотношением сторон». Вычислительная геометрия. 47 (6): 683. arXiv:1012.1749. Дои:10.1016 / j.comgeo.2013.12.008. S2CID  12973376.. Версия конференции: Выпуклые древовидные карты с ограниченным соотношением сторон (PDF). EuroCG. 2011 г.
12. Бальзер, Майкл; Деуссен, Оливер (2005). "Карты деревьев Вороного". В Стаско, Джон Т .; Уорд, Мэтью О. (ред.). Симпозиум IEEE по визуализации информации (InfoVis 2005), 23-25 ​​октября 2005 г., Миннеаполис, Миннесота, США (PDF). Компьютерное общество IEEE. п. 7..
13. Ваттенберг, Мартин (2005). «Заметка о визуализациях заполнения пространства и кривых заполнения пространства». В Стаско, Джон Т .; Уорд, Мэтью О. (ред.). Симпозиум IEEE по визуализации информации (InfoVis 2005), 23-25 ​​октября 2005 г., Миннеаполис, Миннесота, США (PDF). Компьютерное общество IEEE. п. 24..
14. Обер, Дэвид; Huet, Чарльз; Ламберт, Антуан; Ренуст, Бенджамин; Саллаберри, Арно; Сольнье, Агнес (2013). "Карта Госпера: Использование кривой Госпера для построения иерархических данных ". IEEE Transactions по визуализации и компьютерной графике. 19 (11): 1820–1832. Дои:10.1109 / TVCG.2013.91. PMID  24029903. S2CID  15050386..
15. Шнейдерман, Бен (1992). «Визуализация дерева с помощью древовидных карт: подход к двумерному заполнению». Транзакции ACM на графике. 11: 92–99. Дои:10.1145/102377.115768. HDL:1903/367. S2CID  1369287.
16. Кокс, Аманда; Фэрфилд, Ханна (25 февраля 2007 г.). "Состояние рынка легковых автомобилей, фургонов, внедорожников и грузовиков". Нью-Йорк Таймс. Получено 12 марта, 2010.
17. Картер, Шан; Кокс, Аманда (14 февраля 2011 г.). «Бюджетное предложение Обамы на 2012 год: как потрачено 3,7 триллиона долларов». Нью-Йорк Таймс. Получено 15 февраля, 2011.

внешние ссылки

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