Древовидное отображение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Онак и Сидиропулос ^[15] доказали верхнюю оценку . ${\displaystyle O((d\log {n})^{17})}$
2. Де-Берг, Онак и Сидиропулос ^[16] улучшают верхнюю оценку и доказывают нижнюю оценку . ${\displaystyle O(d+\log {n})}$ ${\displaystyle O(d)}$
3. Де-Берг, Спекманн и ван-дер-Вил ^[17] улучшают верхнюю границу до , совпадая с теоретической нижней границей. (Для особого случая, когда глубина равна 1, они представляют алгоритм, который использует только четыре класса многоугольников с углом 45 градусов (прямоугольники, прямоугольные треугольники, прямоугольные трапеции и пятиугольники с углом 45 градусов) и гарантирует соотношение сторон максимум 34/7.) ${\displaystyle O(d)}$

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

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

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

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

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

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

Древовидные карты Вороного

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

Древовидные карты-головоломки ^[19]

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

ГосперКарты

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

История

Использование пространства на жестком диске визуализируется в TreeSize , программном обеспечении, впервые выпущенном в 1996 году.

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

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

Третья волна инноваций в виде древовидных карт пришла примерно в 2004 году, после того как Маркос Вескамп создал Newsmap — древовидную карту, на которой отображались заголовки новостей. Этот пример неаналитической древовидной карты вдохновил многих подражателей и представил древовидные карты новой, широкой аудитории. ^{[ нужна цитата ]} В последние годы древовидные карты стали использоваться в основных средствах массовой информации, в том числе в газете New York Times. ^{[23] [24]} Проект Treemap Art Project ^[25] подготовил 12 изображений в рамках для Национальных академий (США) , продемонстрировал выставку «В каждом алгоритме есть ИСКУССТВО» ^[26] в Вашингтоне, округ Колумбия, и еще один набор для коллекции Музея. современного искусства в Нью-Йорке.

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

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

Рекомендации

