层次化数据是一种常见的数据类型,比如计算机文件系统、组织结构、生物分类信息等.层次化数据的可视化一直是信息可视化领域的重要研究内容^{[1, 2, 3]},相关工作主要分为两类:采用显式(explicit)表达的节点连接图(node-link diagrams)和采用隐式(implicit)表达的空间划分方法(space-filling methods)^[4].一般而言,节点连接图将节点间的父子关系显式地表示为直线、弧线或者曲线,能够清晰地展现节点间的上下级关系.但其空间利用率一般较低,难以进行大规模层次化数据的可视化^[5].以树图^[6]及其变种^{[7, 8, 9, 10]}为代表的空间划分方法使用具有一定面积或体积的块或体来表示数据中的个体节点,并以这些块或体在空间上的包含关系来表示节点间的上下级关系.与节点连接图相比,空间划分方法能够很好地利用可视空间,便于处理大规模的层次化数据.但它们一般将大部分空间用于叶子节点的呈现,导致非叶子节点间的上下级或相邻关系难以识别^[11].

为了结合上述两类方法的优势,研究者们提出了一些改进方案,如,将节点连接图和空间划分相结合的方法^{[12, 13, 14, 15]}、将数据节点表示成圆的圆形树图方法^[16]等.其中,圆形树图方法具有空间利用率较高,并清晰呈现节点间层次结构的优点,得到了极大的重视.但现有的圆形树图生成方法采用启发式的布局算法,空间利用率不是很好^[17],并且其布局一旦完成,则很难进行局部的动态调整,限制了数据的动态更新及交互可视化处理.

本文提出一种新的圆形树图生成方法,该方法以一种变分圆排列算法进行圆的布局优化.与传统方法相比,新方法有更高的空间利用率,能够更清晰地展示节点间的层次结构.特别是,新方法的布局算法易于对当前的布局进行动态调整,由此可方便地支持层次下行、层次上行与焦点+上下文等自然交互方式.新方法在生物分类数据上的应用实践表明了其有效性,一个实例如图1所示(有6层数据、2 516个节点,右下角图例表示层数).

图1(Fig.1)

图1 生物分类数据的变分圆形树图表示 Fig.1 Variational circular treemaps for the biological taxonomic dataset

· 矩形树图

矩形树图是一种经典的空间划分方法^[6],以矩形嵌套的形式对一个矩形区域进行递归划分.划分后的每个矩形区域表示一个数据节点,其子区域对应于其子节点.矩形树图空间利用率高,易于理解与实现.但它有以下缺点:容易产生狭长矩形,导致划分区域纵横比(aspect ratio)不一;只能对矩形区域进行划分,不适用于其他形状区域;叶节点的显示占用了大部分空间,导致非叶节点之间的层次结构表现不清晰.为了克服矩形树图的这些缺点,已有多种改进策略.Bruls等人提出正方化树图(squarified treemap),用接近正方形的矩形代替狭长矩形的方法改进划分区域纵横比不一的状况^[18].Bederson等人进一步提出了有序树图,以改进正方化树图的布局顺序^[19].Itoh等人提出了两种基于Delaunay三角网格的矩形排列算法,改善了纵横比不一的情况^[20].Balzer等人提出了Voronoi树图,引入Voronoi图进行空间分割^[21].Voronoi树图能够对任意形状区域进行划分,有较高的空间利用率和较统一的划分区域纵横比,但其层次结构仍较难清晰地呈现.Jarke等人提出了Cushion树图,对不同划分区域设置不同的明暗阴影,以强化层次结构的表现^[9].Hilbert/Moore树图通过“漂移定位”度量(location drift metric)来提高空间分布稳定性^[8].关于这些方法的详细情况,请参考综述文章^{[2, 22, 23]}和网站^[24].

· 圆形树图

