计算机仿真    2014-3
北京工商大学

在数据结构优化管理的研究中,传统的力导向方法应用于层次结构数据的展示时,会存在树形布局展示不清楚的问题。为解决上述问题,通过层次数据特征分析,提出了一种面向层次数据的力导向布局算法,将力导向布局中不同层次的边赋予不同初始弹簧长度,以解决层次数据中结构信息展示不清楚的问题,然后结合层次上下行、Overview+Detail等交互技术,通过与气泡图的协同,清晰展示层次数据的内容信息,从结构和内容角度对层次数据进行可视化和可视分析。实验表明,能够有效提高层次结构数据的展示能力,最后应用于农产品中农残检测结果数据的分析和观察,取得良好效果。

引言

层次数据的节点链接可视化方法主要包括双曲树(Hyperbolic Tree)和径向树(Radial Tree)等。

双曲树是一种fbcus+context技术来显示大型层次数据的可视化方法。该技术的本质是使用统一的算法将层次结构布局到双曲平面上,然后再将该双曲平面映射到圆形显示区域。

力导向算法是一种常用的绘制一般网状结构的方法。最初由PeterEades提出,它仿真物理力学的概念,对网络图中任意一个节点,都受到引力及斥力。引力是由与此节点有边相连接的每个邻居所提供的合力,其意义是节点与其邻居之间的距离不会太远;斥力是由整个网络图中除了本身以外的节点所提供,为了让任意两节点不会因距离太近而产生重叠的现象,也因此整个网络图不会太密集而影响视觉。

算法的终止通过给定节点的初始位置,放人此力导向的物理模型中,系统自动调整节点位置,直至达到稳定条件才结束。

对于簇状数据,出现了一种与力导向结合的方法,此方法是一种基于将一个图划分为多个子图的多级技术.开始先构建最小的子图,使用力导向布局调整节点的位置.然后在下一层级的子图划分中使用调整好后的结果。

但是,力导向算法应用于树型数据的研究还较少。本文将力导向算法应用于层次数据的布局,提出一种可变弹簧的力导向布局算法,能够较好展示结构信息,并结合气泡图展示其中的内容信息,设计完成了多视图协同可视分析系统.

向层次数据的力导向布局算法

传统力导向布局会产生边长度相对一致的情况,而这种情况对层次结构的展示是不明显的,尤其是在节点普遍具有较大出度的情况下,在布局中表现为中心节点即根节点处有节点混杂,在叶节点处子树的交叉遮挡现象严重.子树的成团效果不明显,因而影响对层次数据的观察。

本文考虑调整不同层次的边的长度以示区分,以不同的边长表现不同的层次,使得根节点处的边长较长而叶节点的边长较短。并依树形结构的结构特征达到一定的边长比值,从而实现中心节点处发散而叶节点处收敛的目的。

对于不同层次的边赋以不同的长度,以区别其向指父节点和其子节点的边。并使相邻层次满足边长比例为C,C为某常数,将此布局算法称为可变弹簧力导向布局算法VSFDP
image_1bv7ns6oms0c1668t6319ui1a2r9.png-201.6kB

斥力计算:
image_1bv7o1k039em1j491adjmstuh5m.png-154.7kB

引力计算:
image_1bv7ob1pv1imautboti1942lq913.png-297kB

确定不同层次弹簧长度的比值常数C
对于一棵规则的满n叉树来说,节点所处的层次越高,其子树包含的节点数目越多。这篇文章将N层节点与N+1层节点的比值定为常数n,则C=n,但是如果每层节点的度的比值不是常数,那么就使用数的平均度来作为常数C:
image_1bv7p29jq1rl9hp3p5jijs17s1g.png-78.6kB

VSFDP算法步骤:

  1. 将输入数据转化为树型结构存储
  2. 计算树型结构的源数据:非叶子节点的度,树的平均度
  3. 根据期望距离(默认长度)+比例常数C来规定每层的边长度
  4. 建立模型,代入数据

交互方式

  • 层次放大和层次缩小
  • Overview+Detail
  • 气泡图

系统设计

可视化流水线是将原始数据转换成计算机内存中数据结构。并用一种可视化方法将数据在屏幕上展现出来的过程,如图下图所示,在这个过程中包括用户的交互反馈以及各种工具方法等的使用。
image_1bv7qncht5oh1hskfvgk0719861t.png-35.2kB

实验结果

image_1bv7qqn1n12s1157p11ec1d8h1nka2a.png-209.1kB

总结

这篇论文第一个创新点是对传统力导向算法的改进,加入了分层布局,使用整个图的平均度作为常数C,这样的结果就是度大的节点被分为一层,这里他们在布局时会被赋予较长的边距离,然后依次类推,下一层节点拥有较小的度,但是赋予的边的距离也同样变短。
另外,在交互手段上使用气泡图辅助,气泡图的圆心在当前层的节点位置,半径同样是按层间的比例,在将布局展示的同时通过气泡来辅助交互。