Набор подходов для суммирования сложных деревьев в более легко представляемую и удобочитаемую форму.

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

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

Это очень распространенный сценарий.

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

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

В этой статье я:

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

Как всегда, код доступен по запросу.

Пример данных

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

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

Почему данные примера должны быть скучными? Что ж, если данные интересны, у нас возникнет соблазн использовать наши знания о значении данных для упрощения дерева, тогда как при чисто алгоритмическом подходе мы не можем этого сделать.

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

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

Простые алгоритмы

Во-первых, я хотел бы рассмотреть некоторые из более простых, но все же полезных алгоритмов, которые мы можем использовать.

Алгоритмы фильтрации узлов

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

Это вообще не очень полезно. Он теряет много важной структуры; тот факт, что парковки, по-видимому, разделены на три города: Фрамли, Уиктон и Олдерли, утерян, и, что еще хуже, исчезли целые категории доходов без предупреждения лица, принимающего решения, о том, что они когда-либо существовали. Возможно, если мы установим более щедрый порог и удалим только очень маленькие узлы, результат будет лучше.

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

Алгоритмы фильтрации узлов полезны при упрощении очень большого графа (см. пример в этой статье), но они не обязательно подходят для визуального суммирования (сравнительно) небольшого дерева.

Алгоритмы ограничения глубины

Другой базовый подход к упрощению дерева заключается в уменьшении глубины дерева, чтобы ни один узел не мог быть удален от корня более чем на n узлов. Теоретически мы ожидаем, что это часто будет давать довольно хорошие результаты, потому что оно должно сохранять узлы, представляющие большие скопления данных, и удалять их менее важные потомки. Давайте попробуем ограничить глубину до 5 узлов.

Это не так ужасно, как простой алгоритм фильтрации узлов, но у него есть серьезные недостатки. Во-первых, он сжимает дерево так, что все его аспекты имеют одинаковую глубину, скрывая тот факт, что некоторые виды доходов от парковки более сложны, чем другие. Другая проблема заключается в том, что это создает иллюзию того, что «Framley» в некотором роде является тем же «видом» узла, что и «выдающийся», представляя их обоих как конечные узлы. Он также сохраняет много деталей в разделе «Fines», просто потому, что «Fines» уже имеет много узлов на глубине 5.

Обратите внимание, что есть несколько менее наивных способов ограничить глубину дерева; два популярных:

  • Удаление листьев: удаление всех конечных узлов. Повторяйте до тех пор, пока максимальная глубина не станет желаемой. Это лучше сохраняет часть формы дерева.
  • Ограничение глубины снизу вверх: ограничивайте глубину, удаляя узлы рядом с корнем, а не удаляя узлы далеко от корня. Этот подход довольно сложен, но дает хорошие результаты для определенных случаев использования.

Алгоритмы ограничения ширины

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

  1. рассчитать максимальное количество узлов, которые могут существовать на определенной глубине
  2. на каждой глубине удаляйте, перемещайте или объединяйте одноуровневые узлы до тех пор, пока этот максимум больше не будет превышен

Например, давайте попробуем подход с ограничением ширины, при котором одноуровневые узлы, представляющие меньший доход, объединяются в узел «Другое» до тех пор, пока ни один из узлов не будет иметь более двух одноуровневых узлов.

Это работало намного лучше, чем подходы с фильтрацией и ограничением глубины! Впервые кое-что из формы дерева было сохранено (не говоря уже о том, что визуальный интервал не очень хорош — это просто проблема макета). Возможно, результат был бы еще лучше, если бы мы установили более жесткие параметры, заставив больше узлов объединяться в «Другое».

Ладно, не суть. Но алгоритм ограничения широты с умеренными настройками, безусловно, был эффективен.

Алгоритмы сохранения топологии

При упрощении любого графа можно сохранить общую топологию графа, удалив любые узлы порядка 2, то есть узлы, имеющие ровно 2 соединения. Это всего лишь один из алгоритмов упрощения с сохранением топологии, но очень мощный. Применительно к деревьям все сводится к удалению всех узлов, имеющих ровно 1 дочерний узел, сохранению дочернего узла и присоединению его к прародителю.

