第 5 章 图和层次数据可视化 万物之间相互存在着各种各样的联系,这种联系可以是简单的,也可以是复 杂的;可以是无向的,也可以是双向的;可以是加权的,也可以是不加权的;可以是 确定的,也可以是不确定的。事物之间的这种联系可以用一张图表示。我们在日 常生活中可以碰到各种各样的图结构,如生物科学中的蛋白质-蛋白质交互网络、 社会科学的关系网、语言学中的词共现网络,以及我们生活中无处不在的通信网 络等。在各种由图表示的关系中,有一种特殊的关系———层次关系。层次化数据 广泛存在于生活的各个领域,族谱、分类、拓扑、公司员工、文件系统、文本文章、源 代码和人口数据等都是具有内在层次结构的典型例子,可以通过具有父子关系的 树表示它们的结构关系。即便是不存在潜在的层次化结构的数据,如标量数据和 大型语料库,也可以通过聚类构建层次结构,从而获得关于数据的概览,方便人们 理解这些数据。 对图和层次数据的分析,有助于我们洞悉社会、语言和不同通信模式的内在 结构,尤其数据之间的联系可能蕴含比数据本身更丰富的信息。对图和层次数据 的可视化是信息可视化领域一个非常重要的研究方向。本章将介绍图数据的可 视化方法,我们将层次化数据作为图的一种特殊种类融入进来介绍。 ..5.背景知识 1 图是计算机科学领域最重要的数据模型之一,许多问题都可以建模为一个图 的结构,如理论计算机科学中的自动机、管 道和道路的流网络、数字化和非数字化的 社交网络、计算机网络、公司和金融事务网 络、社区中流行病的传播、实验中的相关或 受控变量等。如图5-1所示,对图的分析 有赖对他们的可视表达,图可视化研究致 力于开发有效的图布局和可视映射。而对 大尺度图形的可视化又常常需要借助有效 的交互技术,尤其如果图太大或太复杂,就 不能在一个静态视图里可视化。很多时 候,仅交互本身并不足以完成特定的分析 图5-1图可视分析的主要构成 图片来源:文献[1] 第5章图和层次数据可视化105 任务,因此我们还需要借助一些算法如机器学习或图分析的支持[1]。 5.1 图的定义和分类 1. 一个图G=(通常由顶点集合 V 和连接顶点的边集合 E 构成,图的顶点和边上又 V,E) 可以附加各种属性,如它们的类型、大小以及其他与应用相关的信息。图可以分为有向的和 无向的:有向图的边是有序的,即e12(v2,而无向图的边是无序的,即e12 v1,v1); v2)≠e21( e21(v1 (v1,v2)=v2,)。同时包含有向边和无向边的图称为混合图。图中的一条长度为 s 的路径(pah) 即ptG ()a1,a其中, t由一系列连接在一起的顶点构成, aha1,=a2,…,s, ai ∈ V 且(ai+1)∈E。树是一种无环无向连接图。在图理论中,(s) (a) 当一个有向图的边是加权 ai, 时,则称为网络。还有一类我们称之为复合图。一个复合图C(G,T)由共享同样顶点集的 图G=(V,EG ) V,r)构成: 和树T=(ET , .e=(v2)∈EG ,tT (v2)ntT (v1) v1,v1.pahr,adv2.pahr, 复合图可以通过对图顶点自下而上连续聚类得到。这个聚类操作通常会为每个聚类创建一 个父节点,也称为元节点。元节点属性可以通过所聚类原始节点定义,元节点之间的连接边 也通过聚类得到,称为元边,它们的属性也类似地从原始边计算得到。最后,图可能会随着 时间演化,形成所谓的动态图,动态图的节点和边的属性甚至图结构本身都可能随时间改 变。图5-2总结了这里介绍的图分类。 图5- 2 图分类:基于时间依赖关系(左)和图结构(右) 图片来源:文献[1] 1.图的预处理 5.2 对于规模太大、太复杂的图,人们理解起来会觉得有很大挑战,即便存在一些高级的顶 点和边的放置算法(布局)。对可视化而言,图的预处理主要是对图进行简化,在减少图规模 的同时维持其主要结构。此外,也可以对图属性进行预处理以突出图中的感兴趣部分。主 要的图缩减方法有两类:图过滤和图聚类,下面分别介绍。 1. 图过滤 可以通过两类方法进行图的过滤:随机过滤从原始图中随机选择过滤的边和顶点;而 确定性方法则依据特定算法选取拟移除的顶点和边,选取的依据可以是顶点/边的属性、拓 扑信息或其他图属性等。 2. 图聚类 图聚类方法将顶点和边合并为单一顶点和边以减少图的规模,并揭示不同顶点组之间 106数据可视化与设计思维 的关系。可以通过多次的图聚类构造一个层次图。图聚类的方式有很多种,可以通过预定 义的顶点层次、顶点属性或根据顶点聚类等。 ..5.2图的可视表示 可视化是对图进行探索性分析的主要方式,其任务包括设计合适的可视表示类型、如何 将各种图形元素高效地放置在屏幕上,以及如何对各种属性进行有效映射,最终实现较好的 可读性。在计算机生成的图可视化中,通常会考虑一些审美要求,这些审美要求通常定义为 布局算法中的一个目标函数。 5.2.1静态图的可视表示 1.树 如前所述,层次结构在现实世界中非常常见,可用于记录日常生活和业务流程中生成的 各种关系数据。而树状结构则是表示层次结构最直接的方式,因此在可视化领域也得到广 泛的采用,Treevis.net[2]提供了超过300种关于树在线可视化技术的介绍,这足以说明树可 视化在数据分析中所发挥的关键作用。关于树可视化的技术,大致可分为3类。 (1)空间填充技术。试图利用整个屏幕区域显示层次结构,基于节点位置而非连接表 示节点关系,通常用于可视化对数据集的层次剖分,区域大小用于编码节点的可量化属性, 还可以用颜色和高度表示额外的数据属性。基于所采用的放置策略又可以进一步分为圈 地、近邻和交叉3类。圈地方法(见图5-3(a))在父节点所圈区域内递归地布局其子节点,近 邻方法(见图5-3(b))通过将子节点放置在父节点旁边以体现它们之间的关系,交叉方法 (见图5-3(c))将子节点跨过父节点放置。 图5- 3 3种不同的空间填充层次可视化方法 图片来源:文献[1] (2)节点-链路方法。采用链路揭示不同数据项之间的关系(见图5-4)。通过设计不同 的标准来优化布局。图绘制领域的研究人员提出了各种各样的布局算法,二维的有分层、径 第5章图和层次数据可视化107 向、气球布局,三维的如Conetree、Phyllotrees等。 图5-4基于节点-链路的树可视化 图片来源:文献[1] (3)混合方法。顾名思义,结合节点-链路和圈地的方法,用Treemap表示一部分层次 结构,其他的用节点-链路图表示(见图5-5)。主要优点是既能以一种灵活且空间利用率高 的方式表示层次结构,又能清晰地表达数据结构的关系,强调其内容。 图5- 5 混合的树可视化 图片来源:文献[3] 层次多变量数据可视化。尽管在多元数据和层次数据的可视化方面已经非常深入和成 功,但对于层次多元数据的可视化,即每个节点上有多个属性的树,却研究甚少。层次多元 数据广泛存在于各个领域,如生物学中的组学数据、人口普查中的统计数据、层级组织的商 108数据可视化与设计思维 业数据等,其特殊性需要专门的可视化技术进行有效分析。在来自生物信息学领域的 Functree2[4]的启发下,Zheng和Sadlo[5]对具有共同层次结构的多元定量特征的可视化进 行了系统设计研究。对任务进行深入分析后,他们将设计空间缩小到多变量可视化和层次 可视化的组合,并将需求按照可泛化性进行优先级排序。 .静态表示:适用于(印刷)出版物。 .避免遮挡:将表示限制为2D。 .简单解释:显式视觉映射。 .可读性:清晰的多变量和分层属性。 .内部节点上的任意数据:不仅是聚合。 在可视化分层数据时,由于视觉空间是有限的,层次结构的紧凑性和可读性之间总是要 进行权衡的。非常紧凑的可视化,如树状图(见图5-6(a)),尽管实现了高信息密度,但通常 会使读取数据的层次结构[6-7]变得困难,导致需求4不被满足。而非常低紧凑性的层次可视 化,如节点链接图,可能受益于层次结构[8]的可读性增加,但占用了太多的可视化空间[9],限 制了可视化多元属性的可用空间数量,从而导致降低多变量属性的可读性。因此,在选择层 次可视化概念时,往往需要平衡层次结构的紧凑性和可读性。此外,有些层次可视化技术可 能会发生遮挡,如Beamtrees[10]或Cheops[11]就不满足需求2。Zheng和Sadlo认为冰柱图 (见图5-6(c))、旭日图(见图5-6(d))和圆形树状图(见图5-6(e))是集成多元可视化概念的 潜在候选方法,因为它们在可读性和紧凑性方面取得了较好平衡。对于多变量可视化,候选 概念需要利用层次结构的紧凑性和可读性之间的权衡所留下的视觉空间。像平行坐标、散 点图矩阵和维度堆叠将很难与层次方法结合,因为它们已经表现出相当高的视觉复杂性并 且需要相当大的空间。而Glyphs作为一类多元可视化概念,使用小而独立的视觉对象,在 可读性方面具有主要优势。根据上述5个需求,许多Glyphs概念都不能很好地用于多元可 视化。因为对多变量属性使用条形图会进一步分解段的宽度,这在层次可视化中已经趋于 太薄。这促使他们将堆叠条形图和饼图锁定为多变量可视化概念,它们足够紧凑且易于阅 读,是与分层可视化技术结合的较好选择。 图5- 6 可视化层次数据的传统图 图片来源:文献[5] 在具体设计上,文献[5]将堆叠条形图融入旭日图/冰柱图中,旭日图/冰柱图的每一部 分都包含一个堆叠条形图。为了防止表示中的不对称并避免将数量映射到角宽度,这不是 一个好的定量视觉变量,他们将堆积条形图定向在径向(旭日图)或垂直(冰柱图)方向,即, 值沿线段的(径向)长度方向被编码。直接应用传统的堆叠条形图(见图5-7(a))将很难比较 兄弟之间的属性(堆叠条形图的单个条形之间),这促使他们尝试对齐堆叠的部分。图5-7(b) 试图通过标准化每个条形来实现,这种标准化简化了不同条形之间的属性比较,但它使定量 第5章图和层次数据可视化109 解释变得复杂。第二种(也是首选的)方法是分别对齐每个属性(见图5-7(c)~(e)) 。第一 个设计(见图5-7(c)) 可以很好地使用单个堆叠条形图。但是,如果将其整合到旭日图/冰柱 图中,它就不能很好地工作,因为还需要(白色)区域来分离节点,以及层次结构的级别(对应 图5-7(d)中的白色圆圈), 这会导致视觉干扰。因此,文献[5]在堆叠条形图中尝试了另一 种“填充”颜色,例如黑色(见图5-7(d)), 但这在视觉上打乱了堆叠的信息,使其更难被视为 一个多元实体。除此之外,填充颜色可能被误解为一个附加属性。所有这些都促使他们使 用低饱和颜色填充(见图5-7(e)) 作为集成方法的解决方案。 图5-7堆叠条形图构件的设计研究 图片来源:文献[5] 传统的旭日图和冰柱图都只能使用(角)宽度显示内部节点处子级值的总和。而文献[5] 将垂直方向的堆叠条放入冰柱图(见图5-8(a)), 并将径向方向放入旭日图(见图5-8(c)) 。这 意味着与传统的旭日图形相比,定量信息被映射到线段的径向长度,而不是角宽度。对于冰柱 图,它被映射到线段的长度而不是宽度。通过这种新映射,任何多变量数据都可以显示在内部 节点上。他们还允许自由选择线段的(角)宽度,提出了选择(角)宽度的两个策略:等兄弟策 略和等叶策略。等兄弟策略取父节点的(角度)宽度,并将其平均分配给其子节点的(角度)宽 度,如图5-c) -8(g) 以及图5-a) -8(中的冰柱图所示。等叶策略 8(和图5中的旭日图, 8(和图5e) 将整个全局(角度)宽度(在旭日图中为2π,在冰柱图中为整个可视化宽度)平均分配给层次结 构的所有叶段。该策略应用于旭日图(见图5-8(d)和图5-8(h)) 及冰柱图(见图5-8(b)和 图5-8(薄叶” 增加了紧凑度,使叶片的识别和读取更加容 f))。等叶策略成功地避免了“ 问题, 易。这两种策略可以很好地表达层次多元数据的层次方面和多元方面。 图5- 8 多元冰柱图(左两列)和多元旭日图(右两列) 图片来源:文献[5] 110数据可视化与设计思维 作为一种增加层次结构紧凑性的设计方案,文献[5]还考虑了气泡树状图(见图5-9(a)和 图5-9(b))[12],它使用紧凑的填充曲线反映层次结构,而不是圆形树状图中使用的圆形。在 气泡树状图中,内部节点的包装曲线的平滑度可以通过参数进行调整,提供从凸壳到凹壳的 形状。气泡树状图的紧凑性可以实现更大的叶子表示,如多元循环树状图MCT(见图5-9(d)) 和多元气泡树状图MBT(见图5-9(e))之间的比较所示。考虑到传统饼图(见图5-10(a)) 有一些局限性,例如,在传统的饼图中,每个量化属性都映射到磁盘的一个扇区,磁盘的面积 取决于所有属性值的总和。但是,如果属性具有不同的单位,那这种表示就不太合适。饼图 的替代优化方案为极坐标区域图(也称夜莺玫瑰图)。极坐标区域图不是将数量映射到具有 不同角度的扇区,而是将每个数量映射到角度相等但半径不同的扇区,如图5-10(b)所示。 文献[5]使用圆形指南扩展了极坐标区域图,以支持与其最大值的定量比较(见图5-10(c)),这 适用于所有属性具有相同单位或具有不同单位的属性已标准化的情况。极坐标区域图可以 很方便地比较层次之间的关系。 图5-9增加层次结构紧凑性气泡图设计 图片来源:文献[5] 文献[5]使用omics数据集评估了其提出的方法,omics数据集被Functre2可视化关 注。该数据集由NCBI基因标识符丰度的7个样本组成,各自的层次关系在KEGG数据库 中预定义。树的每一层对应功能类别,从上到下依次是生物类别、生物过程和KEGG通路。 文献[5]在两个主要的分析任务中将其与Functre2进行比较和探索。在Functre2中比较 节点之间的样本值很困难,因为堆叠的条形图不是对齐的,因此,在Functre2中提供了交 互功能,可以选择一个属性并将其值映射到圆圈区域,以便在节点之间进行比较,如 图5- 1(所示。相反, 5] 见图5-b)e) 。 a) 文献[允许在一个静态表示中同时比较所有属性( 1(~( 在Functre2中,如果想了解KEGG通路中的值如何与上层中的值相关,例如生物过程或 生物类别,可以选择一个叶子节点,并借助高亮显示的路径检查相应的上层节点(见 图5-11 )。另外,在Functre2的静态视图中,在没有交互的情况下定位较低级别的主要节 点(例如,定位图5-11(a)中的节点a、b、c)不太容易。由于Functre2是基于径向树的,因此 视觉阅读由于扩展的视觉转换而变得复杂。当树具有多个级别时,这种基于选择的突出显 示非常有用。然而,在图5-11(b)~(e)中,可以直接找到这种关系。 图5-10 传统饼图、极坐标区域图、扩展的极区图 图片来源:文献[5] 第5章图和层次数据可视化111 图5a)Fe2与文献[5]的((e))MSB和((d))MIP进行比较,皆使用o数据集进(u) 行(r) 演示。等兄弟(角)宽度((d),(e))和等叶(角)宽度((b),(c))的布局策略 -11 (tb),(c),(mics 图片来源:文献[5] 图5-12显示了使用MBT和MCT的相同数据。图5-12(a)展示了MBT在可视化叶片 特性方面的优势,图5-12(b)显示了这些多变量如何在MCT的内部节点上成比例地变化。 从图5-11(b)和图5-12(b)中可以看出MCT的紧凑性相当低。 图5-12 用MBT(a)和MCT(b)可视化的omics数据集,内部节点显示其子节点的多变量平均值 图片来源:文献[5] p采取类似做法:所有的子 节点都被代表当前节点的轮廓包围。因此,其与描 述空间嵌入对象的集合成员关系的方法有相似之 处。例如,BubbleSets使用移动方块(移动方块算 法的2D版本)绘制嵌入对象的轮廓,而Bubble Tremap使用的是弧线;在不确定表达方面,以叶子 的附加属性值和聚合模型的形式给定具有不确定性 图5-13 BbbleTremap 的值层次结构(见图5-14(a)和图5-14(b)),Bubble 图片来源:(u) 文献[12] Tremap通过从层次结构的每一层提取特征来构建 一个气泡树状图,然后将这些特征分别映射到圆上,并分析定义叶片和内部节点的基于圆弧 的轮廓。如图5-14(c)所示,为了实现紧凑的布局,BubbleTremap实现了一个力导向的模 型。BubbleTremap从组织在层次结构(见图5-14(a))中的测量分布开始。通常只知道叶 子结构的情况。通过应用合适的不确定性模型,BubbleTremap将底层分布的特征传播到 根(见图5-14(b))。然后,BubbleTremap使用圆弧和基于力的模型(见图5-14(c))计算树状 图布局。最后,BubbleTremap在层次的每一层(见图5-14(d))周围画叶圆和内节点轮廓。 112数据可视化与设计思维 紧凑性和可读性的权衡是层次数据可视化中的一个重要挑战:如果树状图非常紧凑, 底层结构就很难把握,因为紧凑性没有为分组线索或其他视觉特征留下空间。Bubble Treemap[12]在紧凑性和可读性之间提供了一个很好的折中方法。它们在布局中分配额外 的空间,以几何方式将确定的和不确定的信息编码在一起,类似于错误条。层次结构的叶节 点被编码为圆形,并被基于圆弧的可参数化轮廓所包围。兄弟子层次结构的轮廓使用一个 力指向模型进行包装,并被另一个可参数化的轮廓包围。这个过程递归地继续,直到遍历整 棵树。这种方式可以将额外的组级信息(如不确定性)编码到轮廓的视觉表示中。 BubbleTreemap提出一种新型的圆形树状图,其为额外的视觉变量分配额外的空间。 在这个扩展的视觉设计空间中,将层次结构的数据及其不确定性编码到一个组合图中。 BubbleTreemap引入了一种分层和基于力的圆形填充算法来计算气泡树状图,其中每个节 点都是使用嵌套的轮廓弧可视化的。气泡树地图不需要任何颜色或阴影,这提供了额外的 设计选择。BubbleTreemap利用标准误差和基于蒙特卡罗的统计模型,将不确定性可视化 作为树状图的一个应用来探索,讨论了不确定性如何在层次结构中传播。 具体地,BubbleTreemap利用Wang等[13]的方法创建初始填充,如图5-13所示,为了 合理地利用展示空间,使用压缩边缘的方式提高空 间的利用率。在轮廓和集合成员方面,树状图通过 将子节点的区域聚合到父节点的区域来隐式编码层 次结构。BubbleTreema 图5-14 构建BubbleTemap过程用于展示数据不确定性 图片来(r) 源:文献[12] 第5章图和层次数据可视化113 多个层次数据的可视化。现有的大多数树可视化方法一次只能对一个层次数据集进行 可视化,在进行两个以上层次数据集之间的比较时仍然存在困难,特别是当每个节点都具有 多维属性时。针对这个问题,YuDong等[14]提出了PansyTree,借助树的方式可视化层次 结构的合并。 他们设计了一个名为Pansy的独特图标来表示结构中的每个合并节点,每个Pansy图 标使用颜色区分不同的数据集。它在花中心提出一个视觉提示来计算当前节点中合并属性 的总量。另外,定义垂直向上为起点,3个数据集依次顺时针排列。每片花瓣的角度0°~ 120°为红色,120°~240°为蓝色,240°~360°为黄色。同样,在每个特定的颜色中,属性值也 是顺时针排列的。将3个节点的数据合并为一个节点,按顺时针方向排列各自的属性。花 瓣高度代表正值的大小,不同颜色的花瓣排列顺序相同。花瓣高度等于0表示属性值为0, 同时引入带有灰色的sepal区分合并层次结构中是否存在属性值为0的节点数据。此外, 自然界中的每种植物都有生命周期。 当花朵盛开时,它的花瓣逐渐生长。图5-15显示了从种子到盛开的花的生命周期。生 命周期分为生长、早熟和成熟期3个阶段。PansyTree利用花瓣的高度编码属性信息,利用 花瓣的开花过程描述生长模式。考虑到在合并后的结构中,层次结构显示的实际需求比相 同层次的位置需求更迫切,采用强制布局分配每个节点的位置,通过调整节点之间的排斥系 数避免节点之间的重叠,从而形成一个整体的拓扑树结构。为了在强制布局中显示层次结 构和节点之间的关系,进一步定义根及其子节点之间的链接为“主干”,其他的为“分支”。设 置带有动画链接的视觉提示,称为“动画光标”,以显示关系的紧密程度。 图5-15 PyTre “成长期” 图片来源(a) :(n) 文献[1(s) 4] 在交互方面,为了帮助用户进行层次比较,PansyTre 设计了3种交互技术作为辅助工 具:一是结构提示突出显示。当动画链接重叠或速度相似时,力导向布局的随机性和不确 定性可能导致用户难以理解层次结构。因此,PansyTre 设置了结构提示,以突出所选 Pansy、它的祖先和后代的属性和关系;二是筛选层次结构的条件排列。对于数百个节点的 合并树,需要针对用户通常关心的特殊组设置不同的条件排列过滤器,否则其他颜色的合并 节点会分散他们的注意力。为了方便这样的过滤器,PansyTre 添加了一个用于交互的草 图,它通过选择3种颜色提供几个组合的可视化输出;三是折叠/展开节点以显示详细信息。 当整体层次结构有相对较大的深度和宽度时,屏幕大小将影响用户体验。因此,PansyTre 在初始状态下,根据合并树的平均宽度对一定深度的层次结构进行折叠或展开,以保证结构 平衡。 图5-16是一个基于PansyTre 的原型系统。该系统包含一个合并数据集(D)的主视图 和一个悬停在桌面上的选定面板(E),其中顶部显示每个大学计算的每个层级的节点数量。