写在前面：继UP-Span算法之后，研究一下加上top-k之后挖掘效率是否会效果更强，通常而言，top-k领域挖掘算法对密集型数据集效率会有显著的提升，而且针对UP-Span算法的不足，top-k的策略在一定程度上可以解决。

Top-K High Utility Episode Mining from a Complex Event Sequence

样本

定义

• 事件（event）一个事件被定义为 $pair(e, t)$，其中 $e$ 是事件类型，$t$ 是属于 $N^+$ 的事件发生时间点

• 同时事件集（simultaneous event set）当一组事件在同一个时间点 $t$ 发生时，这个事件集叫做同时事件集

• 复杂事件序列（complex event sequence）复杂事件序列 $CES = <(SE_1, t_1), (SE_2, t_2), \dots, (SE_{\rm n}, t_{\rm n})>$ 是一个有序同时事件集序列

• 包含同时事件的情节（episode containing simultaneous event sets）一个情节 $\alpha = <(SE_1), (SE_2), \dots, (SE_{\rm n})>$ 是同时事件的非空完全有序集合

• 发生（occurrence）给定一个情节 ，当1）情节 $\alpha = <(SE_1), (SE_2), \dots, (SE_{\rm m})>$ 发生在时间段 [$ t_{\rm s}, t_{\rm e}$]；2）情节 $\alpha$ 的第一个同时事件集 $SE_1$ 发生在 $T_{\rm s}$ 时间点，最后一个同时事件集 $SE_{\rm m}$ 发生在 $t_{\rm e}$ 时间点，那么称时间间隔 [$t_{\rm s}, t_{\rm e}$] 为情节 $\alpha$ 的出现。其中，情节 $\alpha$ 的所有发生组成集合命名为 $occSet(\alpha)$ 。例如：情节 $occ<(E), (D)> = \lbrace [1,3], [3,3], [1,5], [3,5]\rbrace$

• 最小发生（minimal occurrence）给定情节 $\alpha$ 的两个时间间隔 [$t_{\rm s}, t_{\rm e}$], [$t_{\rm s}’, t_{\rm e}’$]，[$t_{\rm s}’, t_{\rm e}’$] 是 [$t_{\rm s}, t_{\rm e}$] 的子集：当1）[$t_{\rm s}, t_{\rm e}$] 是情节 $\alpha$ 的出现；2）时间间隔 [$t_{\rm s}’, t_{\rm e}’$] 不存在子集。最小发生记为 $minOcc(\alpha)$。其中，情节 $\alpha$ 的所有最小发生组成集合 $minOccSet(\alpha)$。例如：$minOccSet(<(E), (D)>) = \lbrace [1,3], [3,3], [3,5]\rbrace$

• 内部效用和外部效用（internal and external utility）在情节效用挖掘中，每一个事件 $e_{\rm i}$ 都关联着一个正外部效用 $p(e_{\rm i})$ 和正内部效用 $q(e_{\rm i}, t_{\rm j})$

• 事件在某个时间点的效用值（utility of an event at a time point）在某个时间点 $ t_{\rm i} \in N^+$ 下某个事件 $E_{\rm i}$ 的效用定义为 $u(e_{\rm i}, t_{\rm i}) = p(e_{\rm i}) \times q(e_{\rm i}, t_{\rm i})$

• 同时事件集在某个时间点的效用值（utility of a simultaneous event set at a time point）在某个时间点 $t_{\rm i} \in N^+$ 下某个同时事件集 $SE = (e_1, e_2, \dots, e_{\rm n})$ 的效用定义为 $u(SE, T_{\rm i}) = \sum_{j = 1}^{n}u(e_{\rm j}, t_{\rm i})$。例如：$u(<(GF)>, t_6) = (2 \times 1) + (3 \times 1)$

• 情节关于最小发生的效用值（utility value of an episode w.r.t its minimal occurrence）设 $minOcc(\alpha) = [t_{\rm s}, t_{\rm e}]$ 是情节 $\alpha = <(SE_1, SE_2, \dots, SE_{\rm n})>$ 的最小发生，其中每一个同时事件集 $SE_{\rm i} \in \alpha$ 都与某一个时间点 $T_{\rm i} \in N^+$ 相关联。那么情节关于最小发生的效用值定义为 $u(\alpha, minOcc(\alpha)) = \sum_{i = 1}^{n}u(SE_{\rm i}, t_{\rm i})$，其中 $t_{\rm s} \le t_{\rm i} \le t_{\rm e}$

• 复杂事件序列情节的总效用值（utility of an episode in a complex event sequence）设 $minOccSet(\alpha) = [minOcc_1(\alpha), minOcc_2(\alpha), \dots, minOcc_{\rm n}(\alpha)]$ 是关于情节 $\alpha$ 的最小发生集。而基于复杂事件序列 $CES$ 的情节效用定义为 $uv(\alpha, CES) = \sum_{i = 1}^{n}u(\alpha, minOcc_{\rm i}(\alpha))$，并且有 $u(\alpha) = uv(\alpha) / u(CES)$

