数据可视化是一个跨学科的领域,它将数据信息和知识转化为视觉形式,能够充分发掘人在视觉感知和模式识别方面的优势,帮助人们发现和理解大规模的复杂数据中潜在的规律和特征.数据可视化为人们提供了一种快速进行信息传递和知识发现的方式和手段.在数据分析领域,可视化既是数据分析的关键技术也是数据分析结果呈现的关键技术^[1].

树是对现实事物关系的一种抽象,树所代表的层次数据在生活和工作中极其常见,比如生物进化树、系统树图、文件组织结构、公司人员管理关系、家谱图等.Shneiderman^[2]根据信息的特征把信息可视化分为一维信息(1-dimensional)、二维信息(2-dimensional)、三维信息(3-dimensional)、多维信息(multidimensional)、层次信息(hierarchical)、网络信息(network)、时序信息(temporal)可视化.树是层次信息的直接形式,树可视化作为信息可视化中的一个重要分类,广泛应用在生产生活以及科学研究中.

“比较”在可视分析中不是一个单一的任务,相反地,它需要用户在一组相关对象上进行一系列操作从而完成一组任务,比如寻找相似、差异分析等^[3].由于树特殊的结构特点,树比较可视化在各个领域都有广泛的应用.根据数据源的不同,树比较可视化有4个主要的应用领域:生物信息学(bioinformatics)、层次分类(hierarchical classification)或分面分类(faceted classifications)、模式映射(schema mapping)以及计算机软件开发领域^[4].

在生物信息学中,对一组生物进行物种关系分析,可以生成一组不同的模型,用系统发生树(phylogenies)和分类树(taxonomies)表示.每个模型都能反映这组生物在生物进化或者生物特性上的相似性.通过比较来分析模型的差异或者对模型进行整合修改,能够增加生物学家对物种的了解,从而建立一个更优的模型^{[5, 6, 7, 8, 9, 10]}.

对数据进行层次分类或者分面分类时,通常选择一组能够表征数据特性的属性,根据属性值逐层分类,进而形成一个树结构,树的每个叶节点代表一类数据,从根到叶节点的路径代表了这个类别在每个属性上的值的归属情况.而用于分类的属性不同或者使用的属性顺序不同,生成的树结构会有较大的差异,选取合适的属性和顺序对于用户理解数据有很大的帮助.文献^{[11, 12, 13, 14]}中使用的美国联邦预算数据、肺癌发病数据等,都是采用选取一组属性对数据逐层划分的方式生成树结构,再进行可视分析.一些数据属性本身就能代表层次信息,比如在NBA球员数据^[13]中,球员球队所在的分区(东部/西部)、赛区以及城市等属性,在地域上形成了一个层次结构,将球员的数据放在层次结构中比较,能够清晰地表现球员在地域上的分布特点.

对层次异构数据的比较是树比较可视化的直接应用,其关键在于寻找数据中节点的最优匹配.树比较可视化一方面有助于找到最优匹配,另一方面也是一种最直观的结果展示方法.

在软件分析以及源代码分析中,代码的包结构以及代码的语法树都是树结构,所以代码可视化多以树的形式呈现.Beck等人^[15]用树比较的方法帮助用户分析软件结构;Telea以及Wettel等人^{[16, 17, 18]}将树比较应用在版本管理系统中,分析代码演变过程和进行错误追踪^[19];Leschke等人^[20]用树比较的方法分析目录结构变化,以此来协助数字取证.

除此之外,在涉及层次数据的可视化工作中,大多有比较的任务参与其中.而不同的数据语义和比较任务需要不同的比较方法.研究树比较可视化有助于合理地进行方法选择,因此,本文对树比较可视化方法进行文献综述,以期为树比较可视化方法选择提供参考和依据.

树可视化方法根据节点关系的表现形式分为4类:缩进形式、点线链接形式、邻接形式和空间填充式.

使用缩进的形式表示树结构时,如图1(a)所示,同一级的节点有相同的缩进,每个子节点比其父节点有多一级的缩进.缩进形式的树可视化方法常应用在文件浏览器中,使用缩进来表现文件的目录结构,用户使用折叠和展开操作,可以快速地对文件结构进行浏览并定位文件的位置.缩进形式的缺点在于可扩展性不高,文件目录较多时,一次只能显示一部分,给文件定位带来困难.在实际的应用中,可通过添加搜索功能解决定位困难的问题.

点线链接形式是最基本的树的表示形式,它是用连线表示节点父子关系的一种可视化手段,如图1(b)所示.在点线链接形式中,每个点表示一个实体对象,实体对象之间的关系用它们之间的连线表示.点线链接形式的优点在于它能够清晰地表达数据的层次结构;缺点在于当数据量增大时,节点数量随着深度的增加呈指数级增长,接近根节点的位置节点较少,而远离根节点的位置节点较多,使得空间利用率不高并且空间分配不均匀,远离根节点的位置容易形成聚集.气泡图^{[21, 22]}采用的方式是将父节点放在一个圆形的中间,其子节点环绕在周围,递归采用相同的方式布局子节点,直到叶子节点.气泡图在一定程度上提高了空间利用率.其他还有放射布局、双曲线布局以及雷达布局等方式,都通过改变子树延伸的方向来弥补普通从上到下或从左到右布局空间利用率低的缺点.

