将集合层次结构可视化为颜色编码的图形

javascript java data-visualization graph-algorithm

2022-09-02 10:39:33

我最近一直在阅读很多关于Java和Javascript的图形库，但我还没有找到一个好方法来做我想做的事情。

从本质上讲，我有一个关于一堆元素（最多几千个）的集合层次结构。这些集合可以完全或部分重叠，完全覆盖或彼此完全不相交。我想做的是显示以下信息：

集合的大小（相对于其他集合）
根据集合所涵盖的元素计算的集合的“热”值（以颜色代码表示）
集合的完整拓扑在单个图形中（以便向用户显示重叠，交集等）

编辑：也许我应该举个例子来说明我所说的集合和元素以及部分重叠的层次结构是什么意思。以下是我处理的那种集合的过度简化版本（请注意，数字和字母表示彼此可比较的元素）：110ahX

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的情况下）创建这些图形，或者在HTML部署的情况下使用Javascript，两者都完全没问题。但是，有一件事是约束性的，那就是图形需要创建，或者可以导出为高分辨率矢量图形。

简而言之，我的问题：

有没有一种很好的方式来可视化我拥有的数据类型？如果是这样，它是否以易于实现的形式存在（即库）？
如果没有简单的解决方案，换句话说，如果在这种情况下我需要发明我的轮子，我该如何自己实现这样的图表？什么是好的起点？我需要特别注意什么？

谢谢！

编辑：我的潜在想法是将通用集合中的所有元素布局为具有所需颜色叠加的六边形网格，然后绘制集合的边界。然而，这个想法有几个问题，特别是为元素指定位置的问题，以便集合不会在整个图中全部拆分。任何意见/建议？

答案 1

是的，这是一个相当有研究的问题。你所描述的被称为超图。每个元素都可以表示为图形中的顶点，集合是超边缘。然后问题就变成了可视化超图的问题。

enter image description here

不幸的是，没有一个完美的，通用的解决方案，因为即使是最简单的图形也可能具有复杂的可视化效果。

如果你的集合相对较小（< 5 个元素），则可以使用常规图形绘图库，如 graphviz。为此，只需连接每个集合中的所有顶点对，并以不同的方式为它们着色即可。这将产生类似于以下内容的解决方案：

enter image description here

答案 2

您是否考虑过二维网格：

将设置的数字放在一个轴上
将所有集合中的唯一元素放在另一个轴上
为集合中元素所在的每个单元格着色（通过查看该行和列的标签）

虽然这种可视化方法通常不如到目前为止提到的一些更复杂的方法，但它的优点是，当你有数千个元素和数千个集合时，它实际上是可能的。

诀窍是以一种对用户有用的方式将最多的信息放在一起的方式对行和列进行排序。我的直觉告诉我，你试图解决的问题是使彩色细胞尽可能“斑点状”——如果每组相邻的彩色细胞都被称为“区域”，那么它们的不同区域数量最少，孔洞最少。

这本身就是一个非常复杂的问题，但至少可以通过为每个集合与每个其他集合计算一些邻接因子来部分解决。你要找的是亲密的“孤岛”——所以从最相似的一对集合开始，把它们添加到图表中，并把它们视为一个区域。重新计算您的接近度数字，该区域替换它所持有的货币对（以某种方式平均？）。找到下一个最接近的项目对（每个项目是一个区域或一组），如果该对与图形中任何现有区域的接近度在某个阈值内，则附加到该区域的一侧，否则创建一个新的单独区域（再次删除该对的接近度值并重新计算该区域本身）。最终，所有集合都将添加到区域，并且所有区域都将加入。连接两个区域可以有四种可能性（可能需要翻转），因此可以通过两个区域的4条边上的集合的接近度来计算图形中要附加的边。

虽然这可能永远不会给出最佳配置，但与随机分布相比，它应该提出一些区域较少的东西。

最后，一些动态重新排序可能是有用的，它允许用户选择一个有趣的集合或元素，并将其用作完全重新排列的图形的种子，根据与该元素的接近程度（以及随后与另一个元素组合后的区域）计算每个加法，而不是任何元素的整体最低接近度。

下面是结果的图表，在对问题中的示例数据集执行了上述逻辑过程之后：

Sets and Elements

决定如何对列进行排序很复杂，但基本上，当这样的移动不会干扰任何已添加的线段的彩色块区域时，您可以通过将列移动到相邻来获得合理的结果。

其他想法：

计算集合接近度不仅仅是它们有多少个共同的元素，还有多少个不共同的元素。如果两对集合在对之间有 3 个共同的元素，但一个有 5 个非共享元素，另一个有 3 个非共享元素，则具有 3 个非共享元素的对比另一个更接近匹配。
将集合添加到图形后，有机会对元素进行重新排序。将元素堆叠得尽可能靠左是第一个放置的良好开端。之后，将最常见的元素堆叠在最左边似乎很好。在那之后，它崩溃了。我想知道让彩色单元格尽可能接近对角线（从左上角到右下角）是否也是一种有用的算法 - 这让我想起了设计结构矩阵，尽管它只显示了单向依赖关系而不是双向关系。
当彩色 blob 由与所有其他集合完全不相交的集合组成时（如示例中包含 X 的集合），可以将其移动到单独的图形中。