写在前面：补一个之前已经做好笔记的算法—TKE，该算法是在频繁项集的背景下进行top-k情节挖掘，解决阈值设定问题。
TKE: Mining Top-K Frequent Episodes
定义
有限事件集：$E = \lbrace i_1, i_2, \dots, i_{\rm m}\rbrace$
同时事件集：$SE_{\rm t_i}$ 表示有多个事件在时间点 $t_i$ 同时发生
复杂事件序列：$S = <(SE_{\rm t_1}, t_1), (SE_{\rm t_2}, t_2), \dots, (SE_{\rm t_n}, t_{\rm n})>$，且该复杂事件序列是按照时间顺序排列，其中 $SE_{\rm t_i} \subseteq E$ （额外规定：在复杂事件序列中，忽视那些没有事件发生的时间点）
发生：设存在一个复杂事件序列 $S = <(SE_{\rm t_1}, t_1), (SE_{\rm t_2}, t_2), \dots, (SE_{\rm t_n}, t_{\rm n})>$，某个情节 $\alpha$ 在事件序列 $S$ 中的某个时间段 [$t_{\rm s}, t_{\rm e}$] 发生，其中 $X_{\rm i} \subseteq SE_{\rm i}$ （子集关系）
发生集：$occSet(\alpha)$ 表示情节 $\alpha$ 在 $S$ 上的所有发生时间段
情节：情节 $\alpha$ 是一组非空有序同时事件集合，$\alpha = <X_1, X_2, \dots, X_{\rm p}>$，其中 $X_{\rm i} \subseteq E$
并行情节：包含单一事件（single event）集合（含有多个）的情节称为并行情节（parallel episode）
串行情节：每个事件集只有一个事件的情节称为串行情节（serial episode）
支持度：$sup(\alpha) = \mid\lbrace t_{\rm s} \mid [t_{\rm s}, t_{\rm e}] \in occSet(\alpha)\rbrace\mid$，即情节 $\alpha$ 在事件序列 $S$ 上有多少次发生
频繁情节挖掘：在指定的发生时间窗口中，在复杂事件序列 $S$ 中挖掘那些支持度大于阈值的情节 $\alpha$
top-$k$ 频繁情节挖掘：在频繁情节挖掘的基础上取消设置阈值，改成通过 top-$k$ list 对阈值进行自增
局部列表：在第一次计算一元事件的支持度来提升阈值后，删除那些低阈值的事件，剩下的频繁事件组成局部列表（Location List，垂直结构）$locList(e)$ 表示为事件 $e$ 在事件序列中的所有位置组成的列表，有 $sup(e) = \mid locList(e)\mid$
绑定列表：$boundList(e) = \lbrace [t, t] \mid e \in SE_{\rm t} \in S’\rbrace$，其中 $S’$ 是经过阈值筛选后剩下的事件序列；复合情节$ep$ 与 $e$ 的系列扩展的绑定列表定义为 $boundList(serialExtension(ep, e)) = \lbrace [u,w] \mid [u, v] \in boundList(ep) \land [w, w] \in boundList(e) \land w − u < winlen \land v < w\rbrace$，其中 $sup(ep) = \mid\lbrace t_{\rm s} \mid [t_{\rm s}, t_{\rm e}] \in boundList(ep)\rbrace\mid$
步骤
- 通过计算各一元事件的支持度来提升阈值，同时进行过滤 【Single Episode Increase (SEI)】
- 对筛选出来的频繁事件构造垂直结构（location list）
- 通过两两联合 location list 去挖掘top-$k$并行情节
- 反复调用上两步直到挖掘不到频繁情节
算法
个人总结
因为 EMMA 算法因为阈值设定原因，会忽略掉那些本可以与其它情节组成频繁情节的非频繁情节，所以TKE把阈值设置成1自增，即考虑了低支持度情节组合的可能。而且与top-$k$高效用项集挖掘一样，list结构同样利用堆实现优先队列结构。这篇算法比较简单，可以作为Episode pattern mining入门算法，了解一下并行情节和串行情节是怎么代码实现的。
参考
- http://www.philippe-fournier-viger.com/spmf/TOP_K_EPISODES.pdf