圆形树图或称为卵石图(pebble map)^[16],是由Wetzel首次提出的一种空间划分类层次化数据可视化方法.该方法用圆表示层次化数据的节点,将数据节点的值映射为对应圆的面积大小.最外围的圆表示根节点,下层节点的圆置于上层节点的圆内.与传统树图相比,圆形树图具有以下优点:各划分区域保持一致的纵横比;能够清晰地呈现节点间的层次结构;便于特定节点圆的选择操作,因为圆与圆之间的空白区域为用户提供了足够的交互空间.目前,已有很多圆形树图的实际应用,比如,一种圆形树图的变种CropCircles已应用于网页本体(Web ontologies)的交互可视化^[25],Fischer等人将圆形树图与一种圆形符号相结合以表示层次化时序数据^[26].对于圆形树图的布局,Wang等人提出了一种启发式的圆布局算法^[17].该方法简单且易于实现,但不能保证最优的空间利用率,且很难对已完成的布局进行局部调整,因此无法支持焦点+上下文等自然交互操作.任磊等人提出了圆形树图的焦点+上下文交互方法^[27],通过对圆心进行三角网格剖分,并跟踪网格邻居的方法来保证变形前后的上下文一致性,然而其布局的空间利用率仍然不是很高.

本文提出的变分圆形树图具有圆形树图的固有优势,同时,基于变分优化的布局算法,能够显著提高空间利用率,可在任意形状的显示区域内进行布局,并支持焦点+上下文等自然交互操作.

变分圆形树图的算法概图如图2所示.用户可指定圆形或者任意多边形作为显示区域,用于表示层次化数据的根节点,其他节点用圆表示.各非叶节点通过变分圆排列方法对其孩子节点进行优化布局,在此,各孩子节点可以具有不同的权重值,权重值反映这些孩子节点对应的圆在该节点的圆内的面积比例.层次化数据的每个节点往往关联一组节点属性,这些属性可根据应用需求进行组合以进行权重赋值,或直接由用户交互地进行权重赋值.为每个节点的权重赋值后,再对同一父节点的兄弟节点的权重进行归一化处理(本文中假定同一层兄弟节点是无序的).

图2(Fig.2)

图2 框架概览 Fig.2 An overview of our framework

在完成各节点权重赋值后,布局算法从根节点开始以广度优先的方式递归地处理各个层次节点的圆的布局.在此,同一父节点的兄弟节点在其父节点的圆内进行它们对应的圆的最大化,并且相互之间不重合,以尽可能地提高空间利用率,详见第2.1节.如图3所示,变分圆形树图采用嵌套圆的方式表示层次化数据的各节点,保持了传统圆形树图的优点.同时,该树图中不同层之间留有一定的空隙,便于清晰地表达层次结构,也为用户交互提供了较大的空间, 便于拾取选择操作.

图3(Fig.3)

图3 变分圆形树图布局算法 Fig.3 Variational circular treemaps layout algorithm

同一父节点下各兄弟节点的对应圆的布局,实质上是一个圆排列问题.这是一个典型的组合优化问题,可以描述为:在给定大小的圆形或任意多边形区域中,如何分布一组给定大小比例的圆,使得这组圆在给定区域中的总面积最大,并且互相不重叠.

假设给定区域W$ \in $R²和半径为$\{ {r_i}\} _{i = 1}^n > 0$的一组圆$\{ {C_i}\} _{i = 1}^n$.为所有的圆$\{ {C_i}\} _{i = 1}^n$引入统一的缩放因子k$ \in $R⁺,使C_i变为kC_i.这样,在区域W中对圆$\{ {C_i}\} _{i = 1}^n$进行圆排列布局问题可表示为以下最优化问题:

目标:Maximize k

约束:kC_i⊆W,i$ \in ${1,…,n}

kC_i$\cap $kC_j=∅,i,j$ \in ${1,…,n},i≠j

在此,圆$\{ {C_i}\} _{i = 1}^n$在区域W中的一个排列可表示为$\{ {x_i}\} _{i = 1}^n$,其中,x_i是C_i的圆心坐标.这样,上述优化问题的第2条约束可以改写为||x_i-x_j||-kr_i-kr_j≥0.

