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

Question

我最近一直在阅读关于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的情况下)或在HTML部署的情况下使用Javascript创建这些图表,要么非常好.然而,一个限制因素是图形需要创建或可以导出到高分辨率矢量图形.

我的问题简而言之:

1. 有没有一种很好的方式可视化我拥有的数据类型？如果是这样,它是否以易于实现的形式(即图书馆)存在？
2. 如果问题没有简单的解决方案,换句话说,如果我需要在这种情况下发明我的轮子,我该如何自己实现这样的图形？什么是一个好的起点？我应该特别注意什么？

谢谢!

编辑:我可能的想法是将通用集中的所有元素布局为具有所需颜色叠加的六边形网格,然后绘制集合的边界.然而,该想法存在若干问题,特别是指定元素的位置的问题,使得集合不会在整个图形上被分割.有什么意见/建议吗？

Answer 1

是的,这是一个相当充分研究的问题.你所描述的被称为超图.每个元素都可以表示为图形中的顶点,并且这些集合是超边界.然后问题变成可视化超图.

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

如果您的集合相对较小(<5个元素),则可以使用常规图形绘制库,如graphviz.要做到这一点,只需连接每组中的所有顶点对,然后对它们进行不同的着色.这将产生类似于此的解决方案:

Answer 2

您是否考虑过二维网格：

\n\n

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

\n\n

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

\n\n

诀窍在于以对用户有用的方式对行和列进行排序，从而将最多的信息放在一起。我的直觉告诉你，你要解决的问题是使彩色单元格尽可能“像斑点”\xe​​2\x80\x94如果每组相邻的彩色单元格称为“区域”，则具有最少的数量不同的区域，并且其中的洞最少。

\n\n

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

\n\n

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

\n\n

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

\n\n

这是对您问题中的示例数据集执行上述逻辑处理后的结果图：

\n\n

\n\n

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

\n\n

附加想法：

\n\n

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

\n

Answer 3

我没有您的解决方案来以正确的格式获取数据。看一下 MIT 创建的用于构建图形的 javascript 插件sigmajs。还没有查看它接受的数据，但可能值得一看。