一个针对增量式可视化的可视化过程增强模型 (An Enhanced Visualization Process Model for Incremental Visualization)

在传统的可视化场景中,数据是稳定的,显示设备是固定的,但是随着技术的进步,这一场景已经不再必然成立。比如,流数据的质量和数量可能随时间变化;显示设备也变得无处不在,可视化的显示设备可能发生变化。

传统的可视化场景由整体式可视化(monolithic visualization)应对已经足够。在整体式可视化中,数据可以一次性获得,经历一个由运算子组成的流水线后产生最终的可视化结果。这些运算子可以在应用于数据之前或者之后进行修改,但是在应用过程中不能修改。对于更加富于变化的可视化场景,则需要使用增量式可视化,它允许用户和可视化的中间结果进行交互。

对于整体式可视化,已有的模型,比如数据流模型,数据状态模型等,自90年代提出以来,依然为许多面向数据流的软件提供底层理论支撑。但是对于增量式可视化,虽然已经有很多不同的具体方法被提了出来,但是关于它的模型依然有待研究。该工作正是针对缺少理论模型的现状,对已有的模型进行增强,从而提出了增量式可视化的模型。

增量式可视化

该文章定义增量式可视化为“一种迭代式改进的可视化流程,它通过增加或者更新可视化的细节,逐步完成对一个数据集的可视表示”。作者们定义了两个重要概念:数据块和处理步骤。对于一个大小为的数据集,可以将它分割为i 个数据块,其中1 ≤ i  ≤ n 。对于一个共有个子步骤的运算子,在增量式可视化中被设置为个处理步骤,其中1 ≤ j ≤ m 

相关工作

作者们从增量式可视化的视角,提取出一些相关工作与增量式可视化的对应关系。这些相关工作分为两种。一种是基本的可视化架构,另一种是特定的可视化方法。前者包括核外可视化,它与增量式可视化中的数据分块相对应;递进式可视化,与数据分块、处理过程细分、不间断的交互皆有关联;并行可视化,对应于数据分块和过程细分;驾驭式计算,与过程细分和不间断的交互相关。后者包括,流数据可视化,与数据分块有联系;分层可视化,与过程细分有关;在线动态图可视化,与数据分块有关。

而增量式可视化与这些相关工作相异之处在于:后者是由问题驱动的,是被动的。驱动它们的问题,一是输入数据不适合整体式可视化,例如,数据集太大无法存入内存;受限于网络需要以流数据形式进行传播;数据集大小未知等。二是运行时间过长或者不符合流畅交互的要求。前者不仅可以由问题驱动,还可以主动反映用户的意愿,由用户感兴趣的输出结果驱动,例如,用户希望加快第一个可视化结果的出现速度,或者用户希望首先观察自己感兴趣的数据子集,可能是整体的趋势,也可能是离群值,因而对数据按照优先级进行排序。

增量式可视化带来了许多机遇,它允许用户观察早期的中间可视化结果并进行交互;它支持用户对不完善的可视化进行快速地调整;它使用户更好地理解最终的可视化表示结果是如何产生的。同时,它也带来新的挑战,即如何创建增量式可视化以及如何使用增量式可视化。

创建增量式可视化的挑战在于决定如何划分数据块和运算子。只进行数据块划分的方式称为质量优先策略,因为它要求每一个数据块都要经过全部的处理步骤才能输出成可视化结果。只进行运算子细分的方式称为数量优先策略,因为每一个步骤都处理全部数据。增量式可视化中常见的是平衡这两种划分方式。

使用增量式可视化的挑战在于用户面对的可视化结果是不全面的,需要从数据和处理过程的角度判断可视化中间结果的可靠性,从而决定是否进行交互。过早进行交互,则交互对象仍不适合进行交互;反之,则会浪费宝贵的时间。因此,增量式可视化需要提供有意义的和足够的信息,使用户了解当前在可视化过程中所处的位置。

一个增量式可视化过程模型

数据状态参考模型

数据参考模型被证明和数据流模型具有同等的表达能力。该文章提出的模型以数据状态参考模型为基础,通过替换运算子而建立,充分利用原有模型的表达能力。

在数据参考模型中,数据存在多种状态,包括输入(原始)数据、派生数据、几何数据和图像数据等。数据之间的转换关系包括,过滤,即输入数据转换为派生数据;映射,即派生数据转换为几何数据;渲染,即几何数据转换为图像数据。