本文基于Aurenhammer^[28]提出的能量图(power diagram)处理上述圆布局问题.对于一个区域W$ \in $R²以及一组带权重的站点(site),其能量图是区域W中关于这些站点的一个空间划分,保证每个站点对应的单元W_i中的点到该站点的能量距离(power distance)比到其他任何站点的距离都要小.因此在R²空间中,我们将圆心为x_i、半径为r_i的圆对应于权重为${w_i} = r_i^2$、位置为x_i的能量图站点,即可生成一个能量图.在能量图的各个分区中内嵌一个最大内接圆,即可完成兄弟节点在其父节点的圆内的圆形布局.

本文提出的变分圆排列算法类似于计算CVT(centroidal voronoi tessellation)^[29]采用的Lloyd方法^[30],即,迭代地更新能量图并增大缩放因子k,直至达到最优化的要求,算法停止,输出各圆的位置,并将此时的k值作为所有圆的缩放因子.为保证各个分区单元中最大内接圆的唯一性,若某些单元W_i中有平行边的情况,比如对于一个矩形区域W_i,它有无数多个最大内接圆,本文则随机地确定一个最大内接圆.具体算法的伪代码见算法1.

算法 1. 变分圆排列算法.

输入:区域W$ \in $R²,权重为$\{ {w_i}\} _{i = 1}^n$的节点圆$\{ {C_i}\} _{i = 1}^n$,缩放因子k$ \in $R⁺,初始圆排列$\{ {x_i}\} _{i = 1}^n{\rm{.}}$

输出:$\{ {x_i}\} _{i = 1}^n$和k.

步骤:

1. 对于圆排列$\{ {x_i}\} _{i = 1}^n$,构造W中$\{ {x_i}\} _{i = 1}^n$对应的封闭能量图$\{ {\Omega _i}\} _{i = 1}^n{\rm{.}}$

2. 为每个单元W_i计算其最大内接圆${\tilde C_i},{\tilde C_i}$圆心为${\tilde x_i},{\tilde C_i}$半径为${\tilde r_i} = {\max _{q \in {\Omega _i}}}{\min _{p \in \partial {\Omega _i}}}||p - q||$.此处的¶W_i表示W_i的边界.

3. 令$k' \leftarrow k,k \leftarrow \min \left\{ {{{\tilde r}_i}/\sqrt {{w_i}} } \right\}{\rm{.}}$

