统一的树可视化形式描述语法 – GoTree

树可视化是可视化领域长期以来的研究热点。近40年来,研究者利用不同的视觉映射方式发展了超过300种树可视化形式(https://treevis.net/),并且广泛应用在日常生活中,例如展示电脑文件目录结构的缩进列表,反映股市中公司市值以及股价升降的Treemap。针对树可视化快速构建的问题,北京大学可视化与可视分析实验室袁晓如团队近期提出针对树可视化形式的描述性语法GoTree,支持用户从坐标系,视觉元素,以及布局三个方面描述预期的树可视化形式从而支持面向大众用户的灵活高效的可视化构建。这项成果发表于ACM CHI 2020。

在实际应用中选择的树可视化形式分析层次结构数据往往受到多方面因素的影响,包括层次结构数据的深度、大小、节点属性,用户的知识背景、交互方式、具体分析任务等等。在数据分析过程中,甚至需要在多个不同的树可视化形式之间进行切换。

目前用户可以通过多种方式构建树可视化。基于可视化工具包的方式(例如D3)具有丰富的表达性,支持各式各样的树布局算法以及灵活地拓展。然而该方法需要相关的编程基础以及前期的训练,对于非计算机专业的设计人员或者大众用户是一个极大的挑战;可视化描述性语法(例如Vega)对于构建流程与可视化结果解耦,使得用户无需了解可视化的构建步骤,只需要按照预先定义的规则描述预期的可视化形式。然而目前的描述性方法无法支持针对树可视化布局的细粒度描述,例如Vega中“slicedice”参数即代表了Treemap中slice-and-dice布局算法。交互式的可视化构建工具(例如Tableau)更加简洁直观,只需要用户在图形界面上的交互地拖拽选择等操作,然而该方法的表达能力有限,仅仅支持特定经典的树可视化形式。基于上述分析,现有的树可视化构建方式依旧存在两个问题有待解决:1) 如何快速构建多种不同的树可视化形式;2) 如何在不同树可视化形式之间灵活地切换。

GoTree

北京大学可视化与可视分析实验室袁晓如团队提出了树可视化形式的描述性语法GoTree,其本质上提供给用户一种高层次的构建方法:如图1所示,GoTree将树可视化解构为基本组件,支持用户通过描述的方式组合不同组件构建相应的树可视化,改变树可视化的某一部分组件即可在不同树可视化之间快速切换。下面本节从三个方面介绍GoTree的具体方法,1) 定义了哪些基本的树可视化组件;2) 如何将树可视化解构为基本组件;3) 如何根据不同组件构建树可视化。

图1. GoTree树可视化形式描述性语法的计算流程

定义树可视化组件

GoTree中定义的树可视化基本组件分为三类:

  • 第一类是坐标系,坐标系需要用户定义两个参数,分别是维度(二维或三维)以及类别(笛卡尔坐标系或极坐标系)。
  • 第二类是视觉元素,视觉元素包括节点以及节点之间的连边,用户可以指定视觉元素中的视觉属性,例如形状,颜色,大小等。
  • 第三类是布局,即视觉元素在坐标系中的具体位置。GoTree将布局转换为元素之间的关系,包括父子关系与兄弟关系两类。其中父子关系定义了树可视化中根节点及其子树之间的相对位置关系,兄弟关系定义了树可视化中子树之间的相对位置关系。

解构树可视化

在上述定义的树可视化组件中,坐标系与视觉元素只需要用户将预期可视化的特征转换为具体的定义,例如冰柱图树可视化形式(icicle plot)定义在二维笛卡尔坐标系下,节点映射为矩形,节点之间的连边处于隐藏状态。

本小节将重点介绍GoTree针对树可视化布局的解构方法。树形结构具有递归定义的重要特点,即一个树的子树仍然可以视作一个独立的树。很多树可视化形式也具有这个特点。我们将一个树可视化递归解构的结果定义为树单元(treeunit)。若树可视化中子树内部的布局与其他子树无关,则将其定义为单元可分(unit-decomposable)的树可视化,图2展示了单元可分的树可视化形式以及其解构结果;与之相对的是子树内部布局会受到其他子树的影响,我们将其定义为单元不可分(non-unit-decomposable)的树可视化形式,例如FlexTree, force-directed Tree。

图2. 左:单元可分树可视化形式示例及其解构得到的树单元;右:单元不可分的树可视化形式示例

一个树单元内部包含根节点(root)以及子树(subtree)。为了定义树单元内部元素之间的关系,我们引入子树组(subtree group)的定义,即根节点下所有子树的集合。我们将根节点与子树组之间的关系定义为父子关系,子数组内部的子树之间的关系定义为兄弟关系。为了布局树单元中的元素,我们沿坐标轴将父子关系与兄弟关系进一步解构(图3),其中父子关系分为包含(include),并置(juxtapose)和被包含(within)三类,兄弟关系分为对齐(align)和平铺(flatten)两类。

