Визуализация заданных иерархий в виде цветных графиков

Я читал довольно много о графических библиотеках для Java и Javascript в последнее время, но я не нашел хорошего способа делать то, что хочу.

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

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

Изменить: Возможно, я должен привести пример того, что я имею в виду под множествами и элементами и частично перекрывающимися иерархиями. Ниже приведена упрощенная версия типов наборов, с которыми я имею дело (обратите внимание, что числа 1 - 10 и буквы a - h и X представляют собой элементы, которые сопоставимы друг с другом):

Set1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
Set2 = {1, 2, 3, 4, 5, 6}
Set3 = {1, 2, 3}
Set4 = {1, 4, 5, 6, 7}
Set5 = {a, b, c, d, e, f, g, h}
Set6 = {a, b, c, d, e}
Set7 = {a, b, c, 7}
Set8 = {2, 4, 7, 8, c, f}
Set9 = {X}

Я не уверен, как я собираюсь отображать эту информацию интуитивным способом. Я видел графики Voronoi ¹, ², которые мне действительно нравятся визуально, однако у них есть другой математический фон, поэтому Я не думаю, что смогу изобразить иерархию, которую я имею в надлежащем порядке. Я хотел бы создать эти графики во время выполнения (в случае Java) или использовать Javascript в случае развертывания HTML, либо это прекрасно. Однако одна вещь, которая является ограничением, заключается в том, что графики должны быть либо созданы, либо могут быть экспортированы в векторную графику с высоким разрешением.

Мои короткие вопросы:

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

Спасибо!

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

Ответ 1

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

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

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

Ответ 2

Вы рассматривали двумерную сетку:

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

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

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

Это очень сложная проблема сама по себе, но ее можно хотя бы частично решить, обработав некоторые коэффициенты смежности для каждого набора по отношению к любому другому набору. То, что вы ищете, - это "острова" близости - так что начните с пары самых похожих наборов, добавьте их в график и рассмотрите их как область. Пересчитайте свои номера близости с областью, заменяющей пару, которую он удерживает (усреднение каким-то образом?). Найдите следующую наиболее близкую пару элементов (каждый элемент является регионом или множеством), и если эта пара находится в определенном пороге близости к любой существующей области на графике, присоедините ее к одной стороне этого региона, в противном случае создайте новую, отдельную область (снова удаляя значения близости пары и пересчитывая для самой области). В конце концов, все наборы будут добавлены в регионы, и все регионы будут объединены. Объединение двух областей может иметь четыре возможности (может потребоваться щелчок), так что стороны, которые нужно прикрепить на графике, можно вычислить по близости множеств на 4 ребрах двух областей.

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

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

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

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

Дополнительные мысли:

Вычисление близости набора - это не только количество элементов, которые они имеют вместе, но и количество элементов, которые у них есть, которые не являются общими. Если две пары наборов имеют 3 элемента, общие между парами, но у одного есть 5 не разделяемых элементов, а у другого есть 3 не разделяемых элемента, то пара с тремя не разделяемыми элементами является более близкой, чем другая.
После добавления набора к графику есть возможность изменить порядок элементов. Укладка элементов как можно более левого является хорошим началом для первого размещения. После этого укладывание наиболее распространенных элементов влево-влево кажется хорошим. После этого он ломается. Интересно, будет ли полезный алгоритм получать цветные ячейки как близко к диагонали (слева направо налево), это немного напоминает Матрица структуры проектирования, хотя это показывает только односторонние зависимости, а не двусторонние отношения.
Когда цветной блок состоит из множеств, которые полностью не пересекаются со всеми другими наборами (например, набор, содержащий X в вашем примере), его можно перемещать на отдельный граф.

Ответ 3

Существует много подходов к этой проблеме, но лично я бы сделал диаграмму Венна с использованием динамически созданного SVG с помощью инструмента, такого как Raphael JS и покрасьте его так, как я хочу. Кроме того, Raphael имеет api как Set, который позволяет вам дать полную подробную информацию об элементах и их отношениях. Там SVG to Code converter также, вероятно, поможет понять, как вы можете генерировать элементы SVG.

В качестве альтернативы вы можете использовать такие инструменты, как графики Venn:

который, как представляется, легко адаптируется к этому сценарию. Там также Flotr2, который может создавать пузырьковые диаграммы:

или даже Canvas Express.

Немного больше настроек с помощью любого из более поздних инструментов позволит вам правильно его выполнить...

Ответ 4

У меня нет вашего решения для получения данных в правильном формате. Взгляните на этот плагин javascript, созданный MIT для построения графиков, sigmajs. Не смотри на данные, которые он принимает, но может быть стоит посмотреть.