一种两类关联层次数据的可视化方法

摘要

本发明属于信息可视化领域，具体涉及一种两类关联层次数据的可视化方法，用于可视化关联层次数据。本发明先用基于力导向的节点‑链接树和基于放射环的空间填充树分别可视化相互独立的两个层次数据，然后通过直线将两棵树中具有关联关系的节点连接起来，形成一个双关联树。为减少边交叉和视觉混乱现象，通过路径绕行的布局优化算法，引入了隐形圈的概念，用三次贝塞尔曲线取代直线优化关系边。本发明提出的针对两类关联层次数据的可视化方法，可同时展示两类关联层次数据中的层次关系和关联关系，并有效减少视觉杂乱，帮助用户查看数据间的关联关系，有助于进一步的数据分析。

权利要求

1.一种两类关联层次数据的可视化方法，所述两类关联层次数据包括：2个层次数据以及2个层次数据之间的关联关系信息，其特征在于：其具体操作步骤为：步骤一、用两个多叉树分别存储待可视化的两类层次数据中的两个层次数据，两个多叉树分别表示为多叉树A和多叉树B；所述多叉树中的节点采用顺序存储结构与链式存储结构相结合的方法，具体为：采用链式存储结构按照自顶向下的顺序存储每一层次中的第一个节点；对于同一层次中的节点采用顺序存储结构；

步骤二、对步骤一中得到的多叉树A采用放射环算法生成空间填充布局；

步骤三、对步骤一中得到的多叉树B采用力导向算法生成节点-链接布局，并使节点-链接布局中的根节点位于步骤二中得到的空间填充布局的根节点显示区域的中心点O位置处，确保节点-链接布局位于空间填充布局中的根节点显示区域内；

步骤四、对两类层次数据中的关联关系进行可视化；具体为：

步骤4.1：根据2个层次数据之间的关联关系信息，分别找到多叉树A和多叉树B中有关联关系的节点对，并在步骤三得到的视图上将有关联关系的节点对用直线段进行连接，称所述直线段为直线关系边；多叉树A和多叉树B中有关联关系的节点称为关系节点；

步骤4.2：重复步骤4.1的操作，直至将2个层次数据之间的所有关联关系信息均用直线关系边显示在步骤三得到的视图上，得到初步可视化结果。

2.如权利要求1所述的一种两类关联层次数据的可视化方法，其特征在于：其还包括步骤五对初步可视化结果进行路径绕行处理，得到最终可视化结果；具体操作步骤为：步骤5.1：设置一个半径为r，圆心位于点O的隐形圈，r1＜r＜r2，其中，r1是节点-链接布局中距离根节点最远的节点与根节点之间的距离；r2是空间填充布局中根节点显示区域的半径长度；

步骤5.2：对步骤4生成的可视化结果中节点-链接布局中的所有关系节点依次做以下处理，得到以当前关系节点为其中一个端点的直线关系边经过绕行处理后，在隐形圈内部的路径，具体为：首先，找到当前关系节点NA的父节点NB和节点NB的父节点NC；并计 算通过节点NB和节点NC的直线的斜率，用符号kBC表示；然后，过节点NA，做一条斜率为kBC的直线，该直线与步骤5.1中所述隐形圈有2个交点，分别计算节点NA到2个交点的距离，用符号D表示2个交点中距离节点NA近的交点；最后，连接点NA和点D，线段NAD即为以当前关系节点为其中一个端点的直线关系边经过绕行处理后，在隐形圈内部的路径；

步骤5.3：对步骤4生成的可视化结果中节点-链接布局中的所有关系节点依次做以下处理：首先，查看当前关系节点NA的直线关系边的个数，然后对当前关系节点NA的每条直线关系边做以下处理，得到每条直线关系边经过绕行处理后，在隐形圈外部的路径，具体为：步骤5.3.1：当前关系节点NA的当前直线关系边的两个端点中，一个是点NA，另一个用符号Sa表示；用直线连接节点D和节点Sa；用符号W表示点D到点Sa的距离；

步骤5.3.2：如果W＜100像素，则直线段DSa即为当前直线关系边经过绕行处理后，在隐形圈外部的路径；

步骤5.3.3：如果W≥100像素，进行以下处理：

