GaussianCubes:在大规模多维数据的可视化探索中实时建模(GaussianCubes:Real-TimeModeling...

大规模数据的可视化探索中存在着两个互相矛盾的需求：表达能力和计算效率。近来提出的一些方法，比如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。

在线性的最小二乘法中，y _i = mx _i + 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β|| ² ，解得β = (X ^T X) ^-1 X ^T y。

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

假设x ⁱ 为矩阵X的第i列，可以得到

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

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

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.