Paper Reader:Visual Abstraction and Exploration of Multi-class Scatterplots

接着上一篇文章,探索密集地理数据可视化的优化。这次从论文上下手。以浙大博士陈海东写的《Visual Abstraction and Exploration of Multi-class Scatterplots》入手。这篇文章首先介绍了解决散点图覆盖问题的优化方法,并设计了一个系统原型。我从散点图特征的介绍写到论文笔记,并思考进一步研究的方向。大概有10篇左右的相关论文,论文名都给出,大家可以google到,如有不便,也可直接向我索要。当然论文以及文章的图片都是归作者所有,如若侵权请告之。最后的最后,本人行文潦草,如若发现错误也可联系我。


1. 散点图

散点图[2]是用来显示两个定量变量之间关系的图像,两个变量通过x轴和y轴的定位分布在一张图里面。散点图的数据集依据图像可能得出的模式有:两个变量的线性相关性、图像的斜率来表示两个变量的相对变化趋势、点分散的程度表示变量之间的关系。可以看看下图的几个例子,值得留意的是下图中第一行第三个散点图出现的离群值(outlier)。散点图被广泛用在可视化数据集的离群值、积累、局部趋势和关联关系。在多类散点图中,每个不同的类别通过不同的颜色或者形状呈现给分析人员。

当数据太多时,在散点图中就会出现密集区域的点重叠的问题,也就是在当前图像范围中,一个像素点包含多个数据点最终导致散点图无法提供给分析人员的洞察,这在上一篇文章中也说过了。当然,在多变量数据可视化的情形下,重叠问题还会导致不同的类别相互扰乱。针对这种问题,现有研究已经在使用的一些公共方法有等高线(contouring)、混色(color blending)、颜色交织(color weaving)。这三个方法的描述如下:

  • 等高线:Adrian Mayorga在13年发表的一篇论文,题目为《Splatterplots: Overcoming Overdraw in Scatter Plots》,中设计了一种新颖的散点图——splatterplot,他在文中指出等高线的引入能很好地勾勒出不同类别的形状,但等高线不能捕捉到离群值。这里我们再看看多变量重叠的地方(比如下图)出现图中混淆视觉的情况,这是因为出现了同心的等高线。我们需要避免这种情况。

  • 混色:Adrian使用混色来区分不同类别、变量的图像,更具体点的是使用色调来区别不同的类别,应对图像重叠的问题则通过亮度和饱和度来区分重叠程度。这样就规定了一个颜色混合的设置(如下图):从白色(密度为0)到单变量的密度颜色、再到多变量的颜色混合。

  • 颜色交织:H.Hagh-Shenas在03年发表的论文《Weaving versus Blending: a quantitative assessment of the information carrying capacities of two alternative methods for conveying multivariate data with color》中针对颜色的渲染方法进行了实验,并指出相比混色,颜色交织能更有效地传达多元数据的空间分布信息。可以看下图(取自另一篇论文《A new Weaving Technique for Handling Overlapping Regions》,Martin等人写),虽然交织的方法比混色能更加突出重叠区域,但是不是很清晰地表达复杂区域的分析特征。

作者指出这三种方法都存在陈述性误导。此外,对于不同类别之间渲染的顺序也会导致重叠区域的变化,不能保留完好的定量分析。