步骤A1：对线段DSa六等分，用符号P1表示从D点开始的第一等分点，用符号P2表示从D点开始的第三等分点；将点P1和P2作为3次贝塞尔曲线的2个控制点的初始位置；

步骤A 2：对3次贝塞尔曲线的2个控制点P1和P2沿与线段DSa垂直的方向进行同方向移动，移动的距离用符号L'表示，其值可通过公式(1)计算得到；移动后的点分别用P3和P4表示，点O到线段DSa的距离小于点O到线段P3P4的距离；

其中，L表示点O到线段DSa的距离；

步骤A3：以D为初始位置，以点P3和P4为控制点，以Sa为终点做一条3次贝塞尔曲线，得到当前直线关系边经过绕行处理后，在隐形圈外部的路径；

经过上述步骤的操作，即可完成路径绕行处理，得到最终可视化结果。

说明书

一种两类关联层次数据的可视化方法

技术领域

[0001] 本发明属于信息可视化领域，具体涉及一种两类关联层次数据的可视化方法，用于可视化关联层次数据。

背景技术

[0002] 在现实工作和生活中，具有相互联系的多个层次数据广泛存在于食品安全、金融信息和社会网络等各领域中。

[0003] 层次数据是一组通过层次结构关系互相关联的数据。

[0004] 两类关联层次数据是指具有关联关系的两个层次数据，包括：2个层次数据以及2个层次数据之间的关联关系信息。

[0005] 如：在食品中农药残留检测数据就是一个两类层次数据。食品中农药残留检测数据中含有地域和农药分类信息两个层次数据，地域信息包括全国7个区域：华北、华东、华南、华中、东北、西北和西南；区域下包含不同的省；省下包含市；市下包含区县；区县下包含不同的超市，具有明显的层次结构。农药按照毒性程度可以分为4个类别：低毒、中毒、高毒和剧毒；每种毒性下面又包含有多种农药，也具有层次结构。不同超市的农产品检出农药情况就是地域信息与农药信息之间的关联关系。如何对两类层次数据及其隐含的相互关联关系进行可视化和可视分析是一个亟待解决的问题。

[0006] 迄今为止，针对单个层次数据的可视化方法，已取得大量成果，其主要技术包括节点-链接法(Node-Link)和空间填充法(Space-Filling)两大类。

[0007] 节点-链接法是外观上最接近树型结构的层次数据可视化方法，该方法采用节点表示树型结构中的信息单元，用连线表示树型结构中的父子关系，可以直观的展示层次结构。常见的有树(Tree)，双曲树(Hyperbolic Browser)，径向树(Radial Tree)等。空间填充法的主要思想是将整个信息集合映射到一个区域，通过用矩形，正方形，扇形或是多边形等的嵌套填充来描述层次结构。其中常见的方法有两种：树图(Treemap)和放射环(Sunburst)。

[0008] 此外，混合(Hybrid)布局算法在层次数据可视化方法中也逐渐发展起来，其主要思想是将节点-链接、空间填充以及简单的统计图有效的结合起来，达到优势互补的效果。Zhao S等人在2005年在文献《Elastic hierarchies:Combining treemaps and node-link diagrams》中提出将节点-链接和树图相结合，在有限的屏幕空间内，允许用户对树中任何一个节点进行节点-链接和树图之间的切换显示，可以高效查看各节点的信息属性，用以帮助用户更好的了解树图中所携带的信息。该方法保留了节点-链接对层次结构和树图对节点权值的高表现性。Huang M  L等人在2009年在文献《Treemapbar:Visualizing additional dimensions of data in bar chart》中将树图嵌入到柱状图中，当柱状图的密度增加时，可以使用表透镜(TableLens)技术查看特定区域的细节，优化显示空间的利用率。2012年，Kobayashi A等人在文献《Edge Equalized Treemaps》中利用树图和柱状图的结合，将柱状图嵌入到树图中，柱状图的宽度相等。通过该方法，可以对数据进行比较。对层次数据可视化的方法还有很多，但这些方法主要解决同一类层次数据的可视化和可视分析问题，对两类层次数据的可视分析问题较少涉及。

[0009] 因此，已公开的对层次数据进行可视化的方法并不能有效地解决两类层次数据及其关联关系的可视分析。

发明内容