在该模型的图形表示中,运算子代表算法步骤的封装,用于数据转换,通常表示成矩形节点;数据传输则表示为运算子之间的连接线。

数据状态参考模型的扩展模型

扩展模型增强运算子和数据传递,以对运算子细分和数据分块进行建模,同时显式建模数据源和结果视图。

增强的数据传递对分块后的数据在不同运算子之间的传递进行建模,它们被表示成相邻运算子连接线上的若干标记,如图1。标记线的数量代表数据块的数量,连接线之间的距离表示数据块的大小。数据块可以来自原始数据源,也可以来自对原始的整个数据集或者较大的数据块进行定序(sequencing)得到的较小数据块,或者对较小数据块进行缓冲(buffering)后得到的较大数据块。

图1. 左侧为完整数据的图形表示,右侧为分块数据的图形表示。

增强的运算子对可视化过程的细分进行建模,被表示为运算子底部从白色到黑色的若干标记。每个标记代表着某个中间步骤的结果,其中黑色代表可视化过程完成时的结果,灰色代表部分完成时的结果,白色代表输出的是未经改变的输入,从而可以表示可选的运算子。见图2。灰色标记的数目可以用于表达中间过程的数目,也可以仅作为象征性的数目。

运算子执行返回一系列结果:如果运算子是可选的,则第一个输出结果与输入相同,接着是质量提高的部分结果,直到最终的完整结果。每一个阶段的输出都应是后续运算子的有效输入,所以导致数据状态转换的运算子不可以是可选运算子。

一个运算子中间过程的最大数目取决于运算子最大中间步骤数,而需要被产生的中间结果的数目则取决于用户的需要,比如根据用户对更新速度的需求,不显示所有的中间的结果,而只对每k 个中间结果显示一次,或者在两个中间结果的差异超过一定的阈值时才需要更新显示。

图2. 增强后的运算子,左侧为非可选运算子,右侧是可选运算子。

于是这两个增强使得模型依然由数据源、运算子、最终视图之间的连接线连接而成,和原来模型的区别仅仅在于显式地显示增强的过程细分和数据块划分。

数据分块

数据分块包括定序和缓冲。

定序将较大数据块分割为小数据块,由2个参数进行控制:数据块大小和排序策略。数据块的大小随着需求或者数据性质的变化而调整,例如,对所需求的不同数据层次,选择不同的大小;排序策略定义了分块数据分发的顺序,反映用户的兴趣,当数据块可以计算与用户的兴趣的相关度时,可以按照这种相关度进行排序。

缓冲则将大量小数据块合并成大数据块,这样做既能避免输入没有实际意义,提高有效性;又能减少因小数据块过多造成的开销,提高效率。设置缓冲的参数有数据块大小和时间间隔。数据块大小设置了分发数据块的最小值,同样需要考虑数据性质,比如不同数据层次要求不同大小的数据块。时间间隔是分发数据块的最小时间,用来调节帧率,可以防止过快更新造成的闪烁。

不同参数设置的定序和缓冲可以结合使用,生成多种分块方式。例如,分割式数据块(partition chunk)和修正式数据块(revision chunk)。分割式数据块是指每个小数据块交集为空、并集为数据集全集的数据分块方式。修正式数据块是指每个数据块比它之前的数据块更新或者质量更高,并且替代之前的数据块,例如,一个细分的运算子,由中间部分结果到最终结果的输出就满足这一过程。定序和缓冲的串联可以使得数据分块方式更复杂,比如可以实现多层次的分割方法。

运算子细分

通过多个处理阶段或者经历大量迭代/循环步骤的运算子才可能进行进一步的细分。对一个运算子的细分可以从两方面来考虑。一方面,从输入的角度,参数(parameter)可以控制运算子的细分方式;另一方面,从输出的角度,测度(metric)可以考察结果的质量和完整性,且其值可以作为运算子的输入参数从而引导处理过程。在模型的图形表示中,参数和测度分别表示成朝向和远离运算子矩形的三角形,如图3。

图3. 左侧为运算子的参数的图形表示,右侧为运算子的测度的图形表示。

常见的测度有3种:

  1. 质量测度,用于评估单个数据块的质量,比如在可视化流程中已经经历的处理步骤数;
  2. Δ测度,用于评估相邻两个数据块的差异,可以在数据层面和视图层面进行测量;
  3. 误差测度,对于当前处理完成的数据块,评估当前结果相对于完整结果的误差。

这些测度应当被协调起来使用。

数据分块和运算子细分的结合