图1(Fig.1)

图1 树可视化的基本表示方法 Fig.1 Basic representation of tree visualization

冰柱图(icicle plot,如图1(c)所示)是使用邻接关系表示节点父子关系的方式.子节点在父节点的一侧与父节点相邻,所有节点的排列沿某个方向延伸,而叶子节点深度的不同,使得节点排列产生锯齿的形状,很像冬天屋檐下的冰柱,冰柱图因此得名.该方式牺牲了一定的结构性,但是提高了空间利用率;缺点在于:当子树的深度差异比较大的时候,在不同分支下会形成很大的锯齿,同样存在空间利用不均的问题.

树图(treemap)^[23](如图1(d)所示)是空间填充形式的代表,它用图形的包含关系来表示树节点的父子关系,能够将空间利用率最大化.不足之处在于不能清晰地表示树的层次结构,虽然可以通过矩形边框特殊化的方式来增强层次信息,但是会浪费一定的空间,当层次结构复杂的时候效果也不理想.Cushion树图^[24]通过添加阴影效果的方式来强调层次信息.如果数据层次较深且数据较多,低层的元素可能会退化成接近像素点矩形,不容易辨认.Squarified树图^[25]具有良好的纵横比,有序树图(ordered treemap)^[26]能够保持节点的布局顺序同数据的存储顺序的一致性,避免局部数据改变时其他节点的位置偏移过大而失去节点的上下文.

Jürgensmann等人^[27]使用可视化的方式对树可视化方法进行了总结.肖卫东等人^[28]总结了层次信息可视化技术,并提出了一个基于表现-维度的分类框架.TreeVis.net^[29]从维度(dimensionality)、表现方式(representation)以及对齐方式(alignment)这3个方面对树可视化文献建立了索引.Shneiderman^[30]阐述了树图的种类以及发展.张昕等人^[31]对不同的树图布局算法从纵横比、稳定性、可读性等几个方面进行了比较.Schulz等人^[32]从维度、点表示形式、边表示形式以及布局方式这4个方面讨论了层次数据可视化方法的设计空间(design space).表1中列出了不同的树可视化方法的优缺点.

表1(Table 1)

表1 树可视化方法比较Table 1 Comparison of tree visualization methods 形式 方法/布局 优点 缺点 缩进形式 类的加权方法数 方法简便且易于实现,可以使用纯 文本 数据量大时需要滚动操作,容易失 去上下文,空间利用率低 点线链接 上下/左右布局、径向(radial)布局、 气泡图、H-Tree、正交布局、Cone 树 能够直观地表达数据的结构信息 节点数量随深度增加呈几何级数 增长(可以使用双曲布局、变形、节点过滤等方式解决) 邻接形式 Icicle Plot,Sunburst 相对于点线链接形式,省略了边的 绘制,提高了空间利用率 单一方向上增长过快,树内部结构 差异较大时锯齿状明显,空间利用 不均衡 空间填充 Slide-and-Dice布局、Squarified 布局、Ordered树图、Voronoi树图、 Contrast树图 空间利用率高,父节点属性值和子 节点属性值之间有加和关系 对层次结构的表达不明显

表1 树可视化方法比较 Table 1 Comparison of tree visualization methods

树比较可视化是树可视化中的一个重要内容,从被比较的树的数目角度,可以分为树内比较、两树比较和(三树及)多树比较,在这3类中,以两树比较最为常见;从数据特点角度可以分为静态树比较和动态树比较;从比较的任务角度可以分为结构比较和属性比较,数据不同,任务的侧重也不同.完成可视比较的任务需要恰当的方法支持^[3],根据其展示方式主要分为3类:(1) 并置(juxtaposition);(2) 合并(superposition);(3) 动画(animation).前两种方法主要侧重于用树可视化的方法展示数据,通过空间位置、颜色形状映射等方式展现每个实体对象的关联以及属性值差异;动画的方式则多用于动态树的比较.

根据不同的需求和数据特点,树的比较可以划分为不同的任务类型.2003年的信息可视化大赛以树的比较为主题,将比较任务分为拓扑结构比较和属性比较.在拓扑比较中,关注树的整体差异、局部差异,节点的增加、删除以及子树之间的差异.树是数据的抽象,树的每个节点一般对应数据中的一个实体对象,属性的比较主要是比较实体对象的属性值变化.比如在某个属性或者某几个属性上,树内部或树之间是不是有明显的差异,值是增加还是减少等等.具有不同特性的数据对应的比较任务的侧重点也不尽相同.

