一种图中集关系的视觉分析方法

摘要

本发明公开了一种图中集关系的视觉分析方法，首先获取网络中结点信息，包括其相关性，然后根据其相关性确定结点在平面上的位置。随后，基于结点位置产生一颗包含所有集合中结点的项所构成的生成树，并对生成树进行分段。最后，在分段的基础上，根据集合中包含项的情况进行连接线的绘制。在可视化界面中，使用者可与界面进行互动，从而更好的获取所需信息。

说明书

技术领域

本发明涉及的是一种探索图中集关系的可视化系统，该系统旨在揭示不同 的集关系并进行可视化表示。在理论研究的基础上，还将此系统应用于一个样 本数据集以进行观察。

背景技术

当今，集关系出现在各种各样的数据分析当中。许多应用的数据表示都可 以归结为一张充满结点的图，而图中的每个结点都带有各自的额外属性。例如， 一个社交网络中的好友关系可以描述为一张图，图中的每个结点可以表示为一 个用户，而结点可以拥有各自的独特信息，包括该用户感兴趣的音乐、电影、 电视节目等等。通过某种方法揭露网络中的集关系，可以帮助人们更好的分析 某个人在一个社群中的作用。

本研究受到了各类风靡世界的网络应用，例如Facebook，微博等的推动。我 们希望探寻这样一些问题，例如：研究集关系与社交网络中拓扑距离的相关性； 从事物团簇的角度来观察集合分布及其重合性。当前存在的集关系可视化方法 主要分为两类：1.利用空间位置来解释每一项目的重要特性，在这种方法中集合 位置被描绘在闭合等高线之上。2.强调集合关系，例如超集、子集关系以及集合 重合，或者其他的集合语义关系。在集合可视化以及图的视觉分析领域，前人 已经做了众多努力：

Collins等人提出了Bubble Sets方法。在他们的实现中，属于同一个集合的 项会被气泡(Bubble)形状的图形所连接。对于揭示具有类似地图那样固定布局 的项之间的集关系来说，Bubble Sets方法十分有效。与Bubble Sets方法类似， 对于属于同一集合的项，Line Sets方法采用光滑线进行连接，而这些项同样具 有固定的布局。还有一些集合可视化方法，它们并不要求项具有固定布局。这 些项根据其空间属性被分为组，由此，集与集之间的关系将会更加可以辨别。 Simonetto以及Stapleton等人实现了一种全自动方法来生成描述集合重叠的类似 Euler图的可视化效果。Riche和Dwyer使得Euler图可以更易于绘制。此外，集 合可以被解释为超图中的超边。在超图中，项将作为顶点，而每一条超边都可 以有多个顶点。研究人员研究了众多可以被应用于绘制超图的方法，其中包括 Planar，path-based以及cactus support。

在图的视觉分析方向，众多研究关注于图结构拓扑的描述。这些描述主要 通过邻接矩阵，节点连接图，或则两者的组合完成。研究的努力方向更多在于 异构图(包括多种结点与关系类型的图)以及结点带有属性的图的可视化上。 在真实的应用中，每个人都可能有一系列相关联的项。例如在一个学术合作网 络中，每个研究人员都对于不同课题具有兴趣，而在社交网络中，每个人都对 不同的音乐、电影有兴趣。在对于这些网络的研究中，我们希望得知其中的同 质性。

发明内容

本发明所要解决的技术问题就是提供了一种图中集关系的视觉分析方法， 在可视化界面中，使用者可与界面进行互动，从而更好的获取所需信息。

为解决上述技术问题，本发明采用如下技术方案：一种图中集关系的视觉 分析方法，包括如下步骤：

第一步，结点布局，

程序的初始输入为包含所有项的集合，每一项作为一个结点，同时读入的 还有项之间相似性，在相似性数据上采用MDS方法，从而转换得到在平面上各 点的坐标；

第二步，建立连接，

基于第一步得到的初始结点布局，视觉连线将会在其上进行绘制。

优选的，完成连线的绘制主要分两个阶段：

第一阶段，对于所有集合求并，即∪i∈{1,...,m}Si,对其中的所有项产生 一颗生成树；

第二阶段，基于上一步得到的生成树，对于单一集绘制连线。

优选的，第一阶段的详细过程为：

1)根据MDS布局中结点的欧几里得距离，对之前所选结点进行 HCA；

2)基于上一步的聚类，生成一颗生成树，对于连接两个相邻聚簇的最 短连接线将被包含到生成树里；

3)在一定高度对树形图进行切割，由此所有的项将根据其空间临近性 被分为若干组；

