Картографирование деревьев

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

Древовидная карта экспорта Сингапура по категориям продукции, 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.

GosperMaps

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

История

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

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

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

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

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

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

Ссылки

1. Ли, Рита Йи Ман; Чау, Квонг Винг; Цзэн, Фрэнки Фаньцзе (2019). «Ранжирование рисков для существующих и новых строительных работ». Устойчивость . 11 (10): 2863. doi : 10.3390/su11102863 .
2. Kong, N; Heer, J; Agrawala, M (2010). «Перцептивные рекомендации по созданию прямоугольных древовидных карт». Труды IEEE по визуализации и компьютерной графике . 16 (6): 990–8. CiteSeerX 10.1.1.688.4140 . doi :10.1109/TVCG.2010.186. PMID  20975136. S2CID  11597084. 
3. Вернье, Э.; Зондаг, М.; Комба, Дж.; Спекманн, Б.; Телеа, А.; Вербек, К. (2020). «Количественное сравнение зависящих от времени древовидных карт». Computer Graphics Forum . 39 (3): 393–404. arXiv : 1906.06014 . doi :10.1111/cgf.13989. S2CID  189898065.
4. Шнейдерман, Бен (2001). "Упорядоченные макеты древовидных карт" (PDF) . Infovis : 73.
5. Бенджамин, Бедерсон; Шнейдерман, Бен; Ваттенберг, Мартин (2002). «Упорядоченные и квантовые древовидные карты: эффективное использование двумерного пространства для отображения иерархий» (PDF) . ACM Transactions on Graphics . 21 (4): 833–854. CiteSeerX 10.1.1.145.2634 . doi :10.1145/571647.571649. S2CID  7253456. 
6. Шнейдерман, Бен; Ваттенберг, Мартин (2001). «Упорядоченные макеты древовидных карт». Симпозиум IEEE по визуализации информации : 73–78.
7. Энгдаль, Бьёрн. Упорядоченные и квантовые древовидные карты: эффективное использование двумерного пространства для отображения иерархий .
8. Tu, Y.; Shen, H. (2007). «Визуализация изменений иерархических данных с использованием древовидных карт» (PDF) . IEEE Transactions on Visualization and Computer Graphics . 13 (6): 1286–1293. doi :10.1109/TVCG.2007.70529. PMID  17968076. S2CID 14206074 . Архивировано (PDF) из оригинала 8 августа 2022 г. 
9. Tak, S.; Cockburn, A. (2013). «Повышенная пространственная устойчивость с помощью древовидных карт Гильберта и Мура» (PDF) . IEEE Transactions on Visualization and Computer Graphics . 19 (1): 141–148. doi :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. doi : 10.1016/j.dam.2006.08.005 .
13. Вернье, Э.; Комба, Дж.; Телеа, А. (2018). «Количественное сравнение динамических древовидных карт для визуализации эволюции программного обеспечения». Конференция по визуализации программного обеспечения : 99–106.
14. Sondag, M.; Speckmann, B.; Verbeek, K. (2018). «Стабильные древовидные карты с помощью локальных перемещений». IEEE Transactions on Visualization and Computer Graphics . 24 (1): 729–738. doi :10.1109/TVCG.2017.2745140. PMID  28866573. S2CID  27739774.
15. Кшиштоф Онак; Анастасиос Сидиропулос. "Круговые разбиения с приложениями к визуализации и вложениям" . Получено 26 июня 2011 г.
16. Марк де Берг; Онак, Кшиштоф; Сидиропулос, Анастасиос (2013). «Толстые многоугольные разбиения с приложениями к визуализации и вложениям». Журнал вычислительной геометрии . 4 (1): 212–239. arXiv : 1009.1866 .
17. De Berg, Mark; Speckmann, Bettina ; Van Der Weele, Vincent (2014). «Древовидные карты с ограниченным соотношением сторон». Computational Geometry . 47 (6): 683. arXiv : 1012.1749 . doi : 10.1016/j.comgeo.2013.12.008 . S2CID  12973376.. Версия конференции: Выпуклые древовидные карты с ограниченным соотношением сторон (PDF) . EuroCG. 2011.
18. Balzer, Michael; Deussen, Oliver (2005). "Voronoi Treemaps". В Stasko, John T.; Ward, Matthew O. (ред.). IEEE Symposium on Information Visualization (InfoVis 2005), 23-25 ​​октября 2005 г., Миннеаполис, MN, США (PDF) . IEEE Computer Society. стр. 7..
19. Ваттенберг, Мартин (2005). «Заметка о визуализациях, заполняющих пространство, и кривых, заполняющих пространство». В Stasko, Джон Т.; Уорд, Мэтью О. (ред.). Симпозиум IEEE по визуализации информации (InfoVis 2005), 23–25 октября 2005 г., Миннеаполис, Миннесота, США (PDF) . IEEE Computer Society. стр. 24..
20. Обер, Дэвид; Юэ, Чарльз; Ламберт, Антуан; Реноу, Бенджамин; Саллаберри, Арно; Солнье, Агнес (2013). «Карта Госпера: использование кривой Госпера для размещения иерархических данных». Транзакции IEEE по визуализации и компьютерной графике . 19 (11): 1820–1832. дои : 10.1109/TVCG.2013.91. PMID  24029903. S2CID  15050386..
21. Шнейдерман, Бен (1992). «Визуализация дерева с помощью древовидных карт: подход с двумерным заполнением пространства». ACM Transactions on Graphics . 11 : 92–99. doi : 10.1145/102377.115768. hdl : 1903/367 . S2CID  1369287.
22. Бен Шнейдерман ; Кэтрин Плезант (25 июня 2009 г.). «Древовидные карты для визуализации иерархий в ограниченном пространстве ~ Включая историю исследований древовидных карт в Мэрилендском университете» . Получено 23 февраля 2010 г.
23. Кокс, Аманда; Фэрфилд, Ханна (25 февраля 2007 г.). «Состояние рынка автомобилей, фургонов, внедорожников и грузовиков». The New York Times . Получено 12 марта 2010 г.
24. Картер, Шан; Кокс, Аманда (14 февраля 2011 г.). «Предложение Обамы по бюджету на 2012 год: как тратятся 3,7 триллиона долларов». The New York Times . Получено 15 февраля 2011 г.
25. "Treemap Art". Архивировано из оригинала 5 декабря 2023 г.
26. "В каждом AlgoRiThm есть ART: Treemap Art Project". CPNAS . Архивировано из оригинала 8 октября 2023 г.

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