最基础的情况有两种:数据分块在运算子细分之前,或者之后。二者进一步的组合,可以形成更加复杂的场景。以下假设数据分块产生个数据块而运算子细分产生个数据块。

当数据分块在运算子细分之前时,运算子对于如何处理数据块序列有不同的选择,这些选择可以视为一种滑动窗口的设置,并假设滑动窗口的大小为Mem 。当 Mem = 1 时,运算子会在处理完毕一个数据块之后再进行下一个数据块的处理。当 Mem > 1 时,运算子接收Mem 个数据块作为输入进行处理,这对应于运算子要求输入数据大小超过阈值的情况。当 Mem = ∞ 时,运算子使用所有数据块作为输入,当新数据块到达时,它和之前到达的所有数据块一起被处理,运算子的输出也会相应更新。输出最多被分为i×j 块。当数据分块在运算子细分之后时,输出最多为 j×i 块。

运算子何时结束对当前数据块的处理,转而处理新的数据块,由参数Quality 来控制。Quality 可以被定义为可以终止对当前中间结果的改善所需要的新数据块数目。在这种定义下,当Quality=1 时,每当有新数据块到达,运算子都会终止当前计算,对新数据块进行计算,这样会允许尽可能多的数据块通过流水线,而不关心它们的质量,是数量优先策略。当Quality=∞ 时,运算子对当前数据块处理完全部步骤后才会处理下一个数据块,这是质量优先策略。

应用扩展模型时的考虑

创建增量式可视化

设计增量式可视化时最重要的是决定是否分割数据、细分运算子或者同时使用二者。这个问题可以从3个角度来考虑:

  1. 输入的角度:被动决定是否使用增量式可视化,比如数据能否存储于内存,运行时间是否过长等;
  2. 输出的角度:依据输出的需要主动决定是否使用增量式可视化,这些需要可以数量优先或者质量优先策略来解决;
  3. 处理过程的角度:在处理过程中对若干目标进行优化,比如最小化数据块数量以减少开销等。

作者们还提出了多线程的软件架构。该架构将每个运算子映射成一个异步的工作线程,并可以存取一个数据块优先队列,如图4所示。

图4. 上部为可视化流程图局部示意图,下部为对应的软件架构。

一个线程通常工作在内部循环(c)中,迭代式地对一个数据块进行处理和改进,直到结果满足给定的退出条件,退出循环,如果满足一个最终条件,则可以作为下一个运算子的输入(d),否则将中间结果加入该运算子管理的优先队列中,等待被继续处理(e)。在这个架构中,参数数据块大小对应于扩展模型中的数据分块的数量,优先队列的排序方式对应于扩展模型的处理策略,退出条件对应于控制运算子细分。

使用增量式可视化

用户使用增量式可视化时,首先配置 参数,再运行,最后交互式地观察 可视化。该文章列举了三种用户参与度递增的场景。

检视可视化

这一场景关注于运行和观察。用户逐步观察可视化生成的过程,这使用户更好地理解可视化过程,从而能确信当前可视化是否准确反映了数据。这一场景包括图可视化中观察迭代式改进的图布局、聚类数据预处理步骤的动画等。

定制可视化

这一场景关注配置和运行。用户仔细优化数据分块和运算子细分,从而满足需求。例如,在一个监控的场景中,符合预期的结果可以位于不符合预期的数据之后。

与可视化进行交互

这一场景关注观察和配置可视化。交互式地调整可视化的设置,以调节可视化过程。例如,当超出预期的数据块负载出现时,通过调节Quality 参数,达到解决时间阻塞的目的。

使用案例

该论文的作者们将增量式可视化模型应用于NTHSA FARS(Fatality Analysis Reporting System,死亡分析报告系统)数据集中。这个数据集涵盖了2001至2009年间美国所有的交通事故。由于数据集过大,整体式可视化达不到交互式分析所需要的帧率,因此有必要选用质量和错误率合理的增量式可视化方法。

数据描述和需求

该数据集包含超过370,000条致命交通事故的数据,每个条目包含多个属性:经纬度、一天中的时间、人数、死亡人数、工作日的限速速度,醉酒者数目等。这里的任务是,用户指定6个属性的值,系统从数据中找到最相似的条目(前5%),并以密度图的形式展示给用户。