在前人的一些工作中,对可视化中的比较做出了分析和总结:Gleicher等人^[3]从比较方法的设计和交互等方面对信息可视化中的比较进行了总结;而Pagendarm等人^[33]将比较的形式引入到科学可视化,分析了数据层面和图像层面的比较在科学可视化中的应用;Graham和Kennedy等人^[4]对多树可视化进行了文献综述,他们从可视化的树的数量角度出发,分析了对单棵树、两棵树以及多棵树的不同的可视化方法.本文在这些工作的基础上,从展示方式入手,结合其他分类方法对树比较可视化方法进行了总结.

本文第2节从表现方式的角度详述并置、合并和动画的树比较方法.第3节介绍树比较可视化中的交互.第4节讨论树比较可视化中所面临的挑战以及发展.最后,第5节对全文进行总结.

树比较可视化方法按照其布局方式分为并置、合并、动画这3种.表2列出了本文涉及到的主要文献.

表2(Table 2)

表2 文献分类Table 2 Classified papers 方法 主要文献 并置 直接连接 视觉映射 矩阵 [11, 16, 18, 34] [7, 8, 10, 35, 36] [15, 37, 38, 39, 40, 41] 合并 直接比较 显式编码 [9, 12, 13, 14, 17, 19, 20, 42, 43, 44] [14] 动画 - [13, 45, 46]

表2 文献分类 Table 2 Classified papers

并置的比较方法是指使用一般的树可视化方法将比较的数据直接可视化放在同一个视图中,比较通过观察对比的方式完成.并置是最直接的方式,实现上也比较容易,当数据量增多时,方法上也不需要做太多的修改,易于扩展^[3].其优点在于,它能够引导用户关注比较的树中的对应节点,适合在比较的树结构差异比较大的情况下比较其中的相似部分,所以并置常用于结构比较.并置的缺点在于,当比较的树结构相似度很高的时候,相同的部分会在每个树结构中都绘制一次,这些冗余导致空间利用率低下,同时增加了寻找对应节点的难度.

直接依赖用户的观察比较会给用户造成记忆负担,用户需要在并置对象上的比较,因此用并置的方法进行树比较的时候,通常会为用户提供视觉暗示(visual cues)帮助理解数据的关联^[47].因此,并置的比较方式的核心是依靠视觉线索传达比较对象之间的关系^[35].

为用户提供视觉线索常用的方式有两种:一种是直接连接法,一种是视觉映射法.此外,矩阵也是一种特殊的并置比较方式.

直接连接法中,用连线将匹配节点连接,用以引导用户建立起视觉连接和数据实体连接的关系.而连线的透明度可以用来度量相似度,颜色可以编码类别等信息.

Chevalier等人^[18]使用带注解的语法树可视化C++源代码的演变过程,以此来检测不同代码片段的变化.作者根据语义信息和结构信息将C++代码整合成为树形结构,用连线连接代表相同代码片段的节点,通过比较来分析代码中哪些地方有改变,哪些地方没有改变.如图2(a)所示,容易看出,代码段C和J在右侧版本中被删除而在右侧版本中新添加了代码段M.

图2(Fig.2)

图2 并置-直接连接 Fig.2 Juxtaposition-Direct linking

当采用直接连接法时,连线较多会使得整个可视化显示变得混乱,不易于数据的理解.边捆绑(hierarchical edge bundle,简称HEB)技术是一种常用的处理方式,将位置上接近的连线进行一定程度的合并,能够减少连线过多造成的视觉混乱.周虹等人^[48]详细介绍了边捆绑在信息可视化中的使用.Holten等人^[11]把边捆绑应用在源代码比较可视化中,使得两棵树结构的分离和偏移更加明显(如图2(b)所示).Telead等人^[16]在他们的工作CodeFlow中,对C++源代码进行可视化时,同样使用了HEB技术,用来比较不同代码中的结构差异.

Stewart等人^[34]将并置的比较方法应用在三维空间.他们使用了类似平行坐标的展开方式对生物学中的系谱树进行比较.如图2(c)所示,每个切片代表一个系谱树,使用横向的连线将所有系谱树中的对应叶子节点进行连接,并用颜色表示这些节点所代表的类别.这种方法侧重于比较不同系谱树之间的关系,不足之处在于:由于采用了三维的可视化方法,用户无法方便地查看单个系谱树的结构特点,需要借助辅助视图分析单个系谱树.

视觉映射法中,一般使用相同的颜色或者图像符号来表示两棵树中的对应节点,以此建立起两棵树之间的联系.