[0010] 本发明目的是提供一种两类关联层次数据的可视化方法。本发明的基本思想是先用基于力导向的节点-链接树和基于放射环的空间填充树分别可视化相互独立的两类层次数据，然后通过直线将两棵树中具有关联关系的节点连接起来，形成一个双关联树；为减少边交叉和视觉混乱现象，本发明通过路径绕行的布局优化算法，引入了隐形圈的概念，用三次贝塞尔曲线取代直线优化关系边。

[0011] 本发明的目的是通过下述技术方案实现的。

[0012] 一种两类关联层次数据的可视化方法，所述两类关联层次数据包括：2个层次数据以及2个层次数据之间的关联关系信息，其特征在于：其具体操作步骤为：

[0013] 步骤一、用两个多叉树分别存储待可视化的两类层次数据中的两个层次数据，两个多叉树分别表示为多叉树A和多叉树B。所述多叉树中的节点采用顺序存储结构与链式存储结构相结合的方法，具体为：采用链式存储结构按照自顶向下的顺序存储每一层次中的第一个节点；对于同一层次中的节点采用顺序存储结构。

[0014] 步骤二、对步骤一中得到的多叉树A采用放射环(sunburst)算法生成空间填充布局(layout of space-filling)。

[0015] 步骤三、对步骤一中得到的多叉树B采用力导向(force-direct)算法生成节点-链接布局(layout of node-link)，并使节点-链接布局中的根节点位于步骤二中得到的空间填充布局的根节点显示区域的中心点(用符号O表示)位置处，确保节点-链接布局位于空间填充布局中的根节点显示区域内。

[0016] 步骤四、对两类层次数据中的关联关系进行可视化。具体为：

[0017] 步骤4.1：根据2个层次数据之间的关联关系信息，分别找到多叉树A和多叉树B中有关联关系的节点对，并在步骤三得到的视图上将有关联关系的节点对用直线段进行连接，称所述直线段为直线关系边；多叉树A和多叉树B中有关联关系的节点称为关系节点。

[0018] 步骤4.2：重复步骤4.1的操作，直至将2个层次数据之间的所有关联关系信息均用直线关系边显示在步骤三得到的视图上，得到初步可视化结果。

[0019] 步骤五、对初步可视化结果进行路径绕行处理，得到最终可视化结果。

[0020] 由于步骤4生成的初步可视化结果视觉杂乱较严重，因此对步骤4生成的初步可视化结果进行路径绕行处理。具体操作步骤为：

[0021] 步骤5.1：设置一个半径为r，圆心位于点O的隐形圈，r1＜r＜r2，其中，r1是节点-链接布局中距离根节点最远的节点与根节点之间的距离；r2是空间填充布局中根节点显示区域的半径长度。

[0022] 步骤5.2：对步骤4生成的可视化结果中节点-链接布局中的所有关系节点依次做以下处理，得到以当前关系节点为其中一个端点的直线关系边经过绕行处理后，在隐形圈内部的路径，具体为：

[0023] 首先，找到当前关系节点(用符号NA表示)的父节点(用符号NB表示)和节点NB的父节点(用符号NC表示)；并计算通过节点NB和节点NC的直线的斜率，用符号kBC表示。然后，过节点NA，做一条斜率为kBC的直线，该直线与步骤5.1中所述隐形圈有2个交点，分别计算节点NA到2个交点的距离，用符号D表示2个交点中距离节点NA近的交点。最后，连接点NA和点D，线段NAD即为以当前关系节点为其中一个端点的直线关系边经过绕行处理后，在隐形圈内部的路径。

[0024] 步骤5.3：对步骤4生成的可视化结果中节点-链接布局中的所有关系节点依次做以下处理：

[0025] 首先，查看当前关系节点NA的直线关系边的个数，然后对当前关系节点NA的每条直线关系边做以下处理，得到每条直线关系边经过绕行处理后，在隐形圈外部的路径，具体为：

[0026] 步骤5.3.1：当前关系节点NA的当前直线关系边的两个端点中，一个是点NA，另一个用符号Sa表示；用直线连接节点D和节点Sa；用符号W表示点D到点Sa的距离。

[0027] 步骤5.3.2：如果W＜100，则直线段DSa即为当前直线关系边经过绕行处理后，在隐形圈外部的路径。

[0028] 步骤5.3.3：如果W≥100，进行以下处理：