4)根据项的组划分进行分支折叠，对于某些边，它们不处于连接不同 组的位置上，因此可以被移去，而在移去边之后，如果存在结点变 为非连接状态，则将其汇入距离最近的边；

5)对生成树的段进行平滑。

优选的，第二阶段的具体过程为：上一步的生成树以被分段，针对每段进 行连线的绘制，每个段中都有来自不同集的项，绘制连线时采取这样一种策略： 每个集都被赋予一条与段相平行的小道，绘制该集的连线时，要一一检测属于 该段的每一个项，并且让连接线通过：1)中央线，如果该项数据多个集；2) 被分配给该集的线，如果该项不属于该集；3)被分配给该集的线，如果该项单 独属于此集合，在这种情况下，该项还要进行位置的移动，从中央线移至分配 给该集的小道上。

本发明首先获取网络中结点信息，包括其相关性。然后根据其相关性确定 结点在平面上的位置。随后，基于结点位置产生一颗包含所有集合中结点的项 所构成的生成树，并对生成树进行分段。最后，在分段的基础上，根据集合中 包含项的情况进行连接线的绘制。因此在可视化界面中，使用者可与界面进行 互动，从而更好的获取所需信息。

附图说明

下面结合附图和具体实施方式对本发明作进一步描述：

图1为完成连线绘制第一阶段过程原理图；

图2为完成连线绘制第二阶段过程原理图。

具体实施方式

下面对本本发明的实现方式进行说明，将会描述详细的实施方式和具体的 操作过程。

在集关系的可视化表示中，完成如下几个任务十分重要：

1.寻找集中的项

2.辨别一个项所属的若干集合

3.辨别集合的交

4.从项团簇的角度，识别一个集合中项的分布

5.寻找集合之间的隐式重叠

为了完成上述目标，将以以下步骤进行实施：

一、结点布局

程序的初始输入为包含所有项的集合，每一项作为一个结点。同时读入的 还有项之间相似性。在相似性数据上采用Multidimensional Scaling(MDS)方法， 从而转换得到在平面上各点的坐标。MDS方法使得具有较高相似度的结点在平 面上处于相近的位置，这些相邻的结点就构成了一个一个的视觉团簇。

二、建立连接

基于第一步得到的初始结点布局，视觉连线将会在其上进行绘制。我们可 以将对结点坐标进行灵活处理，使得某些结点稍微偏离其MDS布局，达到的目 的就是在绘制连线的时候，不会有太多的视觉杂乱，可以让人们更清晰的辨认 每项。但同时，结点不应该产生过大的偏离进而脱离其原本属于的组。

对于每一个集(Set)，我们可以理解为一个人，而连线的将连接该集所拥有 的所有项(Item)。例如，在一个社交网络图中，项为艺术家的名称，而集为用 户，某一个用户所喜爱的艺术家将被连线连接。

完成连线的绘制主要分两个阶段：

第一阶段，对于所有集合求并，即∪i∈{1,...,m}Si,对其中的所有项产生 一颗生成树。如图1所示。

这一阶段生成的是一个“主干”，对于这颗生成树，如下特性较为重要：分 支尽量少，每个段(segment)尽量光滑，结点位置相对于初始布局偏移较少。 这一阶段的详细过程为：

1)根据MDS布局中结点的欧几里得距离，对之前所选结点进行 Hierarchical agglomerative clustering(HCA)，

2)基于上一步的聚类，生成一颗生成树。对于连接两个相邻聚簇的最短 连接线将被包含到生成树里。

3)在一定高度对树形图进行切割，由此所有的项将根据其空间临近性被 分为若干组。

4)根据项的组划分进行分支折叠。对于某些边，它们不处于连接不同组 的位置上，因此可以被移去。而在移去边之后，如果存在结点变为非 连接状态，则将其汇入距离最近的边。

5)对生成树的段进行平滑。在此过程中，某些项可能会相对其原始位置 发生移动，使得段的形状不要过于曲折。

第二阶段，基于上一步得到的生成树，对于单一集绘制连线。如图2所示。 这一阶段的具体过程为：

上一步的生成树以被分段，针对每段进行连线的绘制。每个段中都有来自 不同集的项，绘制连线时我们采取这样一种策略：每个集都被赋予一条与段相 平行的小道，绘制该集的连线时，我们要一一检测属于该段的每一个项，并且 让连接线通过：1)中央线。如果该项数据多个集；2)被分配给该集的线，如 果该项不属于该集；3)被分配给该集的线，如果该项单独属于此集合。在这种 情况下，该项还要进行位置的移动，从中央线移至分配给该集的小道上。