多视图多类别散点图的利用集合覆盖优化的数据采样 (Data Sampling in Multi-view and Multi-class Scatterplots via Set Cover Optimization)

对高维数据进行可视化,一个常用的方法是散点图。对于具有2个以上维度的数据,可以使用散点图矩阵(scatterplot matrix, SPLOM),其中每一个视图是某2个维度的散点图。随着数据量的增加,在散点图中可能出现点的重叠问题(overdrawing),影响后续的分析。有许多方法用来缓解这种问题,比如调整散点图中的符号(marker),改变它的大小、透明度、位置等;使用密度图;进行数据采样等。本文提出了一种在散点图矩阵中对多类别数据进行多视图联合优化的数据采样方法。

首先,对于一个散点图,利用Z-order曲线进行数据采样。在二维空间中,利用四分树不断地对空间进行四分,直到所有的小格中只有一个或零个数据点。接着,按照左下-右下-左上-右上的顺序(如果原点在左下角)递归地把所有的点连接起来。根据给定的采样数量,将曲线中的点按顺序分段,并在每段中随机挑选一个点保留下来,组成采样结果。

此例中,每三个数据点采样一个

根据以下公式:

采样的结果coreset Q与原始数据集P的核密度估计(KDE)误差具有一定的上界,因此,此方法得到的采样结果在一定程度上可以代表原始数据。

对于多视图的散点图矩阵,首先计算出每个视图Z-order曲线中分段的数据子集(a)。把多个视图的子集结果转换为一个子集-数据点的矩阵(b),其中如果(i, j)项非空,说明子集i包含数据点j。接着,把相同的列合并(c)。在合并后的矩阵中,把采样问题转换为一个精确集合覆盖问题,并利用启发式的方法求解。如果不能恰好覆盖,就要选择更多的点,因此采样数目可能会多于指定的数量。

对于多类别的散点图,首先对每个类别的数据,得到曲线的数据子集,再把它们合并,作为一个局部(local)视图的结果;然后忽略类别,在所有数据上得到Z-order曲线的数据子集,作为全局(global)视图的结果。对这两个结果做同上多视图的处理,得到多类别在某一个视图中的采样结果。

随着数据维度的增加,散点图矩阵中的视图数量会平方增加,计算所需要的时间也会增加。因此,文中把曲线的数据子集看作聚类结果,并通过相似性比较的方法来去除一些视图,以减少计算联合优化采样结果的时间。

此外,文中还提到利用此方法进行异常点检测的方法。

文章进行了大量的实验以及用户研究,以说明此方法的有效性。

在一些数据集(20K)上,文中方法所用的时间与采样数据的大小(采样目标1K)

文中方法(b)与蓝噪声采样(c)结果的对比

在多类别数据集中,文中方法与随机采样、蓝噪声采样的对比。图中值为KDE误差。

[1] R. Hu, T. Sha, O. Van Kaick, O. Deussen and H. Huang, “Data Sampling in Multi-view and Multi-class Scatterplots via Set Cover Optimization,” in IEEE Transactions on Visualization and Computer Graphics.
doi: 10.1109/TVCG.2019.2934799

评论关闭。