在进一步阐述中,作者接着又将常用的方法划分为3类,前面这3种方法都属于第一类。这三类方法分为视觉通道改变、密度估计、空间变形。

  • 视觉通道改变:视觉通道改变就是改变图上点的大小和透明度等属性,这种方法的问题在于使用了一个有限的方法(可视化属性的类型)来兼容可能数量极大的类别。比较简单的方法有动态调节点的大小(在密集区域使用小点,在稀疏区域使用大点来突出离群值的显示),比较复杂点的就是Martin采用的对齐交织技术(The Aligned Weaving Technique),这种对齐的方法将重叠区域的不同类型均匀地着色,使得颜色的区分更加明显。对齐策略又分为堆栈对齐、膜对齐,其中的区别如下图。

  • 密度估计:密度估计就是将点的数量压缩,这种方法一定程度上忽略了离群值。简单的方式就是将绘图空间划分为不同的区域,并计算不同区域内点的数量(Alpha blended scatterplots)。划分方法也有六边形格、精确的数学模型(continuous scatterplot)、核密度估计(kernel density estimation,简称KDE)。KDE使用来估计未知密度函数的工具,其详细公式定义可看wiki。这个名称中的内核(kernel)是在密度估计公式中\( \hat{f}_{n}(x) = \frac{1}{n} \sum\limits_{i=1}^{n}{K_{h}(x-x_{i})} = \frac{1}{nh} \sum\limits_{i=1}^{n} K( \frac{x-x_{i}}{h}) \)的函数K,函数K为一个非负的函数,有多种类型。除了类型的选择会影响估计外,带宽h是也一个影响元素。Michael在12年发表的论文《Interactive Level-of-Detail Rendering of Large Graphs》中提到KDE这种密度估计的方法能避免节点的扭曲和数据的展示。在节点的密度估计公式上,将节点的位置和其对相邻节点的影响作为一个权值融入到计算中,详细的计算过程可看论文。最后在图像上得出的结果与热力图类似,可以从下图结果中看出,不同的缩放级别展示的散点也是不一样的,这样因为使用了四叉树来分层次存储节点。

    还有一些重叠轨迹的可视化方法。但这些方法都对离群值进行了忽略,David Feng在10年的论文《Matching Visual Saliency to Confidence in Plots of Uncertain Data》中使用mean emphasis(翻译过来叫什么?平均偏重)来弥补KDE密度估计方法中离群值的可视化,将离群值展示出来。mean emphasis。通过下面的对比图中,左边为标准的散点图,中间为使用mean emphasis的概率密度分布,右边为纯净的概率密度分布。可以看到左上角的离群值有非常大的偏差,因此在密度估计图里看不到,这也是密度图能发现过滤后的模式的原因。而mean emphasis将本来因为聚合关系被模糊为一个整体的几个亚类别分解了出来。

    上面提到的Splatterplot在限制屏幕复杂度的情况下,将离群点进行采样显示(详细过程可看splatterplots的论文4.5章)。混色和颜色交织的方法也只是在一定程度上实现多类的密度表示可视化。

  • 空间变形:空间变形就是将密集区域的点按照某种算法移动到稀疏区域,这种方法直接改变了点的分布,这种方法在需要定量分析的场景是不合适的。Daniel A. Keim在98年发表的《The Gridfit Algorithm: An Efficient and Effective Approach to Visualizing Large Amounts of Spatial Data》文中制定了一个解决大量数据的重叠的方法——Gridfit algorithm,其思想为层次化地分割数据空间。将密度区域划分为4个子区域,并以四叉树存储必要信息。以下图为例,36个像素区域中有14个点,首先均等地划分4个3X3的子区域。当某个区域的节点数超过了其区域的大小时,比如左上角的区域有10个节点超过了其子区域的大小9,我们就需要重新划分区域使得最后结果中,左上角的区域大小为15,里头有10个节点。划分好后,改变每个子区域内的节点使得相对均匀(也就是每个像素点上只有一个节点)。

    其他还有让使用者自己在图像的重叠和失真之间找到平衡的generalized scatterplot(《Generalized scatter plots》),通过椭圆的图像参数存储聚类数据的the ellipsoid pixel placement scheme(《Enhancing scatter plots using ellipsoid pixel placement and shading》),通过修改局部特征区域的坐标曲度的warping method(《ViSizer: A Visualization Resizing Framework》)。这三种方法的图像展示如下图,从左到右依次为generalized scatterplot(其将重叠区域在某个维度放大)、scatterplot using ellipsoid pixel placement and shading、scatterplot using warping method。

他们也参考了上一篇文章提到的芝加哥人种分布图,并指出该图使用的dot map采用了point sampling scheme来呈现多类的分布呈现方法,指出该方法的优点有二:其一,不同类型的颜色展示没有导致多种类型混淆的染色方法。其二,相关的特征比较都是局部的,没有使得整张图的混乱。最重要的是,这个方法提供了一种点取样的方法来还原的多变量的分布。当然其问题也在上一篇文章中提到过。基于这张图的灵感,论文作者提供了一种多类散点图取样方法——基于蓝噪声的多类散点图取样方法,并应用于一种层次结构上的取样过程,在系统级别上也改进了交互方式,尝试提供了辅助操作以提高散点图的可读性,比如刷选(brushing)、聚焦加上下文(focus+context)。作者通过这样的可视化抽象方法(visual abstraction scheme)使得采样点能描述多类节点的分布。

2. 点密度估计

密度估计的方法在上面已经详细介绍,作者使用的是KDE的密度估计方法,密度公式 \( \hat{f}_{i}(x) = \sum\limits_{i=1}^{m} K_{h}(x-x_{i}^{j}) \)中的\( x_{i}^{j} \)为第i类的数据点,采用的是高斯核密度估计。

3. 蓝噪声取样

取样是保留特征的前提下还能减少渲染点数量的一种方法。蓝噪声指具有最小的低频分量并且频谱中没有明显峰值出现的非周期性随机信号,在有限带宽内,其功率谱密度与频率成正比。在计算机图形学中,蓝噪声用于生成半色调抖动图像,产生适合印刷等再现方式的像素空间结构,这种结构更符合人类视觉特点。蓝噪声样本分布的随机性避免了图像失真问题,这经常出现在使用更结构化样本模式;样本分布的均匀性降低了单纯使用随机取样会产生的噪音数量。现有的蓝噪声取样方法大部分都是从其空间位置获取样本属性,其分布取决于从空间位置获取的样本属性。也就是说不能直接作用于非空域数据。

