Visual Progression Analysis of Event Sequence Data

论文：Visual Progression Analysis of Event Sequence Data

作者：Shunan Guo, Zhuochen Jin, David Gotz, Fan Du, Hongyuan Zha, and Nan Cao

发表：IEEE VAST 2018

背景介绍

Event data是指带有离散的时间信息的事件数据，这些事件数据由特定属性聚集排列成事件序列（event sequence）。以一个人的学术生涯为例，单个实体（entity）的事件序列由本科毕业 -> 做研究 -> 发表论文 -> 博士毕业 -> 成为教授这一系列事件组成。

这些事件序列数据揭示了实体在不同阶段的演变过程，对事件序列数据的模式分析可以帮助发现不同人群疾病的发展过程，或是疾病的发展规律，对于不同人群使用不同的诊疗方案可能会有不同的结果，也需要进行比较。由于不同的individual sequence，其序列长度不同，发展速率不同，这就给使用基于时间或是顺序的大规模事件序列数据的总结摘要来进行模式分析带来了挑战。

本文将事件序列数据划分为不同阶段（stage），从而揭示不同群体的行为模式。

本文贡献在于以下三个方面。

提出了一种针对事件序列数据的无监督阶段分析算法。其将事件序列数据进行对齐和划分。提取出不同持续时间的阶段来更好地反映发展模式。
设计了对以上阶段分析算法结果的可视化系统ET2
利用三种评估手段（case study, interview, performance evaluation）验证了系统的有效性。

系统流程

本文提出的阶段分析算法有以下三个步骤组成。

事件表征

使用了类似于word embedding的方法，将每个event sequence看成sentence,每个event看成word,利用skip-gram model进行训练来得到embedding结果。但不同于自然语言处理方法中训练样本通过滑动窗口生成，几个连续的单词形成上下文语境，对于事件序列，不光要考虑事件排列顺序，还要考虑事件发生的时间间隔。因此，对event embedding训练的损失函数中利用权重wij来调节周围事件出现在中心事件附近概率的权重，时间间隔越小，权重wij越大，损失函数表示如下：

事件对齐

使用了一种叫做动态时间规整(Dynamic Time Warping)的算法。它是一种衡量两个时间序列之间的相似度的方法，主要应用在语音识别领域来识别两段语音是否表示同一个单词。如图所示，上下两条实线代表两个时间序列，时间序列之间的虚线代表两个时间序列之间的相似的点。DTW使用所有这些相似点之间的距离的和，称之为归整路径距离(Warp Path Distance)，用来衡量两个时间序列之间的相似性。动态时间规整算法就是要找到这些对应的时间线上的点来最小化两个序列的相似性。

事件序列对齐算法中，先利用最长事件序列初始化一个中间序列，再使用DTW算法找到要比较的事件序列和中间序列的对应关系，事件之间的距离用事件向量的欧式距离进行度量，每次迭代都会对中间序列的向量进行平均化更新，直到所有事件序列都和中间序列找到对应关系，对于一个序列中一个事件对应中间序列多个事件的情况，我们只选取和该事件最相似的中间序列事件。

事件分割

成阶段使用了一种叫做Content Vector Segmentation(CVS)的方法，它是一种将文档划分成为一些连贯的段落的方法。将中间序列类比为文档，中间序列每个向量看成单词，我们认为相同阶段的事件有着相似的语义，分割算法的目标在于最大化每个segment的coherence(内部语义的相干性)。