图5展示了一种可能的整体式可视化的流程图,用户修改属性值并开始一次查询,系统从相似性搜索开始,生成散点图,再使用非线性映射方法计算密度图中不同颜色对应的像素生成密度图。在Intel i7 4核处理器上运行,完整的处理时间约为4秒,而目标的处理时间应低于0.2秒,因此用户无法进行流畅的探索。

图5. 该论文应对这一场景提出的整体式可视化的流程图。

该论文的作者们选用增量式可视化,调节数据分块和运算子细分的方式,观察处理时间和图像质量,选择合适的增量式可视化。使用数据分块时,虽然处理时间与数据块大小成反比,但是错误率和数据块大小成正比,因此需要同时进行数据分块和运算子细分。运算子细分使用输出质量较低的密度图计算方法,快速计算中间结果。用户需要找到两种方式的平衡,以平衡数据数量和图像质量并保持可交互性。

寻找这一平衡的过程包含3个步骤:

  1. 对增量式可视化进行建模,选择需要的参数:通用参数如数据块大小、Quality 等可以预设默认值,Mem 则需要用户根据语义进行设置;
  2. 选择测度指标,包括错误率、质量、不同迭代步的差异等的测度指标;
  3. 参数化以实现数量/质量平衡,这一步是观察测度指标值,调节模型中的参数。

增量式可视化流水线建模

增量式可视化的流水线如图6。在数据源 之后增加了定序 进行数据分块操作。相似性搜索 运算子的Mem 设为1,因此,它分别处理每个数据块,对每个数据块,计算最相似的前5%的条目。这些最相似的数据被传递到散点图 运算子,该运算子的Mem 为∞,因此会将新数据块与已有数据块共同计算在散点图中。接下来的密度图 运算子使用计算时间依次增加的3种算法:单色映射、线性映射和非线性映射,同时允许不经处理直接输出散点图的结果,因此共有4种输出。

图6. 该论文针对这一场景提出的增量式可视化流程图。

原型系统的界面如图7所示,创立原型系统的目的是研究和确认增量式可视化模型的有效性。原型系统的右上角显示的是流程图,选取其中的一个运算子,在右下角会显示该运算子的细节,包括参数和测度。点击参数或测度可以进行调节,右侧中部是测度值随时间变化的趋势图,可以在右下角视图中控制是否将多个趋势图叠加以供比较。

图7. 该论文用于验证模型有效性的原型系统。

选取过程特定的测度

散点图 运算子包含的测度指标是误差,用于估计数据分块后计算的结果中错误的比例。这一测度指标可以用于估计分块后单独处理数据对于整个数据集的代表性。密度图 运算子计算三种算法输出结果的质量(x ∈ {a, b, c}):

同时还计算相邻可视化结果的差异:

其中是全部的像素,n 对应单个像素。当差异低于预设的阈值时,可以暂时不渲染当前结果甚至结束整个处理过程。

设定参数均衡质量和数量

首先,用户设置较小的数据块大小使得每个数据块包含1000条。然后,用户设置不同的Quality值,比较不同密度图计算方法的质量,发现方法c只有在1.5秒之后才能超过方法a,同样,方法b超过方法a的时间也无法达到交互性的要求,因此,用户选择方法a。然后,用户增加数据块大小,发现数据块大小为25,000时,帧率接近每秒5帧,符合交互性要求。同时错误率为0.011,对用户的探索目标来说可以接受。

该论文作者们列举了不同的数据分块和运算子细分方式的组合,以及相应的速度和错误率,发现数据块大小必须小于29,000(数据块数量超过13);复杂的算法效果好但是需要更多的时间,因此用户倾向于选择将运算子细分为3步。

结论

该论文提出的模型,提供了对增量式可视化的高层次表示,和与可视化流水线进行交互的合适方法。该论文的作者们清楚地将这些交互集成进了模型中,允许用户通过交互引导可视化过程。模型中的参数可以在运行时交互地探索来确定。模型提供的图像表示使得交流变得容易,因为它清楚地将处理架构(数据分块和运算子细分)和处理行为(由参数进行控制)区分了开来。

然而,这一模型并不能指导增量式可视化的创建者如何使用这一模型。一个用户可能需要探索复杂的空间来找到合适的数据分块和运算子细分设置。

参考文献

H. J. Schulz, M. Angelini, G. Santucci and H. Schumann, “An Enhanced Visualization Process Model for Incremental Visualization” in IEEE Transactions on Visualization and Computer Graphics, vol. 22, no. 7, pp. 1830-1842, July 1 2016.

发表评论?

0 条评论。

发表评论


注意 - 你可以用以下 HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>