为了帮助生物学家理解不同系谱树之间的复杂关系,Munzner等人^[8]设计了TreeJuxtaposer,将两棵系统发生树并列放置并计算节点的对应关系,根据计算结果高亮结构差异(如图3所示),同时辅以刷选(brushing)的交互方式,帮助用户寻找其中的相似部分.在TreeJuxtaposer中,用户可以动态查询符合某个条件的节点并高亮显示,以此来进行子结构的相似性比较.不同的系谱算法产生的系谱树具有相同的叶子节点,所以Nye等人^[7]在比较不同的算法产生的系谱树时,依照叶子节点的对应关系对每个分支计算出一个拓扑分数,然后根据拓扑分数在分支中寻找最优的一对一匹配.将两棵树并列放置后,用相同的颜色编码对应分支.InfoZoom^[36]将树结构数据转化成表格的表现形式,每个叶子节点被表示成一列,从根节点到叶子节点用行属性表示,将两棵树并行放置标示出不同的格子进行比较.在此基础上,通过缩放来解决当数据量较多时,每个单元格分配到的面积太小而无法识别的问题.而在DoubleTree^[10]中,采用上下结构放置两棵树,当用户选择其中一棵树的节点时,另一棵树中的对应节点也高亮显示,一个节点存在多个对应节点或不存在对应节点时,使用不同的高亮颜色.在图4中,当选择上方节点时,下方与之对应的节点会高亮显示.

Zhao等人^[35]在研究自然语言处理(NLP)中的语言解析器(discourse parser)时,为了改善算法的准确性,需要分析和比较不同的算法或者相同的算法不同参数的结果,为此提出了DAViewer的可视化原型.

DAViewer中使用了基于修辞树(rhetorical structure tree)的文档组织结构可视化.根据算法的分词结果和词语的属性分类构建树形结构,将这些结果平铺放置来比较.DAViewer使用了冰柱图(icicle plot)和系统树图(dendrogram)的结合体来表现树结构.将所有叶子节点对齐,扩张其他节点在冰柱图中的宽度,就可以很方便地进行列比较.在显示的树结构中,用节点的颜色编码相似度,冰柱图中节点的底色表示计算的错误率,这样,冰柱图同时可以作为一个热力图,表示算法在不同子结构上的计算精确度(如图5所示).

图3(Fig.3)

图3 用相同的颜色表示对应的节点,主要进行结构比较 Fig.3 Using color to encode corresponding nodes,structure comparison mainly

图4(Fig.4)

图4 Double tree[10] Fig.4 Double tree[10]

图5(Fig.5)

图5 DAViewer[35] Fig.5 DAViewer[35]

在树比较中,矩阵作为一种特殊的并置方法,有两种使用方式:一种是将节点平铺为矩阵的两个轴进行节点间的比较,另一种是作为总览图进行总体相似度的比较.前者多用于两树比较,而后者用于多树比较.

通过将比较的树节点作为矩阵的横轴和纵轴,在矩阵中可以比较对应节点的关系.如果将同一个树的节点作为横轴和纵轴,则可以进行树内比较.根据树的内部节点是否参与比较,可以选择缩进方法或者冰柱图^[4]. Ghoniem等人^[37]阐述了在进行大规模图可视化时矩阵方法的优势,矩阵方法侧重于对节点的比较,相对于其他方式,矩阵的方法欠缺对数据的结构比较^[35].Melville等人^[38]分析了图可视化中基于矩阵的比较方法后得出:使用一个矩阵比较的方式能够提高可视化的效果以及寻找差异的准确性,优于用两个矩阵单独表示两个图的方式.同时,矩阵方式的局限性在于比较的树结构一般有相同的叶子节点集合.

Van Ham等人^[39]将矩阵方法用在软件系统不同模块之间的调用关系比较上,缺点是没有将节点之间的层次关系表现出来.Abello等人^[40]以及Beck等人^[15]都使用了基于邻接矩阵的方式,将树结构作为矩阵的坐标轴,而将叶子节点的比较放在对应的矩阵元素中.不同的是,前者用于比较不同人种、国家发病率的层次分布,树结构采用点线链接的形式表示(如图6所示);后者用于可视化软件结构,树结构以冰柱图的方式给出,每个矩阵元素代表节点之间的依赖关系(如图7所示).

图6(Fig.6)

图6 矩阵缩放[40] Fig.6 Matrix zoom[40]

图7(Fig.7)

图7 软件结构比较[15] Fig.7 Comparison of software architecture[15]

Bremm等人^[41]使用矩阵视图作为总览图(图8左上方),列出了任意两棵树之间的相似度,进而帮助用户选择一部分树进行比较,然后通过并置的方式比较选出的树和基准之间的差异.

图8(Fig.8)

图8 矩阵作为总览图[41] Fig.8 Matrix as overview[41]

在并置的比较方法中,大多数采用点线链接形式的树可视化方法,这是因为树图会有以下的问题^[13]:(1) 当树结构发生变化时,节点的位置可能发生突变,很难追踪节点的位置变化;(2) 缺少显著的可视模式呈现布局;(3) 缺少直接的对比方式来高亮差异;(4) 树图在结构的展示上有所欠缺.由于对应节点之间存在一定的距离,在对属性值的比较上稍显欠缺,所以并置的方法比较适合进行结构上的比较.同时,因为点线链接形式的树可视化方法本身具有空间利用率低的特点,在树的节点数量以及层数增多的时候,处在低层的节点数量呈指数级增长,这也就导致了并置的比较方法的本身扩展性不高.通过合适的交互,可以在一定程度上弥补这方面的不足.并置的方式多用于两树比较,通过平铺或向三维空间扩展的方式,可以用于多于两树的比较中.表3对并置的3种方法进行了比较.