• Проект Treemap Art Project подготовил выставку для Национальной академии в Вашингтоне, округ Колумбия.
• «Открытие бизнес-аналитики с использованием визуализаций древовидных карт», Бен Шнейдерман , 11 апреля 2006 г.
• Комплексный обзор и библиография методов визуализации деревьев
• Vliegen, Roel; van Wijk, Jarke J.; van der Linden, Erik-Jan (сентябрь–октябрь 2006 г.). «Визуализация бизнес-данных с помощью обобщенных древовидных карт» (PDF) . IEEE Transactions on Visualization and Computer Graphics . 12 (5): 789–796. doi :10.1109/TVCG.2006.200. PMID  17080801. S2CID  18891326. Архивировано из оригинала (PDF) 24 июля 2011 г.
• История древовидных карт Бена Шнейдермана.
• Исследование гипермедиа с помощью интерактивных динамических карт. Статья Зизи и Бодуэна-Лафона, в которой представлен алгоритм компоновки квадратной древовидной карты (в то время называвшийся «улучшенной компоновкой древовидной карты»).
• Описание Университета Индианы
• Живая интерактивная древовидная карта, основанная на краудсорсинговых скидках от Flytail Group
• Пример древовидной карты на английском языке от The Hive Group
• Несколько примеров древовидных карт, созданных с помощью Macrofocus TreeMap
• Визуализации с использованием динамических древовидных карт и программного обеспечения для онлайн-картирования деревьев от drasticdata