EventThread: Visual Summarization and Stage Analysis of Event Sequence Data

论文：EventThread: Visual Summarization and Stage Analysis of Event Sequence Data

作者：Shunan Guo, Ke Xu, Rongwen ZhaoDavid Gotz, Hongyuan Zha, and Nan Cao

发表：VAST 2017

简介

本文提出了一种对事件序列数据进行可视化概括和阶段分析的技术，并实现了一种全面而集成展示和分析数据的新型可视化系统。

动机

事件序列数据是的是在一段时间内发生的一系列事件，分析事件序列集合可以得出语义上重要的顺序模式。目前已经有许多分析和可视化技术来研究这种数据形式，但仍存在一些问题：

使用统计分析方法来提取明确匹配的事件模式，无法获取相似但不相同的事件序列的潜在集群。
难以将大规模异构事件序列数据转换为统一数据模型。
对提取的结构没有做详尽的语义解释。
对用户调整参数验证实验的支持度不够高。

因此，我们引入了EventThread，用于视觉总结大规模和高维事件序列数据。

系统设计

主要分为预处理模块，分析模块和可视化模块。

数据转换和分析过程

数据过滤：真实事件序列数据包含大量事件类型，分布稀疏且频率有限。实现中使用n-gram（n = 1,2）统计模型将TF-IDF得分低的事件视为噪声去除。

序列比对：移动事件序列，使其沿着共同的起始时间轴对齐。
阶段折叠：将对齐的事件分成多个阶段。
数据建模：事件序列数据可以由三路张量$\mathscr{X} \in R{+}^{M \times T \times N}$表示。其中M，T，N分别表示事件，阶段和实体的数量。$\mathscr{X}{i j k}$表示在第k个实体的j阶段发生的第i个事件。
汇总算法：上步中我们得到了表示事件序列数据集的三路张量χ，利用张量分解得到潜在的序列模式，即线程。转化成如下的优化问题：

$\min \|\mathscr{X}-[\lambda ; \mathbf{A}, \mathbf{B}, \mathbf{C}]\|^{2}$ $\mathbf{B}^{T} \mathbf{B}=\mathbf{I}, \mathbf{A}, \mathbf{B}, \mathbf{C} \in R_{+}^{[N, T, M\} \times K}$

表示张量CP分解算法，产生NK，TK和M*K的因子矩阵A，B和C，K是表示潜在线程数的输入参数。使χ与这些分量的乘积之间的误差最小化，A，B和C分别表示线程在事件，阶段和实体上的分布。

正如文本分析从文档集合中导出主题一样，我们需要从事件组成的序列集合中导出潜在的线程。不同与主题建模的是三路张量允许对潜在线程进行阶段、事件和实体三个方面的解释。