• 高效用情节（high utility episode(HUE)）当一个情节的效用值大在给定的 $MTD$ 中大于或等于阈值时，该情节称为高效用情节

• 最长时间段（maximum time duration）设 $MTD$ 是用户预先设定的最长持续时间，$mo(\alpha) = [t_{\rm s}, t_{\rm e}]$ 是情节 $\alpha$ 的最小发生间隔。当 $(t_{\rm e} - t_{\rm s} + 1) \le MTD$，称 $mo(\alpha)$ 受 $MTD$ 的约束（或者是满足）

• 同时串行连接（simultaneous and serial concatenations）设 $\alpha = <(SE_1), (SE_2), \dots, (SE_{\rm x})>$, $\beta = <(SE_1’), (SE_2’), \dots, (SE_{\rm y}’)>$，$\alpha$ 和 $\beta$ 的同时连结定义为 $simul$-$concat(\alpha, \beta) = <(SE_1),(SE_2) \dots, (SE_{\rm x} \cup SE_1’), (SE_2’), (SE_{\rm y}’)>$，$\alpha$ 和 $\beta$ 的串行连接定义为 $serial$-$concat(\alpha, \beta) = <(SE_1), (SE_2)$, $\dots, (SE_{\rm x}), (SE_1’), (SE_2’), \dots, (SE_{\rm y}’)>$（Ps. 这个类似于扩展项集）

  例如：设 $\alpha = <(B), [4, 4]>, \beta = <(D), [5, 5]>$，那么由串行连接新生成的情节 $\gamma = <(B, D), [4, 5]>$；若此时令 $\alpha = <(A), [5, 5]>$，则 $\gamma = <(B, DA), [4, 5]>$

  同样地，该概念也具有向下封闭（EWDC）的特性，即：设 $\alpha$ 和 $\beta$ 都是情节，且 $\gamma $=$ simul$-$concat(\alpha, \beta)$ 或 $serial$-$concat(\alpha, \beta)$，当 $EWU(\alpha) < minUtil$ 时，$\gamma$ 是低效用情节

• 关于最小发生时间的情节权重效用（episode-weighted utilization of an episode w.r.t a minimal occurrence）设 $mo(\alpha) = [t_{\rm s}, t_{\rm e}]$ 是情节 $\alpha = <(SE_1), (SE_2), \dots, (SE_{\rm n})>$ 最小发生时间段，其中 $mo(\alpha)$ 受 $MTD$ 的约束。那么在时间段 [$t_{\rm s}, t_{\rm e}$] 下情节 $\alpha$ 的情节权重效用 $EWU(\alpha, mo(\alpha)) $=$\sum_{i = 1}^{n}u(SE_{\rm i}, t_{\rm i}) + \sum_{i = e}^{(s + MTD - 1)}u(t_{SE_{\rm i}}, t_{\rm i})$，其中 $t_{SE_{\rm i}}$ 是在 $CES$ 中同时事件集的时间点 $t_{\rm i}$

• 情节效用权重（episode-weighted utilization of an episode）设 $minOccSet(\alpha) = [t_{\rm I_1}, t_{\rm I_2}, \dots, t_{\rm I_n}]$ ，且$t_{\rm I_i} \in minOccSet(\alpha)$ 满足 $MTD$ 约束。那么基于复杂事件序列 $CES$ 的情节 $\alpha$ 效用权重 $EWU(\alpha) = $$\sum_{i = 1}^{n}EWU(\alpha, t_{\rm I_i}) / u(CES)$

• 高权重效用情节（high weighted utilization episode）当一个情节 $\alpha$ 的 $EWU(\alpha) \ge minUtil$ 时，该情节称为高权重效用情节

策略

Pre-insertion Strategy

简而言之就是把计算得到的情节效用插入到 top-k list 中，直到得到第 $k^{th}$ 个效用值作为新的阈值，来达到在挖掘高效用情节之间快速提升阈值的目的

EWU Strategy

通过对计算得到的各情节EWU进行排序（在连接操作之前进行）利用EWU填充 top-k list，以便快速提升阈值和剪枝

Ps. 举例部分有些不能理解，或许检查代码能有新思路

算法

TUP-Basic

• 和高效用挖掘一样，寻找低层次高效用情节，利用这些情节作为前缀去构造高层次高效用情节
• 通过连接形成的新情节 $\beta$，再调用 Insert_Episode()，用来更新 top-k 情节列表

SimultConcatenation

主要负责挖掘当前事件集的同时事件

SerialConcatenation

主要负责挖掘当前事件集的连续事件

Raise MinUtil

个人总结

算法还有部分没有理解，需要再看看论文，从实验数据上看该算法性能表现比较好，但个人认为使用的阈值提升策略不够多，反单调性应用面窄，还有很大的提升空间。