表3(Table 3)

表3 Summary of juxtaposition methodsTable 3 并置方法总结 优点 缺点 适用情况 直接连接 通过连线的密集程度判断节点对应关系 以及相似度;注重总体的节点对应 连线较多时变得杂乱而影 响视觉呈现 用于比较相似性,寻找其中的对应 节点,而且节点数量不是很多的情况 视觉映射 通过视觉符号或颜色寻找节点对应,通常 借助交互观察局部的对应关系 用户需要根据提供的视觉 元素判断节点的对应关系 用视觉映射的方法发现其中的对应 节点,进行结构上的比较 矩阵 可以进行一对多的节点关系比较 无法进行结构比较 多树比较时,可以用作总览图,为用 户进一步选择提供依据

表3 Summary of juxtaposition methods Table 3 并置方法总结

在并置的方式中,由于需要同时显示比较的树,常常导致空间不够或者节点所占空间太小而无法有效辨识.因此,折叠/展开以及缩放是并置中常用的交互方式^{[7, 8, 10]}.除此之外,在并置的比较方法中,尤其是采用直接连接的可视化系统^{[11, 18, 34]},或者需要手动关联对应节点,或者在系统预先计算出对应节点连接后进行调整,都需要连接的交互方式.在采用视觉映射的方式时,使用颜色或者符号映射进行比较不如连线那么直观,这种情况下,通常会加入过滤/查询的交互^{[7, 10]},帮助用户快速地进行节点定位.

合并的方法是指采用某种算法计算比较树的节点之间的对应关系,根据对应关系将对应节点合并成一个树节点,进而构建一个包含所有节点的树结构.因此,合并后的树结构存在两类节点:合并节点和独立节点.在合并的节点内部,可以通过可视编码属性进行对应节点的比较,而独立节点代表独有的节点.因此,合并方法的核心在于通过直接比较被合并节点的属性值来看节点的属性差异,而通过“节点的有无”比较结构上的差异.

用并置的方式进行比较,用户需要不断地在比较对象之间切换视线,当关注的部分距离较远的时候,视线切换会非常频繁,增加理解的难度,可以通过合并或者重叠的方式来减少视线在比较对象上的切换.因此,合并的方法适用于比较的树结构相似度很高的时候,这样,通过合并对应的节点进行对应节点的属性值的比较.

根据在合并节点中的比较方式,合并的树比较方法分为直接比较和显式编码(explicit encoding)两种.

直接比较是指在合并的节点内部直接可视编码对应的节点的属性的方式进行比较.

Morse等人设计了TaxoNote^[9]对多类别层次结构划分进行比较.TaxoNote将所有分类包含在同一个层次结构中,如图9(a)所示,在展示合并后的结构时,采用了基于缩进的方式,对应的节点可以相邻放置在同一列中.TaxoNote实现了简单的比较,将比较的两个对象放在合并后的对象两侧,同时,用一个表格列出所有类别信息,用户可以通过查询选择感兴趣的类别,从而在树结构中高亮,以此来达到比较的目的.

图9(Fig.9)

图9 直接比较 Fig.9 Compare directly

Zoomology^[42]用于比较两个分类数据集,由于数据的结构相似度很高,采用的是将两棵树合并成一个冰柱概览图的方法,主要比较数据的结构差异.Lee等人^[43]将层次结构的结构差异称为不确定性,实现了CandidTree (如图9(b)所示)来比较两个相似的层次结构中的不确定性.CandidTree将两个树合并成一个,分别使用颜色和透明度编码差异.例如,在两棵树中都出现的节点、只存在于第1棵树中的节点以及只存在于第2棵树中的节点分别用3种不同的颜色表示.用户根据颜色来判断相似的部分以及差异较大的部分,同时,可以交互地比较不同深度、不同层次的节点.当用户选择一个节点时,显示从根节点到当前节点的路径,进而比较绝对路径的差异.他们将CandidTree应用在目录结构的比较上,可以很方便地看到目录结构的差异,比如文件的添加、删除以及移动,如图9(c)所示.Goemez等人^[12]也使用了相同的颜色编码的方式.

Burch等人^[49]使用正交的直线连接父子节点,在延伸的直线上展示时序数据,通过颜色和厚度编码属性信息,在一个节点中同时显示不同时刻的属性.图10显示了节点属性的5种变化趋势.Ghoniem等人^[50]设计了动画树图,将动画的效果应用在树图中,用以观察树节点的属性变化差异.因为树图的节点所占面积和权重对应,所以在动画过程中,用户可以集中在关注区域的变化上,而且面积的变化可以平滑过渡.

图10(Fig.10)

图10 5种不同的属性值变化[49] Fig.10 Five types of value behavior[49]

