用时序MDS视图分析高维数据(Temporal MDS Plots for Analysis of Multivariate Data)

在大数据时代,数据的维度越来越丰富,一个数据往往拥有许多属性(Multivariate)。同时数据越来越多的数据带有着时间属性,如何分析高维数据的在时间上的模式成为一项挑战。在现实中,这类数据包括了计算机通络流量数据、医疗数据、金融数据等。可视分析技术致力于帮助人们理解复杂的数据并且找到数据中蕴含的模式。在2015的VAST论文中,来自德国Konstanz大学的小组提出了时序MDS视图(Temporal MDS Plots)的方法帮助分析高维数据在时间上的模式。

高维数据可视化是可视分析里的一个重要领域。常见的方式有两种:1.通过几何映射把高维数据展示出来,这方面有许多经典的可视化方法:例如平行坐标,把数据投影成直线,映射在每个维度的坐标轴上,还有星型坐标、图标设计等方法。2.把高维数据通过降维投影的方式投影到二维,经典的降维投影的方法有PCA、MDS等。

这篇工作的思想是结合降维和时序分析找到数据中的模式。Dwyer T等人[1]在2004年的工作中把高维数据投影到二维平面的同时把时间轴看成第三个维度(下图左侧)(类似时空立方体),运用这种方法分析金融数据。Hu Y等人[2]则在投影的平面上连线来表示时序关系,用来分析人类体感数据。(下图右侧)

1图1. Dwyer T和Hu Y用降维和时序分析数据

Temporal MDS的思想不同于之前的方法,它包含如下三个步骤:2

图2. 计算Temporal MDS的三个步骤

1. 把高维数据中的每个实体按时间排序,设定一个移动窗口(sliding window),每个窗口内的数据都是原数据的子集,包含相同数量的数据实体,他们在时间上是相邻的。为了保持最后的Temporal MDS视图在在时间上能有过渡的效果,帮助人们更容易找到数据的模式,这个方法要求相邻的移动在数据上有重叠,如下图所示,当数据的重叠比例上升时,Temporal MDS的能更好的展示数据中的模式。具体窗口的大小和数据重叠的比例则和具体数据相关,文章并没有给出一个方法计算。

3

图3. 在滑动窗口间选取不同数据数据重叠率(滑动窗口中包含30个数据,1中没有数据覆盖,2中有10个数据重叠,3中有20个数据重叠)

2.设定好窗口大小和重叠比例之后,数据就被切分成若干个子集。在子集内计算距离矩阵,算法复杂度为O(n^2*m),n为子集内的数据量,m为数据的维度。MDS算法的输入为距离矩阵,通过MDS算法把子集的数据投影到一维空间中,MDS的算法复杂度为O(n^3)。每个数据子集的计算完全独立,所以步骤可以通过并行计算提速。

3.MDS的结果只能保证高维空间中相近的点在投影之后仍然相近,并不能保证投影的后方向一致。如下图所示,如果把在相邻滑动窗口内被重复利用的数据连接起来,可以看到相同的数据点在不同的滑动窗口内的位置相差较大,因此需要对MDS投影结果进行矫正。1维MDS的方向只有两个,按照时间顺序遍历每个滑动窗口的投影结果,如果重复利用的数据点里有超过一半的数据方向与之前相反,则把整个MDS结果翻转。

4 图4. 连接重复使用的数据点,通过Square和Flipped的方式矫正MDS投影

Temporal MDS视图看不到数据具体在每个维度上的分布情况,这个工作提供了Diversity Matrix可视化每个维度在时间上的变化情况。如下图所示,Diversity Matrix的每一行代表一个维度,横坐标的时间范围则和滑动窗口对齐。提供Shannon Entropy 或者Simpson Index两种方式度量每个属性的在滑动窗口包含的数据子集里的分布情况,用颜色映射值的大小。

5

 图5. Diversity Matrix展示每个维度在时间上的分布情况

这个工作还支持用户查找相似的模式,用户可以在Temporal MDS视图上选择一个区域的数据点,通过自动算法找到具有相似的模式。具体算法如下图所示,首先对集合内的所有数据,计算每个数据点和选择数据集的距离,按照这个距离对所有数据点进行排序。基于这个距离用1维的DBSCAN算法进行聚类。得到多个类簇,这些类簇就是潜在的模式,在Temporal MDS视图上用不同的颜色标记出来。

6

最后,作者用这个方式分析网络流数据,如下图所示,能够找到A: Distributed Brute-Force Attack,B: Massive Port Scan, C: Single Port Scan,D: Brute-Force Continuations四种行为模式。但缺少详细的数据描述,我个人只能看到这些行为的持续时间与分布,无法具体解释。

7图6. 使用Temporal MDS分析网络流量数据

评论关闭。