图3. 左:父子关系沿坐标轴解构为包含,并置与被包含关系;右:兄弟关系沿坐标轴解构为对齐与平铺关系

根据上述解构方法,节点-链接树可视化中的父子关系沿x轴为被包含关系,沿y轴为并置关系;兄弟关系沿x轴为并置关系,沿y轴为对齐关系。冰柱图中父子关系沿x轴为包含关系,沿y轴为并置关系;兄弟关系沿x轴为并置关系,沿y轴为平铺关系,如图4所示。在不同的关系中,GoTree支持用户定义具体的参数进一步确定元素的位置,具体的参数定义参见论文。

图4. 节点链接树与冰柱图可视化形式的解构结果

构建树可视化

GoTree将用户对于树可视化形式的描述转换为约束,求解约束即可计算树可视化中的视觉属性值。本节以沿x轴父子之间的包含关系以及兄弟之间的平铺关系为例,介绍将不同关系转换为约束的具体方法。其他类型的约束转换方法参见论文。

在下述约束关系中,我们将Rt,Rn,Rg,与Rs分别定义为树单元、根节点、子数组、以及子树所占据的区域。父子之间的包含关系指根节点沿x轴所占据的空间包含根节点下的子树组所占据的空间,GoTree通过增加paddingLeft以及paddingRight两个参数辅助确定元素的位置,即可以转换得到如下约束(图5):

图5. 树单元内父子之间沿x轴的包含关系图示以及对应约束

兄弟之间的平铺关系指子数组内部每个子树沿x轴所占据的空间之间没有重叠,且每个子树所占据的空间以及其间距之和为整个子数组的宽度,即可以转换得到如下约束(图6):

图6. 树单元内兄弟之间沿x轴的平铺关系图示以及对应约束

GoTree沿坐标轴定义树可视化中的关系,因此转换得到的所有约束均为线性约束,可以使用线性求解器进行求解。转换所得到的约束的特点是参数矩阵稀疏,即约束求解中涉及到大量的变量,而每个变量仅仅定义在有限的约束中,因此我们采用共轭梯度算法求解该线性约束从而保证约束的求解效率。

Tree Illustrator

基于GoTree,北京大学可视化实验室设计开发了树可视化交互构建工具Tree Illustrator。Tree Illustrator支持用户无须手写代码,即可创建或者复合超过100种树可视化形式,甚至探索发现新颖的形式。下图7为Tree Illustrator系统界面:

图7. 树可视化交互构建工具Tree Illustrator系统界面

下图展示了基于Tree Illustrator所构建的部分树可视化形式。更多树可视化形式及其对应描述性语法参见 http://go-tree.info/gallery.html

图8. 基于Tree Illustrator构建的部分树可视化形式

相关论文

GoTree和Tree Illustrator的工作被ACM CHI 2020收录为长文。该成果以北京大学可视化与可视分析实验室博士生李国政为第一作者,袁晓如为通讯作者。该工作得到国家重点研发计划项目和国家自然科学基金的支持。国际学术会议CHI 全称ACM Conference on Human Factors in Computing Systems,是人机交互领域的最高学术会议(CCF-A类会议)。2020年ACM CHI共收到会议论文投稿3126篇,收录760篇,录取率为24.3%。会议原定2020年4月25-30日在美国夏威夷举办。由于疫情影响,会议取消现场活动,论文将按照原定计划4月25日ACM在线图书馆上线发布。

[1] Guozheng Li, Min Tian, Qinmei Xu, Michael J. McGuffin, and Xiaoru Yuan, “GoTree: A Grammar of Tree Visualizations”. In Proceedings of ACM Conference on Human Factors in Computing Systems (CHI 2020), Honolulu, Hawaii, USA. April 25-30, 2020.

结语

本文介绍了近期北京大学袁晓如团队提出的树可视化形式的描述性语法GoTree,将各种外观不同的树可视化形式从坐标系、视觉元素及布局三方面进行逻辑划分,支持用户可以对预期的可视化从坐标系,视觉元素,以及布局三个方面进行细粒度地描述,将其转换为约束,进而求解构建相应的树可视化。基于GoTree描述性语法设计的Tree Illustrator交互构建系统支持用户无需编写代码,即可创建超过100种树可视化形式,复合树可视化形式,甚至探索发现新颖的形式。

更多信息请访问:
http://go-tree.info

其他相关图或树可视化工作可以访问北京大学图可视分析系列网页:
http://vis.pku.edu.cn/graphvis

其他相关可视化快速构建工作可以访问北京大学可视化交互敏捷构建系列网页:
http://vis.pku.edu.cn/agilevis

评论关闭。