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

Question

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

javajavascriptdata-visualizationgraph-algorithm

20

I have been reading quite a bit on graphing libraries for Java and Javascript lately but I haven't found a good way to do what I want to do. Essentially I have a hierarchy of sets with regards to a bunch of elements (up to several thousands). These sets can be fully or partly overlapping, fully covering or completely disjoint from one another. What I would like to do is to display the following information:

一个集合的大小（与其他集合相比）
一个集合的“热度”值（以颜色编码），该值是由它所覆盖的元素计算出来的
所有集合的完整拓扑结构，以单个图形式呈现（以便向用户显示重叠、交集等信息）

编辑：也许我应该举个例子来说明我所说的集合、元素和部分重叠的层次结构。以下是我处理的一种过度简化的集合类型（请注意，数字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. 是否有一种好的方式来可视化我拥有的数据？如果有，是否存在一个现成的实现形式（即库）？ 2. 如果没有简单的解决方案，换句话说，如果我需要自己发明轮子，我该如何实现这样的图表？什么是一个好的起点？我需要额外注意什么？

谢谢！

编辑：我有一个潜在的想法，就是将通用集合中的所有元素布局成一个六边形网格，并覆盖所需的颜色，然后为集合绘制边界。然而，这个想法存在几个问题，特别是指定元素的位置，以便集合不会分散在整个图表中。有任何评论/建议吗？

- posdef

1

我们要讨论多少个集合？对于小数字，对称维恩图可以涵盖所有可能性，但并没有特别注意层次结构。 - AakashM

数百肯定是有的，在很多情况下接近千，甚至有时更多... - posdef

也许你应该看看Matlab。 - Garrett Hall

整个宇宙中可能有多少元素？它们通常会超过集合的数量吗？ - orangepips

1

和弦图可能是一个有用的工具：http://mbostock.github.com/d3/ex/chord.html。对每个集合中的元素进行排序，将每个集合表示为圆周边缘上的一条弧线，集合之间的交集将由弦线表示，也许和弦颜色可以作为热力图来指示交集的程度。在这种设计中，可能会在弧线组合之间绘制多条弦线。 - orangepips

显示剩余9条评论

4个回答

5

您考虑过一个二维网格吗：

- 将集合编号放在一个轴上 - 在另一个轴上放置所有集合中找到的唯一元素 - 对于在一个集合中发现元素的每个单元格进行着色（通过查看该行和列的标签）

虽然这种可视化方法通常比先前提到的一些更复杂的方法差，但它的优点是当您有数千个元素和数千个集合时，实际上可以使用它。

关键将是以使用户有用的方式将最多信息放在一起的方式来排序行和列。我的直觉是你试图解决的问题是使彩色单元格尽可能“bloblike” - 如果相邻彩色单元格的每组被称为一个“区域”，则具有最少数量的不同区域并且它们中的孔最少。

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

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

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

以下是在您的问题示例数据上执行了上述逻辑过程的结果图：

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

- ErikE

Erik的回答很好，感谢你抽出时间！在我休假前，我实际上也尝试了类似的东西 :) 在我的情况下，我选择了一个六边形网格，增加了更多的直接邻居，这可能是明智的选择，也可能不是，取决于底层数据。我用JS编写了一个布局算法，以螺旋方式构建网格，并将数据从数组绑定到螺旋节点上。这将问题简化为对数组中的数据进行排序，这本身可能非常棘手。 - posdef

哦，我认为互动性的想法在这里是非常恰当的。我想让用户以某种方式参与进来，因此一直在研究JavaScript驱动的框架，比如D3.js。 - posdef

2

有很多方法可以解决这个问题，但我个人会使用动态生成SVG的Venn图表，使用像Raphael JS这样的工具，并将其涂上我想要的颜色。此外，Raphael还具有像Set这样的api，可以让您提供有关元素及其关系的完整详细信息。这里SVG to Code converter也可能会帮助您了解如何生成SVG元素。

另外，您也可以使用像Venn charts这样的工具： Venn chart sample

这似乎很容易适应这种情况。还有一个名为Flotr2的工具，它可以创建气泡图： Bubble chart flotr

或者甚至使用Canvas Express。 Canvas Xpress Diagrams

稍微调整一下这些工具中的任何一个，都可以让您正确完成...

- Chibueze Opata

这些对于成千上万个元素的数千个集合似乎不切实际。 - ErikE

0

我没有你所需的将数据以正确格式获取的解决方案。不过，你可以看一下麻省理工学院开发的用于构建图表的 JavaScript 插件 sigmajs。虽然我还没有查看它接受的数据，但可能值得一试。

- keaplogik

谢谢，我会检查一下看看在这种情况下是否有任何有用的东西。 - posdef

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- tskuzzy · Accepted Answer

是的，这是一个相当研究透彻的问题。你所描述的被称为超图。每个元素都可以在图中表示为一个顶点，集合则是超边。问题随之转化为可视化超图。

enter image description here

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

如果你的集合比较小（<5个元素），你可以使用普通的图形绘制库，如graphviz。要做到这一点，只需在每个集合内连接所有顶点对并以不同的颜色进行着色。这将产生类似于以下解决方案的效果：

enter image description here