1. Ли, Рита И Ман; Чау, Квонг Винг; Цзэн, Фрэнки Фанджи (2019). «Рейтинг рисков для существующих и новых строительных работ». Устойчивость . 11 (10): 2863. дои : 10.3390/su11102863 .
2. Конг, Н; Хир, Дж; Агравала, М. (2010). «Перцептивные рекомендации по созданию прямоугольных древовидных карт». Транзакции IEEE по визуализации и компьютерной графике . 16 (6): 990–8. CiteSeerX 10.1.1.688.4140 . дои :10.1109/TVCG.2010.186. PMID  20975136. S2CID  11597084. 
3. Вернье, Э.; Сондаг, М.; Комба, Дж.; Шпекманн, Б.; Телея, А.; Вербек, К. (2020). «Количественное сравнение зависящих от времени древовидных карт». Форум компьютерной графики . 39 (3): 393–404. arXiv : 1906.06014 . дои : 10.1111/cgf.13989. S2CID  189898065.
4. Шнейдерман, Бен (2001). «Упорядоченные макеты древовидных карт» (PDF) . Инфовис : 73.
5. Бенджамин, Бедерсон; Шнейдерман, Бен; Ваттенберг, Мартин (2002). «Упорядоченные и квантовые древовидные карты: эффективное использование двумерного пространства для отображения иерархий» (PDF) . Транзакции ACM с графикой . 21 (4): 833–854. CiteSeerX 10.1.1.145.2634 . дои : 10.1145/571647.571649. S2CID  7253456. 
6. Шнейдерман, Бен; Ваттенберг, Мартин (2001). «Упорядоченные макеты древовидных карт». Симпозиум IEEE по визуализации информации : 73–78.
7. Энгдаль, Бьорн. Упорядоченные и квантовые древовидные карты: эффективное использование двумерного пространства для отображения иерархий .
8. Ту, Ю.; Шен, Х. (2007). «Визуализация изменений иерархических данных с помощью древовидных карт» (PDF) . Транзакции IEEE по визуализации и компьютерной графике . 13 (6): 1286–1293. дои : 10.1109/TVCG.2007.70529. PMID  17968076. S2CID 14206074 . Архивировано (PDF) из оригинала 8 августа 2022 г. 
9. Так, С.; Кокберн, А. (2013). «Повышенная пространственная стабильность с помощью древовидных карт Гильберта и Мура» (PDF) . Транзакции IEEE по визуализации и компьютерной графике . 19 (1): 141–148. дои :10.1109/TVCG.2012.108. PMID  22508907. S2CID  6099935.
10. Брюльс, Марк; Хейзинг, Кес; ван Вейк, Ярке Дж. (2000). «Квадратные древовидные карты». Ин де Леу, В.; ван Лиер, Р. (ред.). Визуализация данных 2000: Учеб. Совместный симпозиум Eurographics и IEEE TCVG. по визуализации (PDF) . Спрингер-Верлаг. стр. 33–42..
11. Роэль Влиген; Эрик-Ян ван дер Линден; Ярке Дж. ван Вейк . «Визуализация бизнес-данных с помощью обобщенных древовидных карт» (PDF) . Архивировано из оригинала (PDF) 24 июля 2011 года . Проверено 24 февраля 2010 г.
12. Нагамоти, Х.; Абэ, Ю.; Ваттенберг, Мартин (2007). «Аппроксимационный алгоритм разделения прямоугольника на прямоугольники с заданными площадями». Дискретная прикладная математика . 155 (4): 523–537. дои : 10.1016/j.dam.2006.08.005 .
13. Вернье, Э.; Комба, Дж.; Телеа, А. (2018). «Количественное сравнение динамических древовидных карт для визуализации эволюции программного обеспечения». Конференция по визуализации программного обеспечения : 99–106.
14. Сондаг, М.; Шпекманн, Б.; Вербек, К. (2018). «Стабильные древовидные карты посредством локальных перемещений». Транзакции IEEE по визуализации и компьютерной графике . 24 (1): 729–738. дои : 10.1109/TVCG.2017.2745140. PMID  28866573. S2CID  27739774.
15. Кшиштоф Онак; Анастасиос Сидиропулос. «Круговые разделы с приложениями к визуализации и встраиваниям» . Проверено 26 июня 2011 г.
16. Марк де Берг; Онак, Кшиштоф; Сидиропулос, Анастасиос (2013). «Толстые многоугольные разбиения с применением к визуализации и встраиваниям». Журнал вычислительной геометрии . 4 (1): 212–239. arXiv : 1009.1866 .
17. Де Берг, Марк; Шпекманн, Беттина ; Ван дер Вил, Винсент (2014). «Древовидные карты с ограниченным соотношением сторон». Вычислительная геометрия . 47 (6): 683. arXiv : 1012.1749 . дои : 10.1016/j.comgeo.2013.12.008 . S2CID  12973376.. Версия конференции: Выпуклые древовидные карты с ограниченным соотношением сторон (PDF) . ЕвроКГ. 2011.
18. Бальцер, Майкл; Дойссен, Оливер (2005). «Древовидные карты Вороного». В Стаско, Джон Т.; Уорд, Мэтью О. (ред.). Симпозиум IEEE по визуализации информации (InfoVis 2005), 23–25 октября 2005 г., Миннеаполис, Миннесота, США (PDF) . Компьютерное общество IEEE. п. 7..
19. Ваттенберг, Мартин (2005). «Заметка о визуализациях, заполняющих пространство, и кривых заполнения пространства». В Стаско, Джон Т.; Уорд, Мэтью О. (ред.). Симпозиум IEEE по визуализации информации (InfoVis 2005), 23–25 октября 2005 г., Миннеаполис, Миннесота, США (PDF) . Компьютерное общество IEEE. п. 24..
20. Обер, Дэвид; Юэ, Чарльз; Ламберт, Антуан; Реноу, Бенджамин; Саллаберри, Арно; Солнье, Агнес (2013). «Карта Госпера: использование кривой Госпера для размещения иерархических данных». Транзакции IEEE по визуализации и компьютерной графике . 19 (11): 1820–1832. дои : 10.1109/TVCG.2013.91. PMID  24029903. S2CID  15050386..
21. Шнейдерман, Бен (1992). «Визуализация дерева с помощью древовидных карт: подход к двухмерному заполнению пространства». Транзакции ACM с графикой . 11 : 92–99. дои : 10.1145/102377.115768. HDL : 1903/367 . S2CID  1369287.
22. Бен Шнейдерман ; Кэтрин Плезант (25 июня 2009 г.). «Древовидные карты для визуализации иерархий в ограниченном пространстве ~ включая историю исследований древовидных карт в Университете Мэриленда» . Проверено 23 февраля 2010 г.
23. Кокс, Аманда; Фэрфилд, Ханна (25 февраля 2007 г.). «Здоровье рынка легковых автомобилей, фургонов, внедорожников и грузовиков». Нью-Йорк Таймс . Проверено 12 марта 2010 г.
24. Картер, Шан; Кокс, Аманда (14 февраля 2011 г.). «Бюджетное предложение Обамы на 2012 год: как потрачено 3,7 триллиона долларов». Нью-Йорк Таймс . Проверено 15 февраля 2011 г.
25. "Искусство древовидной карты" . Архивировано из оригинала 5 декабря 2023 года.
26. «В каждом алгоритме есть ИСКУССТВО: Художественный проект древовидной карты» . КПНАС . Архивировано из оригинала 8 октября 2023 года.

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

• Treemap Art Project подготовил выставку для Национальных академий в Вашингтоне, округ Колумбия.
• «Обнаружение бизнес-аналитики с помощью визуализации древовидных карт», Бен Шнейдерман , 11 апреля 2006 г.
• Комплексный обзор и библиография методов визуализации дерева.
• Влиген, Роэль; ван Вейк, Ярке Дж.; ван дер Линден, Эрик-Ян (сентябрь – октябрь 2006 г.). «Визуализация бизнес-данных с помощью обобщенных древовидных карт» (PDF) . Транзакции IEEE по визуализации и компьютерной графике . 12 (5): 789–796. дои :10.1109/TVCG.2006.200. PMID  17080801. S2CID  18891326. Архивировано из оригинала (PDF) 24 июля 2011 года.
• История древовидных карт Бена Шнейдермана.
• Исследование гипермедиа с помощью интерактивных динамических карт. Статья Зизи и Бодуэн-Лафона, представляющая алгоритм компоновки квадратной древовидной карты (в то время называвшийся «улучшенной компоновкой древовидной карты»).
• Описание Университета Индианы
• Живая интерактивная древовидная карта, основанная на краудсорсинговых скидках от Flytail Group.
• Образец древовидной карты на английском языке от The Hive Group
• Несколько примеров древовидных карт, созданных с помощью Macrofocus TreeMap.
• Визуализация с использованием динамических древовидных карт и онлайн-программы для создания древовидных карт от Drasticdata.