Древовидные структуры: treemap и dendrogramm

Иерархические данные представляют собой один из наиболее естественных способов структурирования информации: каталоги файлов, организационные схемы, классификации, биологические таксономии. В визуализации такие структуры требуют специальных алгоритмов раскладки, поскольку стандартные координатные системы не отражают отношения «родитель–потомок».

В Vega и Vega-Lite для работы с иерархиями применяются два базовых подхода: представление через плоский список с последующей реконструкцией дерева (stratify), либо использование уже вложенной структуры данных. Дальнейшая визуализация строится через специализированные трансформации и layout-алгоритмы: treemap, pack, tree, cluster.

Для построения древовидных визуализаций используется два основных формата:

1. Плоская структура (edge list) Каждая запись содержит идентификатор и ссылку на родителя:

[
  {"id": "A", "parent": null, "value": 10},
  {"id": "B", "parent": "A", "value": 5},
  {"id": "C", "parent": "A", "value": 8},
  {"id": "D", "parent": "B", "value": 2}
]

2. Вложенная структура (tree object)

{
  "name": "A",
  "children": [
    {
      "name": "B",
      "children": [
        {"name": "D", "value": 2}
      ]
    },
    {
      "name": "C",
      "value": 8
    }
  ]
}

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

Построение иерархии через stratify

Трансформация stratify преобразует плоский список в дерево:

{
  "data": {
    "values": [
      {"id": "A", "parent": null, "value": 10},
      {"id": "B", "parent": "A", "value": 5},
      {"id": "C", "parent": "A", "value": 8},
      {"id": "D", "parent": "B", "value": 2}
    ]
  },
  "transform": [
    {
      "type": "stratify",
      "key": "id",
      "parentKey": "parent"
    }
  ]
}

После этого данные становятся иерархическим деревом, пригодным для дальнейших layout-операций.

Treemap: плотная упаковка иерархии

Treemap отображает дерево через вложенные прямоугольники, где площадь каждого элемента пропорциональна значению.

Основные характеристики treemap

Ключевая идея:

  • каждый узел представлен прямоугольником
  • дочерние элементы делят пространство родителя
  • площадь = значение метрики
  • глубина иерархии кодируется вложенностью

Алгоритмы раскладки

Vega использует алгоритмы:

  • squarify — минимизация вытянутости прямоугольников
  • binary — рекурсивное деление
  • slice / dice — последовательное разбиение по осям

Treemap в Vega

В Vega treemap реализуется через трансформацию treemap:

{
  "data": {
    "values": [
      {"id": "root", "parent": null, "value": 0},
      {"id": "A", "parent": "root", "value": 10},
      {"id": "B", "parent": "root", "value": 20},
      {"id": "C", "parent": "A", "value": 5},
      {"id": "D", "parent": "A", "value": 5}
    ]
  },
  "transform": [
    {
      "type": "stratify",
      "key": "id",
      "parentKey": "parent"
    },
    {
      "type": "treemap",
      "field": "value",
      "size": [{"signal": "width"}, {"signal": "height"}],
      "method": "squarify"
    }
  ],
  "mark": "rect",
  "encoding": {
    "x": {"field": "x0"},
    "x2": {"field": "x1"},
    "y": {"field": "y0"},
    "y2": {"field": "y1"},
    "color": {"field": "depth", "type": "ordinal"}
  }
}

Важные поля результата treemap

После трансформации каждый узел получает координаты:

  • x0, y0 — верхний левый угол
  • x1, y1 — нижний правый угол
  • depth — уровень вложенности
  • children — вложенные элементы

Особенности масштабирования treemap

Treemap эффективен при:

  • большом количестве элементов
  • необходимости показать доли целого
  • ограниченном пространстве

Ограничения:

  • теряется точная структура ветвления
  • глубина визуально менее читаема
  • сравнение узлов одной ветки затруднено

Vega-Lite и treemap

Vega-Lite не всегда требует ручной работы с layout-трансформациями, но поддерживает иерархии через hierarchical преобразования (в зависимости от версии).

Пример treemap в Vega-Lite:

