从事件序列中提取和可视化子模式(CoreFlow: Extracting and Visualizing Branching Patterns from Event Sequences)

时间事件序列,如应用程序日志数据和Web访问者点击流,有助我们理解用户行为和做相应的决策。事件序列数据的可视化和分析是一个备受关注的研究领域,但仍然是一个尚未解决的问题。序列数据集可以包含数千个或多个不同的序列。这些序列中的每一个都可能由数百个有序事件组成。独特事件的数量可以是成百上千。巨大的数量和复杂性使得传统的可视化技术不适用。即使我们将事件聚合为较少的类别,仍然很难提供一个很好的概览。

如果我们认为每个序列都是旅行者的旅程,那么一个有效的可视化应该会显示出沿途重要的里程碑(事件)。尽管在具体的道路和时间上存在差异,旅行者们可能在旅行的早期会走一些共同的里程碑。在达到某些里程碑时,一些旅行者提前结束行程,而其他人则会继续探索其他里程碑和目的地。这篇文章的核心技术也是基于这种方法来提取分支模式,CoreFlow由三个递归的步骤组成 [1]:

  1. 排序:根据事件在序列中出现的频率进行排序,如果排名相同,我们比较其在每个序列中出现的平均索引号,选择排名最高的事件E。
  2. 划分:对所有序列,根据其是否包含E事件,将这些序列分别为两部分。
  3. 剪枝:对于包含E事件的序列,去掉从序列开始到E事件的所有事件。剪枝的终止条件是,当事件都被剪掉或者事件的支持度小于我们设定的阈值(包含某一事件的最小序列数)。最后我们递归调用以上三个步骤。

图1:提取子模式步骤

 

图1所示是我们提取子模式的具体步骤。在第一行中,在Rank操作中,我们可以看到C事件的支持度(#SEQ)为4,平均索引号(AVGIDX)为0.5,所以C事件出现次数是最多的,排名最靠前。然后在Divide操作中,我们选择C事件,根据C事件将序列分为两部分,虚线上面的序列包含C事件,虚线上面的不包含C事件。在Trim操作后中,对于包含C事件的序列,去掉从序列开始到C事件的所有事件。在第一次循环结束后我们得到了一个子模式(从start到C事件)。然后我们循环利用以上过程,最后我们可以从图2中,看出我们最终的提取结果。

图2:原始的序列数据以及提取出的子模式

 

图3所示是我们使用CrowFlow方法提取的一个网站点击流数据,我们首先来看前景的点边图,在每个节点上标注了提取出得关键事件,旁边的百分比表示该事件在序列出现的比例,边的粗细表示从一个事件到另一个事件的序列数。背景是一个冰柱图,每个矩形的宽度表示该事件的所占的比例,矩形高度表示从一个事件到另一个事件的平均时间花费。

图3: 混合使用冰柱图和点边图

 

总结:本文提出了利用子模式进行事件序列分析的思想。我们提出了一种新的技术——CoreFlow,这种技术通过递归应用排序,划分和剪枝三个阶段来提取子模式。与序列模式挖掘的技术相比,CoreFlow具有可扩展性,能够在几秒钟内,计算出事件数以百万计的模式。我们设计并开发了一个基于CoreFlow系统。来自用户的反馈证实了我们的方法在某些领域中的有效性。

[1] Liu, Zhicheng et al. “CoreFlow: Extracting and Visualizing Branching Patterns from Event Sequences.” Comput. Graph. Forum 36 (2017): 527-538.

评论关闭。