4. 如果(k'-k)/k≤e,则转到步骤5;否则,令${x_i} \leftarrow {\tilde x_i},i = 1,2,...,n{\rm{,}}$转到步骤1.

5. 结束,输出当前$\{ {x_i}\} _{i = 1}^n$和k.

作为算法1的初始输入,缩放因子k以及初始的圆排列$\{ {x_i}\} _{i = 1}^n$都在算法初始时给定.初始缩放因子k根据给定区域W的大小设定一个足够小的值.对于圆形边界,我们通常先将其转换为半径为1的单位圆,然后把k设为10^-6/max_i{w_i}.对于初始圆排列$\{ {x_i}\} _{i = 1}^n{\rm{,}}$采用随机放置的方式设定.

在算法的迭代过程中,每次迭代都重新计算当前的能量图,使得缩放因子k越来越大,并更新当前的圆布局.当k值不再增加时,算法终止.步骤4中的阈值e用于终止判断.通常不需要把阈值e设置得非常小,以较好地平衡算法执行效率和质量,并可以防止k非常接近阈值的时候出现过度迭代的现象.在实现中,我们一般将e设为10^-3.图4示意了该算法的迭代过程(虚线表示能量图).

图4(Fig.4)

图4 同层5个节点的圆排列过程 Fig.4 Disk packing process for five nodes in one level

值得注意的是,圆布局问题已被证明是一个NP-hard问题^[31],算法1提出的优化过程只能达到局部最优,并不能达到全局最优.关于本算法更详细的技术细节,参见文献^[32].

在圆形树图中,随着深度和节点数目的增加,用于表示深层节点的区域会越来越小,导致它们难以辨认.为此,我们提出两种交互技术,以使所关注的数据得到放大呈现,便于用户观察深层节点.这两种交互技术,一种是焦点+上下文交互技术,或称为鱼眼视图效果;另一种是层次下行、上行操作.

在焦点与上下文交互中,首先选取特定焦点区域,之后在保持上下文的前提下逐步增大焦点区域的范围.在圆形树图中,通过点击上下层圆之间的空隙,可以方便地选取特定节点圆作为焦点与上下文交互中的焦点圆.然后,交互过程中的鱼眼视图变形效果,按以下方式实现:逐步增大焦点圆的权重值,并保持其兄弟节点的权重值不变;随后调用第2.1节的布局算法1对该层节点进行圆形布局.

由于变分圆形树图各节点具有统一的纵横比,只需对焦点圆所在层的节点圆进行重新布局,即可将变形效果自然地传递到子层视图.在此,使用堆栈记录鱼眼变形过程,可以很容易地实现回溯变形.图5给出了一个鱼眼变形的实例(焦点圆用粗黑线突出显示).

图5(Fig.5)

图5 鱼眼变形样例 Fig.5 Demo of fisheye distortions

为了实现鱼眼视图变形,将用户指定的焦点圆C_j的权重由初始权重w_j逐步增大到目标权重w_t,我们引入一个参数j用于描述视图变形程度,定义为j=w_t/(1-w_j+w_t),w_j≤j<1,即,焦点圆权重增大到目标权重后,其对应圆相对其父节点的圆的面积比例.这样,在用户指定参数j以后,目标w_t可由此公式计算得到.具体实现情况,见算法2.

算法 2. 鱼眼视图变形算法.

输入:在区域W中,权重值为$\{ {w_i}\} _{i = 1}^n$的节点圆$\{ {C_i}\} _{i = 1}^n$的合法圆排列为$\{ {x_i}\} _{i = 1}^n$;焦点圆C_j的权重为w_j;变形参数j和目标权重w_t=j(1-w_j)/(1-j);权重递增步长J;空堆栈S.

· 鱼眼变形过程

1. 将节点圆$\{ {C_i}\} _{i = 1}^n$当前圆排列压入堆栈S.

2. 如果w_j>w_t,则返回.

3. w_j←(1+J)w_j.

4. 调用算法1对节点圆$\{ {C_i}\} _{i = 1}^n$进行布局.

5. 显示当前布局,转至步骤1.

· 回溯变形过程

1. 若堆栈S为空,则返回.

2. 弹出堆栈S栈顶元素H.

3. 显示栈顶元素H对应的布局,转至步骤1.

需要注意的是:参数j由用户指定,取值范围为[w_j,1).图5中,参数j取值为0.8.参数J用于描述焦点圆在每次迭代中权重增大的比例,这里的取值是0.01.

变分圆形树图中的层次下行/上行可实现视图在不同层次之间的切换.由于该树图中各节点具有统一的纵横比,并且不同层之间留有一定的空隙,因此可以非常容易地完成对某层视图节点的选择操作.图6给出了一个层次下行/上行的实例(焦点圆用粗黑线突出显示),在此,最上层视图中并没有显示所有的深层视图,用户可以在层间切换过程中查看更多的深层视图.

图6(Fig.6)

图6 层次下行/上行样例 Fig.6 Demo of drill-down & roll up

本节将变分圆形树图应用于生物分类数据的可视化中,以验证本方法的有效性.实验用数据集来自于生物大百科全书(EOL)^[33]和综合分类学信息系统(ITIS)^[34].EOL是一个以收集生物信息为目的的开放Wiki平台,已有130万个条目信息.ITIS按照Linnaean分类法将EOL生物信息分为9层,分别为Kingdom,Phylum,Class,Order,Superfamily,Family,Fenus,Species和Infraspecies.

本文算法用C++语言实现,主要调用了CGAL^[35]用于计算能量图.

实验中尝试了多种节点权重值计算方式,如孩子节点的数目、孩子叶节点的数目、节点的深度等.实验中发现,孩子节点的数目作为权重从美学角度来讲是一个较好的选择.为每个节点确定权重后,我们归一化处理共享同一父节点的兄弟节点的权值.以生物分类数据的第2层Kingdom层为例,所有的生物类别在本层分为5个节点,归一化后的权重值分别为Animalia(w=0.686),Monera(w=0.058),Plantae(w=0.098),Fungi(w=0.079)及Protozoa(w=0.079).

变分圆形树图对生物分类数据可视化的整体视图见后文图10(d).实验中,计算第2层5个节点的布局花费时间0.14s,第3层51个节点花费时间0.73s,第4层170个节点花费时间3.44s,第5层487个节点花费时间8.78s,第6层1 803个节点花费时间20.17s;对所有2 516个节点进行布局共花费33.26s.上述实验数据是从一台CPU主频为3.10GHz的台式机上测试得到的.

本方法与传统圆形树图相比在空间利用率方面具有明显优势.图7比较了本方法和传统圆形树图方法对同一个数据节点可视化的效果(取自kingdom Fungi的Ascomycota,共43个孩子节点).对于生物分类数据的前6层圆布局,我们计算了该层圆面积总和与根节点对应区域面积的比值,见表1.其中,第2列和第3列分别给出了传统圆形树图方法和本方法的比值,最后一列给出了本方法相对于传统圆形树图的改进幅度.

图7(Fig.7)

图7 一层数据节点的比较 Fig.7 Comparison with one level data

表1(Table 1)

表1 传统圆形树图和本文方法的空间利用率的比较Table 1 Comparisons on the space utilization ratios between the original circular treemaps and our method 层次 传统方法 本文方法 提高(%) 2 0.614 3 0.614 3 0 3 0.421 2 0.479 0 14 4 0.275 2 0.322 1 17 5 0.180 5 0.226 7 26 6 0.105 0 0.156 2 49

表1 传统圆形树图和本文方法的空间利用率的比较 Table 1 Comparisons on the space utilization ratios between the original circular treemaps and our method

图8和图9(焦点圆用粗黑线突出显示)分别给出了层次下行/上行和焦点+上下文交互的过程.

图8(Fig.8)

图8 层次下行/上行操作 Fig.8 A drill-down & roll-up process

图9(Fig.9)

图9 鱼眼效果应用于动物门的节肢动物门 Fig.9 A fisheye process to focus on the Arthropoda in Animalia

在图8中,最左边的视图为生物分类数据最上层视图,用户可以采用层次下行/上行的交互方式逐步查看Animalia,Onychophora以及Peripatopsidae Bouvier 1907层次的视图.

图9给出了对Animalia节点中对Arthropoda节点进行细节查看的鱼眼视图变形效果.在变形过程中,我们能够保持变形的平滑过度,并且保持兄弟节点圆的相对位置关系和相对大小比例关系.

本方法也与经典正方化树图、加权能量Voronoi树图以及传统的圆形树图进行了比较.图10中给出了生物分类数据应用4种方法进行可视化的结果比较.为公平起见,采用统一的颜色编码方式与节点权重值计算方式,即利用所包含叶子节点的个数定义节点权重.由对比结果可知,与另外两种树图方法相比,两种圆形树图方法能够清晰地显示生物分类数据的层次结构,因为正方化树图和加权能量Voronoi树图几乎将所有的空间用于表示叶子节点,不便于层次结构的辨识.此外,本文方法与传统的圆形树图相比,空间利用率更高.实际应用中,本文方法中的颜色编码也可以选择其他方式,比如,可以用颜色来表示节点深度等,以获得更好的视觉效果.

图10(Fig.10)

图10 正方化树图、PW Voronoi树图、圆形树图和变分圆形树图应用于EOL数据集的比较 Fig.10 Comparison with the squarified treemaps,PW Voronoi treemaps,original circular treemaps, and variational circular treemaps for the EOL data

变分圆形树图对于边界的形状并无要求,可非常自然地生成圆形树图与Voronoi树图的混合树图,如图11所示,其中包含5层1 706个节点的数据.

图11(Fig.11)

图11 变分圆形树图与Voronoi树图的混合形式 Fig.11 A hybrid of variational circular treemaps and Voronoi treemaps

本文提出的变分圆树形图生成方法将求解多个半径不同的圆的布局问题与组合优化中的圆排列问题相结合,显著改善了圆形树图的空间利用率.该方法除了能够更清晰地展示层次结构以外,还便于进行层次下行、层次上行与焦点+上下文等自然交互的可视化处理.新方法易于实现,计算快捷,便于进行拾取选择操作,在多点触控桌面平台上有很大的应用潜力.