流式多维数据可视化的增量降维方法(An Incremental Dimensionality Reduction Method for Visualizing Streaming Multidimensional Data)

降维方法常用于多维数据的分析和可视化。然而,由于(1)高计算复杂度,(2)无法在不同时间步的降维结果中保留用户的心理地图和(3)无法处理数据包含不同维数的情况这三个挑战,降维方法无法直接应用到流式多维数据中。本文[1]介绍了一种增量式降维方法来解决这些挑战,使得用户能够实时可视化和分析流式多维数据。

该方法主要针对PCA(主成分分析)来做改进。首先,它通过采用增量式PCA减少计算量。这种降维方法会在新数据点到来时,增量式地更新数据的低维表示。这种情况下,降维结果的更新只考虑整个数据集的一个小子集,从而降低计算复杂度和内存使用。作者们选用了Ross等人提出的模型[2]。这种模型在计算过程中不断更新样本均值,该均值随后可以用于更新PCA的特征基。也就是说,该模型不需要设置学习阶段,因此我们不需要等到一定数量的新数据到达才执行更新。此外,该模型还支持设置遗忘因子来减少过去数据对最新降维结果的贡献。

接下来,该方法应用Procrustes变换[3](一种几何变换方法)来保存用户的心理地图。该变换通过仅使用平移、缩放、旋转、翻转或这些变换的组合来找到两组位置之间的最佳重叠。它可以帮助找到先前和当前PCA结果的最佳重叠。下面的例子展示了在相邻时间步的数据中使用和不使用Procrustes变换的降维结果比较。从中可以看出,在使用了该变换之后,绘制的结果在所有时间步中都是稳定的。

流式数据中经常会出现新数据具有不同数量维度的情况。如下图(a)所示,n个存储的数据点具有D个维度(灰色区域),m个新数据点具有l个维度(红色区域),其中l小于等于D。当新数据点只有l维时,我们只可以得到l维的PCA结果。也就是说,我们只能使用l维(图中橙色轮廓内的区域)对n+m个数据点应用PCA。或者,如果我们想对所有维度应用PCA,我们只能使用n个数据点(图2a中的灰色区域)来作为PCA的输入。这两种策略都无法将新数据点在全维空间中与现有数据点进行比较。

作者们提出了一种位置估计方法来解决这个挑战。基于“新的数据点可能在其它维度中和其余数据点具有相似的关系”这一假设,该方法首先对l维数据应用增量PCA,然后将m个新数据点的位置投影到D维的PCA结果中,试图最大限度地保留l维的PCA结果中新的和现有数据点之间的距离关系。它的目标函数如下所示。

其中,sui和sui’分别表示从一个新的数据点u到第i个现有数据点在l和D维PCA结果中的距离。我们可以从中求得alpha(缩放因子)和x(新数据点u在D维PCA结果中的位置)。

该位置估计方法引入了两个不确定性,它们表示新数据点投影到D维PCA结果上的不精确程度。第一个不确定性是优化后的剩余花费,用于指示l维PCA结果中每对数据点之间的距离与D维PCA结果中的数据点之间的距离有何不同。

第二个不确定性是基于“当应用位置估计方法时,一个新的数据点没有所有D维的值(新的数据点只有l维)”这样一个事实。我们利用PCA得到的主成分载荷(PC loading)来计算这种不确定性。PC loading表示原始变量和主成分(PC)之间的相关性,它指示每个维度对每个PC的影响程度。作者们希望通过该不确定性来表示当我们只有l维数据时,第i个PC已经覆盖了多少的信息。

之后,作者们测量了不同步骤在不同数据点(100,1000,10000)和不同维数(10,100,1000)情况下的完成时间。结果如下图所示,其中各项的单位均为毫秒。从中可以看出,这些步骤的计算成本较低,可以支持实时流数据分析。

作者们还开发了一个系统来帮助用户对流式多维数据进行可视化探索。它包含三个视图,即投影图,平行坐标和散点图矩阵。散点图矩阵中的背景色用于表示两个维度之间的Pearson相关性系数。

  1. T. Fujiwara, J. Chou, S. Shilpika, P. Xu, L. Ren,
  2. and K. Ma. An Incremental Dimensionality Reduction Method for Visualizing Streaming Multidimensional Data. IEEE Transactions on Visualization and Computer Graphics.
  3. D. A. Ross, J. Lim, R.-S. Lin, and M.-H. Yang. Incremental learning for robust visual tracking. International Journal of Computer Vision, 77(1-3):125–141, 2008.
  4. D. Akca. Generalized procrustes analysis and its applications in photogrammetry. Technical report, ETH Zurich, 2003.

评论关闭。