Tu等人^[13]在进行树比较时,同样使用了合并的策略.不同的是,他们采用了树图作为树的表现形式.树图的优势在于,它能够在反映数据属性总体变化的同时呈现个体的属性的变化,这是树图的结构所决定的.在树图中,父节点的属性值是其子节点属性的总和,这个特点在使用树图可视化文件目录结构的时候尤其明显.他们将两个树图合并,具有相同父节点的元素被合并到同一个树图单元中,从而可以直接比较两个实体的属性.为了降低布局突变的影响,他们为此还提出了螺旋树图(spiral treemap)布局算法.如图9(c)所示,对NBA中2002~2003和2003~2004两个赛季的球员所在球队的统计进行了可视化,使用节点的两个对角区域编码两个赛季中球员的球队归属,用所占比例表示两个赛季的得分情况.使用树图的形式,虽然可以使用颜色和纹理表示节点值的差异,但是无法表现内部节点结构上的差异.

其他一些工作^{[14, 19, 20, 44, 47]}在进行树比较时,也都使用了合并的方法.Ambros等人^[19]将合并比较用于代码版本管理系统中Bug的追踪分析,Timothy^[20]用于分析文档结构随时间的变化,比较不同时间点的文档结构差异,从而为数字鉴证人员提供了一个分析工具.

在合并的比较方法中,另一种方式是显式编码.显式编码是指直接可视化节点属性的关系和值的不同,比如差值、变化百分比例等.Gleicher等人^[3]把显式编码作为一种独立的比较方法,但是在树结构中,比较不能完全脱离结构,所以通常用在合并以后的树结构中.显式编码侧重于可视化数据在结构或者属性上值的差异,弱化了对结构和属性绝对值的可视化比较.显式编码的好处是,在数据量增大的时候,用户可以很容易地注意到数据中变化比较大的节点^[3].

TreeVersity2^[14]用于进行层次数据的时变比较,一般是层次化后的表格数据.比如肺癌死亡率的数据,按照种族、性别以及是否吸烟分组后的结果.在时间线视图中,分层显示节点属性随时间的变化,Stem视图用于比较两个时间点的数据,又分为两个子视图:点线子视图用点线连接的形式,每个节点用颜色、高度、形状等表示不同属性的差异值;柱状子视图将柱状图和冰柱图结合,层之间用邻接关系表示父子关系,每个节点用颜色、高度、宽度、方向等编码不同属性的差值或变化百分比(如图11所示).在比较任务中,颜色编码是经常用到的一种方式,在一些情况下,多个属性需要全局的颜色映射,但是在属性的值域差异很大时,值域范围小的属性几乎不可见.Tominski等人^[51]提出用合并一部分重叠值的方式来改善比较任务中的颜色编码.

图11(Fig.11)

图11 显式编码,TreeVersity2[14] Fig.11 Explicit encoding,TreeVersity2[14]

合并的比较方法是利用了层次数据在结构上的相似性而采取的数据比较策略,多用于比较的树相似性很高时.直接比较用于比较属性的绝对值差异,而显式编码用于比较相对值差异,结构性的差异可以通过各自独有的节点数目来得出.合并的方式一般用于两树比较中.表4总结了两种合并的比较方法的优缺点以及适用情况.

采用合并的树比较方法,比较的信息大多集中在合并节点的内部,因此,交互多以能够有助于查看细节的方式为主,比如简单的缩放(zooming)、焦点+上下文(focus+context)技术^[43]、鱼眼(fish eye)技术^[52]等.

表4(Table 4)

表4 合并方法总结Table 4 Summary of superposition methods 名称 优点 缺点 适用情况 直接比较 注重属性值的绝对量 之间的比较 需要同时可视化比较节点的 属性,空间使用较多 进行对应节点属性值的直接比较 显式编码 属性的相对值比较,注 重比较值的差异程度 缺少属性的绝对量的上下文, 可能会造成数据的错误理解 当属性值的绝对量不是关注的重点时, 可以考虑使用显式编码的方式

表4 合并方法总结 Table 4 Summary of superposition methods

动画的方式常用于动态树的比较中,尤其是具有实变特征的数据,其目的在于发现数据在结构或属性值上的变化趋势.动画能够有效地表现结构上的变化^[53]和属性的变化趋势^[54].Card等人^[45]设计了TimeTree(如图12所示),将树可视化应用在时变数据中,不同时间点的树结构变化使用了动画来展现,通过拖动底部的一个时间轴的方式实现不同的时间点视图的切换.Tu等人^[13]采用将树图和地图联动的方式,通过地图的纹理变化查看数据的变化程度,如图13所示.

