Визуализация иерархических данных: метод древовидных карт

Введение

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

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

Алгоритмы плитки

Для создания древовидной карты необходимо определить алгоритм разбиения на области, то есть способ разделения региона на подрегионы заданной площади. В идеале, алгоритм древовидной карты должен создавать области, удовлетворяющие следующим критериям:
Небольшое соотношение сторон – в идеале, близкое к единице. Области с небольшим соотношением сторон (то есть, «плоские» объекты) легче воспринимаются. Сохранение некоторой упорядоченности входных данных. Изменение, отражающее изменения в исходных данных (высокая стабильность). Эти свойства находятся в обратной зависимости друг от друга. По мере оптимизации соотношения сторон, порядок размещения становится менее предсказуемым. По мере повышения стабильности порядка, соотношение сторон ухудшается.

Ортоконвексные деревья

В выпуклых древовидных картах (treemaps) отношение сторон не может быть постоянным – оно увеличивается с глубиной дерева. Для достижения постоянного отношения сторон используются ортоконвексные древовидные карты (treemaps), основанные на вычислениях диаграммы Вороного. Алгоритм итеративный и не предоставляет верхней границы для отношения сторон. Jigsaw Treemaps основаны на геометрии кривых, заполняющих пространство. Они предполагают, что веса являются целыми числами и что их сумма является полным квадратом. Области карты представляют собой прямоугольные многоугольники и являются сильно неортоконвексными. Гарантируется, что их отношение сторон не превышает 4. GosperMaps основаны на геометрии кривых Госпера. Они упорядочены и стабильны, но имеют очень высокое отношение сторон.

История

Областные визуализации существуют уже несколько десятилетий. Например, мозаичные графики (также известные как диаграммы Маримеко) используют прямоугольную мозаику для отображения совместных распределений (то есть, как правило, это по сути стопки столбчатых диаграмм, где столбцы имеют разную ширину). Однако ключевой особенностью древовидной карты (treemap) является рекурсивная структура, позволяющая расширять ее на иерархические данные с любым количеством уровней. Эта идея была изобретена профессором Беном Шнайдерманом в лаборатории взаимодействия человека и компьютера Университета Мэриленда в начале 1990-х годов. Шнайдерман и его коллеги затем развили эту идею, представив различные интерактивные методы фильтрации и настройки древовидных карт. Все эти ранние древовидные карты использовали простой алгоритм разбиения на части ("slice and dice"). Несмотря на множество полезных свойств (стабильность, сохранение порядка и простота реализации), метод "slice and dice" часто создает мозаику с множеством длинных и узких прямоугольников. В 1994 году Монтас Хаскоет и Мишель Бодуэн Лафон изобрели алгоритм "квадратизации", который позже популяризировал Ярке ван Вейк, создающий мозаику, прямоугольники которой были ближе к квадратам. В 1999 году Мартин Ваттенберг использовал вариант алгоритма "квадратизации", который он назвал "pivot and slice", для создания первой веб-древовидной карты – SmartMoney Map of the Market, отображающей данные о сотнях компаний на фондовом рынке США. После запуска древовидные карты вызвали всплеск интереса, особенно в финансовой сфере. Третья волна инноваций в области древовидных карт пришлась на 2004 год, когда Маркос Вескамп создал Newsmap – древовидную карту, отображающую заголовки новостей. Этот пример неаналитической древовидной карты вдохновил многих последователей и представил древовидные карты новой, широкой аудитории. В последние годы древовидные карты стали широко использоваться в основных средствах массовой информации, в том числе в New York Times. Проект Treemap Art Project создал 12 оформленных изображений для Национальных академий (США), которые были представлены на выставке Every AlgoRiThm has ART in It в Вашингтоне, округ Колумбия, и еще один набор для коллекции Музея современного искусства в Нью-Йорке.

Area based visualizations have existed for decades. For example, mosaic plots (also known as Marimekko diagrams) use rectangular tilings to show joint distributions (i. e., most commonly they are essentially stacked column plots where the columns are of different widths). The main distinguishing feature of a treemap, however, is the recursive construction that allows it to be extended to hierarchical data with any number of levels. This idea was invented by professor Ben Shneiderman at the University of Maryland Human – Computer Interaction Lab in the early 1990s. Shneiderman and his collaborators then deepened the idea by introducing a variety of interactive techniques for filtering and adjusting treemaps. These early treemaps all used the simple "slice and dice" tiling algorithm. Despite many desirable properties (it is stable, preserves ordering, and is easy to implement), the slice and dice method often produces tilings with many long, skinny rectangles. In 1994 Mountaz Hascoet and Michel Beaudouin Lafon invented a "squarifying" algorithm, later popularized by Jarke van Wijk, that created tilings whose rectangles were closer to square. In 1999 Martin Wattenberg used a variation of the "squarifying" algorithm that he called "pivot and slice" to create the first Web based treemap, the SmartMoney Map of the Market, which displayed data on hundreds of companies in the U. S. stock market. Following its launch, treemaps enjoyed a surge of interest, especially in financial contexts. A third wave of treemap innovation came around 2004, after Marcos Weskamp created the Newsmap, a treemap that displayed news headlines. This example of a non analytical treemap inspired many imitators, and introduced treemaps to a new, broad audience. In recent years, treemaps have made their way into the mainstream media, including usage by the New York Times. The Treemap Art Project produced 12 framed images for the National Academies (United States), shown the Every AlgoRiThm has ART in It exhibit in Washington, DC and another set for the collection of Museum of Modern Art in New York.