Gaussian Cubes: 在大规模多维数据的可视化探索中实时建模 (Gaussian Cubes: Real-Time Modeling for Visual Exploration of Large Multidimensional Datasets)

大规模数据的可视化探索中存在着两个互相矛盾的需求:表达能力和计算效率。近来提出的一些方法,比如Nanocubes和imMens,使得大数据集上的实时交互探索成为可能。然而,它们支持的分析种类有限,只能快速得到直方图和heatmaps等。为了改善这一情况,文章提出了Gaussian Cubes,可以对数据进行交互式地建模,包括线性最小二乘法,主成分分析等。

与基于data cubes的方法不同,在它们的基础上,除了预先计算数据子集的数量 (count),Gaussian Cubes还提前计算了数据子集的多元高斯分布,这使得它能够在一秒内对具有百万点的数据拟合数百个模型。

图1 Gaussian Cubes额外计算的数据

数据立方体 (Data Cubes)

Data cubes预先计算并存储了许多查询的聚集结果,比如count, min, max,并尽可能地计算了所有的组合。图1左下是在Style和Trans.上建立索引得到的结果。

此外,预先计算的结果可以用来快速得到更多的结果,比如,计算Style中sedan和SUV的和,只需把已有的结果相加,不需要扫描全部数据。

充分数据 (Sufficient statistics)

例如,average = sum / count,因此想要得到average,就要知道sum和count,后两个就是前者的sufficient statistics。

在线性的最小二乘法中,yi = mxi + b,目标是使误差的平方和 E 最小,等价于求

这样,就需要知道 x, y, yy, xy 的和,才能计算出m和b。

Gaussian Cubes

要考虑哪些充分数据要存储下来,哪些模型能够因此快速计算。Gaussian Cubes希望快速计算样本的数量,均值与协方差矩阵。它在传统的data cubes的基础上,提前计算了变量的和,以及变量之间两两相乘得到的乘积的和,如图1右下部分。data cubes计算的变量称作indexing variables,用来进行模型拟合的变量称作modeling variables。

这两种变量可以是相交的。随着indexing variables的增加,存储空间指数增长;随着modeling variables的增加,存储空间平方增长。

利用Gaussian Cubes进行可视化

1. 最小二乘 (Ordinary Least Squares and Generalizations)

考虑平凡的情况,y = Xβ,其中 y: n×1, X: n×b, β: b×1

为了得到参数β,需要最小化|| y – Xβ||2,解得β = (XTX)-1XTy。

矩阵的求逆运算复杂度O(d3),矩阵相乘复杂度O(nd2),总体复杂度O(d3+nd2),其中n为样本数据量,d为维数。

假设xi为矩阵X的第i列,可以得到

因为Gaussian Cubes提前计算了相应的数值,矩阵乘法的复杂度降为O(d2),不再与样本数据量有关。总体的复杂度变为O(d3),可以拟合几百万的数据。

同样,许多泛化的最小二乘法也可以这样快速拟合。

2. 主成分分析 (Principal Components Analysis, PCA)

主成分分析是数据降维的一种常用方法。一般来说,数据集的主成分是方差较大的方向,将数据映射到这几个方向上,希望新的数据能够保持大部分的信号。从计算上看,主成分可以通过协方差矩阵的特征向量得到,这正是Gaussian Cubes能够快速计算的。

考虑一个3维数据集,它的变量为x, y, z,对应的协方差矩阵为

其中,每一项的计算过程为

这样,需要计算的数据是Σx,Σy,和Σxy,而这些就是Gaussian Cubes提前计算好的。

在主成分轴上快速得到近似散点图

如何得到数据在PCA降维后得到的新维度上的分布呢?一个直观的方法是扫描全部的数据。那可以利用data cube来快速得到吗?这里就出现了一个问题:如果没有全部的数据,降维就无法完成,因此无法提前计算散点图。

文章利用Gaussian Cubes提出了一种得到近似散点图的方法。把数据立方体想成有向图的形式,每个结点都是数据子集聚集得到的值,它的子结点都是根据某一变量进行的细化分类。在这一结构上,再基于一个假设:方差下降得越快,映射收敛到能够映射到独立点就越快,作者提出了一个贪心算法,在对结点进行划分的时候,选择使映射方差之和降低最大的划分方式。这种算法在实验中表现较好。伪代码如下图:

实验

在实验部分,作者设计了一个人造数据集以及三个案例研究。

数据集的情况如下:

1. 人造数据

作者生成了一个三维数据集,包含了一百万条数据,并在数据集上生成多元高斯。

2. 天文星体数据

测试了近似散点图的效果。

3. 飞行数据

计算飞机的延迟率,测试数据的线性拟合。

4. 地震建筑应力模拟

用来比较不同方法下PCA的效率。

总结

Gaussian Cubes提供了一些数据拟合模型的支持,但仍有限制,只有在一些所需数据为一阶、二阶的计算能够快速计算。

而且modeling variables的选择仍然依赖人工;模型拟合的好坏没有提供评价标准。

最后,现阶段的Gaussian Cubes基于Nanocubes,迁移到别的系统上也比较容易。作者希望在近似散点图中提出的data cubes的traversal方法能够应用到更多的可视形式以及数据挖掘算法中。

参考文献:

[1] Zhe Wang, Nivan Ferreira, Youhao Wei, Aarthy Sankari Bhaskar and Carlos Scheidegger, “Gaussian Cubes: Real-Time Modeling for Visual Exploration of Large Multidimensional Datasets”, IEEE Trans. Vis. Comput. Graphics, vol. 23, no. 1, pp. 681 – 690, Jan 2017.

发表评论?

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>