Это называется «удаление синглтона», это очень простой и широко используемый алгоритм, и в нашем случае результат таков:

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

Алгоритмы стекирования

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

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

Это не идеально, но намного лучше, чем то, что каждый из подходов создал сам по себе. Некоторые алгоритмы (такие как удаление одиночных элементов) очень часто лучше выполнять в качестве последнего шага; некоторые лучше работают в качестве первого шага.

Сложные алгоритмы

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

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

Что такое грамматическая индукция?

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

Если это не кажется вам полезным, учтите, что вы делаете это, когда сжимаете файл; алгоритм вашей программы сжатия генерирует грамматику (в каком-то смысле), которую затем можно применить к некоторому небольшому количеству исходных данных для воссоздания исходного файла.

Грамматическая индукция также имеет много других применений. Грамматику можно интерпретировать как каталог важных (то есть часто повторяющихся) частей ввода; это может позволить нам различать более случайные или более повторяющиеся области данных в больших неструктурированных наборах данных, которые широко используются в криминалистике, телекоммуникациях и вооруженных силах.

Индукция грамматики по последовательным данным: LZW

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

Индукция грамматики по данным произвольного доступа: Sequitur

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

Грамматическая индукция по дереву

Однако в нашем случае мы начнемс дерева, поэтому большая часть работы, которую делает Sequitur, бесполезна для нас. Фактически, начав с дерева, мы получили грамматику на тарелке; это просто не очень полезная грамматика, поскольку дерево грамматики имеет один узел для каждого узла в исходном дереве. Но мы можем обработать эту грамматику несколькими способами, чтобы сократить грамматику, создав таким образом более простое дерево, обладающее многими свойствами исходного дерева. Одна вещь, которую мы можем сделать, — это определить важные узлы в этой грамматике, узлы, которые применялись бы чаще всего, если бы мы действительно использовали грамматику для воспроизведения исходного дерева. Для этого мы будем использовать алгоритм такой формы:

  1. Определите функцию «сводка по поддереву», входом которой является поддерево, а выходом — сводка — элемент данных, который можно сравнивать и который представляет структуру поддерева.
  2. Примените эту функцию к каждому узлу в дереве.
  3. Изучите дерево и сравните сводки поддерева с помощью функции «сопоставление поддерева». Определите узлы, чьи сводки совпадают.
  4. Замените эти узлы узлами-заполнителями, указывающими, что была найдена повторяющаяся структура.
  5. Вернитесь к шагу 2 и повторите необходимое количество раз.

Здесь возможен огромный объем параметризации.

(Примечание для ленивых и любопытных читателей — да, также можно было бы сериализовать дерево как строку, запустить на нем Sequitur, а затем продолжить обработку сгенерированного Sequitur дерева, что для больших реальных случаев использования обычно будет намного сложнее. меньше, чем исходное дерево. Однако у этого подхода есть проблемы во многих реальных случаях использования, потому что Sequitur не может легко выполнить «нечеткое совпадение», тогда как в реальной жизни мы часто хотели бы идентифицировать близкие, но не полностью похожие поддеревья.)

Применение грамматической индукции к нашему дереву примеров

В нашем простом примере мы будем использовать следующие функции и параметры:

  • Функция сводки поддерева: «сводка» — это строка, созданная путем сериализации поддерева, включая имена узлов поддерева. В реальном случае обычно лучше не включать имена узлов в сводку.
  • Функция сопоставления поддерева: мы сравниваем строки, чтобы увидеть, равны ли они.
  • Другие параметры: Мы делаем только один проход по дереву, и все узлы, совпадающие с другими узлами, заменяются на итоговые узлы.

Сводным узлам даются имена, оканчивающиеся на «…», поэтому вы можете видеть, какие они. Если бы мы заморачивались над правильной компоновкой, мы бы сделали что-то посложнее.

Результат выглядит следующим образом:

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

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

По сути, мы применили к дереву уровень сжатия на основе грамматической индукции, но затем (поскольку наша цель — визуализировать упрощенное дерево, а не воссоздавать исходное дерево) мы выбросили саму грамматику, т. е. дерево. сводок поддеревьев.

Упрощение примера дерева

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

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

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

Следующие шаги

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

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

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

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

Спасибо за чтение.