内容简介：大规模数据的可视化探索中存在着两个互相矛盾的需求：表达能力和计算效率。近来提出的一些方法，比如Nanocubes和imMens，使得大数据集上的实时交互探索成为可能。然而，它们支持的分析种类有限，只能快速得到直方图和heatmaps等。为了改善这一情况，文章提出了Gaussian Cubes，可以对数据进行交互式地建模，包括线性最小二乘法，主成分分析等。与基于data cubes的方法不同，在它们的基础上，除了预先计算数据子集的数量 (count)，Gaussian Cubes还提前计算了数据子集的多元高
大规模数据的可视化探索中存在着两个互相矛盾的需求：表达能力和计算效率。近来提出的一些方法，比如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β|| 2 ，解得β = (X T X) -1 X T y。
矩阵的求逆运算复杂度O(d 3 )，矩阵相乘复杂度O(nd 2 )，总体复杂度O(d 3 +nd 2 )，其中n为样本数据量，d为维数。
假设x i 为矩阵X的第i列，可以得到
因为Gaussian Cubes提前计算了相应的数值，矩阵乘法的复杂度降为O(d 2 )，不再与样本数据量有关。总体的复杂度变为O(d 3 )，可以拟合几百万的数据。
同样，许多泛化的最小二乘法也可以这样快速拟合。
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.
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Design systems
Not all design systems are equally effective. Some can generate coherent user experiences, others produce confusing patchwork designs. Some inspire teams to contribute to them, others are neglected. S......一起来看看 《Design systems》 这本书的介绍吧!