{
  "$schema": "https://vega.github.io/schema/vega-lite/v5.json",
  "data": {
    "values": [
      {"id": "A", "parent": null, "value": 10},
      {"id": "B", "parent": "A", "value": 5},
      {"id": "C", "parent": "A", "value": 8}
    ]
  },
  "transform": [
    {
      "type": "stratify",
      "key": "id",
      "parentKey": "parent"
    },
    {
      "type": "treemap",
      "field": "value",
      "method": "squarify",
      "size": [{"signal": "width"}, {"signal": "height"}]
    }
  ],
  "mark": "rect",
  "encoding": {
    "x": {"field": "x0"},
    "x2": {"field": "x1"},
    "y": {"field": "y0"},
    "y2": {"field": "y1"},
    "color": {"field": "depth"}
  }
}

Dendrogram: визуализация структуры дерева

Dendrogram (дендрограмма) отображает иерархию в виде графа с узлами и связями. В отличие от treemap, здесь сохраняется структура ветвления.

Основные свойства

  • узлы соединяются линиями (links)

  • положение определяется алгоритмом tree layout

  • расстояния кодируют глубину

  • форма может быть:

    • вертикальная (top-down)
    • горизонтальная (left-right)
    • радиальная

Tree layout в Vega

В Vega используется трансформация tree:

{
  "data": {
    "values": [
      {"id": "A", "parent": null},
      {"id": "B", "parent": "A"},
      {"id": "C", "parent": "A"},
      {"id": "D", "parent": "B"}
    ]
  },
  "transform": [
    {
      "type": "stratify",
      "key": "id",
      "parentKey": "parent"
    },
    {
      "type": "tree",
      "method": "tidy",
      "size": [{"signal": "height"}, {"signal": "width"}],
      "separation": true
    }
  ]
}

Отрисовка узлов и связей

После применения tree каждый узел получает координаты x, y. Для связей используется генерация линий:

{
  "mark": "rule",
  "encoding": {
    "x": {"field": "parent.x"},
    "y": {"field": "parent.y"},
    "x2": {"field": "x"},
    "y2": {"field": "y"}
  }
}

Узлы:

{
  "mark": "circle",
  "encoding": {
    "x": {"field": "x"},
    "y": {"field": "y"},
    "size": {"value": 100},
    "color": {"field": "depth"}
  }
}

Радиальная дендрограмма

Радиальная версия tree layout преобразует декартовы координаты в полярные:

  • угол = функция позиции по горизонтали
  • радиус = глубина узла

Пример преобразования:

{
  "transform": [
    {
      "type": "formula",
      "as": "angle",
      "expr": "datum.x / 200 * PI * 2"
    },
    {
      "type": "formula",
      "as": "radius",
      "expr": "datum.y"
    },
    {
      "type": "formula",
      "as": "x",
      "expr": "cos(datum.angle) * datum.radius"
    },
    {
      "type": "formula",
      "as": "y",
      "expr": "sin(datum.angle) * datum.radius"
    }
  ]
}

Сравнение treemap и dendrogram

Treemap:

  • оптимален для плотного отображения значений
  • хорошо показывает доли
  • плохо отображает структуру связей

Dendrogram:

  • сохраняет структуру дерева
  • удобен для анализа иерархии
  • требует больше пространства

Комбинированные подходы

Vega позволяет строить гибридные визуализации:

  • treemap + tooltip с путём узла
  • dendrogram + окраска по агрегированному значению
  • кластеризация перед построением дерева

Агрегация данных в иерархиях

Для treemap и dendrogram часто используется агрегация:

{
  "type": "aggregate",
  "groupby": ["parent"],
  "ops": ["sum"],
  "fields": ["value"],
  "as": ["total"]
}

Иерархические алгоритмы опираются на агрегированные значения для определения размеров узлов.

Производительность и ограничения

При работе с большими деревьями возникают проблемы:

  • экспоненциальный рост числа узлов визуализации
  • высокая стоимость рекурсивных layout-алгоритмов
  • необходимость предварительной агрегации

Оптимизация достигается через:

  • сокращение глубины
  • фильтрацию ветвей
  • предварительное вычисление агрегатов на сервере

Практическая модель выбора визуализации

  • treemap применяется при анализе распределений
  • dendrogram применяется при анализе структуры
  • tree layout используется для навигационных иерархий
  • cluster layout используется для группировки схожих элементов

Внутренняя модель Vega для иерархий

В Vega иерархия представляет собой расширенный граф:

  • nodes: элементы данных
  • links: связи parent-child
  • layout: функция отображения пространства
  • value propagation: вычисление агрегатов вверх по дереву

Эта модель позволяет унифицировать treemap, tree и pack в одной системе трансформаций.

Оглавление