当扩展到多类取样时,当前的研究实现了对更加抽象的离散值的多类取样。然而这组特殊的方法也只是通过一个矩阵将单个类别以及总和相关的蓝噪声属性取样,这个矩阵记录的是不同类别之间间距的。陈家挺写的《Bilateral Blue Noise Sampling》在两个方面优化了蓝噪声多类取样:第一,能够处理更一般的非空间样本参数;第二,实现针对连续的蓝噪声属性取样。

回到这篇论文来,作者采用的是一个自适应的多类蓝噪声取样方法。在样本点的生成过程中,一个\( n\times n\)(n为数据的类别)的对称矩阵\( R^{n} \)用来检查位置x是否有冲突发生。\( R_{i,j}^{x}\)表示第i类和第j类之间在x点上的距离约束,由密度估计来提供具体的数值。从下图可以看到,x最终渲染成了Class1。

重取样是重构通过KDE生成的连续密度场,在论文中提高对于散点图的重取样可能会生成新的点。作者的方法中,重取样作用在一个离散的样本空间内,这个样本空间是基于所有的输入。在《 Multi-class blue noise sampling》文中,计算了每个类别都计算了填充率(fill rate)。在重取样时,总是从当前填充率最高的类别中选取样本点。如若其能通过上述的冲突检测。

当然取样导致的数据不一致还会出现在操作人员在进行缩放的时候,比如下图当中的边界值。

作者实现了层次抽样方法的原因,使得缩放时页面展示的结果能平滑的展现。层次抽样的处理方法是一个粗粒度到细粒度的取样预计算过程。具体的说,在粗粒度大的层次初始化一个参数,使得图上的某个小区域内所有的点能展示出来。这样层级的预计算取样点在下一轮取样中使用。使得最后记录的点以缩放的升序。通过这种方法在缩放时能平滑地展示取样的数据点。

4. 抽象可视化

通过上一步最后得到重取样的多类别点是不会在页面上产生覆盖问题的数据点。但是视觉混乱还是没有完全消除,在空间密度比较高的情况下还是会导致视觉混乱。作者通过两种方法来消除这种影响:一者是点的颜色,二者是点的形状。

  • 作者设计的方式是提供用户自己选择颜色,或者自动生成一套颜色方案。自定义颜色的考虑应该是考虑到不同使用者实际的颜色敏感度以及软硬件的具体表现,而自动生成的颜色。总之就是提高不同点之间的区别。
  • 作者采用了圆点型、椭圆型、点线型的形状。椭圆型是来自《Generating pointillism paintings based on Seurat's color composition》中的点图,作者通过局部线性回归分析计算出椭圆的参数,并将主半径与副半径之比限制为1.618。点线型是来自《Flow-based Scatterplots for Sensitivity Analysis》中的敏感度分析,敏感度分析是分析通过细小的输入变化得到的结果,点上的线为其计算得来的导数。这两种形状的点产生的图如下图,感受一下。

5. 可视化系统应用

作者设计的可视化系统如上图。(a)区域为每个数据类别的提供了一维的直方图来过滤需要呈现的数据,并可以拖拽到主界面(b)区域。(b)区域提供还提供一下高亮、区域选择、刷、注释、快照这些常用的功能。(c)区域为工具栏,可以看到上文提高过得点的颜色自定义,点的形状选定。而(d)区就是配置面板,从KDE的参数到图像中点的大小都能配置。在局部探索方式上,还提供了通过等高线来分析数据分布的密度特征。

6. 个人总结

看这篇文章的目的考虑需要写的论文点。首先KDE和蓝噪声取样都是属于比较成熟的方法,在学术上有很多实施方案和改良,但是将两者结合使用还比较少见,所以作者将其结合起来。传统的处理高密度区域数据渲染方法(混色、颜色交织、等高线)也是在可视化早期就探索出了一些结合方法和变体。离群点的保留和抽象化数据(取样)之间的取舍也有人有所研究。这些内容在我上述提到的10来篇论文中都有所涉及。作者最后还提到一个改进的方向:数据类别的图像渲染顺序会影响到最终呈现的结果。但个人觉得这个问题的解决可能比较难,只能作开放性探索,目前能想到的方法是安装类别的重要程度渲染散点图等人为地设置渲染顺序。第二个是将取样方法在地图上应用,这个方面也是一个比较好的点,但是在前面的论文搜索发现单独的等高线优化散点图,我们只能往将等高线和取样方法结合方向上思考,但也需要注意作者在系统设计上提及过等高线,所以若需要往这个方向写需要加快脚步。


参考

  1. Visual Abstraction and Exploration of Multi-class Scatterplots@IEEE

  2. 散点图@stattrek

  3. 这篇论文的评述@浙大可视化小组