动画的方式除了用在动态树的比较之外,还可以用在两树以及多树的比较上,所采取的方式是在比较的树之间做动画切换.Robertson等人^[54]在进行Polyarch可视化时加入了动画的效果,用以观察不同树结构中节点的增加和减少.不稳定的树图布局算法,导致动画的效果比较差^[55].Tu等人^[13]在进行树比较时提出了树图的螺旋式布局(spiral layout).螺旋式的布局方式在很大程度上提高了布局的连续性和稳定性.同样是基于布局的稳定性考虑,Gotz^[46]提出了Dynamic Voronoi Treemap算法,能够保持稳定性和良好的纵横比,能够平滑、实时地展示时序变化的层次数据.这些方法在一定程度上降低了不稳定的布局算法对动画效果的影响,在文献^{[52, 56, 57]}中也都使用了动画的方式进行树的比较.

图12(Fig.12)

图12 TimeTree[45] Fig.12 TimeTree[45]

图13(Fig.13)

图13 用地图的纹理变化反映数据变化[13] Fig.13 Using image texture changes to reflect changes in data[13]

由于在动画过程中树中节点的位置会发生变化,用户不能很好地跟踪树中变化的部分^[4].尽管在平滑过度的动画中用户可以跟踪到变化的位置,但是一个时刻用户只能看到比较的树中的一棵并关注局部位置,这就增加了比较的难度.所以,动画的方式相对其他比较方式来说使用较少.

近年来,有不少工作将其他方法引入到树的比较可视化中.Amenta等人^[6]以及Hillis等人^[57]都采用了MDS (multi-dimensional scaling)技术,根据多维属性计算任意两棵树之间的距离,然后将其映射到一个散点图中.通过这种方式,实现了多树的比较.这类方法只能在粗粒度层次上对树进行分类比较,而无法进行细节性的比较.

可视化是帮助用户建立数据的构思模型(mental models)的工具^{[58, 59, 60, 61]},而交互允许用户与数据快速交流,更好地验证假设和发现内在联系,帮助用户调整构思模型^[62].交互注重探索的过程,在某种程度上能够弥补数据展示方式的不足.任磊等人^[63]将人机交互技术概括为5类:动态过滤技术(dynamic query)与动态过滤用户界面、整体+详细技术(overview+detail)与Overview+Detail用户界面、平移+缩放技术(panning+zooming)与可缩放用户界面(ZUI)、焦点+上下文技术与Focus+Context用户界面、多视图关联协调技术(multiple coordinated view)与关联多视图用户界面.

在可视比较中,交互一般有两种目的:(1) 连接相关的对象(连接,高亮);(2) 重新排列和整理对象^[47].在树可视化中,折叠展开、缩放以及查询是常用的交互方式,这些方式也常用在树比较可视化中.通过折叠展开和缩放,能够在节省空间的同时让用户关注于重要的部分,而查询能够进行节点的快速定位.在树比较的可视化方法中,连接(linking)和刷选(brushing)的交互方式常用于标记数据中用户感兴趣的 部分.Becker等人^[64]指出,在用并置的方式做数据比较时,常常结合连接和刷选操作,尤其是在多个视图协作的情况下.Graham等人^[65]提出,将连接操作和增强焦点概念应用到树形结构中.在树结构中,用户可以交互地选择相似的节点进行连接或高亮操作,而这些节点较之其他节点更受用户的关注,因此,这些节点会分配到更多的空间,而用户关注的焦点就会更多地集中在这些节点上.采用这种方式,可以突出相似的节点.如图14所示,Kehrere等人^[66]在进行树内比较时,通过用线连接比较的对象来指出比较的方向.为了比较一棵树中不同的子树,Burch^[67]在树图中引入了相似链接的概念,用户可以根据节点属性以及所在的层次,动态地将相似节点连接起来.同时,用户可以自定义不同属性的阈值以及层次表示.

图14(Fig.14)

图14 用连线指明比较的方向[66] Fig.14 Compare direction by linking[66]

Munzner等人^[8]引入了可见性保证(guaranteed visibility)的概念,其核心思想是:在缩放和折叠操作中,时刻保持用户关注部分的可见性,这就使得关注的相似节点在突出的位置显示.Conklin等人^[68]将分解可视化的方式(breakdown visualization)应用在表格数据和统计数据中,允许用户按照不同的层次将数据分割成不同的分组,同时允许用户在一棵树中的不同分支内比较.TreeJuxtaposer^[8]中使用了Focus+Context的技术,在保留概览的情况下进行局部的比较.任磊等人^[69]综述了海量层次信息可视化与Focus+Context技术的相关工作,针对海量层次信息可视化的交互问题,在嵌套圆可视化技术的基础上提出了基于上下文感知的Focus+Context交互式可视化技术.InfoZoom^[36]中则使用缩放的手段显示低层的节点.而在Chevalier 等人^[18]的工作中,引入了细节层次(level of detail)的概念,用户可以交互地选择显示哪些层次的细节.Isenberg等人^[70]将树比较的方法应用在多人协作中,将多点触控的屏幕作为显示媒介,结合多点触控屏幕的交互优势,用户能够更加方便地进行比较. Tominski等人^[47]受到现实生活中人们进行的各种比较操作的启发,提出可以通过附加视觉线索来支持可视比较.在实现的交互比较的原型中,通过折叠的交互方式来解决节点重合带来的覆盖问题,用户可以根据需要将上层节点折叠,使得下方的节点能够显示出来.Plumlee等人^[71]指出,在进行比较任务时,通过添加注解的方式有助于降低用户的理解成本.表5总结了树比较可视化中常用的交互方式以及其作用.

