Pattern Trails: 对子空间中数据变化的可视分析(Pattern Trails: Visual Analysis of Pattern Transitions in Subspaces)

在高维数据中,任意维度的组合都形成一个子空间,数据关系则因维度考量的不同而发生改变。举例来说,虎与狼在肉食性、体型、栖息地等方面相近,但在基因组成、群聚性上,虎与猫则更为相近。然而,维度的组合极其繁多,其数量随维度的增多而呈指数级增长。对于如此大量的子空间,我们该如何发掘其中数据关系的变化呢?针对该问题,这篇发表于IEEE VAST 2017的文章[1]提出了Pattern Trails,一种基于可视化的交互式分析方法。

方法设计

Pattern Trails方法主要分为三步:

  1. 获取不同的子空间、并按照相似性进行组织
  2. 展现各个子空间的数据和维度特征
  3. 帮助用户分析数据变化、并将其与维度变化联系起来

1. 子空间的获取与组织

1.1 子空间的获取

任意一个M维(M≥2)的高维数据集都会有2M个子空间。去除0维和1维的特殊情形,则共有 (2M-M-1) 个至少二维的子空间。维度较低的情况下,我们尚且可以穷举所有维度组合;但对于维度较高的数据,我们需要有策略地挑选其中有价值的部分来进行分析。在数据挖掘(Data Mining)领域,一个聚类性明显的子空间往往被认为是有价值的,并相应诞生了“子空间聚类”(Subspace Clustering)方法来进行搜寻。该工作中,作者们采用了名为SURFING [2]的子空间聚类方法来缩减初始子空间的数目。

1.2 子空间的组织

以往的研究通过比较维度成分(如编辑距离)来衡量子空间是否相似,但这不足以反映实际的数据结构。该工作则通过比较各子空间的距离矩阵来分析其数据分布的相似性。具体来说,将所有数据两两之间的距离化作向量(如图1),再计算这些“距离向量”之间的相似性(如欧氏距离),便能得到两个子空间的数据相似性。在此基础上,Pattern Trails采用了自下而上的层次聚类(Hierarchical Agglomerative Clustering),从而提供不同层级的子空间概括。

图1. 通过距离矩阵比较子空间的数据相似性

图1. 通过距离矩阵比较子空间的数据相似性

无论穷举或是筛选,获得的子空间数目依然庞大,需要对其进行有效的组织 —— 而最直接的方法便是基于相似性的聚类。

2. 子空间特征可视化

Pattern Trails利用了较为简单的可视化形式(如图2)来展现子空间特征。首先,所有子空间在水平方向上按相似性进行排列,其数据特征则由MDS投影来表现。投影图利用统一的数据着色方案,以便用户观察、跟踪特定数据的变化。在投影图之下,作者使用了点线形式来说明子空间的维度组成。其中每条线代表一个维度,有(无)格点代表该子空间(不)存在某一维度。

图2. 展现子空间的数据与维度特征

图2. 展现子空间的数据与维度特征

子空间较多时,投影图之间容易相互遮挡,用户便可以选择特定层级的聚类来简化视图。其中每个聚类利用其成员子空间的“维度的并集”作为代表。举例来说,某个聚类包含“ABC”、”ACE”、“BCEF”三个子空间(每个字母代表一个维度),则作为代表的“并集子空间”就是“ABCEF”。然而从图3可以看到,利用并集作代表极容易造成结果的重合,并带给用户误导。

图3. 不同的聚类拥有相同的“并集子空间”

图3. 不同的聚类拥有相同的“并集子空间”

3. 分析子空间中的数据变化

为了帮助用户更好地观察子空间之间的数据变化,Pattern Trails允许用户刷选自己感兴趣的数据局部,并利用折线将各投影图中相同的数据连接起来(图3)。根据连线形式的不同,作者们总结了五种数据变化的模式,并进行相应的特征检测与标记。投影图顶部的红-绿连线(如图4)标记了哪些子空间之间发生了聚类分裂/合并行为。

图4. 数据变化的模式及其自动检测

图4. 数据变化的模式及其自动检测

 

案例分析

图5. 案例分析:US News/QS世界大学排行数据

图5. 案例分析:US News/QS世界大学排行数据

案例分析所使用的数据,是由US News/QS于2012年发布的世界大学排行数据,包含7个维度、总共120个子空间。首先,作者们罗列了所有可能的子空间、并进行了人工分析(如图5(a))。如图可见,在聚类结构发生突变的相邻子空间(垂直虚线处),只有“国际教员评分”(International Faculty Score, IFS)这一维度发生了显著变化。用户所选的数据部分,在考虑了IFS维度后、便从同一个聚类中分裂出来了。另一方面,作者们也利用SURFING缩减了初始子空间后展开分析(如图5(b))。由聚类结果可见,有/无IFS维度是聚类之间形成差异的主要原因,这与人工分析的结论一致。可见通过Pattern Trails,用户能够有效地跟踪数据在多个子空间之间的变化,并分析造成变化的维度因素。

 

总结

总的来说,Pattern Trails展现了子空间的结构与维度特征,并帮助用户跟踪、分析数据在各个子空间之间的变化。尽管仍有部分待解决的问题,如视图重叠、数据可扩展性、投影图的旋转/对称问题等等,该工作对于子空间可视分析的思路依然十分值得借鉴。

 

参考文献:

[1] Dominik Jackle, Michael Hund, Michael Behrisch, Daniel A. Keim and Tobias Schreck. Pattern Trails: Visual Analysis of Pattern Transitions in Subspaces. Visual Analytics Science and Technology (VAST), 2017 IEEE Conference on. IEEE, 2017: 1-12.

[2] Christian Baumgartner, Claudia Plant, Karin Kailing, Hans-Peter Kriegel and Peer Kroge. Subspace selection for clustering high-dimensional data. Data Mining, 2004. ICDM ’04. Fourth IEEE International Conference on, 2004, pp. 11-18.

评论关闭。