[0029] 步骤A1：对线段DSa六等分，用符号P1表示从D点开始的第一等分点，用符号P2表示从D点开始的第三等分点。将点P1和P2作为3次贝塞尔曲线的2个控制点的初始位置。

[0030] 步骤A2：对3次贝塞尔曲线的2个控制点P1和P2沿与线段DSa垂直的方向进行同方向移动，移动的距离用符号L'表示，其值可通过公式(1)计算得到；移动后的点分别用P3和P4表示，点O到线段DSa的距离小于点O到线段P3P4的距离。

[0031]

[0032] 其中，L表示点O到线段DSa的距离。

[0033] 步骤A3：以D为初始位置，以点P3和P4为控制点，以Sa为终点做一条3次贝塞尔曲线，得到当前直线关系边经过绕行处理后，在隐形圈外部的路径。

[0034] 经过上述步骤的操作，即可完成路径绕行处理，得到最终可视化结果。

[0035] 有意效果

[0036] 本发明提出的一种两类层次数据的可视化方法，可同时展示两类层次数据中的层次关系和关联关系，并有效减少视觉杂乱，帮助用户查看数据间的关联关系，有助于进一步的数据分析。

附图说明

[0037] 图1为本发明具体实施方式中多叉树A树图；

[0038] 图2为本发明具体实施方式中多叉树B树图；

[0039] 图3为本发明具体实施方式中对多叉树A采用放射环算法生成的空间填充布局示意图；

[0040] 图4为本发明具体实施方式中对多叉树B采用力导向算法生成的节点-链接布局示意图；

[0041] 图5为本发明具体实施方式中对天津市超市中蔬菜农药残留检测结果数据进行可视化操作后，得到的最终可视化结果图。

具体实施方式

[0042] 下面结合附图和实施例，对本发明技术方案作进一步的说明。

[0043] 本实施例中的两类关联层次数据为天津市超市中蔬菜农药残留检测结果，2个层次数据分别是农药毒性层次数据和地域关系层次数据，分别如表1和表2所示。2个层次数据之间的关联关系信息如表3所示。

[0044] 表1农药毒性层次数据(农药毒性分类信息表)

[0045]

[0046] 表2地域关系层次数据(地域信息表)

[0047]

[0048] 表3农药信息与地域信息关联关系表

[0049]地域信息 对应地区检测出的农药名称
Sm1 Pr1
Sm1 Pr2
Sm2 Pr1
Sm3 Pr6
Sm4 Pr6
Sm5 Pr3
Sm6 Pr4
Sm7 Pr8
Sm9 Pr7
Sm11 Pr5

[0050] 采用本发明提出的两类关联层次数据的可视化方法，对上述数据进行可视化操作，其具体操作步骤为：

[0051] 步骤一、用多叉树A存储农药毒性层次数据，得到的多叉树A如图1所示；用多叉树B存储地域关系层次数据，得到的多叉树B如图2所示；多叉树A和多叉树B。中的节点采用顺序存储结构与链式存储结构相结合的方法，具体为：采用链式存储结构按照自顶向下的顺序存储每一层次中的第一个节点；对于同一层次中的节点采用顺序存储结构。

[0052] 步骤二、对步骤一中得到的多叉树A采用放射环(sunburst)算法生成空间填充布局(layout of space-filling)，如图3所示。

[0053] 步骤三、对步骤一中得到的多叉树B采用力导向(force-direct)算法生成节点-链接布局(layout of node-link)，如图4所示，并使节点-链接布局中的根节点位于步骤二中得到的空间填充布局的根节点显示区域的中心点O位置处，确保节点-链接布局位于空间填充布局中的根节点显示区域内。

[0054] 步骤四、对两类层次数据中的关联关系进行可视化。具体为：

[0055] 步骤4.1：根据2个层次数据之间的关联关系信息，分别找到多叉树A和多叉树B中有关联关系的节点对，并在步骤三得到的视图上将有关联关系的节点对用直线段进行连接，称所述直线段为直线关系边；多叉树A和多叉树B中有关联关系的节点称为关系节点。

[0056] 步骤4.2：重复步骤4.1的操作，直至将2个层次数据之间的所有关联关系信息均用直线关系边显示在步骤三得到的视图上，得到初步可视化结果。

[0057] 步骤五、对初步可视化结果进行路径绕行处理，得到最终可视化结果。