表5(Table 5)

表5 树比较可视化中的交互Table 5 Interactive techniques in visualization of tree comparison 类别 交互方式 目的/作用 基本交互 缩放 折叠/展开 连接 刷选 查询/过滤 进行局部位置节点的细节查看 显示或者隐藏部分层次节点 建立节点之间的对应关系 选择用户感兴趣的部分进行进一步比较操作 快速定位节点 焦点相关的交互 可见性保证 总览+细节 焦点+上下文 在视图改变过程中将感兴趣的节点一直保留在视图中 在一个全局图中进行细节的比较查看 在进行细节比较的同时为用户保留当前位置在全局中的上下文信息

表5 树比较可视化中的交互 Table 5 Interactive techniques in visualization of tree comparison

树比较的可视化方法主要面临以下两个方面的挑战.

(1) 树结构的表现形式以及比较形式

树比较的表现形式受到树的表现形式的约束,常用的树表现形式为缩进形式、点线链接形式、邻接形式和树图.从比较形式上说,树比较可视化方法以并置和合并两种方式为主,而这也是符合人比较习惯的方式.无论是发掘或创造新的树表现形式还是比较形式,在可视化领域中都是一个比较难的问题.

(2) 扩展性

树的结构决定了当树节点以及层次增多的时候会带来扩展性问题,同时,对比较的形式也会产生影响.随着数据量越来越大、比较任务的不断变化以及不同数据的比较需求,现有方法的局限性越来越明显.一方面需要根据可视化的需求选择合适的方法,另一方面也需要在现有的方法基础上做一些创新性的改变.

目前的树比较可视化方法中,大多采用的是点线链接形式和树图形式,其他形式相对较少.而用到的点线链接形式中,又以从左到右/从上到下的布局为主,空间利用率不高,其他布局方式用到的很少.从Schulz等人^[32]提出的树可视化方法设计空间出发,结合比较任务的特点,可以进行一些方法上的尝试,比如使用径向布局的方式.而陈谊等人^[72]在分析关联层次数据时,提出了SR(sunburst with relationship)算法,通过将层次节点聚集的方法应用于Sunburst中,为可视化关联关系提供了空间.该算法可以用于树比较中,在保持层次结构上下文的情况下对节点的属性进行可视比较.随着科技的发展,除了电脑屏幕以外,可视化也开始应用在诸如手机、平板以及大屏等设备上,这些设备具有不同的显示特性以及操作特性.如何让现有的可视化技术适应新的设备,以及在这些设备上如何进行交互,都是值得研究的课题.

本文对树比较可视化中使用的方法进行了总结,树比较可视化方法按照表现形式分为并置、合并以及动画这3种.并置的方法多用于进行树的结构比较;合并的方法适合比较节点的属性;动画的方式则用于具有时序性质的层次数据,比较数据不同时间点的差异以及数据随时间的变化趋势.综合以上分析,表6列出了不同方法的比较,作为树比较可视化方法选择的参考.同时,本文还对树比较可视化中的交互以及该研究领域面临的挑战和发展进行了讨论.

表6(Table 6)

表6 树比较可视化方法总结Table 6 Summary of tree comparison visualization 树内比较 两树比较 多树比较 静态树 动态树 属性比较 结构比较 并置 直接连接 - ★★★★★ ★☆☆☆☆ ★★★★☆ ★☆☆☆☆ ★★★☆☆ ★★★★☆ 视觉映射 - ★★★★★ ★★☆☆☆ ★★★★☆ ★☆☆☆☆ ★★★★☆ ★★★☆☆ 矩阵 ★★☆☆☆ ★★☆☆☆ ★★★☆☆ ★★★★☆ ★☆☆☆☆ ★★★☆☆ ★☆☆☆☆ 合并 直接比较 - ★★★★★ ★★☆☆☆ ★★★★☆ ★☆☆☆☆ ★★★★☆ ★★★☆☆ 显式编码 - ★★★★★ ★☆☆☆☆ ★★★★☆ ★☆☆☆☆ ★★★★☆ ★★★☆☆ 动画 ★★☆☆☆ ★★☆☆☆ ★★★☆☆ ★☆☆☆☆ ★★★★☆ ★★★☆☆ ★★★☆☆ 注:本表可以作为树比较可视化方法选择的基本依据,在实际选择中,需要结合数据特点以及可视化目的进行选择

表6 树比较可视化方法总结 Table 6 Summary of tree comparison visualization

致谢 本文在撰写过程中得到了北京大学智能科学系袁晓如研究员的指导,并与其学生进行了多次讨论,在此表示感谢.