[0058] 由于步骤4生成的初步可视化结果视觉杂乱较严重，因此对步骤4生成的初步可视化结果进行路径绕行处理。具体操作步骤为：

[0059] 步骤5.1：设置一个半径为r＝140个像素，圆心位于点O的隐形圈。节点-链接布局中距离根节点最远的节点与根节点之间的距离r1是125个像素；空间填充布局中根节点显示区域的半径长度r2180个像素。

[0060] 步骤5.2：对步骤4生成的可视化结果中节点-链接布局中的所有关系节点依次做以下处理，得到以当前关系节点为其中一个端点的直线关系边经过绕行处理后，在隐形圈内部的路径，具体为：

[0061] 首先，找到当前关系节点NA的父节点NB和节点NB的父节点NC；并计算通过节点NB和节点NC的直线的斜率kBC，各关系节点对应的斜率kBC如表4所示。然后，过节点NA，做一条斜率为kBC的直线，该直线与步骤5.1中所述隐形圈有2个交点，分别计算节点NA到2个交点的距离，用符号D表示2个交点中距离节点NA近的交点。最后，连接点NA和点D，线段NAD即为以当前关系节点为其中一个端点的直线关系边经过绕行处理后，在隐形圈内部的路径。

[0062] 表4各关系节点对应的斜率KBC值表

[0063]节点-链接布局中的关系节点 KBC
Sm1 0.44
Sm2 0.44
Sm3 1.11
Sm4 1.11

[0064]Sm5 -28.56
Sm6 -28.56
Sm7 -1.38
Sm9 -1.38
Sm11 -0.37

[0065] 步骤5.3：对步骤4生成的可视化结果中节点-链接布局中的所有关系节点依次做以下处理：

[0066] 首先，查看当前关系节点NA的直线关系边的个数，然后对当前关系节点NA的每条直线关系边做以下处理，得到每条直线关系边经过绕行处理后，在隐形圈外部的路径，具体为：

[0067] 步骤5.3.1：当前关系节点NA的当前直线关系边的两个端点中，一个是点NA，另一个是Sa；用直线连接节点D和节点Sa；用符号W表示点D到点Sa的距离。

[0068] 步骤5.3.2：如果W＜100，则直线段DSa即为当前直线关系边经过绕行处理后，在隐形圈外部的路径。

[0069] 步骤5.3.3：如果W≥100，进行以下处理：

[0070] 步骤A1：对线段DSa六等分，用符号P1表示从D点开始的第一等分点，用符号P2表示从D点开始的第三等分点。将点P1和P2作为3次贝塞尔曲线的2个控制点的初始位置。

[0071] 步骤A2：对3次贝塞尔曲线的2个控制点P1和P2沿与线段DSa垂直的方向进行同方向移动，移动的距离用符号L'表示，其值可通过公式(1)计算得到；移动后的点分别用P3和P4表示，点O到线段DSa的距离小于点O到线段P3P4的距离。各关系节点对确定的直线关系边对应得到的W、L和L'值如表5所示。

[0072] 表5各直线关系边对应得到的W、L和L’值表

[0073]直线关系边 W L L’
Sm1 Pr1 71.08 ----- -----
Sm1 Pr2 180.68 138.17 38.17
Sm2 Pr1 86.70 ----- -----
Sm3 Pr6 114.59 130.92 30.92
Sm4 Pr6 88.03 ----- -----
Sm5 Pr3 142.66 139.24 39.24
Sm6 Pr4 198.94 134.77 34.77
Sm7 Pr8 119.88 133.48 33.48

[0074]Sm9 Pr7 73.77 ----- -----
Sm11 Pr5 154.88 139.99 39.99

[0075] 步骤A3：以D为初始位置，以点P3和P4为控制点，以Sa为终点做一条3次贝塞尔曲线，得到当前直线关系边经过绕行处理后，在隐形圈外部的路径。

[0076] 经过上述步骤的操作，即可完成路径绕行处理，得到最终可视化结果，如图5所示。

[0077] 本发明的主要内容已通过上述优选实例作了详细介绍，应当认识到上述的描述不应被认为是对本发明的限制。在本领域技术人员阅读了上述内容后，对于本发明的多种修改和替代都将是显而易见的。因此，本发明的保护范围应由所附的权利要求来限定。